2015-05-13
662
Двойственная задача математического программирования
Целью лабораторной работы является усвоение студентами понятия двойственности в теории линейного программирования, приобретение практических навыков преобразования прямой ЗЛП в двойственную и формализации двойственной ЗЛП с помощью электронных таблиц MS Excel.
Сущность двойственности в задачах математического программирования
Любой задаче линейного программирования, называемой исходной, соответствует другая – двойственная. Решая одну из задач, мы получаем также решение другой.
Если исходная задача линейного программирования в стандартной форме выглядит следующим образом:
(3.1)
и представима в матричном виде:
Таблица 3.1
| x1 | … | xn | ||
| y1= | a11 | … | a1n | -b1 |
| … | … | … | … | … |
| ym= | am1 | … | amn | -bm |
| Z= | c1 | … | cn |
то, если сопоставить независимым переменным новые зависимые переменные v, а каждой зависимой переменной новую независимую переменную p, построив для этого вспомогательную матрицу:
Таблица 3.2
|
|
|
| v1 | … | vn | W | ||
| x1 | … | xn | |||
| p1 | y1= | a11 | … | a1n | -b1 |
| … | … | … | … | … | … |
| pm | ym= | am1 | … | amn | -bm |
| Z= | с1 | … | cn |
а затем «отбросить» исходные переменные x и y и транспонировать вспомогательную матрицу, которая в итоге будет выглядеть следующим образом:
Таблица 3.3
| p1 | … | pm | ||
| v1= | a11 | … | am1 | c1 |
| … | … | … | … | … |
| vn= | a1n | … | amn | cn |
| W= | -b1 | … | -bm |
получаем следующую ЗЛП в стандартной форме, называемую сопряжённой (или двойственной) к исходной:
(3.2)
Особенности двойственной задачи линейного программирования заключаются в следующем.
1.Если исходная является задачей максимизации, то двойственная - задачей минимизации.
2.Коэффициенты целевой функции исходной задачи становятся свободными членами ограничений двойственной.
3.Свободные члены ограничений исходной задачи становятся коэффициентами целевой функции двойственной.
4.Матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений исходной.
5.Знаки неравенств ограничений меняются на обратные.
6.Число переменных исходной задачи равно числу ограничений двойственной, а число переменных двойственной равно числу ограничений исходной задачи.
7.Если исходная задача имеет оптимальное решение, то и двойственная имеет оптимальное решение, причём оптимальные значения линейных форм равны:max Z=min W.
