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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Z
3 2 0 0 70
Имеется только одна отрицательная правая часть (во втором
уравнении), поэтому замену переменной проведем во втором уравнении.
Отметим, что если бы в левой части второго уравнения все
коэффициенты были бы неотрицательны, то задача (6.26) не имела бы ни
одного допустимого решения, ведь уравнение вида
nn
xaxa +
+
L
11
= b
−
,
где 0,,,
1
≥baa
n
L не имеет неотрицательных решений.
Есть две возможности выбрать новую базисную переменную: или
1
x
,
или
2
x
. Сделаем выбор, исходя из требования неотрицательности всех
оценок
j
Δ , n
j
,,1 L= . По формуле пересчета
s
rs
rj
jj
x
x
Δ−Δ=Δ
′
≥ 0, (6.28)
где
−
r
номер уравнения, в котором заменяется базисная переменная;
−
s
номер новой базисной переменной.
Так как
j
Δ ,
s
Δ ≥ 0 и было условлено, что
rs
x
< 0, то наверняка
j
Δ ≥ 0,
когда 0
≥
rj
x . Если же 0<
rj
x , то условие (6.28) можно записать в виде
rj
j
rs
s
x
x
Δ
≤
Δ
. (6.29)
Итак, отношение
rs
s
x
Δ
должно быть минимальным из всех отношений
rj
j
x
Δ
, таких, что 0<
rj
x .
В нашем случае имеем:
2)
2
2
;
1
3
min( =
−−
. Новой базисной
переменной становится переменная
2
x
. Построим табл. 6.4.
Таблица 6.4
2 6 2
−1
Базисные
перемен.
c
баз
1
x
2
x
3
x
4
x
Правые
части
x
3
2 0,5 0 1 1,5 15
x
2
6 0,5 1 0
−0,5
5
Z
2 0 0 1 60
Вектор
x
= (0, 5, 15, 0) ─ допустимое и оптимальное решение задачи

Страницы