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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Обозначим через y вектор
баз
c
1
−
B
, тогда условие (6.6) запишется в
виде
Δ = yA −
c
. Транспонируя это равенство, получаем
Δ=− cyA
T
. (6.7)
Если
*
баз
c
− это вектор коэффициентов целевой функции при
оптимальных базисных переменных то соответствующий вектор
Δ
−
неотрицателен, все оценки
j
Δ ≥ 0, n
j
,,1 L
=
. Тогда вектор
y =
*
баз
c
1−
B
(6.8)
есть допустимое решение задачи (6.4), так как
Δ=− cyA
T
≥ 0 ⇒
cyA
T
≥
.
В нашем случае
*
баз
c
= (2, 3, 0);
*
баз
c
1
−
B
= (2, 3, 0)
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
−
−
125,15,1
075,05,0
05,01
=
= (0,5; 1,25; 0).
Из равенства (6.7) следует, что оценка
j
Δ
− это разность между
значениями левой и правой части
j
-го ограничения задачи (6.4), когда в
качестве значений неизвестных берутся компоненты вектора
y =
баз
c
1
−
B
.
Эти значения удовлетворяют системе ограничений задачи (6.4) в случае
выполнения (6.8).
Убедимся, что вектор
y = (0,5; 1,25; 0) − допустимое решение
двойственной задачи:
)3(3)1(0225,115,0
1
c
=
=
−
×
+
×
+×
; +× 5,15,0
)2(210125,1
2
c==×+×+ ;
543321
0,, cccyyy =
=
=
> . Целевая
функция двойственной задачи равна на векторе
y = (0,5; 1,25; 0) числу
max
130125,185,06 ZW
=
=×+×+×= , так что найденное решение
двойственной задачи не только допустимо, но также и оптимально.
Докажем, что всегда вектор (6.8) есть оптимальное решение задачи
(6.4).
max
Z
= (
*
баз
c
,
0
X
) = (
*
баз
c
,
1
−
B
0
A )=(
*
баз
c
1
−
B
,
0
A )=(
y
,
0
A ) = )( yW .
Из совпадения значений целевых функций пары двойственных задач
вытекает (следствие 1 из основного неравенства) оптимальность вектора
y
. Теорема доказана.
Легко видеть, что если исходная система ограничений записана в
стандартной форме (матрица
A содержит единичную матрицу E), то
матрица
1−
B
состоит из тех столбцов оптимальной симплекс-таблицы,
которые соответствуют исходным базисным переменным. Тогда вектор
y

Страницы