Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Постановка транспортной задачи. Балансировка задачи.




Имеется двудольный граф

a,b – объем товара

с – стоимость доставки товара

И.Д.: ai , i = 1..n (количество единиц товара от поставщиков)

Bj, j = 1..m (количество единиц товара потребителям)

cji – стоимость транспортировки единицы товара от i-го поставщика j-ому потребителю (руб./ед.товара)

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

a) Штрафы за недопоставку ед.товара j-ому потребителю С2j , j = 1..m ( < )

b) Издержки на хранение оставшегося на складе товара (стоимость хранения товара на i-ом складе) С1i , i = 1..n ( > )

Балансировка задачи:

Под балансировкой транспортной задачи будем понимать задачу, в которой = .

Сведение Т.З. к сбалансированной:

a) <

Вводится фиктивный поставщик, при этом весь недостающий товар - =

Сn+1,j = C2j


b) >

Вводится фиктивный потребитель, при этом требуемый товар - =

Сi,m+1 = C1i

 


Сведение транспортной задачи к задаче линейного программирования.

П.З.: Пусть имеются 2 поставщика и три потребителя

С = (стоимость перевозок)

Целевая функция:

Обозначим xij – план перевозок, т.е. сколько единиц товара следует перевезти от i-ого поставщика j-ому потребителю.

Ограничения:


Постановка транспортной задачи. Поиск допустимого нач.решения. Метод С-З угла. Метод min стоимости.

(Из предыдущего вопроса)

П.З.: Пусть имеются 2 поставщика и три потребителя

С = (стоимость перевозок)

Найти: план перевозок, т.е. сколько единиц товара следует перевезти от i-ого поставщика j-ому потребителю.

Метод СЗ угла:

= 4·300+5·100+5·0+3·0+6·100+4·400=3900 руб.

Метод min стоимости:

Начинаем с клеточки, где min стоимость (3).

= 4·0+5·200+5·200+3·300+6·0+4·200=3700 руб.


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

Пусть имеются 3 поставщика и 4 потребителя.

U, V – потенциалы.

1)Сбалансируем задачу:

 

2)Определить начальн. допустимый план:

= 9·200+4·150+6·50+3·250+5·150+3·100+3·100=4800 руб.

3)Определение включаемой в базис переменной.

Определение потенциалов:

Ui, i=1..n; Vj, j=1..m

Базисные переменные:

Для базисных переменных: Ui+Vj=Cij (стоимость перевозки):

U1+V2=9; U2+V1=4; U2+V2=6; U2+V3=3; U2+V4=4;U3+V1=3;

U4+V4=3.

7 уравнений и 8 неизвестных => 1 переменная свободная, принимаем ее = 0.

Н-р: U1=0 => U2=-3; U3=-4; U4=-5; V1=7; V2=9; V3=6; V4=8.

Коэффициенты целевой функции (для Симплекс метода):



Включ. в базис переменная X11.

4)Определение исключаемой из базиса переменной.

Построение цикла

5)Определение потенциалов:

 

Включаем в базис переменную С32.

Исключаем переменную X12 (=0).


32. Задача о построении минимального покрытия графа (остова)

ПЗ: Имеется сеть из N узлов. Соединение между узлами оценивается в единицах (н-р, расстояние в м, км, ст. в руб.).

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

Общая протяженность д.б. минимальной. Остовы:

Метод решения: Метод определения минимального остова::

 

1. Выбираем самое минимальное соед., заносим соед-ые узлы в список:

P Сп1={(3,4)}; список1={3,4};

2. Пока не все вершины находятся в списке: 2.1

2.1 Определим узел, не принадлежащий списку, из которого имеется самое мин. сиз которого имеется самое мин. ащий списку2.1

до множества узлов, принадлежащих списку. Добавляем это соед. в остов

P Cп2={(3,4);(2,4)} Cп2={3,4,2}

P Cп3={(3,4);(2,4);(2,5)} Сп3 = {3,4,2,5}

P Cп3={(3,4);(2,4);(2,5);(1,3)} Сп4={3,4,2,5,1}

P Cп5={(3,4);(2,4);(2,5);(1,3),(3,6)} Сп5= {3,4,2,5,1,6} P Cп – список ребер!


33.Задача о минимальном пути. Метод потенциалов

Дано:

N узлов сети и дана матрица расстояний (стоимости) соед. между уздами. Требуется найти путь минимальной длины из узла № N1 до узла № N2. Граф может быть ориентированным N1=Y1 N2=Y8

 

 
01 61 71 81 01 01 01 01
61 01
71 01
81 01
01 01
01 01
01 01
01 01

 

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

Начальной вершине присваиваем 0-ой потенциал. Потенциал – минимальное расстояние между вершиной, имеющей потенциал, и другой вершиной.

1.Определение потенциала начального узла φ1=0, Сп ={1}, Edgesij=0, i,j=1..n – это ребра

2. Расчет потенциалов:

2.1. Для каждой вершины k из списка рассмотрим ребра вида Edgeskj=0, Если φj > φk +Ckj то φj = φk +Ckj , Edgeskj=0, Сп = Сп +{j}

2.2. Если существует i, j такое что Edgesij=0, то возврат к п. 2.1.

3. Определение минимального пути. Путь = (N2)

3.1. Для первой вершины имеющегося пути, k ищем j: Cjk = φk - φj

3.2. Добавляем путь Путь = Путь +{j}

3.3. Если j ≠ N1 то идти к п. 3.1

4. Вывод пути и его стоимости

Пример:

1). Сп={1}, Edgesij=0, φ1=0

2). φ2=6, φ3=7, φ4=8. Сп={1,2,3,4}

3). φ5=13, φ3=16, φ3=10 (т.к. φ3:10>7, то оставляем 7), φ6=15, φ7=17, φ7=15

4). Сп = {1,2,3,4,5,6,7}, φ8=19.

φ:

5. Нахождение оптимального пути:

Путь1=(Y5,Y8)

Путь2=(Y2,Y5,Y8)

Путь3=(Y1,Y2,Y5,Y8)


Алгоритм Форда-Фалкерсона

Впервые был предложен в 1956г. До этого времени задача решалась с помощью методов линейного программирования, что было крайне не эффективно. Алгоритм является псевдополиномиальным и имеет оценку O(nm log U), где m = |E|, n = |V|, U = max(Cij).

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

Увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Дугу из вершины a в вершину b назовем допустимой, если выполняется одно из следующих условий:

1. f(e) < c(e) и дуга согласованна

2. f(e) > 0 и дуга несогласованна

По увеличивающей цепи можно пустить поток величины Q, где Q = min{q(ei), 1 ≤ i ≤ l} и q(e) = {с(e) – f(e), если дуга согласованна, f(e), если дуга не согласованна}. Для того, чтобы увеличить величину потока сети на Q, необходимо увеличить на Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной.

В своей работе [3] Форд и Фалкерсон (Ford and Fulkerson) доказали, что поток в сети, для которой нельзя построить увеличивающую цепь, является максимальным.

 

Для нахождения увеличивающей цепи ими был предложен “Метод расстановки пометок”. Процесс расстановки меток начинается в источнике сети и заканчивается в ее стоке. Как только сток оказался помеченным, мы можем говорить о существовании увеличивающей цепи из источника в сток. Метка, “наносимая” на вершины сети, содержит необходимый минимум информации, достаточный для того, чтобы восстановить эту цепь и определить величину, на которую можно изменить поток в ней. Вершина сети может находиться в одном из 3-х состояний: “непомеченная”, “помеченная” и “просмотренная”.

 

Этап 1. Расстановка меток.

Все вершины получают статус непомеченных.

Процедура расстановки меток.

Возьмем произвольный помеченный, но не просмотренный узел x. Пусть он имеет пометку [i, +, e(x)], где i – вершина из которой был помечен x; флаг, показывающий, что дуга (i,x) согласованна; e – величина потока, который можно пропустить по этой дуге. Рассмотрим все непомеченные смежные вершины y, такие что дуга (x, y) согласованна. Пометим вершину y меткой [x, +, e(y)], где e(y) = min{e(x) , c(x, y) – f(x, y)}. Затем рассмотрим все непомеченные смежные вершины y, соединенные с ней несогласованной дугой. Пометим их меткой [x, -, e(y)], где e(y) = min{e(x), f(y,x)}. Теперь все рассмотренные узлы y имеют статус помеченных, а узел x - просмотренный.

Эта общая для всех узлов сети процедура. Пометим источник меткой [~, ~, ∞] и будем последовательно вызывать ее для всех смежных узлов, постепенно двигаясь по сети. Как только процедура будет вызвана для стока, будет получена увеличивающая цепь и следует перейти ко второму этапу. В противном случае процедура будет вызываться, пока все помеченные вершины не станут просмотренными, и если сток сети не был достигнут – увеличивающая цепь не может быть построена и по теореме Форда-Фалкерсона имеющийся поток сети является максимальным.

 

Этап 2. Изменение потока.

Процедура изменения потока дуги.

Возьмем узел x. Если он имеет метку [y, +, e], то увеличим поток по дуге (y, x) на e. Если он имеет метку [y, -, e], то уменьшим поток по дуге (y, x) на e. Если y не является источником, то вызовем процедуру для узла y.

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

 

Следует особо отметить, что узлы, имеющие статус “помеченных”, больше не участвуют в процессе поиска увеличивающей цепи, весьма эффективно с вычислительной точки зрения.[1][1]

 

Алгоритм Форда-Фалкерсона гарантирует нахождение максимального потока только в сетях с целочисленными пропускными способностями. На практике “чистый” алгоритм Форда-Фалкерсона не применяется, т.к. оценка его производительности зависит от величины пропускных способностей дуг сети. Все дело в том, что в нем не дается каких либо правил выбора увеличивающей цепи.

Рассмотрим сеть на рис. 1. Предположим, что реализован алгоритм, отдающий предпочтение увеличивающим цепям максимальной длины. В этом случае на первом шаге мы пустим дополнительный поток по цепи (0,1),(1,2),(2,3).

 

рис. 1 рис. 2

 

На втором шаге выберем цепь (0,2),(2,1),(1,3). Так как дуга (2,1) несогласованна, величина пущенного по ней потока будет вычитаться из величины потока, полученного на предыдущем шаге. Мы получили сеть (рис. 3) практически эквивалентную исходной.

рис. 3

 

Очевидно, что для нахождения максимального потока понадобиться 1000 итераций! В то время, как если бы мы на первом шаге выбрали цепь (0,1),(1,3), то результат был бы получен за одну итерацию! На практике, величина пропускных способностей часто зависит от единиц измерения, и может принимать огромные значения. Если же допустить иррациональные пропускные способности дуг, то можно привести пример невычислимой сети [4]. Величина потока в такой сети не превысит даже четверти истинного значения. Подобная неопределенность длилась не долго, уже в начале 70-х г. были предложены сразу 2 правила выбора увеличивающих цепей, которые существенно улучшают алгоритм Форда-Фалкерсона.

 

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

Время работы алгоритма зависит от того, как ищется дополняющий путь. Логично было бы искать его методом поиска в ширину, в этом случае путь будет кратчайшим из всех дополняющих путей(если длину каждого ребра считать единицей). Эта реализация метода Форда-Фалкерсона называется алгоритмом Эдмондса-Карпа. Время его работы есть O(V*E2).

К задаче о максимальном потоке в сети сводятся некоторые комбинаторные задачи — например задача о максимальном паросочетании в двудольном графе (см. соотв. визуализатор).

Чтобы решить эту задачу, добавляем к имеющемуся графу две вершины, одна из которых будет истоком, а вторая — стоком и соединяем соотв. исток с каждой вершиной одной доли, а сток — с каждой вершиной другой. При этом все пропускные способности ставим одинаковые — например по 1, а все ребра превращаем в дуги, направленные от истока к стоку. Если найти в получившейся сети максимальный поток, тогда величина его будет равна мощности максимального паросочетания, а дуги, по которым будет течь этот максимальный поток и будут насыщенными ребрами максимального паросочетания.

 

 


 

Последнее изменение этой страницы: 2017-09-22

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...