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

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

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





















Реферат





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

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





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

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

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

третьего курса 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                                                           -2 y1 + 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,

L 3max = 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















 























2