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

Введем несколько определений.

Определение 3.1. Допустимым решением ( или планом) задачи линейного программирования называется вектор X = (х₁, х₂,..., х_n), удовлетворяющий условиям (3.2) и (3.3).

Другими словами, решение Х=(х₁, х₂,..., х_n) системы уравнений (3.2) называется допустимым, если оно содержит лишь неотрицательные компоненты, то есть, х _j ≥ 0 для любых j = 1, n. В противном случае решение называется недопустимым.

Определение 3.2. Допустимым базисным решением ( или опорным планом) системы m линейных уравнений с n переменными называется решение, в котором все n-m свободных (неосновных) переменных равны нулю.

Другими словами,план X = (х₁, х₂,..., х_n) называется опорным, если векторы A_i (i =1,m), входящие в разложение (3.5) с положительными коэффициентами х _i, являются линейно независимыми

В задачах ЛП допустимые базисные решения (опорные планы) представляют особый интерес. Совместная система уравнений (3.2) имеет бесконечное множество решений, из них базисных решений – конечное число, не превосходящее

Определение 3.3. Допустимое базисное решение (опорный план) называется невырожденным, если оно содержит m положительных компонент (то есть, все базисные решения >0), в противном случае допустимое базисное решение называется вырожденным.

Определение 3.4. Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение, обеспечивающее наименьшее (наибольшее) значение целевой функции.

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

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

Определение 3.5. Точка А, для которой выполняется условие

А = L₁·A₁ + + L₂·A₂ +... + L_n·A_n при L_i ≥ 0 (i = 1, n) и L_i = 1 называется выпуклой линейной комбинацией точек А₁, А₂,..., А_n

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

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

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

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

Выпуклым многогранником называется замкнутое ограниченное выпуклое множество трехмерного (n-мерного) пространства, имеющее конечное число угловыхточек. Угловые точки многогранника называются его вершинами, а многоугольники, ограничивающие многогранник, - гранями, отрезки, по которым они пересекаются, - ребрами.