Линейная_алгебра_УП_очная_ЭлРес

таблицу №5, соответствующую базису А2, А3, А4 опорного решения α’ = (0, 3, 4, 2, 0), которое также не является оптимальным, из–за наличия положительной оценки δ1=2.

Для перехода к следующему опорному решению находим min {	i	}для
a'is 0	a'is

1-го столбца, а именно, min {2/1; 4/1}=2. Следовательно, за разрешающий элемент для преобразования Жордана. берем а21=1. Получаем симплекс таблицу №6, соответствующую базису А1, А2, А3 опорного решения α’’ = (2, 3, 2, 0, 0), которое является оптимальным, так как все оценки векторов условий задачи

неположительные. ■			работы
Замечание. Решая каноническую задачу линейного программирования на
минимум, мы выполняем ряд шагов. При этом на каждом шагеМБИосуществляется
самостоятельной			ВПО
либо переход от базиса исходного п рн го решения к базису нового опорного
							.
решения, на котором значение целевой функции меньше, чем на исходном
							г
опорном решении, либо переход к очередному базису исходно о опорного
				2013
решения, если это опорное решение является вырожденным.
Так как опорных решений	у		канонической			задачи линейного
программирования конечное чис о,	ЧОУ				число шагов задача
	то	через конечное

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

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

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

приведенную к базису В1, …, Вl, …, Вk, …, Вr

порного решения α:

…

B1’

…

B ’

…

Bk’

…

Br’

…

As’

…

B’

…

1

…

0

…

0

…

0

…

a’1s

…

α1

Москва

…

…

…

…

…

…

… …

…

…

…

…

…

0

…

1

…

0

…

0

…

a’ s

…

α

…

…

…

…

…

…

… …

…

…

…

…

…

0

…

0

…

1

…

0

…

a’ks

…

αk

…

…

…

…

…

…

… …

…

…

…

…

Для

студентов

…

0 … 0

…

0

…

1

…

a’rs

…

αr

…

0

…

0

…

0

…

0

…

δs

…

δ0

81

работы
Среди положительных одинаковых оценок в симплекс таблице выбираем
оценку δs с наименьшим номером. Затем среди отношений вида {	i	} для всех
	a'is

a’is > 0 выбираем наименьшее. Если указанное о ношение не является единственным, то выбираем то, которое имеет наименьший номер i . Применяя это правило на каждом шаге симплекс метода, удем получать базис системы условий задачи, который не встречался ранее. Поэтому через конечное число шагов задача будет решена.

Теорема. (о разрешимости задачи линейного программирования на

минимум)	самостоятельной
Если	каноническая задача линейного программирования на минимум
		ВПО				допустимых
имеет допустимое решение, а целевая функция на множествеМБИ
решений ограничена снизу, то эта задача имеет оптимальное решение.
					.
▲ В теореме о существова ии опор ого решения было доказано, что если
					г
каноническая задача линейного программирования имеет допустимое решение,
			2013
то эта задача имеет и опорное решение. Принимаем это				опорное решение за

начальное опорное решение и решаем задачу симплекс методом. Так как целевая функция ограничена снизу наЧОУмножестве допустимых решений, то

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

Ответьте на вопросы
1.	Если все оценки			вект ров условий в симплекс таблице оказались
			студентов					действия	при	решении
	неположительными,				о	каковы последующие
	канонической задачи линейного программиро ания на минимум симплекс
	методом?
2.	В симплекс таблице				среди		ценок векторов	условий	КЗЛП	имеется
	положительная. Каковы последующие действия при решении канонической
	задачи линейного программирования на минимум симплекс методом?
3.	Каков критерий выбора разрешающего элемента для перехода к новому
	опорному решению?
4.	Какой критерий используется на Москвакаждом шаге симплекс метода для
	ускорения процесса нахождения оптимального решения?
5.	Каков результат перехода от						одной симплекс	таблицы	к другой, если
	э емент столбца В, стоящий в одной строке с разрешающим элементом,
	равен нулю?
6.	Каков результат перехода от одной симплекс таблицы к другой, если
	элементДля	столбца В,		стоящий в одной строке с разрешающим элементом,

82

больше нуля?

работы

7.

Запишите выражение для любого оптимального решения, если при решении

КЗЛП два опорных решения оказались оптимальн

ми?

8.

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

минимум.

x1

+

4x2

+

х3

= 5,

МБИ

Решите самостоятельно

Задачи 1. Найти

оптимальное

решение

к нонической

задачи линейного

программирования при заданном опорном ешении.

1.1

самостоятельной

f(X)

=

x1

+

2x2

–

x3

(min),

x1

–

2x2

+

x3

= –1,

ВПО

.

xj ≥ 0, j = 1, 2, 3,

α = (1, 1, 0)

г

1.2

2013

f(X)

=

x1

+

x2

+

x3

(max),

–x1

+

x2

+

х3

= 2,

ЧОУ

3x1

–

2x2

+

x3

= 0,

xj ≥ 0,

j = 1, 2, 3,

α = (0, 1, 1)

1.3.

f(X)

=

2x1

+

x2

+

3x3

+

x4

2x5

(max)

x1

+

x2

+ xМосква3 + x4

+

= 4,

x1

– 2x2

+

5x3

– x4

= 4,

Для

x1

– x2

–

x3

+ 2x4 = 1,

студентов

xj ≥ 0, j = 1, 2, 3, 4,

α = (0, 0, 1, 1)

1.4.

f(X)

=

6x1

+

x2

+

4x3

–

5x4

(max)

3x1

+ x2

–

5x3 + x4 = 4,

5x1

+ x2

+

x3

– x4 = 4,

xj

≥ 0,

j = 1, 2, 3, 4,

α = (1, 0, 0, 1)

1.5.

f(X)

=

x1

+

x2

+

x3

–

x4 +

3x5

(min)

2x1 + x2

+ x3

+

2x4

= 5,

x3

–

x4

+

3x5 = 2,

xj

≥ 0,

j = 1, 2, 3, 4, 5,

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

83

1.6.

работы

МБИ

f(X)

=

x1

+ x2

+ 13x4

–

x5 +

3x6

(min)

f(X)

=

5x1

+ 10x2 + 3x3

(max)

3x1

+ 2x2

– x3

+

x4

–

2x5 = 23,

–x1 + 3x2

– 2x3

+ x4

= 9,

x1

+ 2x2

+ x3

+

x5 = 29,

xj ≥ 0, j = 1, 2, 3, 4, 5,

самостоятельной

ВПО

α = (0, 0, 24, 57, 5).

1.7.

– x2

x1

– x3

–

9x4

–

4x5+5x6

= –5,

+ 2x2

.

x1

– x3

+

3x4

–

x5

+2x6

= 4,

г

x3

+

8x4

+

2x5

–2x6

= 6,

xj

≥ 0,

j = 1, 2, 3, 4, 5,6,

2013

ЧОУ

α = (4, 3, 6, 0, 0, 0).

Задача 2. Решить задачи симплекс методом

f(X)

=

x1

+

4x2

+ x3

+

x4

–

2x5+x6

(min)

x1

–

x2

–

x4

= –0,

x1

+ x2

+ x3

+ x5

= 1,

Москва

x2

+ x3

+

x6

= 1,

Для

xj

≥ 0,

j = 1, 2, 3, 4, 5,6.

студентов

– 4x3

– 2x6

(min)

f(X)

=

x1

–x1

– x2

– 2x6

= –1,

–x1

+ 2x3

+ х5

+ 3х6

= 0,

x1

– x3

+ x4

– x6

= 1,

xj

≥ 0,

j = 1, 2, 3, 4, 5,6.

84

2. 9. Метод искусственного базиса для нахождения начального опорного решения

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

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

нахождения начального опорного решения использовать более эффективный
метод – метод искусственного базиса.			работы			МБИ
Рассмотрим каноническую задачу линейного программирования
	n							.
(1)	f(X) = γj xj + γ0			(min),
	j 1
	n
(2)	Аj xj =B,
							г
	j 1
(3)	xj ≥ 0, j = 1, 2, …, n.
Построим для задачи (1) – (3) искусственнуюВПО						каноническую				задачу
линейного программирования вида:
(4)	φ(X) = xn+1 + xn+2 + … +xn+m					(min),
	n
(5)	Аj xj	+E1 xn+1	+ E xn+2 + … + Em xn+m						=B,
(6)	j 1				2013
	xj ≥ 0, j=1,2,…,n, n+1, n+2, … , n+m,
		ЧОУ
		Москва
самостоятельной
опорного решениястудентоввектор β = (0, …, 0, b1, b2, …, bm) является опорным
где Ej – единичный век ор (j = 1, 2, …, m)				, а xn+1		, xn+2		, …	,	xn+m	–
искусственные переменные.

Основные св йства ис усственной задачи

10. Вектор β = (0, …, 0, b1, b2, …, bm) являет я опорным решением задачи (4)–

(6).

▲ Заметим, что по определению канонической задачи линейного программиров ния все координаты вектора ограничений В = (b1, b2, …, bm) должны быть неотрицат льными, т.е. bi ≥ 0, i = 1, 2, …, m.

Для
Так как единичные векторы E1, E2	, … , Em	образуют базис системы

векторов условий А1, А2, …, Аn, E1, E2 , … , Em задачи (4) – (6), то вектор ограничений В можно представить в виде линейной комбинации векторов E1, E2 , … , Em с нео рицательными коэффициентами bi ≥ 0, i = 1, 2, …, m, т.е. в виде В = b1 E1+ b2 E2 + … + bm Em . Следовательно, по свойству базиса

решением задачи (4) – (6). ■

85

20. Задачи (4) – (6) всегда имеет оптимальное решение.

▲ Задачи (4) – (6) имеет допустимые решение, одним из которых является, например, вектор β = (0, …, 0, b1, b2, …, bm), так как опорное решение всегда является допустимым. Из (6) следует, ч о все искусственные переменные неотрицательны, т.е. хn+i ≥ 0, i = 1, 2, …, m. Поэтому целевая

функция (4) φ(X) = xn+1 + xn+2 + … +xn+m ограничена снизу на множестве допустимых решений, т.е. φ(X) ≥ 0. Следовательно, по теореме о разрешимости

канонической задачи линейного программиров ния, задачи (4) – (6) имеет оптимальное решение.■

Замечание. Так как у задачи (4) – (6) всегда известно начальное опорное
			работы
решение, то ее можно решить симплекс методом, который через конечное
число шагов приведет к оптимальному решению этой задачиМБИ.
Теорема (о методе искусственн го базиса)
Пусть вектор β = (α1, α2, …, αn, αn+1, αn+2, …, αn+m) является
оптимальным решением искусстве ой задачи (4) –(6). Тогда:					.
1) если αn+1 = αn+2
		= …= αn+m =0 , то вектор α = (α1, α2, …, αn) является
	самостоятельной		ВПО	2013	г
опорным решением исходной канонической задачи линейного программирования
(1) – (3);		ЧОУ

2) если среди чисел αn+1, αn+2, …, αn+m , хотя бы одно отличается от

нуля, т.е. найдется αn+1>0 , i = 1, 2, …, m , то задача (1) – (3) не имеет ни одного допустимого решения, т.е. система ограничений канонической задачи

линейного программирования (1) – (3) является несовместной.

▲ Докажем перв е утверждение. По условию вектор β = (α1, α2, …, αn,
	студентов
αn+1, αn+2, …, αn+m)	являе ся оптимальным решением искусственной задачи (4) –
(6). Тогда вектор	β является опорным решением этой задачи, а, следовательно,
и допустимым решением и, по пределению,		является решением системы
линейных уравнений (5), т. е. вып лняет я оотношение:
А1 α 1 +А2 α 2 +…+Аn α n +E1 α n+1 + E2 α n+2 + … + Em α n+m =B,
Так как αn+1 = αn+2 = …= αn+m =0 , то п следнее равенство можно записать
в виде А1 α 1 +А2 α 2 +…+Аn α n =B.
Откуда, по опр д л нию, следует, что вектор α = (α1, α2, …, αn) является
допустимым решением исходной задачи Москва(1) – (3).
Так как вектор β = (α1, α2, …, αn, 0, 0, …, 0)		является опорным решением

искусственной задачи, то ненулевым координатам этого вектора соответствуют инейно независимые векторы условий этой задачи. Тогда некоторые из указанных линейно независимых векторов соответствуют ненулевым

координатам вектора α = (α1, α2, …, αn). Следовательно, вектор α является
опорнымДля	решением исходной задачи (1) – (3).

86

Второе утверждение теоремы будем доказывать от противного, предположив, что существует число αn+i>0 , i = 1, 2, …, m, но при этом исходная задача (1) – (3) имеет допустимое решение α = (k1, k2, …, kn), которое удовлетворяет системе (2) и kj ≥0, j =1, 2, …, n . Тогда по определению допустимого решения выполняется соотношение: А1 k 1 +А2 k 2 +…+Аn k n = B,

которое можно переписать в виде
А1 k 1 +А2 k 2 +…+Аn k n +An+1 0 + An+2 0 + … + An+m				0	= B.
Откуда следует, что вектор β’ = (k1, k2, …, kn, 0,				0,	…, 0) является
допустимым решением искусственной задачи (4) – (6).
Так как по условию вектор β = (α1, α2, …, αn, αn+1, αn+2, …, αn+m) является
		работы
оптимальным решением искусственной задачи, то φ(β) ≤ φ(β’), что равносильно
неравенству: αn+1 + αn+2 + …+ αn+m ≤ 0 + 0 + … + 0. Однако,МБИпо предположению,
самостоятельной		ВПО		+ αn+2 + …+ αn+m> 0.
существует αn+1>0 , i = 1, 2, …, m, а, след вательно, αn+1
Получено противоречие. Таким	образом, предположение					.
					о существовании
допустимого решения исходной					г
	задачи является неверным. Следовательно,
			2013
система ограничений исходной задачи является несовместной. ■
Замечание. Если среди векторов условий исходной задачи встречается k
	ЧОУ

единичных векторов, причем k ≤ m, то при составлении искусственной задачи можно ограничиться (m – k) искусственными переменными. Например, исходная задача имеет вид:

n

γj

xj + γ0 (min),

(1) f(X) =

j 1

Москва

(2) E1 x1

+ E2

x2

+ … + Ek

xk

+ Аk+1 xk+1 + … + Аn xn

=B,

студентов3x1

+

2x3

–

x4

=7,

(3) xj ≥ 0, j=1,2,…,n;

k ≤ m.

Тогда иску

твенную задачу можно записать

следующем виде:

(4)

φ(X) = xn+1 + xn+2 + … +xn+m–k (min),

(5)

E1 x1 + … + Ek

xk

+ Аk+1 xk+1 + … + Аn xn

+E1 xn+1 + + … + E n+m–k

xn+m–k =B,

(6)

xj ≥ 0, j=1,2,…,n, n+1, n+2, … , n+m–k.

При ер. Решить задачу

f(x)=

2x1

–

x2

+

x3

–

x4

(max)

–2x1

+

x2

–

x3

+

x4

= –2,

Для

2x1

+

x3

+

x4

=12,

3x1

xj ≥ 0, j = 1, 2, 3, 4.

=7,

+

2x3

–

x4

xj ≥0, j = 1, 2, 3, 4.

▲ Приведем данн ю задачу к задаче на минимум в канонической форме:

f(x)=

–2x1

+

x2

–

x3

+

x4

(min)

2x1

+

x2

+

x3

–

x4

=2,

2x1

+

x3

+

x4

=12,

87

					работы
Так как А2 = Е2, то искусственная задача примет вид:
φ(x)= x5	+	x6	(min)	x3	–	x4	+ x5	=2,
2x1	+	x2	+
2x1			+	x3	+	x4	МБИ	=12,
3x1			+	2x3	–	x4	+x6	=7,
		xj ≥0, j = 1, 2, 3, 4, 5, 6

Решим искусственную задачу симплекс методом c начальным опорным решением β1=(0, 12, 0, 0, 2, 7). Из таблицы 1 видно, что вектор β1 не является оптимальным, так как в строке оценок существуют положительные числа δ1=5

самостоятельной							и	δ3=3. Поэтому разрешающий
Таблица 1 А1	А2	А3	А4	А5	А6	В	элемент		а13=1 выбираем в 1-м
2	0	1	–1	1	0	2	или	2-м	столбце, используя
2	1	1	1	0	0	12

																													критерий:			.
					3			0			2						–1			0				1		7						г
	–γ				0			0			0				0						–1				–1	0
	δ				5					0			3				–2				0				0		9		max{5*min{2/2,12/2,7/3};
																														3* min{2/1, 12/1, 7/2}}=6.
					–1			0			0				1						–1				–1	0
																													оценки δ4=1.2013
Таблица 2					2					0			1				–1				1				0		2			После		преобразования
					0					1			0				2				–1				0		10		Жордана		получаем		симплекс
					–1					0			0				1				–2				0		3		таблицуВПО2, из которой следует, что
	δ				–1					0			0				1				–3				0		3		опорное решение β2=(0, 10, 2, 0, 0,
Таблица 3					1					0			1				0				–1				1		5		3) также не является оптимальным
					2					1			0				0				3				–2		4		из-за наличия положительной
																											Москва
	δ				0					0			0				0				–1				–1		0			Проводим		преобразование
решение
		α2=(2,0,3,5)студентовявляется оптимальным решением исходной задачи,																																так
Таблица 4			A1					A2			A3				A4					B					ЖорданаЧОУ				с разрешающим элементом а34=1 и
			1					0			1				0					5					получаем				симплексную			таблицу 3,		из
			2					1			0				0					4					к торой				следует,		что опорное		решение
			–1					0			0				1					3					Β3=(0, 4, 5, 3, 0, 0) является оптимальным
	–γ		2					–1			1				–1					0
	δ		2					0			0				0					2					решением искусственной задачи.
																											По		доказанной			теореме	вектор
Таблица 5			0			–1/2					1				0					3
																									α1=(0,4,5,3) является опорным решением
			1					1/2			0				0					2
			0					1			0				1					5					исходной				задачи,		но	не	является
Для	δ		0					–1			0				0					–2					оптимальным ее решением, так как среди
оценок векторов								словий исходной задачи в симплекс таблице 4, приведенной к
базису опорного решения α1, есть положительная δ1=2.
	Выбираем за разрешающий элемент а21=2 и проводим преобразование

Жордана. Получаем симплекс таблицу 5, из которой следует, что опорное как все вектора условий имеют неположительные оценки, при чем f( α2)=2.■

88

Ответьте на вопросы

1.

Записать искусственную задачу для данной канонической задачи линейного

программирования.

2.

Выписать начальное опорное решение искусственной канонической задачи

линейного программирования.

3. Когда

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

имеет оптимальное решение?

4.

Сформулируйте теорему о методе искусственного базиса.

5. При

каком решении искусственной канонической задачи линейного

программирования исходная задача

имеет опо ное решение?

6.

При

самостоятельной

задачи

линейного

каком

решении

искусственной каноническойработы

ВПО

МБИ

программирования исходная задача не имеет решений?

7.

При каких условиях число искусственных переменных может быть меньше,

чем

число

уравнений

в

исход ой

канонической

.

линейного

задаче

программирования?

2013

г

Решите самостоятельно

ЧОУ

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

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

1.1.

Москва

Задача 2. Решить за ачи:

f(X)

=

x1

–

x2

+

x3

(min),

Для

x1

–

x2

+

х3

= 3,

студентов

x1

–

4x2

–

2x3

= –3,

xj ≥ 0,

j = 1, 2, 3,.

1.2.

f(X)

=

x1

+

2x2

–

x3

+

3x4

(min),

x1

+ 2x2 – x3

+ x4

= 1

–x1

+ 2x2 + 3x3 – x4

= 2,

x1

+ 5x2 + x3

– x4

= 5,

xj

≥ 0,

j = 1, 2, 3, 4.

2.1.

f(X)

=

x1

–

5x2

–

х3

+

х4

(max).

x1

+ 3x2 + 3x3 +

x4

= 3,

2x1

+

3x3

–

x4

= 4,

xj

≥ 0,

j = 1, 2, 3, 4.

89

2.2.

2.3.

2.4.

2.5.

2.6.

Для

работы

f(X)

=

2x1

+

8x2

+

х3

–

2х4

(min).

x1

x2

+

2x3

+

x4

= 6,

МБИ

+

x3

= 5,

x2

–

x3

+

x4

= 5,

6x2

+

x3

= 9,

xj ≥ 0,

j = 1, 2, 3, 4.

f(X)

=

–x1

+

x2

+

3x3

–

x4

(min),

x1

+ 3x2

+ 2x3 + x4

= 6,

самостоятельной

2x1

–

2x3

+

x4

= 3,

ВПО

.

xj ≥ 0,

j = 1, 2, 3, 4.

f(X)

=

x1

+

4x2

+

x3

+

x4

2013

г

+ x5 (min),

x1

+ 4x2

+ 2x3

+ 2x4 + x5 = 1,

ЧОУ

x1

– 2x2 + 2x3

– 2x4

– x5 = – 6,

x1

+ 2x2

+ 2x4

– x5 = 2,

xj ≥ 0, j = 1, 2, 3, 4,5.

xj ≥ 0,Москваj = 1, 2, 3, 4,5.

f(X)

=

4x1

+

x2

+

x3

+

x4

(max),

x1

+

x2

+

3x4

+ 4x5

= 13,

студентов

x1

– x2

+ x4

+ 2 x5 = 5,

3x1

+

x3

+

x4

+ x5

= 15,

xj ≥ 0, j = 1, 2, 3, 4,5.

f(X)

=

x1

+

x2

+

10x3 +

x4

+ 13x5 (min),

x1

+

x2

+

3x3

–

x4

+ 3x5

= 21,

x2

+

x3

+ 2x5 = 8,

x3

+

x4

+ x5 = 6,

90