Затраты на транспортировку

Участки дорог Заводы	А	В	C	D	Количество рейсов, ед.
АБЗ-1	5	6	2	2	600
АБЗ-2	9	7	4	6	240
АБЗ-3	7	1	4	5	1360
АБЗ-4	5	2	2	4	1000
АБЗ-5	6	4	3	4	800
Потребность в машинах, ед.	600	800	1400	1200	–

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

Заполним расчетную таблицу 2 и составим первый опор­ный план методом минимальных затрат, выбирая на каждом шаге наименее затратный маршрут и максимально возможную поставку по этому маршруту. Заполнение таблицы начинается с клетки (3,2) с наименьшими издержками, в которую записыва­ется поставка 800. Затем последовательно заполняются клетки (4,3); (1,4); (5,3); (5,4); (3,4); (3,1); (2,1).

Таблица 2

Итерация 1

Заводы	Участки дорог								Предл.
	А		В		C		D
АБЗ-1	5		6		2		2	600	600	0
АБЗ-2	9	– 240	7		4	+	6		240	5
АБЗ-3	7	+ 360	1	800	4		5	– 200	1360	3
АБЗ-4	5		2		2	1000	4		1000	1
АБЗ-5	6		4		3	– 400	4	+ 400	800	2
Спрос	600		800		1400		1200		4000	–
	4		–2		1		2		–	Z = 12480

У словие, что заполненных клеток в таблице должно быть равно m + n – 1 = 5 + 4 – 1= 8, выполняетcя.

Переходим к анализу первого опорного плана. Рассчитываем значение целевой функции:

Проверим, является ли план оптимальным, если нет, то улучшаем его.

1. Рассчитываем значения потенциалов по формуле (4):

; ; ; ; ; ; ; ; .

2. Рассчитываем характеристики для свободных клеток:

; ; ; ; ;

; ; ;

; ;

; .

2. Максимальная по абсолютной величине отрицательная характери­стика в клетке (2,3), для которой строим цепь.

3. Проставляем по углам цепи, начиная с выбранной клетки, знаки «+», «–». В клетках со знаком «–» минимальная поставка 200. Ее перерас­пределяем по цепи. Там, где стоит знак «+», прибавляем, а где «–», вычитаем. Заполняем следующую расчетную табл. 3.

Расчеты ведем аналогично. Получены следующие отрицательные ха­рактеристики: ; ; .

Для клетки (4,1) строим цепь. Перераспределяем по цепи поставку 40. Заполняем таблицу для итерации 3.

В расчетной табл. 4 нет отрицательных характеристик, следователь­но, план оптимальный.

Таблица 3

Итерация 2

Заводы	Участки дорог								Предл.
	А		В		C		D
АБЗ-1	5		6		2		2	600	600	0
АБЗ-2	9	– 40	7		4	+ 200	6		240	3
АБЗ-3	7	560	1	800	4		5	200	1360	1
АБЗ-4	5	+	2		2	– 1000	4		1000	1
АБЗ-5	6		4		3	200	4	600	800	2
Спрос	600		800		1400		1200		4000	–
vj	6		0		1		2		–	Z=12080

Таблица 4

Итерация 3

Заводы	Участки дорог								Предл.
	А		В		C		D
АБЗ-1	5		6		2		2	600	600	0
АБЗ-2	9		7		4	240	6		240	3
АБЗ-3	7	560	1	800	4		5	200	1360	3
АБЗ-4	5	40	2		2	960	4		1000	1
АБЗ-5	6		4		3	200	4	600	800	2
Спрос	600		800		1400		1200		4000	–
	4		-2		1		2		–	Z = 12000

Согласно оптимальному плану, необходимо за квартал с АБЗ-1 направить на участок D 600 машин асфальта, с АБЗ-2 к участку С – 240 машин, с АБЗ-3 к участку А – 560 машин и к участку В – 800 машин, с АБЗ-4 к участку А – 40 машин и к участку С – 960 машин, с АБЗ-5 к участку С – 200 машин и к участку С – 600 машин. При этом минимальные затраты на перевозку составят 12000 д. е.