Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 79 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

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

Рубрика: 

79
≥+
≥+
≥++
≥+
.15
;12
;334
;22
31
32
321
21
yy
yy
yyy
yy
(2.2.64)
Из теоремы равновесия следует, что если допустимое решение (2.2.62) является
оптимальным, то при оптимальном решении (y
1
, y
2
, y
3
) двойственной задачи (2.2.63) —
(2.2.64) первые три неравенства (2.2.64), соответствующие положительным значениям х
1
,
х
2
, х
3
, должны быть уравнениями, т. е.
++
=++
=+
.22
;334
;22
32
321
21
yy
yyy
yy
(2.2.65)
Система линейных уравнений (2.2.65) имеет единственное решение:
.17/2,17/13,17/8
321
=== yyy (2.2.66)
При значениях y
1
(2.2.66) четвертое ограничение-неравенство в системе
ограничений (2.2.64) является строгим неравенством:
,117/1817/2517/8
>
=
⋅
+
которое соответствует x
4
= 0.
Значениям y
1
(2.2.66), отличным от нуля, соответствуют ограничения (2.2.61),
которые при значениях х
j
(2.2.62) обращаются в равенства.
Итак, в каждой паре двойственных условий взаимосопряженных задач (2.2.60) —
(2.2.61) и (2.2.63) — (2.2.64) при значениях неизвестных (2.2.62) и (2.2.66) одно условие
является равенством, как только второе — строгим неравенством.
Следовательно, по теореме равновесия, допустимые решения (2.2.62) и (2.2.66)
являются оптимальными.
Для оптимального решения (2.2.66) имеем следующее значение целевой функции
(2.2.63):
W
min
=9⋅8/17+5⋅13/17+8⋅2/17=9.
Мы видим, что значения z
мax
=9 и w
мin
=9, соответственно задач (2.2.60) — (2.2.61) и
(2.2.63) — (2.2.64), совпадают, что, в силу теоремы 2, еще раз убеждает нас в том, что
допустимые решения (2.2.62) и (2.2.66) оптимальны.
Задача, двойственная канонической задаче линейного программирования
Пусть каноническая задача линейного программирования задана в векторной
форме.
Найти неотрицательный вектор Х = [х
1
, х
2
, . . ., х
n
], который максимизирует
целевую функцию
z = СХ (2.2.67)
при условиях:
A
i
X = b
i
, i=1,2,...,m, (2.2.68)
где С = (с
1
, с
2
, . . ., с
n
) — вектор коэффициентов целевой функции;
А
i
=(а
i1
, а
i2
,..., а
iп
) — строки матрицы условий А = ||a
ij
||
mxn
.
Всякое ограничение-равенство f = 0 может быть заменено парой неравенств вида
f≤0 и -f≤0. Поэтому каноническую задачу (2.2.67) — (2.2.68) можно сформулировать в
форме следующей стандартной задачи линейного программирования.

Страницы