2.5. Симплекс-метод решения злп.

Пусть требуется решить задачу

(2.52)

(2.53.)

(2.54)

Так как по доказанному выше решением задачи (2.52.)-(2.54.) является опорный план (неотрицательное базисное решение системы линейных уравнений ), то метод решения задачи должен содержать четыре момента:

1. обоснование способа перехода от одного опорного плана к другому;

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

3. указание способа построения нового опорного плана, более близкого к оптимальному;

4. указание признака отсутствия конечного решения.

Определение к-матрицы кзлп

Определение 2.18. К-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной системе , содержащую единичную подматрицу на месте первых n своих столбцов и все элементы ( n+1 )-го столбца которой неотрицательны.

Теорема 2.17. Каждая К-матрица определяет опорный план КЗЛП и наоборот.

Доказательство теоремы очевидно.

Из теоремы 2.11 следует, что число К-матриц конечно и не превышает .

Пример 2.8. В примере 2.4 опорным планам:

соответствует К-матрица = ;

соответствует К-матрица = ;

соответствует К-матрица = .

Переход от одной к-матрицы злп к другой к-матрице

Пусть известна К-матрица

(2.55)

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

= ,

тогда =( 3,1,6); = =(1,2,4) и, следовательно, опорный план, определяемый , имеет вид

=(2,0,1,0,0,4).

Итак, пусть К-матрица (2.55) определяет невырожденный опорный план

(2.56)

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

Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана-Гаусса. В результате получим новую матрицу

, (2.57)

элементы которой выражаются через элементы матрицы следующим образом: (2.58)

(2.59)

, (2.60)

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

Теорема 2.18. Пусть в k-м столбце К-матрицы - есть хотя бы один строго положительный элемент ( , ). Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую К-матрицу - , выбрав направляющий элемент из условия:

(2.61)

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

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

Из соотношения следует, что

>0

тогда и только тогда, когда

>0.

Это первое условие, которое мы должны наложить на выбор направляющего элемента.

Из соотношения следует, что

тогда и только тогда, когда

(1)

Это условие выполняется для всех

Перепишем неравенство (1) для строго положительных в виде (2)

Очевидно, что неравенство (2) будет выполняться для всех >0, если выбрать таким, что

>0.