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

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

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

загрузка...