Лекция 5
Задача линейного программирования

Основные определения и теоремы

Задача, в которой требуется минимизировать (или максимизировать) линейную форму при условии, что , j = 1, ..., m, или , j = m + 1, ..., p и xi > 0, i = 1, ..., n, называется задачей линейного программирования в произвольной форме записи.

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

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

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

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

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

Рассмотрим задачу с ограничениями . Эту систему ограничений можно представить в виде системы

.

Введем следующие обозначения:

, ,…, , ,…, , .

Тогда задачу линейного программирования можно записать в виде:

,

.

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

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

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

Введем понятие базисного решения. Из матрицы расширенной задачи выберем m линейно независимых векторов-столбцов, которые обозначим как матрицу B_m´m, а через D_m´n обозначим матрицу из оставшихся столбцов. Тогда A_p = [B, D], и ограничения расширенной задачи линейного программирования можно записать в виде:

.

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

Умножим последнее равенство на B^-1 слева: , и найдем отсюда :

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как функция линейна, то . (*)

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

.

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

.

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

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

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

Теорема 2.

Если известно, что система векторов условий , (m ≤ n) линейно независима и такова, что , где все x_i > 0, то точка является угловой точкой многогранника решений.

Теорема 3.

Следствия.

1. Угловая точка многогранника решений имеет не более m положительных компонент вектора .
2. Каждой угловой точке многогранника решений соответствует m линейно независимых векторов из данной системы: .