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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

симплекс-таблиц, в каждой из которых все оценки
j
Δ
неотрицательны,
0
≥Δ
j
(обеспечение допустимости вектора y ). Но значения переменных
j
x хотя и удовлетворяют системе ограничений задачи (6.3) (
0
AxA = ), но
не удовлетворяют условию
j
x ≥ 0, n
j
,,1 L
=
(среди правых частей есть
отрицательные). На каждом новом векторе
y целевая функция W задачи
(6.4) меньше, чем на предыдущем. Через конечное число шагов находится
min
W
, что означает одновременное определение
max
Z
и оптимального
решения
x
(все правые части симплекс-таблицы становятся
неотрицательными). Описанный алгоритм называется
двойственным
симплекс-методом. Обоснование двойственного симплекс-метода
сопроводим решением примера.
Пример. Рассмотрим такую ЗЛП
max262
4321
→−++= xxxxZ
;
3032
331
=
++ xxx
;
102
421
−
=
+−− xxx ; (6.26)
0,,
41
≥xx L
.
Математическая модель двойственной задачи:
min1030
21
→−= yyW
;
22
21
≥− yy
;
623
21
≥− yy
; (6.27)
2
1
≥y ;
1
2
−≥y .
Составим первую симплекс-таблицу (табл. 6.3).
Вектор
x
= (0; 0; 30; −10) недопустим, так как 0
4
<
x . Но вектор
1
y
=
= (
3
Δ
+ 2;
4
Δ
−1) = (0 + 2; 0 −1) = (2; −1) − допустимое решение
двойственной задачи.
ZyyW
=
=
−
= 701030
211
. Перейдем к вектору
2
y ,
на котором целевая функция
W уменьшится.
Сначала выберем уравнение, в котором заменяется базисная
переменная. Условимся уменьшать целевую функцию
W , выбирая правую
часть и соответствующий опорный элемент отрицательными
.
Таблица 6.3
2 6 21
−1
Базисные
перемен.
c
баз
1
x
2
x
3
x
4
x
Правые
части
x
3
2 2 3 1 0 30
x
4
−1 −1 (1/2)
−
2 (1)
0 (0)
1 (−1/2) −10 (5)

Страницы