Открытая транспортная задача
При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей: При этом возможны два варианта: а) если , то объем запасов превышает объем потребления, все потребители будут удовлетворены полностью и часть запасов останется не вывезенной. Для решения задачи вводят фиктивного (n + 1) потребителя, потребности которого . Модель такой задачи будет иметь вид при ограничениях: ; б) если , то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения такой задачи вводят фиктивного (m+ 1) поставщика, запас которого . Модель такой задачи имеет вид при ограничениях: . При введении фиктивных поставщика или потребителя открытая транспортная задача становится закрытой и решается по рассмотренному алгоритму для закрытых задач, причем тарифы, соответствующие фиктивным поставщику или потребителю, принимаются либо равными нулю, либо большими или равными наибольшему из всех транспортных тарифов. В решении целевой функции фиктивный поставщик или потребитель не учитываются. Пример. Составить оптимальный план перевозки грузов от трех поставщиков с грузами 240, 40, 110 т к четырем потребителям с потребностями 90, 190, 40 и 130 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю заданы матрицей . Решение. Запасы груза у поставщиков: 240 + 40 + 110 = 390 т. Потребности потребителей: 90 + 190 +40 + 130 = 450 т. Так как запасов груза меньше, чем потребности потребителей, то задача открытая. Следовательно, вводим фиктивного поставщика с грузом а4ф = 450 – 390 = 60 т. Тариф фиктивного поставщика примем равным нулю. Распределительная таблица:
Так как m + n – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введем в клетку (2, 2) нулевую поставку. Расчет потенциалов проведен в распределительной таблице. Оценки свободных клеток: D11 = – 2, D13 = 3, D21 = – 14, D24 = – 7, D32 = – 4, D33 = – 10, D4ф1 = – 8, D4ф3 = – 1, D4ф4 = – 5. Оценка свободной клетки (1, 3) больше нуля, от нее строим цикл и перераспределяем грузы:
Полученное перераспределение грузов вносим в распределительную таблицу и проверяем на оптимальность:
Оценки свободных клеток: D11 = – 2, D21 = – 14, D23 = – 3, D24 = – 7, D32 = – 4, D33 = – 13, D4ф1 = – 8, D4ф3 = – 4, D4ф4 = – 5. Следовательно, получено оптимальное решение: . Стоимость транспортных расходов составит: L(X)min = 90×13 + 40×9 + 110×8 + 40×8 + 90×3 + 20×6 = 3120 ден. ед. Применение транспортных задач в экономике Транспортная задача является важным частным случаем задачи линейного программирования. Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не относящихся к транспортировке груза. В этом случае величины тарифов имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся: 1) оптимальное закрепление за станками операций по обработке деталей. В них сij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции должен использоваться каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения сij берутся с отрицательным знаком; 2) оптимальные назначения или проблема выбора. Имеется m механизмов, которые могут выполнять n различных работ с производительностью сij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности; 3) задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции; 4) увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность; 5) решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть направлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки.
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (718)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |