Симплексный метод решения задачи линейного программирования
Трудность решения задачи линейного программирования заключается в том, что не все модели задач можно свести к равносильным моделям с двумя переменными, а с большим количеством ― практически невозможно решить.
Наиболее распространенным методом решения задач линейного программирования является так называемый симплекс-метод. Из геометрической интерпретации задача линейной оптимизации видно, что экстремум функции достигается в крайней (угловой) точке выпуклого многогранника, т.е. в области допустимых решений. Поэтому в основу симплекс-метода положена идея рассмотрения только крайних точек (вершин) многогранника, а не все бесконечное множество его точек.
Симплексный метод это метод последовательного улучшения планов, который является универсальным методом решения задач линейного программирования. Суть этого метода заключается в том, что вначале получают допустимый план, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение), оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций).
Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача. Результат каждой итерации (включая данные задачи) удобно записывать в виде симплексной таблицы (вид которой представлен при решении задачи примера 4). Направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи. Симплекс-метод основан на следующих свойствах ЗЛП:
1. Множество всех планов задачи линейного программирования выпукло.
2. Не существует локального экстремума, отличного от глобального. Другими словами, если целевая функция принимает экстремальное значение, то данное значение будет единственным.
3. Целевая функция задачи линейного программирования достигает своего максимального (минимального) значения в крайней точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
4. Каждой угловой точке многогранника решений отвечает опорный план задача линейной оптимизации.
Предположим, что в симплексной таблице содержится некоторый опорный план (см. пример 4). Через конечное число шагов либо будет найден оптимальный план задачи, либо будет установлено неразрешимость задачи. Перебор опорных планов осуществляется в процессе перехода от одного базиса системы переменных к другому базису. При этом приходится определять переменные, участвующие в преобразовании базиса. Переменная, включаемая в базис в задаче максимизации определяется по отрицательному коэффициенту в строке целевой функции симплексной таблицы. Если таких коэффициентов несколько, то выбирают максимальный по модулю. Такую переменную называют разрешающей, а столбец коэффициентов при ней разрешающим. Для выбора переменной исключаемой из базиса составляют симплексные отношения: это отношение свободного коэффициента к элементу такого же знака разрешающего столбца. Наименьшее из них и указывает уравнение (разрешающее), в котором содержится исключаемая переменная. После выбора разрешающего столбца и разрешающей строки определяется на их пересечении разрешающий элемент и осуществляется преобразование модели задачи к новому базису.
Симплексное преобразование после выбора разрешающего элемента при табличных записях выполняется по следующим правилам:
- Разрешающий элемент (ark) заменяют обратной величиной (т.е. 1/аrk);
- Остальные элементы разрешающей строки делятся на разрешающий элемент (а‘rj= ,j= );
- Остальные элементы разрешающего столбца делятся на разрешающий элемент и знак меняется на противоположный (a‘ik= —,i=);
- Остальные элементы таблицы преобразовываются по правилу прямоугольника: искомый элемент равен разности произведений элементов главной и побочной диагоналей, деленной на разрешающий элемент (по воображаемому прямоугольнику пересчета) (a‘ij= ,i=,j= ,i r,jk).
Таким образом, получаем новый опорный план задачи в следующей симплексной таблице. А для того, чтобы определить является ли новый опорный план оптимальным, необходимо знать следующие признаки:
Признак оптимальности задачи максимизации: Если все оценки индексной строки (строки целевой функции) не отрицательны, то соответствующий план является оптимальным в задаче максимизации.
Признак оптимальности задачи минимизации: Если все оценки индексной строки (строки целевой функции) не положительны, то соответствующий план является оптимальным в задаче минимизации.
В тех случаях когда затруднительно найти первоначальный опорный план канонической формы задачи линейного программирования применяется метод искусственного базиса (М – метод).
Решим симплексным методом следующую задачу.
Пример 4. Предприятие выпускает четыре вида продукции П1, П2, П3 и П4. Для производства продукции оно располагает тремя ресурсами, запасы которых ограничены величинами 35, 30 и 40 единиц. Удельные затраты на единицу продукции и цена единицы готовой продукции заданы в виде таблицы:
Расход ресурсов на единицу продукции
Тема 3. Симплексный метод решения задач линейного программирования
Суть симплекс-метода заключается в том, что решение ЗЛП осуществляется итерационно и основывается на переходе от одного допустимого базисного решения к другому, при котором значение целевой функции улучшается. Этот процесс длится до тех пор, пока дальнейшее улучшение целевой функции станет невозможно.
В алгебраических терминах симплекс-метод предполагает:
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходить к нехудшему опорному плану.
Геометрический смысл симплекс-метода состоит в последовательном переходе от одной вершины многогранника ОДР к соседней, в которой целевая функция принимает лучшее значение, до тех пор, пока не будет найдено оптимальное решение.
Симплексный метод универсален, поскольку позволяет решить любую ЗЛП.
2. Критерий оптимальности решения злп
Для использования симплекс-метода ЗЛП должна быть приведена к каноническому виду с предпочтительными переменными.
Критерий оптимальности. Решение ЗЛП является оптимальным, если неотрицательны коэффициенты целевой функции при переменных, имеющих определенный смысл (экономический, технологический, физический), и все свободные члены в правой части уравнений системы ограничений ( ).
В ходе решения ЗЛП могут возникнуть 4 случая:
1) , следовательно, план не оптимален и используется основной симплекс-метод;
2) , следовательно, план не оптимален и применяется двойственный симплекс-метод;
3) , следовательно, план не оптимален и применяется смешанный симплекс-метод;
4) , следовательно, согласно критерию оптимальности, план оптимален.
3. Алгоритм основного симплекс-метода:
1) Записать математическую модель в допустимом предпочтительном виде канонической формы.
2) Составить нулевую итерацию, записав математическую модель ЗЛП в первую симплекс-таблицу и взяв в качестве базисных переменных предпочтительные.
3) При наличии отрицательных коэффициентов целевой функции сj осуществить подготовку к переходу к новому решению по следующей схеме:
а) среди отрицательных коэффициентов целевой функции выбрать максимальный по модулю, соответствующий столбец в симплекс-таблице называется разрешающим и помечается знаком *.
б) среди всех отношений правых частей системы ограничений к положительным элементам разрешающего столбца выбрать минимальное, соответствующая строка называется разрешающей и помечается знаком *.
в) элемент, стоящий на пересечении разрешающего столбца и разрешающей строки, называется разрешающим и помещается в рамку .
4) Заполнить следующую симплекс-таблицу:
а) базисную переменную (б.п.) в разрешающей строке заменить на переменную разрешающего столбца, все остальные переменные оставить в неизменном порядке;
б) заполнить столбцы базисных переменных: на пересечении столбца и строки базисной переменной поставить 1, остальные элементы столбца приравнять нулю;
в) если в разрешающем столбце прежней таблицы есть 0, то соответствующую ему строку переписать без изменений;
г) если в разрешающей строке прежней таблицы есть 0, то соответствующий ему столбец переписать без изменений;
д) построить опорную строку (·) в новой таблице, разделив все элементы разрешающей строки прежней таблицы на разрешающий элемент;
е) все остальные элементы новой таблицы определяются по правилу треугольника: новый элемент равен прежнему минус произведение соответствующего по строке элемента в разрешающем столбце прежней таблицы на элемент опорной строки в столбце искомого элемента новой таблицы; исключением является элемент, стоящий на пересечении строки целевой функции и столбца свободных членов ограничений, для которого в правиле треугольника «–» следует заменить на «+».
5) Целевая функция в новой таблице проверяется на оптимальность: если при реальных переменных, то получен оптимальный план решения ЗЛП, а если среди сj есть отрицательный коэффициент, то перейти к пункту 2 алгоритма.
Задача. Для изготовления двух видов , продукции используют три вида ресурсов , , . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в технологической таблице:
Число единиц ресурсов, затрачиваемых на изготовление единицы продукции