pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

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

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

Влесопилении методы линейного программирования широко ис­ пользуются для решения задачи планирования раскроя пиловочного сырья на пиломатериалы. Рассмотрим содержательную постановку и математи­ ческую модель этой задачи.

Влесопильный цех ЛДП поступают бревна, рассортированные на п размерных групп. Известна спецификация пиломатериалов, которые тре­ буется получить в результате раскроя данного объема пиловочного сырья. Задан также набор поставов для раскроя бревен каждой размерной группы. Требуется определить, какой объем бревен следует распилить по каждому из рассматриваемых поставов, чтобы выполнить спецификацию пиломате­ риалов при минимальном расходе пиловочного сырья.

Введем обозначения:

Vk - имеющийся объем бревен к-й размерной группы, к = 1, 2,..., п; Qi - минимально допустимый объем выработки пиломатериалов z-ro сечения, i = 1, 2,..., т (т - общее число сечений выраба­

тываемых пиломатериалов);

xjg - искомый объем бревен к-й размерной группы, распиливаемых по у-му поставу, j = 1, 2,..., Nk (Nk - количество пред­ назначенных к использованию поставов для раскроя бревен к-й размерной группы);

akp - коэффициент объемного выхода пиломатериалов z-ro сечения, полученных при раскрое бревен к-й размерной группы поу-му поставу. Эти коэффициенты являются известными характери­ стиками применяемых поставов.

Сучетом введенных обозначений объем пиломатериалов z-ro сече­

ния, полученных в результате распиливания кубометров бревен к-й раз­ мерной группы поy-му поставу, составляет akjlxkj. Общий объем таких пи­ ломатериалов получают в результате суммирования этого выражения по

* Nk

всем поставам и размерным группам, т. е. Y^Lakjixkj • Поэтому требование

к=1j=]

выработки пиломатериалов z-ro сечения в объеме, не меньшем Qh м3, реа­ лизуется в виде следующего ограничения:

62

n	Ni		(3.52)
H	a , x, >Q„ i = 1, 2,..., m.
A=1 j-\		^kji^kj

Если, кроме того, задан максимально допустимый объем Q* выра­ ботки этих пиломатериалов, то необходимо дополнительно учесть соот­ ветствующее ограничение:

lLiLakjiXlg ^Q*> ' = !> 2»--» т■		(3-53)
к=\j=1
Общий объем бревен к-й размерной группы, распиливаемых по
всем рассчитанным для них поставам, равен, очевидно,	л	**# •
	2

У = 1

Тогда ограничение по ресурсам пиловочного сырья может быть за­ писано в виде

^ x kj<Vk, к = 1 , 2 , ( 3 . 5 4 )

№

Переменные х# должны быть неотрицательны:

Хц>0, к = 1,2.....п; j = l,2,...,Nk.

(3.55)

В качестве критерия оптимальности можно принять минимум рас­ хода сырья. Соответствующая целевая функция запишется в виде

п Nk	(3.56)
£ £ * * ,-> min.
к=\>1

Вместо этого критерия можно рассмотреть критерий минимума от­ ходов сырья при его раскрое. Обозначим через сщкоэффициент объемного выхода пиломатериалов при распиливании бревен к-й размерной группы по7-му поставу. Его величина равна

Ckj ~ lLakji j

/=1

где rrij - число сечений пиломатериалов, вырабатываемых с использовани­ ем 7-го постава.

Тогда коэффициент объемного выхода отходов для этого же поста­ ва равен

mj

	i - ckj=i - ' L akn-
	Ы
Целевая функция, реализующая критерий минимума отходов сырья,
примет вид
т	-Сц )ху ^ ипт .	(3.57)

к=\у=1

Совокупность соотношений (3.52) - (3.56) или (3.52) - (3.55), (3.57) - это задача линейного программирования, являющаяся математиче­ ской моделью задачи планирования раскроя пиловочного сырья.

Предположим теперь, что планируется раскрой пиловочного сырья с учетом его качества, а в спецификации на выработку пиломатериалов на­ ряду с их сечениями указывается и требуемая сортность. В этом случае бревна сортируют на размерно-качественные группы, которые распилива­ ются по различным поставам. Пиломатериалы также различаются не толь­ ко по сечениям, но и по размерно-качественным характеристикам. Ма­ тематическая модель этой задачи формально не отличается от модели пре­ дыдущей. Индекс к теперь будет номером размерно-качественной группы сырья, общее число которых равно п. Для числа размерно-качественных групп пиломатериалов сохраняется обозначение т9а индекс i будет ее но­ мером.

Пример. Решим на ЭВМ задачу планирования раскроя бревен с учетом качест­ ва сырья и пиломатериалов в соответствии с моделью (3.52), (3.54), (3.55), (3.57) [13]. Раскрою подлежат сосновые бревна длиной 5,5 м, диаметром 18...28 см, рассортиро­ ванные на шесть размерных групп. В каждой размерной группе содержится 30 % бре­ вен 2-го и 70 % 3-го сорта. Всего, таким образом, имеется 12 размерно-качественных групп сырья. В табл. 3.12 и 3.13 приведены спецификации сырья и вырабатываемых пиломатериалов соответственно.

Для всех основных сечений пиломатериалов, указанных в спецификации, со­ ставлено и рассчитано на ЭВМ 18 поставов с высотой бруса, равной 0,44...0,75 диамет­ ра вершинного торца бревна. Их краткая характеристика приведена в табл. 3.14. Для бревен различных сортов одного диаметра использован постав одной структуры. Влия­ ние сорта бревен сказывается на посортном выходе пиломатериалов. Объемный же вы­ ход пиломатериалов по поставу из бревен различных сортов считается одинаковым. Это допущение принято из-за отсутствия достоверных данных.

				Т а б л и ц а 3.12
	Диаметр, см		Объем, м3
		2-го сорта	3-го сорта	Всего
	18	30	70	100
	20	45	105	150
	22	45	105	150
	24	60	140	200
	26	60	140	200
	28	60	140	200

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

В табл. 3.15 приведены результаты расчета постава № 1 для раскроя бревен 2-го сорта диаметром 28 см, длиной 5,5 м, объемом 0,41 м3. При расчете посортного выхода пиломатериалов (графы 9 и 10 табл. 3.15) использованы соответствующие нор­

мативы. Непосредственно для решения поставленной задачи из этой таблицы берут следующие данные:

1) посортный выход пиломатериалов каждого сечения, % (графы 9 и 10 для строк 10...12). Поделив эти числа на 100, получим коэффициенты а ^ в ограничениях

(3.52);

2) объем отходов древесины, равный 37,46 % для данного постава, поделенный на 100, он представляет собой соответствующий коэффициент (1 - ) в целевой функ­ ции (3.57) (строка 13).

			Т а б л и ц а 3.13
Номинальные размеры пиломатериалов, мм			Сорт
Толщина	Ширина	Объем, м3
60	150	56,50	0...2
60	150	52,25	3,4
50	125	57,00	0...2
50	125	42,75	3,4
32	125	83,60	0...2
32	125	71,25	3,4
25	Разная	50,00	0...2
25	»	40,00	3,4
19	»	25,00	0...2
19	»	40,0	3,4
16	»	60,00	0...4
Итого		578,35
П р и м е ч а н и е .	Длина пиломатериалов -	5,5 м.
Величины	Vk в правых частях ограничений (3.54) по ресурсам сырья приведе­

ны в графах 2 и 3 табл. 3.12. Значения Q. из ограничений (3.52) на выработку пилома­

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

Рассматриваемая задача была решена на ЭВМ с использованием пакета прикладных программ “Линейное программирование в АСУ” (111Ш ЛП АСУ). Предварительно ее модель (3.52), (3.54), (3.55) и (3.57), содер­ жащая двухиндексные переменные Хф была приведена к стандартному ви­ ду задачи линейного программирования (3.20) - (3.22) с одноиндексными

переменными Xj. Для этого введена сплошная нумерация поставов:

п

j = 1, 2 , . JV, где N = YjNk . Переменная xj означает объем сырья, распили­ ла

ваемого по у-му поставу. Очевидно, что величина Xj принимает ненулевые значения только для тех размерно-качественных групп сырья, которые распиливаются по данномуу-му поставу, и равна нулю для всех остальных групп сырья. Поэтому теперь для записи ограничения по ресурсам сырья, аналогичного неравенству (3.54), приходится ввести новый параметр Ьф Это число равно 1, если по у-му поставу распиливают

		65
Номер постава	Диаметр, см	Сорт
1	28	2
2	28	3
3	26	2
4	26	3
5	24	2
6	24	3
7	22	2
8	22	3
9	20	2
10	20	3
11	18	2
12	18	3
13	28	2
14	28	3
15	26	2
16	26	3
17	24	2
18	24	3
19	22	2
20	22	3
21	20	2
22	20	3
23	18	2
24	18	3
25	28	2
26	28	3
27	26	2
28	. 26	3
29	24	3
30	24	3
31	22	2
32	22	3
33	20	2
34	20	3
35	18	2
36	18	3

				Т а б л и ц а 3.14
		Постав
150	25		19		60		19
1	2		4 ’		3 *		4
150		19		60		19
I	s	4	*	3	’	4
150	19		60		25		19
1	4 *		2 *		2	’	2
150		16		60		16
1		2 *		2	’	4
150	16		60		25		16
1	2	’	Г		2		2
150		60		25		16
1		1	’	2	*	2
125	25		19		50		19
*	2	>	4	5	4	9	4
1
125	25		19		50		19
1	2 *		4 *		4 *		2
125	25		19		50		19
1	2	’	2 *		3	*	4
125		16		50		16
1		4	*	3 ’		2
125		16		50		25
1		2	’	2		2
125		16		50		16
1		2 ’		2	*	2
125	25		19		32		19
9	2	9	4	9	9		4
1					6
125	25		19		32		19
1	2		4 *		6 ’		2
126	25		19		32		19
1	2		2	’	5	’	2
125		16		32		16
1		4	’	4 ’		4
125		16		32		16
1		2 *		4 *		4
125		16		32		16
1		2	’	3	’	2

66

Постав (запись от центра)

	тол­	мм
Число досок	Номинальная	щина доски,
1	2
1	150
1	25
2	19
1	60
2	60
2	19
2	19

			Номинальные
	-	Расстояние от	размеры доски
	полупо	центра поста­
		ва до наруж­
		ной пласти
	шириныРасход мм,става	доски в мм/	мм,Ширина	м,Длина
		долях вер­
		шинного ра­
		диуса
	3	4	5	6
	77	77 / 0,55	233,87	5,5
	29,4	106/0,76	150
	23,25	129,65/0,92	125	4,75
	23,25	152,9/1,09	75	2,0
	30,91	30,91/0,22	150	5,5
	65,42	96,33/0,69	150	5,5
	23,25	119,58/0,85	125	5,5
	23,25	142,83/ 1,02	100	3,25

Итого выход пиломатериалов

Т а б л и ц а 3 .1 5

Полезный выход

общий

в том числе сорта, %

т2	£	0...2-Й	сп
7	8	9	10
0,0412	10,06	6,34	3,72
0,0225	5,51	3,03	2,48
0,0056	1,39	0,695	0,695
0,0495	12,07	7,6	4,47
0,099	24,14	15,21	8,93
0,0261	6,37	3,82	2,55
0,0123	3,01	1,505	1,505

	0,2564	62,55	38,2	24,35
60	0,1485	36,21	22,81	13,4
25	0,0412	10,06	6,34	3,72
19	0,0665	16,28	9,05	7,23
Объем отходов древесины	0,1536	37,46	-	-

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

Ъ ц Х ] < У к , к = 1,2......

п.

(3.58)

м

Пример. Согласно табл. 3.12 имеются бревна 2-го сорта диаметром 28 см в объеме 60 м3. Их распиливают, как видно из табл. 3.14, только по поставам № 1, 13 и 25. Поэтому соответствующее ограничение (3.58) запишется в явном виде:

Xj + хп + х25 < 60.

(3.59)

Вместо ограничений (3.52) и (3.55) и целевой функции (3.57) записывают соотношения аналогичного им следующего вида:

'E aj,x, ZQt, i' = l, 2,..., т-

(3.60)

>1

Xj £0, j = 1, 2,..., N;

(3.61)

Номер	Наименование					Переменные
строки	ограничении		*1	*2	*3	*4	*5
0	Целевая функция		0,375	0,375	0,392	0,392	0,387
1	2	3	4	5	6	7	8
1	60x150	0...2	0,228	0,163	0,269	0,186	0,233
2	60x150	3,4	0,134	0,199	0,144	0,228	0,100
3	50x125	0...2
4	50x125	3,4
5	32x125	0...2
6	32x125	3,4
7	25 х разная	0...2	0,063	0,050			0,070
8	25 х разная	3,4	0,037	0,050			0,043
9,	19х разная	0.. .2	0,090	0,051	0,111	0,078	0,100
10	19х разная	3,4	0,072	0,112	0,083	0,117	0,067
11	16х разная	0...4
12	28	2	1
13	28	3		1
14	26	2			1
15	26	3				1
16	24	2					1
17	24	3
18	22	2
19	22	3
20	20	2
21	20	3
22	18	2
23	18	3

			Т а б л и ц а 3.16
		Тип	Значение
	*36		ограничений
. . .		ограни­
	0,429	чений	Нижняя	Верхняя
			граница	граница
9	10	11	12	13
		>	56,50	_
		>	52,25
		>	57,00	_
		>	42,75	_
	0,160	>	83,60	_
	0,240	>	71,25	_
		>	50,00	_
		>	40,00	_
		>	25,00	_
		>	40,00	_
	0,171	>	60,00	_
		<	—	60
		<	—	140
		<		60
			—
		<		140
			—
		<		60
			—
		<	—	140
		<		45
			—
		<	—	105
		<	—	45
		<	—	105
				30
			—
	1	<	—	70

														Т а б л и ц а			3.17
			of	Толщина, мм		Специс жкация пиломатериалов, подлежащих выработке
	о				60	60	50	50	32	32	25	I 25	I	19	I1 19	I	16
				Ширина, мм	150	150	125						1
	«Г		В					125	125	125			Разная
	са		§	Длина, м	5,5	5,5	5,5	5,5	5,5	5,5			Разная
2	о
	Он		R
s	ю			Сорт	0...2	3,4	0...2	3,4	0...2	3,4	0...2	3,4		0...2	3,4	0...4
о			К
к	6 е		1=1	Плановый	56,5	52,25	57	42,75	83,6	71,25
о-				объем, м 3							50,0	40,0		25,0	40,0	60,0
<и	I	&	S
jg				Объем по по­				Получено пиломатериалов по расчету, м 3
О		О	VO м
К	Й	и	О 2	ставу, м3
2	28		98,11	61,37	16,03	19,49					4,94	4,94		4,97	11,0
6	24	3	78.62	48,21	14,15	12.05					4,72	4,19		5,24	7,86
8	22		105.0	64,05	22,89	18.06										23,1
11	18	2	9,8	5,1	1,79	1,01					1,01	0,56					0,73
12	18		11,45	5,96	1,64	1,64					0,98	0,85					0,85
16	26	3	57,40	35,69			11,79	10,52			3.5	2,87		2,39	4,62
21	20	2	42.62	25,36			9,74	5,48			3,65	2,43				4,06
22	20	3	105.0	62,49			21,37	16,12			7.5	7.5					10,0
24	18		57,74	34,63			14,1	10,63									9,9
25	28	2	60.0	35,4					12,58	6,73	3.8	2.05		5,56	4,68
26	28	3	41,89	24,72					6,02	7,46	2,25	1,84		2,35	4,8
27	26	2	60,0	35,98					14,33	7,66	4,33	2,33		3,83	3.5
28	26	3	82,6	49.53 .					13,53	16,74	5,04	4,13		3,44	6,65
29	24	2	60,0	36,39'					13,2	8,8	4,19	3,8		3.4	3,0
30	24	3	61,39	37,23					8,18	14,32	4.09	4,1		2.04	4.5
31	22		45,0	27,0					10,26	5,94							10,8
33	20	2	2,38	1,38					0,65	0,37						0,36
35	18		20,2	11.54					4,85	3,23						3,46
Итого			999,2	602,03	56,5	52,25	57,0	42,75	83,6	71,25	50,0	41,59		33,22	50,61	63,26
Недовыполнение, %
Перевыполнение, %												3,98		32,88	26,53	5,43

69

Z (l - сj )Xj -> min.

(3.62)

y=i

Запишем, например, ограничение (3.60) для пиломатериалов сорта 0 - 2 сече­ ния 60 х 150 мм. Присвоим этой размерно-качественной группе пиломатериалов номер / = 1. Для их выработки используются поставы № 1 - 12 (см. табл. 3.14). Поэтому име­ ем

^11*1 ^12*2 “*"•••"*"

12*12 ~ ^1 '

(3.63)

Величина Q\ равна 56,5 м3 (см. табл. 3.13), а коэффициенты посортного выхода пиломатериалов ац берутся из таблиц расчета поставов. Так. а,\ = 0,228 (см. табл. 3.15).

Для ввода в ЭВМ исходные данные задачи (3.58), (3.60) - (3,62) сведены в мат­ рицу, фрагмент которой представлен в табл. 3.16. В ее верхней строке, начиная с чет­ вертой графы, приведен список переменных задачи. Индекс каждой переменной совпа­ дает с номером постава из табл. 3.14. В первой графе таблицы пронумерованы ограни­ чения. Номер 0 соответствует целевой функции. Номера с 1-го по 11-й присвоены ог­ раничениям (3.60). Во второй графе в этих строках приведены сечения пиломатериалов. Строки с 12-й по 23-ю соответствуют ограничениям (3.58). Во второй графе в них вписаны значения диаметра бревен. В третьей графе указан сорт пиломатериалов и бревен. В клетке на пересечении каждой строки и графы записывается коэффициент при соответствующей переменной в рассматриваемом ограничении или в целевой функции для нулевой строки. Пустые клетки соответствуют нулевым коэффициентам. Например, ограничение (3.63) записано в первой, а ограничение (3.59) - в двенадцатой строке табл. 3.16.

Результаты решения задачи сведены в табл. 3.17. Из таблицы видно, что объем выработки пиломатериалов толщиной 32...60 мм равен плановому заданию, а для ос­ тальных толщин превышает его. В целом перевыполнение плана выработки пиломате­ риалов не превышает 5 %. Из анализа данных в графах 2 - 4 табл. 3.17 видно также, что ресурсы сырья по всем его размерно-качественным группам израсходованы полностью, за исключением бревен 3-го сорта диаметром 18 см. По ним предусматривается недо­ расход в объеме 0,8 м3. Найденному оптимальному решению соответствует значение целевой функции, равное 396,166 м3.

Отметим, что поставленная задача имеет решение только при условии выпол­ нимости спецификации, поэтому выбор исходных данных должен быть хорошо обос­ нован.

3.6. Двойственные задачи линейного программирования

3.6.1. Прямая и двойственная задачи

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

Рассмотрим ЗЛП с ограничениями в виде неравенств:

		70
	W = Yjcj xj	max J
	y=i	(3.64)
	n
	H aijxj - bj,
		/ = 1,2,..., m;

>1

Xj> 0, j = l,...,n.

Исходную ЗЛП часто называют прямой задачей.

ЗЛП, двойственная к ЗЛП (3.64), формулируется следующим обра­

зом:

F = Yibiy i -> min; /=1

	т	(3.65)
	'I]aijyi>Cj, 7 = 1,...,
		п\

i=1

х >0, i =

Пусть, например, исходная задача имеет вид

W = х, - 2 х 2 + З;с3 - х4 —» шах;

2*, - х2 + 2х3 - Зх4 < 5;

(3.66)

х, + 2хг - + х4 < 3;

х, >0,...,x4 >0.

Двойственной к ней будет следующая ЗЛП:

	F =	+ Зу2 -> min; ^
	2 у , + у 2>1;
	~ У 1+2у 2> - 2;		(3.67)
	2У \ - У г * 3 ’
	~ЗУ\ +У2 ^ ~ 1>
	У\ -0 ;	у 2 >0.	J

Отметим прежде всего, что каждому ограничению-неравенству ис­ ходной задачи соответствует неотрицательная переменная двойственной. Требование максимизации в исходной задаче заменено в двойственной за­ даче требованием минимизации. Направление знаков неравенств в двойст­ венной задаче противоположно направлению знаков неравенств в исход­ ной задаче.

В некотором смысле двойственная задача - это исходная задача, по­ вернутая на 90°. Рассмотрим первую графу коэффициентов, входящих в