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

(2)	Аj xj =B,	работы
2.7.	Симплекс таблицы и их свойства

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

n

(1) f(X) = γj xj + γ0,

j 1

n

j1

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

(4)

a21

a22

…

a2j

…

a2n

МБИb2

Задачу (1) – (3) можно записать в виде таблицы (4), а именно,

со второй строкой

A1

A2

…

Aj

…

An

B

так далее

самостоятельнойсистемы векторов условий,

умноженной на

γi2, и

a11

a12

…

a1j

…

a1n

b1

ВПО

…

…

…

…

…

…

…

am1

am2

…

amj

…

amn

bm

–γ1

–γ2

… –γj

…

–γn

γ0

Пусть вектор

α

есть некоторое опорное

2013

задачи.

(1) – (3).

решение

Выберем один из базисов этого опорного решения, например, Агi1. Аi2, … , Аir .

Тогда это опорное решение будет иметь следующие структуру

ЧОУ

α = ( 0, 0, …, 0, αi1, 0, 0, …, 0, αi2, 0, 0, … , 0, αir, 0, 0, .., 0)

Преобразовав систему векторов условий рассматриваемой задачи

методом Гаусса к базису

Аi1. Аi2, … , Аir

выбранного опорного решения α ,

получим таблицу (5):

Москва

A1’

…

Ai1’

…

Ai2’

…

Air

…

An’

B’

условий

задачи

(1)студентов– (3), приведенных

к базису

Аi1. А

i2, …

, Аir

опорного

γi1

‘a11

… 1

…

0

…

0

…

‘a1n

α1’

(5)

γi2

‘a21

… 0

…

1

…

0

…

‘a2n

α2’

…

…

…

…

…

…

…

…

…

…

…

γir

‘ar1

… 0

…

0

…

1

…

‘arn

αr’

–γ1

… –γi1

…

–γi2

…

γir

…

–γn

γ0

δ1

… δir

…

δi2

…

δir

…

δn

δ0

Последняя строка таблицы (5)

получена в результате последовательного

сложения

противополож нных

значений

коэффициентов

целевой

функции

сначала

первой строкой системы векторов условий, умноженной на

γi1, затем

Для

включая последнюю строку векторов условий, умноженную на γir.

Таблицу

(5)

будем

называть симплекс таблицей

системы

векторов

условий задачи (1) – (3), приведенных к базису опорного решения, в данном случае к бази у Аi1. Аi2, … , Аir , а числа δ1, δ2, …, δn – оценками векторов

решения α.

71

Свойства симплекс таблицы

10. Если симплекс таблица приведенна к базису Аi1. Аi2, … , Аir опорного решения α, то в столбце В’ находятся координаты опорного решения α,

соответствующие векторам базиса Аi1. Аi2, … , Аir , о ес ь α1’ = αi1, α2’ = αi2, …, αr’ = αir,

▲ Так как вектор α = ( 0, 0, …, 0, αi1, 0, 0, …, 0, αi2, 0, 0, …, 0, αir, 0, 0, .., 0)

является опорным решением задачи (1) – (3), то он является и допустимым решением этой задачи, а следовательно, является решением системы линейных

уравнений (2), то есть выполняется соотношение:

(6)

Аi1 αi1+ Ai2 αi2+…+ Air αir = B.

’

работы

’

, 0, 0, …, 0, α2

’

,

Решением системы (5) является вектор α

= ( 0, 0, …, 0, α1

0, 0, … , 0, αr’, 0, 0, .., 0). Системы (5) и (4) равносильны, такМБИкак получены одна

из другой методом Гаусса. Поэтому вект р α’

является решением системы (4),

и, следовательно, выполняться соот оше ие:

.

(7)

Аi1 α1’+ Ai2 α2’+…+ Air αr’ = B.

Вычитая из соотношения (6) соотношение (7), получаем соотношение:

(8)

’

)+ Ai2

’

г’

) = Ө.

Аi1 (αi1 – α1

(αi2 – α2

)+…+ Air (αir – αr

Так как векторы

Аi1. Аi2, … , Аir

являются базисом системы векторов

ЧОУ

ВПО

2013

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

условий задачи (1) – (3), то они линейно независимы. Следовательно,

соотношение (8) возможно, при		αi1 – α1’ = 0, αi2	– α2’ = , …, αir – α1’ = 0.
Откуда αi1 =α1’, αi2 = α2’, …, αir = α1’ ■
= αi2, …, α1’ = αir (см. 10 ) следует: δ0 = γ0 +Москваγi1 αi1+ γi2			αi2+…+ γir αir = f(α). ■
20. Оценки базисных вект р в опорного решения всегда равны нулю, то есть,
студентов		xj ≥ 0, j = 1, 2, 3.
если векторы Аi1. Аi2, … , Аir	являются базисом некоторого опорного решения
задачи (1) – (3), то δi1 = δi2	=…,= δir.

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

30. Если си плекс таблица приведена к базису порного решения α, то δ0 = f(α).

▲ Из построения строки оценок для системы векторов условий задачи

(1) – (3), приведенной к базису Аi1. Аi2, … , Аir , и с учетом того, что α1’ = αi1, α2’

Для					является опорным решением КЗЛП на
Пример. П сть вектор α =(1, 0, 1)
минимум вида:		+	4x2	–	x3	(min),
f(X) = 3x1
	2x1	–	x2	+	х3	=3,
	x1	+	x2	+	x3	=2,

72

Покажем, что δ0 = f(α).

работы

▲ Приведем систему векторов условий данной задачи к базису А1, А3

опорного решения α =(1, 0, 1)

A1

A2

A3

B

A1

A2

A3

B

A1

A2

A3

B

*(–1)

2

–1

1

3

2

–1

1

3

0

3

1

1

МБИ

*(3)

δ

1

1

1

2

–1

2

0

–1

1

–2

0

1

–γ

–3

–4

1

0

*(1)

δ

0

–13

0

2

В

полученной симплекс таблице имеем строку оценок õ=(0, –13, 0)

самостоятельнойδn = –γn

a'1n

γ1

+

…

a'rn γr .

системы векторов условий, приведенных к базису А1,

А3

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

α

ВПО

=(1, 0, 1), а

δ0 = 2 соответствует значению целевой функции на этом опорном

решении f(α) = 3 *1 + 4* 0 – 1* 1 = 2, след вательно, δ0 = f(α). ■

Лемма (о целевой функции). Пусть

δ1, …, δj, …, δn оценки векторов

условий задачи (1) –

(3), приведе

г

α. Если

ых к базису опорного решения

1,r+1

20131n

1

вектор

β=( 1, …, j, …, n ) является допустимым решением.данной задачи,

n

то f(β)=f(α) – δj j.

ЧОУ

j 1

▲ Пусть векторы А1, А2, …, Аr

являются базисом опорного решения

α=(α1, α2, …, αr, 0, 0, …, 0). Тогда симплекс таблица системы векторов условий

задачи (1) – (3), приведенных к данному базису будет иметь вид:

A’1

A’2

…

A’r

A’r+1

…

A’n

B’

(10)

…

…

Москва…

…

'

…

1

0

…

0

a

/

a

α

0

1

…

0

a'2,r+1

a'2n

α2

есть должно выполнятсястудентовравенство:

…

…

…

…

…

(9)

…

…

…

0

0

…

1

'

'

αr

a r,r+1

a rn

–γ1

–γ2

–γr

–γr+1

–γn

γ0

δ1

δ2

δr

δr+1

δn

δ0

где по правилу п стр ения стр ки (δ1, …, δj, …, δn), оценки примут следующие

значения: δ1= δ2= …= δr=0 и

δr+1=

–γr+1

a'1,r+1 γ1

+

…

a'r,r+1 γr

,

+

a'1,r+2 γ1

a'r,r+2 γr

δr+2=

–γr+2

+

…

Для

+

,

+

По

условию

вектор β=( 1,

…,

j,

…,

l n

)

является

допустимым

решением задачи (1) – (3), следовательно, он

является решением СЛУ (2) , то

’

1

’

2

’

r

’

’

’

А1

+ А 2

+ … + Аr

+ Аr+1 r+1 + … + Аn n

= В.

73

						работы
С учетом этого соотношения и таблицы (9) получаем:
	1 +	a'1,r+1 r+1	+	…	+ a’1n	n	=	α1,
	2 +	a'2,r+1 r+1	+	…	+ a’2n	n	=	α2,
(11)	…	…		…	…		n	…	МБИ
n ) +…+ γr ( r +…+ a’r,r+1 r+1 + a’r,r+2				r+2	+…+ a’rn			) =
	r +	a'r,r+1 r+1	+	…	+ a’rn	n	=	αr.
Значение целевой функции на векторе β=( 1,								…,	j, …, n )с учетом
соотношений (10) и (11) будет равно:
f(β) = γ1 1 + γ2 2 + … + γr r + γr+1				r+1	+ γr+2	r+2 +…+ γn				n + γ0 =
= γ1 1 + γ2 2 + … + γr		r + ( –δr+1 + a1,r+1 γ1 +…+ a’r,r+1 γr)								r+1 + ( –δr+21 + a1,r+2
γ1 + … + a’r,r+2	γr) r+2 +…+ ( –δn + a1,n γ1 +…+ a’n γr) n + γ0 =
самостоятельной					1 + …+ a’1,r+1				+ a’1,r+2 r+2 +…+ a’1n
= γ0 – δr+1 r+1	– δr+2 r+2	–…– δn n + γ1 (						r+1
						ВПО				.
= γ0 + γ1α1 + … + γr αr – δr+1 r+1 – δr+2				r+2	–…– δn		n.			г
Так как	для базисных векторов А1, А2, …, Аr оценки равны нулю, т.е.δ1=

δ2= …= =δr=0, то значение целевой функции на векторе β можно записать в
виде				2013
f(β) = γ0 + γ1α1 + … + γr αr – δ1 1 – δ2	2	…– δr r		– δr+1 r+1 – δr+2	r+2 –…–
n
δn n == f(α) – δj j. ■
j 1
Теорема (достаточное условие оптимальности опорного решения)
Если для опорного решения		α0	канонической задачи		линейного
	Москва
программирования на минимум (1) – (3) найдется базис, для которого все
оценки неположительные, то есть δj≤0		для всех		j = 1, 2, …, n, то вектор α0
студентов
является оптимальным решением даннойЧОУзадачи.
▲ Пусть δ1, δ2, …, δn – оценки системы			екторов условий, приведенных к
некоторому базису порного решения α0. Если ве тор β=( 1, …,					j, …, n )

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

								n
программирования (1) – (3), то по доказанн й лемме имеем: f(β)=f(α) – δj j.
								j 1
	Т к к к, для любых j=1, 2, …, n					по условию δj≤0 , а вектор β=( 1, …, j,
…, n )		произвольное допустимое решение данной задачи, т.е. j≥0 для всех
Для		0						0
j=1, 2, …, n , то f(β)≥f(α ). Следовательно, по определению вектор α является
оптимальным решением задачи (1) – (3) на минимум. ■
	Пример. Пус ь вектор α =(1, 0, 0, 0)						является опорным решением КЗЛП
на минимум вида:
		f(X) = -10x1	+	4x2	–	9x3	+6х4	(min),
		x1	+	x2	+	3х3	+2х4,	=1,
		x1	–	x2	–	x3		=1,
					xj ≥ 0, j = 1, 2, 3, 4

74

Выясним, является ли вектор α оптимальным решением данной задачи. ▲ Приведем систему векторов условий задачи и строку с

противоположенными значениями коэффициентов целевой функции к симплекс таблице, соответствующей базису А1, А2 данного опорного решения.

А1

А2

А3

А4

В

А

А2

А3

А4

В

А

А2

А3

А3

В

1

1

1

1

3

0

1

1

1

3

0

1

1

0

1

1

1

1

–1

–1

2

1

0

–2

–4

2

0

0

1

2

–1

0

–γ

10

–1

9

–6

0

0

–11

–21

–6

–10

δ=

0

0

1

–17

–10

работы

В

строке

оценок

первой

симплекс

А1

А2

А3

А4

В

МБИ

таблице имеется положительная оценка δ3=1.

1

–1/2

0

3/2

1

0

1/2

1

–1/2

0

Поэтому

нельзя

утверждать,

что

вект р

δ=

0

–1/2

0

–33/2

–10

α =(1, 0, 0, 0) является оптимальным реше ием

данной задачи. Однако,

если

в качестве базиса данного опорно.

о решения

взять векторы А1, А3, то в новой симплекс таблице все векторыгусловий данной

задачи

имеют

неположите ьные оценки

и,

следовательно,

по

доказанной

теореме вектор α =(1, 0, 0, 0)

ВПО

явля тся оптимальным решением данной КЗЛП.■

Теорема ( о неограниченности целевой функции).

Пусть симплекс

аблица

приведена

к

некоторому базису опорного

решения α канонической задачи линейного программирования (1) – (3) на
минимум. Если при эт м существует столбец Аs								с положительной2013			оценкой,
т.е. δs > 0, где			s=1, 2, …, n , а все остальные элементы						этого столбца
неположительные,							ЧОУ
			.е, αis ≤ 0, i=1, 2, …, r , то целе ая функция данной задачи
							Москва
самостоятельной0 0 … 1 a r,r+1 … a rs								… a rn	αr
		студентов

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

▲ Пусть симплекс

аблица приведена к базису

А1, А2, …, Аr опорного

решения α=(α1, α2, …, αr, 0, 0, …, 0) и имеет вид:

A’1

A’2

A’r

A’r+1

…

A’s

…

A’n

B’

…

1

0

…

0

a/1,r+1

…

a'1s

…

a'1n

α1

Для

0

1

…

0

a'2,r+1

…

a'2s

…

a'2n

α2

…

…

…

…

…

…

…

…

'

'

'

0

0

0

δr+1

…

δs

…

δn

δ0

С едова ельно, вектор ограничений В’, а также вектор условий А’s

можно пред тавить в виде линейной комбинации базисных векторов, а именно,

(12) А’1	α1+ А’2		α2 + …+ А’r αr = В’ и
’	’	’	’	’
А1	a 1s	+ А	2 a’2s + … + А r a’rs = A s

75

		работы
(13) А’1 a’1s	+ А’2	a’2s + … + А’r a’rs – A’s =Ө .
Помножив соотношение	(13)	на переменную t > 0 и вычтя его из
соотношения (12), получим:

А’1 ( α1 – t a’1s ) + А’2 ( α2 – t a’2s ) + … + А’r (αr – t a’rs) + A’s t = B’.

Из последнего соотношения и с учетом т го, что a’is ≤ 0, следует, что вектор

Αt = (α1 – t a’1s , α2 – t a’2s , …, αr – t a’rs , 0, …, 0, t, 0, …, 0 )

является допустимым решением задачи (1) – (3). По лемме о целевой функции

для допустимого решения αе

имеем

0

f(αt) = f(α) – δ1 ( α1

– t a’1s

) – δ2

( α2 – t a’2s ) – …– δr ( αr – t a’rs ) – δs t .

самостоятельной0 1 –1 0 3

С учетом того, что оценки базисных векторов равны нулю, т.е., δ1= δ2=

x1

+

6x2

–

x3

–

ВПОx4

+

x5

= 6,

…= δr=0, значение целевой функции можно записать в видеМБИ: f(αt) = f(α) – δs

t.

Так, как

δs > 0 , то при t→ +

целевая функция неограниченно уменьшается,

.

т.е., f(αt) → – , и, следовательно, задача е имеет оптимального решения.■

Пример. Дано опорное реше ие α = ( 2, 0, 3, 0, 7)

КЗЛП на минимум:

А1

А2

А3

А4

А5

В

2013

f(x)=

–4x1

–

9x2

–

x3

+

x4

–

x5

(min)

2x1

+

2x2

+

x3

–

x4

=7,

г

x1

+

x2

–

x3

–

x4

=5,

ЧОУ

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

Выясним, имеет ли данная задача оптимальное решение?

▲ Приведя систему векторов условий к симплексной таблице, соответствующей

											базису	А1 , А3 ,		А5	данного
											опорного решения α = ( 2, 0, 3,
			2	2	1		–1	0	7
					студентов						0, 7), видим, что оценка δ4 = 2 >
			1	1	–1		–1	0	5
			1	6	–1		–1	1	6		0, а се остальные координаты
–γ=			4	9	1		–1	1	0
											ве тора	А4 неположительные.
											Следовательно,		по	доказанной
		А1’		А2’	А3’	А4’		А5’	В’
			0	0	–1		1	0	–3		теореме,	целевая			функция
			1	1	1		–1	0	5		неограниченна		снизу			на
			0	5	–2		0	1	1
											множестве			допустимых
			0	5	–3		3	1	–20
											решений,	то	есть		исходная
										Москвазадача не имеет оптимального
		А1’’		А2’’	А3’’		А4’’	А5’’	В’’
											решения. ■
			1	1	0		0	0	2
δ=			0	5	0		–2	1	7
			0	0	0		2	0	–18
Ответьте на вопросы
1. КакДля			получить симплекс таблицу системы векторов условий канонической

задачи линейного программирования?

76

2.		работы
	Чему соответствуют элементы столбца ограничений В симплекс таблицы,
	приведенной к базису опорного решения?
3.	Какова величина оценок векторов базиса опорного решения в
	соответствующей симплекс таблице?
4.	Чему соответствует величина оценки столбца граничений В симплекс
	таблицы, приведенной к базису опорного решения?
5.	Сформулируйте лемму о целевой функции.
6.	Приведите схему доказательства леммы о целевой функции.

7. Сформулируйте теорему о достаточном условии оптимальности опорного

решения.
8. Докажите теорему о достаточном условии оптимальности опорного
самостоятельнойxj ≥ 0, j = 1, 2, 3,					α = (0, 1, 3).
решения.				МБИцелевой функции
9. Сформулируйте теорему	о неограниченности
канонической задачи линейного пр граммирования на минимум.
					.
10.Докажите теорему о неограниченности целевой функции						канонической
задачи линейного программирова ия		а минимум.	2013		г
xj ≥ 0,	j = 1, 2, 3,					α = (1, 1, 0).
Решите самостоятельно

Задача 1.Доказать, что опорное решение α является оптимальным решением

f(X)

=

x1

+

2xЧОУ2

–

ВПО

5x3

(max),

для данной КЗЛП .

1.1.

f(X)

=

x1

–

2x2

+

x3

(min),

x1

–

x2

+

2х3

=0,

x1

+

x2

+

5x3

= ,

1.2.

студентов

Москва

Для

x1

–

3x2

+

11х3

=–9,

3x1

–

x2

+

9x3

=5,

xj

≥ 0, j = 1, 2, 3,

α = (3, 4, 0).

Задача 2. Используя опорное решение α

данной

КЗЛП, доказать

неограниченность ее целевой функции.

2.1.

f(X)

=

–x1

–

x2

–

x3

(min),

–2x1

+

x2

+

х3

=4,

–x1

+

2x2

–

x3

=–1,

2.2.

f(X)

=

2x1

+

x2

–

x4

(max),

x1

–

x2

–

x3

+

=0,

x1

+

x2

–

x3

2x4 =2,

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

xj ≥ 0,

j = 1, 2, 3, 4,

77

4. Аj xj =B,

работы

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

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

n

3. f(X) = γj xj + γ0,

j 1

n

j1

5.xj ≥ 0, j=1,2,…,n.

Пусть вектор

α

опорное решение данной задачи.

МБИ

Выберем некоторый

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

, …, Вl ,

…, Вk , …, Вr, т.е.,

базис этого опорного решения, например, В1

опорное решение имеет вид

ВПО

α = ( 0, …, 0, α1, 0, …,, 0, αl, 0,

…, 0, αk, 0,…, 0, αr, 0, 0, .., 0).

Приведя систему векторов усл вий

к

базису

.

выбранного опорного

решения, получим симплекс таблицу

г

…

B1’

…

Bl’

…

Bk’

…

Br’

…

As’

…

B’

…

2013

…

1

…

0

…

0

0

…

a’1s

…

α1

…

…

…

…

…

…

…

…

…

…

…

…

ЧОУ

(4)

…

0

…

1

…

0

…

0

…

a’ls

…

αl

…

…

…

…

…

…

…

…

…

…

…

…

…

0

…

0

…

1

…

0

…

a’ks

…

αk

…

…

…

…

…

…

…

…

…

…

…

…

…

0

…

0

…

0

…

1

…

a’rs

…

αr

…

0

…

0

…

0

…

0

…

δs

…

δ0

студентов

1. Если любой век ор системы условий задачи в полученной симплекс

таблице имеет неположительную оценку, т.е., δj≤0

для всех j=1, 2, …, n, то

опорное решение

α является

птимальным решением данной задачи (теорема

о достаточном усл вии оптимальн сти опорного решения).

2. Если в си

плекс аблице существует

s-й столбец с положительной

оценкой, т.е. δs > 0, где s=1, 2, …, n

, а все стальные элементы

s-го столбца

неположительные, т.е,

αis ≤ 0, i=1, 2, …, r , то целевая функция данной задачи

неограниченна на множ стве допустимых решений, и, следовательно, задача не
имеет оптимального решения (теорема оМоскванеограниченности целевой функции).
Для	a'ks	a'is 0	a'is
	3. Если оценка s-го столбца положительная, т.е. δs > 0, где s=1, 2, …, n, но

при этом среди элементов этого столбца найдется положительный, т.е, α’is >0,

i=1, 2, …, r , то рассматриваются отношения вида	i	для всех		a’is > 0 , среди
	a'is
которых выбирается наименьшее. Пусть это будет отношение			k		= min {	i	}.

78

Затем проводится преобразование Жордана симплекс таблицы (4) с разрешающим элементом α’ks. При этом k-ю строку помножаем на 1 / α’ks , далее эту же строку поочередно прибавляем к строке i, где i = 1, 2, …, r, и к строке оценок, предварительно помножив соответс венно на величину (–α’is) и на (–δs) .После такого преобразования будет п лучена симплекс таблица (5),

приведенная к базису, отличному от предыдущего, так как вектор Вk

уступил

место вектору Аs.

…

B1’’

…

Bl’’

…

Bk’’

…

Br’’

…

As’’

…

B’’

…

1

…

0

…

–a’1s / a’ks

…

0

…

0

…

α1–a’1s αk / a’ks

…

…

…

…

…

…

…

…

…

…

…

…

(5)

работы

…

0

…

1

…

–a’ls / a’ks

…

0

… 0

…

αl–a’1s αk / a’ks

МБИ

…

…

…

…

…

…

…

…

…

…

…

…

…

0

…

0

…

1 / a’ks

…

0

… 1

…

αk / a’ks

…

…

…

…

…

…

…

…

… …

…

…

…

0

…

0

…

–a’rs / a’ks

…

1

…

0

…

αr–a’rs αk / a’ks

.

…

0

…

0

…

–δs / a’ks

…

0

… 0

…

δ0–δs αk / a’ks

г

Симплекс таблица (5) обладает следующими свойствами:

10. Она приведена к базису В1, …, Bl, …, Bk–1, Bk+1, …, Br, …, As.

2

0

ВПО

. Все элементы столбца огранич ний неотрицательные.

▲ Так как вектор α является опорным решением рассматриваемой

задачи, то αk ≥ 0. По выбору α’ks > 0, следовательно,

k

≥ 0. Тогда для любых

a'

ks

a’is ≤ 0

будет вып лняться неравенство αi–a’is αk

/ a’ks 2013≥ 0, а для всех a’is

> 0

будем иметь αl–a’1s αk / a’ks

= a’is (αi / a’is – αk / a’ks ) ≥ 0, т.к.

k

= min {

i

}.■

a'is

ЧОУ

a'ks

a'is 0

30. Таблица приведена к базису опорного решения

α’ = (0, …, 0, α1–a’1s αk / a’ks,

Москва

Замечаниясамостоятельной

при переходе

отстудентоводного опорного

решения

к

другому

выбирать

тот

0, …, 0, αl–a’1s αk / a’ks, 0, …, 0, αr–a’rs αk / a’ks, 0, …, 0, αk / a’ks, 0, …, 0), на котором значение целевой функции не больше, чем на предыдущем опорном

решении α, т.е., f(α’) ≤ f(α).

	▲ Из т блицы (4) следует, что f(α) = δ0. Так как αk ≥ 0,					δs > 0, α’ks > 0,
	то f(α’) = δ0 – δs	k	≤ δ0 = f(α).■
	Для	a'ks
		> 0, то приходим к такому новому опорному решению α’, для
	1) Если αk
	которого f(α’) < f(α). Если же			αk =0, то α’ =	α и произошел переход к новому
	базису исходного опорного решения α.
	2) Пои к оптимального решения симплекс методом можно ускорить, если
	разрешающий элемент α’ks,			который	соответствует	наибольшему из

79

											k													работы
	произведений вида {δs												} по всем δs > 0 и по всем α’ks >0. При этом значение
											a'ks
	целевой функции уменьшается на максимально возможную величину.
		3) Если с помощью симплекс метода будут найдены два оптимальных
												1								2							4				МБИ5
решения α’opt и α’’opt, то линейная комбинация этих																												птимальных решений вида
	α = λ1 α’opt				+ λ2 α’’opt, где λ1											+ λ2 = 1, λ1 ≥ 0, λ2 ≥ 0,													удет также оптимальным
	решением.
		Принимая симплекс таблицу (5) за исходную, повторяем всю процедуру.
		Пример. Дано опорное решение α = (0, 0, 4, 8, 3) КЗЛП вида
					самостоятельной																		x3	+		x4			–		2x5		(min)
						f(x)=			–2x1							–	5x2				–
											x1				+		4x2				–		x3	+	2x4				–		x			=12,
											2x				+		3x							+	2x									=13,
											2x1				+		3x2				+		x3	+		x4			+		x5		.	=15,
								xj ≥ 0, j=1, 2, 3, 4,5																								г
	№1		А1			А2		А3			А4					А5				В				Используя							симплекс						метод,
		1			4			–1		2					0					12		найти оптимальное решение.
		2			3			0		2						–1				13		= (0, 0, 4, 8, 3). 2013
		2			3			1		1					1					15				▲ Приведем систему векторов
	–γ=	2			5			1			–1				2					0		условий задачи и строку с
																						противоположеннымиВПО												значениями
	№2	3			7			0		3					1					27		коэффициентов								целевой				функции к
		2			3			0		2						–1				13		симплекс				таблице, соответствующей
		2			3			1		1					1					15
			0			2		0			–2					1			–15			базису А3, А4, А5									опорного решения α
																						Москва									min
	№3	3			7			0		3					1					27		В симплекс т блице №4 векторы А1 и
		5			10			0		5					0					40
			–1			–4		студентов											–12			Таким				образом,							преобразование
								1			–2				0							ЧОУА2 имеют положительные оценки δ1=2
			–3			–5		0			–5				0				–42			и		δ2=5.					Следовательно,								данное
	№4	0				1		0		0					1					3		опорное						решение					не			является
		1			2			0		1					0					8		оптимальным.
																						Для перехода к новому опорному
		1			0			1		0					0					4
	δ=	2			5			0		0					0					–2		решению						выбираем					разрешающий
																						элемент,				используя							оба			критерия.
	№5	0			1			0		0					1					3
	Для																																		i
			1		0			0		1						–2				2		Сначала находим												{			} для
		1			0			1		0					0					4												a'is 0			a'is
	δ=	2			0			0		0						–5			–17			1-го		min {8/1, 4/1}=4 и 2-го столбца
																						min{3/1,							8/2}=3.				Затем				для
	№6	0			1			0		0					1					3
																						уменьшения числа итераций находим
		1			0			0		1						–2				2
		0			0			1			–1				2					2		max{δ1* 4; δ2 *3}= max{2* 4; 5*3}=15.
	δ=		0			0		0			–2					–1			–21
	Жордана проводим								с разрешающим													элементом				а12=1. Получаем										симплекс

80