Решение транспортной задачи методом северо-западного угла

Имеются три пункта отправления А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

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

загрузка...