Постановка ТЗ

Транспортная задача – специальный класс ЗЛП. Эти модели часто описывают перемещение (перевозку) какого-либо товара из точки отправления (например, место производства) в пункт назначения (например, склад, магазин, грузохранилище). Назначение ТЗ – определить объем перевозок из пунктов отправления в пункт назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления, и ограничения, учитывающие потребность грузов в пункте назначения. В транспортной модели предполагается, что стоимость перевозки по какому-либо маршруту прямо пропорциональна объему груза, перевозимого по этому маршруту.

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

ТЗ может быть решена как обычная ЗЛП. Однако, матрица системы ограничений ТЗ настолько своеобразна, что для ее решения разработаны специальные методы.

Задача. Пусть в пунктах хранится однородный груз в размерах единиц. Этот груз следует доставить в n заданных пунктов назначения , причем в каждый из них требуется завезти соответственно единиц этого груза. Обозначим стоимость перевозки груза из пункта в пункт . Таким образом, имеем:

– вектор запасов поставщиков ;

– вектор запросов потребителей ;

– матрицу стоимостей перевозок

.

Будем искать матрицу и целевую функцию где обозначает количество единиц груза, которое необходимо доставить из пункта в пункт .