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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Если все новые оценки неотрицательны, то найденное ранее решение
оптимально. В противном случае следует продолжить поиск оптимального
решения с помощью симплекс-метода.
Пусть, например, задача (6.30) изменилась так
max238
4321
→
+
+
+
= xxxxZ
;
32
4321
=+++ xxxx
;
422
421
=
+
−
xxx
;
0,,,
4321
≥xxxx
.
Здесь
A
′
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2
1
;
X
′
=
1−
B
A
′
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
4,02,0
2,04,0
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2
1
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
1
0
;
c
′
= (2);
Δ
′
=
=
баз
c
X
′
−
c
′
= (8, 1)
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
1
0
− (2) = (1) − (2) = (−1). Оценка
4
Δ вновь
введенной переменной
4
x меньше 0. Целевую функцию
можно
увеличить, если сделать переменную
4
x
базисной во втором уравнении,
переведя переменную
1
x в свободные переменные.
Включение дополнительных ограничений. Каждое дополнительное
ограничение добавляет строку в симплекс-таблицу. Если это ограничение
содержит свою базисную переменную, строка вставляется в оптимальную
симплекс-таблицу естественным образом. В противном случае в новое
уравнение нужно добавить искусственную базисную переменную и
продолжать решение, используя метод искусственного базиса.
Пусть в систему ограничений задачи (6.30) добавилось неравенство
2
21
≤+ xx . Превратим неравенство в уравнение 0;2
4421
≥=+
+
xxxx .
Переменная
4
x становится базисной переменной третьего уравнения.
Чтобы добавить это уравнение в оптимальную симплекс-таблицу, нужно
выразить базисные переменные
1
x и
2
x через свободную переменную
3
x
(см. табл. 6.5, ч.III):
31
2,02,2 xx −= ;
32
7,04,0 xx
−
=
.
Уравнение
2
421
=+
+
xxx примет вид 6,09,0
43
−
=
+
−
xx . Последняя
симплекс-таблица станет такой (табл. 6.6)
Таблица 6.6
1 8 3 0 Базисные
перемен.
c
баз
1
x
2
x
3
x
4
x
Правые
части
x
2
8 0 1 0,4 0 0,4
x
1
1 1 0 02 0 2,2
x
4
0 0 0
−0,9
1
−0,6
Z
0 0 0,4 0 5,4

Страницы