7.7.1. Основная идея метода Кармаркара

Рассмотрим очень простой пример.

Максимизировать г = хх при выполнении ограничения

0<x,<2.

Вводим дополнительную (остаточную) переменную х2. Задача в стандартной форме будет записана следующим образом.

Максимизировать г = х1

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

ос j ~\~ ос 2) хх, х2 > 0.

Эта задача представлена на рис. 7.6. Ее пространство решений совпадает с отрезком прямой АВ. Направление возрастания целевой функции z совпадает с положительным направлением оси хх.

Рис. 7.6. Иллюстрация основной идеи метода Кармаркара

Начнем поиск оптимального решения с произвольной внутренней (не крайней) точки С пространства допустимых решений (отрезок АВ). Градиент целевой функции г = х, в точке С показывает направление скорейшего возрастания функции г. Если мы зафиксируем какую-нибудь точку вдоль градиента и опустим из нее перпендикуляр на пространство допустимых решений, то получим новую точку D с лучшим значением целевой функции. Такое улучшение значения целевой функции получено вследствие движения по направлению проекции CD градиента. Если мы повторим описанную процедуру для точки D, получим новую точку Е, которая будет еще ближе к точке оптимума В. Таким образом, если мы будем двигаться (но осторожно) в направлении проекции градиента, то, вероятно, рано или поздно

споткнемся о точку оптимума В. Если же необходимо найти минимум целевой функции (вместо ее максимума), следует перемещаться в направлении, противоположном проекции градиента, т.е. от точки В к точкеА, где хх = 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).