задачи / 11

Транспортная задача. Copyright © Semestr.RU Математическая модель транспортной задачи: F = ∑∑c_ijx_ij, (1) при условиях: ∑x_ij = a_i, i = 1,2,…, m, (2) ∑x_ij = b_j, j = 1,2,…, n, (3) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	Запасы
1	4	1	2	60
2	1	4	7	36
3	4	5	2	100
4	1	5	5	50
Потребности	144	76	136

Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 60 + 36 + 100 + 50 = 246 ∑b = 144 + 76 + 136 = 356 Занесем исходные данные в распределительную таблицу.

	1	2	3	Запасы
1	4	1	2	60
2	1	4	7	36
3	4	5	2	100
4	1	5	5	50
5	0	0	0	110
Потребности	144	76	136

Этап I. Поиск первого опорного плана. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	1	2	3	Запасы
1	4	1[60]	2	60
2	1[36]	4	7	36
3	4	5	2[100]	100
4	1[50]	5	5	50
5	0[58]	0[16]	0[36]	110
Потребности	144	76	136

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=1	v3=1
u1=0	4	1[60]	2
u2=0	1[36]	4	7
u3=1	4	5	2[100]
u4=0	1[50]	5	5
u5=-1	0[58]	0[16]	0[36]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij. Минимальные затраты составят: F(x) = 1*60 + 1*36 + 2*100 + 1*50 + 0*58 + 0*16 + 0*36 = 346