Бережная_Матметоды моделирования эк cистем

изделий между предприятиями, оптимальное закрепление механиз­ мов по определенным видам работы.

6. Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателей с^у. Выбор к.петки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице [су — (а/ + Ру)], а по максимальной положительной разнице [су —

— (а/ + Ру)]. Оптимальным будет план, которому в последней таб­ лице сопутствуют свободные клетки с неположительными элемен­ тами: все разности [Cij — (а^ + Ру)] < 0.

7. Необходимо в одно время распределить груз различного ро­ да по потребителям. Задачи данного типа называются многопродук­ товыми транспортными задачами. В этих задачах поставщики т ро­ дов грузов разбиваются на т условных поставщиков, а потребите­ ли п родов грузов разбиваются на п условных потребителей. С уче­ том этой разбивки составляют полную транспортную таблицу При этом заметим, что некоторые маршруты A^Bj должны быть блоки­ рованы (закрыты), поскольку в данной постановке задачи грузы разного рода не могут заменять друг друга. Этим маршрутам A^BJ должна соответствовать очень высокая стоимость перевозки. Мно­ гопродуктовую задачу не всегда обязательно описывать одной мо­ делью. Например, если поставки грузов различного рода независи­ мы, то задачу можно представить в виде комплекса транспортных задач по каждому роду груза. Однако если между грузами различ­ ного рода существует связь (например, одни из грузов можно заме­ нить другими), то в общем случае исходную модель (задачу) не уда­ ется разбить на комплекс простых транспортных задач.

Рассмотрим примеры задач транспортного типа.

Пример 8.1. Одно фермерское хозяйство (А^) имеет продо­ вольственное зерно двух видов: 3 тыс. т — III класса и 4 тыс. т — IV класса. Второе фермерское хозяйство (Aj) также имеет зерно двух классов: 5 тыс. т — III класса и 2 тыс. т — IV класса. Зерно должно быть вывезено на два элеватора: на первый элеватор (£{) необходимо поставить 2 тыс. т пшеницы III класса, 3 тыс. т пше­ ницы IV класса и остальные 2 тыс. т пшеницы любого класса.

Аналогично второй элеватор (^2) должен получить 8,25 тыс. т, из них пшеницы — 1 тыс. т III класса и 1,5 тыс. т IV класса.

Стоимость перевозки в д. е. 1 т зерна составляет: из пункта Ai в пункты ^1 и ^^2 "~ 1 и Ь5 соответственно; из пункта А2 в пункты Bi и Bj — 2 и I л. е. соответственно.

Составить оптимальный план перевозок.

280

Решение

Каждого поставщика условно разбиваем на две части согласно двум видам зерна {А^^ и Ai^\ Aj и А^), аналогично потребителей разбиваем на три части (пшеница III класса, IV класса и любой класс): В^, В^ и ^i^, а также B-i, Bi и Bi^ Потребности превыша­ ют запасы, поэтому вводим фиктивного поставщика Ау Часть кле­ ток в таблице запираем большими числами М\ например, в клетке (1; 2) стоит большое число. Это значит, что поставщик .4^^ не мо­

жет удовлетворить потребителя В^					пшеницей IV класса за счет
имеющейся пшеницы III класса.
С учетом сделанных замечаний составим первую таблицу
(табл. 8.6).
			Исходные данные					Таблица 8.6
				Потребители				Запас,
Поставщики			^1			В2
								тыс. т
		В?
			^И	В,^	Вг'	Вг'	Вг'
	л?	1	м	1	1,5	м	1,5	3 • 1
		м
Ах	л,'		1	1	Л/	1,5	1,5	4
			м
	Лг'	2		2	1	М	1	5
А2	Аг'	М	2	2	Л/	1	1	2
Лг		0	0	0	0	0	0	1,25
Спрос,		2	3	2	1	1,5	5,75	15,25
тыс. т

Перевозки от фиктивного поставщика не производятся, поэтому Сз! = С52 = ^53 = ^54 = С55 = ^56 ~ О* Величина М намного боль­ ше Су. Применяя метод потенциалов, в итоге получим таблицу с оптимальным решением (табл. 8.7).

Анализ решения.

Первый поставщик поставит на первый элеватор {В^) пшени­ цу III класса {хц = 2); пшеницу IV класса {х^^ = 3), а также пше­ ницу любого класса (III или IV) (xi3 = 1; ^23 = 1).

Второй поставщик (Ai) поставит на второй элеватор (^2) пше­ ницу III класса (Х31 = 1), пшеницу IV класса (Х45 = 1,5) и частично

281

			Оптимальное i[)ешение					Таблица 8.7
				Потребители				Запас,
Поставщики			^1			В2
								тыс. т
		Вх'		В,^	В2'
			V			Вг'	^2«
	Ах'	2 '	л/	l'	1,5	м	1,5	3
Ai	Ах'	м	з'	l'	Л/	1,5	1,5	4
	Аг'	2	М	2	i '	М	4 1	5
Аг	Аг'	М	2	2	м	1,5'	0,5 1	2
Аъ		0	0	0	0	0	1,250	1,25
Спрос,		2	3	2	1	1,5	5,75	15,25
тыс. т

любую пшеницу (хзб = 4; Х/^^ = 0,5). Потребность элеватора в лю­ бой пшенице не удовлетворена на 1,25 тыс. т (хзб = 1,25). Мини­ мальные затраты на перевозку составили: Z^^^ = 14 д. е.

Пример 8.2. Модель производства с запасами.

Фирма переводит свой головной завод на производство опреде­ ленного вида изделий, которые будут выпускаться в течение четы­ рех месяцев. Величины спроса в течение этих четырех месяцев со­ ставляют 100, 200, 180 и 300 изделий соответственно. В каждый ме­ сяц спрос можно удовлетворить за счет:

•запасов изделий, произведенных в прошлом месяце, сохраня­ ющихся для реализации в будущем;

•производства изделий в течение текущего месяца;

•избытка производства изделий в более поздние месяцы в счет невыполненных заказов.

Затраты на одно изделие в каждом месяце составляют 4 д. е. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 д. е. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполнен­ ных заказов, облагается штрафом в размере 2 д. е. в месяц.

Объем производства изделий меняется от месяца к месяцу в за­ висимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответ­ ственно.

282

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

Решение

Задачу можно сформулировать как транспортную. Эквивалент­ ность между элементами производственной и транспортной систем устанавливается следующим образом (табл. 8.8):

			Таблица 8.8
	Транспортная система		Производственная система
1.	Исходный пункт /	1. Период производства /
2.	Пункт назначения у	2. Период потребления у
3.	Предложение в пункте /	3.	Объем производства за период /
4. Спрос в пункте у		4.	Реализация за периоду
5.	Стоимость перевозки из / и у	5.	Стоимость производства и
		хранения за период / и у

Перед нами структура транспортной модели. Для рассматрива­ емой задачи стоимость «перевозки» изделия из периода / в период у выражается как:

• стоимость производства в /-и период, / = у;

•стоимость производства в /-й период плюс стои­ мость задержки от / до у, / < у;

•стоимость производства в /-й период плюс штраф за нарушение срока, / > у.

Из определения Су следует, что затраты в период / при реализа­ ции продукции в тот же период / (/ = у) оцениваются только стои­ мостью производства. Если в период / производится продукция, которая будет потребляться позже (/ <у), то имеют место дополни­ тельные издержки, связанные с хранением. Аналогично производ­ ство в /-Й период в счет невыполненных заказов / > у влечет за со­ бой дополнительные расходы в виде штрафа. Например,

сц = 4 д. е.; С24 = 4 + (0,5 + 0,5) = 5 д. е.;

С41 = 4 + (2 + 2 + 2) = 10 д. е.

Исходная транспортная таблица выглядит следующим образом (табл. 8.9).

283

			Исходные данные			Таблица 8.9
	Период		Период			Объем
		1	2	3	4	производства
		4	4,5	5		5,5
	1		4	4,5		50
		6				5
	2		6	4		180
		8				4,5
	J					280
	4	10	8	6		4
		100				270
	Спрос		200	180	300
	Задача решается обычным методом потенциалов на минимум
	затрат по производству и хранению продукции.
	Пример	8.3. Имеются три сорта бумаги в количестве 10, 8 и

5 т, которую можно использовать на издание четырех книг тира­ жом 8000, 6000, 10 000, 15 000 экземпляров. Расход бумаги на од­ ну книгу составляет: 0,6; 0,4; 0,8; 0,5 кг, а себестоимость тиража книги при использовании /-го сорта бумаги задается следующей матрицей (д. е.):

^24	16	32	25^
^(^• = 18	24	24	20
30	24	16	20

Определить оптимальное распределение бумажных резервов.

Решение

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

Потребности в бумаге легко определить, зная тираж и расход на одну книгу (т):

8000 • 0,6 = 4,8;

15 000 . 0,4 = 6;

6000 • 0,8 = 4,8;

10 000 • 0,5 = 5.

284

Общие запасы бумаги составляют 23 т, а общие потребности - 20,5 т, поэтому необходимо в таблицу ввести фиктивный тираж В^ с нулевыми затратами. В связи с тем что мы составляем модель от­ носительно бумаги, а матрица су характеризует себестоимость печа­ тания книги, необходимо исходную матрицу преобразовать отно­ сительно единицы бумаги (каждый столбец матрицы Су разделим на количество бумаги, приходящейся на одну книгу).

Согласно изложенному составим первую таблицу (табл. 8,10).

Таблица 8.10

Исходные данные

Поставщики		Потребители				Запасы,
	Вх	Вг	Въ	В,		т
					^5*
	40	20	80	50		0
А^			60			10
	30	30		40		0
Л2						8
	50	30	40	40		0
Лъ	4,8	4,8			2,4	5
Потреб­			6	5		23
ность, т

Используя метод потенциалов, получим оптимальное решение (табл. 8.11).

		Оптимальное решение					Таблица		8.11
Поставщики			Потребители					Запасы,
		В,			В,			т	1
	^1			^3			^5*
	40		20		80	50	2,4	0
А,		4,8			2,8			10
	30		30		60	40		0
Лг	4,8			1	2,2			8
	50		30	5	''	40		0
Лг								5
	4,8			6			2,4
Потреб­		4,8			5			23
ность, т

285

Анализ решения.

Бумаги 1-го сорта в количестве 4,8 т затрачено на издание вто­ рой книги; 2,8 т — на издание четвертой книги; 2,4 т — не исполь­ зовано. Бумаги 2-го сорта затрачено: на первую книгу — 4,8 т; на из­ дание третьей книги - 1,0 т; на издание четвертой книги — 2,2 т; бумага 3-го сорта использована на издание третьей книги в количе­ стве 5 т.

8.4. Метод Фогеля

Как известно, метод потенциалов позволяет за конечное число шагов найти оптимальный план, следовательно, желательно, чтобы первый опорный план был ближе к оптимальному. Способ получе­ ния опорного плана, предложенный американским ученым У. Фо­ гелем, позволяет найти практически оптимальный план. Найден­ ный план или совпадение с оптимальным, или незначительно от него отличается.

Способ Фогеля рассмотрим в табл. 8.12. Процесс начинается с определения разностей между двумя наименьшими элементами каждой строки и каждого столбца таблицы. Так, в столбце В^ ми­ нимальный элемент равен 3, следующий за ним по величине эле­ мент — 8, разность между ними равна 5. Эта и другие разности по строкам и столбцам записаны в таблицу. Затем из всех разностей выбирается наибольшая. В приведенном примере это А = 6 в стро­ ке А^. Минимальный элемент в соответствуюш.ей строке равен 5 и совпадает с клеткой (А^В^), сюда же записывается поставка (см. табл. 8.12).

Все запасы А^ исчерпаны, поэтому эту строку в дальнейшем не рассматриваем (ее можно вычеркнуть).

Смысл способа Фогеля легко понять. Найденные разности по­ казывают, насколько больше будут затраты, если в соответствую­ щем столбце (или строке) поставка будет записана не в клетку, где находится минимальный в этом столбце (строке) элемент, а в клет­ ку, где находится элемент, следующий за ним по величине.

Теперь, когда из рассмотрения исключены элементы столбца jffj, изменяются разности по строкам, но по столбцам они не изме­ няются (см. 4-ю строку и столбец). В столбце ^2 осталась разность А = 6, она и является наибольшей.

Находим в столбце В2 минимальный элемент, равный 3, и в клетку AiBj делаем поставку. Вновь находим разности (см. 5-ю строку и столбец).

Опять имеем две максимальные разности в строке А^и в столб­ це В^ (А = 4). В строке А^ минимальный элемент 13 в А^В^, но он

286

Ai

Лг

Аз

А,

Аь

Аб

Ау

As

1 Потреб-

1 нести

1

::f

2 юе

Таблица 8.12 Пример нахождения опорного плана методом Фогеля

								Запа­		Разности
	^1	^2	Вз	^4	Bs	Вб	В,		по строчкам
								сы	1	2	3	4	5
	1 1	3	5	7 \	9	11	4	30	2	2	'2	1	1
	17	1?					1
	14	12	10	10	8	6	3	29	3	3	3	3	3
i	7				26		3
		9	13	17	21	24	29	28	2	2	2	4	4
			19	Я		1
1	35	32	29	26	23	20	20	27	0	0	0	0	0
						27
	7	10	13	16	12	8	5	26	2	2	2	3	3
						11	15
	25	20	15	5	11	17	23	25	6 — — — —
				25
	10	8	9	16	12	17	10	24	1	1	1	1	1
							24
	2	5	8	8	3	15	21	23	1	1	— — —
					23
	17	12	19	33	49	39	43	212
	1	2	3	2	5	2
	1	2	3	1	5	2

1 3	о	6	6	4	3	1	2
	с:
4	S	-	6	4	3	1	2
	ж
5	со	-	~	4	3	1	2

не является минимальным в своем столбце. Точно также не являет­ ся минимальным в своей строке минимальный элемент столбца ^з- Если учитывать, что мы ищем не абсолютный оптимум, а лишь один из базисов, можно произвольно выбрать или строку Ау или столбец By Но можно вычислить в соответствующих столбце и строке вторые разности — это разности между минимальными эле-

287

ментами и элементами, не ближайшими к ним по величине, а сле­ дующими за ними.

Вторая разность для столбца В^ равна (9 — 5 = 4), а для строки А^ (21 - 13 = 8), поэтому поставку надо сделать в клетку А^Ву

Проводя аналогичные рассуждения, можно получить допусти­ мый план (см. табл.), общие затраты на перевозку составляют Z=1818.

8.5. Транспортная задача в сетевой постановке

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

Рис. 8.1. Транспортная задача в сетевой форме

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

288

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

Решение задачи на сети начинается с построения начального опорного плана. Последовательность решения задачи рассмотрена на конкретном примере (см. рис. 8.1). Поставку груза из вершины в вершину будем обозначать стрелками с указанием величины по­ ставок.

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

1)все запасы должны быть распределены, а потребности удов­ летворены;

2)к каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;

3)общее количество стрелок должно быть на единицу меньше числа вершин (л + m - 1);

4)стрелки не должны образовывать замкнутый контур.

План распределения груза, отвечающий этим требованиям, представлен на рис. 8.2.

Рис. 8.2. Пример опорного план распределения груза при решении задачи на сети

Далее следует проверить план на оптимальность. Для этого вы­ числяем потенциалы. Одной из вершин (например, вершине 1) присвоим некоторое значение потенциала (например, равное 10). Для наглядности потенциалы будем заключать в рамки. После это­ го, двигаясь по стрелкам, определяем потенциалы остальных вер­ шин, руководствуясь правилом: если стрелка выходит из вершины, то к потенциалу этой вершины прибавляем показатель С^ критерия

289