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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

продолжить поиск оптимального решения, используя процедуру
двойственного симплекс-метода.
Пусть, например, правая часть первого уравнения возросла на единицу,
а правая часть второго уменьшилась на единицу, т.е.
0
AΔ
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−1
1
;
0
A
′
=
0
A +
0
AΔ
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
4
3
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−1
1
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
3
4
;
0
X
′
=
0
X
+
+
1−
B
0
AΔ
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2,2
4,0
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
4,02,0
2,04,0
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−1
1
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2,2
4,0
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
− 2,0
6,0
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2
1
.
Обе правые части по-прежнему больше 0. Оптимальное решение ЗЛП
max38
321
→
+
+
= xxxZ
:
42
321
=+
+
xxx
;
32
21
=
−
xx
;
0,,
321
≥xxx
дается вектором
x
= (2, 1, 0);
max
Z = 10.
Изменение коэффициентов целевой функции.
Изменение коэффициентов целевой функции влечет только изменение
оценок свободных переменных. Эти оценки вычисляются непосредственно
по оптимальной симплекс-таблице, когда в столбце
баз
c
нужно проставить
новые значения коэффициентов
j
c . Если полученные оценки
j
Δ вновь все
неотрицательны, найденное решение по-прежнему оптимально, если нет,
то поиск оптимального решения нужно продолжить симплекс-методом.
Включение в исходную модель дополнительных переменных. Если
в исходную модель включаются новые переменные
knn
xx
++
,,
1
L , то в
матрице
A
появляются новые столбцы; матрица
A
превращается в
матрицу
A
′
:
A
′
=
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
+++
+++
+++
kmnmnmn
knnn
knnn
aaa
aaa
aaa
L
LLLL
L
L
21
22212
12111
.
Вектор коэффициентов целевой функции получает размерность
k
n
+
,
в целевой функции появляются
k
новых коэффициентов,
knn
cc
++
,,
1
L .
Обозначим через
c
′
вектор (
knn
cc
++
,,
1
L
).
В последней симплекс-таблице матрица
расширится на матрицу
X
′
=
1−
B
A
′
;
а у вектора оценок Δ появятся новые компоненты,
Δ
′
=
баз
c
X
′
−
c
′
.

Страницы