Транспортные задачи

З.С.

математической моделью.

программирования специального вида о поиске оптимального распределения однородных объектов из

аккумулятора к приемникам с минимизацией затрат на перемещение.

грузов из пунктов отправления в пункты потребления, с минимальными затратами

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

продукта из однородных пунктов наличия в однородные пункты потребления на

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

Гаспаром Монжем в 1781 году. Прогресс в решении проблемы был

достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

математик и экономист, пионер и один из создателей линейного программирования.)

ряда особенностей её можно решить проще (для задач малой размерности).

Условия

задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из ~A_i в ~B_j груза ~X_ij больше либо равно 0, а в маленькие клетки — соответствующие тарифы ~C_ij.

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

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

Заполнение таким образом, что полностью выносится груз из ~A_i или полностью удовлетворяется потребность ~B_j

(наименьшего) элемента. Его суть заключается в сведении к минимуму побочных

перераспределений товаров между потребителями.

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

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

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