|
Для решения задач линейного программирования предложено немало различных алгоритмов. Наиболее эффективным среди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана.
Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем.
Симплексный метод - это итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения, в частности по угловым точкам многоугольника решений, полученного геометрическим методом.
В тех случаях, когда модель содержит т уравнений, для построения пробных решений используются т переменных, принимающих некоторые положительные значения при нулевых значениях остальных переменных. Вначале допустим, что решение существует, причем оптимальное значение целевой функции конечно. В этом случае вычислительная процедура может быть представлена в следующей последовательности.
1. Выберем т переменных, задающих допустимое пробное решение, и исключим эти переменные из целевой функции.
2. Проверим, нельзя ли за счет одной из переменных, приравненной вначале к нулю, улучшить значение целевой функции, придавая ей отличные от нуля (причем положительные) значения. Если это возможно, перейдем к третьему этапу, в противном случае прекратим вычисления.
3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из выражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен.
4. Разрешим систему т уравнений относительно переменной, вошедшей в новое пробное решение. Исключим эту переменную из выражения для целевой функции. Вернемся ко второму этапу.
Важно отметить, что при однозначном понимании данного предписания предложенный алгоритм действительно приводит к оптимальному решению для любой модели линейного программирования за конечное число итераций, если система ограничений задачи совместна.
Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции изменяется. Рассмотрим алгоритм симплексного метода на примере задачи планирования товарооборота.
Коммерческое предприятие реализует п товарных групп, располагая т ограниченными материально-денежными ресурсами. Известны расходы ресурсов каждого i-вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А = (аij), и прибыль ct получаемая предприятием от реализации единицы товара j группы. Надо определить объем и структуру товарооборота, при которых прибыль коммерческого предприятия была бы максимальной.
|
