Транспортная задача линейного программирования.
Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеется m пунктов отправления: i = 1 ÷ m Для каждого пункта известны объёмы отправления:Q1, Q2…Qm. Имеется n пунктов назначения; j=1 ÷ n Известна потребность грузов в каждом пункте: V1, V2…Vn. Задана матрица стоимостей доставки (или расстояний) по каждому варианту Ci j (Li j ) Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого i – ого пункта отправления (от поставщика) в каждый j – пункт назначения(до потребителя) Xi j c min транспортными издержками (или при min общем грузообороте)
Математическая постановка транспортной задачи Искомая переменная -
В общем виде данные представляются в таблице
Для того, чтобы транспортная задача решалась она должна быть закрытой, т. е. должно выполнятся условие: Если задача не закрыта, то её необходимо привести к закрытой форме. В случае, если потребности по пунктам назначения превышают запасы пунктов отправления, вводится фиктивный поставщик с недостающим объёмом отправления. В случае, если запасы поставщиков превышают запасы потребителей, вводится фиктивный потребитель с необходимым объёмом потребления. Транспортной задаче присущи следующие особенности: - распределению подлежат однородные ресурсы; - условия задачи описываются только равенствами; - все переменные выражаются в одинаковых единицах измерения; - во всех равенствах коэффициенты при переменных =1; -каждая неизвестная встречается только в 2-х равенствах системы ограничений.
Алгоритм метода потенциалов.
Решение задачи методом потенциалов включает следующие этапы: 1. Разработка начального плана; 2. Расчёт потенциалов; 3. Проверка плана на оптимальность; 4. Поиск max звена не оптимальности (если условие оптимальности было нарушено); 5. Составление контура перераспределения ресурсов; 6. Определение min элемента в контуре перераспределения ресурсов; 7. Получение нового плана. Описанная процедура повторяется несколько раз (итераций) пока не будет найдено оптимальное решение. Существует несколько методов отыскания начального плана: - метод северо-западного угла: - метод min стоимости(элемента).
Вычислительный алгоритм метода потенциалов рассмотрим на примере решения конкретной задачи при 3-х пунктах отправления и 4-х пунктах назначения.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (209)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |