Осложнения транспортной задачи

Осложнения транспортной задачи  [c.130]

Еще одно возможное осложнение транспортной задачи - это запрещение определенной перевозки от г -го поставщика ку-му потребителю для составляемого плана перевозок (ремонт дороги, неплатеж и пр.). В этом случае, естественно, можно просто ввести ограничение . = 0. Однако вновь это означает невозможность использования эффективных "транспортных" алгоритмов решения.  [c.133]


Если это условие не выполняется, т.е. транспортная задача не сбалансирована, упоминавшиеся выше специальные высокоэффективные алгоритмы ее решения не могут быть применены. Чтобы обеспечить их применение, в формулировку задачи вносят искусственные изменения, восстанавливающие баланс спроса и предложения. Как это делается, мы рассмотрим ниже, в разделе "Осложненные случаи транспортной задачи".  [c.120]

Первое осложнение при такой постановке заключается в гом, что возможный суммарный объем производства, как правило, не сбалансирован и превышает суммарный объем потребления (это так называемая открытая транспортная задача, рассмотренная же ранее называется закрытой). Эту задачу, однако, можно свести к обычной транспортной, вводя добавочный фиктивный пункт потребления Bn+i с такими характеристиками потребность продукта в нем равна разности между возможным объемом производства продукта и суммарной потребностью всех реальных пунктов потребления, т. е. в него сводятся все излишки, а затраты на перевозку в него из всех пунктов производства равны нулю,  [c.45]


Первое осложнение при такой постановке задачи заключается в том, что возможный суммарный объем производства, как правило, не сбалансирован и превышает суммарный объем потребления (это так называемая открытая транспортная задача, рассмотренная же ранее называется закрытой). Преодолеть такое затруднение можно, введя добавочный фиктивный пункт потребления Bn+i со следующими характеристиками потребность продукта в нем равна разности между возможным объемом производства продукта и суммарной потребностью всех реальных пунктов потребления (это значит, что в такой пункт свозятся все излишки), а затраты на перевозку в него из всех пунктов производства равны нулю. В результате приходим к обычной транспортной задаче, в которой, однако, в элементах матрицы затрат к затратам на транспортировку добавлены затраты на производство в пункте отправления. Решив эту задачу, определим, в частности, оптимальные объемы производства как суммы потоков из каждого пункта производства в реальные пункты потребления.  [c.57]

Заметим, что на сети, изображенной на рис. 16, груз из пункта / может быть перевезен в пункт IX по разным дорогам. Если бы мы захотели перейти к матричной форме транспортной задачи, то нам надо было бы заранее решить, по какому из маршрутов мы повезем груз. Если пропускная способность каждой из дорог не ограничена, то переход к матричной форме не вызовет затруднений при относительно простой сети. В более сложных сетях этот вопрос можно решить с помощью специально предназначенных для этого алгоритмов. Если же пропускная способность некоторых участков сети дорог ограничена, то возникают осложнения следующего рода. Пусть по участку дороги от пункта IV до пункта V можно провезти не более 30 единиц груза. Но по этой дороге мы можем везти груз и из пункта / в пункты V, VIII и IX, и из пункта /// в пункт VI. Спрашивается, на какие из перевозок мы должны наложить ограничения при переходе к матричной постановке По-видимому, на все вместе. Но, с другой стороны, если возможности дороги между пунктами IV и V будут исчерпаны, часть грузов можно будет перевозить по другим дорогам. Однако при этом изменится величина затрат на перевозки единицы груза, так что в матричной постановке величина сц оказывается зависимой от ху, и задача становится нелинейной. Хотя все эти трудности перехода к матричной постановке задачи перевозки грузов все-таки можно преодолеть при помощи разнообразных искусственных приемов, многие предпочитают решать задачи в сетевой постановке, не переходя к матричной. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач сразу на сети. К сожалению, эти алгоритмы более громоздки, чем алгоритмы решения транспортной задачи в матричной постановке. Есть и другие недостатки сетевой постановки задачи, есть и ряд дополнительных преимуществ,  [c.160]