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

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

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

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

6. Оптимизация транспортных потоков. Метод потенциалов

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

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

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

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

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

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

Так как оно должно быть максимально допустимым, то Если 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).(13)

Таким образом, число базисных переменных равно m+ n-1. Построение начального плана завершено.