Преобразованная задача имеет тот же тип, что и исходная. Мы можем опять начать решение этой задачи с точки Y = (l/n, 1/п, 1/п), являющейся центром симплекса, и повторить действия, выполненные на предыдущем этапе. После каждой итерации на основании полученного Y-решения нетрудно вычислить значения исходных Х-переменных.
Теперь покажем, как определить новую точку решения для преобразованной задачи. На любой k-й итерации задача имеет следующий вид.
Минимизировать г = CDtY
при ограничениях
AD,Y = 0,
Y лежит в шаре радиуса аг.
Поскольку шар радиуса аг является частью пространства допустимых решений, определяемого ограничениями IX = 1, X > О, эти ограничения можно исключить из рассмотрения. Можно показать, что решение последней задачи вычисляется по следующей формуле
новое текущее
лить так:
= (1/п, 1/п, 1/п), ср- проекция градиента, которую можно вычис-
с-p-pppVpkcd/,
где Р =
Выбор параметра а - ключевой момент при построении алгоритма. Обычно а выбирается настолько большим, насколько это возможно, чтобы ускорить сходимость к оптимальному решению. Но при выборе слишком большого значения а можно "упереться" в запрещенную границу симплекса. В настоящее время не известно оптимальное значение а. Кармаркар предлагал использовать а = (п - 1)/Зл. Итак, алгоритм Кармаркара требует выполнения следующих этапов.
Этап О. Алгоритм начинается с точки Х0 = (1/п, 1/п, 1/п), вычисляются параметры г = - 1) и а = (п - 1)/Зп.
Основной этап к. Определяем
Dt = diag{x„......xj,
I 1 J
и вычисляем
Y -IA
IV, c.
x4.,=
новое новое
где с= [I - РГ(РРГ)P](CD/
Пример 7.7.3
Рассмотрим следующую задачу ЛП, которая уже приведена к форме, необходимой для выполнения алгоритма Кармаркара.
Минимизировать z = 2хх + 2х2 - Зх3
при ограничениях
*, - 2*2 + *3 = О, хг + х2 + х3 = 1, хх, х2, х3> 0.
Эта задача удовлетворяет всем условиям алгоритма Кармаркара, а именно точка X = (1/3, 1/3, 1/3) удовлетворяет уравнению х, - 2х2 + х3 = 0 и оптимальное значение целевой функции равно нулю (оптимальным решением является вектор (О, 0,6, 0,4)).
Итерация 0
с = (2, 2,-3), А = (-1,-2,3),
V 1 1 Ч 1 2
МзЗз} = а=9
= 0.33333,
D„ =
Используя проективные преобразования, получаем У0: Итерация 1
III 3 3 3
cD0 = (2,2,-3)
I 0 0Л
0 i о о о
AD0= (-1,-2,3)
i О О
О I о
О 0 1
I 2
"з" 3
ч з/
| 10 0 | |
I - РГ(РРГ)Р = | 0 I 0 | |
| ,0 0 1, | |
Г- - О
3 з
U 1 U
1 42
25 -20 -5N -20 16 4 ч -5 4 1 ,
Отсюда получаем
с =[I-Pr(PP) P](CDk)7 =
25 -20 -5"l -20 16 4 -5 4 1
( i\ з
25 -20 V-5y
Далее находим
Hc„ll = J25:+(-20);+(-5)Ao,257172. 1262
ill] -Л x -! x-lx(25.-20,-5)r: 3 3 3j 9 V6 0,257172 126 v y
= (0,263340, 0,389328, 0,347332)r.
Теперь найдем Xt D Y ш
V - 0 hohoc Л
ID Y
"О л новое
1d,yho»« = -(U,l)(0,263340,0,389328,0,347332)r =
" = yho».k = (0,263340,0,389328,0,347332/ ,
z, =0,26334. Итерация 2
cD, =(2,2,-3)
AD, =(1,-2,
0,263340 0
0 0,389328 0 0 0 0,347332
= (0,526680,0,778656, -1,041996)
(0,263340 0
0 0.389328 0 0 0 0,347332
= (-0,263340, -0,778656,1,041996)
(ppT =
I - РГ(РРГ) p =
-0,26334 -0,778656 1,041996 1 1 1 J
-0,263340 Л -0,778656 1 1,041996 1
0,567727 0 0 0,333333J
Г-0,263340 1 -0,778656 1 1,041996 1
0,567727 0 V-0.263340 -0,778656 1,0419961
0 0,33333