Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспортной задачи
Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij, (3;3): 6 + 18 > 23
Выбираем максимальную оценку свободной клетки (3;3): 23
Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 B5 Запасы A1 28 27[100] 18[30] 27 24[70] 200 A2 18[190] 26 27 32 21[60] 250 A3 27 33 23[90] 31[110] 34 200 Потреб. 190 100 120 110 130 Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij (Алгоритм нахождения потенциалов описан выше).
v1=0 v2=27 v3=18 v4=26 v5=24 u1=0 28 27[100] 18[30] 27 24[70] u2=-3 18[190] 26 27 32 21[60] u3=5 27 33 23[90] 31[110] 34 В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Подсчитаем затраты на распределение товаров:
F = 27*100 + 18*30 + 24*70 + 18*190 + 21*60 + 23*90 + 31*110 = 15080
Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15080рублей.
2.5Метод аппроксимации Фогеля
Используя построенную матрицу тарифов, найдём оптимальный опорный план методом аппроксимации Фогеля.
B1 B2 B3 B4 B5 Запасы A1 28 27 18 27 24 200 A2 18 26 27 32 21 250 A3 27 33 23 31 34 200 Потребности 190 100 120 110 130 Проверим необходимое и достаточное условие разрешимости задачи.
Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:
B1 B2 B3 B4 B5 Запасы Δcij A1 28 27[100] 18 27[30] 24[70] 200 6,6,3,0 A2 18[190] 26 27 32 21[60] 250 3,5,5 A3 27 33 23[120] 31[80] 34 200 4,8,2,2 Потреб. 190 100 120 110 130 Δcij 9 1,6 5 4,4 3,10 Для нахождения опорного плана данным методом нужно найти разность между наименьшими элементами в столбцах и строках. Затем определяем наибольшую разность(Δcij). Дальше находим минимальный тариф в столбце (или строке) которому принадлежит Δcij, и отдаём ему сколько можно отдать : это тариф [A2;B1]. Исключаем из вычислений первый столбец .
Другие рефераты на тему «Экономико-математическое моделирование»:
Поиск рефератов
Последние рефераты раздела
Скачать реферат