Simplex method.ipynb

Симплекс метод

Один из самых первых методов оптимизации для задач линейного программирования.

Любую задачу ЛП можно представить в стандартной форме:

$$\min ; c^T x$$ $$\text{s.t.} \quad Ax = b$$ $$\quad ; ; x \geq 0$$

Такое представление осуществляется с помощью добавления в каждое неравенство $a^Tx \leq b$ slack-переменной:
$$a^Tx + \xi = b,$$
$$\xi \geq 0.$$

Для любой задачи линейного программирования возможны три случая:

1. Не существует ни одной допустимой точки: $P = {Ax = b, x \geq 0} ; = ; \emptyset$;
2. Задача неограничена: $\inf_{x \in P}c^T x ; = ; -\infty$;
3. Существует решение задачи $x^*$, доставляющее оптимум.

Центральным фактом, используемом в сиплекс методе, является следующее утверждение:
Пусть ЛП задача в стандартной форме ограничена. $x \in P$ - произвольная допустимая точка. Тогда существует вершина $x^{'}$ множества $P$ такая, что $c^Tx^{'} \leq c^T x$.

Таким образом, если оптимум достигается в некоторой точке, то он по необходимости достигается в некоторой вершине полиэдра $P$.

Симплекс метод в общем виде, начинает с некоторой выршины множества $P$, и на каждом шаге пытается перейти в соседнюю вершину, такую, значение функционала в которой не возрастает.

Уточнений требует процедура выбора начальной точки, а также процедура перехода в соседнюю вершину.

Удобным для вычислений является следующий критерий угловых точек:
$$x \in P - \text{вершина} \quad \Leftrightarrow \quad A_x ; \text{имеет линейно независимые столбцы},$$
где $A_x$ - матрица, полученная вычёркиванием столбоцов матрицы $A$ с такими индексами $j$, для которых $x_j = 0$.

Дополним столбцы $A_x$ до базиса, получим невырожденную квадратную матрицу $A_B$. Выразим базисные компоненты вектора x через остальные-небазисные:
$$x_B ; = ; A_B^{-1}b , - , A_B^{-1}A_N x_N ; \geq ; 0,$$
значение целевого функционала:
$$c^T x ; = ; c_BA_B^{-1}b , + , (c_N - c_B A_B^{-1} A_N) x_N.$$

В угловой точке, по построению, $x_N = 0$, но теперь мы можем попробовать увеличить значение некоторой координаты в $x_N$, чтобы уменьшить значение целевого функционала. Единственное ограничение, которое у нас есть: $x_B \geq 0$.

Поэтому будем увеличивать некоторую координату $x_N$ до тех пор, пока все координаты $x_B$ будут неотрицательными. После этого, новую ненулевую координату из $x_N$ сделаем базисной, обменяв с некоторой нулевой координатой из $x_B$.

Конкретная реализация симплекс метода зависит от того, как именно будет выбираться координаты.

Метод Блэнда: выбирать всегда координаты с наименьшим номером. Для него доказано, что такой симплекс-метод никогда не зациклится, и найдёт минимум за конечное число шагов.

Выбор начальной точки: запустившись из некоторой угловой точки, симплекс-метод всегда сможет решить задачу за конечное число шагов. Но, выбор начальной точки не совсем элементарная задача.

Для этого, на так называемой первой фазе симплекс метода, решают вспомогательную линейную программу:

$$\min ; \xi $$ $$\text{s.t.} \quad Ax - \xi = b$$ $$\quad ; ; x \geq 0$$ $$\quad ; ; \xi \geq 0$$

Для неё легко указать допустимую угловую точку: $(\xi_0, 0, 0, \dots, 0)$, где $\xi_0$ - минимальное число, чтобы все неравенства выполнялись.

Решив вспомогательную ЛП задачу на первом шаге, если $\xi < 0$, то исходная задача несовместна. Иначе мы получим допустимую угловую точку для второй нормальной фазы алгоритма.