Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 270 + 230 + 200 + 250 = 950 ∑b = 170 + 210 + 200 + 170 + 200 = 950 модель транспортной задачи является закрытой. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 4 5 7 4[70] 3[200] 270
A2 9 8[30] 10[200] 8 4 230
A3 3[170] 4[30] 6 7 5 200
A4 8 7[150] 8 5[100] 4 250
Потребности 170 210 200 170 200
Ответ
Fmin=4750
X=17010900000300200002000080001700
Решение
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 4*70 + 3*200 + 8*30 + 10*200 + 3*170 + 4*30 + 7*150 + 5*100 = 5300 Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
1 2 3 4 5 Запасы
1 4[+] 5 7 4[70][-] 3[200] 270
2 9 8[30] 10[200] 8 4 230
3 3[170][-] 4[30][+] 6 7 5 200
4 8 7[150][-] 8 5[100][+] 4 250
Потребности 170 210 200 170 200
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;1): 0 + 5 > 4; ∆11 = 0 + 5 - 4 = 1 > 0 (1;2): 0 + 6 > 5; ∆12 = 0 + 6 - 5 = 1 > 0 (1;3): 0 + 8 > 7; ∆13 = 0 + 8 - 7 = 1 > 0 (2;5): 2 + 3 > 4; ∆25 = 2 + 3 - 4 = 1 > 0 (4;3): 1 + 8 > 8; ∆43 = 1 + 8 - 8 = 1 > 0 max(1,1,1,1,1) = 1 Выбираем максимальную оценку свободной клетки (1;1): 4 Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,1 → 1,4 → 4,4 → 4,2 → 3,2 → 3,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 70. Прибавляем 70 к объемам грузов, стоящих в плюсовых клетках и вычитаем 70 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 4; 0 + v1 = 4; v1 = 4 u3 + v1 = 3; 4 + u3 = 3; u3 = -1 u3 + v2 = 4; -1 + v2 = 4; v2 = 5 u2 + v2 = 8; 5 + u2 = 8; u2 = 3 u2 + v3 = 10; 3 + v3 = 10; v3 = 7 u4 + v2 = 7; 5 + u4 = 7; u4 = 2 u4 + v4 = 5; 2 + v4 = 5; v4 = 3 u1 + v5 = 3; 0 + v5 = 3; v5 = 3
1 2 3 4 5 Запасы
1 4[70][+] 5 7 4 3[200][-] 270
2 9 8[30][-] 10[200] 8 4[+] 230
3 3[100][-] 4[100][+] 6 7 5 200
4 8 7[80] 8 5[170] 4 250
Потребности 170 210 200 170 200
является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (2;5): 3 + 3 > 4; ∆25 = 3 + 3 - 4 = 2 > 0 (4;3): 2 + 7 > 8; ∆43 = 2 + 7 - 8 = 1 > 0 (4;5): 2 + 3 > 4; ∆45 = 2 + 3 - 4 = 1 > 0 max(2,1,1) = 2 Выбираем максимальную оценку свободной клетки (2;5): 4 Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,5 → 2,2 → 3,2 → 3,1 → 1,1 → 1,5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
. у = min (2, 2) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 4; 0 + v1 = 4; v1 = 4 u3 + v1 = 3; 4 + u3 = 3; u3 = -1 u3 + v2 = 4; -1 + v2 = 4; v2 = 5 u4 + v2 = 7; 5 + u4 = 7; u4 = 2 u4 + v4 = 5; 2 + v4 = 5; v4 = 3 u1 + v5 = 3; 0 + v5 = 3; v5 = 3 u2 + v5 = 4; 3 + u2 = 4; u2 = 1 u2 + v3 = 10; 1 + v3 = 10; v3 = 9
1 2 3 4 5 Запасы
1 4[100][+] 5 7 4 3[170][-] 270
2 9 8 10[200][-] 8 4[30][+] 230
3 3[70][-] 4[130][+] 6 7 5 200
4 8 7[80][-] 8[+] 5[170] 4 250
Потребности 170 210 200 170 200
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;3): 0 + 9 > 7; ∆13 = 0 + 9 - 7 = 2 > 0 (3;3): -1 + 9 > 6; ∆33 = -1 + 9 - 6 = 2 > 0 (4;3): 2 + 9 > 8; ∆43 = 2 + 9 - 8 = 3 > 0 (4;5): 2 + 3 > 4; ∆45 = 2 + 3 - 4 = 1 > 0 max(2,2,3,1) = 3 Выбираем максимальную оценку свободной клетки (4;3): 8 Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (4,3 → 4,2 → 3,2 → 3,1 → 1,1 → 1,5 → 2,5 → 2,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
