Студопедия

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

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Дадим формулировку задачи о максимальном потоке в терминах линейного программирования.

Пусть ХKM - объем перевозок из пункта К в пункт М.

Согласно рис.4 К = 0, 1, 2, 3, М = 1, 2, 3, 4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных ХKM, а именно, Х01, Х02, Х03, Х12, Х13, Х14, Х23, Х24, Х34 .

Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F → max,

Х01 + Х02 + Х03 = F (0)

- Х01 + Х12 + Х13 + Х14 = 0 (1)

- Х02 - Х12 + Х23 + Х24 = 0 (2)

- Х03 - Х13 - Х23 + Х34 = 0 (3)

- Х14 - Х24 - Х34 = - F (4)

Х01 ≤ 2

Х02 ≤ 3

Х03 ≤ 1

Х12 ≤ 4

Х13 ≤ 1

Х14 ≤ 3

Х23 ≤ 1

Х24 ≤ 2

Х34 ≤ 2

ХКМ ≥ 0, К, М = 0, 1, 2, 3, 4

F ≥ 0.

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему.

Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не " рождаются" в ней.

Условие (4) - это условие " выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом (" вход" равен " выходу").

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

Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок.

Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом " не знает").

 

4. Алгоритм Форда–Фалкерсона (алгоритм расстановки пометок)

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

Увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Дугу из вершины 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 поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной.

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

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

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.