Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 8 )

Транспортная задача является классической задачей дискретной математики в разделе математического программирования (прогнозирования).

Дано: Пусть имеется m пунктов распределения и n пунктов потребления товара. Количество товара в m пунктах обозначим { ai }, i=1,…,m, а потребность в данном товаре в n пунктах потребления – { bj }, j=1,…,n. Стоимость перевозок оценивается расстояниями между i-ым пунктом поставки и j-ым пунктом потребления и моделируется матрицей стоимости С={ cij }.

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

;

;

xij ³0, i = 1,...,m; j = 1,...,n,

Решение задачи можно найти за следующие два этапа:

1.  поиск опорного плана;

2.  поиск оптимального плана на основе опорного.

Для поиска опорного плана (начального решения по распределению товаров по пунктам потребления) здесь представлены эвристические методы «северо-западного угла» и минимальной стоимости, для поиска оптимального плана – метод потенциалов.

2.7.1. Метод «северо-западного угла»

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

Положим x11 = min{a1 ,b1}. Если a1 < b1, то x11 = a1 (это означает, что весь запас товара из 1-го пункта хранения направляется в 1-ый пункт потребления). Если b1 < a1 , тогда первый пункт потребления получил требуемое количество товара, поэтому xij = 0 при i=2,...,m. Оба варианта представлены ниже.

				a1		a1	0	..	0	0		b1				a1 - b1
				a2						a2		0				a2
				...						...		...				...
				am						am		0				am
b1	b2	...	bn			b1-a1	b2	..	bn			0	b2	...	bn

a1 < b1 b1 < a1

Далее процесс распределения проходит по аналогии с предыдущим шагом:

·  для a1 < b1: рассматривается остаток в 1-ом пункте хранения и он направляется в оставшиеся пункты потребления, начиная со второго;

·  для b1 < a1: в 1-ый пункт направляются товары из других пунктов по очереди, начиная со второго.

Построение распределения выполняется до тех пор, пока не будут исчерпаны все пункты распределения и не будут насыщены все пункты потребления.

Пример: Рассмотрим пример с тремя пунктами хранения [15] (m=3) и пятью пунктами потребления (n=5) однородного товара. Стоимость перевозок, а также количество товара в пунктах хранения (правый столбец 330+270+350=950) и потребность в нем в пунктах потребления (нижняя строка 220+170+210+150+200=950) отображены в следующей матрице:

10	12	24	50	12	330
13	22	49	66	320	270
26	27	35	67	63	350
220	170	210	150	200	b\a

Т. к. b1 < a1, то весь товар для 1-го пункта потребления поступит из 1-го пункта хранения:

220					110
					270
					350
0	170	210	150	200	b\a

2-ой пункт потребления с b2= 170 получит товар из 1-го пункта хранения 110 шт. и 2-го пункта хранения в количестве 170 – 110 = 60 шт.:

220	110				0
	60				210
					350
0	0	210	150	200	b\a

3-тий пункт потребления получит весь остаток товаров из 2-го пункта хранения:

220	110				0
	60	210			0
					350
0	0	0	150	200	b\a

4-ый и 5-ый пункты потребления поделят между собой товар из 3-го пункта хранения. Процесс распределения закончен. Получен опорный план перевозок.