презентация_Л2-3
.pdf
По формулам (9) пересчитываем симплекс-таблицу:
|
si0 |
x3 |
x5 |
x4 |
5 |
1 |
1 |
x1 |
4 |
1/3 |
2/3 |
x2 |
1 |
–1/3 |
1/3 |
F |
–3 |
–2/3 |
–1/3 |
Оптимальное решение:
x3 = x5 = 0, x4 = 5, x1 = 4, x2 = 1
Целевая функция
F = –3
ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
ПРЯМАЯ ЗАДАЧА ЛП (ПЗЛП)
F CX maxAX B
x j 0 ( j 1, 2,..., n)
где
X (x1 x2 ... xn )T C (c1 c2 ... cn )
A (aij ) |
(i 1,..., m, |
j 1,..., n) |
B (b1 b2 ... bn ) |
|
|
ДВОЙСТВЕННАЯ ЗАДАЧА ЛП (ДЗЛП)
F BY minATY C
yi 0 (i 1, 2,..., m)
где
Y ( y1 y2 ... ym )T
Правила перехода от ПЗЛП к ДЗЛП
кол-во неизвестных (yi) ДЗЛП = кол-ву ограничений ПЗЛП
кол-во ограничений ДЗЛП = кол-ву неизвестных xj ПЗЛП
ЦФ (max) ПЗЛП ЦФ (min) ДЗЛП и наоборот
коэфф. ЦФ ДЗЛП = своб. членам ограничений ПЗЛП
своб. члены ограничений ДЗЛП = коэфф. ЦФ ПЗЛП
коэфф. любого ограничения ДЗЛП = коэфф. при одной переменной из всех ограничений ПЗЛП
все неизвестные ДЗЛП неотрицательны
Теорема
Если прямая / двойственная задача ЛП
имеет / не имеет оптимального решения, то двойственная / прямая задача ЛП имеет то же / не имеет оптимального решения.
Пример 2
ПЗЛП:
F 4x1 |
18x2 |
30x3 |
5x4 max |
||||
3x1 x2 4x3 x4 3 |
|
|
|||||
|
|
|
|
|
|
|
|
2x1 4x2 x3 x4 3 |
|
|
|||||
x1, x2 , x3 , x4 0 |
|
|
|
|
|
|
|
3 |
1 4 1 |
|
|
3 |
|
||
A |
|
|
|
, |
B |
|
, |
2 |
4 1 1 |
|
|
3 |
|
||
C 4 |
18 |
|
30 |
|
5 , |
|
|
X x |
x |
x |
x |
T |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
|
ДЗЛП:
3y1 3y2 min
3y1 2 y2 4 |
|
||||
|
4 y2 |
18 |
|
||
y1 |
|
||||
|
|
|
|
|
|
4 y1 y2 30 |
|
||||
y |
y |
2 |
5 |
|
|
|
1 |
|
|
|
|
y1, y2 0 |
|
|
|||
Решение: |
|
|
|
|
|
min min( 3y1 3y2 ) 36 при |
y1 y2 6 |
||||
Следовательно
max F max( 4x1 18x2 30x3 5x4 ) 36