Имеются 3 пункта поставки однородного груза и 5 пунктов потребления . На пунктах груз находится соответственно в количествах условных единиц. В пункты требуется доставить соответственно единиц груза. Стоимость перевозки единицы груза (с учетом расстояний) из в определена матрицей . Требуется найти план закрепления потребителей и поставщиков, чтобы общие затраты на перевозки были минимальны.
9. 10.
Решение
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 300 + 360 + 400 = 1060 ∑b = 150 + 350 + 300 + 150 + 110 = 1060 модель транспортной задачи является закрытой.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 9 15 7[300] 20 3[0] 300
A2 8 6[100] 9 3[150] 2[110] 360
A3 10[150] 7[250] 11 15 20 400
Потребности 150 350 300 150 110
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 7*300 + 6*100 + 3*150 + 2*110 + 10*150 + 7*250 = 6620 Улучшение опорного плана. Проверим оптимальность опорного плана
. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
v1=10 v2=7 v3=7 v4=4 v5=3 Запасы
u1=0 9[+] 15 7[300] 20 3[0][-] 300
u2=-1 8 6[100][-] 9 3[150] 2[110][+] 360
u3=0 10[150][-] 7[250][+] 11 15 20 400
Потребности 150 350 300 150 110
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (1;1): 0 + 10 > 9; ∆11 = 0 + 10 - 9 = 1 > 0 (2;1): -1 + 10 > 8; ∆21 = -1 + 10 - 8 = 1 > 0 max(1,1) = 1 Выбираем максимальную оценку свободной клетки (1;1): 9 Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
v1=9 v2=6 v3=7 v4=3 v5=2 Запасы
u1=0 9[0] 15 7[300] 20 3 300
u2=0 8[+] 6[100][-] 9 3[150] 2[110] 360
u3=1 10[150][-] 7[250][+] 11 15 20 400
Потребности 150 350 300 150 110
Проверим оптимальность опорного плана