2.3. Задания

1.Найти минимальное и максимальное значения целевой функции следующих задач линейного программирования:

2. Построить задачи линейного программирования, для которых имеет место а) НР1; б) НР2.

3. Базисные решения системы линейных

УРАВНЕНИЙ, ЖОРДАНОВЫ ПРЕОБРАЗОВАНИЯ

3.1. Базисные и опорные решения

Пусть дана система линейных уравнений:

, (3)

где матрица, столбец матрицы . Будем считать, не нарушая общности, что . Известно, что точка является вершиной многогранного множества , тогда и только тогда, когда вектор есть опорное решение системы линейных уравнений (3).

О п р е д е л е н и е 1. Базисным решением системы линейных уравнений (3) называется допустимое решение, ненулевым компонентам которого соответствуют линейно-независимые столбцы матрицы .

О п р е д е л е н и е 2. Базисное неотрицательное решение системы линейных уравнений (3) называется опорным.

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

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

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

Переменные , соответствующие столбцам , называются базисными, остальные - небазисными.

Пример 5. Найти какое-нибудь опорное решение системы линейных уравнений:

Р е ш е н и е. Перечислим все базисы, образованные столбцами матрицы ограничений:

.

Для построения базисного решения выберем один из базисов,

на­пример , и приравняем нулю небазисные переменные , . Найдем базисные переменные , решив систему уравнений:

Решение является

базисным , но не опорным. Рассмотрим базис :

- вырождено опорное решение, которому соответствует четыре базиса: .

▀

3.2. Жордановы таблицы

Если базис опорного решения (пусть для определенности ), то система уравнений (3) может быть представлена в виде

, (4)

где -вектор базисных переменных, , - вектор небазисных переменных. С помощью элементарных преобразований систему (4) можно привести к виду:

(5)

где

Такая форма записи системы называется жордановой . Запишем систему уравнений (5) в развернутом виде:

(6)

Легко заметить, что столбцы , т.е. - вектор коэффициентов разложения в базисе . Система (6) может быть представлена в форме жордановой таблицы:

						...		...
						...		...
			...		...	...	...	...	...		...
						...		...		=		(7)
			...		...	...	...	...	...		...
						...		...

Легко построить базисное решение , соответствующее базису и жордановой таблице (7), приравняв нулю небазисные переменные; тогда базисные переменные приравниваются свободным членам , т.е. . Если свободные члены все неотрицательны, то построенное базисное решение будет опорным. Переход к новому базисному решению осуществляется с помощью одного шага жордановых исключений с разрешающим элементом . Назовем r-ую строку таблицы разрешающей, а s-ый столбец - разрешающим. При этом меняются местами базисная переменная и небазисная . В результате получаем новую жорданову таблицу:

						...		...
						...		...
			...		...	...	...	...	...		...
						...		...		=		(8)
			...		...	...	...	...	...		...
						...		...

Элементы таблицы (8) получаются по следующим формулам (пра­вила жордановых преобразований):

1) ; 2) ;

3) ; 4) .

Пример 6. Построить жордановы таблицы для системы линейных уравнений примера 5, используя базисы и .

Решение. В базисе имеем:

.

Тогда жорданова форма системы и жорданова таблица имеют вид:

		0 -1	1/2 1/2	7/8 5/8	= =	1 1

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

	7/5 -8/5	-1/5 4/5	-7/5 8/5	=	-2/5 8/5

Этой таблице соответствует базисное решение .

-

Замечание. Система уравнений (3) может быть преобразована к виду:

(9)

Тогда систему (9) можно представить модифицированной жордановой таблицей вида:

					-	...	-	...	-
				=		...		...		+
			...		...	...	...	...	...		...
				=		...		...		+		(10)
			...		...	...	...	...	...		...
				=		...		...		+

Правила преобразования таблицы (10) при переходе от одного базиса к другому остаются прежними; поэтому мы не будем делать различия между эти­ми формами записи, но будем оговаривать, где подразумевается знак равенства.