Линейного программирования

1) Задача не имеет оптимальных решений.

Данный случай может возникнуть: либо тогда, когда допустимое множество решений пусто ("не из чего выбирать" оптимальный план),

либо когда допустимое множество представляет собой неограниченное многогранное множество, и целевая функция на нем неограниченно возрастает (если L ® max) или неограниченно убывает (при L ®min).

2) Задача имеет единственное решение (единственный оптимальный план).

Это решение обязательно совпадает с одной из вершин допустимого множества.

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

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

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

В следующем параграфе рассмотренные общие положения будут проиллюстрированы на примере задачи линейного программирования с двумя переменными.