11.2. Применение теории Куна-Таккера к решению зкп.
Сформулируем теорему Куна-Таккера для ЗКП (11.1)-(11.2).
Теорема 11.1.
Для
того чтобы точка
была решением задачи (11.1)-(11.2), необходимо
и достаточно существование такого
,
чтобы точка
была седловой точкой функции Лагранжа
задачи выпуклого программирования
(11.1)-(11.2).
Так как функция (11.1) является непрерывно дифференцируемой, то справедлива теорема:
Теорема 11.2.
Для того чтобы точка была решением задачи (11.1)-(11.2), необходимо и достаточно существование такого , чтобы для точки выполнялись условия (10.18)-(10.23). (см.главу 10).
Запишем функцию Лагранжа для ЗКП (11.1)-(11.2):
Согласно теореме 11.2 выпишем условия существования седловой точки. (11.4-11.9)
(1)
, (11.4)
(2)
, (11.5)
(3)
, (11.6)
(4)
, (11.7)
(5)
, (11.8)
(6)
(11.9)
Дополним
неравенства 11.4
и 11.7
до равенств, введя дополнительные
переменные:
.
Получим:
, (11.10)
, (11.11)
,
(11.12)
, (11.13)
, (11.14)
,
.
(11.15)
Равенства
(11.11) и (11.13)
равносильны более простым, так как
векторы
и
одновременно
либо отличны от нуля, либо равны нулю.
,
,
Система уравнений:
(11.16)
(11.17)
содержит
(m+n)
уравнений с 2(m+n)
неизвестными:
.
Так
как равенства
и
равносильны равенствам
,
то по крайней мере (n+m)
неизвестных равны нулю.
Следовательно, решение ЗКП сводится к отысканию неотрицательного базисного решения системы уравнений (11.16-11.17), которое может быть получено методом искусственного базиса (см. параграф 2.7).
11.3. Решение задач.
Алгоритм решения ЗКП
Пример 11.1:
,
1 шаг. Запишем функцию Лагранжа для данной ЗКП:
2
шаг.
Вычислим
,
:
3 шаг. Запишем условия существования седловой точки.
4
шаг. Вводим дополнительные переменные
и
получим систему из 4-х уравнений с 8-ю
неизвестными:
5
шаг. Выпишем расширенную матрицу
полученной системы уравнений:
Так
как матрица
не является K-матрицей, то добавим к 1-му
и второму уравнениям искусственные
переменные
,
в результате чего получим ЗЛП:
Которую решаем симплекс-методом (см. таблицу 11.1).
S |
N |
C |
XN |
X1 |
X2 |
Y1 |
Y2 |
V1 |
V2 |
W1 |
W2 |
Z1 |
Z2 |
|
0 |
Z1 |
-1 |
4 |
4 |
-2 |
1 |
1 |
-1 |
0 |
0 |
0 |
1 |
0 |
1 |
Z2 |
-1 |
6 |
-2 |
4 |
1 |
5 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
|
W1 |
0 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
2 |
|
W2 |
0 |
5 |
1 |
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
5 |
|
|
|
-10 |
-2 |
-2 |
-2 |
-6 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
1 |
X1 |
0 |
1 |
1 |
- 1/2 |
1/4 |
1/4 |
-1/4 |
0 |
0 |
0 |
1/4 |
0 |
|
Z2 |
-1 |
8 |
0 |
3 |
3/2 |
11/2 |
-1/2 |
-1 |
0 |
0 |
1/4 |
1 |
8/3 |
|
W1 |
0 |
1 |
0 |
3/2 |
-1/4 |
-1/4 |
1/4 |
0 |
1 |
0 |
-1/4 |
0 |
2/3 |
|
W2 |
0 |
4 |
0 |
11/2 |
-1/4 |
-1/4 |
1/4 |
0 |
0 |
1 |
-1/4 |
0 |
8/11 |
|
|
|
-8 |
0 |
-3 |
-3/2 |
-11/2 |
-1/2 |
1 |
0 |
0 |
1/2 |
0 |
|
|
2 |
X1 |
0 |
4/3 |
1 |
0 |
1/6 |
1/6 |
-1/6 |
0 |
1/3 |
0 |
1/6 |
0 |
8 |
Z2 |
-1 |
6 |
0 |
0 |
2 |
6 |
-1 |
-1 |
-2 |
0 |
1 |
1 |
1 |
|
X2 |
0 |
2/3 |
0 |
1 |
-1/6 |
-1/6 |
1/6 |
0 |
2/3 |
0 |
-1/6 |
0 |
|
|
W2 |
0 |
1/3 |
0 |
0 |
2/3 |
2/3 |
-2/3 |
0 |
-11/3 |
1 |
2/3 |
0 |
1/2 |
|
|
|
-6 |
0 |
0 |
-2 |
-6 |
1 |
1 |
2 |
0 |
0 |
0 |
|
|
3 |
X1 |
0 |
5/4 |
1 |
0 |
0 |
0 |
0 |
0 |
5/4 |
-1/4 |
0 |
0 |
1 |
Z2 |
-1 |
3 |
0 |
0 |
-4 |
0 |
5 |
-1 |
31 |
-9 |
-5 |
1 |
3/31 |
|
X2 |
0 |
3/4 |
0 |
1 |
0 |
0 |
0 |
0 |
-1/4 |
1/4 |
0 |
0 |
|
|
Y2 |
0 |
1/2 |
0 |
1 |
1 |
1 |
-1 |
0 |
-11/2 |
3/2 |
1 |
0 |
|
|
|
|
-3 |
0 |
0 |
4 |
0 |
-5 |
1 |
-31 |
9 |
6 |
0 |
|
|
4 |
X1 |
0 |
35/31 |
1 |
0 |
5/31 |
0 |
-24/124 |
5/124 |
0 |
7/62 |
25/124 |
-5/24 |
|
W1 |
0 |
3/31 |
0 |
0 |
-4/31 |
0 |
5/31 |
-1/31 |
1 |
-9/31 |
-5/31 |
1/31 |
|
|
X2 |
0 |
24/31 |
0 |
1 |
-1/31 |
0 |
5/124 |
-1/124 |
0 |
11/62 |
-5/124 |
1/124 |
|
|
Y2 |
0 |
32/31 |
0 |
0 |
9/31 |
1 |
7/62 |
|
0 |
-3/31 |
7/62 |
11/62 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
