Двойственные задачи линейного программирования

1.

ДВОЙСТВЕННЫЕ ЗАДАЧИ
ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ

2.

Каждой задаче линейного программирования определенным образом
можно поставить в соответствие некоторую другую задачу, которая
называется двойственной задачей линейного программирования. Запишем
прямую (исходную) задачу линейного программирования, которая
заключается в определении максимума целевой функции:
max L( x) c1x1 c2 x2 ... cn xn
При ограничениях:
xj 0
a11 x1 a12 x 2 ... a1n x n b1 ,
a x a x ... a x b ,
21 1
22 2
2n n
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a m1 x1 a m 2 x 2 ... a mn x n bm
( j 1, 2, ..., n) , bi 0
(i 1, 2, ..., m)

3.

Определение:
Двойственной
задачей
линейного
программирования по отношению к исходной задаче называется задача,
которая состоит в определении минимального значения целевой
функции:
min F ( y) b1 y1 b2 y2 ... bm ym
При ограничениях:
yi 0
(i 1, 2, ..., m) .
a11 y1 a21 y2 ... am1 ym c1 ,
a y a y ... a
12 1
22 2
m 2 y m c2 ,
. . . . . . . . . . . . . . . . . . . . . . . . . . .. . .
a1n y1 a2n y2 ... amn ym cn ,

4.

Отметим особенности пары взаимно двойственных задач.
1. Если основная задача – задача на максимум (минимум), то система
ограничений должна состоять из неравенств вида ≤ (≥), и в таком случае
двойственная задача должна быть задачей на минимум (максимум), а ее система
ограничений должна состоять из неравенств вида ≥ (≤).
2. В основной задаче все переменные должны быть неотрицательными.
3. Коэффициентами целевой функции F(Y) двойственной задачи являются
свободные члены системы ограничений основной задачи, и их число равно т.
4. Основная матрица системы ограничений двойственной задачи получается
транспонированием матрицы системы ограничений основной задачи.
5. Свободными членами системы ограничений двойственной задачи являются
коэффициенты целевой функции основной задачи. Теория двойственности в
линейном программировании
строится на теоремах двойственности,
позволяющих установить взаимосвязь между оптимальными решениями пары
двойственных задач. Решив одну из пары двойственных задач, можно или найти
оптимальное решение другой задачи, не решая её, или установить его отсутствие.
6. Все переменные двойственной задачи неотрицательные.

5.

Пример 1. Для задачи линейного программирования составить
двойственную задачу и решить обе эти задачи. Сопоставить экстремальные
значения соответствующих целевых функций, а также значения основных и
дополнительных переменных в основной и двойственной задачах.
L( X ) 4 x1 3x2 2 x3 max ,
5