6.5. Симплексный метод и приведение задачи лп к правильной форме

Для приведения канонической задачи ЛП к правильной форме и улучшения начального допустимого плана (перехода к другому начальному допустимому плану, значение целевой функции которого меньше) используется симплексный метод (фактически метод Жордана – Гаусса при особом выборе разрешающего или ключевого элемента).

Пусть в столбце матрицы A, где необходимо получить нули и единицу (ключевой столбец), минимум отношения ресурсов  к соответствующим положительным элементам этого столбца достигается в строке (ключевая строка): для ключевого элемента выполняется

для любого .

Тогда при исключении при помощи ключевого элемента получим новую правую часть при , а при также .

Таким образом, при таком выборе ключевого элемента не нарушается каноничность задачи, и после использования преобразования Жордана – Гаусса получим правильный столбец. Такое преобразование называется симплексным. Обычно при приведении к правильному виду в качестве ключевого столбца выбирается тот, у которого в дополнительной строке стоит наименьший коэффициент целевой функции, если над ним в столбце имеется . При этом новая ключевая строка не должна совпадать с полученной ранее, чтобы не испортить уже полученные правильные столбцы. Проводя такие преобразования, приходим либо к правильной форме (отбрасывая как в методе Гаусса нулевые строки-тождества), либо получим (как в методе Гаусса) невозможное равенство вида

,

где , и .

В последнем случае ограничения задачи несовместны (область  Ǿ) и задача ЛП неразрешима.

Если симплексное преобразование применяется к правильной задаче для улучшения начального допустимого плана, то, выбрав новый ключевой столбец (новую базисную переменную из числа старых свободных переменных) и проведя симплексное преобразование, изменим какой-нибудь старый правильный столбец. Фактически будет осуществляться переход к новой вершине симплекса и если решение есть, то, перебрав несколько вершин (а их в симплексе конечное число!), найдется вершина, где значение целевой функции будет оптимальным (наименьшим).

 Замечание. Если при наличии некоторых значений , возникает повтор правильных столбцов (зацикливание), то выход из цикла осуществляется выбором ключевого столбца, не совпадающего со столбцами из цикла.

Пример 18. Приведем к правильной форме каноническую задачу ЛП

, ,

где ограничения

Расширенная матрица этой задачи записывается следующим образом:

.

Выбираем первый столбец за ключевой и ключевой элемент а₁₁ из минимума отношений

.

Проделаем симплексное преобразование над первым столбцом (S_i – строки):

.

Следовательно, новая форма

.

В матрице снова находим новый ключевой столбец (третий) и ключевой элемент а₂₃:

min .

Получая на месте а₂₃ единицу, имеем матрицу

.

в качестве ключевого возьмем второй столбец, потому что выбор четвертого столбца, где , и ключевой элемент 6/5, изменит первый правильный столбец.

Так как , то в качестве ключевого элемента примем а₁₂ = 4/5.

Проделаем симплексные преобразования:

.

Таким образом, получена правильная форма со свободной переменной и базисными переменными , , . Начальный допустимый план , значение целевой функции .

Проверим вычисления, найдя значения исходной целевой функции

.