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

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

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

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

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

Вид продукции Норма расхода ресурса на единицу прибыли Прибыль на единицу изделия
  А В  
Объем ресурса  

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



Базисные переменные Свободные члены (план) x 1 x 2 x 3 x 4
x 3
x 4
F j - C j  

1-я итерация . Находим генеральный столбец и генеральную строку: Симплексный метод решения оптимизационной задачи линейного программирования. - student2.ru Симплексный метод решения оптимизационной задачи линейного программирования. - student2.ru

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

Базисные переменные Свободные члены (план) x 1 x 2 x 3 x 4
x 1 0,4 0,2
x 4 0,8 - 1,6
F j – C j 0,2 - 1,4

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

Базисные переменные Свободные члены (план) x 1 x 2 x 3 x 4
x 1 - 0,5 0
x 2 - 2 1,25
F j - C j - 1 - 0,25

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

Наши рекомендации