Теория двойственности в линейном программировании

Лекция 3. Теория двойственности в линейном программировании 3.1 Экономическая интерпретация теории двойственности в линейном программировании. Любую деятельность в народном хозяйстве, отрасли или на конкретном предприятии можно рассматривать как процесс затраты определенных ресурсов и выпуска некоторой продукции. Процесс этот может происходить в различных формах, выполняться с применением различных ресурсов. Ресурсы, как правило, ограничены, причем эффективность их применения в различных процессах не одинакова. Поэтому возникает необходимость применения аппарата линейного программирования для решения различных задач оптимального планирования и организации производства. Теория двойственности в линейном программировании устанавливает связь между оптимальным распределением ресурсов и некоторой системой оценок на ресурсы, соответствующих оптимальному плану. Допустим, что предприятие имеет в своем распоряжении m видов ресурсов в количестве bi (i = 1, 2,…, m) единиц, из которых производится n видов продукции. Для производства единицы продукции j – го вида (j = 1, 2,…, n) расходуется aij единиц i – го ресурса. Прибыль от реализации единицы продукции j – го вида равна cj денежных единиц. Требуется составить такой план выпуска продукции, при котором предприятие получает максимальную прибыль. Обозначим через xj (j = 1, 2,…, n) количество продукции j – го вида, выпускаемое на предприятии. Тогда, с учетом принятых обозначений, функция цели принимает вид: Z = c1x1 + c2x2 + … + cnxn  max (3.1) Ограничения по использованию ресурсов записываются в виде: a11x1 + a12x2 + … + a1nxn  b1 a21x1 + a22x2 + … + a2nxn  b2 ………………………………………(3.2) am1x1 + am2x2 + … + amnxn  bm Переменные xj (j = 1, 2,…, n) по смыслу задачи являются неотрицательными, т.е. xj  0; j = 1, 2,…, n (3.3) Предположим теперь, что при изучении вопроса об использовании ресурсов на предприятии появилась другая возможность – прямая реализация ресурсов на сторону. Иначе говоря, некоторая организация решила закупить ресурсы предприятия и необходимо установить оптимальные цены на эти ресурсы. При определении цен на ресурсы предприятие руководствуется следующими принципиальными положениями: 1. цена единицы ресурса i - го вида (pi) не может быть ниже его себестоимости (si), т.е. pi  si (i = 1, 2,…, m), ибо в противном случае предприятие терпит прямые убытки от реализации ресурсов; 2. при реализации всех ресурсов по их себестоимости предприятие не получает никакой прибыли. Если при оптимальном использовании ресурсов предприятие получает некоторую (пусть даже незначительную) прибыль, то оно никогда не будет продавать имеющиеся в его распоряжении ресурсы по их себестоимости. Таким образом, цена за единицу ресурса (pi) будет складываться из его себестоимости (si) и некоторой неотрицательной оценки (yi), т.е. pi = si + yi; (i = 1, 2,…, m). Следует отметить, что искомые оценки будут относительными, так как одни и те же ресурсы для разных предприятий представляют различную ценность. Кроме изменением объемов ресурсов. того, оценки должны изменяться с Покупающая организация заинтересована в том, чтобы затраты на все ресурсы в количествах b1, b2,…, bm ,были минимальны, т.е. m m i 1 i 1 b1  s1  y1   b2  s2  y2   ...  bm  sm  ym    bi si   bi yi  min Первая сумма в правой части равенства представляет собой суммарную себестоимость имеющихся на предприятии ресурсов, т.е. является величиной постоянной и представляет собой ту денежную сумму, которая в любом случае взимается с покупателя. Переменной же величиной, которая заслуживает детального изучения, является вторая сумма в приведенном выше выражении. Она представляет собой денежную сумму, выплачиваемую покупателем владельцу ресурсов, сверх суммарной себестоимости имеющихся ресурсов. Эта величина получила название суммарной оценки ресурсов. Таким образом, покупатель заинтересован в минимизации суммарной оценки ресурсов, т.е. f = b1y1 + b2y2 + … + bmym  min (3.4) С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная суммарная оценка ресурсов была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. Иначе говоря: Прямая реализация ресурсов целесообразна только в случае, когда оценка всех ресурсов, расходуемых на изготовление единицы продукции каждого вида не меньше, чем прибыль от реализации единицы продукции. На изготовление единицы продукции j – го вида (j = 1, 2,…, n) расходуется a1j единиц ресурса 1 – го вида, a2j единиц ресурса 2–го вида,…, amj единиц ресурса m – го вида с оценками соответственно y1, y2,…, ym. Поэтому, отмеченное выше требование приобретает вид: a1jy1 + a2jy2 + … + amjym  cj; j = 1, 2,…, n: a11y1 + a21y2 + … + am1ym  c1 a12y1 + a22y2 + … + am2ym  c2 ………………………………………….(3.5) a1ny1 + a2ny2 + … + amnym  cn, причем, оценки ресурсов не могут быть отрицательными, т.е. yi  0; i = 1, 2,…, m. (3.6) Две задачи линейного программирования (3.1) – (3.3) и (3.4) – (3.6), получили название пары двойственных задач. Одну из задач линейного программирования (не играет роли, какую именно) называют прямой задачей, а другую – двойственной. 3.2. Симметричные и несимметричные двойственные задачи. Абстрагируясь от экономической интерпретации пары двойственных задач линейного программирования, рассмотрим связь между ними. Рассмотренные задачи (3.1) – (3.3) и (3.4) – (3.6) обладают следующими свойствами (для определенности будем считать задачу на максимум – прямой, а на минимум – двойственной): 1. условия неотрицательности переменных имеются в обеих задачах; 2. прямая задача решается на максимум, двойственная – на минимум; 3. коэффициенты целевой функции прямой задачи являются свободными членами в двойственной, и наоборот, свободные члены прямой задачи являются коэффициентами целевой функции в двойственной; 4. в прямой задаче ограничения заданы неравенствами типа «», а в двойственной – неравенствами типа «»; 5. матрицы коэффициентов в системах ограничений обеих задач являются транспонированными друг к другу; 6. число ограничений одной задачи совпадает с числом переменных в другой задаче. Две задачи линейного программирования, обладающие указанными свойствами, называются симметричными двойственными задачами. Симметричная пара двойственных задач характеризуется тем, что как в прямой, так и в двойственной задаче, ограничения задаются неравенствами. Приведем примеры симметричных двойственных задач. Пример 1. Исходная задача Двойственная задача: Z = 2x1 + x2 + 5x3  min f = 4y1 + 5y2 + 6y3  max x1 + x2 + x3  4 y1 + y2 + 2y3  2 x1 – 2x2 + 2x3  5 y1 – 2y2 – 2y3  1 2x1 – 2x2 + 3x3  6 y1 + 2y2 + 3y3  5 xj  0; j = 1, 2, 3. yi  0; i = 1, 2, 3. Пример 2. Исходная задача: Двойственная задача: Z = 7x1 + 13x2 + 8x3  max f = 3y1 + 4y2 + 2y3 + 5y4  min x1 + 2x2  3 x1 + x3  4 x1 + 3x2 + 2x3  2 x1 + x2  5 xj  0; j = 1, 2, 3 y1 + y2 + y3 + y4  7 2y1 + 3y3 + y4  13 y2 + 2y3  8 yi  0; i = 1, 2, 3, 4. Рассмотрим теперь случай, когда система ограничений одной из задач двойственной пары (например, система (3.2)) задана в виде уравнений. Рассмотрим произвольное ограничение: ak1x1 + ak2x2 + … + aknxn = bk; (k = 1, 2,…, m) Данное равенство можно заменить системой двух неравенств: ak1x1 + ak2x2 + … + aknxn  bk ak1x1 + ak2x2 + … + aknxn bk Для того чтобы оба неравенства имели тип «», умножим второе ограничение на – 1. Тогда получим: ak1x1 + ak2x2 + … + aknxn  bk – ak1x1 – ak2x2 – … – aknxn  – bk Таким образом, исходная задача имеет систему ограничений в виде неравенств типа «». Поставим теперь в соответствие первому ограничению двойственную переменную yk, а второму – yk. Используя теперь свойства 1. – 6. для пары симметричных двойственных задач, получим запись двойственной задачи: f = b1(y1 – y2) + b2(y2 – y2) + … + bm(ym – ym)  min a11(y1 – y1) + a21(y2 – y2) + … + am1(ym – ym)  c1 a12(y1 – y1) + a22(y2 – y2) + … + am2(ym – ym)  c2 ……………………………………………….. a1n(y1 – y1) + a2n(y2 – y2) + … + amn(ym – ym)  cn yi  0; yi  0; i = 1, 2,…, m. С помощью введения обозначений yi = yi – yi (i = 1, 2,…, m), полученная задача сводится к виду (3.4) – (3.6). Однако следует отметить, что в данной ситуации переменные yi могут принимать любые (в том числе и отрицательные) значения. Итак, если в исходной задаче линейного программирования ограничения заданы в виде уравнений, то двойственная задача имеет тот же вид, что и в случае симметричной пары, за одним исключением: двойственные переменные могут принимать произвольные значения. Пример 3. Исходная задача: Двойственная задача: Z = x1 + x2 + x3 – 2x4  max f = 3y1 + 3y2  min 2y1 – 2y2  1 2x1 + x2 + 2x3 +2x4 = 3 y1 + y2  1 –2x1 + x2 + 4x3 + 2x4 = 3 xj  0; j=1, 2, 3, 4. 2y1 + 4y2  1 2y1 + 2y2  – 2 Пример 4. Исходная задача: Z = 2x1 + 3x2 – x3 + 4x4  min Двойственная задача: f = 2y1 + 12y2 + 13y3  max 2x1 + x2 – x3 + 2x4 = 2 2y1 + 5y2 + y3  2 5x1 – x2 + x3 + 3x4 = 12 y1 – y2 + 2y3  3 x1 + 2x2 + 3x3 – x4 = 13 -y1 + y2 + 3y3  -1 xj  0; j = 1, 2, 3, 4. 2y1 + 3y2 – y3  4 3.3.Основное неравенство и малая теорема двойственности. Запишем пару двойственных задач (3.1) – (3.3) и (3.4) – (3.6) с помощью знаков суммирования. Исходная задача: n Z   c j x j  max (3.1) j 1 n _____ a ij j 1 x j  bi ; i  1, m ____ x j  0; (3.2) (3.3) j  1, n Двойственная задача: m F   bi yi  min (3.4) i 1 m a ij i 1 _____ yi  c j ; j  1, n ____ (3.5) (3.6) yi  0; i  1, m Теорема. (Основное неравенство теории двойственности). Для любых допустимых решений X=(x1,x2,…,xn) и Y=(y1,y2,…,ym) пары двойственных задач справедливо неравенство: n m c x  b y j 1 j j i 1 i i (3.7) Доказательство: Учитывая соотношения (3.2) и (3.5), получим: m m  n   m  c j x j     aij yi  x j     aij x j  yi   bi yi  j 1 j 1  i 1 i 1  j 1 i 1   n n Отсюда получаем требуемое неравенство (3.7). Теорема доказана. Мы провели доказательство для симметричной пары двойственных задач. Нетрудно убедиться, что оно справедливо и для несимметричной пары. Экономическое содержание основного неравенства (3.7) состоит в том, что для любого допустимого плана производства X = (x1, x2,…, xn) и любого допустимого вектора оценок ресурсов Y = (y1, y2,…, ym) общая прибыль от реализации продукции не превосходит суммарной оценки ресурсов. Теорема Если для некоторых допустимых решений Х = (х1,x2,…,xn) и Y = (y1,y2,…,ym) пары двойственных задач выполняется равенство n m c x  b y j 1 j  j i i 1  i (3.8) то векторы Х и Y являются оптимальными решениями соответствующих задач. Доказательство: Согласно основному неравенству, любое допустимое решение X = (x1, x2,…, xn) исходной задачи удовлетворяет условию n m c x  b y j 1 j j i 1 i  i Откуда, учитывая равенство (8), получаем: n n c x  c x j 1 j j j 1 j  j и так как это неравенство справедливо для любого допустимого решения Х исходной задачи, то Х является оптимальным планом исходной задачи. Аналогично доказывается оптимальность решения Y двойственной задачи. Следовательно, условие (3.8) является достаточным, для того чтобы Х и Y являлись оптимальными решениями соответствующих задач двойственной пары. Таким образом, план производства и вектор оценок ресурсов являются оптимальными, если прибыль от реализации всей произведенной продукции и суммарная оценка ресурсов совпадают. Теорема. (малая теорема двойственности). Для существования оптимального решения любой из задач двойственной пары необходимо и достаточно существование допустимого решения для каждой из них. Доказательство: Необходимость очевидна, так как оптимальное решение входит в класс допустимых решений, т.е. для существования оптимального решения необходимо наличие допустимого решения. Достаточность: Пусть Y = (y1, y2,…, ym) – произвольное допустимое решение двойственной задачи. Тогда любое допустимое решение X = (x1, x2, …, xn) исходной задачи удовлетворяет неравенству n m c x  b y j 1 j j i 1 i i  n откуда следует, что линейная форма Z   c j x j ограничена на непустом j 1 множестве допустимых решений исходной задачи. Следовательно, существует оптимальное решение исходной задачи. Аналогичными рассуждениями доказывается разрешимость двойственной задачи. Теорема доказана. 3.4. Первая основная теорема двойственности и ее экономическая интерпретация. Теорема. (первая основная теорема двойственности). Если одна из задач двойственной пары имеет оптимальное решение, то и другая имеет оптимальное решение, причем оптимальные значения целевых функций равны. Если функция цели одной из задач не ограничена, то область допустимых решений другой задачи пуста. Доказательство: Возьмем симметричную пару двойственных задач (4.1) – (4.3) и (4.4) – (4.6). Сформулируем исходную задачу как задачу на минимизацию линейной формы (для этого достаточно умножить целевую функцию на –1, так как для линейной функции max Z = min (– Z)). Введя дополнительные переменные xn+1, xn+2,…, xn+m, получим: – Z = – c1x1 – c2x2 – … – cnxn  min (3.1) a11x1 + a12x2 + … + a1nxn + xn+1 = b1 a21x1 + a22x2 + … + a2nxn + xn+2 = b2 ………………………………………………..(3.2) am1x1 + am2x2 + … + amnxn + xn+m = bm xj  0; j = 1, 2,…, n+m. (3.3) Введя дополнительные переменные ym+1,ym+2,…,ym+n для двойственной задачи, и умножая полученные равенства на –1 (для образования единичного базиса) получим: F = b1y1 + b2y2 + … + bmym  min (3.4) – a11y1 – a21y2 – … – am1ym + ym+1 = – c1 – a12y1 – a22y2 – … – am2ym + ym+2 = – c2 ………………………………………………….(3.5) – a1ny1 – a2ny2 – … - amnym + ym+n = – cn yi  0; i = 1, 2,…, m+n. ……..(3.6) Между неизвестными x1, x2,…, xn+m, исходной задачи и неизвестными y1, y2,…, ym+n двойственной задачи установим взаимно однозначное соответствие: x1  ym+1; x2  ym+2;…xn  ym+n; xn+1  y1; xn+2  y2;…, xn+m  ym, (3.9) так что базисным неизвестным одной задачи соответствуют свободные неизвестные другой. В исходной задаче базисными являются неизвестные xn+1, xn+2,…, xn+m, а в двойственной – ym+1, ym+2,…, ym+n (мы рассматриваем теперь и такие базисы, в которых условие неотрицательности свободных членов в системе ограничений не выполняется). При установленном соответствии между неизвестными проявляется следующее свойство коэффициентов: если xn+i – базисная, а xj – свободная неизвестные исходной задачи; yi и ym+j – соответствующие им свободная и базисная неизвестные двойственной задачи, то коэффициент, с которым yi входит в уравнение, содержащее ym+j, только знаком отличается от коэффициента, с которым xj входит в уравнение, содержащее xn+i. Более того, если для каждой из задач двойственной пары составить первые симплексные таблицы, то элементы столбца свободных членов одной таблицы только знаками будут отличаться от соответствующих элементов последней строки другой таблицы. Пусть в одной из задач рассматриваемой пары, например, в исходной, преобразуем базис: неизвестная xs входит в базис вместо неизвестной xn+r (предполагаем, что ars  0). Условимся сопровождать такую замену соответствующей заменой базиса в двойственной задаче: неизвестную ym+s выведем из базиса и введем вместо нее yr. Оказывается, при этом отмеченное выше свойство коэффициентов и связь между элементами симплексных таблиц сохраняются. Действительно, при исключении неизвестной xs из всех уравнений системы (3.2) кроме r – го, элемент aij преобразуется по закону: aij aij – aisarj/ars, а соответствующий ему элемент – aij системы (3.5) при соответствующей замене, путем исключения неизвестной yr из всех уравнений кроме s-го, преобразуется по закону: – aij – aij – (– arj)( – ais)/( – ars)= – (aij – aisarj/ars), и аналогично преобразуются элементы столбца свободных членов и последней строки (оценочных коэффициентов) симплексных таблиц, т.е. наше утверждение о связи между элементами остается справедливым и для следующей пары симплексных таблиц. Если исходная задача имеет оптимальное решение, то через конечное число шагов получится окончательная симплексная таблица, в которой в последней строке среди оценочных коэффициентов не будет ни одного положительного, а в столбце свободных членов – ни одного отрицательного элемента, кроме, может быть, значения целевой функции. Ей отвечает определенная симплексная таблица двойственной задачи, в которой в силу указанного соответствия, столбец свободных членов не будет содержать ни одного отрицательного элемента, кроме, может быть, значения целевой функции, а в последней строке не будет ни одного положительного оценочного коэффициента, так как в последней строке симплексной таблицы двойственной задачи стоят те же числа, что и в столбце свободных членов симплексной таблицы исходной задачи, лишь умноженные на (– 1). Это означает, что для двойственной задачи также получено оптимальное решение, причем минимальное значение функции – Z только знаком отличается от минимального значения функции F, т.е. min F = max Z и первая часть теоремы доказана. Перейдем к доказательству второй части теоремы. Пусть функция Z не ограничена сверху, т.е. –Z не ограничена снизу. Тогда на некотором этапе решения исходной задачи симплексным методом получится таблица, в которой для некоторого оценочного коэффициента qk = Zk – Ck > 0 среди расположенных над ним коэффициентов его столбца не будет ни одного положительного. В соответствующей строке сопутствующей симплексной таблицы двойственной задачи свободный член будет отрицательным, а среди коэффициентов при неизвестных не будет ни одного отрицательного. Уравнение, соответствующее такой строке, не может обратиться в тождество при неотрицательных значениях неизвестных. Это означает противоречивость системы ограничений двойственной задачи в области неотрицательных решений, т.е. область допустимых решений двойственной задачи пуста. Теорема доказана полностью. Остается рассмотреть экономическую интерпретацию первой основной теоремы двойственности. В терминах оценок она может быть сформулирована оптимального следующим плана, образом: если максимизирующего задача прибыль определения от реализации продукции, разрешима, то разрешима и задача определения минимальных оценок ресурсов, причем прибыль, полученная реализацией оптимального плана, совпадает с суммарной оценкой ресурсов. Можно сказать, что оценки выступают как инструмент балансирования затрат и результатов. 3.5.Решение симметричных двойственных задач. При доказательстве первой основной теоремы двойственности было выяснено, что, решая одну из задач двойственной пары задач линейного программирования, мы автоматически решаем и другую. Соотношения между переменными прямой и двойственной задач определяются формулами (3.9), причем значения переменной одной из задач являются оценками целевой, (m + 1) – й, строки в другой задаче. Указанные свойства двойственных задач могут успешно применяться в тех случаях, когда поставленная перед исследователем задача является трудоемкой в вычислительном плане. В данном случае целесообразнее построить двойственную задачу (которая решается существенно проще) и, решив ее указать оптимальное решение исходной задачи. Наиболее распространенным случаем такого рода является приведенный в таблице 3.1. Таблица 3.1. Задача 1 (исходная) Задача 2 (двойственная) Z = CX  min F = BY  max AX  B YA  C X0 Y0 При решении исходной задачи, в условиях неотрицательности В, применяется алгоритм метода искусственного базиса, который является довольно трудоемким. Используя симметричность можно вместо исходной задачи выбрать более удобную двойственную задачу, решаемую по алгоритму симплексного метода. Пример 5. Решить задачу линейного программирования F = x1 + x2 + x3 + x4  min 3x1 + 2x2 + x3  80 x1 + 6x2 + 9x3 + 13x4  40 xj  0; j =1, 2, 3, 4. Построим двойственную задачу: Z = 80y1 +40y2  max 3y1 + y2  1 2y1 + 6y2  1 y1 + 9y2  1 13y2  1 y1  0; y2  0. В исходной задаче четыре основные неизвестные и две дополнительных х5 и х6 (вводимые для того, чтобы привести систему ограничений к уравнениям). В двойственной задаче две основные неизвестные и четыре дополнительных (y3, y4, y5, y6). Таким образом, система соответствий (3.9) в нашем случае приобретает вид: x1  y3; x2  y4; x3  y5; x4  y6; x5  y1; x6  y2, т.е. значения переменных исходной задачи будут получены из (m + 1) – й строки последней симплекс-таблицы двойственной задачи по правилу: xj = qj = Zj – Cj (j = 1, 2,…, 6) Введя в ограничения двойственной задачи дополнительные переменные y3, y4, y5 и y6 приведем их к уравнениям. В этом случае двойственная задача принимает вид: Z = 80y1 +40y2  max 3y1 + y2 + y3 = 1 2y1 + 6y2 + y4 = 1 y1 + 9y2 + y5 = 1 13y2 + y6 = 1 yi  0; i = 1, 2,…, 6. Полученную задачу решаем симплексным методом. Строим первую симплекс-таблицу. Таблица 3.2. i Базис С базиса 80 40 A1 A2 A3 A4 A5 A6 B 1 A3 1 3 1 1 2 A4 1 2 6 1 3 A5 1 1 9 1 4 A6 1 0 13 1 m+1 Zj – Cj –80 –40 Данная задача решается на максимум, следовательно, условием оптимальности является отсутствие отрицательных элементов среди оценок (m + 1) – й строки. Из построенной таблицы видно, что две оценки (q1 и q2) не удовлетворяют условиям оптимальности. 1= min{1/3; 1/2; 1/1}=1/3; |1q1| = |1(Z1 – C1) | = 80/3; 2 = min{1/1; 1/6; 1/9; 1/13}=1/13; |2q2|=|2(Z2 – C2)|=40/13; max|jqj| = 80/3. Следовательно, разрешающим элементом является число 3, стоящее на пересечении первой строки и столбца А1. Используя алгоритм симплексного метода, переходим к следующей таблице. Таблица 3.3. i Базис С базиса 80 40 A1 A2 A3 A4 A5 A6 B 1 A1 80 1/3 1 1/3 1/3 2 A4 1/3 16/3 –2/3 1 3 A5 2/3 26/3 –1/3 1 4 A6 13 1 80/3 Zj – Cj m+1 1 0 –40/3 80/3 Полученный план вновь не является оптимальным, так как в (m+1)-й строке оценка q2 = Z2 – C2 = – 40/3 < 0. Это означает, что вектор А2 следует ввести в базис: 2 = min{1; 1/16; 1/13; 1/13} = 1/16. Следовательно, разрешающим элементом является число 16/3, стоящее на пересечении второй строки и столбца А2 (из базиса выводится вектор А4). Составляем следующую симплексную таблицу. Таблица 3.4. i Базис С B 80 40 базиса A1 A2 A3 A4 –1/16 1 A1 80 5/16 1 3/8 2 A2 40 1/16 1 –1/8 3 A5 1/8 3/4 4 A6 3/16 13/8 55/2 m+1 Zj – Cj A5 A6 –13/8 1 –39/16 1 5/2 3/16 25 Полученный план является оптимальным, т.к. среди оценок (m+1) –й строки нет отрицательных. Итак, оптимальный план двойственной задачи: y1 = 5/16; y2 = 1/16; y3 = y4 = 0; y5 = 1/8; y6 = 3/16; Fmin = Zmax = 55/2. Значения переменных исходной задачи находим из (m + 1) – й строки последней симплексной таблицы двойственной задачи по правилу: xj = qj. Итак: x1 = 25; x2 = 5/2; x3 = x4 = x5 = x6 = 0. 3.6. Двойственный симплексный метод. Как следовало из доказательства первой основной теоремы двойственности, принципиально допустимо решать задачу линейного программирования, когда среди свободных членов в системе ограничений имеются отрицательные числа. В процессе реализации соответствующего алгоритма, получившего название двойственного симплексного метода, мы получаем допустимое (если область допустимых решений не пуста) и оптимальное (если функция цели ограничена) решение. Итак, для решения задачи линейного программирования применяется алгоритм двойственного симплексного метода, если система ограничений задачи задана в виде уравнений, содержит единичный базис, но среди свободных членов имеются отрицательные числа. Пусть bk < 0, тогда k – е ограничение имеет вид: ak1x1 + ak2x2 + … + aknxn = bk (3.10) Если все akj  0 (j = 1, 2,…, n), то задача линейного программирования не имеет решения из-за пустоты области допустимых решений. Действительно, если все akj  0, то в силу неотрицательности переменных xj все слагаемые в левой части равенства (4.10) будут неотрицательны, их сумма также будет неотрицательной величиной и, следовательно, не может быть равна bk < 0. Если же некоторые akj < 0, то для столбцов, содержащих эти отрицательные значения, вычисляем j = min{bi/aij}  0. Отметим, что разрешающим элементом в данном случае может быть и отрицательное число, важно чтобы отношение bi /aij было неотрицательным. Если j = 0 (т.е. bi = 0), то aij берется за разрешающий элемент только в том случае, если aij>0. Такой выбор разрешающего элемента на данном этапе не приводит к увеличению количества отрицательных компонент вектора X = (x1,x2,…,xn). Процесс решения задачи разбивается на два этапа. На первом этапе необходимо избавиться от отрицательности в столбце свободных членов, на втором – полученную задачу решаем симплексным методом. Пример. Решить задачу линейного программирования двойственным симплексным методом: Z = x1 + x2  min x1 + 2x2  14 – 5x1 + 3x2  15 4x1 + 6x2  24 x1  0; x2  0. Введя дополнительные переменные x3, x4 и x5, сведем систему ограничений к уравнениям. Тогда задача примет вид: Z = x1+ x2  min x1 + 2x2 + x3 = 14 – 5x1 + 3x2 + x4 = 15 4x1 + 6x2 – x5 = 24 xj  0; j=1,2,…5. Полученная система уравнений содержит два единичных вектора (коэффициенты при переменных х3 и х4). Для получения третьего единичного вектора умножим третье уравнение на – 1. Тогда задача преобразуется к виду: Z = x1+ x2  min x1 + 2x2 + x3 = 14 – 5x1 + 3x2 + x4 = 15 – 4x1 – 6x2 + x5 = – 24 xj  0; j = 1, 2,…,5. Составим первую симплексную таблицу. Таблица 3.5. i Базис С базиса 1 1 A1 A2 A3 A4 A5 B 1 A3 14 2 A4 15 –5 3 A5 m+1 Zj – Cj –24 1 2 1 3 1 –4 –6 1 –1 –1 Так как х5 = – 24 < 0, то просматриваем элементы третьей строки. Среди них имеются два отрицательных коэффициента, стоящие в столбцах, соответствующих векторам А1 и А2. Имеем: 1 = min (14/1; – 24/ – 4) =6; 1q1= 6( – 1)= – 6; 2 = min(14/2; 15/3; – 24/ – 6) = 4; 2q2 = 4( – 1) = – 4. Вводя в базис вектор А1, мы увеличиваем значение целевой функции на 6, а вводя вектор А2 – на 4. Поэтому вводим в базис вектор А2. Используя алгоритм симплексного метода, переходим к следующей симплексной таблице. Таблица 3.6. i Базис С базиса A3 6 2 A4 3 3 A2 1 4 4 Zj – Cj 1 A1 A2 A3 A4 A5 B 1 m+1 1 –1/3 1 1/3 1 1/2 2/3 1 –1/6 –1/3 –1/6 –7 В данной таблице получен оптимальный план: Zmin = 4; x1 = 0; x2 = 4; x3 = 6; x4 = 3; x5 = 0. Предложенная процедура выбора разрешающего элемента не является оптимальной для всех задач линейного программирования, решаемых двойственным симплексным методом. Однако она не приводит к увеличению количества отрицательных переменных. В случае если все элементы столбца свободных членов отрицательны, j следует выбирать не по минимуму, а по максимуму отношений, т.е. j = max(bi/aij) > 0. Пример. Решить задачу линейного программирования двойственным симплексным методом: Z = 2x1+8x2+x3+5x4  min 2x1 – x2 + 3x3 – x4 + x5 = – 18 – x1 – 2x2 – 4x3 – 2x4 + x6 = – 24 – 3x1 – 4x2 – 2x3 + 3x4 + x7 = – 30 xj  0; j = 1, 2,…, 7. Построим первую симплексную таблицу, введя в базис векторы А5, А6 и А7. Таблица 3.7 i С Базис 2 8 1 5 A1 A2 A3 A4 A5 A6 A7 B базиса 1 A5 –18 2 –1 3 –1 1 2 A6 –24 –1 –2 –4 –2 1 3 А7 –30 –3 –4 –2 3 1 –2 –8 –1 –5 m+1 Zj - Cj В данной таблице все значения переменных отрицательны. В базис введем вектор А2, т.к. в этом столбце все элементы отрицательны, а это позволяет избавиться от наибольшего количества отрицательных элементов в столбце свободных членов: 2 = max(– 18/ – 1; – 24/ – 2; – 30/ – 4) = 18. Таким образом, в базис входит вектор А2, исключается из базиса вектор А5, разрешающий элемент = – 1. Таблица 3.8 i 1 Базис A2 С базиса 8 2 8 1 5 A1 A2 A3 A4 A5 A6 A7 B 18 –2 1 –3 1 –1 –10 –2 1 42 –11 –14 7 –4 1 –18 –25 3 –8 2 A6 12 3 А7 m+1 Zj – Cj 144 –5 В полученной таблице столбец В не содержит отрицательных элементов, следовательно, далее задачу решаем обычным симплексным методом. План, помещенный в таблице 3.8. не является оптимальным, т.к. в (m+1) – й строке оценка q4 = Z4 – C4 = 3 > 0. Это означает, что вектор А4 следует ввести в базис; 4 = min (18/1; 42/7) = 6. Таким образом, из базиса исключается вектор А7, разрешающий элемент равен 7. Таблица 3.9 i Базис С базиса 2 8 1 5 A1 A2 A3 A4 A5 A6 A7 B 1 A2 8 12 –3/7 2 A6 12 –5 3 А4 5 6 –11/7 –93/7 0 –19 m+1 Zj – Cj 126 1 –1 0 –10 –2 0 –3/7 –2 0 –1/7 1 1 –4/7 0 1/7 0 –44/7 0 –3/7 В таблице 3.9. получен оптимальный план: Zmin = 126; x1 = 0; x2 = 12; x3 = 0; x4 = 6; x5 = 0; x6 = 12; x7 = 0. Пример. Используя двойственный симплексный метод, решить задачу линейного программирования: Z = 2x1 – 5x2  min 4x1 + 3x2 + x3 = 12 – 3x1 – 4x2 + x4 = – 24 xj  0; j = 1, 2, 3, 4. Составим первую симплексную таблицу, введя в базис векторы А3 и А4. Таблица 3.10 i Базис С A3 2 A4 m+1 –5 A1 A2 A3 A4 B базиса 1 2 12 4 –24 Zj – Cj –3 –2 3 –4 5 1 1 Так как х4 = – 24 < 0, то просматриваем коэффициенты второй строки. Среди них два отрицательных коэффициента, стоящие в столбцах, соответствующих векторам А1 и А2. Имеем: 1 = min(12/4; – 24/ – 3) = 3; 1q1 = 3( – 2) = – 6; 2 = min(12/3; – 24/ – 4) = 4; 2q2 = 45 = 20. Таким образом, согласно (3.14), при введении в базис вектора А1 значение целевой функции возрастает на 6, а при введении вектора А2 – уменьшается на 20. Так как задача решается на минимум, то в базис следует ввести вектор А2. Таблица 3.11 i Базис С базиса 2 –5 0 A1 A2 A3 A4 B 1 A2 –5 4 4/3 1 1/3 2 A4 –8 7/3 0 4/3 1 0 –5/3 m+1 Zj – Cj –20 –26/3 В полученной таблице х4 = – 8 < 0. В соответствующей этому элементу второй строке отсутствуют отрицательные элементы. Следовательно, задача линейного программирования не имеет решений изза пустоты области допустимых решений. 3.7. Вторая основная теорема двойственности и ее экономическое содержание. Теорема. Для того чтобы решения X=(x1, x2,…, xn) и Y = (y1, y2, …, ym) пары двойственных задач являлись оптимальными, необходимо и достаточно выполнение условий:  m  x   aij yi  c j   0,  i 1   j _____ j  1, n (3.11) _____  n   y   aij x j  bi   0, i  1, m  j 1   i (3.12) т.е. если какое либо неравенство системы ограничений одной из задач двойственной пары не обращается в точное равенство оптимальным решением этой задачи, то соответствующая компонента оптимального решения двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального решения одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным решением должно обращаться в точное равенство. Доказательство: Необходимость. Пусть X и Y являются оптимальными решениями пары двойственных задач. В этом случае (согласно первой основной теореме двойственности) n c j 1  j jx  m b y i i 1  i В силу же основного неравенства теории двойственности: n c x j j 1 m n m   aij y x   bi yi j i 1 j 1  i  j i 1 Отсюда получаем два равенства n c x j 1 j m b y i 1 i m j  i n   aij yi x j (3.13) i 1 j 1 m n   aij yi x j (3.14) i 1 j 1 Из равенства (4.13) следует, что  m  x   aij yi  c j   0,  j 1  i 1  n  j откуда, учитывая, что все xj и выражения в скобках (в силу (4.5)) неотрицательны, получаем:  m  x   aij yi  c j   0,  i 1   j _____ j  1, n (т.е. сумма неотрицательных выражений равна нулю тогда и только тогда, когда каждое из слагаемых равно нулю) и соотношения (3.11) доказаны. Аналогично, из равенства (3.14) имеем:  n   y   aij x j  bi   0,  i 1  j 1  m  i откуда, учитывая, что все yi неотрицательны, а выражения в скобках (в силу (4.2)) неположительны, получаем: _____  n   y   aij x j  bi   0, i  1, m  j 1   i (т.е. сумма неположительных выражений равна нулю тогда и только тогда, когда каждое из слагаемых равно нулю) и соотношения (3.12) доказаны. Достаточность. Просуммировав равенства (3.11) по j, а равенства (3.12) по i, получим: m n  a i 1 j 1 m ij n  a i 1 j 1 ij n y x   c j x 0j  i  j j 1 m y x   bi yi  i  j i 1 откуда следует, что значения целевых функций пары двойственных задач в точках X и Y равны. Согласно теореме 3.2. решения X и Y являются оптимальными решениями пары двойственных задач. Достаточность, а также и вторая теорема двойственности, полностью доказана. Условия (3.11) – (3.12) часто называют условиями дополняющей нежесткости. Рассмотрим экономическое содержание второй основной теоремы двойственности. Если по некоторому оптимальному плану производства (X) расход i – го ресурса строго меньше его запаса, т.е. n a j 1 ij x j  bi , то в каждом оптимальном плане оценок Y оценка yi единицы этого ресурса равна нулю (yi = 0). Если же оценка единицы ресурса строго больше нуля (yi > 0), то в каждом оптимальном плане производства расход этого ресурса равен его запасу, т.е. n a j 1 Таким образом, оценки ij x j  bi . оптимального плана (названные Л.В. Канторовичем объективно обусловленными оценками) выступают как мера дефицитности ресурсов. Дефицитный ресурс, полностью используемый по оптимальному плану производства, имеет положительную оценку, а не дефицитный ресурс, не полностью используемый, имеет нулевую оценку.