Преобразованная задача имеет тот же тип, что и исходная. Мы можем опять начать решение этой задачи с точки 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

ч з/

Г- - О

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