Нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети

Рассмотрим постановку задачу нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети:

(1).

(2).

(3).

(4).

(5).

Выражение (1) означает, что необходимо найти минимальный маршрут перевозки максимального количества потока в транспортной сети за заданное количество моментов времени. Выражение (2) показывает, что максимальное количество потока за p периодов времени, равно потоку, выходящему из источника за p периодов времени Выражение (4) показывает, что максимальное количество потока за p периодов времени равно потоку, входящему в сток за p периодов времени Количество потока, входящее в источник за p периодов времени, равно количеству потока, покидающему сток за p периодов времени и равно. В (3) утверждается, что для каждого узла, кроме источника и стока, и каждого момента времени количество потока, вошедшее в в момент времени равно числу единиц потока, выходящему из в момент. Неравенство (5) показывает, что потоки для всех моментов времени должны быть меньше пропускных способностей по соответствующим дугам.

Иными словами, необходимо перевезти единиц потока с минимальными затратами в динамической транспортной сети, так, чтобы последняя единица потока вошла в сток в момент времени не позднее p.

Формальный алгоритм решения данной задачи:

Этап 1. Перейти от заданного нечеткого динамического графа к «растянутому во времени» на p интервалов нечеткому статическому графу путем «растягивания во времени» исходного динамического графа за заданное количество временных интервалов путем создания отдельной копии каждой вершины в каждый рассматриваемый момент времени. Пусть представляет собой «растянутый во времени» граф исходного динамического графа. Множество вершин графа задается как Множество дуг состоит из дуг, идущих из каждой пары «вершина-время» в каждую пару «вершина время» вида где и. Пропускные способности, соединяющие пары «вершина-время» с равны, стоимость перевозки единицы потока по дуге, соединяющей пару «вершина-время» с, равна Вводим искусственный источник и сток и соединяем дугами с каждым истинным источником, а с каждым истинным стоком. Фиктивные дуги, идущие от искусственных вершин, имеют бесконечную пропускную способность и нулевую стоимость. Ищем максимальный поток от к .

Этап 2. Строим нечеткую остаточную сеть для «растянутого во времени графа» в зависимости от величин, идущих по дугам графа потоков. Нечеткая остаточная сеть строится по «растянутой во времени» сети в зависимости от величин потоков, (далее), идущих по дугам последней следующим образом: каждая дуга в остаточной нечеткой сети, соединяющая пару «вершина-время» с парой «вершина-время», по которой поток отправляется в момент времени имеет нечеткую остаточную пропускную способность, стоимость с временем прохождения и обратную дугу, соединяющую с с остаточной пропускной способностью, стоимостью и временем прохождения потока по данной дуге.

Этап 3. Ищем путь минимальной стоимости по алгоритму Форда из искусственного источника в искусственный сток в построенной нечеткой остаточной сети, начиная с нулевых значений потоков.

(I) Если путь найден, переходим к этапу 4.

(II) Если пути не удалось найти, то получен максимальный поток минимальной стоимости в растянутом во времени статическом нечетком графе из в, и переходим к шагу 5.

Этап 4. Пускаем по найденному пути максимальное количество единиц потока в зависимости от ребра в остаточной сети с минимальной остаточной пропускной способностью .

Этап 5. Обновляем значения потоков в графе: для дуг, соединяющих пару «вершина-время» с в с неположительной модифицированной стоимостью изменяем поток по соответствующим дугам, идущим из в из с на. Для дуг, соединяющих пару «вершина-время» с в с неотрицательной модифицированной стоимостью изменяем поток по дугам, идущим из в из с на и переходим к этапу 2, начиная с нового значения потока по дугам и заменяя значение потока в графе: .

Этап 6. Если найден максимальный поток минимальной стоимости в графе из фиктивного источника в фиктивный сток, определяемый множеством путей, переходим к первоначальному динамическому графу следующим образом: отбрасываем искусственные вершины, и дуги, соединяющие их с другими вершинами. Таким образом, в исходном динамическом графе получен максимальный поток минимальной стоимости, эквивалентный потоку из источников (начальная вершина исходного графа, растянутая на p интервалов) в стоки (конечная вершина, растянутая на p интервалов) в графе после удаления фиктивных вершин, а каждый путь, соединяющий вершины и, по которому идет поток стоимости соответствует потоку. стоимости .