РефератыМатематикаДвДвойственность линейного программирования

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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ


ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ МЕНЕДЖМЕНТА


Реферат


по дисциплине «Математические методы принятия управленческих решений»


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


Выполнила студентка


очной формы обучения


специальности «Менеджмент организации»


третьего курса 32
группы


Шумакова Ю. А.


Проверила


Кочетова Л.А.


Оренбург


2009


Содержание


Введение………………………………………………………………..…….3


1. Виды двойственных задач и составление их математических


моделей……………………………………………………………………….4


2. Основные теоремы двойственности……………………………………..6


3. Решение двойственных задач…………………………………………….7


4.Экономический анализ задач с использованием теории двойственности……………………………………………………………….….12


5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов…………………………………………………………………………..14


Заключение…………………………………………………...……………..18


Библиографический список……………………………………………......19


Введение


Двойственность в линейном программировании - принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу.


Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой.


Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.


Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной
. Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару.


Различают симметричные, несимметричные и смешанные двойственные задачи.


1. Виды двойственных задач и составление их математических моделей


Симметричные двойственные задачи


Дана исходная задача


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 , 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 - произвольные по знаку.


Математическая модель двойственной задачи имеет вид


S(y) = b1y1 + b2y2 +…+ bmym → min


при ограничениях:


a11y1 + a21y2 + … + am1ym ≥ c1 ,


a12y1 + a22y2 + … + am2ym ≥ c2 ,


………………………………………


a1ny1 + a2ny2 + … + amnxn ≥ cn ,


yj ≥0 , i = 1,m , j = 1,n.


yi – произвольные по знаку, i = 1,m.


Смешанные двойственные задачи


Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.


2. Основные теоремы двойственности


ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений X и Y выполняется равенство


L(x)max = S(y)min.


Если одна из двойственных задач неразрешима ввиду того, что


L(x)max→ ∞ (или S(y)min→ - ∞), то другая задача не имеет допустимых решений.


ТЕОРЕМА 2. Для оптимальности допустимых решений X и Y пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений


Xопт j( ∑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,


y1 – 2y2 + y3 = -1.


Подставим Хопт в систему ограничений исходной задачи:


-2*4 + 1 ≤ 2, 9 < 2 ═> у1 = 0,


4 – 2*1 ≤ 2, 2 = 2 ═> у2 > 0,


4 + 1 ≤ 5, 5 = 5 ═> у3 > 0.


Тогда система ограничений двойственной задачи примет вид


y2 + y3 = 1,


– 2y2 + y3 = -1.


Откуда Yопт = (0, 2/3, 1/3), при этом S(y)min = 3.


Пусть дано решение двойственной задачи Yопт = (0, 2/3, 1/3), S(y)min= 3, найдем решение исходной.


По 1-й теореме двойственности L(x)max = S(y)min = 3. Так как y2 , y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:


x1 - 2x2 = 2 ,


x1 + x2 = 5.


Откуда Хопт = (4,1), при этом L(x)max = 3.


Рассмотрим решение задач методом, основанным на взаимно однозначном соответствии между переменными: основным переменным исходной задачи соответствуют балансовые переменные двойственной, и наоборот. Для этого решим двойственную задачу симплексным методом:


S(y) = 2y1 + 2y2 + 5y3 → mах


При ограничениях:


-2y1 + y2 + y3 – у4 = 1,


y1 – 2y2 + y3 – у5 = 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.


Из таблицы следует, что Yопт = (0, 2/3, 1/3), S(y)min = 3.


На основании 1-й теоремы двойственности получаем


L(x)max = S(y)min = 3.


Решение другой задачи найдем по соответствию между переменными:






















Основные


переменные


Балансовые


переменные


Исходная задача Х1 Х2 Х3 Х4 Х5
двойственная У4 У5 у1 У2 У3
Балансовые переменные Основные переменные

Значение хj определяем по последней симплексной таблице в строке ∆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 - 2x2 + x4 =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 2/3


А = 0 -1/3 1/3 ,


1 1 1


0 1/3 2/3


Уопт = С*А = (1 -1 0) × 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

Таким образом, решение двойственной задачи следующее:


Yопт = (0, 2/3, 1/3), при этом S(y)min= 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опт в систему ограничений двойственной задачи:


2*1/2 +2 ≤ 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 ,


1 1 -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


2x1 + 3x3 ≤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-й теореме двойственности


L(x)max = S(y)min = 1/3.


Так как х1 > 0, х3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:


y1 + 2y2 = 1,


3y1 + 3y2 = -1,


Откуда y1 = -5/3, y2 = 4/3, т.е. Yопт = (-5/3, 4/3).


4. Экономический анализ задач с использованием теории двойственности


Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель


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 = 0, то при увеличении i –го ресурса оптимальный доход остается неизменным и ценность этого ресурса равна нулю. В самом деле, сырье, запасы которого превышают потребности в нем, не представляют ценности для производства и его оценку можно принять за нуль.


Если у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) составить план производства трех видов, максимизирующих прибыль;


2) определить дефицитность сырья;


3) установить размеры максимальной прибыли при изменении сырья А на 6 т, Б – на 3 т, В – на 2 т, Г – на 2 т. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль;


4) оценить целесообразность введения в план производства фирмы нового вида изделий (четвертого), нормы затрат на единицу которого соответственно равны 1, 2, 2, 0, а прибыль составляет 15 усл. ед.


Решение.
1. Обозначим через Х = ( х1, х2, х3) план производства изделий трех видов, тогда математическая модель задачи примет вид


L (x) = 3x1 + 4x2 + 2x3 → max


при ограничениях:


x1 + 2x2 + x3 ≤ 18,


2x1 + x2 + x3 ≤ 16 ,


x1 + x2 ≤ 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 .


0 1/2 -1 1/2


1 0 -1 -1


Найдем интервал устойчивости оценок по видам сырья:


∆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. Для оценки целесообразности введения в план производства фирмы четвертого вида изделий используем формулу


∆4 = ∑ aijyоптi – c4 = 1*0 + 2*1/2 +2*2 + 0*3/2 -15 = -10 < 0.


Так как прибыль превышает затраты, то введение в план производства четвертого вида изделий целесообразно.


Заключение


Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственноиз условий исходной, или прямой задачи, которая применима к любой форме представления прямой задачи. В основу такого подхода положен тот факт, что использование симплекс-метода требует приведения любой ЗЛП к каноническому виду.


Правила получения двойственной задачи из задачи исходной.


1. Если в исходной задаче ищется максимум целевой функции, то в двойственной ей - минимум.


2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи.


3. В исходной ЗЛП все функциональные ограничения - неравенства вида «≤», а в задаче, двойственной ей, - неравенства вида «≥».


4. Коэффициенты при переменных в системах ограничений взаимно двойственных задач описываются матрицами, транспонированными относительно друг друга.


5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.


6. Условие неотрицательности переменных сохраняется в обеих задачах.


Теория математического линейного программирования позволяет не только получать оптимальные планы с помощью эффективных вычислительных процедур, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, которая является двойственной по отношению к исходной ЗЛП.


Библиографический список


1. Белолипецкий В. М. Математическое моделирование в задачах. / В.М. Белолипецкий, Ю.И. Шокин. – М. : Финансы и статистика, 2002.- 774 с.


2. Красс М. С. Основы математики и ее приложения в экономическом образовании: Учебник. - 5-е изд., испр. и доп. / М.С. Красс, Б.П. Чупрынов. – М. : Дело, 2006. – 720 с.


3. Солодовников А. С. Математика в экономике. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов. – М. : Изд–во МГУ, 1999. – 591 с.


4. Черемных Ю. Н. Математические методы в экономике. 2 - изд. / Ю.Н. Черемных. – М. : Дело и сервис, 2001. – 657 с.


5. http://lib.mexmat.ru


6. http://slovari.yandex.ru

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

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

Слов:3626
Символов:31567
Размер:61.65 Кб.