Составители:
Рубрика:
81
=+−+−
=+++−
.1582
;2221244
54321
54321
xxxxx
xxxxx
(2.2.77)
Проверить, что допустимое решение
x
1
= 0, x
2
=1/2, x
3
= 2, x
4
= 0, x
5
= 0 (2.2.78)
является оптимальным решением данной задачи.
Обратим внимание на пары двойственных условий:
≥−≥+
≥−≥−
≥≥+
≥−≥−−
≥−≥+
.0,4
;0,12
;0,6812
;0,524
;0,14
521
421
321
221
121
xyy
xyy
xyy
xyy
xyy
(2.2.79)
Поскольку в предполагаемом решении х
2
и x
3
положительны, из теоремы
равновесия следует, что во второй и третьей парах двойственных условий (2.2.79) первые
ограничения должны быть уравнениями.
Таким образом получаем простую систему линейных уравнений:
=+
=+
,6812
;524
21
21
yy
yy
из которой находим:
y
1
=7/2, y
2
=-9/2. (2.2.80)
Подставляя это решение в первое, третье и четвертое ограничения-неравенства
(2.2.79), найдем:
4y
1
+y
2
= 4⋅7/2- 9/2 = 19/2 >-1;
2y
1
- y
2
= 2⋅7/2+ 9/2 = 23/2 >-1;
y
1
+y
2
= 7/2 - 9/2 = -1 > - 4.
Итак, в каждой паре двойственных условий (2.2.79) одно условие является
равенством, как только второе — строгим неравенством, Следовательно, указанные
допустимые решения (2.2.78) и (2.2.80), соответственно прямой и двойственной задач, яв-
ляются оптимальными.
Для окончательной проверки убедимся в совпадении целевых функций обеих
задач.
Для прямой канонической задачи (2.2.76) — (2.2.77) имеем значение
2/19262/1565
32max
=⋅+⋅−=+−= xxz
и для двойственной задачи то же значение:
w
мin
=22y
1
+ 15y
2
= 22⋅ 7/2+ 15(-9/2)=19/2.
Ниже мы увидим, что критерий оптимальности и теорема равновесия будут
использованы для доказательства очень важной теоремы об опорных решениях
канонической задачи линейного программирования.
2.2.3. Теорема об опорных решениях
Напомним, что каноническая задача линейного программирования состоит в
отыскании неотрицательного вектора Х=[x
1
, х
2
, . . ., х
п
], который максимизирует
(минимизирует) целевую функцию
z = CX (2.2.81)
при условии
x
1
A
1
+ x
2
A
2
+...+х
п
А
n
=В, (2.2.82)
где С = (с
1
, c
2
, . . ., с
п
) — вектор коэффициентов целевой функции (2.2.81);
Страницы
- « первая
- ‹ предыдущая
- …
- 79
- 80
- 81
- 82
- 83
- …
- следующая ›
- последняя »
