Задача о перевозках с перегрузкой
Забежав несколько вперед (см. гл. 3), укажем, что сетевой подход позволяет использовать алгоритм транспортной задачи для решения более сложных задач. Втранспортной задаче предполагается, что ни в одном из маршрутов, соединяющих источник с некоторым стоком, другие источники и стоки не могут быть использованы в качестве промежуточных пунктов. Если считать допустимой перевозку фузов из источника в сток через другие источники и стоки, то новая задача может быть сведена к обычной транспортной задаче. Объем вычислений, естественно, возрастает, так как в сеть будут включены дополнительные маршруты, соединяющие каждый источник со всеми другими источниками и каждый сток со всеми другими стоками. Считаем, что транспортные затраты с^, соответствующие дополнительным маршрутам, известны. Новая задача сводится к модифицированной транспортной задаче, в которой предложения и спрос, соответствующие дополнительным маршрутам, заданы таким образом, что они не влияют на выбор маршрутов, осуществляемый в основном алгоритме. Выполнение последнего требования необходимо, поскольку ограничения на поток по дополнительным маршрутам, задаваемые предложением и спросом, являются фиктивными и вводятся только для вычислительных целей.
Пусть — минимальная из величин
и
— суммарных предложения и спроса, т.е.
— это реальный поток, протекающий по модифицированной сети. Тогда очевидно, что величину спроса
-го исходного источника и величину предложения
-го исходного стока можно принять равными
, т.е. весь поток может протекать через один источник или через один сток. Поскольку
то исходные величины предложения и спроса должны быть увеличены на
. Если же увеличить исходные данные на
, то некоторые планы перевозок, допустимые в исходной задаче, в модифицированной задаче станут недопустимыми. Выбор
не скажется на решении задачи. Поэтому выбирают
.
Рассмотрим традиционную транспортную задачу (табл. 2.12).
Пусть в ней каждый источник и каждый сток может использоваться в качестве промежуточного пункта (узла). Здесь следовательно, в модифицированной задаче надо выбрать
= 30.

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

Матрица условий модифицированной транспортной задачи для решения задачи перевозок с перегрузкой приведена в табл. 2.13. Транспортные затраты для дополнительных маршрутов (три последние строки и два последних столбца в табл. 2.13) предполагаются известными.

Эту задачу можно решить методом потенциалов. Решив модифицированную транспортную задачу, тем самым решим поставленную задачу о перевозках.
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны: