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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 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), что соответствует закрытию строки или столбца: переменные в остальных клетках строки или столбца будут равны нулю. Конкретнее, если X₁₁=а₁, то закрывается первая строка и X₁₂=X₁₃=…=X_1n=0, а следующей базисной переменной будет X₂₁. Из указанного выше принципа следует X₂₁=min(a₂, b₁-a₁). Если же окажется, что X₁₁=b₁, то закроется первый столбец и следующей базисной переменной станет X₁₂=min(a₁-b₁, b₂).

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

Общее правило определения значения очередной базисной переменной: X_ij=min(остаток от a_i, остаток до b_j). (5.13)

Из него следует, что на каждом шаге закрывается или строка, или столбец, а на последнем шаге при назначении X_mn закрываются одновременно 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