Теорема 2.24.

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

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

Пусть

Это означает, что все искусственные компоненты оптимального опорного

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

т.е. (2.90)

и вектор принадлежит множеству P´ _M.

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

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

1. На S – й итерации симплексного метода ни одна из искусственных переменных не является базисной, т.е. Тогда матрица (2.89) является K – матрицей основной задачи линейного программирования, а план - опорным планом основной задачи, определяемым этой K -матрицей.

2. На S – й итерации симплексного метода в числе базисных оказались искусственные переменные, например,

т.е.

Тогда в силу равенства (2.90) p базисных компонент вектора равны нулю:

и, следовательно, он является вырожденным оптимальным опорным планом вспомогательной задачи линейного программирования, а матрица содержит p< m единичных столбцов и не является K – матрицей основной задачи.

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

Для этой цели рассмотрим любую r - ю строку из первых p строк матрицы (r = 1, 2, …, p).

Среди элементов этой строки есть хотя бы один элемент, отличный от нуля, так как в противном случае ранг матрицы A меньше m.

Выберем этот элемент в качестве направляющего и совершим один шаг метода Жордана – Гаусса преобразования матрицы с выбранным направляющим элементом. В результате базисная искусственная переменная будет заменена одной из основных переменных , а элементы (n+1) – го столбца матрицы не изменятся.

После p таких шагов метода Жордана – Гаусса матрица будет преобразована в K - матрицу основной задачи линейного программирования, определяющую ее исходный опорный план .

Очевидно, что этот опорный план будет вырожденным.

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

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

удовлетворяет ограничениям (2.86)-(2.88).

Но тогда вектор - план вспомогательной задачи линейного программирования и такой, что

Следовательно, < , а это противоречит предложению об оптимальности вектора .

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

Пример 2.13. Рассмотрим задачу

=0.4X₁+0.3X₂+0.1X₃+0.1X₅+0.2X₆ (1)

2X₂+2X₃+4X₄+X₅=150

X₁+X₂+2X₅=200 (2)

X₁+X₃+2X₆=300

; j=1,..., 6 (3)

Так как ограничения (2) рассматриваемой ЗЛП уже имеют вид строгих равенств, то для приведения ее к каноническому виду достаточно только изменить знак функции на противоположный и рассмотреть задачу нахождения -0.4X₁-0.3X₂-0.1X₃-0.1X₅-0.2X₆ (4) при тех же ограничениях (3.2)-(3).

Рассмотрим расширенную матрицу системы уравнений (2)

Так как расширенная матрица не содержит единичной подматрицы порядка 3, то она не является К -матрицей ЗЛП и, следовательно, к задаче (2)-(4) не может быть применен симплекс-метод.

Рассмотрим метод отыскания исходного опорного плана (К -матрицы)- метод искусcтвенного базиса.

Для задачи (2)-(4) запишем ВЗ:

-(U₁+U₂+U₃) max (5)

2X₁+2X₃+4X₄+X₅+U₁=150

X₁+X₂+2X₅+U₂=200 (6)

X₁+X₃+2X₆+U₃=300

(7)

Результаты первого этапа представлены в табл. 2.7

Таблица 2.7

											-1	-1	-1
S	i
			-1												37.5
			-1												-
			-1												-
				-650	-2	-3	-3	-4	-3	-2
				37.5		0.5	0.5		0.25		0.25			-		-
			-1													-
			-1												-
				-500	-2	-1	-1		-2	-2
				37.5		0.5	0.5		0.25		0.25				-
															-
			-1			-1			-2			-1
				-100			-1			-2
				37.5		0.5	0.5		0.25		0.25
						-0.5	0.5		-1			-0.5	0.5

На третьей итерации симплексного метода получен оптимальный план вспомогательной задачи: =(200; 0; 0; 37.5; 0; 50; 0; 0; 0),

в котором ни одна из искусственных переменных не является базисной, следовательно, вектор =(200; 0; 0; 37.5; 0; 50) является невырожденным опорным планом исходной задачи, определяемым К -матрицей.

На втором этапе решаем задачу

max(-0.4X₁-0.3X₂-0.1X₃-0.1X₅-0.2X₆)

.

Решение приведено в табл. 2.8.

Таблица 2.8.

					-0.4	-0.3	-0.1		-0.1	-0.2
S	i
				37.5		0.5	0.5		0.25
			-0.4
			-0.2			-0.5	0.5		-1		-
				-90					-0.5
				12.5	-0.125	0.375	0.5
			-0.1		0.5	0.5					-
			-0.2
				-40	0.25	0.25
			-0.1		-0.25	0.75
			-0.1		0.5
			-0.2	137.5	0.625	-0.375		-1
				-40	0.25	0.25

На первой итерации (табл. 2.8.) второго этапа получен оптимальный план исходной задачи ₁=(0; 0; 12.5; 100; 150) и =40.

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

₂=(0; 0.25; 0; 100; 137.5) и =40.

Исходная задача имеет бесчисленное множество решений, задаваемое формулой (8)

Пример 2.14. Решить ЗЛП:

max(2X₁-X₂-X₄)

X₁-2X₂+X₃=10

-2X₁-X₂-2X₄ 18 (9)

3X₁+2X₂+X₄ 36

Приведем ЗЛП (9) к каноническому виду

max(2X₁-X₂-X₄)

X₁-2X₂+X₃=10

-2X₁-X₂-2X₄- S₁ =18 (10)

3X₁+2X₂+X₄-S₂ =36

Расширенная матрица системы линейных уравнений (10)

не является К -матрицей ЗЛП (10), т.к. не содержит единичной подматрицы.

Запишем вспомогательную задачу для ЗЛП (10). Т.к. матрица содержит один единичный вектор =(1; 0; 0), то при формулировке ВЗ достаточно ввести лишь две искусственные переменные U₁; U₂ во второе и третье уравнения системы (10).

Итак, ВЗ имеет вид

-(U₁+U₂) max

X₁-2X₂+X₃=10

-2X₁-X₂-2X₄-X₅+U₁=18 (11)

3X₁+2X₂+X₄-X₆+U₂=36

; U₁, U₂ 0

Решение ВЗ приведено в табл 2.9.

Таблица 2.9

											-1	-1
S	i
					-1	-2							-
			-1		-2	-1		-2	-1				-
			-1							-1
				-54	-1	-1
										-1
			-1		-0.5			-1.5	-1	-0.5		0.5
					1.5			0.5		-0.5		0.5
				-36	0.5			1.5		0.5		0.5

На первой итерации получен оптимальный план.

=(0; 18; 46; 0; 0; 36; 0).

Т.к. вектор имеет отличную от нуля искусственную переменную U₁=36, то множество планов ЗЛП (9) пусто в силу несовместности системы уравнений (10).

2.8. Модифицированный симплекс-метод