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

Определение 1. Задача, в которой требуется минимизировать (или максимизи­ровать) линейную форму

при условии, что

, ,

или

, ,

и

, ,

называется задачей линейного программирования в произвольной форме записи.

Определение 2. Задача в матричной форме вида

                                               (1)

называется симметричной формой записи задачи линейного программирования.

Определение 3. Задача линейного программирования вида

                                               (2)

называется канонической формой записи задачи линейного программирования.

Любую задачу линейного программирования можно привести к кано­ни­ческой форме. Например, если система ограничений задана в виде

,

то можно, введя дополнительные переменные, привести ее к виду

,  ,  ,

где . Если же ограничения в задаче заданы в виде

,

то

,  ,  .

Определение 4. Набор чисел , удовлетворяющий огра­ни­чениям задачи линейного программирования, называется ее планом.

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

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

.                                        (3)

Очевидно, что столбцы матрицы образуют базис -мерного пространства. Поэтому вектор и любой столбец матрицы можно представить в виде линейной комбинации столбцов матрицы .

Умножим (3) на слева

,                                           (4)

и найдем отсюда :

.                                                    (5)

Придавая различные значения, будем получать различные решения .

Если положить , то

.                                                           (6)

Решение (6) называют базисным решением системы из уравнений с неизвестными.

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

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

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

Определение 6. План задачи линейного программирования будем называть опорным, если векторы условий с положительными коэффициентами линейно независимы.

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

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

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

Теорема 1 (основная теорема линейного программирования).

1. Линейная форма достигает своего минимума в угловой точке многогранника решений.

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

Доказательство: Доказательство теоремы основано на следующей лемме.

Лемма. Если - замкнутое, ограни­ченное, выпуклое множество, имеющее конечное число крайних (угловых) точек, то любая точка может быть представлена в виде выпуклой комбинации крайних точек .

1) Пусть - некоторая внутренняя точка. Многогранник ограниченный замкнутый, имеет конечное число угловых точек. – допустимое множество.

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

,  ,  .

Так как функция линейна, то

.                                                   (*)

Выберем среди точек ту, в которой линейная форма принимает наименьшее значение. Пусть это будет точка . Обозначим минимальное значение функции в угловой точке через :

.

Подставим данное значение функции в линейную форму (*) вместо и получим:

.

Так как - оптимальная точка, то получили противоречие: (!). Следовательно, ,   – угловая точка.

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

,    и   ,

то     .

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

Теорема 2. Если известно, что системы векторов условий , линейно независима и такова, что

,

где все , то точка является угловой точкой многогранника решений.

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

Следствия:

1) Угловая точка многогранника решений имеет не более положительных компонент вектора .

2) Каждой угловой точке многогранника решений соответствует линейно независимых векторов из данной системы: .