SHPORA.net :: PDA

[ Back ]

1. Построить область допустимых решений.

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

3. Если область допустимых решений является непустым множеством, построить нормаль линий уровня n = (c1 ,c2 ) и одну из линий уровня, имеющую общие точки с этой областью.

4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум- в противоположном направлении.

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

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