АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  3. I. Решение логических задач средствами алгебры логики
  4. I. Ситуационные задачи и тестовые задания.
  5. II. Основные задачи и функции
  6. II. Решение логических задач табличным способом
  7. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  8. II. Цель и задачи государственной политики в области развития инновационной системы
  9. III. Разрешение споров в международных организациях.
  10. III. Решение логических задач с помощью рассуждений
  11. III. Цели и задачи социально-экономического развития Республики Карелия на среднесрочную перспективу (2012-2017 годы)
  12. MFG/PRO – лучшее решение для крупных и средних промышленных предприятий с дискретным типом производства

Транспортные задачи описывают перевозку какого-либо груза из пункта отправления в пункт назначения. Цель транспортной задачи – определить объем перевозок из пунктов отправления в пункты потребления с минимальной суммарной стоимостью, учитывая ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления, и потребность грузов в пунктах потребления. Стоимость перевозки по какому-либо маршруту прямо пропорциональна перевозимому объему груза по данному маршруту.

Пусть имеется 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 у.е.


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)