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

↑

▷ Содержание

⇐ ПредыдущаяСтр 4 из 6Следующая ⇒

Симплексный метод это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной точки к другой. При этом значение целевой функции улучшается. Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной, приходят к искомому оптимуму. На этом принципе основан симплекс -метод. Симплекс это выпуклый многогранник в n -мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов, кроме случаев зацикливания. Алгоритм симплексного метода состоит из ряда этапов. Первый. Строится исходная оптимиз модель. Далее исходная матрица условий преобразуется в приведенную каноническую форму. если после добавления дополнительных переменных матрица условий не содержит полную единичную подматрицу, то вводятся искусственные переменные, которые не имеют никакого экономического смысла. Они вводятся исключительно для того, чтобы получить единичную подматрицу и начать процесс решения задачи при помощи симплексного метода. Второй. Строится исходная симплекс-таблица и отыскивается некоторое начальное базисное решение. Множество переменных, образующих единичную подматрицу, принимается за начальное базисное решение. Третий. Проверка базисного решения на оптимальность осуществляется при помощи специальных оценок коэффициентов целевой функции. Если все оценки коэффициентов целевой функции отрицательны или равны нулю, то имеющееся базисное решение оптимальное. Четвертый этап. Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличивает целевую функцию. При решении задач на максимум прибыли в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по максимальному положительному значению оценки коэффициента целевой функции. Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом. Далее, если хотя бы один элемент генерального столбца а ij 0 строго положителен, то отыскивается генеральная строка. Для отыскания генеральной строки все свободные члены делятся на соответствующие элементы генерального столбца. Из полученных результатов выбирается наименьший. Соответствующая ему строка на данной итерации называется генеральной. Она соответствует ресурсу, который лимитирует

Продолжение

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

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

Пример решения оптимизационной задачи линейного программирования симплексным методом

Пусть необходимо найти оптимальный план производства двух видов продукции х1 и х2 Табл– Исходные данные примера

1. Построим ОМ ограничение по ресурсу А; ограничение по ресурсу В. 2. Преобразуем задачу в приведенную каноническую форму. Для этого достаточно ввести дополнительные переменные x3 и x4. В результате неравенства преобразуются в строгие равенства: Построим исходную симплексную таблицу и найдем начальное базисное решение. Им будет пара значений дополнительных переменных, которым соответствует единичная подматрица х3=20 и х4=36.

1-я итерация. Находим генеральный столбец и генеральную строку:

Генеральный элемент равняется 5.

2-я итерация. Найденное базисное решение не является оптимальным, так как строка оценок (F j - C j) содержит один положительный элемент. Находим генеральный столбец и генеральную строку: max(0,0,3,-1,4,0)=0,2

Найденное решение оптимально, так как все специальные оценки целевой функции (Fj - Cj) равны нулю или отрицательны. F (x) =29; x1=2; x2 =5.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры