Транспортная задача
Автор: wert85 • Январь 23, 2020 • Контрольная работа • 629 Слов (3 Страниц) • 376 Просмотры
1 | 2 | 3 | Запасы | |
1 | 3 | 4 | 1 | 90 |
2 | 5 | 7 | 2 | 70 |
3 | 6 | 4 | 5 | 60 |
4 | 4 | 3 | 1 | 50 |
Потребности | 100 | 110 | 120 |
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 90 + 70 + 60 + 50 = 270
∑b = 100 + 110 + 120 = 330
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 60 (270—330). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
1 | 2 | 3 | Запасы | |
1 | 3 | 4 | 1 | 90 |
2 | 5 | 7 | 2 | 70 |
3 | 6 | 4 | 5 | 60 |
4 | 4 | 3 | 1 | 50 |
5 | 0 | 0 | 0 | 60 |
Потребности | 100 | 110 | 120 |
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
1 | 2 | 3 | Запасы | |
1 | 3 | 4 | 1[90] | 90 |
2 | 5[70] | 7 | 2 | 70 |
3 | 6 | 4[60] | 5 | 60 |
4 | 4 | 3[20] | 1[30] | 50 |
5 | 0[30] | 0[30] | 0 | 60 |
Потребности | 100 | 110 | 120 |
Значение целевой функции для этого опорного плана равно:
F(x) = 1*90 + 5*70 + 4*60 + 3*20 + 1*30 + 0*30 + 0*30 = 770.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 1; 0 + v3 = 1; v3 = 1
u4 + v3 = 1; 1 + u4 = 1; u4 = 0
u4 + v2 = 3; 0 + v2 = 3; v2 = 3
u3 + v2 = 4; 3 + u3 = 4; u3 = 1
u5 + v2 = 0; 3 + u5 = 0; u5 = -3
u5 + v1 = 0; -3 + v1 = 0; v1 = 3
u2 + v1 = 5; 3 + u2 = 5; u2 = 2
v1=3 | v2=3 | v3=1 | |
u1=0 | 3 | 4 | 1[90] |
u2=2 | 5[70] | 7 | 2 |
u3=1 | 6 | 4[60] | 5 |
u4=0 | 4 | 3[20] | 1[30] |
u5=-3 | 0[30] | 0[30] | 0 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;3): 2 + 1 > 2; ∆23 = 2 + 1 - 2 = 1.
Проведем перестановку по циклу: 2,3 → 2,1 → 5,1 → 5,2 → 4,2 → 4,3.
В результате получим новый опорный план.
1 | 2 | 3 | Запасы | |
1 | 3 | 4 | 1[90] | 90 |
2 | 5[40] | 7 | 2[30] | 70 |
3 | 6 | 4[60] | 5 | 60 |
4 | 4 | 3[50] | 1[0] | 50 |
5 | 0[60] | 0 | 0 | 60 |
Потребности | 100 | 110 | 120 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 1; 0 + v3 = 1; v3 = 1
u2 + v3 = 2; 1 + u2 = 2; u2 = 1
u2 + v1 = 5; 1 + v1 = 5; v1 = 4
u5 + v1 = 0; 4 + u5 = 0; u5 = -4
u4 + v3 = 1; 1 + u4 = 1; u4 = 0
u4 + v2 = 3; 0 + v2 = 3; v2 = 3
u3 + v2 = 4; 3 + u3 = 4; u3 = 1
...