Алгоритм решения ЗЛП

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

2. Строим вектор n.

3. Проводим линию уровня Lo, которая перпендикулярна n.

4. Линию уровня перемещаем по направлению вектора n. Перемещение линии уровня производится до тех пор, пока у нее не окажется только одна общая точка с областью допусти­мых решений. Эта точка, определяющая единственное решение задачи ЛП, и будет точкой экстремума - точка максимума (выхода из ОДР) или минимума (входа в ОДР).

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

где , Х₁ и Х₂ оптимальные решения в угловых точках ОДР.

Задача ЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми.

5. Находим координаты точки экстремума и значение це­левой функции в ней.

Дата добавления: 2014-01-03