Теперь определим новые переменные xv х2, х7 на основе соотношений
у~(М + 1)хг]=1, 2,3,
(М + l)Xj, j = 4, 5,
Sl = (M+l)x6, s2 = (M + l)x7.
Подставляя последние выражения в равенства (2), (5) и (6), получим новые ограничения в виде равенств.
+ х,- 2ха = О,
, + х2 + х3 + х4 + хь + хе - Мх7 = О, [ + х2 + х3 + х4 + х5 + х6 + х7 = 1, + 2х2 + х3 - 2х7 = О, х5 -~ х7 О, .>0,;=1,2, 7.
Теперь осталось ввести искусственную переменную xs в левую часть каждого ограничения - эта переменная будет новой целевой функцией, которую следует минимизировать. Если прямая задача имеет допустимое решение, то минимум этой целевой функции будет равен нулю. Но алгоритм Кармаркара дополнительно требует, чтобы точка
х-(- 1111111
удовлетворяла системе АХ = 0. Это условие можно выполнить для однородной системы (т.е. для системы, у которой правые части уравнений равны нулю), если соответствующий коэффициент при искусственной переменной хе в любом уравнении систем будет равен сумме всех остальных коэффициентов этого уравнения. С учетом этого замечания получаем следующую преобразованную задачу ЛП.
Минимизировать z = xs
при ограничениях
jCj 4- х2 - 2х4 - 0х3 = О, х
+ 2х2 + х3 - 2х7 - 2xs =
- Мх7 - (6 - M)xg = О, х, + %гх, + х, - %гхч - zxs = О,
ОС OCrj I ) у
х, + х, + я, 4- х, + ли 4- х* 4- х, + xa = 1, x>0,j=l,2, ...,8.
Отметим, что решение этой задачи дает оптимальные решения как прямой, так и двойственной задач.
Теперь опишем основные этапы алгоритма Кармаркара. На рис. 7.7, а показано типичное трехмерное пространство решений, определяемое однородной системой ограничений АХ = 0, состоящей из одного уравнения. В данном случае пространство решений совпадает с отрезком прямой АВ, лежащим внутри симплекса IX = 1, причем точка (1/3,1/3,1/3) является допустимой внутренней точкой пространства решений. Аналогично на рис. 7.7, б показано четырехмерное пространство решений (треугольник ABC), определяемое однородной системой ограничений, также состоящей из одного уравнения. В этом случае центром симплекса является точка (1/4, 1/4, 1/4, 1/4).
а) Трехмерное пространство решений
(о, 0, 0, 1)
(0,1,0,0)
б) Четырехмерное пространство решений Рис. 7.7. Трех- и четырехмерный симплексы
Принципиальная идея Кармаркара заключается в том, что вычисления начинаются с внутренней точки, соответствующей центру симплекса, далее в направлении проекции градиента определяется новая точка решения, которая должна быть строго внутренней, т.е. все ее координаты должны быть положительными. Это является необходимым условием сходимости алгоритма.
Чтобы новая точка решения была внутренней, она не должна выходить за пределы симплекса. (Это значит, что на рис. 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 Здесь надо уточнить, что центр этой сферы находится в барицентре симплекса. Далее в этом разделе, не оговаривая этого явно, везде предполагается, что центры всех сфер совпадают с барицентром симплекса. - Прим. ред.