Транспортная задача.

 

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

а_i — общее количество груза в i-м пункте отправления;

b_j — общее количество груза, необходимое в j-м пункте назначения;

c_ij - затраты на транспортировку единицы груза из i-го пункта отправления в j-й пункт назначения;

Z - совокупные затраты на транспортировку всего груза;

x_ij - исходное неизвестное количество груза, которое перевозится из пункта i в пункт j.

Из условия задачи следует модель линейного программирования:

- целевая функция (1)

- 1-я система ограничений (2)

- 2-я система ограничений (3)

- 3-я система ограничений (4)

Система ограничений (2) говорит о том, что весь груз из каждого пункта его сисредоточения должен быть вывезен, система ограничений (3) - потребность в грузе в каждом пункте должна быть удовлетворена, система ограничений (4) - по любому маршруту либо перевозится некоторое количество груза x_ij > 0, либо нет x_ij = 0.

Следовательно, транспортная задача является задачей линейного программирования

с n + m ограничениями, то есть с уравнениями с n + m неизвестными. Транспортная задача, у которой суммарное наличие груза совпадает с суммарной потребностью, то есть выполняется условие

(5)

называется сбалансированной (закрытой), а если условие (5) не выполняется, то открытой (решение открытой сводится к решению закрытой).

Выполнение условия (5) позволяет исключить одно из ограничений (2) или (3) и свести их число к n + m - 1. Иными словами, если выполняетс условие (5), то любая транспортная задача имеет оптимально допустимое решение (план), содержащее не более n + m - 1 компонент.