Двойственность линейного программирования

Двойственность линейного программирования ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ МЕНЕДЖМЕНТА Реферат по дисциплине Двойственность линейного программирования» специальности «Менеджмент организации» третьего курса 32 группы Шумакова Ю. А. Проверила Оренбург 2009 Содержание Введение………………………………………………………………..……. 3 1. Виды двойственных задач и составление их математических моделей………………………………………………………………………. 4 2. Основные теоремы двойственности…………………………………….. 6 3. Решение двойственных задач……………………………………………. 7 4. Экономический анализ задач с использованием теории двойственности……………………………………………………………….…. 12 Заключение…………………………………………………...…………….. 18 Библиографический список……………………………………………...... 19 Двойственность в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП. Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной . Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару. 1. Виды двойственных задач и составление их математических моделей Симметричные двойственные задачи Дана исходная задача L (x) = c1x1 + c2x2 +…+ cnxn → max при ограничениях: a11x1 + a12x2 + … + a1nxn ≤ b1 │ y1 , a21x1 + a22x2 + … + a2nxn ≤ b2 │ y2 , ……………………………………… ≤ bm │ ym , xj≥0 , j = 1,n , i = 1,m. Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого: - каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную yi ; - составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи; - составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств меняются на противоположные; Математическая модель двойственной задачи имеет вид S(y) = b1y1 + b2y2 +…+ bmym → min при ограничениях: a11y1 + a12y2 + … + am1ym ≤ c1 , a12y1 + a21y2 + … + am2ym ≤ c2 , ……………………………………… a1ny1 + a2ny2 + … + amnym ≤ cn , yj ≥0 , i = 1,m , j = 1,n. Несимметричные двойственные задачи Дана исходная задача L (x) = c1x1 + c2x2 +…+ cnxn → max при ограничениях: a11x1 + a12x2 + … + a1nxn = b1 │ y1 , a21x1 + a22x2 + … + a2nxn = b2 │ y2 , ……………………………………… am1x1 + am2x2 + … + amnxn = bm │ ym , xj ≥0 , j = 1,n. Задача дана в каноническом виде. Составим математическую модель двойственной задачи. Для ее составления пользуемся тем же правилом, что и для составления симметричной задачи, с учетом следующих особенностей: ≥, если максимум, то ≤ ; - переменные yi - произвольные по знаку. Математическая модель двойственной задачи имеет вид → min при ограничениях: a11y1 + a21y2 + … + am1ym ≥ c1 , a12y1 + a22y2 + … + am2ym ≥ c2 , a1ny1 + a2ny2 + … + amnxn ≥ cn , yj ≥0 , i = 1,m , j = 1,n. Смешанные двойственные задачи Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач. 2. Основные теоремы двойственности ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений X и Y выполняется равенство L(x)max = S(y)min. L(x)max→ ∞ (или S(y)min→ - ∞), то другая задача не имеет допустимых решений. ТЕОРЕМА 2. Для оптимальности допустимых решений X и Y пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений ∑aijyопт i - cj ) = 0, yопт i ( ∑aijxоптj - bi ) = 0. Теоремы позволяют определить оптимальное решение одной из пары задач по решению другой. 3. Решение двойственных задач Решение симметричных задач Рассмотрим решение задач с использованием теорем двойственности. Исходная задача Двойственная задача L (x) = x1 - x2 → max S(y) = 2y1 + 2y2 + 5y3 → min при ограничениях: при ограничениях: -2x1 + x2 ≤ 2│ y1 -2y1 + y2 + y3 ≥ 1 │x1 x1 - 2x2 ≤ 2 │ y2 y1 – 2y2 + y3 ≥ -1 │x2 x1 + x2 ≤ 5 │ y3 yi ≥0, I = 1,3. x1 ≥0 , x2 ≥0. Решим исходную задачу графическим методом, получим Хопт = (4,1), при этом L(x)max = 3. На основании 1-й теоремы двойственности L(x)max = S(y)min = 3. Так как x1, x2 > 0, то по 2-й теореме двойственности систему ограничений можно записать в виде равенств: -2y1 + y2 + y3 = 1, Подставим Хопт в систему ограничений исходной задачи: -2*4 + 1 ≤ 2, 9 < 2 ═> у1 = 0, 4 – 2*1 ≤ 2, 2 = 2 ═> у2 > 0, ≤ 5, 5 = 5 ═> у3 > 0. Тогда система ограничений двойственной задачи примет вид Откуда Yопт = (0, 2/3, 1/3), при этом S(y)min = 3. Пусть дано решение двойственной задачи Yопт = (0, 2/3, 1/3), S(y)min= 3, найдем решение исходной. > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства: x1 + x2 = 5. Откуда Хопт = (4,1), при этом L(x)max = 3. Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом: S(y) = 2y1 + 2y2 + 5y3 → mах -2y1 + y2 + y3 – у4 = 1, bi БП У1 У2 У3 У4 У5 cj -2 1 1 -1 0 1 У5 1 2 -1 0 1 1 5 У3 -2 1 1 -1 0 1 0 У5 -3 3 0 -1 1 2 ∆j -12 3 0 -5 0 5 5 У3 -1 0 1 -2/3 -1/3 1/3 2 У2 -1 1 0 -1/3 1/3 2/3 ∆j 9 0 0 -4 -1 3 yj ≥ 0, i = 1,5. L(x)max = S(y)min = 3. Основные переменные переменные Исходная задача Х1 Х2 Х3 Х4 Х5 двойственная У4 У5 у1 У2 У3 Балансовые переменные Основные переменные ∆iв соответствующем столбце, причем значения хj берем по модулю: Х1 → У4, Х1 = │∆4│= │-4│=4, Х2 → У5, Х2 = │∆5│= │-1│=1. Хопт = (4,1), при этом L(x)max = 3. Если исходная задача решена симплексным методом, то решение двойственной задачи может быть найдено по формуле где С – матрица-строка коэффициентов при базисных переменных целевой функции в оптимальном решении исходной задачи; А - обратная матрица для матрицы А, являющейся матрицей коэффициентов базисных переменных системы ограничений исходной задачи в оптимальности решении. L (x) = x1 - x2 → max при ограничениях: -2x1 + x2 + x3 = 2, x1 + x2 + x5 = 5, x1 ≥0 , j = 1,5. Из таблицы (см. ниже) следует, что Хопт = (4,1), L(x)max = 3. матрицы записываются в виде С = (1 -1 0)1×3 , -2 1 1 А = 1 -2 0 , 1 1 0 3×3 А = 0 -1/3 1/3 , 1 1 1 0 1/3 2/3 × 0 -1/3 1/3 = (0 2/3 1/3). 1 1 1 ci БП 1 -1 0 0 0 L (x) х1 х2 х3 х4 х5 bi 0 х3 -2 1 1 0 0 2 0 Х4 1 -2 0 1 0 2 0 Х5 1 1 0 0 1 5 ∆j -1 1 0 0 0 0 0 х3 0 -3 1 2 0 6 1 Х1 1 -2 0 1 0 2 0 Х5 0 3 0 -1 1 3 ∆j 0 -1 0 1 0 2 0 х3 0 0 1 1 1 9 1 Х1 1 0 0 1/3 2/3 4 -1 Х2 0 1 0 -1/3 1/3 1 ∆j 0 0 0 2/3 1/3 3 Таким образом, решение двойственной задачи следующее: Решение несимметричных задач Рассмотрим решение задач с использованием теорем двойственности. Исходная задача Двойственная задача L (x) = 3x1 + x2 + 3x3 + x4 → min S(y) = 9y1 + 6y2 → mах x1 - 2x2 + 3x3 - x4 = 9│ y1 2y1 + y2 ≤ 3 │x1 x1 + x2 - 6x3 - x4 = 6 │ y2 -2y1 + y2 ≤ 1 │x2 xj ≥0 , j = 1,4. 3y1 - 6y2 ≤ 3 │x3 -2y1 - y2 ≤ 1 │x4 y1, y2 - произвольные по знаку. Yопт = (1/2, 2), при этом S(y)max = 33/2. По 1-й теореме двойственности L(x)min = S(y)mах = 33/2. Подставим Yопт в систему ограничений двойственной задачи: ≤ 3, 3 = 3, -2 *1/2 + 2 ≤ 1, 1 = 1, 3*1/2 – 6*2 ≤ 3, -21/2 < 3 → х3 = 0, -2*1/2 – 2 ≤ 1,-3 < 1 → х4 = 0. Так как х3 = х4 = 0 , то система ограничений исходной задачи примет вид 2x1 - 2x2 = 9, x1 +x2 =6. Решая данную систему, получим Хопт = (21/4, 3/4, 0,0), при этом L(x)min = 33/2. Рассмотрим решение задач с использованием обратной матрицы. Xопт = (21/4,3/4,0,0), при этом L(x)min = 33/2. Решение двойственной задачи найдем по формуле где С = (3,1), А = 2 -2 , А = 1/4 1/2 , Yопт = (3 1) * 1/4 1/2 = (1/2 2). -1/4 1/2 Таким образом, Yопт = (1/2, 2), при этом S(y)mах = 33/2. Решение смешанных двойственных задач Смешанные двойственные задачи можно решать с использованием теорем двойственности. L (x) = x1 - 6x2 - x3 → mах S(y) = 3y1 + 4y2 → min x1 + 3x2 + 3x3 = 3│ y1 y1 + 2y2 ≥ 1 │x1 ≤4 │ y2 3y1 ≥ -6 │x2 xj ≥0 , j = 1,3. 3y1 + 3y2 ≥ -1 │x3 y1 – произвольная по знаку, y2 ≥0. Найдем оптимальное решение двойственной задачи: Хопт = (1,0,2/3), при этом L(x)max = 1/3. По 1-й теореме двойственности Так как х1 > 0, х3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств: y1 + 2y2 = 1, 3y1 + 3y2 = -1, Откуда y1 = -5/3, y2 = 4/3, т. е. Yопт = (-5/3, 4/3). Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель L(x) = ∑ сjxj→ mах при ограничениях: ∑ aijxj ≤ bi │y, xj ≥0, i = 1,m, j = 1,n. Двойственная задача имеет вид S(y) = ∑ biyi→ min при ограничениях: ∑ aijуj ≥ cj, уi≥ 0, i = 1,m. ТЕОРЕМА 3. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений исходной задачи на оптимальное значение ее целевой функции, т. е. уi= ðLi/ ðbi/ ðLi ≈ ∆ Li, ðbi≈ ∆bi, тогда ∆ Li≈ уi * ∆bi. Для задачи оптимального использования сырья это уравнение показывает, что при изменении i – ресурса оптимальный доход является линейной функцией его приращения, причем коэффициентом служит уi – i –я компонента оптимального решения двойственной задачи. Если уi мало, то значительному увеличению i –го ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика. ценности для производства и его оценку можно принять за нуль. Если уi велико, то незначительному увеличению i –го ресурса будет соответствовать существенное увеличение оптимального дохода и ценность ресурса высока. Уменьшение ресурса ведет к существенному сокращению выпуска продукции. цену», оценку единицы i –го ресурса , объективно обусловленную оценку. Так как уi представляет частную производную от оптимального дохода по i – му ресурсу, то уi характеризует скорость изменения оптимального дохода при изменении i –го ресурса. С помощью уi можно определить степень влияния ограничений на значение целевой функции. Предельные значения (нижняя и верхняя границы) ограничений ресурсов, для которых остаются неизменными, определяются по формулам: bi = min (xj / dij ) , bi = max (xj / dij ) , где xj – значение переменной в оптимальном решении; dij– элементы матрицы ( dij ) = А , обратной к матрице базиса оптимального решения, для которой А = ( аij )m×n. 5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов Фирма выпускает три вида изделий, располагая при этом сырьем 4 типов : А, Б, В, Г соответственно в количествах 18, 16, 8 и 6 т. Нормы затрат каждого типа сырья на единицу изделия первого вида составляют соответственно 1, 2, 1, 0, второго вида – 2, 1, 1, 1 и третьего вида 1, 1, 0, 1. Прибыль от реализации единицы изделия первого вида = 3 усл. ед., второго =4 усл. ед., третьего = 2 усл. ед. Требуется: Решение. 1. Обозначим через Х = ( х1, х2, х3) план производства изделий трех видов, тогда математическая модель задачи примет вид L (x) = 3x1 + 4x2 + 2x3 → max ≤ 18, 2x1 + x2 + x3 ≤ 16 , ≤ 8, x2 + x3 ≤ 6, xj ≥0 , j = 1,3. Решаем задачу симплексным методом, при этом последняя таблица будет иметь вид сi БП х1 х2 х3 х4 х5 Х6 Х7 bi 0 х4 0 0 0 1 0 -1 -1 4 2 х3 0 0 1 0 1/2 -1 ½ 3 3 х1 1 0 0 0 ½ 0 -1/2 5 4 х2 0 1 0 0 -1/2 1 ½ 3 ∆j 0 0 0 0 1/2 2 3/2 33 Из таблицы следует Хопт = (5,3,3,4,0,0,0), при этом L(x)max = 33 усл. ед. Согласно теоремам двойственности Уопт = (0,1/2,2,3/2,0,0,0), при этом S(y)min = 33 усл. ед. 2. Наиболее дефицитным является сырье типа В, для которого двойственная оценка у3 = 2. Менее дефицитным является сырье вида Б, для которого у2 = ½. Совсем не дефицитным является сырье А (у1 =0). Для определения интервала устойчивости оценок найдем обратную матрицу для матрицы коэффициентов при базисных переменных в оптимальном решении системы ограничений. Базисными переменными в оптимальном решении являются х1, х2, х3, х4. Матрица коэффициентов при этих переменных в системе ограничений примет вид 1 2 1 1 А = (аij) = 2 1 1 0. 1 1 0 0 0 1 1 0 Тогда обратная матрица для матрицы А следующая: 0 1/2 0 -1/2 0 1/2 -1 1/2 Найдем интервал устойчивости оценок по видам сырья: ∆b1 = min (xоптj/ d1j ) = 3 / (1/2) = 6, ∆b1 = min (xоптj/ d1j ) = 4 / (-1/2) = 8. Интервал устойчивости оценок по отношению к первому ограничению: (b1 - b1; b1+ b1) = (18 – 6; 18 + 8) = (12; 26). Аналогично определим интервалы устойчивости оценок по отношению к ограничениям остальных видов сырья: ∆b2 = min ( 3/1; 4/(1/2) ) = 3, ∆b2 = │3/ (-1/2) │=6, ∆b3 = min ( 3/(1/2); 4/(1/2) ) = 6, ∆b3 = │3/ (-1) │=3, ∆b4 =5/1 = 5, ∆b4 = max│3/ (-1); 4/(-1) │=3. Интервалы устойчивости оценок по отношению ко второму ограничению: (16 – 3; 16 + 6) = (13;22), к третьему ограничению: (8 – 6; 8 + 3) = (2;11), (6 – 5; 6 + 3) = (1;9). 3. Изменения сырья согласно условиям задачи на +6, -3, +2, +2 т приводят к ограничению запаса сырья до 24, 13, 10, 8 т соответственно. Поскольку эти изменения находятся в пределах устойчивости оценок, на что указывают интервалы, то раздельное их влияние на прибыль определяется по формуле Li = yоптi* bi, тогда L1 max = yопт1 * b1 = 0*6 = 0, L2 max = yопт2 * b2 = 1/2*(-3) = -3/2, L3max = yопт3 * b3 = 2*2 = 4 , L 4max = yопт4 * b4 = 3/2*2 = 3. Суммарное влияние на прибыль: L max = L1 max + L2 max + L3 max + L4 max = 0 – 3/2 +4 +3 = 11/2 усл. ед. Если изменение сырья не находится в пределах устойчивости оценок, то необходимо найти новые условные оценки, т. е. решить задачу симплексным методом с изменением количества сырья соответствующих видов. ∆4 = ∑ aijyоптi – c4 = 1*0 + 2*1/2 +2*2 + 0*3/2 -15 = -10 < 0. Так как прибыль превышает затраты, то введение в план производства четвертого вида изделий целесообразно. Заключение Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственноиз условий исходной, или прямой задачи, которая применима к любой форме представления прямой задачи. В основу такого подхода положен тот факт, что использование симплекс-метода требует приведения любой ЗЛП к каноническому виду. Правила получения двойственной задачи из задачи исходной. 1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум. 2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи. 3. В исходной ЗЛП все функциональные ограничения - неравенства вида «≤», а в задаче, двойственной ей, - неравенства вида «≥». 4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга. 5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой. Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП. 1. Белолипецкий В. М. Математическое моделирование в задачах. / В. М. Белолипецкий, Ю. И. Шокин. – М. : Финансы и статистика, 2002. - 774 с. 2. Красс М. С. Основы математики и ее приложения в экономическом образовании: Учебник. - 5-е изд., испр. и доп. / М. С. Красс, Б. П. Чупрынов. – М. : Дело, 2006. – 720 с. 3. Солодовников А. С. Математика в экономике. / А. С. Солодовников, В. А. Бабайцев, А. В. Браилов. – М. : Изд–во МГУ, 1999. – 591 с. 5. http://lib.mexmat.ru 6. http://slovari.yandex.ru