Постановка задачи. Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у т производителей (поставщиков), по п потребителям этих ресурсом.

Наиболее часто встречаются следующие задачи, относящиеся к транспортным:

• прикрепление потребителей ресурса к производителям;

• привязка пунктов отправления к пунктам назначения;

• взаимная привязка грузопотоков прямого и обратного направлений;

• отдельные задачи оптимальной загрузки промышленного оборудования;

• оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

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

Суммарные объемы отправления должны равняться суммарным объемам назначения:

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

В случае если:

• потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

• запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

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

Транспортным задачам присущи следующие особенности:

• распределению подлежат однородные ресурсы;

• условия задачи описываются только уравнениями;

• все переменные выражаются в одинаковых единицах измерения;

• во всех уравнениях коэффициенты при неизвестных равны единице;

• каждая неизвестная встречается только в двух уравнениях системы ограничений.