Свойства решений задачи линейного программирования

Пусть ЗЛП представлена в виде:

при

Выделим зависимость между m и n и количеством решений системы уравнений.

Пусть m>n. Количество уравнений больше числа переменных и нет линейно-зависимых уравнений. Система не имеет решений.

Если m=n и нет линейно зависимых, то система ограничений имеет единственное решение. Следовательно, ЗЛП имеет единственное решение именно в этой точке.

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

Запишем ЗЛП в векторном виде:

при

Пусть m<n. Все m уравнений линейно- независимы. Тогда переменные можно выразить через переменные . Назовем - базисными переменными, а – свободными.

Область допустимых значений будем называть многогранником планов (для ЗЛП от двух неизвестных – выпуклый многоугольник). Точку пересечения линий будем называть крайней точкой многогранника планов.

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

Теорема1. Если система векторов , имеет линейно-независимую подсистему , то допустимое решение (,0,0,…,0) является крайней точкой многогранника планов.

Замечание: Среди крайних точек многогранника плана и находится оптимальное (max) решение.

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