"споткнемся" о точку оптимума В. Если же необходимо найти минимум целевой функции (вместо ее максимума), следует перемещаться в направлении, противоположном проекции градиента, т.е. от точки В к точкеА, где хх = 0.
Конечно, данную процедуру нельзя считать алгоритмом (в обычном смысле), но идея очень интересная! Чтобы воплотить эту идею в алгоритм, необходимо выполнить модификации приведенной процедуры, гарантирующие, что, во-первых, последовательность шагов, сделанных вдоль проекции градиента, не "перескочит" через точку оптимума, во-вторых, в общем л-мерном случае направления, указанные проекциями градиентов, не приведут алгоритм к неоптимальной точке (т.е. не "зациклят" алгоритм на неоптимальной точке). Если реализовать эти условия, то получим вполне работоспособный алгоритм.
7.7.2. Алгоритм Кармаркара
Существует несколько вариантов алгоритма Кармаркара. Мы рассмотрим исходный вариант, предложенный его автором. Кармаркар предполагал, что задача ЛП приведена к следующему виду.
Минимизировать z = СХ
при ограничениях
АХ = 0, IX = 1, Х>0.
Здесь все ограничения представлены в виде однородных уравнений, за исключением ограничения IX = X" ,-v/ = l> которое определяет л-мерный правильный симплекс.4 Обоснованность алгоритма Кармаркара "покоится" на выполнении двух условий.
1. Вектор Х=-,-.....- ) удовлетворяет ограничениям АХ = О.
\п п п)
2. min z = 0.
Кармаркар предложил алгебраические преобразования, приводящие общую задачу ЛП к виду, представленному выше. Эти преобразования показаны в следующем примере. Там также показано, как в результате преобразований добиться того, чтобы вектор X = (1/п, 1/п, 1/л) являлся допустимым решением системы АХ = 0 (условие 1). Преобразования, необходимые для выполнения условия 2 (min г = 0), мы не приводим из-за их громоздкости и трудоемкости.
4 Симплексом (л-мерным) называется выпуклая оболочка п точек X,, Х2, Х„, не лежащих на одной (п - 2)-мерной плоскости. Точки X,, Х2, Хп являются вершинами симплекса, при этом любую точку симплекса можно представить как выпуклую комбинацию (см. раздел 7.1) его вершин. Двухмерный симплекс - это отрезок, трехмерный - треугольник, четырехмерный - тетраэдр. (Здесь размерность симплекса определяется по размерности пространства, а не по размерности (л - 1)-мерной гиперплоскости, на которой он расположен.) В данном случае вершинами симплекса являются точки X, = (0, 1, ...,0), i= 1, л. Такой симплекс является частным случаем правильного симплекса. -Прим. ред.
Пример 7.7.1
Рассмотрим следующую задачу.
Максимизировать z = ух + у2
при ограничениях
У, + 2у2<2, */„*/2>0.
С помощью дополнительной переменной у3 > О преобразуем ограничение ух + 2у2 < 2 в равенство:
i/, + 2i/2 + z/3 = 2.
Теперь введем неравенство
Ух + Уг + У г U,
где U - достаточно большое положительное число, но такое, которое не удаляло бы ни одной допустимой точки исходного пространства решений. В данном примере, исходя из равенства ух + 2у2 + у3 = 2, достаточно взять U, равное 5. После введения еще одной дополнительной переменной у4 получаем
Ух +</2 + г/з + 2Л = 5-
Теперь можно сделать уравнение ух + 2у2 + у3 = 2 однородным, умножив его правую часть на (г/, + у2 + у3 + у4)/5, поскольку последнее соотношение равно 1. Таким образом, после приведения подобных членов получаем
3У1+8у2 + 3Уз-2у4 = 0.
Чтобы преобразовать равенство ух + у2 + у3 + у4 = 5 в уравнение, определяющее симплекс, введем новые переменные хх = yjb, / = 1,2, 3, 4. Получаем следующую задачу ЛП.
Максимизировать z = Ьхх + 5дг2
при ограничениях
Зхх + 8х2 + Зх3 - 2х4 = О, хх + х2 + х3 + х4 = 1, х>0, i = l,2, 3, 4.
Теперь обеспечим выполнение условия, что точка Х = (1/л, 1/п, 1/п), являющаяся центром (барицентром) симплекса, будет удовлетворять однородному уравнению. Для этого от левой части каждого однородного уравнения отнимем искусственную переменную с коэффициентом, равным алгебраической сумме всех коэффициентов левой части уравнения (в данном случае имеем 3+8+3-2 = 12). Эта искусственная переменная также прибавляется к уравнению симплекса и в виде штрафа появляется в выражении целевой функции. В нашем примере искусственная переменная хь войдет в задачу ЛП следующим образом.
Максимизировать z = Ьхх + Ьх2 - Мхь
при ограничениях
Зхх + 8х2 + 3*3 - 2х4 - 12хъ = О,
ОС I I ОС1 j
*,>(),/= 1,2.....5.
Для этой системы уравнений новый центр симплекса (1/5, 1/5, 1/5) является допустимым решением однородного уравнения. Значение константы М в выражении целевой функции должно быть достаточно большим, чтобы привести перемен-ную хь к нулевому значению (сравните с М-методом из раздела 3.4.1).
Последний пример показывает, что любую задачу ЛП можно с помощью преобразований привести к виду, который необходим для выполнения алгоритма Кармаркара. Но эти преобразования громоздкие и неочевидные, поэтому их редко используют на практике. Существуют различные модификации алгоритма, которые не требуют обязательного выполнения второго условия (min г = 0).
Пример 7.7.2
Рассмотрим еще раз задачу из примера 7.7.1.
Максимизировать г=у1+у2
при ограничениях
Уг + 2уг<2,
Начнем с формулировки прямой и двойственной задач.
Прямая задача Двойственная задача
Максимизировать уо = yi + Уг при ограничениях yi + 2у2 < 2,
Уь Уг 2 0.
Ограничения этих задач в стандартной форме запишутся так:
у1 + 2уг+у3 = 2,у3>0.
w,-w2 = l,w2>0. (1)
Из условия оптимума у0 = w0 вытекает, что
yi+y2-2Wl = 0. (2)
Выбираем достаточно большое число М, чтобы выполнялось неравенство
y.+y. + yw. + wM. (3)
Теперь путем введения дополнительной переменной преобразуем неравенство (3) в равенство:
У1+У2 + Уз + и>х + и>2 + 51=М, SjO. (4)
Далее введем новую переменную s2 такую, что следующие два равенства, вытекающие из равенства (4), будут выполняться тогда и только тогда, когда s2 = 1.
</i + У г + Уз + wi + w2 + si - S2M = °.
y1 + y1 + ya + wl+w2 + sl+s2 = M + 1. (5)
При условии s2 = 1, что обусловливают равенства (5), ограничения (1) можно записать как
У, + 2</2 + </,-282 = 0.
ш, - и>2 - ls2 = 0. (6)
Минимизировать щ = 2щ при ограничениях
w,>\ 1 2*,>lj
Wi > 0.