Симплексный метод решения ЗЛП

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

Использование графического метода (когда оптимальное решение находится с помощью геометрических построений) возможно только при решении ЗЛП с двумя переменными.

При бóльшем числе переменных необходимо применение алгебраического аппарата.

Общий метод решения ЗЛП называется симплексным (или симплекс-методом).

Идея симплекс-метода

При решении ЗЛП графическим методом было отмечено, что оптимальному решению всегда соответствует одна из угловых точек многоугольника (многогранника) решений. Именно этот результат и положен в основу симплекс-метода.

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

Переходы от одной угловой точки к другой необходимо осуществлять до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.

Итак, симплексный метод предполагает:

1. умение находить начальное опорное решение;

2. наличие признака оптимальности опорного решения;

3. умение переходить к лучшему (или, по крайней мере, не худшему) опорному решению.

Геометрическая интерпретация идеи симплекс-метода

x₂

П усть имеется задача на отыскание минимального значения целевой функции

.

На рисунке изображён многоугольник её решений.

Допустим, что найдено первоначальное опорное решение, соответствующее угловой точке . Тогда прямая проходит через точку , и имеет значение .

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

x₁

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

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

Алгоритм симплекс-метода

1. Нахождение первоначального опорного решения

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных , удовлетворяющие условиям-равенствам и обращающие в минимум линейную функцию этих переменных.

(1)

(2) . (3)

Положим, что все уравнения системы (2) являются линейно независимыми.

Равенства называются линейно независимыми, если никакое из них нельзя получить из других путём умножения на какие-то коэффициенты и суммирования, т.е. никакое из них не является следствием остальных.

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

Свободным переменным можно придавать какие угодно значения, не нарушая условий (2) и (3).

Если свободные переменные приравнять к нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (2) будет являться опорным решением ЗЛП.

Пример.

1) Приводим данную задачу к ОЗЛП.

.

2) Разделим переменные на базисные и свободные.

Количество базисных переменных равно числу уравнений в системе ограничений:

Количество свободных переменных:

Выберем в качестве базисных переменных те дополнительные переменные, которые добавили к неравенствам, чтобы получить равенства:

.

Т.к. каждая из этих переменных входит в одно из уравнений системы ограничений с коэффициентом, равным 1, а во все остальные уравнения – с коэффициентом, равным 0, то они легко выражаются через переменные и .

3) Выразим базисные переменные и целевую функцию через свободные переменные.

4) Полагаем свободные переменные, равными нулю.

тогда

Так как то полученное решение является опорным (на графике – точка  ).

1. Проверка опорного решения на оптимальность

Теорема. Опорное решение является оптимальным, если коэффициенты при свободных переменных в целевой функции отрицательны или равны нулю.

Если полученное опорное решение не оптимально, то нужно перейти к другому опорному решению.

Пример (продолжение).

1. Проверим, является ли полученное опорное решение оптимальным.

Т.к. коэффициенты при свободных переменных и положительны, то это решение не является оптимальным.

1. Переход к следующему опорному решению

При переходе от одного опорного решения к другому между множествами базисных и свободных переменных происходит взаимообмен переменными: одна из базисных переменных переходит в разряд свободных, а одна из свободных переменных переходит в разряд базисных.

Например, для рассматриваемой задачи:

Для перехода к лучшему опорному решению следует увеличивать от исходного нулевого значения ту свободную переменную, которая в целевой функции имеет положительный коэффициент.

Однако увеличивать эту переменную следует так, чтобы значения базисных переменных оставались неотрицательными (так, чтобы не выйти за пределы допустимых решений).

Если в целевой функции несколько переменных имеют положительный коэффициент, то для обмена следует выбирать ту свободную переменную, которой соответствует . Это в большинстве случаев позволяет быстрее получить оптимальное решение.

Пример (продолжение).

1. Переходим к другому опорному решению.

И меющееся решение можно улучшить, если увеличить переменную , но только до 4, иначе станет меньше 0.

Выбранную свободную переменную обменивают с такой базисной, которая при увеличении этой свободной переменной первой обращается в ноль.

Т о есть меняем местами переменные и (переменную введём в базис, а сделаем свободной).

, .

,

.

,

.

,

.

Получим следующую систему уравнений:

.

Полагаем , тогда , , , (на графике - точка ).

1. Проверяем опорное решение на оптимальность.

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

1. Переходим к следующему опорному решению.

Переменную переведём в разряд базисных, а переменную - в разряд свободных.

,

.

,

.

,

.

,

.

Базисные переменные , , выражаются через , следующим образом:

.

Полагаем , тогда , , , (на графике – точка ).

Это решение является оптимальным, т.к. увеличение свободных переменных не приведёт к уменьшению (коэффициенты при свободных переменных в целевой функции отрицательны).

Максимум исходной целевой функции равен: .

Ответ: при , .

Симплексные таблицы

Процедура пересчёта коэффициентов в системе ограничений и в целевой функции при замене свободной переменной на базисную может осуществляться с помощью симплексной таблицы.

Пусть решается задача на отыскание минимума функции

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

,

где - дополнительные переменные, которые выбираются в качестве базисных.

, или

Исходные данные заносим в первую симплексную таблицу.

В левом столбце таблицы ( ) записываются свободные члены . В основную часть таблицы (начиная со второго столбца и первой строки) заносятся коэффициенты при свободных переменных.

В последней строке таблицы указываются коэффициенты целевой функции, взятые из выражения в скобках.

Далее таблица преобразуется по определённым правилам.

1. Выбирается максимальное (любое) положительное число в нижней строке симплексной таблицы (кроме столбца ’ ’).

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

1. Допустим, что правило I даёт нижний элемент -го столбца (столбец с номером называется ключевым).

Составляются все неотрицательные отношения элементов первого столбца (столбца свободных членов) к элементам ключевого столбца, другими словами, все отношения , для которых .

Элемент, скажем , который даёт наименьшее отношение , называется разрешающим, а строка с номером называется ключевой.

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

1. Новая таблица строится следующим образом:

   1. меняются местами обозначения ключевой строки и ключевого столбца ( и ), при этом остальные обозначения остаются без изменений;

   2. разрешающий элемент заменяется обратной величиной

, где - элементы новой таблицы;

1. каждый элемент ключевой строки заменяется его отношением к разрешающему элементу , , , ;

(новая строка получается из старой делением на разрешающий элемент )

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

, , , ;

1. все остальные элементы таблицы заменяются элементами вида

.

Последнее правило можно записать более коротко:

.

Далее переходим к п.I алгоритма.

Пример 1. ОЗЛП:

В качестве первоначальных базисных выбираем переменные ; выражаем их и целевую функцию через свободные переменные .

Ответ: при