74. Понятие двойственности в задачах линейного программирования (злп). Правила построения двойственных задач (симметричных и несимметричных).

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

Прямая задача max Z=

Двойственная задача min Z=

Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.

Прямая задача: сколько и какой продукции хj (j=1,n) надо произвести, чтобы при заданных стоимостях единицы продукции cj (j=1,n), объемах имеющихся ресурсов bi (i=1,m) и нормах расходов aij максимизировать выпуск продукции в стоимостном выражении?

Двойственная задача: какова должна быть оценка единицы каждого из ресурсов yi (i=1,m), чтобы при заданных bi, cj и aij минимизировать общую оценку затрат на все ресурсы.

Правила построения симметричных двойственных задач:

1. Если прямая на max, то двойственная к ней на min и наоборот.

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

3. Свободные члены bi ограничения прямой задачи явл. коэф-ми целевой функции двойственной задачи.

4. Матрицы коэффициентов прямой и двойственной задач явл. транспонированными друг к другу.

5. Если прямая задача на max то ее сист. ограничений представляется в виде неравенств со знаком <=. Двойственная задача решаемая на min и её сист. ограничений имеет вид неравенств со знаком >=.

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

7. Все переменные в задачах неотрицательны.

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

Правила построения несимметричных двойственных задач:

1. Если на переменную x_j прямой задачи накладывается условие неотрицательности, то j-ое условие системы ограничений двойственной задачи явл. неравенство.

2. Если на x_j прям. задачи не накладывается условие неотрицательности, то j-ое ограничение системы двойственной задачи записывается в виде строгого равенства.

3. Если в прямой задаче имеются ограничения равенства то на соотв. переменные двойственной задачи не накладываются условие неотрицательности.

75. Теоремы двойственности и их экономическое содержание.

1. Основное неравенство двойственности: для любых допустимых решений x и y пары двойственных ЗЛП справедливо неравенство

2. Теорема существования (Малая теорема двойственности): чтобы прямая и двойственная задачи имели оптим. решение необходимо и достаточно, чтобы сущ-ли допустимые решения для каждой из них.

3. I теорема двойственности: если одна из пары двойственных задач имеет оптим. решение, то и вторая также имеет оптим. решение, причём экстрем. значения их целевых функций совпадают

Если же целевая функция одной из задач не ограничена, то система ограничений второй – противоречива.

Экон. смысл в том, что оптим. план производства можно построить тогда, когда ресурсы обладают рацион. оценками, и наоборот, ресурсы допускают естественную оценку лишь при наличии оптим. плана производства. Причём оценка продукта, полученного при реализации оптим. плана, совпадает с суммарной оценкой ресурсов z(x)=f(y). Другой план не рентабелен.

4. II теорема двойственности (теорема о дополняющей нежёсткости): чтобы планы x и y пары двойств. задач были оптим. необход. и достат. вып-е условий:

Если какое-либо огранич-е одной из задач обращ-ся в строгое нерав-во, то соотв. переменные двойств. задачи в её оптим. плане = 0. Если же какая-либо переем-я оптим. плана прямой задачи положительна, то соотв. огран-е в двойств. задаче её оптим. планом обращ-ся в строгое равен-во.

Экон. интерпретация: оценки оптим. плана – это мера дефиц-ти ресурсов. Ресурс использ. полностью – дефицитный. Его оценка положительна. Двойств. оценка недефиц. ресурса = 0.

5. Критерий оптимальности Канторовича: чтобы допуст. реш-е x и y пары двойств. задач было оптим. необх. и достат., чтобы знач-я целевых ф-й для них совпадали, т. е. z(x)=f(y)

6. III теорема двойственности: знач-я перем-ых в оптим. плане равны изменению цел. ф-и при малом изменении соотв. ограничения на рес-сы ( ). Эконом. содерж. – двойств. оценки равны изменению цел. ф-и при измен-и соотв. ресурса на 1.