Введение в линейное программирование. Палий И.А. - 35 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

Составители: 

Рубрика: 

неограниченности целевой функции Z существует такое допустимое
решение
),,,(
21 n
xxxx L=
задачи (6.3), на котором Z = ),(
x
c >
0
W
.
Получено противоречие с основным неравенством.
6.4.2. Теорема 2 (первая теорема двойственности).
Если одна из пары двойственных задач имеет решение, то и другая
имеет решение
, причем оптимальные значения целевых функций
совпадают
,
minmax
WZ
=
.
Будем предполагать, что известно оптимальное решение задачи (6.3).
Чтобы провести доказательство в другую сторону, нужно привести задачу
(6.4) к каноническому виду.
Одновременно с общим доказательством покажем и на конкретном
примере, как, имея оптимальную симплекс-таблицу для задачи (6.3),
получить оптимальное решение задачи (6.4).
Пример 1. В табл. 6.1 показано оптимальное решение следующей ЗЛП
max23
21
→+= xxZ ;
65,1
321
=
++ xxx ; 82
421
=
+
+ xxx ; 1
521
=
+
+
−
xxx ; 0,,
51
≥xx L .
Приведем математическую модель двойственной задачи.
min86
321
→++= yyyW ;
32
321
≥−+ yyy ; 25,1
321
≥
+
+ yyy ; 0
1
≥y ; 0
2
≥y ; 0
3
≥y
Таблица 6.1
3 2 0 0 0 Базисные
перемен.
c
баз
x
1
x
2
x
3
x
4
x
5
Правые
части
x
2
2 0 1 1
−0,5
0 2
x
1
3 1 0
−0,5
0,75 0 3
x
5
0 0 0
−1,5
1,25 1 2
Z
0 0 0,5 1,25 0 13
Здесь
max
Z = 13, оптимальные значения переменных: x
1
= 3; x
2
= 2; x
3
=
=
x
4
= 0; x
5
=2.
Исходные матрица коэффициентов при переменных и столбец правых
частей таковы
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
=
1
8
6
;
10011
01012
0015,11
0
AA .
Обозначим через
B матрицу (часть матрицы A), столбцы которой − это
столбцы коэффициентов при
базисных переменных данной стандартной
формы
в исходной системе уравнений.

Страницы