Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Под названием транспортная задача ,определяется широкий круг задач с единой математической моделью, эти задачи относятся к задачам линейного программирования и могут быть решены оптимальным методом. Однако, спец.метод решения транспортной задачи позволяет существенно упростить её решение, поскольку транспортная задача разрабатывалась для минимизации стоимости перевозок.

Классическую транспортную задачу можно решить симплекс - методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из Ai в Bj груза \(xij\geq 0\), а в маленькие клетки — соответствующие тарифы Cij.

Нахождение опорного плана

Требуется определить опорный план и путём последовательных операций найти оптимальное решение. Опорный план можно найти следующими методами: "северо - западного угла", "наименьшего элемента".

  • Метод минимального элемента

Одним из способов решения задачи является метод минимального (наименьшего) элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями. Метод получения начального решения — записывать отгрузки в первую очередь в те ячейки, где тариф минимален. Этот метод позволяет получить более приближенное к оптимальному решение, которое, однако, может потребовать дальнейшей оптимизации. Метод минимальных тарифов с его модификациями (минимальный тариф по строке или минимальный тариф по столбцу) был описан Данцигом в работе 1951 г.

  • Метод северо - западного угла

На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из Ai или полностью удовлетворяется потребность Bj.

Допустимое (но не всегда оптимальное с точки зрения стоимости доставки) начальное решение транспортной задачи можно построить, последовательно перебирая строки таблицы (то есть поставщиков) сверху вниз. В пределах каждой строки, нужно перебрать слева направо не охваченных или не полностью охваченных поставками потребителей, записывая в соответствующие ячейки объем поставляемого груза от поставщика в данной строке, и так до исчерпания возможностей поставщика. Таким образом, весь груз от поставщиков будет распределен по потребителям. Этот метод был предложен Данцигом в 1951 г. и назван Чарнесом и Купером «правилом северо-западного угла».

Алгоритм:

- Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.

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

- Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.



В1, 20кг
В2, 30кгВ3, 30кгВ4, 10кг
А1, 30кгx11 = 20кг
x12 = 10кг

А2, 40кг
x22 = 20кгx23 = 20кг
А3, 20кг

x33 = 10кгx34 = 10кг

В таблице желтым цветом отмечены ячейки с ненулевыми объемами перевозки груза (базисные ячейки).

 Метод Фогеля

Для поиска начального решения транспортной задачи можно применить также метод Фогеля, который обычно дает еще более приближенное к оптимальному решение.В отличие от метода северо - западного угла или метода минимальных тарифов генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи  метода потенциалов.




2012-12-20 • Просмотров [ 3596 ]