СВОЙСТВА РЕШЕНИЙ ЗЛП

Свойства решений ЗЛП сформулируем в виде теорем.

Теорема 1. Для существования оптимальных решений ЗЛП необходимо и достаточно, чтобы многогранник решений содержал хотя бы одну точку, и чтобы линейная форма F на нем была ограничена снизу при определении opt типа min и сверху при определении opt типа max.

Теорема 2. Если ЗЛП имеет оптимальный план, то он достигается в вершинах выпуклого многогранного тела, которое является ОДР (областью допустимых решений или планов). Если же оптимальный план достигается более чем в одной вершине, то он достигается в любой точке выпуклой линейной комбинации соответствующих вершин многогранника.

ОПОРНЫЕ ПЛАНЫ ЗЛП

Рассмотрим каноническую форму записи ЗЛП

Чтобы имело смысл говорить об оптимальном плане задачи (20)–(22), необходимо и достаточно, чтобы система ограничений (21) была совместна в области неотрицательных значений переменных.

Так как в системе линейных уравнений (21) m уравнений и n переменных, то ранг r системы должен быть меньше числа переменных (r<n). В таком случае среди переменных r переменных – базисные, а (n-r) переменных – свободные

Определение. Опорным планом ЗЛП называется такой план, в котором базисные переменные неотрицательны, а свободные равны нулю.

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

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ОПОРНЫХ ПЛАНОВ

Известно, что планы ЗЛП с точки зрения геометрии можно трактовать, как геометрическое место точек выпуклого многогранного тела, которое является ОДР задачи. Тогда опорные планы ЗЛП с точки зрения геометрии можно трактовать как вершины этого многогранного тела.

Теорема. Каждому опорному плану ЗЛП соответствует вершина многогранника Ω и наоборот, каждой вершине многогранника Ω соответствует опорный план. Таким образом, оптимальные планы следует искать среди опорных планов.