20.2. Алгоритм решения задач
1. Находим область допустимых решений системы ограничений задачи.
2. Строим вектор .
3. Проводим линию уровня L0, которая перпендикулярна .
4. Линию уровня перемещаем по направлению вектора для задач на максимум и в направлении, противоположном , Для задач на минимум.
Перемещение линии уровня производится до тех пор, пока у нее не окажется только одна общая точка с областью допустимых решений. Эта точка, определяющая единственное решение задачи ЛП, и будет точкой экстремума.
Если окажется, что линия уровня параллельна одной из сторон ОДР, то в таком случае экстремум достигается во всех точках соответствующей стороны, а задача ЛП будет иметь бесчисленное множество решений. Говорят, что такая задача ЛП имеет Альтернативный оптимум, и ее решение находится по формуле
Где 0 ≤ T ≤ 1, 1 и 2 — оптимальные решения в угловых точках ОДР.
Задача ЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми.
5. Находим координаты точки экстремума и значение целевой функции в ней.
< Предыдущая | Следующая > |
---|