2.3. Теоретические основы линейного программирования

Рассмотрим каноническую задачу линейного программирования (КЗЛП )

(2.22)

Будем в дальнейшем считать, что ранг матрицы А системы уравнений равен m , причем m<n.

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

(2.23)

(2.24)

(2.25)

где - j-й столбец матрицы А.

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

_{Согласно определению и предположению о том, что r(A)=m} , всякому опорному плану задачи линейного программирования (как и всякому базисному решению системы линейных уравнений ) соответствует базисная подматрица В порядка m матрицы А и определенный набор m базисных переменных системы линейных уравнений .

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

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

Определение 2.16. ОП ЗЛП, число строго положительных компонент которого равно m ( ),будем называть невырожденным ОП. В противном

случае ОП ЗЛП вырожденный.

Определение 2.17. Опорным планом ЗЛП будем называть такой план _,

что векторы , входящие в разложение

со строго положительными , линейно независимы.

Теорема 2.10.

Докажем что оба определения опорного плана равносильны.

Пусть вектор - опорный план в смысле определения (2.14) с базисными компонентами

Тогда матрица

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

Следовательно, если все , то вектор является опорным планом в смысле определения (2.17).

Если же среди ровно k (k<m) строго положительных компонент, то соответствующие им k векторов линейно независимы, так как они образуют подсистему линейно независимой системы векторов, т.е. и в этом случае вектор является опорным планом в смысле определения (2.17). Обратно, пусть вектор - опорный план в смысле определения (2.17), причем его компоненты

строго положительные, а соответствующие им векторы (*) линейно независимы.

Так как векторы , то .

Пусть k=m. Тогда компоненты векторов (i=1,2,…,m) образуют базисную матрицу B матрицы A , а компоненты вектора являются его базисными компонентами. Следовательно, вектор - невырожденный опорный план ЗЛП в смысле определения (2.14).

Пусть теперь k<m. Тогда среди векторов

можно найти вектор , не входящий в систему векторов (*) и такой что если его присоединить к системе (*), то полученная система из (k+1)-ого вектора

(**)

линейно независима.

В самом деле, предположим, что система векторов (**) линейно зависима. Это означает, что в матрице А есть минор k-ого порядка равный нулю, т.е. ранг матрицы А равен k и по предположению меньше m. Получили противоречие, следовательно система векторов (**) линейно независима.

Рассуждая аналогичным образом, можно доказать, что систему векторов (*) можно дополнить до системы из m линейно независимых векторов

(***)

присоединив к ней (m-k) векторов

системы , не входящих в (*).

Компоненты векторов системы (***) образуют базисную подматрицу матрицы А, а компоненты вектора являются его базисными компонентами.

Следовательно, в этом случае вектор есть неотрицательное решение системы линейных уравнений с k<m строго положительными компонентами , т.е. вырожденным опорным планом в смысле определения (2.14).

Пример 2.4.

Пусть ограничения КЗЛП имеют вид:

Найти все ее базисные решения, указать опорные планы.

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

Преобразуем методом Жордана-Гаусса, выбирая направляющие элементы в столбцах и

Так как значения и неотрицательны, тогда данная матрица определяет опорный план

Все найденные базисные решения и соответствующие базисные подматрицы сведем в таблицу 2.1.

Табл.2.1.

№ п/п	Набор базисных переменных системы	Базисные подматрицы матрицы	Расширенные матрицы	Базисные решения
1				(2;3;0;0)
2				(2,5;0;1;0)
3				(11/4;0;0;3/2)
4				(0;-4;15;0)
5				(0;-4;0;11)
6				(0;0;11;-15)

Из таблицы следует, что данная задача имеет 6 базисных решений, но только 3 опорных плана:

, ,

В параграфе 2.2. было дано определение крайней точки выпуклого множества (2.12). Теорема 2.11 устанавливает связь между понятием опорного плана ЗЛП и крайней точкой множества ее планов P.

Теорема 2.11 (о крайней точке). Опорный план ЗЛП является крайней точкой множества P и наоборот.

Доказательство.

Пусть вектор - опорный план ЗЛП, у которого компоненты строго положительные, а остальные (n-k) компонент равны нулю.

Тогда согласно определению опорного плана ЗЛП векторы линейно независимы.

Предположим, что вектор не является крайней точкой множества P, то есть существуют векторы , и такие, что

(2.26)

Векторы и - планы ЗЛП. Это означает, во-первых, что компоненты векторов и неотрицательные и вследствие (2.26) ровно k компонент вектора и ровно k компонент вектора могут быть строго положительными. Остальные (n-k) компонент каждого из векторов и равны нулю.

Во-вторых, компоненты векторов и удовлетворяют функциональным ограничениям (2.24) ЗЛП. Следовательно, имеют место слудующие равенства:

Вычитая из первого равенства второе, получим,

(2.27)

Так как векторы линейно независимы, то из (2.27) следует, что или . Последнее означает, что = .

Получили противоречие, следовательно, - крайняя точка множества P.

Обратно, пусть теперь вектор - крайняя точка множества P, строго положительными компонентами которой являются . Так как вектор - план ЗЛП, то его компоненты удовлетворяют функциональным ограничениям (2.24) задачи, то есть имеет место равенство

(2.28)

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

(2.29)

Зададим некоторое ε>0. Умножим левую и правую части равенства (2.29) сначала на ε, затем на (-ε). Каждое из полученных равенств сложим с (2.28), в результате получим

(2.30)

(2.31)

Выберем ε настолько малым, чтобы выполнялись неравенства

(2.32)

(2.33)

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

и

соответственно, а остальные n-k компонент равны нулю.

Согласно (2.30)- (2.33) векторы и являются планами ЗЛП.

Имеем , то есть лежит внутри отрезка, соединяющего две различные точки и множества P.

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

Следствие 1. Крайняя точка множества P может иметь не более m строго положительных компонент.

Следствие 2. Число крайних точек множества P конечно не превышает .

Следствие 3. Если множество P ограниченное, то оно является выпуклым многогранником.

Теорема 2.12. (о существовании оптимального плана или решения ЗЛП) Если линейная форма ограничена сверху на непустом множестве P, то ЗЛП разрешима, то есть существует такая точка , что . (теорема Вейерштрасса)

Теорема 2.13. Если множество P не пусто, то оно имеет опорный план (или крайнюю точку).

Доказательство.

Заметим, прежде всего, что если правые части b_i (i = 1,2,…,m) системы линейных уравнений равны нулю, то, так как ранг матрицы А равен m, вектор является вырожденным опорным планом задачи линейного программирования. Поэтому в дальнейшем будем предполагать, что среди b_i есть отличные от нуля.

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

(2.34)

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

(2.35)

Введём обозначение

(2.36)

Изменением знака в (2.35) можно всегда добиться, чтобы μ было положительным.

У множим левую и правую части (2.35) на и полученное равенство сложим с (2.34), будем иметь

и ли, так как

(2.37)

В силу (2.36)

(2.38)

и обязательно существует такое j, для которого в соотношении (2.38) имеет место равенство.

Положим для определённости, что .

Таким образом, мы построили план задачи линейного программирования, j-я компонента которого есть , а остальные n-k+1 компонент равны нулю.

Если при этом векторы оказались линейно зависимыми, то рассуждая аналогично, получим план задачи линейного программирования, у которого k-2 строго положительных компонент и так далее до тех пор, пока не построим такой план задачи линейного программирования с l (l≤k) строго положительными компонентами, что соответствующие этим компонентам векторы будут линейно независимыми. Так по предложению среди b_i есть отличные от нуля, то l≠0.

Согласно определению опорного плана ЗЛП построенный план является при l = m невырожденным, а при l<m вырожденным опорным планом задачи линейного программирования.

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

(2.39)

где

(2.40)

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

Доказательство.

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

Тогда , то есть вектор ,определяемый соотношениями (2.39) и (2.40) также является решением задачи линейного программирования.

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

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

(2.41)

Тогда учитывая (2.40), будем иметь

.

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

Можно доказать следующую теорему о существовании оптимального опорного плана или опорного решения задачи линейного программирования.

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

Доказательство.

Заметим, что так как по условию теоремы множество планов P не пусто, то согласно теореме 2.13 оно имеет хотя бы одну крайнюю точку.

Рассмотрим 2 случая:

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

, , (2.42)

где - крайние точки множества Р.

Исключим из системы крайних точек те, которые входят в разложение (2.42) с коэффициентом α_i=0. Пусть это будут точки

.

Тогда

, ,

т.е. выполняются условия теоремы 2.14 и, следовательно,

,

что и доказывает теорему.

2. Пусть Р – неограниченное множество, а - конечное решение задачи линейного программирования.

Тогда можно указать такое положительное число М, что

. (2.43)

Введём дополнительное функциональное ограничение

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

(2.44)

при условиях

Множество планов данной задачи обозначим . Множество – ограниченное, а так как компоненты вектора удовлетворяют условиям (2.45) – (2.47) и , то является решением задачи. Следовательно, согласно доказанному в случае 1 во множестве существуют крайние точки такие, что

причём

, (2.48)

Если бы хотя бы одна крайняя точка (i=1,2,…,N) не принадлежит гиперплоскости

, (2.49)

то она является крайней точкой множества Р и теорема доказана.

Пусть все крайние точки (i=1,2,…,N) принадлежат гиперплоскости (2.49), то есть имеют место равенства

Тогда из (2.48) имеем

что противоречит условию (2.43) выбора М>0.

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