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

Введение

Задача линейного программирования (ЗЛП) состоит в определении значений упорядоченной совокупности переменных x_j, j=1(1)n при которых линейная целевая функция достигает экстремального значения и при этом выполняются (удовлетворяются) все ограничения (они также линейные) в форме равенств или неравенств. Требуется найти план  Х _<n> = <x₁, x₂, ..., x_n>, который обеспечивает получение целевой функцией с экстремальным значением. Идеи моделей линейного планирования (программирования) впервые были высказаны и опубликованы советским математиком Л. В. Канторовичем в 1939 году в работе "математические методы организации и планирования производства". В 1975 году Л. В. Канторович и Т. Купманс получили Нобелевскую премию по экономическим наукам с формулировкой «за их вклад в теорию оптимального распределения ресурсов». В 1947 г. очень близкие идеи высказаны американским математиком Дж. Данцигом. А еще позднее стали массово появляться работы, посвященные проблемам выбора оптимальных решений в силу их исключительной важности. Признание приоритета за Л. В. Канторовичем не оспаривалось практически никогда, а после присуждения Нобелевской премии тем более. 

Исходные данные примера

Найти минимум линейной формы Q = x₁+x₂ + x₃

Как видим, ЗЛП уже в канонической форме: b_j>0, j =1(1)n, Q min, базис выделен. 1.   1. Устанавливаем, совпадают ли ранги матриц системы ограничений и расширенной. Ранги совпадают, следовательно, система ограничений совместна.

Разделяем переменные на базисные: x₁, x₂, x₃  с номерами φ = 1, 2, 3; и свободные: x₄, x₅, x₆ . Выразим базисные переменные и целевую функцию через свободные переменные.

Исходный опорный план x⁰_<6> получаем при x₄ = x₅ =x₆ =0, т. е. x⁰_<6> =<5, 3, 5, 0, 0, 0>. Так как все β_ф>0, то этот план – допустимый, а значение целевой функции в точке x⁰_<6>, равно Q(x⁰_<6>) =γ₀ = 13.

2. Далее в соответствии со структурной схемой алгоритма установим, является ли план x⁰_<6> оптимальным. Для этого формируем симплекс таблицу.

Оптимален ли опорный план? Так как некоторые из коэффициентов при свободных переменных в целевой функции (см.последнюю строку табл.) положительные (γ₄>0, γ₆ >0), то в соответствии с алгоритмом план x⁰_<6> , не является оптимальным, т.е. ЦФ можно уменьшить, увеличением соответствующих свободных переменных (множество Г ={4,6}). Среди коэффициентов ЦФ находим наибольший γ_v

3. Ввод переменной в базис. Индекс ν найденного коэффициента (v = 6) указывает, какую переменную надо ввести в базис для оптимизации плана. В базис вводится переменная х₆ (ее будем увеличивать до момента, когда нарушится первый раз некоторое ограничение). Столбец, где находится х_6, называется направляющим.

4. Устанавливаем далее существование оптимального плана. В направляющем столбце (отмечен заливкой, тот где х₆) симплекс таблицы проверяем знаки у коэффициентов. Если имеются положительные коэффициенты (α₂₆ = 1 > 0, α₃₆ = 6 > 0), то оптимальный план существует. Это означает, что в базисе имеются переменные, которые с ростом х₆ будут уменьшаться до нуля.

5.  Вывод переменной из базиса. Очевидно, из базиса выводится та переменная, которая раньше других обратится в нуль с возрастании х₆. Находим эту переменную среди тех, для которых α_ф6>0

Исключается из базиса, таким образом, переменная х₃ и она включается в число свободных переменных. Строка, где находится х_3, называется направляющей, а элемент α₃₆ - генеральным (разрешающим) элементом.

Таким образом, подготовлен новый шаг итерационного процесса. Формируем вновь подмножества базисных переменных: x₁, x₂, x₆  с номерами φ = 1, 2, 6; и свободные: x₄, x₅, x₃ . 6. Переходим к новой точке (вершине) симплекса. Для этого формируем новую симплексную таблицу путем использования промежуточной (вспомогательной) таблицы.

Формирование новой и вспомогательной симплексной таблицы:

1.          Вычисляют λ =1/α_iv = 1/α₃₆ =6 ^-1 и вписывают в клетку генерального элемента.

2.          Умножение на (+λ) элементов направляющей строки и на (-λ) элементов направляющего столбца и запись результатов в нижние полуклетки (кроме генерального элемента).

3.          Выделение в направляющих строке верхних, а в столбце – нижних полуклеток.

4.          Запись во все остальные клетки произведений, соответствующих выделенных элементов (полуклеток).

 Формирование новой симплексной таблицы:

1.          В направляющие строку и столбец в верхние полуклетки вносим элементы соответствующих нижних полуклеток.

2.          Во все остальные клетки запишем суммы чисел из верхних и нижних полуклеток вспомогательной таблицы.

После заполнения таблицы находим новый опорный план при x₃ = x₄ = x₅ =0 и значение ЦФ: 

Далее, следуя алгоритму, выясним, является ли полученный план оптимальным, т.е. можно ли уменьшать значения ЦФ далее. Для этого проверяем знак у коэффициента (γ_j ) ЦФ. Наличие γ_j > 0 говорит, что ЦФ можно еще уменьшить, т.е. полученный план – не оптимальный.

Определяем индекс свободной переменной, увеличение которой приведет к уменьшению ЦФ.

Для оптимизации переменную х₄ следует ввести в базис. В новой таблице нормированный столбец, содержащий х₄. Теперь выясним, существует ли оптимальный план, т.е. стоит ли его определять. Для этого определяем, есть ли в направляющем столбце положительные коэффициенты у некоторых (хотя бы у одной) базисных переменных. Очевидно, что эта базисная переменная будет уменьшаться с ростом свободной переменной х₄. Такая переменная в таблице есть (она не единственная) – это 5/3 и 1/3 соответственно у х₂ и х₆. Из этого следует, что оптимальный план существует. Определяем индекс переменной, которую необходимо вывести из базиса, т.е. ту, которая раньше других обратится в ноль.

Находим эту переменную из условия:

Из базиса, таким образом, должна быть выведена переменная х₂. Для следующего итерационного шага имеем: базисные переменные x₁, x₄, x₆  с номерами φ = 1, 4, 6; и свободные: x₂, x₃, x₅.

Формируем вспомогательную таблицу 2: 1.          Вычисляют λ = 1/α_iv = 1/α₂₄ = 3/5 и вписывают в клетку генерального элемента.

2.          Умножение на (+λ) элементов направляющей строки и на (-λ) элементов направляющего столбца и запись результатов в нижние полуклетки (кроме генерального элемента).

3.          Выделение в направляющих строке верхних, а в столбце – нижних полуклеток.

4.          Записываем во все остальные клетки произведений, соответствующих выделенных элементов.

Анализ таблицы показывает, что все коэффициенты при свободных переменных в нижней строке таблицы отрицательные, следовательно, план X³_<6>= <71/10, 0, 0,13/10, 0, 2/5 > для данной ЗЛП является оптимальным. Он обеспечивает получение наименьшего значения ЦФ Q₂(x³_<6>) = 77/10 < Q₁(x¹_<6>) = 53/6, где план Q₁(x¹_<6>) = x₁, +x₂ +x₃ получен ранее.

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