Принципиальная идея Кармаркара заключается в том, что вычисления начинаются с внутренней точки, соответствующей центру симплекса, далее в направлении проекции градиента определяется новая точка решения, которая должна быть строго внутренней, т.е. все ее координаты должны быть положительными. Это является необходимым условием сходимости алгоритма.

Чтобы новая точка решения была внутренней, она не должна выходить за пределы симплекса. (Это значит, что на рис. 7.7, а новая точка не может быть точкой А или В, а на рис. 7.7, б- не может совпадать с точками отрезков АВ, ВС и АС.) Для того чтобы определить такую точку, построим сферу, вписанную в симплекс. В л-мерном пространстве в правильный симплекс можно вписать сферу с максимальным радиусом г, равным \lsjn(n -1) .5 Тогда пересечение сферы радиуса от (0 < а < 1) и пространства решений, определяемого системой АХ = 0, будет содержать только внутренние точки пространства решений с положительными координатами. В таком случае для определения новой точки решения можно перемещаться вдоль проекции градиента до тех пор, пока будем находиться внутри ограниченного пространства, являющегося пересечением шара радиуса аг и пространства, определяемого системой АХ = 0.

Новая точка решения не обязана быть центром симплекса. Поэтому, чтобы сделать алгоритм итерационным, необходимо найти способ перенести новую точку решения снова в центр симплекса. Для этого Кармаркар предложил оригинальную идею проективных преобразований. Пусть

xt х,.

i = 1, 2.....n.

где xkl - i-й элемент текущего решения, т.е. г-я координата текущей точки решения Х4. Такое преобразование правомерно, поскольку все xki > 0. Также отметим,

что по определению ,у, = 1 (т.е. 1Y= 1). Это преобразование можно записать в

матричном виде

Y Р.Х 1D/X

где D,. - диагональная матрица, у которой i-й диагональный элемент равен xkl. Это преобразование осуществляет взаимно-однозначное отображение Х-пространства в Y-пространство, поскольку нетрудно проверить, что из последней формулы следует

Х = 1D.Y

По определению min СХ = 0. Отсюда следует, что значение lDtY должно быть положительным. В таком случае исходная задача ЛП преобразуется в следующую.

Минимизировать z = CDtY

при ограничениях

ADkY = 0, 1Y-1, Y>0.

5 Здесь надо уточнить, что центр этой сферы находится в барицентре симплекса. Далее в этом разделе, не оговаривая этого явно, везде предполагается, что центры всех сфер совпадают с барицентром симплекса. - Прим. ред.

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