Методы решения задач лп

Методы линейного программирования - численные методы решения оптимизационных задач, сводящихся к формальным моделям линейного программирования.

Существуют конечные и итеративные методы решения задач ЛП.

Итеративный метод сходится к точному решению асимптотически на бесконечном числе итераций, а при конечном дает приближенное решение.

Конечные методы позволяют получить точное решение за конечное число шагов. Они делятся на:

- универсальные, применимые для любых задач ЛП;

- специальные, предназначенные для решения определенных классов задач ЛП.

Симплекс-метод. Характеристика метода

Симплекс-метод реализует направленный перебор допустимых базисных решений в виде итеративного процесса. На каждой итерации осуществляется переход по ребру допустимого множества от одной вершины к другой, смежной исходной, в которой значение критерия лучше или, в редких случаях, не хуже, чем в исходной. Поскольку число крайних точек конечно, а целевая функция линейна, то такой процесс сходится за конечное число шагов к глобальному оптимуму (для разрешимой задачи).

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

В симплекс-методе можно выделить три основные компоненты:

1. Способ построения начального базисного решения.

2. Процедуру перехода от одного базисного решения к другому.

3. Признак оптимальности.

Неразрешимость задачи определяется по ходу работы алгоритма.

Этапы симплекс-метода:

1. Построение начального неотрицательного базисного решения.

2. Анализ оценок. При этом возможны три ситуации:

а) все оценки неотрицательны, следовательно, вычисления прекращаются, так как выполнился признак оптимальности.

б) имеются отрицательные оценки, но, по крайней мере, одной их них (например, Δ_j) соответствует вектор, для которого все коэффициенты разложения неположительны (_ij0). В этом случае  не ограничено сверху и, как следует, критерий неограниченно возрастает. Решение прекращается.

в) для каждой отрицательной оценки есть _ij>0. Решение может быть улучшено выполнением 3 этапа.

3. Переход к новому базисному решению путем введения переменной с минимальной оценкой и выводом переменной, на которой достигается минимум.

Этапы 2 и 3 повторяются до выполнения одного из условий останова.

М одифицированный алгоритм симплекс-метода

Отличается от простого симплекс-метода тем, что основан на обратной матрице базиса.

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

4. Модели управления транспортными потоками.

Задачи, называемые транспортными, составляют большой подкласс распределительных задач. С содержательной стороны они не обязательно связаны с доставкой или перевозкой грузов, а выделяются из других задач особой структурой математической модели. Поэтому правильнее говорить о моделях транспортного типа. Если удельные затраты на перевозку не зависят от количества перевозимого груза, транспортная задача описывается линейной моделью. При этом ее особенности позволяют применять специальные методы линейного программирования, которые более эффективны, чем универсальные.