|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИТранспортные задачи описывают перевозку какого-либо груза из пункта отправления в пункт назначения. Цель транспортной задачи – определить объем перевозок из пунктов отправления в пункты потребления с минимальной суммарной стоимостью, учитывая ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления, и потребность грузов в пунктах потребления. Стоимость перевозки по какому-либо маршруту прямо пропорциональна перевозимому объему груза по данному маршруту. Пусть имеется n пунктов отправления и m пунктов потребления некоторого груза. Обозначим xij – объем груза, перевозимого из пункта i в пункт j, а cij стоимость перевозки единицы груза в этом направлении. Транспортную задачу решают методом потенциалов. Для этого всю информацию записывают в таблицу (каждая таблица будет отражать одну итерацию решения): Каждая внутренняя клетка таблицы делится на четыре части, в которые записывается следующая информация: cij – стоимость перевозки единицы груза из пункта i в пункт j, xij – объем перевозимого груза из пункта i в пункт j, dij – оценка (определяется в процессе решения), sign – знак «+» или «–» (определяется в процессе решения). В столбец U и строку V записывают потенциалы, вычисленные для соответствующих строк и столбцов. Алгоритм транспортной задачи Шаг 1. Нахождение первоначального плана перевозок. Для определения первоначального плана перевозок используется правило северо-западного угла. Согласно этому правилу рассмотрим клетку [ k,p ], находящуюся в северо-западном (левом верхнем) углу таблицы, начиная с клетки [1, 1]. Определим объем перевозки из пункта k в p таблицы исключаем либо только строчку k, либо только столбец p. Переходим к новой клетке [ k,p ], находящейся в северо-западном углу оставшейся таблицы и повторяем процедуру до тех пор, пока все строки и столбцы не будут исключены. Клетки, для которых определен объем перевозок, являются базисными, их число n+m- 1. Для некоторых из этих клеток может получиться xij = 0. Остальные клетки внебазисные и информация о xij в них не заносится. Шаг 2. Проверка оптимальности решения. Считаем суммарную стоимость перевозок L. Для проверки найденного решения на оптимальность вычислим потенциалы всех пунктов отправления и потребления (Ui и Vj). Присвоим первой строке потенциал равный единице U1 = 1. Остальные потенциалы находим, используя Шаг 3. Определение нового базисного решения. Определим клетку [ q,s ], выводимую из базиса. Для этого построим цикл пересчета П, в котором одна из клеток не базисная ([ k,p ]), а остальные – базисные. В общем случае цикл пересчета может представлять собой замкнутую ломанную, имеющую сложную ступенчатую конфигурацию. При этом на любой горизонтальной и вертикальной линии цикла должно находиться четное количество клеток. Клетке [k,p] присваиваем знак «+» и записываем его в поле sign. В соседнюю клетку цикла записываем «–» и т.д., чередуя плюсы и минусы, так чтобы в каждой строке и столбце количество плюсов равнялось количеству минусов. Объемы предложения и потребления: Решение: Суммарный объем предложения (80) не равен суммарному объему потребления (75), следовательно транспортная задача является открытой и необходимо ввести фиктивного потребителя В5 с объемом потребления 80-75=5 ед. Назначим стоимость перевозок в пункт В5 в размере 50 у.е. Составим таблицу и определим исходный базис методом северо-западного угла. После этого вычисляем оценки по формуле Максимальная оценка d41=4>0 – полученное решение не оптимально и его можно улучшить Максимальная оценка d23 =4>0, следовательно, решение не оптимально и его можно улучшить. Перейдем к новому базису. Стоимость перевозок L=428 у.е. Максимальная оценка d25 =2>0, следовательно, решение не оптимально и его можно улучшить. Стоимость перевозок L=424 у.е. Максимальная оценка равна нулю, следовательно, решение оптимально. Стоимость перевозок без учета фиктивного потребителя составит L=424-250=174 у.е. Ответ: минимальная стоимость перевозок равна 174 у.е. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |