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

			работы
рационе. Это количество		продукта	содержит	aij xj	–	количество			i-го
химического	вещества, а	во всех	продуктах дневного				рациона		общее
				n
количество	i-го химического вещества равно			aij xj		и не должно быть
				j 1		МБИ
			n
меньше дневной нормы его потребления, т.е. aij xj					≥ bi		. Стоимость всего
			j 1
								n
набора X=(x1, …, xj, …, xn ) продуктов дневного рациона равна f(X) = cj xj .
								j 1

Таким образом, приходим к математической постановке задачи

планирования рационального питания в виде задачи линейного
самостоятельной	ВПО
программирования на минимум:
n
f(X) = cj xj	(min),		.
j
j 1
n
aij xj ≥ bi. i=1,2,…,m,
xj 1≥ 0, j=1,2,…,n.		2013
Задача планирования транспортных	перевозок. Вгm пунктах

производится однородный продукт в количествах a1, a2…, ai, …, am единиц,
который необходимо пер в зти в	ЧОУ
	другие n пунктов, в которых этот продукт
потребляется в количествах b1,	…, bj, …, bn.единиц. Стоимость перевозки

одной единицы продукта из i (i = 1, 2, … m) пункта производства в j (j=1, 2, …,

n) пункт потребления равна cij	денежных единиц, а производится продукта
Тогда: f(X) = c ij x ij	– суммарнаяМосквастоимость всех перевозок;
m	n
больше, чем потребляется, т.е. ai ≥ bj .
студентов	j 1
i 1

Требуется сформировать план пере озок продукта, при котором все потребности в продукте будут удо летворены с наименьшими затратами на перевозку.

Определим вектор X = (x11,… ,x ij, … ,x mn). как план перевозок между поставщика и и потребителями, где xij – к личество единиц продукта, которое перевозится из пункта производства i в пункт потребления j, и при чем либо перевозка имеется, либо она отсутствует, т.е. xij ≥ 0, i = 1, 2, … m; j = 1, 2, …,n,

	Для	m	n
		i 1	j 1

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

производится, .е. xi1 + … + x ij+ … + x in ≤ ai , i = 1, 2, … m;

в j пункт потребления завозится единиц продукта не менее, чем потребляется,

т.е. x1j + … + xij + … + x mj ≥ bj, j = 1, 2, …, n.

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

51

программирования на минимум:

			m	n
			f(X) =	c ij x ij (min),
			i 1	j 1
			xi1 + … + xij + … + x in ≤ ai , i = 1, 2, … m,
			x1j + … + xij + … + x mj ≥ bj , j = 1, 2, …,n,
			xij ≥0, i = 1, 2, … m; j = 1, 2, …,n.
	Замечание. При математической постановке экономической задачи
необходимо:
-	ввести переменные величины, каждая из которых определяет некоторый
	управляемый экономический параметр;				работы
- сформировать систему ограничений, связывающие введенные переменные,
	используя условия задачи.							МБИ
-	построить функцию цели (качества) выб ра значений переменных;
Ответьте на вопросы										.
1.	Дайте содержательную постановку				задачи
							планирования работы
	предприятия.								г
2.	Опишите	процесс	математической		постановки			задачи		планирования
	работы предприятия.				ВПО
3.	Напишите матема ическую постановку задачи планирования работы
	предприятия.
4.	Дайте содержательную постановку задачи планирования рационального
	питания.						2013
5.	Опишите	процесс	математической		постановки			задачи		планирования
	рационального питания			ЧОУ
6.	Напишите	математическую		постанов у		задачи				планирования
	рациональн го питания.
7.	Дайте содержательную пос ановку задачи планирования транспортных
	перевозок.
8.	Опишите процесс математической постановки задачи									планирования
	тран портных п р возок.			постановкуМосква
9.	Напишите	математическую				задачи				планирования
	самостоятельной
	транспортных перевозок.
Решите самос оя ельно
	Задача 1. Ма терская может отремонтировать за неделю либо 200 машин

классаДляБ, либо 600студентовмашин класса Ж. Стоимость ремонта машины класса Б равна С1 д.е., а класса Ж – С2 д.е. Сколько и какого класса машин необходимо

52

ремонтировать мастерской за неделю, чтобы ее доход был максимален, если:

а) С1 = 850 д.е., С2 = 530 д.е.; в) С1 = С2 ; с) С1=3С2; д) С1/ C2 = 9/2?

Задача 2. Фирма изготавливает для продажи изделия, используя цех механической обработки и цех покраски.

За одну смену механический цех может изг т вить либо 600 изделий типа А, либо 1200 изделий типа В. За то же время цех покраски может обработать либо 1200 изделий типа А, либо 800 изделий типа В. Цена изделий

типа А равна 50 д.е., а типа В – 30 д.е.
Рассчитайте суточную программу п оизводства изделий типа А и В так,
чтобы доход от их продаж был максимален, если:
а) оба цеха работают одну смену;	работы
в) механический цех работает три смены, а покрасочный – двеМБИсмены;

с) оба цеха работают две смены, но из-за нехватки сырья может быть изготовлено изделий типа А не более 800 штук, а изделий типа В не более 1000

штук.			ВПО		.
		ЧОУ		2013	г
		Москва
Для	самостоятельной
	студентов

53

работы

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

Рассмотрим каноническую задачу линейного программирования (КЗЛП)

n

(1)

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

j 1

a11

x1

+ … + a1j

xj

+ … + a1n

xn

= b1,

.

. . . . .

.

. . . .

. . .

(2)

ai1

x1

+

… +

aij

xj

+

…

+ ain

xn

=

bi,

.

. . . . .

.

. . . .

. . .

(3)

am1

x1

+ … + amj

xj

+ … + amn

xn

= bm,

x1

≥

0, .

xj

≥

.0,

xn

≥

0.

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

ВПО

Обозначим векторы условий и вектор ограничений КЗЛП соответственноМБИ

a11

a1j

a1n

b1,

.

…

…

…

…

г

ai1

= А1,

aij

= Аj,

ain

= An,

bi,

= B

…

…

xj

≥ 0,

…

…

2013

am1

(3)

j=1,2,…,n.

amj

amn

bm,

Тогда каноническую задачу

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

записать в виде

n

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

j 1

n

(2)

Аj

xj = B,

Москва

j 1

Пусть вектор α = ( α1,

, αj, …, αn) является допустимым решением задачи

студентов

(1)–(3), т.е. этот век ор является решениемЧОУ

системы линейных уравнений (2) и

удовлетворяет у ловиям не отрицательности неизвестных (3). При этом i1, i2,

..., ik – номера всех ненулевых к рдинат вектора α.

Определение. Допус имое решение α = ( α1, , αj, …, αn) канонической задачи линейного программирования (1) – (3) называется опорным решением , если векторы условий Аi1, Ai2, …, Aik, соответствующие ненулевым

координ т м вектора α = ( α1, , αj, …, αn), образуют линейно независимую
систему векторов
	Для
	Замечание. Чтобы выяснить, является ли вектор α = ( α1, , αj, …, αn)
опорным решением (1) – (3), необходимо:
	проверить, являе ся ли вектор α решением системы линейных уравнений (2),
проверить, удовлетворяет ли вектор α ограничением (3),
	выписать номера всех ненулевых координат вектора α и показать, что

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

54

Пример 1. Дана КЗЛП:
(1)	f(X) =	x1	–	x2	+	x3	+	x4		(min)
(2)		x1	+	x2	–	x3	+ x4		=	3,
		2x1 –		x2	+	x3	–	x4	=	0,
		x1	+	x2	+ 2x3 – x4				=	1,
(3)		xj ≥ 0			, j=1,2, 3, 4					МБИ

и вектор α =(1, 1, 0, 1). Определить, является ли вектор α опорным решением данной задачи.

	▲ Подставив координаты вектора α = (1, 1, 0, 1), в (2) – (3), убеждаемся,
что	он является допустимым решением данной задачи. Ненулевым
		самостоятельной1 –1 1 –1											векторыработыусловий А1, А2, А4,
координатам				вектора			α	соответствуют
														ВПО
преобразовав которые методом Гаусса, получаем систему единичных векторов.
Это соответствует тому, что векторы усл вий																		г
А1	А2	А4			А1		А2		А4			А1	А2	А4			А1		А2		А4
1	1	1			1		1		1			0	1	1		2013			.1		0
																0
2	–1	–1			3		0		0			1	0	0			1			0	0
1	1	–1			0		0		–2			0	0	–2			0			0	1
									2x1	– x2ЧОУ–			2x3	=		2,
	А1,	А2,		А4 образуют						систему			линейно			независимых					векторов.

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

задачи.■	A3		A1	A3Москва
A1
Пример 2. Дана КЗЛП			–	x2	+	2x3			(max)
(1) f(X)	=	x1
(2)		x1	+	x2	–	x3	α1,	=	1,
Лемма (арифметическаястудентов).				Пусть					α2, …, αl некоторые
(3)		xj ≥ 0		, j=1,2, 3.
и вектор α = (2, 0, 1). Определить, является ли ве тор α опорным решением
данной задачи.
▲ Подставив координа ы вектора α =(2,							0, 1).в (2) – (3), убеждаемся, что

он является допустимым реше ием данн й задачи. Ненулевым координатам вектора α соответствуют векторы условий А1, А3, преобразовав которые методом Гау а, видим,

Для
они образуют	2	–2			0		0
	линейно		зависимую				систему векторов. Следовательно, по

опреде ению, век ор α =(2, 0, 1) не является опорным решением данной КЗЛП.■

положительные числа, а k1, k2, …k ненулевой набор чисел, т.е. найдется

55

	работы
номер j такой, что kj ≠ 0, j = 1, 2, … . Тогда найдется положительное число δ
такое, что: αj δ kj ≥ 0 для всех	j = 1, 2, … l, а одно из чисел {αj		δ kj}
обязательно равно нулю.
Доказательство предлагается студентам провес и самостоятельно.
j 1		МБИ

Теорема (о существовании опорного решения). Если каноническая задача линейного программирования имеет хотя бы одно допустимое решение, то эта задача имеет и опорное решение.

▲ Рассмотрим КЗЛП

		n	xj + γ0,
получим	(1)	f(X) = γj
	самостоятельной
		j 1		ВПО
	(2)	n
		Аj xj =B,
	(3)	xj ≥ 0, j = 1,2,…,n,

которая имеет хотя бы одно допустим е решение. Из всех допустимых решений

данной задачи выберем допустимое реше ие с наименьшим числом ненулевых
			2013		где
координат. Пусть таким решением будет вектор α = ( α1, …, α ., 0, …, 0),
координаты α1> 0, …, α	> 0 (координаты всегда можно перенумероватьг				так,
что первыми из них станут нену евые) и докажем,			что выбранный вектор
		ЧОУ
является опорным решени м задачи (1) – (3).
Предположим про ивное, а именно, что вектор α не является опорным
решением. Тогда по определению опорного решения, векторы A1, A2, … A ,
соответствующие ненулевым координатам выбранного вектора				α, образуют
		Москва
линейно зависимую систему. Из определения линейно зависимой системы
векторов следует, ч о найдется ненулевой набор чисел k1, k2, …k				такой, что
студентов
будет выполняться соо ношение
(4)	A1 k1 + A2 k2 + … + A k		= Ө.
Так как вект р α	является допу тимым решением рассматриваемой

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

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

линейных уравнений (2). Если же число δ выбрать так, что оно удовлетворяет арифметической лемме, то координаты векторов α’ и α” будут удовлетворять

56

условию (3), а сами векторы будут являться допустимыми решениями задачи

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

вектора α. Следовательно, вектор α							является опорным решением задачи (1)–
(3).■
Ответьте на вопросы
1.	Выпишите в координатной форме j-й вектор условий канонической задачи
	линейного программирования.
2.	Дайте определение линейно зависимой системе векторов.
3.								работы
	Дайте определение опорного решения канонической задачи линейного
	программирования.									МБИ
4.	Как выяснить, является ли вект р						п рным решением данной канонической
	задачи линейного программирова ия?										.
5.	Выпишите формулировку арифметической леммы.
6.
	Сформулируйте теорему о существовании опорного решения для данной
	канонической задачи линейного программирования.										г
7.	На каком противоречии построено доказательство теоремы о существовании
								ВПО
	опорного решения для данной канонической задачи линейного
	программирования?								2013
Решите самостоятельно
	Дана система усл вий канонической зад чи линейного программирования
и векторы		α(k).	Выясни ь,			являются ли эти векторы опорными решениями
данной задачи:							ЧОУ
1.	х1	+	х2	–	х3	+ 3х4	= 3,
	2х1	–	х2	+ 3х3		– х4	= 4,
	х1	+ 2х2		–	х3	+ 2х4	= 2,

xj≥ 0,	j–1, 2, 3, 4, α(1) = (1, 0, 1, 1), α(2)=(3, –1, –1, 0).
2.					Москва
х1	+ х2	+ 2х3	– х4	= 4,
2х1	самостоятельной
	– х2	+ х3	– 2х4	= 2,
–х1	+ 2х2	+ х3	+ 3х4	= 2,

	xj≥ 0, j–1, 2, 3, 4,			α(1) = (1, 1, 1, 0),			α(2)=(2, 2, 0, 0), α(3)=(0, 2, 1, 0).
3	х1	– х2	студентов		–	3x5	= 1,
			+ х3	+ 3x4
	Для	+ х2	– х3	+ x4	+	х5	= 1,
	х1
	х1	+ х2	+ х3	+ 5x4	–	х5	= 3,
						57

4.

5.

6.

Для

х1

–

х2

+

2х3

–

3х4 = –2,

работы

xj≥ 0,

j–1, 2, 3, 4, α = (1, 1, 1, 0, 0),

х1 +

х2

+ х3

+ x4

– 2x5

= 5,

МБИ

х3

+ x4

+

х5

= 4,

xj≥ 0,

j–1, 2, 3, 4, α = (0, 1, 1, 1),.

х1

+ х2

+

x4

– х5

= 4,

х1

+ х2

+ х3 –

2х5

= 5,

xj≥ 0,

j–1, 2, 3, 4,5, α = (1, 2, 2, 1, 0),.

х1

–

х2

+ 2х3

+ 3х4

= 4,

2х1

+ 3х2

– х3

+

х4

= 3,

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

ВПО

.

х1

+ 2х2

– х3

– х4 = –1,

2х1

–

х2

+

3х3

+

8х4 =13,

2013

х1 – х2

+ х3

ЧОУ

+ 3х4 = 5,

xj≥ 0,

j–1, 2, 3, 4, α = (1, 0, 1, 1).

г

студентов

Москва

58

(2)	Аj xj =B,	работы
	2. 5. Базис опорного решения
Среди базисов	системы векторов	А1, …, Аj, …, Аn	условий
канонической задачи линейного программирования
	n
(1)	f(X) = γj xj + γ0,

j 1

n

j1

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

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

МБИ

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

Определение. Базис Ai1, Ai2, …, Air

системы векторов А1, …, Аj, …, Аn

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

α = ( α1, …,

αj, …, αn ), если αi = 0

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

.

г

Таким образом, базис Ai1, Ai2, …, Air

системы векторов А1 , …, Аj, …, Аn

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

α = ( α1, …,

2013

αj, …, αn ), если небазисным векторам из системы векторов условий задачи (1) –

(3) соответствуют нулевые координаты опорного решения.

3x1

+ 2xЧОУ2 – x3

+

3x4

=2,

Замечание. Так как в кторы условий,

ВПОсоответствующие

ненулевым

координатам опорного реш ния α =( α1 ,…, αj

,…, αn ), входят в каждый его

базис, то это опорное решения может иметь не один базис.

Пример. Дана КЗЛП

1

0

Москва2

1

1/5 0

2/5

3 2 –1 3

5

f(X)

= 3x1

–

x2

+

x4

(

min

),

2x1

–

x2

+

x3

–

x4

=3,

студентов

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

и ее опорное решение α = ( 1, 0, 1, 0). Ненулевым координатам опорного

решения соответствуют векторы А1, А3

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

задачи. Разрешив

етодом Гаусса систему векторов условий рассматриваемой

задачи относительно векторов А1, А3

А1

А2

А3

А4

А1

А2

А3

А4

А1

А2

А3

А4

2

–1

1

–1

2

–1

1

–1

0

–7/5

1

–7/5

Для

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

Свойства базисов опорного решения Свойство 1. Любому опорному решению канонической задачи линейного

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

59

▲ Пусть вектор α = ( 0, …,0, α i1 , 0,…, 0, αi2 , 0, …, 0, αil, 0, …, 0 )

является	опорным	решением	канонической		задачи	линейного
программирования			работы
(2)		n
(1)	f(X) = γj xj + γ0,
		j 1
	n	Аj xj =B,
	j 1
(3)	xj ≥ 0, j = 1, 2, …, n.				МБИ
где α i1>0 , αi2>0, …, αi > 0. Тогда по определению в системе векторов условий
задачи (1)	– (3) векторы Ai1, Ai2,		…, Ai , соответствующие			ненулевым
системы векторовсамостоятельнойусловий рассматриваемой канонической задачи линейного
координатам данного		опорного решения, образуют		линейно независимую
			ВПО

систему векторов, которую можно дополнить до базиса всей системы векторов условий данной задачи. Пусть этим базис м будет система из векторов Ai1, Ai2, … Ai Ai +1, , …, Air . Тогда небазисным векторам из системы векторов

условий задачи (1) – (3) соответствуют	улевые координаты опорного решения
и по определению векторы Ai1, Ai2, …, Air		2013		о решения
		образуют базис опорно.
α. ■			г
Следствие. Число нену евых координат у любого опорного решения α
	ЧОУ

канонической задачи лин йного программирования не превышает r = rang{ A1,

…, An } – ранга системы век оров условий этой задачи.

▲ Выше было доказано, что любому опорному решению КЗЛП

соответствует хотя бы один базис системы векторов условий КЗЛП. Число
	Москва
векторов в любом базисе системы векторов условий КЗЛП совпадает с рангом
студентов

этой системы. По определению базиса опорного решения, все координаты опорного решения α, соот етст ующие не базисным векторам системы векторов условий КЗЛП , равны нулю. Следовательно, ненулевых координат у опорного решения α не более, чем r.■

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

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

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

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

▲ Пусть вектор α = ( 0, …, 0, α i1, 0,…, 0, αi2, 0, …, 0, αir, 0, …, 0 ) –

невырожденное опорное решение КЗЛП, у которого по определению α i1>0,

60