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

αi2>0, …, αir> 0, где r = rang{ A1, …, An }, и в соответствующий ему базис системы условий КЗЛП должны входить векторы условий КЗЛП – Ai1, Ai2, …, Air . Так как ранг системы векторов условий КЗЛП совпадает с количеством ненулевых координат данного опорного решения, о век оры Ai1, Ai2, …, Air могут образовывать только единственный базис, соответствующий рассматриваемому опорному решению. ■

Утверждение о том, что вырожденному опорному решению КЗЛП может соответствовать несколько базисов системы векторов условий КЗЛП ,

подтверждается следующим примером.				работы
Пример. Дана КЗЛП :	+	x2					),
f(X) = x1
					(	min
x1	+	x2	–	2x3	+	x4	МБИ
							=1,
x1	–	x2	+	3x3	–	x4	=1,
	xj	≥ 0,	j = 1, 2, 3, 4.

и дано вырожденное опорное реше ие α =( 1, 0, 0. 0) этой задачи. Очевидно, что
			.
вектор А1, соответствующий ненулевой координате данного опорного решения,
самостоятельной	ВПО	2013	г
образует линейно независимую систему векторов и, следовательно, может быть
дополнен до любого из базисов системы векторов условий, соответствующего

данному опорному решению, например, либо до базиса А1, А2 , либо до базиса

А1, А3, либо до базиса А1, А4.

Свойство 3. Один и тот же базис системы векторов условий

(3) и, следов тельностудентов, являются решениемМосквасистемы линейных уравнений (2). Поэтому, под тавляя указанные векторы в систему линейных уравнений (2) ,

канонической задачи линейного программирования (1) – (3) не может являться

базисом двух различных п рных решений этой з д чи.
	▲ Предположим, ч о базис A1, …, Ar системы векторов условий КЗЛП
	ЧОУ
(1) – (3) являет я бази ом опорного решения: α’ =( α’1 ,…, α’r , α’r+1,…, α’ n ) и
опорного решения α” =( α”1 ,…, α”r , α”r+1,…, α”n ) , у которых α’r+1= 0,…, α’n = 0
и	α”r+1 = 0,…, α”n = 0. След вательно, α’ =( α’1 ,…, α’r , 0,…, 0 ) и α” =( α”1 ,…,
α”r	, 0,…, 0 ). По определению опорного решения векторы α’=(α’1, …, α’r ,0, …,
0 )	и α” =( α”1, …, α”r, 0,…, 0 ) являются д пустимыми решениями КЗЛП (1) –

получаем: А1 α’1 + А2 α’2 +…+ Аr α’r = B и А1 α”1 + А2 α”2 +…+ Аr α”r = B.

После вычитания второго соотношения из первого, получим:

А1 (α’1 – α”1 ) + А2 (α’2 – α”2 )+…+ Аr (α’r – α “r) = Ө.

Из этого соо ношения с учетом линейной независимости базисных

векторов A1, …, Ar , имеем: α’1 – α”1 = 0, α’2 – α”2 = 0, …, α’r – αr = 0. то есть

α’1 = α”1, α’2 =		α”2, …, α’r = αr. Следовательно, один и тот же базис системы
условийДля	КЗЛП	(1) – (3) является базисом только одного опорного решения,

61

работы

(n m)!m!

т.к. α’ = α”.■

Следствие. Каноническая задача линейного программирования (1) – (3) имеет конечное число различных опорных решений.

▲ Любому опорному решению задачи (1) – (3) соо ветствует не менее одного базиса системы векторов условий задачи. Один и тот же базис системы векторов условий рассматриваемой задачи не может быть базисом двух различных опорных решений этой задачи. Следовательно, число опорных решений не превосходит числа базисов системы векторов условий задачи (1) –

(3). В то же время, число базисов любой системы из n m-мерных векторов

самостоятельной					n!	.
конечно и не превосходит числа сочетаний из n по m , то есть, cnm
	ВПО
Следовательно, число опорных решений каноническойМБИзадачи линейного
программирования то же конечно.■			.
Свойство 4. Базис системы векторов	условий канонической				задачи
			г
линейного программирования (1) – (3) является базисом некоторо о опорного
решения этой задачи тогда и тол ко тогда,		2013
	когда вектор о раничений В

системы линейных уравнений (2) инейно выражается через базисные векторы

задачи (1) – (3), о ес ь оно удовлетворяетЧОУогр ничениям (3) α i1≥0 , αi2≥0 , …, αir≥ 0 и является решением системы линейных ура нений (2), то есть обращает

с неотрицательными коэффициентами.

▲ Необходимость. Пусть Ai1 , Ai2, …, Air базис системы векторов условий задачи (1) – (3) являе ся базисом опорного решения α = ( α1, …, αj, …, αn ) этой задачи. Из определения базиса опорного решения следует, что αi = 0

задачи (1) – (3) и вектор ограничений В Москвапредставим в виде Аi1 αi1 + Аi2 αi2 +…+

для любых i ≠ i1, i2, …, ir, .

По определению, п рное решение является допустимым решением

ее в точное чи ловое равенство вида Аi1 αi1 + Аi2 αi2 +…+ Аir αir = B.

Следовательно, вект р ограничений В линейно выражается через базисные векторы Ai1, Ai2, …, Air с нео рицательными коэффициентами.

Достаточность. Пусть Ai1, Ai2, …, Air базис системы векторов условий

Аir αir = B , где α i1≥0 , αi2≥0 , …, αir≥ 0. Рассмотрим вектор α =( 0, …, 0, α i1, 0, …, 0, αi2 , 0, …, 0, αir, 0, …, 0 ). Очевидно, что этот вектор удовлетворяет условию

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

координатам	соо ве с вуют векторы из набора базисных векторов Ai1, Ai2, …,
Air. Может	лучить я, что среди координат α i1, αi2, …, αir окажутся такие,

которые равны нулю ( например, если вектор α является вырожденным). В этом
случаеДля	студентов
	остальным	ненулевым координатам вектора будут соответствовать
некоторая, часть		базисных векторов, которая будет, очевидно, линейно

62

независимой. Таким образом,

вектор α по определению является опорным

решением задачи (1) – (3). Кроме того, векторы условий данной задачи, не

попавшие в набор базисных векторов Ai1, Ai2, …, Air , будут соответствовать

нулевым координатам рассматриваемого вектора α.

Следовательно, по определению, набор базисных векторов Ai1, Ai2, …, Air

системы векторов условий задачи (1) – (3) является

азисом

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

α.■

Замечание. На основании свойства 4 можно н йти все опорные решения

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

действия:

работы

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

МБИ

В

и

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

выбрать среди них разложение с не трицательными коэффициентами;

для каждого

выбранного разложе ия

вектора

В

с

неотрицательными

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

Пример. Найти все опорные решения КЗЛП:

.

г

f(X)

=

x1

+

2x2

–

х3

(

min

),

x1

+

x2

–

x3

ВПО

,

=3,

2x1

+

x2

+

x3

=3

xj

≥ 0,

j=1, 2, 3, 4.

Найдем все базисы системы векторов условий данной задачи, разрешив ее

относительно различных пар векторов, входящих в эту систему, а именно:

А1

А2

А3

В

А1’

А2’

А3’

В’

А1’’

2013

В’’

А2’’ А3’’

1

2

–1

3

1

2

–1ЧОУ

3

1

0

1

1

2

1

1

3

0

–3

3

–3

0

1

–1

1

А1’’’

А2’’’

А3’’’

В’’’

А1’’’’

А2’’’’

А3’’’’

В’’’’

1

1

0

2

1

1

0

2

0

–1

1

–1

1

0

1

1

Получили три базиса системы векторов условий данной задачи: А1’’, А2’’;

А1”’,

А3”’ и А2’’’’,

А3’’’’

и соответствующие им векторы решений системы

уравнений: α’’=(1,1,0), α’’’=(2,0,1), α’’’’=(0,2,1), из которых опорными решениями

’’

Москва’’’

данной задачи будут векторы α

=(1,1,0), α

=(2,0,1).■

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

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

1.

Какое количество базисов может иметь система векторов условий

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

2.

айте определениестудентовбазиса

опорного

решения

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

задачи

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

63

3. Сколько базисов системы векторов условий канонической задачи линейного программирования может соответствовать опорному решению этой задачи?

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

5. Сколько нулевых координат может иметь оп рн е решение канонической

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

6.

Дайте определение ранга системы векторов.

7.

Дайте определение невырожденного и вырожденного опорного решения.

8. Какое

максимальное количество базисов системы векторов условий

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

Задача 2. Найтисамостоятельнойвсе базисы данного опорного решения:

вырожденному опорному решению?

работы

9. Какое

максимальное количество базисов

ВПО

условий

системы МБИвекторов

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

невырожденному опорному реше ию?

.

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

2013

г

Задача 1. Образуют ли векторы A1, …, Ar базис опорного решения α для

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

1.1.

x1

– x2

+

2x3 +

x4ЧОУ=1,

x1

+

2x2

–

x3

+

x4

=2,

2x1

–

x2

+

3x3

–

x4

=1,

xj ≥ 0,

j= 1, 2, 3, 4.

α = (1,0,0, 1);

А1 , А4 ;

А2, А4.

1.2.

Москва

2.2.Для

x1

+ 2x2

–

x3

+

x4

=1,

α = (1,0,0,студентов0);

xj

≥ 0,

j= 1, 2, 3, 4.

α = (1,0,0, 0); А1 , А2 ; А1, А3;

А1 , А4 ;

А2, А3.

1.3.

x1

+

2x2

–

x3

+

x4

=2,

x1

–

3x2 + x3

+ x4

=– 3,

2x1

+

x2

–

x3

+

2x4

=1,

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

α = (0,1,0, 0);

А1 , А2 ,А 3;

А2, А3, А4 ;

А1, А3, А4.

2.1.

x1

+

x2

+

x3

+

x4

=1,

x1

–

x2

+

x3

–

x4

=1,

xj

≥ 0,

j=1, 2, 3, 4.

x1

+

x2

+

x3

=1

x1

–

2x3

=0

64

	xj ≥ 0, j= 1, 2, 3.								работы
2.3.	α = (1/2,0,1/2); .
	x1	–	x2	+	x3	+	x4	=2,		МБИ
	2x1	+	x2	–	x3	–	x4	=1,
	xj ≥ 0,		j=1, 2, 3, 4.
	x1	+	x2	+	2x3	–	x4	=3,
	xj ≥ 0,		j=1, 2, 3, 4.
	α = (1,0,1, 0);

2.4.	x1	+	2x2	–	x3	+	x4	=1
	2x1	–	x2	+	x3	–	x4	=0,
	x1	+	3x2	–	x3	+	x4	=2,

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

Задача 3. Является ли базис системы вект ров условий данной канонической

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

ВПО

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

этой задачи?

2013

.

3.1.

x1

+

x2

+

x3

=2,

ЧОУ

г

–x1

–

х2

+

x3

=2,

xj ≥ 0,

j=1, 2, 3.

А2, А3.

3.2.

x1

+

x2

+

x3

=1,

Москва

3.4.

2x1

–

х2

–

3x3

=2,

студентов

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

А1, А3.

3.3.

x1

+

x2

+

3x3

+

2x4

=2,

x1

+

x2

+

x3

–

x4

=1,

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

Для

А2, А3.

x1

+

x2

+

3x3 +

2x4

=2,

x1

+

x2

+

x3

–

x4

=1,

xj

≥ 0,

j=1, 2, 3, 4.

3.5.

А1, А4.

x1

–

x2

+

x4

+

х5

+

4х6

=1,

x1

x2

–

x3

+

7х5

+

2х6

=1,

+

x2

–

х6

=1,

65

xj ≥ 0, j=1, 2, 3, 4.	работы
А1, А2. А3.

Задача 4. Найти все опорные решения для сис емы условий канонической

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

МБИ

4.3.

4.1.

x1

–

2x2

–

x3

+

x4

=–1,

2x1

+

x2

–

x3

+

2x4

=3,

4.2.

xj ≥ 0,

j=1, 2, 3, 4.

x1

+

2x2

+

x3

=4

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

2x1

+

2х2

+

5x3

=5

ВПО

xj ≥ 0,

j=1, 2, 3.

4x1

+

5x2

+

x3

+

x4

=29,

.

6x1

–

x2

–

x3

+

x4

=11,

г

4.4.

xj ≥ 0,

j=1, 2, 3, 4.

2013

x1

+

2x2

+

x3

+

3x4

+ х5

=5,

2x1

+

2x2

+

x3

–

2x4

=–1,

= ,

–

ЧОУ

+

x4

4.5.

xj

≥ 0,

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

5x1

+

2x2

–

x3

+

x4

=42,

4x1

–

4x2

+

x3

+

x4

=16,

4x1

+

x4

=3 ,

xj ≥ 0,

Москва

4.6.

2x1

–

x4

=3,

Для

студентов

3x1

x1

+

2x2

+

x3

+

2x4

=3,

4.7.

xj ≥ 0,

j=1, 2, 3, 4.

x1

+

2x2

+

x3

–

4x4

=4,

2x1

–

x2

+

x3

–

2x4

=2,

x1

+

x2

+

x3

–

3x4

=3,

xj ≥ 0,

j=1, 2, 3, 4.

66

(2) Аj xj =B,

работы

2. 6. Оптимальное решение канонической задачи линейного программирования

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

n

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

j 1

n

	j 1
(3)	xj ≥ 0, j=1,2,…,n.	МБИ
самостоятельной
Задача (1) – (3) может иметь не одно оптимальное решение и при этом
имеет место
Теорема (об	оптимальном решении). Если	каноническая задача
		.
линейного программирования (1) – (3) имеет оптимальные решения, то одно из
них является опорным решением этой задачи.		г
▲ Рассмотрим оптимальное решение задачи (1)		– (3) с наименьшим

числом ненулевых координат. Пусть таким решением будет вектор α0 = ( α1, …,

α , 0, …, 0),	где координаты α1> 0, , α > 0 (координаты всегда можно
перенумеровать так, что бы п рвыми из них сталиВПОненулевые) и докажем, что
выбранный вектор является опорным решением задачи (1) – (3).
Предположим про ивное, а именно, что вектор α не является опорным
решением. Тогда по определению опорного решения, векторы		A1, A2, … A ,
соответствующие ненулевым координатам выбранного2013вектора		α0, образуют

линейно зависимую систему, то есть можноЧОУ ук з ть ненулевой набор чисел k1, k2, …k такой, что будет выполняться соотношение

A1 k1 + A2 k2 + … + A k = Ө.

Так как вект р α0 является птимальным решением, то он является и допустимым решением рассматриваемой задачи, то есть, этот вектор является

решением систе		ы линейных уравнений (2). Тогда по определению решения
системы уравнений долж о выполняться соотношение
		A1 α1 + A2 α2 + … + A α = В.
Прибавив		к соотнош нию (5) соотношение (4), умноженное на δ,
получим		Москва
	А1( α1 δ k1) + А2 ( α2 δ k2 ) + … + А ( α		δ k ) = B.
Из последнего соотношения по определению решения системы уравнений
с едует, что век оры α’ =( α1 + δ k1, α2 + δ k2 , … α + δ k )			и α” =( α1 – δ k1,
α2 – δ k2 , …	α	– δ k ) являются решениями системы линейных уравнений
(2). Если же	числостудентовδ выбрать так, что оно удовлетворяет		арифметической

Для	’		”
		и	α будут удовлетворять условию (3), а
лемме, то координаты векторов α

67

n

работыn

сами векторы будут являться допустимыми решениями задачи (1)–(3) и при этом, хотя бы у одного из этих векторов число ненулев х координат будет меньше, чем . Пусть это будет вектор α’. Тогда этот вектор не будет являться

оптимальным решением, так как

ранее был выбран оп имальный вектор α0 с

наименьшим числом

j 1

j 1

МБИ

ненулевых координат. П эт му для векторов α’ и α’’

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

f(α0) < f(α’),

f(α0) ≤ f(α’’),

n

n

+ δkj) + γ0,

которая равносильна системе:

γj αj + γ0 < γj (αj

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

j 1

j 1

ВПО

γj αj + γ0 ≤

γj (αj

δkj) + γ0.

Откуда получаем противоречивую систему:

.

n

г

0 < δ γj kj,

2013

j 1

n

0 ≤ – δ γj kj.

j 1

ЧОУ

что вектор α0 не является опорным

Таким образом, предпо ожение о том,

решением не верно. Следоват льно,

вектор

α0 является опорным решением

задачи (1) – (3). ■

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

f(X) =

2x1

+

x2

–

xМосква3 – 5x4(min)

имеет оптимальное решение, то его можно найти среди опорных решений этой

задачи, так как число

п рных

решений

конечно. Для этого необходимо

Найти все опорныестудентоврешения, вычислить значение целевой функции на

действовать так:

найти все опорные решения данной задачи;

для каждого найденного

п рн го решения вычислить значение целевой

функции;

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

Пример. Д на КЗЛП
каждомДля	x1	– x2	+ 23	– x4	= 2,
	2x1	+ x2	– 3x3	+ x4	= 6,
			xj ≥ 0,	j = 1, 2, 3, 4.
	из них и выбрать среди них оптимальное решение.

68

работы

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

различных пар векторов, входящих в эту систему:

А1

А2

А3

А4

В

А1

А2

А3

А4

В

А1

А2

А3

А4

В

1

–1

2

–1

2

1

–1

2

–1

2

1

0

–1/3

0

8/3

2

1

–3

1

6

0

3

–7

3

2

0

1

–7/3

1

2/3

вектор α’’ = (8/3, 0, 0, 2/3).■

МБИ

А1

А2

А3

А4

В

А1

А2

А3

А4

В

1

–1/7

0

–1/7

54/21

–3

0

1

0

–8

0

–3/7

1

–3/7

–2/7

–7

1

0

1

–58/3

Данная задача имеет только два опо ных ешения: α’ = (8/3, 2/3, 0, 0),

α’’ = (8/3, 0, 0, 2/3), на которых значение целевой функции соответственно

’

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

равны f(α

) = 6,

f(α ) = 2. Следовательно,

оптимальным решением является

Замечание.

ВПО

Рассмотренный сп с б нахождения оптимального решения

может

быть

реализован

на

совреме

ой

компьютерной

.

Однако

технике.

г

существуют более рациональные способы перебора опорных решений с целью

2013

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

таким способам относится симп ексный метод,

в котором при решении задачи

на

минимум

(максимум)

на

ЧОУ

решения

каждом

шаге поиска оптимального

осуществляется переход от одного опорного решения к другому с меньшим

(большим)		значением целевой функции.
Ответьте на вопросы
1.	Сформулируйте те рему об оптимальном решении канонической задачи
		студентов
	линейного программирования.
2.	Приведите схему доказательст а теоремы, сформулированной в п.1.
3.	Опишите	последовательн сть отыс ания оптимального решения
	каноническ й задачи линейн го программирования, если есть возможность
	найти все опорные решения э ой задачи.

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

Задачи. Для данных канонич ских задач линейного программирования найти
все опорные решения и выбрать среди нихМоскваоптимальные решения:
1.	Для	f(X) = x1	+	x2	–	x3	(min),
		x1	–	2x2	+	х3	=4,
		2x1	+	2x2	+	5x3	=5,
				xj ≥ 0,		j = 1, 2, 3,.
2.

69

3.

4.

Для

xj ≥ 0,

j = 1, 2, 3,

работы4.

f(X)

=

–3x1

+

x2

(min),

x1

–

2x2

+

x3

+

x4=1,

2x1

–

x2

–

x3

+

2x4=3,

xj ≥ 0,

j = 1, 2, 3, 4.

МБИ

f(X)

=

x1

–

2x2

–

x4

(min),

x1

+

x2

+

3x3

–

2x4

=2,

x1

+

x2

+

x3

–

x4

=1,

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

ВПО

.

f(X)

=

x3

+

x4

(min),

4x1

–

5x2

+

x3

–

x4

г

=29,

6x1

–

x2

–

ЧОУ

x3

+

x4

=11,

2013

xj ≥ 0,

j = 1, 2, 3, 4.

студентов

Москва

70