Транспортные задачи (стр. 1 )

Глава 5. ТРАНСПОРТНЫЕ ЗАДАЧИ

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

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

5.1. Основные модели транспортных задач

5.1.1. Простейшая транспортная задача (Т-задача)

Эта задача является основополагающей для всех транспортных задач. Пример такой задачи приведен в разд. 4.9.

В общем случае исходными данными являются:

m – число пунктов отправления (ПО) или производства;

n – число пунктов назначения (ПН) или потребления;

Cij – затраты на перевозку единицы груза из пункта i в пункт j, "ij;

ai – количество груза в пункте i, "i (возможности ПО);

bj – потребность в грузе в пункте j, "j.

Критерием задачи являются суммарные затраты на перевозку. Безотносительно к значениям ai и bj модель записывается в виде

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

(5.1)

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

(5.2)

(5.3)

(5.4)

"Xij ³

Элементы модели:

– матрица перевозок;

– матрица транспортных затрат;

a=(a1, a2, . . . , am) – вектор возможностей ПО;

b=(b1, b2, . . . , bn) – вектор потребностей ПН.

Отметим особенности рассматриваемой задачи:

¨  Модель содержит две группы условий, размерность которых равна соответствующему числу ПО и ПН; число переменных равно произведению m´n;

¨  Все коэффициенты при переменных в условиях (5.3), (5.4) равны единице;

¨  Каждая переменная входит в условия ровно 2 раза, один и только один раз в группу (5.3) и также один раз в группу (5.4);

¨  Задача имеет простые условия разрешимости, которые определяются следующей теоремой.

Теорема.

Для разрешимости Т-задачи необходимо и достаточно, чтобы она была сбалансированной.

Замечание. Теорема справедлива при конечных значениях Сij.

Приведем доказательство.

Необходимость доказывается исходя из того, что задача (5.2)-(5.5) разрешима. В этом случае все условия задачи выполняются. Просуммируем условия (5.3) по i, а условия (5.4) по j:

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

Достаточность доказывается конструктивным способом.

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

Ограниченность переменных снизу задана явно, а ограничение сверху следует из конечности всех ai и bj, больше которых переменные быть не могут. Следовательно, множество ограничено.

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

(5.6)

Очевидно, что оно неотрицательно. Остается проверить выполнение основных условий задачи. Подставив (5.6) в левую часть(5.3), получим:

Þ решение удовлетворяет условиям (5.3).

Подставив первый вариант (5.6) в (5.4), также убеждаемся в выполнении этих условий:

.

Таким образом, допустимое множество сбалансированной задачи непустое и ограниченное, а, значит, задача всегда разрешима. ▲

Условия (5.3), (5.4) – линейно зависимы из-за сбалансированности задачи. Действительно, пусть известны все равенства (5.3) и (n-1) равенство (5.4). Просуммируем отдельно первые и вторые и затем из первой суммы вычтем вторую. В результате получим недостающее равенство, описывающее пункт потребления, не включенный в исходную систему (5.4). Можно строго показать, что число линейно-независимых уравнений или, иначе, ранг системы (5.3), (5.4) равен m+n-1. Следовательно, такую размерность имеют базис и базисное решение Т-задачи.

5.1.2. Транспортная задача с ограниченными пропускными способностями (Td - задача)

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

(5.7)

(5.8)

(5.9)

0 £ Xij £ dij, "i, j, (5.10)

где dij –пропускная способность коммуникации i j.

Ограничения (5.10) вносят существенные коррективы в свойства задачи. Из особенностей модели, присущих Т-задаче, сохраняются все, кроме последней. В Тd-задаче условие сбалансированности не является достаточным для разрешимости задачи. Более того, в число необходимых условий существования решения помимо его входят еще две группы условий, отражающих физическую реализуемость решения:

(5.11)

(5.12)

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

Однако и выполнение всех необходимых условий не гарантирует разрешимость Тd-задачи. Например, условия (5.1), (5.11) и (5.12) выполняются для транспортной сети, показанной на рис. 5.1, что легко проверить. Но задача неразрешима, так как невозможно поставить во второй пункт назначения 8 единиц груза.

5.1.3. Задачи с неоднородным грузом

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

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

Взаимозаменяемость грузов характеризуется коэффициентом взаимозаменяемости . Например, если 1 т. каменного угля заменяет потребителю 2 т. бурого, то Зная все грузы можно привести к одному виду. Затем вместо одного исходного ПО вводится столько, сколько в нем видов груза. Аналогично каждый исходный ПН заменяется новыми, число которых равно числу видов потребностей. Наконец, определяются приведенные затраты на перевозки между всеми новыми пунктами. Если виды грузов в ПО и ПН совпадают, затраты на перевозку равны исходным Cij; если же они разные, то перевозка запрещается (Cij=М). Между ПО с пересчитанным грузом и ПН с взаимозаменяемой потребностью затраты равны

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

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

5.1.4. Многоиндексные задачи

Для учета дополнительных условий перевозки вводятся переменные с числом индексов более двух. В таких случаях говорят о многоиндексных транспортных задачах. Например, если существенное значение имеет вид транспорта, то в модели используются переменные Xijk, означающие количество груза, перевозимое из i-го пункта в j-й k-ым видом транспорта. Модель трехиндексной задачи зависит от конкретных условий. Если в исходных данных имеем производительность каждого вида транспорта pk и не учитываются пропускные способности, то задача описывается трипланарной моделью:

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

Если транспортные средства принадлежат разным перевозчикам, то в модели будут фигурировать четырехиндексные переменные Xijkl, где l – индекс перевозчика.

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

5.1.5. Транспортные задачи по критерию времени

При осуществлении перевозок определяющим показателем могут быть не затраты, а время доставки. Характерными примерами являются чрезвычайные ситуации, перевозка раненых, скоропортящихся продуктов и т. п. В таких задачах главное – как можно быстрее доставить все грузы. Тогда вместо матрицы транспортных затрат дается матрица времени [tij], а критерий выражает время завершения всех перевозок:

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

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

5.2. Метод потенциалов

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

Сначала рассмотрим метод применительно к Т-задаче, а затем сделаем дополнения, позволяющие решать Тd-задачу.

5.2.1. Построение начального плана перевозок

Как было показано выше, размерность базисного решения или плана перевозок равна m+n-1, где m и n – число ПО и ПН сбалансированной задачи. Если задача открытая, то сначала ее необходимо сбалансировать.

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

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

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

Правило северо-западного угла

Все исходные данные и переменные сбалансированной Т-задачи удобно представить в виде таблицы (табл. 5.1).

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

Таблица 5.1

	b1	b2	…	bn
	C11 X11	C12 X12	…	C1n X1n
	C21 X21	C22 X22	…	C2n X2n
…	…	…	…	…
	Cm1 Xm1	Cm2 Xm2	…	Cmn Xmn

Так как оно должно быть максимально допустимым, то

При этом обязательно выполнится одно из равенств (5.3), (5.4), что соответствует закрытию строки или столбца: переменные в остальных клетках строки или столбца будут равны нулю. Конкретнее, если X11=а1, то закрывается первая строка и X12=X13=…=X1n=0, а следующей базисной переменной будет X21. Из указанного выше принципа следует X21=min(a2, b1-a1). Если же окажется, что X11=b1, то закроется первый столбец и следующей базисной переменной станет X12=min(a1-b1, b2).

Весь процесс построения начального плана можно представить в виде следующего дерева решений.

Общее правило определения значения очередной базисной переменной:

Xij=min(остаток от ai, остаток до bj). (5.13)

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

Пример 5.1. Исходные данные и построение начального плана показано в табл. 5.2. Значения базисных переменных выделены красным (серым) цветом, а порядок движения по клеткам отражен стрелками. Этому плану соответствуют суммарные затраты L=1295.

Таблица 5.2

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4
A1	6 75	7 25	3	5	100
A2	1	2 55	5 60	6 35	150
A3	3	10	20	1 50	50
Потребность в грузе	75	80	60	85	300

Правило минимального элемента.

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

Первой заполняется клетка с минимальными затратами. Пусть minCij=Ckp. Тогда Xkp=min(ak, bp). Если при этом закрывается строка k, то в столбце p ищем клетку с минимальными затратами и определяем значение соответствующей переменной согласно (5.13). При закрытии столбца p действуем аналогично в строке k. В общем случае клетка, лежащая в закрытом столбце и/или закрытой строке является закрытой, иначе – открытой. На каждом шаге движение идет либо по столбцу, либо по строке и при этом отыскивается среди открытых клетка с минимальным значением Cij.

Пример 5.2. Построим начальный план по правилу минимального элемента для задачи из примера 1. Результат представлен в табл. 5.3.

Таблица 5.3

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4
A1	6	7 5	3 60	5 35	100
A2	1 75	2 75	5	6	150
A3	3	10	20	1 50	50
Потребность в грузе	75	80	60	85	300

При таком начальном плане L=665, что меньше чем в примере 1. Однако нельзя утверждать, что для любых данных этот способ дает лучший план. Правильнеее говорить, что правило минимального элемента эффективнее в среднем (на множестве задач). В то же время алгоритм реализации этого правила сложнее, чем правила северо-западного угла.