Решение транспортной задачи закрытого типа
Задача. Имеются три пункта отправления А1, А2, А3 однородного груза и пять пунктов В1, В2, В3, В4, В5 его назначения. На пунктах А1, А2, А3 груз находится в количестве а1, а2, а3 тонн соответственно. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно b1, b2, b3, b4, b5 тонн груза. Расстояние в сотнях километров между пунктами отправления и назначения приведены в матрице D. Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах; 2) для решения задачи использовать методы северо-западного угла и потенциалов.
1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
4 | 7 | 19 | 17 | 10 | 1 | 100 | 60 |
Потребности | 10 | 30 | 40 | 50 | 70 | 30 |
Решаем с помощью калькулятора. Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 80 + 60 + 30 + 60 = 230
∑ b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Условие баланса соблюдается. Запасы равны потребностям. Занесем исходные данные в распределительную таблицу.
1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
1 | 3 | 20 | 8 | 13 | 4 | 100 | 80 |
2 | 4 | 4 | 18 | 14 | 3 | 0 | 60 |
3 | 10 | 4 | 18 | 8 | 6 | 0 | 30 |
4 | 7 | 19 | 17 | 10 | 1 | 100 | 60 |
Потребности | 10 | 30 | 40 | 50 | 70 | 30 |
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
1 | 3[10] | 20 | 8[40] | 13[20] | 4 | 100[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] | 100 | 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 = 100; 0 + v6 = 100; v6 = 100
u2 + v6 = 0; 100 + u2 = 0; u2 = -100
u2 + v2 = 4; -100 + v2 = 4; v2 = 104
u2 + v5 = 3; -100 + v5 = 3; v5 = 103
u4 + v5 = 1; 103 + u4 = 1; u4 = -102
v1=3 | v2=104 | v3=8 | v4=13 | v5=103 | v6=100 | |
u1=0 | 3[10] | 20 | 8[40] | 13[20] | 4 | 100[10] |
u2=-100 | 4 | 4[30] | 18 | 14 | 3[10] | 0[20] |
u3=-5 | 10 | 4 | 18 | 8[30] | 6 | 0 |
u4=-102 | 7 | 19 | 17 | 10 | 1[60] | 100 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 104 > 20; ∆12 = 0 + 104 - 20 = 84
(1;5): 0 + 103 > 4; ∆15 = 0 + 103 - 4 = 99
(3;2): -5 + 104 > 4; ∆32 = -5 + 104 - 4 = 95
(3;5): -5 + 103 > 6; ∆35 = -5 + 103 - 6 = 92
(3;6): -5 + 100 > 0; ∆36 = -5 + 100 - 0 = 95
Выбираем максимальную оценку свободной клетки (1;5): 4
Для этого в перспективную клетку (1;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
1 | 3[10] | 20 | 8[40] | 13[20] | 4[+] | 100[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] | 100 | 60 |
Потребности | 10 | 30 | 40 | 50 | 70 | 30 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
1 | 3[10] | 20 | 8[40] | 13[20] | 4[10] | 100[0] | 80 |
2 | 4 | 4[30] | 18 | 14 | 3 | 0[30] | 60 |
3 | 10 | 4 | 18 | 8[30] | 6 | 0 | 30 |
4 | 7 | 19 | 17 | 10 | 1[60] | 100 | 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
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 1; 4 + u4 = 1; u4 = -3
u1 + v6 = 100; 0 + v6 = 100; v6 = 100
u2 + v6 = 0; 100 + u2 = 0; u2 = -100
u2 + v2 = 4; -100 + v2 = 4; v2 = 104
v1=3 | v2=104 | v3=8 | v4=13 | v5=4 | v6=100 | |
u1=0 | 3[10] | 20 | 8[40] | 13[20] | 4[10] | 100[0] |
u2=-100 | 4 | 4[30] | 18 | 14 | 3 | 0[30] |
u3=-5 | 10 | 4 | 18 | 8[30] | 6 | 0 |
u4=-3 | 7 | 19 | 17 | 10 | 1[60] | 100 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 104 > 20; ∆12 = 0 + 104 - 20 = 84
(3;2): -5 + 104 > 4; ∆32 = -5 + 104 - 4 = 95
(3;6): -5 + 100 > 0; ∆36 = -5 + 100 - 0 = 95
(4;2): -3 + 104 > 19; ∆42 = -3 + 104 - 19 = 82
Выбираем максимальную оценку свободной клетки (3;2): 4
Для этого в перспективную клетку (3;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
1 | 3[10] | 20 | 8[40] | 13[20][+] | 4[10] | 100[0][-] | 80 |
2 | 4 | 4[30][-] | 18 | 14 | 3 | 0[30][+] | 60 |
3 | 10 | 4[+] | 18 | 8[30][-] | 6 | 0 | 30 |
4 | 7 | 19 | 17 | 10 | 1[60] | 100 | 60 |
Потребности | 10 | 30 | 40 | 50 | 70 | 30 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 6) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
1 | 3[10] | 20 | 8[40] | 13[20] | 4[10] | 100 | 80 |
2 | 4 | 4[30] | 18 | 14 | 3 | 0[30] | 60 |
3 | 10 | 4[0] | 18 | 8[30] | 6 | 0 | 30 |
4 | 7 | 19 | 17 | 10 | 1[60] | 100 | 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
u3 + v2 = 4; -5 + v2 = 4; v2 = 9
u2 + v2 = 4; 9 + u2 = 4; u2 = -5
u2 + v6 = 0; -5 + v6 = 0; v6 = 5
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 1; 4 + u4 = 1; u4 = -3
v1=3 | v2=9 | v3=8 | v4=13 | v5=4 | v6=5 | |
u1=0 | 3[10] | 20 | 8[40] | 13[20] | 4[10] | 100 |
u2=-5 | 4 | 4[30] | 18 | 14 | 3 | 0[30] |
u3=-5 | 10 | 4[0] | 18 | 8[30] | 6 | 0 |
u4=-3 | 7 | 19 | 17 | 10 | 1[60] | 100 |
Опорный план является оптимальным.
Затраты составят:
F(x) = 3*10 + 8*40 + 13*20 + 4*10 + 4*30 + 0*30 + 8*30 + 1*60 = 1070