ЭМиКМ (пособие)

36

Объемы	1856	31,648	641,6	4807
ресурсов

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

Решение. Составим экономико-математическую модель задачи. Обозна- чим через x1 и x2 − число единиц запланированных к производству столов и диванов соответственно. Cуммарная прибыль от реализации всей выпущенной продукции представляется целевой функцией, которая имеет вид:

Z(X ) = 36,27x1 + 6,7x2.

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

4x2 £1856.

На запасы пиломатериалов:

0,032x1 + 0,06x2 £ 31,648.

На запасы древесностружечной плиты (ДСтП):

1,6x1 £ 641,6.

На объем технологического оборудования:

11,4x1 + 3,8x2 £ 4807.

Кроме того, по смыслу задачи

x1 ³ 0, x2 ³ 0.

Таким образом, экономико-математическая модель задачи примет вид:

найти такой план выпуска столов и диванов X = (x1, x2 ), при котором

достигается максимум целевой функции

Z(X ) = 36,27x1 + 6,7x2 ® max

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

ì4x2 £1856,
ï
ï0,032x1 + 0,06x2 £ 31,648,
ï
í1,6x1 £ 641,6,
ï11,4x + 3,8x		2	£ 4807,
ï	1
ï	³ 0, x2 ³ 0.
îx1

Задача №5. Фирма выпускает три вида изделий. В процессе производства используются три технологические операции. На рис. 5 показана технологиче-

37

ская схема производства изделий 1-го, 2-го и 3-го видов. При изготовлении из- делия 2-го вида технологическая операция 2 не выполняется, а при производст- ве изделия 3-го вида используются только технологические операции 1 и 2. В прямоугольниках, представляющих операции технологического маршрута, ука- заны длительности этих операций при изготовлении изделий каждого типа.

	Операция 1			Операция 2		Операция 3
	1	мин./изд.		3 мин./изд.		1	мин./изд.		Изделие 1
	2	мин./изд.				4	мин./изд.		Изделие 2

1 мин./изд. 2 мин./изд. Изделие 3

Рис. 5 Технологическая схема производства изделий 1-го, 2-го и 3-го видов

Так как эти технологические операции используются фирмой и для дру- гих производственных целей, фонд рабочего времени, в течение которого опе- рации 1, 2 и 3 могут быть применены для производства рассматриваемых изде- лий, ограничен следующими предельными значениями (в сутки):

для операции 1 − 430 мин., для операции 2 − 460 мин., для операции 3 − 420 мин.

Прибыль от продажи одного изделия 1-го, 2-го и 3-го видов составляет соответственно 3, 2 и 5 рублей соответственно. Каков наиболее выгодный су- точный объем производства каждого вида изделия?

Решение. Построим экономико-математическую модель задачи. Обозна- чим x1− количество производимых изделий 1-го вида, x2 − количество произ- водимых изделий 2-го вида, x3 − количество производимых изделий 3-го вида. Тогда математическая формулировка задачи примет вид:

Z(X ) = 3x1 + 2x2 + 5x3 → max (величина прибыли за сутки)

при следующих ограничениях на предельное время использования операций в течение суток:

38

ì1x1 + 2x2 +1x3 £ 430, ïí3x1 + 0x2 + 2x3 £ 460,

ïî1x1 + 4x2 + 0x3 £ 420

и при выполнении условий

x1 ³ 0, x2 ³ 0, x3 ³ 0.

Общая постановка задачи планирования производства

Рассмотренную выше задачу можно легко обобщить на случай выпуска n видов продукции с использованием m видов ресурсов [16].

Обозначим x j ( j = 1,2,...,n) − число единиц продукции Pj , запланиро- ванной к производству; bi (i =1,2,...,m) − запас ресурса Si ; aij − число еди-

ниц ресурса Si , затрачиваемого на единицу продукции Pj (числа aij часто на-

зывают технологическими коэффициентами); c j − прибыль от реализации еди-

ницы продукции Pj .

Тогда экономико-математическая модель задачи планирования производ-

ства примет вид: найти такой план X = (x1, x2 ,..., xn ) выпуска продукции,

удовлетворяющий системе неравенств

ìa x + a x

2

+ ... + a

x

n

£ b ,

ï 11 1

12

1n

1

ïa21x2 + a22x2 + ... + a2n xn £ b2,

í

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

ï

ïa

m1

x

m

+ a

m2

x

2

+ ... + a

mn

x

n

£ b .

î

m

и условию

x1 ³ 0, x2 ³ 0, …, xm ³ 0 ,

при котором функция Z(X ) принимает максимальное значение:

Z(X ) = c1x1 + c2 x2 +... + cn xn ® max.

(2.6)

(2.7)

(2.8)

Ограничения (2.6) и (2.7) могут быть представлены в сокращенной фор-

ме:

n
åaij xi £ bi , xi ³ 0 (i =1,2,...,m).	(2.9)

j =1

39

Примечание 1. Неравенства, представленные в системе (2.6), называются функциональными ограничениями, в условии (2.7) − прямыми, или тривиаль- ными.

Примечание 2. Задачи линейного программирования могут быть условно разбиты на две группы: одноиндексные и двухиндексные − по количеству ин- дексов у переменных решения ( xi и xij ) [18]. В этом смысле все приведенные

выше задачи являются одноиндексными. Двухиндексные задачи рассмотрены ниже.

Общая постановка задачи об использовании мощностей (загрузке оборудования)

Предприятию задан план производства продукции по времени и номенк- латуре: требуется за время T выпустить n1, n2 ,...,nk единиц продукции

P1, P2 ,..., Pk . Продукция производится на станках S1, S2 ,..., Sm , для каждого из которых известны производительность aij (т.е. число единиц продукции Pj ,

которое можно произвести на станке Si за единицу времени) и затраты bij на изготовление продукции Pj на станке Si в единицу времени.

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

Экономико-математическая модель задачи об использовании мощностей

Составим экономико-математическую модель задачи [9]. Обозначим xij −

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

(i =1,2,...,m; j = 1,2,...,k).

Так как время работы каждого станка ограничено и не превышает T , то справедливы следующие неравенства:

40

ìx	+ x + ...	+ x	≤ T,
ï 11	12	1k
ïx21 + x22 + ... + x2k £ T,				(2.10)
í.......................................
ï
ï	+ xm2 + + xmk £ T.
îxm1

Для выполнения плана выпуска по номенклатуре необходимо, чтобы вы- полнялись следующие равенства:

ìa x + a

21

x

21

+ ... + a

m1

x

m1

= n ,

ï

11 11

1

ïa12 x12 + a22x22 + ... + am2 xm2 = n2,

í

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

ï

ïa x

+ a

2k

x

2k

+ ... + a

mk

x

mk

= n .

î

1k 1k

k

Кроме того, по условию задачи

xij ³ 0 (i =1,2,...,m; j = 1,2,...,k).

(2.11)

(2.12)

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

Z(		) = b11x11 + b12 x12 + ...+ bmk xmk → min .	(2.13)
	X

Экономико-математическая модель задачи об использовании мощностей (загрузке оборудования) примет вид: найти такое решение

X = (x11, x12,..., xmk ), удовлетворяющее системам (2.10) и (2.11) и условию

(2.12), при котором целевая функция (2.13) принимает минимальное значение.

Задача №6. На двух автоматических линиях выпускают аппараты трех типов: А, B, C. Другие данные условия задачи приведены в таблице 2.4.

Таблица 2.4

Тип аппа-	Производительность ра-		Затраты на работу линий,
рата	боты линий, шт./сут.		руб./сут.			План, шт.
	1	2	1		2
A	4	3	400		300	20
B	6	5	100		200	40
C	8	2	300		400	50

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

Решение. Составим экономико-математическую модель задачи. Обозна- чим через x1a , x1b и x1c − время, в течение которого 1-я линия будет занята вы-

41

пуском аппаратов A, B и C соответственно. Аналогично, обозначим через x2a , x2b и x2c − время, в течение которого 2-я линия будет занята выпуском

аппаратов A, B и C соответственно.

Так как время работы каждой линии ограничено 10-ю сутками, то спра- ведливы следующие неравенства:

ìx	+ x	+ x	≤10,		(2.14)
í 1a	1b	1c		10.
îx2a + x2b + x2c £

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

ì4x1a + ïí6x1b + ïî8x1c +

3x2a ³ 50,

5x2b ³ 40,	(2.15)
2x2c ³ 50.

Кроме того, по смыслу задачи

		x1a ³ 0, x1b ³ 0, x1c ³ 0,	(2.16)
		x2a ³ 0, x2b ³ 0, x2c ³ 0.
Затраты на производство планового количества аппаратов A, B и C выра-
жаются следующей целевой функцией:
Z(		) = 400x1a +100x1b + 300x1c + 300x2a + 200x2b + 400x2c . (2.17)
	X

Таким образом, экономико-математическая модель задачи примет вид:

найти такое решение X = (x1a , x1b , x1c , x2a , x2b , x2c ), удовлетворяющее системам (2.14) и (2.15) и условию (2.16), при котором целевая функция (2.17) принимает минимальное значение:

Z(X ) = 400x1a +100x1b + 300x1c + 300x2a + 200x2b + 400x2c ® min .

Задача №7. Промышленная фирма производит изделие, представляющее собой сборку из трех различных узлов. Эти узлы изготавливаются на двух заво- дах. Из-за различий в составе технологического оборудования производитель- ность заводов по выпуску каждого из трех видов узлов неодинакова. В таблице 5 содержатся исходные данные, характеризующие как производительность за- водов по выпуску каждого из узлов, так и максимальный суммарный ресурс времени, которым располагает каждый из заводов для производства этих узлов.

Таблица 5

Производительность, узел/час

42

Завод	Максимальный недель-	Узел 1	Узел 2	Узел 3
	ный фонд времени, час
1	100	8	5	10
2	80	6	12	4

Идеальной является такая ситуация, когда производственные мощности обоих заводов используются таким образом, что в итоге обеспечивается выпуск одинакового количества каждого из видов узлов. Однако, этого трудно добить- ся из-за различий в производительности заводов. Более реальная цель состоит, по-видимому, в том, чтобы максимизировать выпуск изделий, что по существу эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или двум видам узлов.

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

Решение. Возможный объем выпуска каждого из трех видов узлов зави- сит от того, какой фонд времени выделяет каждый завод для их изготовления. Обозначим xij − недельный фонд времени (в часах), выделяемый на заводе i

для производства узлов вида j . Тогда объемы производства каждого из трех комплектующих узлов равны:

8x11 + 6x21 (узел 1), 5x12 +12x22 (узел 2), 10x13 + 4x23 (узел 3).

Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделий должно быть равно количе- ству комплектующих узлов, объем производства которых минимален. Если, на- пример, объем производства двух заводов составляет 100, 112 и 108 соответст- вующих узлов, то количество конечных изделий будет равно min{100,112,108} = 100. Поэтому количество конечных изделий можно вы- разить через число комплектующих узлов следующим образом:

min{8x11 + 6x21,5x12 +12x22 ,10x13 + 4x23}.

Условия рассматриваемой задачи устанавливают ограничения только на фонд времени, которым располагает каждый завод. Таким образом, математи- ческую модель можно представить в следующем виде:

Z(X ) = min{8x11 + 6x21,5x12 +12x22 ,10x13 + 4x23} → max

	43
при ограничениях
ì	+ x12 + x13 £100	(завод	1),
ïx11
íx21 + x22 + x23 £ 80		(завод	2),
ïx	³ 0,(i =1,2; j =1,2,3).
î ij

Данная модель не является линейной, но она может быть приведена к ли- нейной форме с помощью простого преобразования. Пусть

y = min{8x11 + 6x21,5x12 +12x22 ,10x13 + 4x23}.

Тогда целевая функция

Z(X ) = y → max

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

ì8x11 + 6x21 ³ y,

ïï5x12 +12x22 ³ y, íï10x13 + 4x23 ³ y,

ïîy ³ 0.

Окончательно математическая модель задачи запишется в виде:

Z(X ) = y → max

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

ì
ï8x11 + 6x21 - y ³ 0,
ï5x12 +12x22 - y ³ 0,
ï10x + 4x					- y ³ 0,
ï		13		23
		+ x12		+ x13 £100,
íx11
ïx	21	+ x	22	+ x	23	£ 80,
ï
ïx		³ 0,(i =1,2; j =1,2,3),
ï ij
îy ³ 0.

Задачи о раскрое материала

Задачи о раскрое материала являются частным случаем общей задачи планирования производства. Ниже рассмотрены две задачи, одна из которых посвящена распилу бревен [9], другая − раскрою ДСтП [10]. Третья задача, по- священная раскрою листов фанеры на комплектные заготовки, предназначена для самостоятельного решения [19].

(i = 1, 2,3, 4)

44

Задача №8. Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотно- шении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план рас- пила, обеспечивающий максимальное число комплектов.

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

				Таблица 2.6
Способ распила i		Число получаемых брусьев длиной, м
	1,2		3,0	5,0
1	5		−	−
2	2		1	−
3	−		2	−
4	−		−	1

Обозначим xi − число бревен, распиленных i -м способом

и x − число комплектов брусьев. Учитывая, что все бревна должны быть рас- пилены, а число брусьев каждого размера должно удовлетворять условию ком- плектности, экономико-математическая модель задачи примет вид: найти та-

кой план раскроя бревен X = (x1, x2 , x3, x4 ), при котором количество

полученных комплектов будет максимальным

Z(X ) = x → max

и выполняются ограничения

ìx		+ x	2	+ x + x	4	= 195,
ï 1				3
ï5x1 + 2x2 = 2x,
ï		+ 2x3 = x,
íx2
ïx	4	= 3x,
ï
ï		³ 0		(i = 1, 2,3, 4).
îxi

Задача №9. ДСтП размером 350×175 см подлежат раскрою на заготовки двух типоразмеров: 200×70 см и 160×90 см1. Требуется получить не менее 300

1 Типоразмеры плит и заготовок обычно указываются в миллиметрах, т.е. 3500×1750 мм, 2000×700 мм и 1600×900 мм. В задаче использованы более крупные единицы измерения − сантиметры, чтобы облегчить некоторые численные расчеты, которые придется выполнять «вручную».

45

заготовок первого и не менее 400 заготовок второго типоразмера. При этом суммарное (по площади) количество отходов должно быть минимально.

Решение. Рассмотрим все возможные варианты раскроя плит (рис. 6).

	350			160	160
70			90
70		160	175
			70	200
	200	90	a)		б)
90	90	90

160

в)

Рис. 6 Варианты раскроя ДСтП на заготовки

На рисунке 5(a) показан вариант раскроя плиты на две заготовки 1-го и одну заготовку 2-го типоразмера, обеспечивающий площадь отходов

350 ×175 - (2× 200 ×70 +160 ×90) = 61250 - 42400 = 18850 см2.

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

По варианту раскроя, представленному на рисунке 5(б), можно получить одну заготовку 1-го и две заготовки 2-го типоразмера, площадь одходов равна

350 ×175 - (200 ×70 + 2 ×160 ×90) = 61250 - 42800 = 18450 см2.

По варианту раскроя, представленному на рисунке 5(в), можно получить три заготовки 2-го типоразмера с площадью отходов

350×175 - 3×160×90 = 61250 - 43200 =18050 см2.

Для решения задачи следует выяснить, сколько плит надо раскроить по каждому из рассмотренных вариантов при выполнении предъявляемых требо-