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

4. Симплекс-метод

Основная идея симплекс-метода.

Рассмотрим стандартную ЗЛП.

max(c1x1 + c2x2 + ... + cnxn)

Если b ≥ 0, то x = 0 — допустимый вектор. Если при этом c ≤ 0, то для любого допустимого вектора справедливо cx ≤ 0, следовательно, нулевой вектор является оптимальным. Если найдется такое s, при котором cs > 0, то попытаемся увеличить xs, не меняя при этом других координат и сохраняя условие допустимости. Ясно, что если для всех i ∈ {1, 2, ... , m} выполнено неравенство ais ≤ 0, то величину xs можно увеличивать неограниченно и, следовательно, целевая функция на множестве допустимых векторов не ограничена сверху. Если же найдется такое i, при котором ais > 0, то неравенство

ограничивает рост xs величиной bi/ais. Положим

Если α > 0, то получим новый допустимый вектор αes, где es — вектор, у которого все компоненты равны 0, кроме s-ой, равной 1. Значение линейной формы на векторе αes равно αcj > 0. Можно проверить, что замена переменной xs на переменную

приведет к стандартной задаче с неотрицательной правой частью и процесс можно повторить. Указанную замену переменных можно выполнить и при α = 0 (так и делается), однако при этом «новый» допустимый вектор равен «старому». Заметим, что существуют примеры, показывающие, что условие c ≤ 0 не является необходимым условием оптимальности точки x = 0.

Числовой пример применения симплекс-метода.

Рассмотрим ЗЛП:

max(2x1 + x2)

Для ее решения введем новую переменную x0 = 2x1 + x2.

Задача теперь заключается в максимизации линейной функции x0 при ограничениях в виде требованиях неотрицательности xj ≥ 0 (j=1,2,...,5) и системы ограничений:

Роль переменной, помещенной в рамку, будет ясна в дальнейшем. В системе линейных уравнений уже выделены базисные (связанные) переменные x0, x3, x4, x5 и небазисные (свободные) переменные x1, x2. Выразим базисные переменные через небазисные:

Обращая небазисные переменные в ноль, получим частное решение системы уравнений x* = (0, 0, 32, 17, 5)T и значение целевой функции x*0 = 0. Заметим, что это решение удовлетворяет требованиям неотрицательности (это произошло из-за того, что правая часть в системе неотрицательна). Таким образом, x* — это допустимый вектор задачи.

Этот вектор не является оптимальным. Действительно, в выражении x0 в системе переменные x1 и x2 входят с неотрицательными коэффициентами, поэтому значение целевой функции x0 можно увеличить за счет увеличения x1 и/или x2. Увеличивая x1 и/или x2, мы должны