Симплексный метод

Симплексный метод

Метод симплекс был представлен Джордж Данциг с 1946 г. Он алгоритм решение задач линейной оптимизации.

Он состоит в минимизации линейной функции нет реальные переменные,

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

Метод

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

1. Проблема написана под стандартная форма.
2. Решение найдено.
3. Найдите сводную колонку.
4. Найдите опорную линию и выполните метод Гаусса.

• ОСТАНОВКА. Оптимальное решение найдено или нет возможного решения.

Пример разрешения

Рассмотрим следующую задачу для применения симплекс-метода:

Шаг 1: Написание в стандартной форме и базовое решение

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

Для этого введем резервная переменная (Икс₃, Икс₄, Икс₅) в каждом из ограничений вида ≤, преобразовать их в равенства (см. курс по стандартной форме):

Затем приравняем целевую функцию к нулю: Z – 3 x₁ -Икс₂ – 0 х₃ – 0 х₄ – 0 х₅ = 0. То есть переменные канонической программы равны нулю, переменные отклонений равны элементу справа (б). С этого момента можно инициализировать массив симплекс-метода.

Исходная таблица симплекс-метода состоит из всех коэффициентов переменных решения исходной задачи и переменных отклонения.

В сторону: симплексное вырождение

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

Шаг 2-3: выбор входящей и исходящей переменной базы данных

Сначала устанавливаем переменную, которая входит в базу. Для этого выбираем столбец, значение которого в строке Z является самым низким среди всех негативов. В данном случае это будет переменная x₁ с коэффициентом -3. Столбец переменной, которая входит в базу, которая называется сводная колонка (в зеленом цвете).

Эта переменная выбрана потому, что ее влияние на значение Z является наибольшим (наибольший градиент). Занесение этой переменной в базу данных состоит в нахождении решения в пространстве решений по градиенту этой переменной. На следующей диаграмме ордината имеет наибольший градиент по отношению к решению Z = 0, поэтому мы будем следовать ее оси (считайте, что max z = x_Б) до тех пор, пока вы больше не сможете улучшить решение.

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

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

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

В этом примере: Cb:= 18/2, 42/2 и 24/3.
Если бы был элемент меньше или равный нулю, это частное не проводится. Когда все элементы сводная колонка при таком условии мы бы выполнили условие остановки и задача имела бы решение без ограниченной части.

Срок действия сводная колонка который привел к наименьшему ненулевому положительному частному в предыдущем делении, указывает строку резервной переменной, которая выходит из базы. В этом случае получается х₅, с коэффициентом 3. Эта линия называется линия вращаться (в красном).

Пересечение ул. линия поворота и сводная колонка Основные моменты поворотный элемент, в данном случае 3.

Шаг 3: обновление таблицы

Новые коэффициенты таблицы рассчитываются следующим образом (поворот Гаусса):

• В строке опорного элемента каждый новый элемент рассчитывается как: Элемент линии Pivot = Старый элемент линии Pivot / Pivot
• В сводном столбце: 0, кроме сводного столбца 1.
• В остальных строках вычисляется каждый элемент (перекрестное произведение): Новый линейный элемент = Старый линейный элемент – (Старая проекция опорной линии * Старая проекция опорного столбца / Старый опорный элемент).

Мы показываем расчеты для линии x₄ :

Таблица, соответствующая этой второй итерации (обратите внимание, что x₅ вышел и х₁ вернулась на место, более того, целевая функция уже не выражается через x₁ но в х₅, а его значение равно 24):

СТОП: условия остановки

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

Значение Z (столбец б) является оптимальным решением проблемы.

Когда это условие не выполняется, процессы повторяются итеративно.

Мы обнаруживаем, что в последней строке все коэффициенты положительны. Оптимальное решение: 33 с вектором решения (12, 3, 0, 0, 3). Вектор решения определяется значением б по строкам основных переменных. Обратите внимание, что х₅ = 3, т.е. ограничение 3 (содержащее резервную переменную x₅) не насыщен с 3 запасом.

Резюме

Особые случаи

• Бесконечные решения: когда симплекс останавливается и неосновные переменные имеют значение 0 в строке Z, это означает, что существует бесконечное количество решений. Чтобы узнать пределы гиперплоскости (или отрезка) решений, достаточно пересчитать симплекс, введя переменную (переменные) в базу.
• Нет решения : методом большой М, возможно, что поле определения быть пустым. В этом случае при расчете большого М некоторые искусственные переменные имеют ненулевое значение.
• Выбор входящей переменной: когда есть выбор среди входящих переменных (одинаковое значение), в качестве приоритета должна быть выбрана базовая переменная линейной программы.
• Выбор исходящей переменной: когда есть выбор среди исходящих переменных, сначала выбираются искусственные переменные, затем избыточные переменные, затем переменные отклонения и, наконец, основные переменные.
• Вырожденное решение: если оптимальное решение имеет нулевые базовые переменные, то оно называется вырожденным, это тот случай, когда базовых переменных больше, чем ограничений.

Пример

Обратите внимание, что иногда в таблицу записывают значение -Z с коэффициентами при c, в этом случае оптимальное решение получается, когда все коэффициенты отрицательные. Рассмотрим следующую линейную программу:

Первая итерация:

Что дает после поворота:

Вот вторая итерация до и после поворота:

Все члены -Z отрицательны, поэтому у нас есть оптимальное решение (0, 250, 0, 200, 500, 0, 100, 0), первое и третье ограничение не насыщены (переменные отклонения на 500 и на 100) ; целевая функция 350000.