Posobie1

Таким образом,

x11 60 30 , x12 50 30 , x13 0, x21					30 , x22 30 30 , x23 70. По-
лученный ответ запишем в виде матрицы
		60 30		50 30	0		0 1.
	X опт					, где
			30	30 30	70
При таком плане перевозок				суммарный		доход	будет максимальным,

а именно Lmax = 1 790.

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

максимальным. Укажем некоторые из этих способов:
60		50	0			50	60	0			45	65	0			30		80	0
					;					;					;					.
	0	30	70				20	70				15	70				30	0	70
						10					15

Первый из этих способов получен при λ = 0, второй — при λ = 1/3, третий — при λ = 0,5, четвертый — при λ = 1.

Задача 3. АООТ «Прицеп» выпускает дачный инвентарь, а именно грабли, мотыги и лопаты. При этом для изготовления одного изделия используется сталь-65Г в количестве 1,7, 0,8 и 1,5 кг соответственно. Запасы стали-65Г на складе составляют 1,3 т на месяц. Анализ рынка сбыта показал, что за год АООТ «Прицеп» реализует не более 20 тыс. грабель, 15 тыс. мотыг и 1 тыс. лопат, причем выпуск одного изделия приносит доход 36, 24 и 40 руб. соответственно. Требуется составить план производства, обеспечивающий АООТ «Прицеп» наибольший доход.

Решение. Обозначим через x1, x2 и x3 соответственно количество грабель, мотыг и лопат (шт.), выпускаемых АООТ «Прицеп» в месяц. Составим математическую модель задачи, выразив ограничения сверху по ежемесячному выпуску продукции в целых числах. Для этого поделим 20 000, 15 000 и 1 000 на 12 и округлим до ближайшего целого числа.

Целевая функция имеет вид:

L(x1, x2, x3) = 36x1 + 24x2 + 40x3 → max,

при ограничениях:

		x1	1 667,
		x2	1 250,
		x3 83,
1,7x		0,8x	2	1,5x	3	1 300,
	1

x1 0, x2 0, x3 0.

Введем в пространстве прямоугольную систему координат Ox1x2x3. Геометрическое место точек, координаты которых удовлетворяют системе ограничений, т. е. ОДР, образует выпуклый многогранник. Грани этого

41

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

зана поверхность (линия) уровня L0 = 12 000, и вектор 10 С , перпендикулярный ей. Вектор 10 С изображен вместо вектора С для удобства, так

как вектор С на этом чертеже будет слишком мал. Будем перемещать эту линию уровня в сторону возрастания целевой функции, т. е. по направле-

нию вектора 10 С . Из взаимного расположения ОДР и линий уровня ясно, что наибольшего значения целевая функция будет достигать в наиболее «выступающих», т. е. удаленных от начала координат точках ОДР: A, B, C или D. Найдем их координаты и значения целевой функции в этих точках. Точка А имеет координаты x1, x2 и x3, удовлетворяющие системе

1,7x 1 300,

x 0,

2

x 0,

31

откуда получаем (в целых числах) x1 = 765 и L1 = 36x1 + 24x2 + 40x3 = 27 540. Аналогично, координаты точки В удовлетворяют системе

1,7x 1,5x 1300,

x 0,

2

83,

x31 3

откуда x1 = 691 и L2 = 36x1 + 24x2 + 40x3 = 28 196. Координаты точки С удовлетворяют системе

1,7x 0,8x 1,5x 1 300,

x 1 250,

2

x 83,

31 2 3

откуда x1 = 103 и L3 = 36x1 + 24x2 + 40x3 = 37 028. Координаты точки D удовлетворяют системе

1,7x 0,8x 1 300,

x 1 250,

2

x 0,

31 2

42

x3

867

		L3=37 028
10	С
		L1=27 540
83	L0=12 000	C
			1 250	1 625
		D		x2
B

765 A

x1	Рис. 17. Графическое решение задачи с тремя переменными

откуда x1 = 176 и L4 = 36x1 + 24x2 + 40x3 = 36 336. Следовательно, наибольшего значения целевая функция достигает в точке С. Оптимальным будет выпуск (в целых числах) 103 грабель, 1 250 мотыг и 83 лопат в месяц. При этом прибыль составит 37 028 руб. На рис. 17 изображены поверхности уровня L1 и L3. Поверхности L2 и L4 находятся очень близко к указанным и не изображены, чтобы не загромождать чертеж.

6. Применение графического метода при проведении экономического анализа ЗЛП (на примере задачи регионального уровня)

При решении задач линейного программирования часто важен не только полученный результат, но и его экономический анализ: понимание взаимосвязи конкретных производственных факторов; значимость ограничительных условий, влияющих на эффективность получаемых решений.

Задача 4. АООТ «Прицеп» выпускает изделия двух типов: задвижки и тиски слесарные. При этом используется сырье четырех видов. Расход сырья задан в таблице 4.

43

				Таблица 4
Изделия		Сырье, кг
	Сталь-45	Чугун	Бронза	Сталь-3
Задвижки	3	0	2	0,5
Тиски слесарные	4	1	0	2

Суточные запасы стали-45 составляют 322 кг, чугуна — 70 кг, бронзы — 180 кг, стали-3 — 100 кг. Розничная цена одной задвижки равна 60 руб., тисков — 100 руб.

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

Решение. Обозначим через x1 и x2 суточные объемы выпуска задвижек (шт.) и слесарных тисков (шт.) соответственно. Составим математическую модель задачи.

Целевая функция имеет вид:

L(X) = 60x1 +100x2 → max,

при ограничениях:

3x1 4x2 322				(ограничение по стали - 45),
	x2 70			(ограничение по чугуну),
	2x1 180			(ограничение по бронзе),
	0,5x 2x	2	100	(ограничение по стали - 3),
	1

x1 0, x2 0.

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

ислесарных тисков должно находиться внутри области допустимых решений OABDE (рис. 18), являющейся «плацдармом» для дальнейших действий руководителей АООТ «Прицеп». Для отыскания точки, в которой находится оптимальное решение, строим вектор, показывающий на-

правление самого быстрого изменения целевой функции (это вектор С с координатами (60; 100)), и линию уровня L0, перпендикулярную указан-

ному вектору. Перемещая прямую L0 по направлению вектора С , найдем точку выхода линии уровня из области допустимых решений. Ею является точка B, координаты которой — (61; 34,75) — определяются как пересечение прямых, заданных уравнениями 3x1 + 4x2 = 322 и 0,5x1 + 3x2 = 100.

44

x2		2x1 = 180
	С
			x2 = 70
A
	B
		D	0,5x1 + 2x2 = 100
О		E	3x1 + 4x2 = 322
	L0			x1

Рис. 18. ОДР и целевая функция в задаче с ограничениями по ресурсам

Следовательно, Lmax= L(B) = 60 ∙ 61 + 100 ∙ 34,75 = 7 135. Таким образом, АООТ «Прицеп» должно выпускать в сутки 61 задвижку и 34,75 слесарных тисков. С этими данными по выпуску выручка от реализации составит 7 135 руб. Если выпускать в сутки 34,75 тисков нельзя, то этот результат можно интерпретировать так: оптимальным является выпуск 34,75 ∙ 4 = 139 тисков за 4 суток.

Экономический анализ. Определим, как влияет на оптимальное решение увеличение или уменьшение запасов исходного сырья. Для анализа задачи примем, что неравенства системы ограничений могут быть активными или пассивными. Если прямая, являющаяся границей множества решений некоторого неравенства, проходит через точку, в которой находится оптимальное решение, то это неравенство представляет собой активное ограничение. В противном случае неравенство относится к пассивному ограничению. Если ограничение активное, то соответствующий ресурс является дефицитным, так как он используется полностью. Если ограничение пассивное, то оно имеется на предприятии в избытке.

Рассмотрим увеличение ресурса правой части ограничения 3x1 + + 4x2 322 по стали-45 (рис. 19). При перемещении прямой 3x1 + 4x2 = 322 параллельно самой себе до точки F(90; 27,5) — точки пересечения прямых 0,5x1 + 3x2 = 100 и 2x1 = 180 — ограничение x1 + 4x2 322 будет оставаться активным, при этом, если АООТ «Прицеп» будет выпускать в сутки 90 задвижек и 27,5 слесарных тисков, величина выручки составит L(90; 27,5) = =8 150 (руб.), что на 1 015 руб. выше реальной выручки. Это может произойти за счет изменения запасов стали-45 (см. описанное выше перемещение

45

прямой 3x1 + 4x2 = 322 до точки F). Для такой выручки предельно допустимый запас стали-45 нужно увеличить до 3 · 90 + 4 · 27,5 = 380 (кг).

x2			2x1 = 180
		С
				x2 = 70
A		B
			F
			D	0,5x1 + 2x2 = 100
О			E	3x1 + 4x2 = 322
		L0				x1
		Рис. 19. Увеличение ресурса по стали-45
Рассмотрим		увеличение ресурса		правой	части ограничения
0,5x1+2x2	100 по стали-3 (рис. 20).
x2			2x1 = 180
		С
	G
				x2 = 70
A		B
			D	0,5x1 + 2x2 = 100
О			E	3x1 + 4x2	= 322	x1
		L0

Рис. 20. Увеличение ресурса по стали-3

При перемещении прямой 0,5x1 + 2x2 = 100 параллельно самой себе до точки G(14; 70) — точки пересечения прямых 3x1 + 4x2 = 322 и x2 = 70 — ограничение 0,5x1 + 2x2 100 будет оставаться активным. При этом величина выручки составит L(14; 70) = 7 840 (руб.), что на 705 руб. выше

46

реальной. Это может произойти за счет изменения запасов стали-3 (см. перемещение прямой 0,5x1 + 2x2 = 100 параллельно самой себе до точки G). Для такой выручки предельно допустимый запас стали-3 нужно увеличить до величины 0,5 · 14 + 2 · 70 = 147 (кг).

Рассмотрим возможность изменения правой части пассивного ограничения 2x1 180 по бронзе (рис. 21).

x2		2x1 = 180
	С
			x2 = 70
A	B
		D	0,5x1 + 2x2 = 100
О		E	3x1 + 4x2	= 322	x1
	L0

Рис. 21. Уменьшение ресурса по бронзе

Прямую 2x1 = 180 можно перемещать параллельно самой себе влево, не изменяя величины реального дохода, до точки B(61; 34,75). При этом предельно допустимый суточный запас бронзы можно уменьшить до зна-

чения 2 · 61 = 122 (кг).

x2		2x1 = 180
	С
			x2 = 70
A	B
		D		0,5x1 + 2x2 = 100
О		E	3x1	+ 4x2	= 322	x1
	L0

Рис. 22. Уменьшение ресурса по чугуну

47

Теперь рассмотрим возможность изменения правой части пассивного ограничения x2 70 по чугуну (рис. 22). Не изменяя оптимального решения, прямую x2 = 70 можно перемещать параллельно самой себе до точки B(61; 34,75). Это означает, что предельно допустимый суточный запас чугуна можно уменьшать до 34,75 кг.

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

			Изменение			коэффициентов
	x2		целевой		функции		оказывает
			влияние на наклон линии уровня,
		С	уравнение которой записывается
			в общем виде как c1x1 + c2x2 =
			= const. Оптимальное решение
			будет	оставаться неизменным,
	A		если	угловой		коэффициент k
		B	линии уровня, проходящей через
			точку B, не будет выходить за
		+	границы отрезка [k1; k2], где k1
		D L0	и k2 — угловые коэффициенты
			прямых BD и AB соответственно.
	О	E x1	Таким образом, –3/4 ≤ k ≤ –1/4
			(рис. 23).
		Рис. 23. Изменение целевой функции	Рассмотрим изменение коэф-
			фициента		целевой		функции

у переменной x1 (коэффициент у x2 оставим без изменения). Имеем

–3/4 ≤ –c1/100 ≤ –1/4 или 25 ≤ c1 ≤ 75.

Таким образом, оптимальное решение не изменится, если розничная цена одной задвижки будет лежать в диапазоне от 25 до 75 руб., в этом случае выручка предприятия составит от 5 000 до 8 050 руб.

Теперь рассмотрим изменение коэффициента целевой функции у переменной x2, оставляя коэффициент у x1 неизменным. В этом случае –3/4 ≤ –60/c2 ≤ –1/4, или 80 ≤ c2 ≤ 240. Следовательно, оптимальное решение не изменится, если розничная цена одних слесарных тисков будет лежать в диапазоне от 80 до 240 руб. В этом случае выручка АООТ «Прицеп» может составить от 6 440 до 12 000 руб.

48

7. Упражнения

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

1. L = x1 + 2x2 → max	2. L = x1 – 2x2 → min
x1 + x2 ≤ 1,	x1 – x2 ≤ 1,
–x1 + x2 ≥ –1,	x1 + x2 ≥ 2,
x1 ≥ 0, x2 ≥ 0.	x1 – 2x2 ≤ 0,
	x1 ≥ 0, x2 ≥ 0.
3. L = 2x1 + 3x2 → min	4. L = x1 + 3x2 → max
–3x1 – 2x2 ≤ –6,	x1 – x2 ≤ 1,
x1 + 4x2 ≥ 4,	x1 – x2 ≥ 0,
x1 ≥ 0, x2 ≥ 0.	2x1 + x2 ≤ 2,
	x1 ≥ 0, x2 ≥ 0.
5. L = 2x1 + 3x2 → min	6. L = x1 + 2x2 → max
x1 + x2 ≤ 4,	x1 – 2x2 ≤ 1,
3x1 + x2 ≥ 4,	–x1 + x2 ≥ –1,
–x1 – 5x2 ≤ –4,	x1 ≥ 0, x2 ≥ 0.
0 ≤ x1 ≤ 3, 0 ≤ x2 ≤ 3.
7. L = x1 + x2 → min	8. L = 2x1 + 3x2 → max
x1 + x2 ≤ 3,	x1 + x2 ≤ 2,
x1 + x2 ≥ 0,	x1 + x2 ≥ 1,
x1 – x2 ≤ 0,	x1 ≥ 0, x2 ≥ 0.
x1 – x2 ≥ –1
0≤ x1 ≤ 1, 0 ≤ x2≤ 2.
9. L = 2x1 – 3x2 → min	10. L = x1 + x2 → max
–4x1 + 5x2 ≤ 20,	x1 + 2x2 ≤ 10,
2x1 + x2 ≥ 6,	x1 + 2x2 ≥ 2,
5x1 – x2 ≤ 45,	2x1 + x2 ≤ 10,
x1 – x2 ≤ 6, x1 ≥ 0, x2 ≥ 0.	x1 ≥ 0, x2 ≥ 0.

11. АООТ «Прицеп» производит совковые и штыковые лопаты. Для их изготовления требуется листовой металл и древесина. Для изготовления одной совковой лопаты требуется 0,04 листа металла и 0,004 м3 древесины, для изготовления одной штыковой лопаты — 0,02 листа металла и 0,004 м3 древесины. Розничная цена одной совковой лопаты 60 руб., а штыковой — 50 руб. Изучение рынка сбыта показало, что спрос на штыковые лопаты превышает спрос на совковые не более чем на 3 тыс. штук в месяц. Кроме того, спрос на совковые лопаты не превышает 15 тыс. штук в месяц. Сколько лопат каждого вида должно изготовлять АООТ «Прицеп» в месяц, если оно располагает 300 листами металла и 60 м3 древесины и хочет получить максимальный доход от реализации своей продукции?

49

12.АООТ «Прицеп» выпускает 4,5-тонные прицепы и кормораздатчики «Ванюша» по цене 40,3 и 74,3 тыс. руб. соответственно. По результатам маркетинговых исследований спрос на изделия первого вида составляет не менее 1 200 ед. в год. Для производства прицепов используются сталь и чугун, запасы которых на предприятии составляют 25 000 и 4 500 т соответственно. Для изготовления 1 тыс. прицепов норма расхода стали составляет 1 615 т, а чугуна — 385 т. Для изготовления 1 тыс. кормораздатчиков расходуется: стали — 2 022 т, чугуна — 478 т. Себестоимость прицепов — 34,66, а кормораздатчиков — 63,9 тыс. руб. Найти оптимальное решение по производству прицепов и кормораздатчиков, чтобы: а) количество выпускаемых изделий было максимальным; б) выручка от выпускаемых изделий была максимальной; в) себестоимость выпускаемых изделий была минимальной.

13.Ремонтный завод «Хоперский» выпускает насосы двух типов: топливные и водяные. В комплектацию этих изделий входят четыре основных вида деталей: корпус, платик, манжета, шестерня. Для изготовления топливного насоса требуется один корпус, четыре платика, четыре манжеты и одна шестерня, для изготовления водяного насоса — 1, 2, 4 и 3 комплектующих деталей соответственно. От реализации одного топливного насоса завод имеет прибыль 50 руб., а от одного водяного — 200 руб. На складе завода имеется следующий запас комплектующих: корпусов — 6 штук, платиков — 8 штук, манжет — 12 штук, шестерней — 9 штук. Составить план производства, обеспечивающий заводу наибольший доход.

14.Провести экономический анализ задач 11—13.

15.Для производства двух видов кормовых биодобавок можно использовать витамины трех групп. При этом на изготовление биодобавки

«Телец» расходуется 16 кг витамина А, 8 кг витамина В1 и 5 кг витамина Е. На изготовление биодобавки «Овен» расходуется 4 кг витамина А, 7 кг

витамина В1 и 9 кг витамина Е. На складе фирмы имеется всего 784 кг витамина А, 552 кг витамина В1 и 567 кг витамина Е. От реализации добавки «Телец» фирма имеет прибыль 4 тыс. руб., а от добавки «Овен» — 7,2 тыс. руб. Определить максимальную прибыль от реализации обеих биодобавок.

16.Фирма выпускает два набора удобрений «Купрум-I» и «КупрумII». В «Купрум-I» входит 3 кг азотных, 1 кг калийных и 1 кг медных удобрений. В «Купрум-II» — 1 кг азотных, 2 кг калийных и 6 кг медных удобрений. После осушения торфяных болот для внесения в почву потребовалось по меньшей мере 9 кг азотных, 8 кг калийных и 12 кг медных удобрений. «Купрум-I» стоит 4 усл. ден. ед., а «Купрум-II» — 6 усл. ден. ед. Какие и сколько наборов удобрений необходимо внести, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

50