ВУЗ:
Составители:
123
му появился модифицированный симплекс-метод, основанный на частичном
преобразовании матрицы коэффициентов канонической формы.
Запишем задачу линейного программирования в следующем виде:
Минимизировать z=c
1
x+…+c
n
x
n
с ограничениями: p
1
x
1
+…+p
n
x
n
=b, (7.9)
где p
j
=(a
ij
,…,a
mj
)
T
– j-тый вектор-столбец матрицы коэффициентов А.
Введем в рассмотрение
B=(p
j1
, p
j2
, …, p
jm
); X=(x
j1
, x
j2
, …, x
jm
)
T
; C=(c
j1
, c
j2
, …, c
jm
).
Тогда для вектора базисных переменных можно записать матричное
уравнение: BX=b, решением которого будет X=B
-1
b=b
*
.
Обычно целевую функцию включают в (7.9) в виде столбца и получают:
;..1)...,,,(
T
21
njaaap
mjjjj
==
T
21
T
1
)0,...,,,(;)0...,,0,0(
mn
bbbbp ==
+
.
Тогда (7.9) перепишется в виде:
∑
=
+
=−+
n
j
njj
bzpxp
1
1
)(
. (7.10)
Матрица
1
0
),...,,(
11
#
"""
#
C
B
pppB
njmj
==
+
является допустимым базисом для (7.10).
Из последнего уравнения следует определение так называемого сим-
плекс-множителя. Вектор-строка
1
1
)...,,(
−
=ππ=π BC
m
называется вектором симплекс-множителей базиса В.
Теперь можно охарактеризовать основные шаги модифицированного
симплекс-метода.
Предполагается, что на k-той итерации имеется обратный базис
1−
B
, а
также базисное решение
bBx
B
1−
=
и
),,( cb
A
.
I. Строка m+1 в
1−
B
имеет вид
)1,...,,,(
21
1
1 mm
B π−π−π−=
−
−
.
Для всех внебазисных решений находятся относительные оценки
∑
=
π−=π−=
m
i
jjijijj
PcacC
1
.
II. Определяется
)min(
j s
cc =
.
Ш. Если
0≥
s
c , то базисное решение оптимально.
Страницы
- « первая
- ‹ предыдущая
- …
- 121
- 122
- 123
- 124
- 125
- …
- следующая ›
- последняя »
