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

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

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

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

2. Транспортные задачи в сетевой постановке

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

Исходный граф транспортной задачи легко сводится к сети с одним стоком и одним истоком путем введения фиктивных пунктов t (исток) и s (сток). Фиктивным дугам приписываются значения параметров: d_ti=a_i, d_js=b_j, C_ti=C_js =0. Пример сети транспортной задачи без промежуточных пунктов приведен на рис. 2

Модель Т_d-задачи в сетевой постановке имеет вид:

åå C_ijx_ij ®min; (2.1)

k ¹ t, k ¹ s; (2.2)

(2.3)

В сбалансированной транспортной задаче

Z =å a _i=å b_j; (2.4)

0£ x_ij £ d_ij. (2.5)

Равенства (2.2) отражают условия баланса для всех пунктов кроме источника и стока. Баланс для последних представлен уравнением (2.3). В модели использованы обозначения: – множество дуг, входящих в вершину k и выходящих из нее, Z – новая величина, называемая потоком сети.

Наибольший интерес представляет постановка задачи, в которой критерием является поток сети:

Z ® max; (2.6)

k ¹ t, k ¹ s; (2.7)

(2.8)

0£ x_ij £ d_ij. (2.9)

Задача (2.6) – (2.9) называется задачей о максимальном потоке. Она имеет большое практическое значение. Для нее разработаны алгоритмы, которые эффективнее методов решения транспортных задач. Они работают непосредственно с сетью как разновидностью графов.

В связи с этим напомним понятие разреза графа (сети), которое используется в основополагающей теореме Форда-Фалкерсона.

Пусть дан ориентированный граф G= (V,U), где V и U -множества вершин и дуг соответственно. Разрезом сети на подмножестве вершин A Ì V, A ¹Æ, A ¹ V, tÎ A, sÎ V\A называется множество дуг ij Î U таких, что i Î A & j Î V\A. Обозначим его P(A). Сумма пропускных способностей дуг разреза называется величиной (пропускной способностью) разреза:

Пример. Построим один из разрезов сети, приведенной на рис.3.

Если A ={t,1,2,3}, то разрезом будет множество дуг P(A)={1,4; 1,6; 2,5; 3,6}, а его величина определяется как d (A)= d₁₄+d₁₆+d₂₅+d₃₆. Дуги, составляющие этот разрез, выделены жирными линиями.▲

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

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

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

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

Дата добавления: 2014-01-11