Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 200 + 450 + 250 = 900 ∑b = 100 + 125 + 325 + 250 + 100 = 900 модель транспортной задачи является закрытой.
B1 B2 B3 B4 B5 Запасы
A1 5 8 7 10 3 200
A2 4 2 2 5 6 450
A3 7 3 5 9 2 250
Потребности 100 125 325 250 100
Решение
Поиск первого опорного плана. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 5[100] 8 7 10[100] 3[0] 200
A2 4 2[125] 2[325] 5 6 450
A3 7 3 5 9[150] 2[100] 250
Потребности 100 125 325 250 100
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. F(x) = 5*100 + 10*100 + 2*125 + 2*325 + 9*150 + 2*100 = 3950
Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj
v1=5 v2=4 v3=4 v4=10 v5=3
u1=0 5[100] 8 7 10[100] 3
u2=-2 4 2[125] 2[325] 5 6
u3=-1 7 3[0] 5 9[150] 2[100]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (2;4): -2 + 10 > 5; ∆24 = -2 + 10 - 5 = 3 > 0 Выбираем максимальную оценку свободной клетки (2;4): 5 Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 5[100] 8 7 10[100] 3 200
2 4 2[125][-] 2[325] 5[+] 6 450
3 7 3[0][+] 5 9[150][-] 2[100] 250
Потребности 100 125 325 250 100
Цикл приведен в таблице (2,4 → 2,2 → 3,2 → 3,4). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
. у = min (2, 2) = 125. Прибавляем 125 к объемам грузов, стоящих в плюсовых клетках и вычитаем 125 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
v1=5 v2=4 v3=7 v4=10 v5=3
u1=0 5[100] 8 7 10[100] 3
u2=-5 4 2 2[325] 5[125] 6
u3=-1 7 3[125] 5 9[25] 2[100]
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 5; 0 + v1 = 5; v1 = 5 u1 + v4 = 10; 0 + v4 = 10; v4 = 10 u2 + v4 = 5; 10 + u2 = 5; u2 = -5 u2 + v3 = 2; -5 + v3 = 2; v3 = 7 u3 + v4 = 9; 10 + u3 = 9; u3 = -1 u3 + v2 = 3; -1 + v2 = 3; v2 = 4 u3 + v5 = 2; -1 + v5 = 2; v5 = 3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (3;3): -1 + 7 > 5; ∆33 = -1 + 7 - 5 = 1 > 0 Выбираем максимальную оценку свободной клетки (3;3): 5 Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 5[100] 8 7 10[100] 3 200
2 4 2 2[325][-] 5[125][+] 6 450
3 7 3[125] 5[+] 9[25][-] 2[100] 250
Потребности 100 125 325 250 100
Цикл приведен в таблице (3,3 → 3,4 → 2,4 → 2,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
