Решение задачи по критерию времени

Такая задача исходно является нелинейной, но может быть легко преобразована к линейной. Любым из способов строится начальный план перевозок. Затем определяется текущее значение критерия Т⁽⁰⁾ как максимальное время в занятых клетках (x _ij> 0). Пусть на k- й итерации получен план со значением критерия Т^(k). Оно может быть уменьшено, если освободить клетку с t_ij= Т^(k). С этой целью на клетке строится разгрузочный цикл так, чтобы в нечетных вершинах выполнялось неравенство t_ij< Т^(k), а в четных – x _ij> 0 (исходная вершина – четная). Такие правила позволяют в общем случае строить более одного цикла на выбранной клетки. В цикле вычисляется q₀ как минимальная перевозка в четных вершинах. Вычитая q₀ в четных вершинах и прибавляя в нечетных, получаем новый план. Если клетка с максимальным временем была единственной и перевозка в ней стала равна нулю, новый план улучшил значение критерия. Если клетка не обнулилась, то на ней строится другой разгрузочный цикл. В случае нескольких клеток со временем Т^(k) для улучшения критерия необходимо разгрузить все. Решение завершается, когда нельзя разгрузить клетку (клетки), определяющую значение критерия. Рассмотренный метод не гарантирует получение оптимального решения.

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

Транспортную задачу можно представить в виде о риентированного графа с одним истоком (в него не входит ни одна дуга) и с одним стоком (из него не выходят дуги), который называют в этом случае сетью. Вершинам графа ставятся в соответствие пункты отправления, назначения и промежуточные пункты. Основной параметр вершины – количество груза. Дуги отображают коммуникации. Им могут быть приписаны такие параметры как количество груза, затраты на перевозку, пропускная способность. Исходный граф транспортной задачи легко сводится к сети с одним стоком и одним истоком путем введения фиктивных пунктов t (исток) и s (сток). Фиктивным дугам приписываются значения параметров: d_ti=a_i, d_js=b_j, C_ti=C_js =0.

Модель Т_d-задачи в сетевой постановке имеет вид: å å C_ijx_ij ®min; (29)

k ¹ t, k ¹ s; (30) (31)

В сбалансированной транспортной задаче: Z =å a _i=å b_j; (32) 0£ x_ij £ d_ij. (33)

Равенства (30) отражают условия баланса для всех пунктов кроме источника и стока. Баланс для последних представлен уравнением (31). В модели использованы обозначения: – множество дуг, входящих в вершину k и выходящих из нее, Z – новая величина, называемая потоком сети. Наибольший интерес представляет постановка задачи, в которой критерием является поток сети: Z ® max; (34)

k ¹ t, k ¹ s; (35) (36) 0£ x_ij £ d_ij. (37) Задача (34) – (37) называется задачей о максимальном потоке. Понятие разреза графа (сети), которое используется в основополагающей теореме Форда-Фалкерсона. Пусть дан ориентированный граф G= (V, U), где V и U - множества вершин и дуг соответственно. Разрезом сети на подмножестве вершин A Ì V, A ¹ Æ, A ¹ V, tÎ A, sÎ V\A называется множество дуг ij Î U таких, что i Î A & j Î V\A. Обозначим его P(A). Сумма пропускных способностей дуг разреза называется величиной (пропускной способностью) разреза:

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

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

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

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

Аналогом цикла пересчета является увеличивающая цепь. Это цепь, соединяющая исток и сток, все дуги которой допустимые. Дуга является допустимой увеличивающей, если ее направление совпадает с направлением потока и поток на ней меньше пропускной способности, то есть x_ij< d_ij. Дуга считается допустимой уменьшающей, если направление дуги противоположно потоку и x_ij > 0.

На увеличивающей дуге поток может возрасти на величину q_ij=d_ij-x_ij, а на уменьшающей дуге возможно снижение потока, равное q_ij = x_ij. Следовательно, максимальное допустимое изменение величины потока по увеличивающей цепи определяется как минимальное из возможных: q₀ = (38)