Пример решения транспортной задачи

На три базы А₁,А₂,А₃ поступил однородный груз в количествах, соответственно равных 6, 8, 10 (ед.) Этот груз требуется перевезти в четыре магазина В₁,В₂,В₃, В₄ соответственно в количествах 4, 6, 8, 8 (ед.). Стоимость доставки единицы груза с каждого из пункта отправления в соответствующие пункты назначения задана матрицей тарифов (в руб.):

Составить план перевозок однородного груза с минимальными транспортными издержками.

Проверим необходимое и достаточное условие разрешимости задачи.

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным (ед.). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределенную таблицу 5.

Таблица 5.

Bj bj Ai ai	B1	B2	B3	B4	Потенциалы
	bj	b1=4	b2=6	b3=8	b4=8	=0
А1	а1=6		2-	+		=1
А2	а2=8		4+	8 4-		=-1
A3	а3=10					=-7
А4	а4=2
Потенциалы	=1	=-1	=4	=1

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Среди тарифов из всей таблицы наилучшим является , поэтому в клетку направляем максимально возможный груз. Он равен . Тогда и из базы не вывезен груз 2 ед., а потребность магазина удовлетворена полностью. Столбец таблицы выходит из рассмотрения. Из оставшихся тарифов строки наименьший - . В клетку направляем максимально возможный груз, равный . Тогда строка выходит из рассмотрения, поскольку из базы вывезен весь груз. Из оставшихся тарифов наилучший и . В клетку направляем груз, равный . При этом вычеркивается столбец из рассмотрения. Из оставшихся тарифов наименьший . В клетку направляем груз, равный . При этом потребность четвертого магазина удовлетворена, а из третьей базы не вывезено 2 ед. Этот нераспределенный груз направляем в клетку , . Потребность третьего магазина не удовлетворена на 2 ед. Направим от фиктивного поставщика – базы 2 ед. в клетку , т.е. .

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

2. Подсчитаем число занятых клеток таблицы, их -7, а должно быть . Следовательно, опорный план является невырожденным.

3. Определяем значение целевой функции первого опорного плана.

(руб.)

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

4. Найдем потенциалы по занятым клеткам таблицы, решая систему уравнений, полагая что и .

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

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

5. Для клетки построим цикл перераспределения груза. Для этого в перспективную клетку поставим знак +, а в остальных вершинах многоугольника чередующиеся значки -, +, -:

4 2 6 2

Затем из чисел , стоящих в минусовых клетках, выбираем наименьшее, т.е. . Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из , стоящих в минусовых клетках. В результате получим новый опорный план II.

План II. Таблица 6.

bj   Ai ai	B1	B2	B3	B4	Потенциалы
b1=4	b2=6	b3=8	b4=8	=0
А1	а1=6	4 -		+ 2		=4
А2	а2=8					=2
A3	а3=10	2 +		-2		=-4
А4	а4=2
Потенциалы	=1	=-1	=4	=1

6. Определяем значение целевой функции:

(руб.)

7. Число занятых клеток в II плане 7, следовательно план невырожденный.

8. Проверяем оптимальность плана методом потенциалов, для этого находим потенциалы по занятым клеткам, полагая :

Затем рассчитаем оценки свободных клеток:

План, полученный в таблице 6, не оптимальный, так как и .

9. Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем , в которую записываем +, затем строим цикл перераспределения:

A₃B₁ 2 2 A₃B₃

Груз перераспределения равен:

Это единственная положительная оценка, поэтому строим цикл для клетки . .

Перераспределив груз, получаем новый план III.

План III таблица 7.

bj   Ai ai	B1	B2	B3	B4	Потенциалы
b1=4	b2=6	b3=8	b4=8	=0
А1	а1=6	2 -		+ 4		=4
А2	а2=8	+		- 2		=1
A3	а3=10					=-4
А4	а4=2
Потенциалы	=1	=-1	=4	=1

10. Число занятых клеток 7, а должно быть , следовательно, план III невырожденный.

11. Вычислим значение целевой функции:

.

12. Проверяем оптимальность плана III методом потенциалов. Находим потенциалы по занятым клеткам:

Проверим оценку свободных клеток:

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

13. Проводим улучшение плана III путем перераспределения груза. В качестве перспективной клетки для загрузки выбираем , в которую записываем +, затем строим цикл перераспределения:

A₂B₁ 2 2 A₃B₃

Определяем груз перераспределения , после проведения операции перераспределения получаем план IV.

План IV. Таблица 8

bj   Ai ai	B1	B2	B3	B4	Потенциалы
b1=4	b2=6	b3=8	b4=8	=0
А1	а1=6					=3
А2	а2=8					=1
A3	а3=10					=-4
А4	а4=2
Потенциалы	=1	=-1	=4	=1

14. План получается вырожденный поскольку в минусовых клетках цикла находятся два одинаковых минимальных объема груза 2. при перераспределении две клетки А₁ В₂ и А₂ В₃ оказались свободными, поэтому число занятых клеток 6 будет меньше, чем m+n-1=7. Для продолжения решения в одну из освободившихся клеток записываем нуль А₁ В₁, т.к. тариф С₁₁ меньше С₂₃.

15. вычисляем значение целевой функции:

16. проверяем оптимальность плана IV методом потенциалов. Находим потенциалы по занятым клеткам:

Проведем оценку свободных клеток:

Поскольку все оценки больше или равны нули, то план оптимален.

тыс.руб.

Анализ плана. Из первой базы необходимо весь груз направить в третий магазин, из второй базы направить в первый и второй магазин в количестве 2 ед. и 6 ед., а груз с третьей базы следует вывозить в первый и второй магазин в количестве 2 и 8 ед. соответственно. При этом плане потребность третьего магазина В₃ остается неудовлетворительной в размере 2 ед. Общая стоимость доставки груза потребителям будет минимальной и составлять 78 тыс. руб. Так как оценка свободной клетки , то задача имеет множество оптимальных планов.