Решение транспортной задачи
Задание
Минимизировать стоимость перевозки при распределении товара внутри города. Данные о наличии товара на складах, спрос потребителей и затратах на перевозку единицы груза от отдельного склада к отдельному потребителю приведены ниже в таблицах.
Таблица 2
Исходные данные
|
Поставщик |
Мощность поставщиков |
Потребители и их спрос |
|||||||
|
1 |
2 |
3 |
4 |
||||||
|
17 |
42 |
21 |
40 |
||||||
|
1 |
60 |
Х11 |
5 |
Х12 |
1 |
Х13 |
4 |
Х14 |
2 |
|
2 |
40 |
Х21 |
2 |
Х22 |
3 |
Х23 |
3 |
Х24 |
4 |
|
3 |
20 |
Х31 |
4 |
Х32 |
2 |
Х33 |
3 |
Х34 |
6 |
Решение
Математическая модель транспортной задачи:
F = ??cijxij, (1)
при условиях:
- ?xij = ai, i = 1,2,…, m, (2)
- ?xij = bj, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов, которая представлена в таблице 3.
Таблица 3
Матрица тарифов
|
1 |
2 |
3 |
4 |
Запасы |
|
|
1 |
5 |
1 |
4 |
2 |
60 |
|
2 |
2 |
3 |
3 |
4 |
40 |
|
3 |
4 |
2 |
3 |
6 |
20 |
|
Потребности |
17 |
42 |
21 |
40 |
Проверим необходимое и достаточное условие разрешимости задачи.
- ?a = 60 + 40 + 20 = 120
- ?b = 17 + 42 + 21 + 40 = 120
Используя метод наименьшей стоимости, построим опорный план транспортной задачи.
Таблица 5
Опорный план транспортной задачи
|
1 |
2 |
3 |
4 |
Запасы |
|
|
1 |
5 |
1[42] |
4 |
2[18] |
60 |
|
2 |
2[17] |
3 |
3[21] |
4[2] |
40 |
|
3 |
4 |
2 |
3 |
6[20] |
20 |
|
Потребности |
17 |
42 |
21 |
40 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Таблица 6
Оптимальность опорного плана
|
v1=0 |
v2=1 |
v3=1 |
v4=2 |
|
|
u1=0 |
5 |
1[42] |
4 |
2[18] |
|
u2=2 |
2[17] |
3 |
3[21] |
4[2] |
|
u3=4 |
4 |
2 |
3 |
6[20] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij.
Выбираем максимальную оценку свободной клетки (3;2): 2
Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 7
|
1 |
2 |
3 |
4 |
Запасы |
|
|
1 |
5 |
1[42][-] |
4 |
2[18][+] |
60 |
|
2 |
2[17] |
3 |
3[21] |
4[2] |
40 |
|
3 |
4 |
2[+] |
3 |
6[20][-] |
20 |
|
Потребности |
17 |
42 |
21 |
40 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3,4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Таблица 8
Новый опорный план
|
1 |
2 |
3 |
4 |
Запасы |
|
|
1 |
5 |
1[22] |
4 |
2[38] |
60 |
|
2 |
2[17] |
3 |
3[21] |
4[2] |
40 |
|
3 |
4 |
2[20] |
3 |
6 |
20 |
|
Потребности |
17 |
42 |
21 |
40 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
Таблица 9
Оптимальность нового опорного плана
|
v1=0 |
v2=1 |
v3=1 |
v4=2 |
|
|
u1=0 |
5 |
1[22] |
4 |
2[38] |
|
u2=2 |
2[17] |
3 |
3[21] |
4[2] |
|
u3=1 |
4 |
2[20] |
3 |
6 |
Опорный план является оптимальным, так как все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 1*22 + 2*38 + 2*17 + 3*21 + 4*2 + 2*20 = 2
