Решение транспортной задачи online

Решение транспортной задачи открытого типа


Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

1 2 3 4 5 Запасы
1 3 20 8 13 4 80
2 4 4 18 14 3 60
3 10 4 18 8 6 30
4 7 19 17 10 1 60
Потребности 10 30 40 50 70

Проверим необходимое и достаточное условие разрешимости задачи.
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 30 (230-200). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
1 2 3 4 5 6 Запасы
1 3 20 8 13 4 0 80
2 4 4 18 14 3 0 60
3 10 4 18 8 6 0 30
4 7 19 17 10 1 0 60
Потребности 10 30 40 50 70 30

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13[20] 4 0[10] 80
2 4 4[30] 18 14 3[10] 0[20] 60
3 10 4 18 8[30] 6 0 30
4 7 19 17 10 1[60] 0 60
Потребности 10 30 40 50 70 30

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u1 + v3 = 8; 0 + v3 = 8; v3 = 8
u1 + v4 = 13; 0 + v4 = 13; v4 = 13
u3 + v4 = 8; 13 + u3 = 8; u3 = -5
u1 + v6 = 0; 0 + v6 = 0; v6 = 0
u2 + v6 = 0; 0 + u2 = 0; u2 = 0
u2 + v2 = 4; 0 + v2 = 4; v2 = 4
u2 + v5 = 3; 0 + v5 = 3; v5 = 3
u4 + v5 = 1; 3 + u4 = 1; u4 = -2
v1=3 v2=4 v3=8 v4=13 v5=3 v6=0
u1=0 3[10] 20 8[40] 13[20] 4 0[10]
u2=0 4 4[30] 18 14 3[10] 0[20]
u3=-5 10 4 18 8[30] 6 0
u4=-2 7 19 17 10 1[60] 0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(4;4): -2 + 13 > 10; ∆44 = -2 + 13 - 10 = 1
Выбираем максимальную оценку свободной клетки (4;4): 10
Для этого в перспективную клетку (4;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13[20][-] 4 0[10][+] 80
2 4 4[30] 18 14 3[10][+] 0[20][-] 60
3 10 4 18 8[30] 6 0 30
4 7 19 17 10[+] 1[60][-] 0 60
Потребности 10 30 40 50 70 30

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 6) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13[0] 4 0[30] 80
2 4 4[30] 18 14 3[30] 0 60
3 10 4 18 8[30] 6 0 30
4 7 19 17 10[20] 1[40] 0 60
Потребности 10 30 40 50 70 30

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u1 + v3 = 8; 0 + v3 = 8; v3 = 8
u1 + v4 = 13; 0 + v4 = 13; v4 = 13
u3 + v4 = 8; 13 + u3 = 8; u3 = -5
u4 + v4 = 10; 13 + u4 = 10; u4 = -3
u4 + v5 = 1; -3 + v5 = 1; v5 = 4
u2 + v5 = 3; 4 + u2 = 3; u2 = -1
u2 + v2 = 4; -1 + v2 = 4; v2 = 5
u1 + v6 = 0; 0 + v6 = 0; v6 = 0
v1=3 v2=5 v3=8 v4=13 v5=4 v6=0
u1=0 3[10] 20 8[40] 13[0] 4 0[30]
u2=-1 4 4[30] 18 14 3[30] 0
u3=-5 10 4 18 8[30] 6 0
u4=-3 7 19 17 10[20] 1[40] 0


 Опорный план является оптимальным.
 Затраты составят:
 F(x) = 3*10 + 8*40 + 0*30 + 4*30 + 3*30 + 8*30 + 10*20 + 1*40  = 1040

Скачать в формате doc

загрузка...