Решение транспортной задачи методом северо-западного угла
Имеются три пункта отправления А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 | 6 | 6 | 8 | 5 | 4 | 3 | 130 |
| 2 | 2 | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3 | 5 | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5 | 4 | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 130 + 55 + 80 + 65 + 135 = 465
∑ b = 130 + 75 + 65 + 60 + 75 + 60 = 465
Условие баланса соблюдается. Запасы равны потребностям.
Занесем исходные данные в распределительную таблицу.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4 | 3 | 130 |
| 2 | 2 | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3 | 5 | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5 | 4 | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[130] | 6 | 8 | 5 | 4 | 3 | 130 |
| 2 | 2 | 4[55] | 3 | 9 | 8 | 5 | 55 |
| 3 | 3 | 5[20] | 7[60] | 9 | 6 | 11 | 80 |
| 4 | 3 | 5 | 4[5] | 4[60] | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2[75] | 8[60] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[55] | 6[75] | 8 | 5 | 4 | 3 | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[20] | 5 | 7[60] | 9 | 6 | 11 | 80 |
| 4 | 3 | 5 | 4[5] | 4[60] | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2[75] | 8[60] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[65] | 6 | 8[65] | 5 | 4 | 3 | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[10] | 5[70] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[5] | 4 | 4[60] | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2[75] | 8[60] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[70] | 6 | 8 | 5[60] | 4 | 3 | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[5] | 5[75] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5 | 4[65] | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2[75] | 8[60] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[55] | 6 | 8 | 5 | 4[75] | 3 | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[20] | 5[60] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[15] | 4[50] | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6[15] | 3[60] | 2 | 8[60] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 10, а должно быть m + n - 1 = 10. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 6; 0 + v1 = 6; v1 = 6
u2 + v1 = 2; 6 + u2 = 2; u2 = -4
u3 + v1 = 3; 6 + u3 = 3; u3 = -3
u3 + v2 = 5; -3 + v2 = 5; v2 = 8
u4 + v2 = 5; 8 + u4 = 5; u4 = -3
u4 + v3 = 4; -3 + v3 = 4; v3 = 7
u5 + v3 = 6; 7 + u5 = 6; u5 = -1
u5 + v4 = 3; -1 + v4 = 3; v4 = 4
u5 + v6 = 8; -1 + v6 = 8; v6 = 9
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
| v1=6 | v2=8 | v3=7 | v4=4 | v5=4 | v6=9 | |
| u1=0 | 6[55] | 6 | 8 | 5 | 4[75] | 3 |
| u2=-4 | 2[55] | 4 | 3 | 9 | 8 | 5 |
| u3=-3 | 3[20] | 5[60] | 7 | 9 | 6 | 11 |
| u4=-3 | 3 | 5[15] | 4[50] | 4 | 2 | 1 |
| u5=-1 | 2 | 5 | 6[15] | 3[60] | 2 | 8[60] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 8 > 6; ∆12 = 0 + 8 - 6 = 2
(1;6): 0 + 9 > 3; ∆16 = 0 + 9 - 3 = 6
(4;6): -3 + 9 > 1; ∆46 = -3 + 9 - 1 = 5
(5;1): -1 + 6 > 2; ∆51 = -1 + 6 - 2 = 3
(5;2): -1 + 8 > 5; ∆52 = -1 + 8 - 5 = 2
(5;5): -1 + 4 > 2; ∆55 = -1 + 4 - 2 = 1
Выбираем максимальную оценку свободной клетки (1;6): 3
Для этого в перспективную клетку (1;6) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[55][-] | 6 | 8 | 5 | 4[75] | 3[+] | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[20][+] | 5[60][-] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[15][+] | 4[50][-] | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6[15][+] | 3[60] | 2 | 8[60][-] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[5] | 6 | 8 | 5 | 4[75] | 3[50] | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[70] | 5[10] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[65] | 4 | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6[65] | 3[60] | 2 | 8[10] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 6; 0 + v1 = 6; v1 = 6
u2 + v1 = 2; 6 + u2 = 2; u2 = -4
u3 + v1 = 3; 6 + u3 = 3; u3 = -3
u3 + v2 = 5; -3 + v2 = 5; v2 = 8
u4 + v2 = 5; 8 + u4 = 5; u4 = -3
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
u5 + v6 = 8; 3 + u5 = 8; u5 = 5
u5 + v3 = 6; 5 + v3 = 6; v3 = 1
u5 + v4 = 3; 5 + v4 = 3; v4 = -2
| v1=6 | v2=8 | v3=1 | v4=-2 | v5=4 | v6=3 | |
| u1=0 | 6[5] | 6 | 8 | 5 | 4[75] | 3[50] |
| u2=-4 | 2[55] | 4 | 3 | 9 | 8 | 5 |
| u3=-3 | 3[70] | 5[10] | 7 | 9 | 6 | 11 |
| u4=-3 | 3 | 5[65] | 4 | 4 | 2 | 1 |
| u5=5 | 2 | 5 | 6[65] | 3[60] | 2 | 8[10] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 8 > 6; ∆12 = 0 + 8 - 6 = 2
(5;1): 5 + 6 > 2; ∆51 = 5 + 6 - 2 = 9
(5;2): 5 + 8 > 5; ∆52 = 5 + 8 - 5 = 8
(5;5): 5 + 4 > 2; ∆55 = 5 + 4 - 2 = 7
Выбираем максимальную оценку свободной клетки (5;1): 2
Для этого в перспективную клетку (5;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6[5][-] | 6 | 8 | 5 | 4[75] | 3[50][+] | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[70] | 5[10] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[65] | 4 | 4 | 2 | 1 | 65 |
| 5 | 2[+] | 5 | 6[65] | 3[60] | 2 | 8[10][-] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4[75] | 3[55] | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[70] | 5[10] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[65] | 4 | 4 | 2 | 1 | 65 |
| 5 | 2[5] | 5 | 6[65] | 3[60] | 2 | 8[5] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
u5 + v6 = 8; 3 + u5 = 8; u5 = 5
u5 + v1 = 2; 5 + v1 = 2; v1 = -3
u2 + v1 = 2; -3 + u2 = 2; u2 = 5
u3 + v1 = 3; -3 + u3 = 3; u3 = 6
u3 + v2 = 5; 6 + v2 = 5; v2 = -1
u4 + v2 = 5; -1 + u4 = 5; u4 = 6
u5 + v3 = 6; 5 + v3 = 6; v3 = 1
u5 + v4 = 3; 5 + v4 = 3; v4 = -2
| v1=-3 | v2=-1 | v3=1 | v4=-2 | v5=4 | v6=3 | |
| u1=0 | 6 | 6 | 8 | 5 | 4[75] | 3[55] |
| u2=5 | 2[55] | 4 | 3 | 9 | 8 | 5 |
| u3=6 | 3[70] | 5[10] | 7 | 9 | 6 | 11 |
| u4=6 | 3 | 5[65] | 4 | 4 | 2 | 1 |
| u5=5 | 2[5] | 5 | 6[65] | 3[60] | 2 | 8[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;3): 5 + 1 > 3; ∆23 = 5 + 1 - 3 = 3
(2;5): 5 + 4 > 8; ∆25 = 5 + 4 - 8 = 1
(2;6): 5 + 3 > 5; ∆26 = 5 + 3 - 5 = 3
(3;5): 6 + 4 > 6; ∆35 = 6 + 4 - 6 = 4
(4;3): 6 + 1 > 4; ∆43 = 6 + 1 - 4 = 3
(4;5): 6 + 4 > 2; ∆45 = 6 + 4 - 2 = 8
(4;6): 6 + 3 > 1; ∆46 = 6 + 3 - 1 = 8
(5;5): 5 + 4 > 2; ∆55 = 5 + 4 - 2 = 7
Выбираем максимальную оценку свободной клетки (4;5): 2
Для этого в перспективную клетку (4;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4[75][-] | 3[55][+] | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[70][-] | 5[10][+] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[65][-] | 4 | 4 | 2[+] | 1 | 65 |
| 5 | 2[5][+] | 5 | 6[65] | 3[60] | 2 | 8[5][-] | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 6) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4[70] | 3[60] | 130 |
| 2 | 2[55] | 4 | 3 | 9 | 8 | 5 | 55 |
| 3 | 3[65] | 5[15] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[60] | 4 | 4 | 2[5] | 1 | 65 |
| 5 | 2[10] | 5 | 6[65] | 3[60] | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v2 = 5; -2 + v2 = 5; v2 = 7
u3 + v2 = 5; 7 + u3 = 5; u3 = -2
u3 + v1 = 3; -2 + v1 = 3; v1 = 5
u2 + v1 = 2; 5 + u2 = 2; u2 = -3
u5 + v1 = 2; 5 + u5 = 2; u5 = -3
u5 + v3 = 6; -3 + v3 = 6; v3 = 9
u5 + v4 = 3; -3 + v4 = 3; v4 = 6
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
| v1=5 | v2=7 | v3=9 | v4=6 | v5=4 | v6=3 | |
| u1=0 | 6 | 6 | 8 | 5 | 4[70] | 3[60] |
| u2=-3 | 2[55] | 4 | 3 | 9 | 8 | 5 |
| u3=-2 | 3[65] | 5[15] | 7 | 9 | 6 | 11 |
| u4=-2 | 3 | 5[60] | 4 | 4 | 2[5] | 1 |
| u5=-3 | 2[10] | 5 | 6[65] | 3[60] | 2 | 8 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 7 > 6; ∆12 = 0 + 7 - 6 = 1
(1;3): 0 + 9 > 8; ∆13 = 0 + 9 - 8 = 1
(1;4): 0 + 6 > 5; ∆14 = 0 + 6 - 5 = 1
(2;3): -3 + 9 > 3; ∆23 = -3 + 9 - 3 = 3
(4;3): -2 + 9 > 4; ∆43 = -2 + 9 - 4 = 3
Выбираем максимальную оценку свободной клетки (2;3): 3
Для этого в перспективную клетку (2;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4[70] | 3[60] | 130 |
| 2 | 2[55][-] | 4 | 3[+] | 9 | 8 | 5 | 55 |
| 3 | 3[65] | 5[15] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[60] | 4 | 4 | 2[5] | 1 | 65 |
| 5 | 2[10][+] | 5 | 6[65][-] | 3[60] | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 55. Прибавляем 55 к объемам грузов, стоящих в плюсовых клетках и вычитаем 55 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4[70] | 3[60] | 130 |
| 2 | 2 | 4 | 3[55] | 9 | 8 | 5 | 55 |
| 3 | 3[65] | 5[15] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[60] | 4 | 4 | 2[5] | 1 | 65 |
| 5 | 2[65] | 5 | 6[10] | 3[60] | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v2 = 5; -2 + v2 = 5; v2 = 7
u3 + v2 = 5; 7 + u3 = 5; u3 = -2
u3 + v1 = 3; -2 + v1 = 3; v1 = 5
u5 + v1 = 2; 5 + u5 = 2; u5 = -3
u5 + v3 = 6; -3 + v3 = 6; v3 = 9
u2 + v3 = 3; 9 + u2 = 3; u2 = -6
u5 + v4 = 3; -3 + v4 = 3; v4 = 6
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
| v1=5 | v2=7 | v3=9 | v4=6 | v5=4 | v6=3 | |
| u1=0 | 6 | 6 | 8 | 5 | 4[70] | 3[60] |
| u2=-6 | 2 | 4 | 3[55] | 9 | 8 | 5 |
| u3=-2 | 3[65] | 5[15] | 7 | 9 | 6 | 11 |
| u4=-2 | 3 | 5[60] | 4 | 4 | 2[5] | 1 |
| u5=-3 | 2[65] | 5 | 6[10] | 3[60] | 2 | 8 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 7 > 6; ∆12 = 0 + 7 - 6 = 1
(1;3): 0 + 9 > 8; ∆13 = 0 + 9 - 8 = 1
(1;4): 0 + 6 > 5; ∆14 = 0 + 6 - 5 = 1
(4;3): -2 + 9 > 4; ∆43 = -2 + 9 - 4 = 3
Выбираем максимальную оценку свободной клетки (4;3): 4
Для этого в перспективную клетку (4;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4[70] | 3[60] | 130 |
| 2 | 2 | 4 | 3[55] | 9 | 8 | 5 | 55 |
| 3 | 3[65][-] | 5[15][+] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[60][-] | 4[+] | 4 | 2[5] | 1 | 65 |
| 5 | 2[65][+] | 5 | 6[10][-] | 3[60] | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4[70] | 3[60] | 130 |
| 2 | 2 | 4 | 3[55] | 9 | 8 | 5 | 55 |
| 3 | 3[55] | 5[25] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[50] | 4[10] | 4 | 2[5] | 1 | 65 |
| 5 | 2[75] | 5 | 6 | 3[60] | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v2 = 5; -2 + v2 = 5; v2 = 7
u3 + v2 = 5; 7 + u3 = 5; u3 = -2
u3 + v1 = 3; -2 + v1 = 3; v1 = 5
u5 + v1 = 2; 5 + u5 = 2; u5 = -3
u5 + v4 = 3; -3 + v4 = 3; v4 = 6
u4 + v3 = 4; -2 + v3 = 4; v3 = 6
u2 + v3 = 3; 6 + u2 = 3; u2 = -3
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
| v1=5 | v2=7 | v3=6 | v4=6 | v5=4 | v6=3 | |
| u1=0 | 6 | 6 | 8 | 5 | 4[70] | 3[60] |
| u2=-3 | 2 | 4 | 3[55] | 9 | 8 | 5 |
| u3=-2 | 3[55] | 5[25] | 7 | 9 | 6 | 11 |
| u4=-2 | 3 | 5[50] | 4[10] | 4 | 2[5] | 1 |
| u5=-3 | 2[75] | 5 | 6 | 3[60] | 2 | 8 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 7 > 6; ∆12 = 0 + 7 - 6 = 1
(1;4): 0 + 6 > 5; ∆14 = 0 + 6 - 5 = 1
Выбираем максимальную оценку свободной клетки (1;2): 6
Для этого в перспективную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6[+] | 8 | 5 | 4[70][-] | 3[60] | 130 |
| 2 | 2 | 4 | 3[55] | 9 | 8 | 5 | 55 |
| 3 | 3[55] | 5[25] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5[50][-] | 4[10] | 4 | 2[5][+] | 1 | 65 |
| 5 | 2[75] | 5 | 6 | 3[60] | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 2) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6[50] | 8 | 5 | 4[20] | 3[60] | 130 |
| 2 | 2 | 4 | 3[55] | 9 | 8 | 5 | 55 |
| 3 | 3[55] | 5[25] | 7 | 9 | 6 | 11 | 80 |
| 4 | 3 | 5 | 4[10] | 4 | 2[55] | 1 | 65 |
| 5 | 2[75] | 5 | 6 | 3[60] | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u3 + v2 = 5; 6 + u3 = 5; u3 = -1
u3 + v1 = 3; -1 + v1 = 3; v1 = 4
u5 + v1 = 2; 4 + u5 = 2; u5 = -2
u5 + v4 = 3; -2 + v4 = 3; v4 = 5
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v3 = 4; -2 + v3 = 4; v3 = 6
u2 + v3 = 3; 6 + u2 = 3; u2 = -3
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
| v1=4 | v2=6 | v3=6 | v4=5 | v5=4 | v6=3 | |
| u1=0 | 6 | 6[50] | 8 | 5 | 4[20] | 3[60] |
| u2=-3 | 2 | 4 | 3[55] | 9 | 8 | 5 |
| u3=-1 | 3[55] | 5[25] | 7 | 9 | 6 | 11 |
| u4=-2 | 3 | 5 | 4[10] | 4 | 2[55] | 1 |
| u5=-2 | 2[75] | 5 | 6 | 3[60] | 2 | 8 |
Опорный план является оптимальным.
Затраты составят:
F(x) = 6*50 + 4*20 + 3*60 + 3*55 + 3*55 + 5*25 + 4*10 + 2*55 + 2*75 + 3*60 = 1495
Составить такой план перевозок, при котором общая стоимость была бы минимальной.
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов.
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4 | 3 | 130 |
| 2 | 2 | 4 | 3 | - | 8 | 5 | 55 |
| 3 | 3 | 5 | 7 | - | 6 | 11 | 80 |
| 4 | 3 | 5 | 4 | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Решение получаем с помощью калькулятора. Максимальная стоимость в данной матрице тарифов равна 11. Поэтому вместо прочерков достаточно указать значение в 2 раза больше заданного. Например, 22 (2*11).
| 1 | 2 | 3 | 4 | 5 | 6 | Запасы | |
| 1 | 6 | 6 | 8 | 5 | 4 | 3 | 130 |
| 2 | 2 | 4 | 3 | 22 | 8 | 5 | 55 |
| 3 | 3 | 5 | 7 | 22 | 6 | 11 | 80 |
| 4 | 3 | 5 | 4 | 4 | 2 | 1 | 65 |
| 5 | 2 | 5 | 6 | 3 | 2 | 8 | 135 |
| Потребности | 130 | 75 | 65 | 60 | 75 | 60 |
Пример №3.
Решение задачи методом северо–западного угла и потенциалов
Имеются три пункта отправления A 1 , A2, A 3 однородного груза и пять пунктов B1,B2,B3,B4,B5 его назначения. На пунктах A1,A2, A3 груз находится в количестве a1, a2, a3 тонн соответственно. В пункты B1,B2,B3,B4,B5 требуется доставить соответственно b1,b2,b3,b4,b5 тонн груза. Расстояния в сотнях километров между пунктами отправления и назначения приведены в матрице D:| Пункты отправления | Пункты назначения | ||||
| B1 | B2 | B3 | B4 | B5 | |
| A1 | d11 | d12 | d13 | d14 | d15 |
| A2 | d21 | d22 | d23 | d24 | d25 |
| A3 | d31 | d32 | d33 | d34 | d35 |
Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.
Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно–километрах; 2) для решения задачи использовать методы северо–западного угла и потенциалов.
