Основные теоремы линейного программирования

Определение: Множество точек называется выпуклым, если вместе с его любыми двумя точками ему принадлежит и весь отрезок, соединяющий их.

На рис. 33.1 изображено выпуклое множество (выпуклый многоугольник), а на рис. 33.2 - невыпуклое.

рис. 33.1	рис. 33.2

Утверждение: Пересечение конечного числа выпуклых множеств также выпуклое множество.

Определение: Точка выпуклого множества называется угловой (или крайней), если через неё нельзя провести ни одного отрезка, состоящего только из точек данного множества и для которого она была бы внутренней.

Для выпуклого многоугольника угловыми точками являются все его вершины. В пространстве выпуклое множество с конечным числом угловых точек называется выпуклым многогранником.

Утверждение: множеством решений системы m линейных неравенств с n переменными является выпуклый многогранник в n -мерном пространстве (исключая случай, когда система несовместна).

Любая задача линейного программирования может быть приведена к канонической модели минимизации линейной целевой функции с линейными ограничениями типа равенств. Поскольку число переменных в задаче линейного программирования больше числа ограничений (n > m), то можно получить решение, приравняв нулю (n - m) переменных, называемых свободными. Оставшиеся m переменных, называемых базисными, можно легко определить из системы ограничений-равенств обычными методами линейной алгебры. Если решение существует, то оно называется базисным. Если базисное решение допустимо, то оно называется базисным допустимым ( опорным планом ). Геометрически, базисные допустимые решения соответствуют вершинам (угловым точкам) выпуклого многогранника, который ограничивает множество допустимых решений. Если задача линейного программирования имеет оптимальные решения, то по крайней мере одно из них является базисным.

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

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

Теорема 33.1: Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

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

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

Из теоремы 33.2 следует, что поиски оптимального решения можно ограничить перебором конечного числа угловых точек (их число меньше , где n - число неизвестных, а m – число ограничений), однако построение возможно только для двух и трёхмерных пространств, поэтому нужны аналитические методы, позволяющие находить координаты угловых точек.

Теорема 33.3: Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений, и наоборот.

Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

В общем виде, когда в задаче участвуют N -неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n -мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более трех весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.