Метод аппроксимации Фогеля
Данный метод состоит в следующем: 1. На каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы; 2. Находят max Δcij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность. Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям. Данный метод в ряде задач приводит к оптимальному плану.
ГЛАВА 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ Постановка задачи Имеются три пункта поставки мониторов: Склад №1, Склад №2, Склад №3. И пять магазинов: Магазин "Терабайт", Магазин "Лидер", Магазин "Эксперт", Магазин "Ока-сервис", "Владимирский рынок", потребления этого товара. Найти оптимальный распределения товаров с минимальными затратами. Дано: Склад №1=200 шт. Склад №2=250шт. Склад №3=200шт. Требуется доставить штук: Магазин "Терабайт"= 190шт. Магазин "Лидер"= 100 шт. Магазин "Эксперт" = 120 шт. Магазин "Ока-сервис" =110 шт. "Владимирский рынок" =130 шт.
Сетка тарифов:
Построим для данной задачи матрицу тарифов, по которой будет происходить поиск оптимального плана распределения товаров между магазинами. Для более удобного решения задачи обозначим магазины и товары переменными: Магазины: Магазин "Терабайт"= B1 Магазин "Лидер"= B2 Магазин "Эксперт" = B3 Магазин "Ока-сервис" = B4 "Владимирский рынок" = B5 Товары: Склад №1= A1 Склад №2 = A2 Склад №3= A3 Тогда матрица будет выглядеть так:
Следуя данной модели можно найти опорный план и решение поставленной задачи.
2.2 Нахождение первоначального плана методом северо-западного угла Используя построенную матрицу тарифов найдём оптимальный опорный план методом северо-западного угла.
Проверим необходимое и достаточное условие разрешимости задачи.
Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:
Решение задачи методом северо-западного угла всегда начинается с левого, верхнего тарифа([A1;B1]). Полностью удовлетворяем потребность данного тарифа. Исключаем первый столбец. Дальше смотрим если запасы ещё остались, рассматриваем рядом стоящий тариф ([A2;B1]), если нет, то исключаем и первую верхнею строк. И рассматриваем следующий тариф по аналогичной схеме. В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Подсчитаем затраты на распределение товаров:
F=28*190+27*10+26*90+27*120+32*40+31*70+34*130=19040
Результат: Затраты на распределение товаров между магазинами найденные методом северо-западного угла составят 19040 рублей. 2.3 Нахождение первоначального плана методом наименьшей стоимости Используя построенную матрицу тарифов, найдём оптимальный опорный план методом наименьшей стоимости.
Проверим необходимое и достаточное условие разрешимости задачи.
Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:
Для решения задачи методом наименьшей стоимости сначала из все матрицы тарифов выбираем наименьший тариф ([A2;B1]). Полностью удовлетворяем его потребность. Исключаем из решения столбец в котором он находился. Ищем следующий минимальный тариф ([A2;B3]). Удовлетворяем его потребности. Исключаем из решения столбец в котором он находился. Дальше продолжаем до тех пор, пока все запасы не будут розданы. В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Подсчитаем затраты на распределение товаров:
F=27*10+18*120+24*70+18*190+21*60+33*90+31*110=15170
Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15170 рублей.
Метод потенциалов Для решения транспортной задачи сначала надо найти опорный план методом северо-западного угла и методом наименьшей стоимости, и из них выбрать метод при котором затраты на распределения товаров минимальны. Для данной задачи минимальным является метод наименьшей стоимости. Опорный метод этого плана и будем использовать для решения задачи методом потенциалов:
Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij Для этого построим систему уравнений:
Из этой системы уравнений находим потенциалы , полагая, что u1 = 0: v1=0, v2=27, v3=18, v4=25, v5=24, u1=0, u1=-3, u3=6
Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij, (3;3): 6 + 18 > 23 Выбираем максимальную оценку свободной клетки (3;3): 23 Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij (Алгоритм нахождения потенциалов описан выше).
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Подсчитаем затраты на распределение товаров:
F = 27*100 + 18*30 + 24*70 + 18*190 + 21*60 + 23*90 + 31*110 = 15080
Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15080рублей.
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (185)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |