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

Задача. Имеются три пункта отправления А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. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₁ + v₃ = 8; 0 + v₃ = 8; v₃ = 8
u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13
u₃ + v₄ = 8; 13 + u₃ = 8; u₃ = -5
u₁ + v₆ = 100; 0 + v₆ = 100; v₆ = 100
u₂ + v₆ = 0; 100 + u₂ = 0; u₂ = -100
u₂ + v₂ = 4; -100 + v₂ = 4; v₂ = 104
u₂ + v₅ = 3; -100 + v₅ = 3; v₅ = 103
u₄ + v₅ = 1; 103 + u₄ = 1; u₄ = -102

	v₁=3	v₂=104	v₃=8	v₄=13	v₅=103	v₆=100
u₁=0	3[10]	20	8[40]	13[20]	4	100[10]
u₂=-100	4	4[30]	18	14	3[10]	0[20]
u₃=-5	10	4	18	8[30]	6	0
u₄=-102	7	19	17	10	1[60]	100

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;2): 0 + 104 > 20; ∆₁₂ = 0 + 104 - 20 = 84
(1;5): 0 + 103 > 4; ∆₁₅ = 0 + 103 - 4 = 99
(3;2): -5 + 104 > 4; ∆₃₂ = -5 + 104 - 4 = 95
(3;5): -5 + 103 > 6; ∆₃₅ = -5 + 103 - 6 = 92
(3;6): -5 + 100 > 0; ∆₃₆ = -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. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₁ + v₃ = 8; 0 + v₃ = 8; v₃ = 8
u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13
u₃ + v₄ = 8; 13 + u₃ = 8; u₃ = -5
u₁ + v₅ = 4; 0 + v₅ = 4; v₅ = 4
u₄ + v₅ = 1; 4 + u₄ = 1; u₄ = -3
u₁ + v₆ = 100; 0 + v₆ = 100; v₆ = 100
u₂ + v₆ = 0; 100 + u₂ = 0; u₂ = -100
u₂ + v₂ = 4; -100 + v₂ = 4; v₂ = 104

	v₁=3	v₂=104	v₃=8	v₄=13	v₅=4	v₆=100
u₁=0	3[10]	20	8[40]	13[20]	4[10]	100[0]
u₂=-100	4	4[30]	18	14	3	0[30]
u₃=-5	10	4	18	8[30]	6	0
u₄=-3	7	19	17	10	1[60]	100

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;2): 0 + 104 > 20; ∆₁₂ = 0 + 104 - 20 = 84
(3;2): -5 + 104 > 4; ∆₃₂ = -5 + 104 - 4 = 95
(3;6): -5 + 100 > 0; ∆₃₆ = -5 + 100 - 0 = 95
(4;2): -3 + 104 > 19; ∆₄₂ = -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. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₁ + v₃ = 8; 0 + v₃ = 8; v₃ = 8
u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13
u₃ + v₄ = 8; 13 + u₃ = 8; u₃ = -5
u₃ + v₂ = 4; -5 + v₂ = 4; v₂ = 9
u₂ + v₂ = 4; 9 + u₂ = 4; u₂ = -5
u₂ + v₆ = 0; -5 + v₆ = 0; v₆ = 5
u₁ + v₅ = 4; 0 + v₅ = 4; v₅ = 4
u₄ + v₅ = 1; 4 + u₄ = 1; u₄ = -3

	v₁=3	v₂=9	v₃=8	v₄=13	v₅=4	v₆=5
u₁=0	3[10]	20	8[40]	13[20]	4[10]	100
u₂=-5	4	4[30]	18	14	3	0[30]
u₃=-5	10	4[0]	18	8[30]	6	0
u₄=-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

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

Правила ввода данных

Поиск

Процесс

Сообщение