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

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

Реализацию метода рассматриваем на примере организации поставки древесины флотом лесосплавного предприятия семи лесозаводам с четырех лесостоянок. Схема расположения на рейде лесостоянок, обозначенных прямоугольниками, и лесозаводов, обозначенных кружками, приведены на рисунке 8.

Рисунок 12 − Схема расположения поставщиков и потребителей: □ – плотостоянки;○ – лесозаводы

Запасы древесины на лесостоянках и потребности заводов в древесине приведены в таблицах 7 и 8.

Таблица 7- Запасы древесины на лесостоянках

Номер лесостоянки.	1	2	3	4
Запас древесины, м^3	32000	16000	17000	21000

Суммарный объем поставки составляет – 86000 м³.

Таблица 8- Потребности заводов в древесине.

Номер лесозавода	1	2	3	4	5	6	7
Потребность в древесине, м^3	17000	16000	15000	18000	14000	17000	9000

Суммарный объем потребности в древесине составляет – 106000 м³.

Расстояние от каждой лесостоянке до каждого лесозавода определяем по схеме рейда.

Удельная себестоимость в рублях на 1 км 1 м³ древесины составляет 10 руб. / км.

Расстояния и себестоимости транспортировки древесины приведены в табл. 9

Таблица 9- Расстояния и себестоимости транспортировки древесины.

№ маршрута	№ плотостоянки	№ лесозавода	L, км	Себестоимость, руб
1	1	1	8,6	86
2	1	2	12,1	121
3	1	3	6,7	67
4	1	4	12,8	128
5	1	5	16,3	163
6	1	6	8,3	83
7	1	7	16,8	168
8	2	1	5,8	58
9	2	2	9,5	95
10	2	3	4,2	42
11	2	4	10,8	108
12	2	5	13,0	130
13	2	6	5,8	58
14	2	7	14,2	142
15	3	1	12,9	129
16	3	2	12,2	122
17	3	3	8,0	80
18	3	4	3,7	37
19	3	5	8,3	83
20	3	6	6,2	62
21	3	7	7,1	71
22	4	1	11,3	113
23	4	2	14,9	149
24	4	3	5,3	53
25	4	4	9,4	94
26	4	5	14,1	141
27	4	6	4,5	45
28	4	7	12,9	129

Метод потенциалов применим только к закрытым транспортным задачам, т.е. когда объем древесины на лесостоянках равен потребности лесозаводов. Для обеспечения этого требования считаем, что на рейде имеется еще одна лесостоянка №5 с фиктивным объемом равным разнице между потребностью лесозаводов и поставкой лесостоянок. Эта разница равна 6 тыс.м³.

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

В начале решения задачи составляем матрицу таблицу 10.

В правый верхний угол каждой клетки записываем значение себестоимости, а внизу заносим значение объема поставки, распределенное по так называемому правилу северо-западного угла.

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

a_i = C_i,j – b_j;

b_j = C_i,j – a_i;

Затем в левые верхние углы небазисных клеток вносим их потенциалы, определенные по зависимости:

П_i,j = a_i + b_j;

Решение задачи является оптимальным в том случае, если во всех клетках выполняется условие:

П_i,j C_i,j

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

Таблица 10 -Матрица для решения задачи

№ лесостоянки	Номер лесозавода																				Ресурсы m3		ai
	1		2			3			4			5			6			7
1		86			121		68	67		134	128		181	163		85	83		85	168					32		0
	17		15
2	60	58			95			42			108		155	130		59	58		59	142					16		-26
			1			15			0
3	-11	129		24	122		-29	80			37		84	83		-12	62		-12	71					17		-97
									17
4	46	113		84	149		28	53			94			141			45		45	129		21		-40
									1			14			6
5	1	0		36	0		-17	0		49	0		96	0		11	0			0		20		-85
																		9
Потребность	17		16			15			18			14			17			9
bj	86		121			68			134			181			85			85

П=17·86+15·121+1·95+15·42+0·108+17·37+1·94+14·141+6·45+9·0=6969;

Таблица 11- Матрица для решения задачи

№ лесостоянки	Номер лесозавода														Ресурсы m3		ai
	1		2		3		4		5		6		7
1		86		121	68	67	134	128	181	163	85	83	181	168		32		0
	17		15
2	60	58		95		42		108	155	130	59	58	155	142		16		-26
			1		15		0
3	-11	129	24	122	-29	80		37	84	83	-12	62	84	71		17		-97
							17
4	46	113	84	149	28	53		94		141		45	14	129		21		-40
							1		3		17
5	-95	0	-60	0	-113	0	-47	0		0	-96	0		0		20		-181
									11				9
Потребность	17		16		15		18		14		17		9
bj	86		121		68		134		181		85		181

П=5913;

Таблица 12- Матрица для решения задачи

№ лесостоянки	Номер лесозавода														Ресурсы m3		ai
	1		2		3		4		5		6		7
1		86		121	68	67	109	128	156	163	60	83	156	168		32		0
	17		15
2	60	58		95		42	83	108		130	34	58	130	142		16		-26
			1		15				0
3	14	129	49	122	-4	80		37	84	83	-12	62	84	71		17		-72
							17
4	71	113	106	149	53	53		94		141		45	141	129		21		-15
							1		3		17
5	-70	0	-35	0	-88	0	-47	0		0	-96	0		0		20		-156
									11				9
Потребность	17		16		15		18		14		17		9
bj	86		121		68		109		156		60		156

П=5913

Таблица 13- Матрица для решения задачи

№ лесостоянки	Номер лесозавода																		Ресурсы m3			ai
	1		2		3		4			5			6			7
1		86		121	68	67		128	128		156	163		79	83		162	168							32			0
	17		15
2	60	58		95		42		102	108			130		53	58		136	142							16			-26
			1		15					0
3	-5	129	30	122	-23	80			37		65	83		-12	62			71							17			-91
							17									3
4	52	113	87	149	34	53			94		122	141			45		128	129			21			-34
							4						17
5	-70	0	-35	0	-88	0		-28	0			0		-77	0			0			20			-156
										14						6
Потребность	17		16		15		18			14			17			9
bj	86		121		68		128			156			79			162

П=5985;

Таблица 14- Матрица для решения задачи

№ лесостоянки	Номер лесозавода																		Ресурсы m3			ai
	1		2		3		4			5			6			7
1		86		121	70	67		124	128		158	163		75	83		158	168							32			0
	16		16
2		58	93	95		42		96	108			130		47	58		130	142							16			-28
	1				15					0
3	-1	129	34	122	-17	80			37		71	83		-12	62			71							17			-87
							14									3
4	52	113	91	149	40	53			94		128	141			45		128	129			21			-30
							4						17
5	-72	0	-37	0	-88	0		-34	0			0		-53	0			0			20			-158
										14						6
Потребность	17		16		15		18			14			17			9
bj	86		121		70		124			158			75			158

П=5872;

Таблица 15- Матрица для решения задачи

№ лесостоянки	Номер лесозавода																		Ресурсы m3			ai
	1		2		3		4			5			6			7
1		86		121		67		124	128		158	163		75	83		158	168							32			0
	1		16		15
2		58	93	95	39	42		96	108			130		47	58		130	142							16			-28
	16									0
3	-1	129	34	122	-20	80			37		71	83		-12	62			71							17			-87
							14									3
4	56	113	91	149	37	53			94		128	141			45		128	129			21			-30
							4						17
5	-72	0	-37	0	-97	0		-34	0			0		-83	0			0			20			-158
										14						6
Потребность	17		16		15		18			14			17			9
bj	86		121		67		124			158			75			158

П=5827;

Как видно из последнего плана во всех клетках выполняется условие: П_i,j C_i,j

Данный план оптимален.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1 Митрофанов А.А., Камусин А.А. Моделирование и оптимизация процессов лесопромышленных производств: Учебное пособие. – Архангельск: Изд-во Арханг. гос. техн. ун-та, 2003. – 118 с.

2 Митрофанов А.А. Якоря на лесосплаве: Методические указания к лабораторным работам. – Архангельск: РИО АЛТИ, 1988. – 25 с.

3 Ширшов С.И Моделирование процессов лесозаготовок на ЭВМ: Методические указания к выполнению лабораторных работ. – Архангельск: РИО АЛТИ, 1989.–29с.

52