2015-03-07
597
I. Одной из часто встречающихся задач хозяйственного управления является задача по разработке рационального плана транспортных перевозок, то есть минимизация затрат на их выполнение. Формулировка транспортной задачи в общем виде: требуется перевезти определенное количество однородного груза из m пунктов отправления в п пунктов назначения. Вводят обозначения:
аi — общее количество груза в i -м пункте отправления;
bj — общее количество груза, необходимое в j -м пункте назначения;
cij - затраты на транспортировку единицы груза из i -го пункта отправления в j -й пункт назначения;
Z - совокупные затраты на транспортировку всего груза;
xij - исходное неизвестное количество груза, которое перевозится из пункта 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 компонент.
