Матан_ЛинПрог

1.4Для откорма животных употребляют два корма: I и II. Стоимость одного килограмма I корма – 5 тенге, II корма – 2 тенге. В каждом килограмме корма I содержится 5 ед. вещества (витамина) A, 2,5 ед. витамина B и 1 ед. витамина C. В каждом килограмме корма II содержится 3 ед. витамина A, 3 ед. витамина B и 1 ед. витамина C. Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты на откорм были минимальными, если суточный рацион предусматривает не менее 225 питательных единиц витамина A, не менее 150 ед. витамина B и не менее 80 ед. витамина C?

1.5На птицеферме употребляются два вида кормов – I и II. В единице веса корма I содержатся единица вещества A, единица вещества B и единица вещества C. В единице веса корма II содержатся четыре единицы вещества A, две единицы вещества B и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества A, не менее четырех единиц вещества B и не менее единицы вещества C. Цена единица веса корма I составляет 3 тенге, корма II – 2 тенге. Составить ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион питания.

1.6Для изготовления шкафов и буфетов деревообделочный завод применяет древесину четырех видов. Запасы древесины составляют соответственно 120, 160, 120, 80 ед. Количество единиц древесины каждого вида, необходимое для изготовления одного шкафа и одного буфета, а также прибыль, получаемая от реализации единицы продукции, даны в таблице.

	КОЛ-ВО ЕД.
ВИД	ДРЕВЕСИНЫ ДЛЯ		ЗАПАСЫ
ДРЕВЕСИНЫ	ПРОИЗВ-ВА ЕД-ЦЫ		ДРЕВЕСИНЫ
	ПРОДУКЦИИ
	Шкафы	Буфеты
I	0	4	120
II	4	0	160
III	2	2	120
IV	1	2	80
ПРИБЫЛЬ	2	3

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

предприятию наибольшую прибыль от реализации всей продукции.

1.7 Для изготовления двух видов деталей ( A и B) предприятие использует токарное, фрезерное и шлифовальное оборудование. Общий фонд полезного рабочего времени на каждом оборудовании соответственно: 8, 6, 9 станко-часов. Для производства 1 ед. детали A требуется времени: на токарном оборудовании – 2 ст/ч, на фрезерном – 1 ст/ч, на шлифовальном – 3 ст/ч, а для производства 1 ед. детали B – 2, 2 и 0 ст/ч на соответствующем оборудовании. Известно, что от реализации 1 ед. детали A предприятие получит 1 тенге прибыли, 1 ед. детали B – 3 тенге. Сколько единиц деталей

A и B должно выпустить предприятие, чтобы получить наибольшую прибыль?

1.8Для откорма животных употребляется три вида кормов I, II, III. В каждом килограмме корма I содержится 2 единицы питательного вещества A, 2 единицы питательного вещества B и 3 единицы питательного вещества C; в килограмме корма II – 1 единица питательного вещества A, 4 единицы питательного вещества B, 4 единицы питательного вещества C; в килограмме корма III – 3 единицы питательного вещества A, 3 единицы питательного вещества B и 2 единицы питательного вещества C. Откорм животных экономически выгоден, если каждое животное будет получать в дневном рационе не менее 6 единиц питательного вещества A, не менее 16 единиц питательного вещества B, не менее 12 единиц питательного вещества C. Стоимость 1 кг корма I – 2 тенге, 1 кг корма II – 3 тенге, 1 кг корма III – 2,5 тенге. Каков должен быть ежедневный расход корма каждого вида, чтобы затраты на приобретение корм были минимальными?

1.9Требуется составить смесь, содержащую три химических вещества A, B, C. Известно, что составляемая смесь должна содержать вещества A не

менее 6 единиц, вещества B не менее 8 единиц, вещества C не менее 12 единиц. Вещества A, B и C содержатся в трех видах продуктов – I, II и III – в концентрации, указанной в таблице.

		ХИМ.		ЦЕНА
ПРОДУКТЫ	ВЕЩЕСТВА			ЕДИНИЦЫ
	A	B	C	ПРОДУКЦИИ
I	2	1	3	2
II	1	2	4	3
III	3	1,5	2	2,5

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

1.10 Требуется составить смесь, содержащую три химических вещества A, B, C. Известно, что составляемая смесь должна содержать вещества A не менее 9 единиц, вещества B не менее 8 единиц, вещества C не менее 12 единиц. Вещества A, B и C содержатся в трех видах продуктов – I, II и III – в концентрации, указанной в таблице.

		ХИМ.		ЦЕНА
ПРОДУКТЫ	ВЕЩЕСТВА			ЕДИНИЦЫ
	A	B	C	ПРОДУКЦИИ
I	3	1	1	4
II	1	2	6	6
III	2	2	0	3

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

§2. Решение системы линейных уравнений методом Жордана-Гаусса

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

a11x1

a12x2

... a1nxn

b1

a22x2

... a2nxn

b2

a21x1

,

(2.1)

..............................................

a

m1

x

a

m2

x

2

... a

mn

x

n

b

1

m

в которой

а

а

а

...

11

12

...

1n

A

а21

а22

а2n

- основная матрица коэффициентов,

...

...

...

...

аm1

аm2

...

аmn

	b						x
	1							1
B	b2		- вектор-столбец свободных членов,	X		x2				- вектор-столбец
	...					...
	b					x
	m							m

неизвестных.

Суть метода Жордана-Гаусса состоит в том, что исключая последовательно переменные из каждого уравнения, кроме одной, получаем решение системы уравнений. При этом вектора, составленные из коэффициентов при неизвестных, с помощью преобразований обращаются в единичные (базисные). Соответствующие этим векторам переменные называются базисными, а остальные переменные - свободными. Если в общем решении системы свободные переменные приравнять нулю, то такое решение называется базисным.

Выпишем все коэффициенты при неизвестных и свободные члены в таблицу:

а11

…

а1j

…

аls

…

а1n

b1

…

…

…

…

…

…

…

…

аi1

…

аij

…

аis

…

аin

bi

…

…

…

…

…

…

…

…

аq1

…

аqj

…

аqs

…

аqn

bq

…

…

…

…

…

…

…

…

аm1

…

аmj

…

аms

…

аmn

bm

Элемент aqs 0 называется разрешающим элементом, а строка и столбец, где находится aqs , называются направляющими. Поделим всю направляющую строку на разрешающий элемент aqs и полученные

результаты запишем в эту же строку следующей таблицы. В направляющем столбце новой таблицы элемент aqs станет единицей, а остальные элементы

столбца заменим нулями. Элементы других столбцов и столбца свободных членов вычисляем по правилу «прямоугольника»:

aij'

aij

ais aqj

aij

aqs ais

aqj

(2.2)

aqs

aqs

b'

b

ais bq

bi aqs ais

bq

(2.3)

i

i

aqs

aqs

То есть во всех столбцах, кроме столбца свободных членов, получатся единичные (базисные) вектора. При этом возможны следующие случаи:

1)левая и правая части i-ой строки таблицы, соответствующей i-му уравнению системы, обращается в нуль (0=0), т.е. i-ое уравнение является линейной комбинацией остальных и поэтому оно может быть отброшено.

2)в i-ой строке таблицы, соответствующей i-му уравнению системы, все коэффициенты aij равны нулю, а bi 0, т.е. 0 bi 0. Это означает, что

система не имеет решений.

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

Задача. Решить систему линейных уравнений

2x		3x		4x			2x		1
	1		2		3			4
2x1 2x2 5x3								3 .
4x 2x			2	2x		3	5x	4	1
	1

Решение. Выпишем все коэффициенты при неизвестных и свободные члены в таблицу и с помощью метода Жордана-Гаусса найдем решение для данной системы.

	A1	A2	A3		A4		B	Выберем						за				разрешающий
I	2	3	-4	2			1	элемент число 2 из столбца A1
	2	2	-5	0			3	и разделим первую строку на
								этот			элемент.							Полученные
	4	2	2	5			1	результаты запишем в эту же
								строку во II –ую таблицу.
II	1	3/2	-2	1			1/2
								Столбец									A			станет
	0	-1	-1	-2			2	единичным.									1		Остальные
	0	-4	10	1			-1	элементы							новой					таблицы
								найдем					с		помощью					правил
II	1	7/2	0	5			-7/2	«прямоугольника» (2.2), (2.3).
I	0	1	1	2			-2	Например, найдем элемент:
								a'	a			a21 a12						a22 a11 a21 a12
	0	-14	0		-19		19	22		22				a						a
													11							11
I	1	-7/38	0	0			3/2				2 3				2 2 2 3				1; или
V	0	-9/19	1	0			0		2
											2				2
	0	-14/19	0	1			-1							элемент:

b'	b		a31 b1				b3 a11 a31 b1
			a
3	3								a
			11					11
	1		4 1		1 2			4 1	1 и так
			2
						2

находятся другие элементы II - ой таблицы.

После заполнения II -ой таблицы выберем за разрешающий элемент число (-1) из столбца A3 и разделим вторую строку на этот элемент. Столбец A3 станет единичным, а остальные элементы новой таблицы найдем с помощью правил (2.2), (2.3).

После заполнения II -ой таблицы выберем за разрешающий элемент число (-19) из столбца A4 и разделим третью строку на этот элемент. Столбец A4 станет единичным, а остальные элементы IV таблицы найдем с помощью правил (2.2), (2.3).

Из последней таблицы получим систему:

														x			7/38x					3/2
																1				2		x3				0		,
																	9/19x2
																	14/19x2									x4 1
откуда			находим									общее				решение:						x1 3/2 7/38x2 ,													x3 9/19x2 ,
x4 1 14/19x2 .												Векторы					A1,A3,A4					образуют базис в трёхмерном
пространстве; соответствующие им неизвестные																													x1,x3,x4						называются
базисными, а переменная x2																называется свободной. Если в общем решении
системы			взятьx2 0,										то получим					базисное решение													x1 3/2,									x3 0,
x4 1.
																	Упражнения
Решить систему уравнений методом Жордана-Гаусса:
	x x					2x					1						x x				2x					1					3x 2x							x					3
2.1.		1		2						3		4		2.2.			1		2					3			0	2.3.				1					2				3
	2x1 x2						2x3										2x1 3x2 x3														x1	x2				2x3						4
	4x x					2	4x				3	2					x 2x				2	x		3		7					2x 2x						2	x				3	4
		1															1															1
									x 3x					x		2											2x 3x				x		2
						2.4.					1		2		3		3											1		2		3
									2x1 x2					3x3									2.5. x1					x2	3x3			4
														2x3 8
									2x1 x2																		3x1 5x2 x3 4
	5x 2x							x				1				3x 3x					2x						1		2x x						3x					1
2.6.		1					2				3	6		2.7.			1		2						3			2.8.			1			2	x3				3
	2x1 x2						2x3									2x1 x2				x3			3						x1 2x2										8
	x 3x				2		x		3		5					x 2x		2	3x				3			4			4x 3x						2	2x				3		1
		1															1														1

						x 2x						x			4										2x x					3x					3
		2.9.					1				2			3		5					2.10.					1			2	x3			3
						2x1 x2						3x3													x1	2x2								2
																										3x2				4x3 1
						3x1 4x2 x3 2																			x1
	3x x			2x				1								x 3x					x		1							3x x							2x						4
2.11.		1	2				3	5					2.12.					1		2		3	7			2.13.					1					2				3
	x1	2x2		3x3												2x1 x2					x3									x1 2x2 x3										1
	2x 3x			2	x		3	4								2x x				2	3x		3	5						2x 3x							2		2x			3		0
		1																1														1
						3x 2x							2x				3								x 5x					x				1
		2.14.					1					2				3					2.15.				1				2			3			7
						2x1 x2 x3									5										2x1 x2					2x3
												3x3 4														4x2				x3 0
						5x1 x2																			x1
	2x 3x				3x				0							x 2x					4x			31						3x 2x									x					5
2.16.		1		2				3				2.17.						1		2			3	29		2.18.						1						2			3			1
	x1	x2	2x3				7									5x1 x2					2x3									2x1				3x2					x3
		2x2		3x3				3											x2		x3 10													x2 3x3 11
	x1															3x1														2x1
					2x x						3x				6									3x x				2x				9
		2.19.					1			2				3			16				2.20.				1		2				3		8
						2x1 4x2 3x3																		x1 2x2					2x3
								4x2				2x3 12																				12
					3x1																			x1 6x2

§3. Графический метод решения задач линейного программирования

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трёхмерного пространства.

Пусть дана задача линейного программирования, состоящая в определении максимального (минимального) значения функции:

F c1x1 c2x2									(3.1)
при ограничениях:
a11x1 a12x2 b1
			a22x2 b2
a21x1									(3.2)
...........................
a	m1	x	a	m2	x	2	b	m
		1
x1 0,			x2 0						(3.3)

Каждое из неравенств (3.2), (3.3) определяет полуплоскость совместно с граничными прямыми ai1x1 ai2x2 bi1 i 1,n , x1 0, x2 0. Если

система неравенств (3.2), (3.3) совместна, то область её решений есть множество точек, принадлежащих всем полуплоскостям.

Областью допустимых решений задачи (3.1) - (3.3) является выпуклое множество, которое называется многоугольником решений. Сторонами многоугольника являются прямые, уравнения которых получаются путём замены знаков неравенств на знаки точных равенств.

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

функция F принимает максимальное	(минимальное) значение. Для
определения данной точки строим линию	уровня c1x1 c2x2 h h const ,

проходящую через многоугольник решений, и будем передвигать её по направлению вектора N (c1;c2) при нахождении максимального значения функции и против направления вектора N (c1;c2 ) при нахождении минимального значения до тех пор, пока она не пройдёт через последнюю общую точку её с многоугольником решений. Координаты указанной точки и определяют оптимальный план данной задачи. Различные случаи решений показаны на рисунках:

рис.1		рис.2
Функция f	c1x1 c2x2	h принимает: максимальное значение в точке В и

минимальное - в точке А (рис.1); максимальное значение во всех точках отрезка АВ (рис.2); не ограничена на многоугольнике решений сверху и снизу (рис.3); не имеет ни одного решения (рис.4).

рис.3

рис.4

Алгоритм решения задач геометрическим методом

1.Строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2.Находят полуплоскости, определяемые каждым из ограничений задачи.

3.Находят многоугольник решений.

4.Строят вектор N (c1;c2).

5.	Строят	линию уровня	c1x1 c2x2 h,	проходящую через
6.	многоугольник решений.
	Передвигают линию уровня c1x1 c2x2 h по направлению вектора N ,
	в результате чего находят точку (точки), в которой целевая функция
	принимает максимальное значение, и против направления вектора N , в
	результате чего находят точку (точки), в которой целевая функция
	принимает	минимальное	значение,	либо	устанавливают
7.	неограниченность сверху (снизу) функции на множестве планов.
	Определяют координаты точки максимума (минимума) функции и
	вычисляют значение целевой функции в этой точке.

Решим графическим методом задачи использования сырья и составления рациона, приведенные в §1.

1.Задача использования сырья.

Найти f 30x1 20x2 max

	2x1			3x2				21
	x		x		2	8
при		1						(*)
	2x			10
		1
	x		0,x				2	0.
		1

Построим многоугольник решений. Для этого в системе координат x1Ox2 на плоскости изобразим прямые:

Для каждого неравенства (*) определим полуплоскость решений. Для этого возьмем любую точку из любой полуплоскости, например (0,0), и

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

OABCD. Для построения прямой	f 30x1	20x2 строим радиус-вектор
N (30;20) 10(3;2). Проведём	прямую,	перпендикулярную ему.

Построенную прямую перемещаем параллельно самой себе в направлении вектора N . Из рисунка видно, что эта прямая достигает максимальное значение в точке C. Точка C лежит на пересечении прямых l2 и l3. Для определения ее координат решим систему уравнений:

x1 x2 8

2x1 10

Оптимальный план задачи: x1 5; x2 3.

Подставляя в целевую функцию значения x1 и x2, получаем:

fmax 30 5 20 3 210.

Таким образом, для того, чтобы получить максимальную прибыль в размере 210 денежных единиц, необходимо запланировать производство 5 ед. продукции Р1 и 3 ед. продукции Р2 .

2.Задача составления рациона.

Найти f 4x1 x2 min

2x1 x2 4

при x1 3x2 6x1 1

x1 0, x2 0.

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

Получили неограниченную сверху многоугольную область с угловыми точками A,B,C.

Построим вектор N (4;1)		и прямую f	4x1 x2 ,	перпендикулярную
ему. Перемещаем	эту прямую	против направления вектора N			до самой
последней точки	открытого многоугольника		A,B,C. В	точке	A целевая

функция примет минимальное значение. Точка A лежит на пересечении прямых l1 и l3. Для определения ее координат, решим систему уравнений:

2x1 x2 4x1 1

Имеем: x1 1,x2 2. Подставим в целевую функцию и получим

fmin 4 1 1 2 6

Для того, чтобы обеспечить минимум затрат - 6 денежных единиц в день, необходимо дневной рацион составить из 1 кг. корма I и 2 кг. корма II.

				Упражнения
	Решить графическим методом задачи:
3.1. f x1 3x2 max		3. 2.	f x1 4x2 min			3.3. f	x1 x2 max
x1 x2 2		x1 2				2x1 4x2 8
			2x2 2
x1 2x2 4		x1				3x1 2x1 0
	2x2 8		2				3x2 3
x1		x2				x1
x 6		x x		2	3	x 1
1		1				1
	0, x2 0		0,		x2 0		0
x1		x1				x2

3.4. f x1 2x2 min 3.5. f 2x1 5x2 max

x1 x2 0								4x1 3x2 12
2x x				2	3			x 2x					2	8
	1							1
x x			2	1				0 x	1		6
	1
x 0,					x	2	0	0 x		2		5
	1
3.6. f x1	x2	min 3.7.						f x1 4x2 max						3.8. f 2x1 10x2 min

x1 x2 1				x1 x2 3 0					x1 5x2 5
x x		2	1	x 2x			2	2 0	x x		2	6
1				1					1
	x2		1			x2 1 0				x2 0
x1				x1					x1
0 x 2				x	2	4 0			0 x 5
	1									1
			2			0,		x2 0		0
0 x2				x1					x2