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

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

Любая задача транспортного типа, как задача линейно­го программирования, может быть решена симплекс-методом. Однако специфические особенности задач рассматриваемого класса позволили разработать более эффективные вычисли­тельные методы. Поскольку в реальных задачах транс­портного типа число ограничений и переменных, как правило, бывает весьма значительным, то использование эффективных вычислительных алгоритмов становится актуальным.

Для задач данного класса естественным и удобным является их геометрическое представление в виде графа спе­циального вида. Это представление в ряде случаев позволяет преобразовывать к задачам транспортного типа даже такие задачи исследования операций, которые на первый взгляд не имеют с ними ничего общего, и использовать для их решения значительно более эффективные вычислительные алгоритмы.

Сетевые оптимизационные модели, обычно являющиеся частными случаями моделей линейного программирования, важны в двух отношениях. Часто они относятся к задачам распределения продук­ции. Следовательно, модели этого класса имеют экономический смысл для многих промышленных фирм, располагающих нескольки­ми предприятиями и хранящих запасы продукции на складах, раз­мещенных в различных пунктах. Кроме того, математическая струк­тура сетей идентична структуре других операционных моделей, на первый взгляд не имеющих с ними ничего общего.

Транспортные задачи линейного программирования тесно связаны с детермини­рованными динамическими задачами исследования операций, в том числе и с многошаговыми задачами принятия решений в условиях определенности, имеющими большое прикладное зна­чение.

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

Математическая постановка транспортной задачи, как мы уже говорили ранее, имеет следующий вид (в данной математической модели обозначим  значение величины потока перевозкок из истока i в сток j):

Минимизировать .

при ограничениях:

  {1..m}

   {1..n}.

В исследовании операций полностью целочисленную транспортную задачу обычно называют классической транспортной задачей.

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

Транспортная задача всегда может быть задана таблицей издержек, связанных с перевозками грузов из данных источников в данные пункты назначения. В ячейку с координатами (i,j) таблицы издержек записывают стоимость перевозки единицы груза из истока i в сток j. Кроме значений стоимости перевозок в данную таблицу в соответствующих строках помещают величины запасов в пунтках-истоках, а в соответствующих столбцах – величины заявок пунктов-стоков. Ниже приведен пример заполненной таким образом таблицы издержек.

 

Сток Исток			…		Запасы:
			…
			…
…	…	…	…	…	…
			…
Заявки:			…

 

Для удобства геометрической интерпретации классической транспортной задачи, представленной в вышерасположенной таблице, каждый j-й сток и каждый i-й исток можно изобразить в виде узла сети, т.е. в виде окружности.

Если узел сети, соответствующий i-му ис­току соединить ориен­тированной дугой с узлом сети, соот­ветствующим j-му стоку, и на этой дуге указать стоимость пе­ревозки единицы товара от i-го пунк­та производства к j-му пункту по­требления, то получим представление рассматриваемой транспортной задачи в виде сети.

Итак, каждая переменная  соответствует потоку вдоль ориентированной дуги из истока I в сток j. Тогда соответствующая ему величина  выражает затраты в расчете на единицу потока, а сама задача заключается в распределении мощностей истоков по дугам таким образом, чтобы при минимальных затратах удовлетворить потребности стоков.

Прежде чем переходить к рассмотрению конкретных при­меров, рассмотрим несколько особенностей постановки классической транспортной задачи.

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

В реальных задачах транспортного типа нетрудно предположить возможность возникновения ситуации, в которой некоторому истоку будет доступен не каждый из имеющихся стоков. В формулировке классической транспортной задачи данная возможность нами учтена не была. Для того, чтобы все-таки учесть подобную ситуацию, договоримся о том, что если в силу каких-либо причин i-й пункт производства не доступен для j-го пункта потребления, то либо исключим из рассмотрения переменную модели , либо примем  соответствующую ей величину  сколь угодно большой.

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

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

Как правило, введение ограничений на пропускные способности дуг в математическую модель классической транспортной задачи приводит лишь к незначительному увеличению объема вычи­слений при поиске оптимального решения. Однако иногда эти ограничения оказываются настолько жесткими, что множество допустимых решений рассматриваемой задачи оказывается пу­стым.

При постановке классической транспорт­ной задачи предполагают идентичность ассортимента, то есть считается, что все пункты производства выпус­кают одну и ту же продукцию. Однако на практике подобная ситуация встречается крайне редко. Обычно, каждое пред­приятие выпускает несколько наименований или, хотя бы, разновидностей товаров, а при разработке плана их перевозок необходимо учитывать всю номенклатуру. Как можно легко себе представить, требуется немалая изобретательность, чтобы подогнать реальную распределительную задачу к условиям клас­сической транспортной модели. К сожалению, здесь нет возможности перечислить все приемы, позволившие успешно справиться с такой подгонкой на практике. Для пояснения основных понятий, которыми при этом пользуются, ниже приводится краткое описание одного из подходов к решению этой проблемы.

Пусть спрос на различные виды продукции в каждом пункте потребления (стоке) j в течение планируемого периода известен. Примем в качестве единицы измерения общего количества требуемой продук­ции всех видов какую-либо удобную общепринятую меру, напри­мер тонну. Аналогично будем измерять поставки в тех же едини­цах. При вычислении величин стоимостей перевозок предположим, что если некоторое предприя­тие i отправляет тонну продукции потребителю j, то эта тонна вклю­чает все виды продуктов, необходимых в пункте j в заданных про­порциях.

Здесь сразу же возникает вопрос, насколько практически реализуемым и точным будет полученное числовое решение задачи. Чтобы разумно отве­тить на этот вопрос, нужно иметь в виду два обстоятельства. Прежде всего, решение, в сущности, представляет собой некоторый план распределения продуктов в течение заданного интервала времени. Иными словами, модель обеспечивает прикрепление предприятий к пунктам назначения или поставщиков к потребителям. Числовые значения величин перевозок  по самой своей природе являются приближенными, поскольку в большинстве реальных случаев значения запросов в пунктах потребления представ­ляют собой лишь прогнозы потребностей на планируемый период. В связи с этим значения , полученные в процессе решения, не являются фактическими значениями количества перевозимых продуктов, а слу­жат только оценками величины будущих поставок. Рассуждая дальше, относи­тельные достоинства полученного плана необходимо сравнить с любы­ми практически реализуемыми вариантами, которые может исполь­зовать фирма, в том числе, разумеется, с принятым планом перево­зок. Учитывая эти соображения, многие фирмы могут существенно повы­сить свои доходы, приняв план перевозок, основанный на решении классической транспортной задачи.

Вернемся теперь непосредственно к рассмотрению методов решения транспортной задачи. Пусть задана некоторая классическая транспортная задача.

Предположим, что имеется n пунктов потребления (например, промышленных предприятий или типографий) П_j, j{1..n}, требующих снабжения некоторым определенным видом сырья. Потребности в сырье каждого предприятия П_j равны соответственно b_j условных единиц j{1..n}. Кроме того, имеется m складов С_i, i{1..m}, на которых хранится требуемое предприятиям сырье. На каждом складе С_i  имеется в наличии запас товара в количестве a_i соответственно, i{1..m}. Склады удалены от предприятий на некоторые расстояния и связаны с ними некоторыми путями сообщений с различными тарифами на перевозку грузов (в нашем случае сырья). Будем считать, что каждый склад связан с каждым пунктом потребления некоторым единственным маршрутом с неограниченной пропускной способностью. Единица сырья, получаемая предприятием П_j со склада C_i с учетом известных тарифов на перевозки, обходится  в c_ij рублей. Для простоты предположим, что все заявки выполнимы и обеспечивают отсутствие излишек на складах, т.е. сумма всех заявок в точности равна сумме всех имеющихся запасов:

.

     Требуется составить план перевозок, т.е. указать с какого склада на какие предприятия, и какое количество сырья нужно направить, чтобы заявки были выполнены, а общие расходы на все перевозки были минимальными.

Составим для данной задачи, как это уже было показано раньше таблицу издержек:

 

Сток Исток			…		Запасы:
			…
			…
…	…	…	…	…	…
			…
Заявки:			…

 

Очевидно, что не все m + n  уравнений системы ограничений транспортной задачи являются независимыми. Действительно. складывая все ограничения по заявкам и все ограничения по запасам, в силу равенства заявок и запасов, получаем доказательство того, что ранг системы ограничений r = m + n – 1. Следовательно, можно разрешить эти уравнения относительно r базисных переменных, выразив их через остальные k свободные.

k = m×n – r = m×n – m – (n – 1) = m×(n – 1) – (n – 1) Þ

k = (m – 1)×(n – 1).

Мы уже останавливались на факте того, что в задаче линейного программирования оптимальное решение достигается в одной из вершин области допустимых решений, где, по крайней мере, k переменных обращаются в нуль.

Значения  количества единиц груза, направляемых из пункта Сi в пункт Пj будем называть перевозками. Любую совокупность значений () будем называть планом перевозок, или просто планом. Тогда план будем называть допустимым, если он удовлетворяет балансовым условиям: все заявки удовлетворены и, все запасы исчерпаны.

В свою очередь, допустимый план будем называть оптимальным в том случае, если он приводит к наименьшей стоимости всех перевозок.

Методы решения транспортной задачи не требуют манипуляций с симплекс-таблицами, а сводятся к операциям с таблицей, где в определенном порядке (см. примеры таблиц издержек выше) записаны все условия транспортной задачи – транспортной таблицей. Стоимость перевозок (соответствующие издержки из таблицы издержек)  будем помещать в правом верхнем углу каждой ячейки, с тем, чтобы в самой ячейке помещать значения соответствующих перевозок  (). Ниже приведен пример заполнения транспортной таблицы:

 

Сток Исток					…				Запасы:
						…
					…
						…
					…
…		…		…		…		…	…
	…		…		…		…
						…
					…
Заявки:					…

 

Ячейки таблицы с отличными от нуля перевозками условимся называть базисными, а остальные (пустые – в дальнейшем в транспортную таблицу мы будем заносить только отличные от нуля значения) свободными.

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения или, в случае транспортной задачи, опорного плана перевозок. В отличие от общего случая задачи линейного программирования, решение транспортной задачи всегда существует. Рассмотрим один из способов построения опорного плана – так называемый метод «северо-западного угла».

Нахождение опорного плана методом «северо-западного угла»

Метод «северо-западного» угла реализует интерактивный поиск опорного решения. Идея метода состоит в следующем. На каждой итерации выбирается такое решение, которое бы с одной стороны учитывало бы результаты предыдущих итераций, а с другой стороны по возможности минимизировало бы  количество оставшихся итераций.

Применительно к транспортной таблице работу метода «северо-западного угла» можно представить так. Первоначально заполняется самая левая верхняя клетка (северо-западный угол таблицы). Это означает, что мы принудительно посылаем товар со склада 1 потребителю 1. Если количество имеющегося в наличии товара на складе 1 превышает размер запроса потребителя 1, то в северо-западную клетку (1,1) следует поместить значение запроса потребителя 1. В противном случае, то есть в ситуации, при которой склад 1 не в состоянии самостоятельно удовлетворить запрос потребителя 1, в ячейку (1,1) транспортной таблицы следует поместить значение запаса склада 1.

Очевидно, что в случае неравенства (или равенства) запаса на складе 1 запросу потребителя 1 возможны два варианта:

1.      Склад 1 полностью удовлетворил запрос потребителя 1, но при этом запас его товаров еще не исчерпан. Тогда на следующей итерации алгоритма мы будем рассматривать соседнюю с востока ячейку, то есть ячейку (1,2) транспортной таблицы.

2.      Склад 1 не в состоянии полностью удовлетворить запрос потребителя 1, то есть запас его товаров исчерпан, а запрос потребителя еще не удовлетворен. Тогда на следующей итерации алгоритма мы будем рассматривать соседнюю с юга ячейку, то есть ячейку (2,1) транспортной таблицы.

3.      Склад 1 полностью удовлетворил потребности потребителя 1, при этом запас товаров на складе был полностью исчерпан. Тогда на следующей итерации алгоритма мы будем рассматривать соседнюю с юго-востока ячейку, то есть ячейку (2,2) транспортной таблицы.

Описанная процедура обеспечивает выбор ячейки транспортной таблицы для следующей итерации алгоритма поиска опорного решения.

Очевидно, что в силу равенства суммарных заявок (запросов) суммарным запасам на последней итерации алгоритма – ячейка (i,j) – в общем случае окажется, что i-ый склад оставшимся своим запасом полностью удовлетворит оставшийся неудовлетворенным на предыдущих итерациях запрос j-того потребителя.

Рассмотрим работу данного метода на конкретном примере. Пусть задана некоторая транспортная задача и соответствующая ей транспортная таблица:

 

Сток Исток											Запасы:
		10		8		5		6		9	48
		6		7		8		6		5	30
		8		7		10		8		7	27
		7		5		4		6		8	20
Заявки:	18		27		42		12		26		125

 

Тогда в соответствии с только что описанным методом «северо-западного угла» будем заполнять таблицу перевозками, начиная с северо-западной ячейки (1,1), рассуждая так.

Удовлетворим пункт В₁  за счет запаса А₁, следовательно
 х₁₁= 18. После этого в пункте А₁ осталось 30 единиц груза. Удовлетворим запрос пункта В₂ за счет остатка А₁, следовательно х₁₂ = 27. оставшиеся 3 единицы груза направим в пункт В₃ Þ х₁₃ = 3. В составе заявки пункта В₃ осталось неудовлетворенным 39 единиц груза. Из них 30 покроем за счет пункта А₂, чем его запас будет исчерпан, и еще 9 единиц возьмем из пункта А₃, следовательно х₂₃ = 30 и х₃₃ = 9 и т.д. Полученное решение будет не только допустимым, но и опорным.

В результате этих действий получим следующее опорное решение:

 

Сток Исток											Запасы:
		10		8		5		6		9	48
	18		27		3
		6		7		8		6		5	30
					30
		8		7		10		8		7	27
					9		12		6
		7		5		4		6		8	20
									20
Заявки:	18		27		42		12		26		125

 

Остановимся теперь на одной особенности плана перевозок. Речь идет о так называемом «вырожденном» плане, в котором некоторые из базисных перевозок оказываются равными 0.

Забегая вперед, отметим, что для решения транспортной задачи необходимо, чтобы уравнения, формирующие план перевозок, имели базис размерности m + n – 1. В противном случае дальнейшее решение транспортной задачи становится не возможным.

Исходя из этого, можно сделать вывод о необходимости строго поддерживать размерность базиса, равную m + n – 1. Тогда в случае получения на некоторой итерации вырожденного плана перевозок необходимо искусственным образом ввести дополнительную базисную переменную. Для этого в любую из свободных клеток транспортной таблицы следует поместить некоторую бесконечно малую величину e и соответственно скорректировать значения всех соседних базисных клеток.

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

 

Сток Исток											Запасы:
		10		8		5		6		9	20
	10		10		e
		6		7		8		6		5	30
					20-e		10+e
		8		7		10		8		7	25
							25-e		e
		7		5		4		6		8	20
									20+e
Заявки:	10		10		20		35		20		95

 

Особенностью этого опорного плана является то, что в нем только 6 , а не 8 отличных от нуля перевозок (r = m + n – 1 = 4 + 5 – 1 = 8).

В дальнейшем нам удобно будет всегда иметь в транспортной таблице r базисных клеток, хотя в некоторых из них, может быть, будут стоять нулевые значения перевозок. Для этого можно ничтожно мало изменить запасы или заявки, например, на величину e, а после нахождения оптимального решения положить e = 0.

Улучшение плана перевозок. Цикл пересчета

Метод «северо-западного» угла позволяет отыскать допустимый план перевозок, который мы назвали опорным планом. Очевидно, что в общем случае опорный план, являясь допустимым, не является оптимальным. Для нахождения оптимального плана перевозок необходимо последовательно, пока это возможно, улучшать опорный план. В этом параграфе мы рассмотрим термины и определения, используемые при улучшении опорного плана, которые нам в дальнейшем потребуются при рассмотрении алгоритмов решения транспортной задачи.

Возвращаясь к нашему исходному примеру, рассмотрим его опорное решение – опорный план перевозок.

 

Сток Исток											Запасы:
		10		8		5		6		9	48
	18		27		3
		6		7		8		6		5	30
					30
		8		7		10		8		7	27
					9		12		6
		7		5		4		6		8	20
									20
Заявки:	18		27		42		12		26		125

 

Стоимость этого плана равна:

L = 18×10 + 27×8 + 3×5 + 30×8 + 9×10 + 12×8 + 6×7 + 20×8 = 1039.

Попробуем улучшить этот план, перенеся, как показано в приведенной выше таблице, 18 единиц из клетки (1,1) в клетку (2,1) и, чтобы не нарушать баланса, перенесем те же 18 единиц из клетки (2,3) в клетку (1,3). В результате переноса мы получили новый план перевозок, который тоже будет допустимым, так как переброску груза с одного маршрута на другой мы осуществляли циклически, заботясь о сохранении баланса заявок и запасов.

 

 

Таким образом, мы получили новый допустимый план, стоимость которого равна:

L = 18×6 + 27×8 + 21×5 + … = 913.

Очевидно, что полученный план перевозок по стоимости предпочтительнее первоначального опорного плана.

Из приведенной таблицы видно, что за счет циклической перестановки грузоперевозок объемом 18 единиц по маршрутам (1,1)^-, (2,1)⁺, (2,3)^-, (1,3)⁺ удалось понизить стоимость плана перевозок на 126 условных единиц стоимости.

Здесь следует обратить внимание на следующее равенство:

1039 – 913 = –126 = 18×(-10 + 6 – 8 + 5) = 18×(-7).

Рассмотрев на практическом примере принципы, лежащие в основе методов улучшения планов перевозок, формально определим некоторые из использованных нами при этом понятий.

Итак, циклом в транспортной таблице назовем несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на угол, равный 90^о. Условимся помечать символами (+) те вершины ломаной линии, образующей цикл, в которых объемы перевозок увеличивается, а символом (-) те вершины цикла, в которых они уменьшаются.

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

 

 

Цикл с отмеченными вершинами будем называть «означенным». Перенести какое-то количество единиц груза по означенному
циклу – это означает увеличить объемы перевозок в положительных вершинах (вершинах, помеченных символом «+») на это количество единиц и одновременно с этим уменьшить перевозки на то же количество в отрицательных вершинах (вершинах, помеченных символом «–»).

Очевидно что, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется.

Назовем ценой (стоимостью) цикла (g) – алгебраическую сумму стоимостей, стоящих в вершинах цикла, с учетом знака этих вершин, например:

g₁ = с₂₁ – с₂₃ + с₄₃ – с₄₁,

g₂ = с₃₄ – с₃₅ + с₅₅ – с₅₄ + с₁₄ – с₁₆.

Распределеительный метод решения транспортной задачи

Данный метод состоит в последовательном улучшении опорного плана перевозок путем отыскания на каждом шаге выгодных циклов переноса грузов. Опорный план для данного метода (как и для других методов решения транспортной задачи методом потенциалов) можно сформировать, применяя метод «северо-западного» угла.

Более подробно рассмотрим теперь процесс формирования очередного цикла переноса на каждом новом шаге алгоритма.

Очевидно, что при перемещении х единиц груза по некоторому циклу с ценой g стоимость перевозок изменяется на величину х×g.

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

Если циклов с отрицательной ценой в таблице больше не осталось, это означает, что оптимальный план достигнут.

При улучшении плана циклическими переносами пользуются приемом, заимствованным из симплекс-метода: на каждом шаге (цикле) заменяют одну свободную переменную на базисную, т.е. заполняют одну клетку и взамен того освобождают одну из базисных клеток.

Можно доказать, что для любой свободной клетки транспортной таблицы всегда существует цикл (и притом единственный), одна из вершин которого лежит в этой клетке, а все остальные в базисных клетках. Если цена такого цикла, с плюсом в свободной клетке, отрицательна, то план можно улучшить. Количество единиц груза (х), которые можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла.

Пример 1.  Распределительный метод решения транспортной задачи.

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

 

 

Решение:

Методом «северо-западного» угла найдем опорный план перевозок:

 

 

1.    Составленный с помощью метода «северо-западного угла» опорный план имеет шесть базисных клеток в соответствующей ему транспортной таблице, что позволяет его использовать без модификаций для дальнейшего решения задачи.

r = n + m – 1 = 4 + 3 – 1 = 6

     Посчитаем теперь стоимость найденного опорного плана:

L = 22×10 + 9×7 + … = 796

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

2.    Вычислим цену цикла для каждой свободной клетки. Количество свободных клеток в транспортной таблице данного опорного плана  равно: k = 3×2 = 6.

      

3.    Для всех свободных переменных (клеток) с отрицательной ценой цикла вычислим максимальное количество груза, которое можно перенести по соответствующему циклу. Очевидно, что максимальное количество груза, которое можно переместить по некоторому выбранному циклу будет равно минимальному значению груза среди отрицательных клеток цикла.

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

 

ij	2,1	2,4	31
g	- 4	- 2	- 2
x	22	20	18
gx	- 88	- 40	- 36

 

5.    Выберем ту свободную переменную, которой соответствует наименьшее значение величины   и перенесем  единиц груза по циклу, соответствующему выбранной переменной: (ij) = (2,1); g₂₁ = - 4; .

 

 

Таким образом, мы уменьшим значение целевой функции L – стоимость плана перевозок – на 88 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:

 

 

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

r = 6

     Стоимость найденного плана перевозок равна:

L = 31×7 + 22×5 + … = 708

Попытаемся опять улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

 

2.            Вычислим цену цикла для каждой свободной переменной:

3.            Вычислим максимальное количество груза, которое можно перенести по циклу с отрицательной ценой. Результаты расчетов, проделанных в предыдущем пункте, показали, что данная таблица содержит всего одну переменную и соответствующую ей свободную клетку. Таким образом, на данной итерации алгоритма нет необходимости в выборе цикла переноса.

.

4.            Для единственной свободной переменной рассчитаем значение критерия :

.

 

 

 

Перенесем  единиц груза по циклу
(2,4)⁺, (3,4)^-, (3,3)⁺, (2,3)^-, уменьшив этим значение целевой функции на 40 единиц. Новому улучшенному плану перевозок будет соответствовать следующая таблица перевозок:

 

 

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

r = 6

     Стоимость найденного плана перевозок равна:

L = 31×7 + 22×5 + … = 668

Попытаемся опять улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

 

2.            Вычислим цену цикла для каждой свободной переменной:

3.            Так как не существует циклов свободных переменных с отрицательной ценой, полученный план перевозок является оптимальным. Стоимость оптимального плана перевозок, как было посчитано ранее, составляет 668 единиц.

 

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

Пример 2.  Решение транспортной задачи.

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

 

 

Решение:

1.                   Методом «северо-западного» угла найдем опорный план перевозок:

 

 

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

r = n + m – 1 = 3 + 3 – 1 = 5 ¹ 4

План получается вырожденный.

 

 

Чтобы избежать этого, нарушаем баланс запасов и заявок на e в 1 и 3 строках, не нарушая общего баланса. Теперь:

r = 5,

а найденный опорный план можно использовать в дальнейшем для решения задачи.

     Стоимость найденного плана перевозок равна:

L = 20×10 + 20×5 + 23×5 + 20×6 = 535.

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

2.                   Вычислим цену цикла для k = 4 свободных клеток.

3.                   Вычислим максимальное количество груза, которое можно перенести по циклам с отрицательной ценой.

4.                   Для свободных переменных с отрицательной ценой цикла вычислим характеристику .

 

 

5.                   Перенесем max x₂₁ = 20 единиц груза по циклу свободной переменной х₂₁, уменьшив значение целевой функции на 100 единиц, то есть:

 

 

В результате получим следующий (уже не вырожденный) план перевозок:

 

 

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

r = 5

     Стоимость найденного плана перевозок равна:

L = 20×5 + 20×4 + 20×6 + 3×5 + 20×6 = 435

Попытаемся еще улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

2.                                                    Вычислим цену цикла для каждой свободной переменной.

3.                                                    Максимальное количество груза, которое можно перенести по циклу свободной переменной х₃₂ = 20.

4.                                                    g₃₂×max x₃₂ = - 80.

 

 

5.                                                    Перенесем 20 единиц груза по циклу переменной x₃₂, , уменьшив значение целевой функции на 80 единиц.

В результате получим следующий план перевозок:

 

 

Полученный на этом этапе новый план перевозок имеет пять базисных клеток в соответствующей ему транспортной таблице (см. таблицу выше).

r = 5

     Стоимость найденного плана перевозок равна:

L = 40×4 + 20×6 + 3×5 + 20×3 = 355

Еще раз попытаемся улучшить найденный опорный план перевозок. Для этого перейдем к пункту 2 алгоритма:

2.           Вычислим цену цикла для каждой свободной переменной.

3.           Максимальное количество груза, которое можно перенести по циклу единственной свободной переменной х₂₂, имеющей  отрицательную цену цикла, равно бесконечно малой величине e. Полагая e = 0, получим окончательный оптимальный план перевозок:

4.            

 

 

стоимость которого равна:

L = 40×4 + 20×6+ 3×5 +20×3 =355

 

Примененный метод «ликвидации вырождения» путем изменений запасов на бесконечно малую величину e не всегда удобен, так как требует дополнительных действий с бесконечно малыми величинами e. Значительно проще было бы не изменять запасы, а вместо величины e поставить в базисной клетке нуль. Тогда базисная клетка будет тем отличаться от свободной, что в ней нуль поставлен, а в свободной нет.

Дальнейшие манипуляции с транспортной таблицей будут идентичны тем, которые мы осуществляли в ситуациях, когда в базисных клетках стояли только положительные перевозки. Отличие состоит только в том, что когда одна из отрицательных вершин цикла окажется в базисной клетке с нулевой перевозкой, нужно переносить по этому циклу нулевую перевозку. Такой перенос нулевой перевозки  получил название фиктивный перенос.

Рассмотрим теперь другой метод решения транспортной задачи – метод потенциалов.

Решение транспортной задачи методлом потенциалов

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

Пусть задана некоторая классическая транспортная задача:

     Будем условно считать, что каждый из пунктов отправления  вносит за перевозку единицы груза платеж . В свою очередь каждый пункт назначения  также вносит за перевозку единицы груза платеж .

     Будем называть «псевдостоимостью» перевозки единицы груза по некоторому маршруту величину, равную сумме внесенных платежей пунктом отправления и пунктом назначения:

.

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

Теорема о платежах транспортной задачи

     Для заданной совокупности платежей  суммарная псевдостоимость плана перевозок, равная величине:

.

при любом допустимом плане перевозок  не зависит от конкретного плана перевозок, то есть сохраняет одно и то же постоянное значение.

Докажем это утверждение.

Доказательство

Теорема доказана.

Теорема об оптимальном плане транспортной задачи

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

Доказательство

     Обозначим  – допустимый план перевозок с соответствующей ему системой платежей , обладающий свойством оптимальности.

Определим стоимость этого плана:

.

Теперь попробуем изменить оптимальный план перевозок , преобразовав его в план .

Стоимость нового плана будет равна следующей величине:

Очевидно, что ввиду условия , действующего в транспортной таблице относительно стоимостей и соответствующих их псевдостоимостей, имеем следующее неравенство:

Теорема доказана.

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

Таким образом, нами доказано, что признаком оптимальности допустимого плана перевозок  является выполнение двух условий:

     План перевозок, обладающий таким свойством, называется потенциальным, а соответствующие ему платежи  - потенциалами пунктов  и .

Оптимальный план перевозок можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющих условию (а). Затем следует улучшить план, одновременно меняя систему платежей так, чтобы они приближались к потенциалам. При улучшении плана перевозок нам помогает следующее свойство платежей и псевдостоимостей:

     Для любой системы платежей , удовлетворяющей условию (а), каждая свободная клетка имеет цену цикла, равную разности между стоимостью и псевдостоимостью в этой клетке транспортной таблицы:

.

     Таким образом, можно предположить следующий алгоритм решения классической транспортной задачи методом потенциалов:

1.    Взять любой опорный план перевозок, в котором отмечены  базисные клетки.

2.    Определить для этого плана платежи  исходя из требования, чтобы в любой базисной клетке псевдостоимости были равны стоимостям:

.

     Очевидно, что один из платежей можно назначить произвольно, например, положить равным нулю, так как количество уравнений вида  всего равно величине , а число неизвестных .

3.    Подсчитать псевдостоимости  для всех свободных клеток. Если окажется, что выполняется условие  (условие (а)), то рассматриваемый план перевозок является оптимальным.

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

5.    Перейти к пункту 2.

 

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

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

 

 

Рассмотренным выше понятиям платежей за перевозку и псевдостоимостей можно дать следующую экономическую интерпретацию.

Пусть поставщики  и потребители  действуют как единая экономическая система, а платежи  - реальные платежи, которые участники системы  и  вынуждены платить за перевозку единицы груза «перевозчику».

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

Тогда с точки зрения вносимых за перевозку груза платежей оптимальным будет такой план перевозок, при котором пункты отправления и назначения  и  не переплачивают «перевозчику» ничего сверх объективной стоимости перевозок, то есть выполняется условие .

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

Для того, чтобы дать читателю возможность сравнить решение задачи различными методами и понять преимущества и недостатки этих методов по сравнению друг с другом, примеры данного раздела будут идентичны уже рассмотренным нами примерам.

Пример 3.  Решение транспортной задачи методом потенциалов.

Пусть задана некоторая классическая транспортная задача. Требуется найти методом потенциалов оптимальный план перевозок этой транспортной задачи, если она имеет следующую таблицу издержек:

 

 

 

Решение:

1.     Методом «северо-западного» угла найдем опорный план перевозок (см. таблицу ниже).

В дальнейшем при решении задачи мы будем по-возможности опускать комментарии, предполагая, что после изучения подробно уже решенных примеров у читателя не возникнет проблем с пониманием хода решения в рассматриваемом примере.

r = n + m – 1 = 4 + 3 – 1 = 6

     Посчитаем теперь стоимость найденного методом «северо-западного» угла опорного плана:

L = 22×10 + 9×7 + … = 796

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

 

 

2.     Определим для этого плана платежи  исходя из требования, чтобы в любой базисной клетке псевдостоимости были равны стоимостям:

Псевдостоимости будем записывать в левом верхнем углу. Один из платежей, например , выбираем произвольно .

 

 

3.     Подсчитаем псевдостоимости для всех свободных клеток:

 

 

Так как для некоторых свободных клеток – (2,1), (2,4), (3,1), (3,2) – не выполняется условие , то рассматриваемый план перевозок не является оптимальным.

4.     В соответствии с алгоритмом улучшим найденный план путем переноски груза циклу любой свободной клетки транспортной таблицы, в которой не выполняется условие . В качестве такой клетки возьмем, например, свободную клетку  (2,1), так как именно в ней имеет место максимальная разница между стоимостью и пседостоимостью:

 

 

В результате циклического переноса получим новый план перевозок (см. таблицу ниже).

 

 

5.     Перейдем к пункту 2.

 

 

 

 

Из анализа последней транспортной таблицы следует, что полученный план перевозок является оптимальным, так он удовлетворяет условиям (а) и (б). Рассчитаем стоимость найденного оптимального плана:

L = 31×7 + 22×5 + 3×6 + 3×5 + ×20×4 + 38×6 = 668

Как и следовало ожидать, мы получили тот же самый ответ, что и при решении этой задачи распределительным методом.

Пример 4.  Решение транспортной задачи с вырожденным планом перевозок  методом потенциалов.

Данная задача аналогична задаче из примера 2. На ее примере мы рассмотрим действия, которые необходимо предпринимать при возникновении в процессе решения задачи вырожденного плана. Забегая вперед, скажем, что для разрешения вырожденной задачи в методе потенциалов используются те же приемы, что мы видели в распределительном методе.

Итак, пусть задана некоторая классическая транспортная задача. Требуется найти оптимальный план перевозок, если данная задача имеет следующую таблицу издержек:

 

 

 

Решение:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Полагая бесконечно малую величину e равной нулю, имеем:

 

 

Решение транспортной задачи с промежуточными пунктами

Одно из практически важных обобщений классической транспортной задачи связано с учетом возможности доставки това­ра от i-го источника к j-му стоку по маршруту, проходящему через некоторый промежуточный пункт (склад). Так, на­пример, промежуточные пункты являются составной частью распределительной системы большинства крупных компаний, имеющих сети универсальных магазинов во многих городах. Такие компании, как правило, имеет зональные оптовые базы (источники), снабжающие товарами более мелкие региональные склады (промежуточные пункты), откуда эти товары поступают в рознич­ную торговую сеть (стоки). При этом товар для каждого фик­сированного стока в общем случае может быть доставлен не из любого источника и по маршрутам, не обязательно проходящим через все промежуточные пункты. Кроме того, промежуточ­ные пункты могут обладать вполне определенной спецификой. Так, например, при транспортировке товара от источника к стоку по маршруту, проходящему через склад, часть товара может быть использована для создания за­паса на складе.

Задачу выбора плана перевозок товаров от источников к стокам с учетом промежуточных пунктов, обеспечивающего минимальные транспортные затраты и потребности стоков, в исследовании операций называют транспортной задачей с промежуточными пунктами. Рассмотрим пример такой задачи.

Пример 5. Задача об оптовых складах.

Некоторая торговая компания имеет восемь крупных оптовых  складов, на ко­торых сосредоточены все имеющиеся в наличии запасы товара. Перед началом рекламной компании решено перераспределить часть запасов товара между складами в соответствии с прогно­зами сбыта в районах их размещения. Требуется разработать план перевозок товара между складами, который позволит при минимальных транспортных затратах создать на каждом скла­де необходимый в соответствии с прогнозами сбыта да данной территории запас товара.

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

-      номера складов (цифры 1-8 в кружках);

-      из­быток товара на складе (если он есть), который должен быть перераспределен в системе складов (он указан под соответствующим кружком с номером склада неотрицательным числом в единицах измере­ния товара);

-      недостаток товара на складе (если он есть), который должен быть устранен за счет его поставок с других складов системы (он указан под соответствующим кружком с номером склада от­рицательным числом и выражен в единицах измерения товара);

-      возможность перевозки товара со склада i на склад j (направленная дуга от кружка с номером i к кружку с номером j);

-      затраты, связанные с перевозкой единицы товара со склада i на склад j (величина  над соответствующей направленной дугой, выраженная в условных денежных единицах).

 

На данном рисунке видно, что суммарный избыток товара, имеющийся на складах системы с номерами 1 и 4, равен суммарному недостатку товара, имеющемуся на складах с номерами 3, 6 и 8 этой же системы. Перераспределение товара может проис­ходить через склады с номерами 2, 4, 5, 6 и 7, которые в рассматри­ваемой задаче и являются промежуточными пунктами.

Источ­ником является лишь склад с номером 1, на котором имеется избыток товара и с которого товар можно только вывозить. Стоками же являются склады с номерами 3 и 8, на которых есть недостаток товара. На эти склады товары можно только за­возить.

Заметим также, что между складами с номерами 4 и 5 возможны перевозки в обоих направлениях, но в общем слу­чае .

Таким образом, на рисунке фактически представлена сеть рассматриваемой транспортной задачи с промежуточными пунктами. Формаль­ное описание этой сети удобно представить в виде следующей таблицы:

 

1	1										+10
2	-1	1	1								0
3		-1		-1							-3
4				1	1	1	-1				2
5			-1		-1		1	1			0
6								-1	1		-1
7						-1			-1	1	0
8										-1	-8

Номер склада

Объемы перевозок

Избыток / недостаток

 

В приведенной таблице каждому узлу сети (складу) соответствует одна строка и каждой направленной дуге сети соответствует одна переменная модели , представляющая собой количество товара (в единицах его измерения), которое должно быть отправлено с i-го склада на j-ый склад. Каждой переменной модели  соответствует один столбец, в котором стоит 1 в i-ой строке, -1 в j-jой строке и  в последней строке. Обратите внимание на то, что в приведенной таблице на пересечении i-ой строки и последнего столбца находится число, равное избытку (если оно неотрицательное) или недостатку (если оно отрицательное) товара на i-ом складе (в единицах измерения товара).

Перейдем теперь к построению транспортной таблицы для рассматриваемой транспортной задачи с промежуточными пунктами. Параллельно с построением попытаемся отыскать доказательство возможности преобразова­ния этой задачи к классической транспортной задаче.

 

 

На первом этапе в исходной таблице нужно выделить строку для каждого источника и указать его «мощность» (избыток то­вара на складе). В данном примере источником является только склад с номером 1, мощность которого  = 10. В транспортной таблице этому складу будет соответствовать первый пункт производства с объ­емом поставок, равным 10.

На втором этапе в исходной таблице нужно выделить столбец для каждого стока и указать его мощность (недостаток това­ра на складе). В данном примере стоками являются третий и восьмой склады. Поэтому  и , что в транспортной таблице соответствует значениям спроса для пунктов потребления 3 и 8.

На третьем этапе нужно сделать следующее.

1. В транспортной таблице выделить строку и столбец для каждого промежуточного пункта. В данном случае промежуточными пунктами являются склады с номерами 2, 4, 5, 6 и 7, которые в транспортной таблице фигурируют как пункты производства и пункты потребления.

2. Для каждого k-го промежуточного пункта определить величину чистого запаса товара , равного объему из­бытка со знаком плюс либо объему недостатка со знаком ми­нус. В данном случае:

.

3. Определить суммарный объем избытка  на всех складах системы, используя последний столбец исходной таблицы. Суммарный объем избытка  представляет собой общий объем перевозок (в единицах измерения товара). В данном случае:

4. Считать, что маршрут транспортировки всего суммар­ного объема избытка товара может проходить через любой промежуточный пункт. Это означает, что любой склад с но­мером k, рассматриваемый как промежуточный пункт, может принять весь суммарный объем избытка товара. Таким образом, в данном случае

В транспортной таблице эти значения фигурируют как спрос.

5. Для каждого k-того промежуточного пункта определить мощность его источника , то есть объем товара, который может быть вывезен со склада с номером k. Так как на складе с номером k величина чистого запаса товара равна , а максимально возможный объем поставок определяется величиной , то:

В данном примере:

В транспортной таблице эти значения фигурируют как поставки.

На четвертом этапе необходимо для каждого k-го промежуточного пункта ввести переменную  при . В данном случае k Î {2, 4, 5, 6, 7}. Интерпретировать переменную  можно как объем товара, который оседает на складе с номером k.

При построении транспортной таблицы ранее нами была введе­на величина , имеющ  ая смысл динамического запаса или буфера в каждом промежуточном пункте. Для каждого k-го промежуточного пункта величина  входит как в , так и в . Поэто­му сумма заявок равна сумме запасов.

Значение  должно быть настолько велико, чтобы оно могло соответствовать лю­бому количеству товара, приходящему через k-ый промежуточ­ный пункт при любом допустимом решении исходной задачи. Поэтому значение  принимают равным суммарному объему избытка товара в системе.

В этом случае значение разности (-) представляет собой объем товара (в единицах его из­мерения), перевезенного через k-ый промежуточный пункт, так как  - максимально возможный объем поставок товара на склад с номером k, a  — объем товара, осевшего на этом складе. В нашей транспортной таблице заполнены лишь те клетки, которые содер­жат переменные , соответствующие направленным дугам сети, а также переменные , соответствующие промежуточ­ным пунктам. Именно в этом и заключается отличие нашей транспортной таблицы от классических транспортных таблиц, которые мы рассматривали ранее.

Следует отметить, что в исходной таблице заданы восемь ограни­чений и десять переменных, а в транспортной  таблице заданы уже тринадцать ограничений (по строкам и столбцам) и пятнадцать переменных. Увеличение размерно­сти на пять единиц объясняется наличием пяти промежуточных пунктов.

Осталось доказать эквивалентность (в смысле отыскания оптимальных решений) исходной транспортной задачи с промежуточными пунктами, представленной в исходной таблице, и соответству­ющей ей классической транспортной задаче.

Нетрудно убедиться в том, что в транспортной таблице строка, соот­ветствующая первому складу (исток), и столбцы, соответ­ствующие третьему и восьмому складам (стоки), задают те же ограничения, что и соответствующие строки в исходной таблице. Обратимся теперь к k-му складу, являющемуся промежуточ­ным пунктом, т.е. k Î {2, 4, 5, б, 7}. Пусть K - множество номеров складов, на которые товар может быть доставлен с k-го склада, а N - множество номеров складов, с которых товар может быть доставлен на k-ый склад. Тогда ограничение для k-го склада, заданное в исходной таблице, имеет следующий вид:

,

где  - величина, чистого запаса товара, введенная на третьем этапе построения рассматриваемой транспортной таблицы.

Так как соответ­ствующие ограничения, задаваемые в транспортной таблице (по строке и по столбцу), могут быть представлены следующим образом:

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

На этом дока­зательство того, что рассматриваемая транспортная задача с промежуточными пунктами эквивалентна классической транспортной задаче, можно считать завершенным.