Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Прочие статьи цикла
Исследование операций
Метод ветвей и границ. Задача коммивояжера
Симплексный метод решения задач линейного программирования
Симплексный метод решения ЗЛП. Пример
Введение
Задача линейного программирования (ЗЛП) состоит в определении значений упорядоченной совокупности переменных xj, j=1(1)n при которых линейная целевая функция достигает экстремального значения и при этом выполняются (удовлетворяются) все ограничения (они также линейные) в форме равенств или неравенств. Требуется найти план Х <n> = <x1, x2, ..., xn>, который обеспечивает получение целевой функцией с экстремальным значением. Идеи моделей линейного планирования (программирования) впервые были высказаны и опубликованы советским математиком Л. В. Канторовичем в 1939 году в работе "математические методы организации и планирования производства". В 1975 году Л. В. Канторович и Т. Купманс получили Нобелевскую премию по экономическим наукам с формулировкой «за их вклад в теорию оптимального распределения ресурсов». В 1947 г. очень близкие идеи высказаны американским математиком Дж. Данцигом. А еще позднее стали массово появляться работы, посвященные проблемам выбора оптимальных решений в силу их исключительной важности. Признание приоритета за Л. В. Канторовичем не оспаривалось практически никогда, а после присуждения Нобелевской премии тем более.
Исходные данные примера
Найти минимум линейной формы Q = x1+x2 + x3
Как видим, ЗЛП уже в канонической форме: bj>0, j =1(1)n, Q min, базис выделен. 1. 1. Устанавливаем, совпадают ли ранги матриц системы ограничений и расширенной. Ранги совпадают, следовательно, система ограничений совместна.
Разделяем переменные на базисные: x1, x2, x3 с номерами φ = 1, 2, 3; и свободные: x4, x5, x6 . Выразим базисные переменные и целевую функцию через свободные переменные.
Исходный опорный план x0<6> получаем при x4 = x5 =x6 =0, т. е. x0<6> =<5, 3, 5, 0, 0, 0>. Так как все βф>0, то этот план – допустимый, а значение целевой функции в точке x0<6>, равно Q(x0<6>) =γ0 = 13.
2. Далее в соответствии со структурной схемой алгоритма установим, является ли план x0<6> оптимальным. Для этого формируем симплекс таблицу.
Оптимален ли опорный план? Так как некоторые из коэффициентов при свободных переменных в целевой функции (см.последнюю строку табл.) положительные (γ4>0, γ6 >0), то в соответствии с алгоритмом план x0<6> , не является оптимальным, т.е. ЦФ можно уменьшить, увеличением соответствующих свободных переменных (множество Г ={4,6}). Среди коэффициентов ЦФ находим наибольший γv
3. Ввод переменной в базис. Индекс ν найденного коэффициента (v = 6) указывает, какую переменную надо ввести в базис для оптимизации плана. В базис вводится переменная х6 (ее будем увеличивать до момента, когда нарушится первый раз некоторое ограничение). Столбец, где находится х6, называется направляющим.
4. Устанавливаем далее существование оптимального плана. В направляющем столбце (отмечен заливкой, тот где х6) симплекс таблицы проверяем знаки у коэффициентов. Если имеются положительные коэффициенты (α26 = 1 > 0, α36 = 6 > 0), то оптимальный план существует. Это означает, что в базисе имеются переменные, которые с ростом х6 будут уменьшаться до нуля.
5. Вывод переменной из базиса. Очевидно, из базиса выводится та переменная, которая раньше других обратится в нуль с возрастании х6. Находим эту переменную среди тех, для которых αф6>0
Исключается из базиса, таким образом, переменная х3 и она включается в число свободных переменных. Строка, где находится х3, называется направляющей, а элемент α36 - генеральным (разрешающим) элементом.
Таким образом, подготовлен новый шаг итерационного процесса. Формируем вновь подмножества базисных переменных: x1, x2, x6 с номерами φ = 1, 2, 6; и свободные: x4, x5, x3 . 6. Переходим к новой точке (вершине) симплекса. Для этого формируем новую симплексную таблицу путем использования промежуточной (вспомогательной) таблицы.
Формирование новой и вспомогательной симплексной таблицы:
1. Вычисляют λ =1/αiv = 1/α36 =6 -1 и вписывают в клетку генерального элемента.
2. Умножение на (+λ) элементов направляющей строки и на (-λ) элементов направляющего столбца и запись результатов в нижние полуклетки (кроме генерального элемента).
3. Выделение в направляющих строке верхних, а в столбце – нижних полуклеток.
4. Запись во все остальные клетки произведений, соответствующих выделенных элементов (полуклеток).
Формирование новой симплексной таблицы:
1. В направляющие строку и столбец в верхние полуклетки вносим элементы соответствующих нижних полуклеток.
2. Во все остальные клетки запишем суммы чисел из верхних и нижних полуклеток вспомогательной таблицы.
После заполнения таблицы находим новый опорный план при x3 = x4 = x5 =0 и значение ЦФ:
Далее, следуя алгоритму, выясним, является ли полученный план оптимальным, т.е. можно ли уменьшать значения ЦФ далее. Для этого проверяем знак у коэффициента (γj ) ЦФ. Наличие γj > 0 говорит, что ЦФ можно еще уменьшить, т.е. полученный план – не оптимальный.
Определяем индекс свободной переменной, увеличение которой приведет к уменьшению ЦФ.
Для оптимизации переменную х4 следует ввести в базис. В новой таблице нормированный столбец, содержащий х4. Теперь выясним, существует ли оптимальный план, т.е. стоит ли его определять. Для этого определяем, есть ли в направляющем столбце положительные коэффициенты у некоторых (хотя бы у одной) базисных переменных. Очевидно, что эта базисная переменная будет уменьшаться с ростом свободной переменной х4. Такая переменная в таблице есть (она не единственная) – это 5/3 и 1/3 соответственно у х2 и х6. Из этого следует, что оптимальный план существует. Определяем индекс переменной, которую необходимо вывести из базиса, т.е. ту, которая раньше других обратится в ноль.
Находим эту переменную из условия:
Из базиса, таким образом, должна быть выведена переменная х2. Для следующего итерационного шага имеем: базисные переменные x1, x4, x6 с номерами φ = 1, 4, 6; и свободные: x2, x3, x5.
Формируем вспомогательную таблицу 2: 1. Вычисляют λ = 1/αiv = 1/α24 = 3/5 и вписывают в клетку генерального элемента.
2. Умножение на (+λ) элементов направляющей строки и на (-λ) элементов направляющего столбца и запись результатов в нижние полуклетки (кроме генерального элемента).
3. Выделение в направляющих строке верхних, а в столбце – нижних полуклеток.
4. Записываем во все остальные клетки произведений, соответствующих выделенных элементов.
Анализ таблицы показывает, что все коэффициенты при свободных переменных в нижней строке таблицы отрицательные, следовательно, план X3<6>= <71/10, 0, 0,13/10, 0, 2/5 > для данной ЗЛП является оптимальным. Он обеспечивает получение наименьшего значения ЦФ Q2(x3<6>) = 77/10 < Q1(x1<6>) = 53/6, где план Q1(x1<6>) = x1, +x2 +x3 получен ранее.
Дальнейшие расчеты необходимо выполнять, начиная с нижней строки, и выполнить проверку плана на оптимальность. Если план оптимальный, то следует заполнить столбец, т.е. компоненты оптимального плана. Остальные клетки можно не заполнять.
Литература
Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.
Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.
Квейд Э. Методы системного анализа // Новое в теории и практике управления производством в США.–М.: Прогресс, 1971.– с.78-99. .
Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.
Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.
Пфанцагль И. Теория измерений. – М.: Наука, 1988.–384 с.
Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.
Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.
