Начальной крайней точки

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

, (з _к)

где – неизвестная переменная, и – заданные векторы, – заданная матрица размера . Будем считать, что (если , то умножим обе части -го уравнения на (-1)).

Рассмотрим вспомогательную задачу, добавляя искусственные переменные и единичную матрицу :

.

Точка является начальной крайней точкой для вспомогательной задачи . Решение задачи имеет вид: . Тогда точка является начальной крайней точкой исходной задачи (з _к).

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

;

,

,

.

Решение: Составим вспомогательную задачу:

;

,

,

.

Начальной крайней точкой вспомогательной задачи является точка . Заметим, что базисная матрица вспомогательной задачи есть единичная матрица. Поэтому . Построим симплексную таблицу:

								-1	-1	-1
базис
	-1				-1
	-1			-1
	-1
		-4	-1	-1	-1	-1	-1	-1	-1	-1
			-1	-1	-1	-1	-1

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

								-1	-1	-1
базис
					-1
	-1			-1
	-1
		-3			-2	-1	-1		-1	-1
					-2	-1	-1

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

Выводим из базиса вектор и строим таблицу для нового базиса :

								-1	-1	-1
базис
				-1
	-1					-1			-1
		-1		-2			-1			-1
				-2			-1

Минимальным отрицательным элементом в последней строке является элемент -2, соответствующий вектору . Столбец будет разрешающим. В этом столбце имеется одно положительное число, поэтому строка является разрешающей. Строим таблицу для базиса :

								-1	-1	-1
базис

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

				-2		-2
базис
	-2
				-2
							-1

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

				-2		-2
базис
				-1
						-1

Так как , то является решением задачи, .

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

Пример 4. Решить задачу линейного программирования:

; (з)

,

,

,

.

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

; (з1)

,

,

,

, .

Полученную задачу линейного программирования (з1) в канонической форме будем решать методом искусственного базиса. Для этого рассмотрим вспомогательную задачу, добавляя искусственные переменные :

; (з2)

,

,

,

, .

Начальная крайняя точка задачи (з2) . Базисные векторы

.

Составим симплексную таблицу для задачи (з2):

										-1	-1
базис
						-1
			-1	-1
	-1					-1	-1
	-1					-2
		-5		-2	-1					-1	-1
				-2	-1

Из таблицы видно, что разрешающим столбцом является столбец , а разрешающей строкой . Заменяем в базисе вектор на вектор и строим новую симплексную таблицу:

										-1	-1
базис
			-1
	-1					-2
		-2			-1						-1
					-1

Заменяем в базисе вектор на вектор и строим новую симплексную таблицу:

										-1	-1
базис
			-1
						-2

Вектор , поэтому точка является решением вспомогательной задачи (з2). Тогда точка является начальной крайней точкой задачи линейного программирования в канонической форме (з1).

Приступим к решению задачи (з1). Составим первую симплексную таблицу для начальной крайней точки . Разложения векторов возьмем из последней симплексной таблицы:

базис
			-1
	-1
						-2
				-1
			-2

Из таблицы видно, что разрешающим столбцом является столбец , а разрешающей строкой . Заменяем в базисе вектор на вектор и строим новую симплексную таблицу:

базис
	-1
						-2
				-1

Далее заменяем в базисе вектор на вектор и строим новую симплексную таблицу:

базис
	-1
				-1

Так как , то точка является решением задачи (з1). Тогда точка является решением исходной задачи (з).

Ответ: . ●