Транспортная задача

Тема 2. Транспортная задача Лекция 4 2 Пример 1. Песчаные карьеры 3 В районе имеется два песчаных карьера, с которых вывозится песок на 5-тонных грузовиках. В этом же районе имеется три завода железобетонных конструкций – потребителей песка, которым требуется соответственно 80, 90 и 130 грузовиков песка в день. Стоимости перевозки песка одним грузовиком от карьеров – поставщиков к заводам – потребителям известны. Необходимо составить план перевозок, минимизирующий суммарные транспортные издержки. Пример 1. Песчаные карьеры Заводы Карьеры с11 100 A1 с21 с12 с22 200 A2 с23 с13 B1 80 B2 90 B3 130 Транспортные издержки 𝑐𝑖𝑗 4 Завод В1 Завод В2 Завод В3 Карьер А1 4 6 3 Карьер А2 8 4 5 Сетевая модель ТЗ. Основные понятия Пусть 𝑁 = {𝑥} – конечное (заданное) множество узлов ( 𝑁 = 𝑛 ) и пусть 𝑢: 𝑁 × 𝑁 → 𝑅1 – заданная функция, называемая функцией пропускной способности. Тогда говорят, что задана сеть. Сеть 𝑁, 𝑢 – это конечный граф без циклов и петель, ориентированный в одном общем направлении, с заданной функцией пропускной способности. 5 Сетевая модель ТЗ. Основные понятия Пропускная способность ребра – максимальное количества груза (вещества), которое может быть провезено от 𝑥 к 𝑦: 𝒖(𝒙, 𝒚). Если 𝑢(𝑥, 𝑦) = 0, перевозка от 𝑥 к 𝑦 невозможна. 6 В рамках ТЗ предполагается, что пропускная способность принимает только целочисленные значения: 𝑢: 𝑁 × 𝑁 → 𝑍 Поток в сети Потоком в сети 𝑁, 𝑢 называется функция 𝑓: 𝑓: 𝑁 × 𝑁 → 𝑅1 удовлетворяющее свойствам: ∀ (𝑥, 𝑦) ∈ 𝑁 × 𝑁 ⟹ 7 1. 𝑓 𝑥, 𝑦 = −𝑓 𝑦, 𝑥 (кососимметрия) 2. 𝑓 𝑥, 𝑦 ≤ 𝑢 𝑥, 𝑦 (допустимость) В рамках ТЗ предполагается, что поток принимает только целочисленные значения: 𝑓: 𝑁 × 𝑁 → 𝑍 Функции от множества A  N, g – некоторая функция на N g  A    g ( x) xA A  N, B  N, R( x, y ) – некоторая функция на  x, y  R  A, B    xA, yB 8 R ( x, y ) Свойства функций от множества g  A  B   g  A  g  B  , A  B   R  A  B, C   R  A, C   R  B, C  , A  B   R  A, B  C   R  A, B   R  A, C  , B  C   9 Свойства потока в сети 1. 𝑓 𝑥, 𝑦 = −𝑓 𝑦, 𝑥 (кососимметрия) 2. 𝑓 𝑥, 𝑦 ≤ 𝑢 𝑥, 𝑦 (допустимость) 1 → 1′ : 𝑓 𝐴, 𝐴 = 0 A  N 2 → 2′ : 𝑓 𝐴, 𝐵 ≤ 𝑢 𝐴, 𝐵 A, B  N 𝑓 𝐴, 𝐵 – полный (суммарный) поток из А в В 10 𝑢 𝐴, 𝐵 – полная (суммарная) пропускная способность рёбер, начинающихся в А и заканчивающихся в В. Источники и стоки Узел 𝑠 ∈ 𝑁 называется источником сети 𝑁, 𝑢 , если 𝑓 𝑠, 𝑁 > 0. Узел 𝑠 ′ ∈ 𝑁 называется стоком сети 𝑁, 𝑢 , если 𝑓 𝑠 ′ , 𝑁 < 0. Будем предполагать, что в сети 𝑁, 𝑢 имеется один исток и один сток. (Предположение единственности). Тогда для всех 𝑥 ≠ 𝑠, 𝑥 ≠ 𝑠 ′ выполнено: 𝑓 𝑥, 𝑁 = 0 11 – промежуточные узлы. Мощность потока. Максимальный поток Число 𝑓 𝑠, 𝑁 = 𝑓 𝑁, 𝑠 ′ > 0 называется мощностью потока. Поток максимальной мощности называется максимальным потоком в сети. 12 Сечение сети Пара множеств 𝑆, 𝑆 ′ , 𝑆 ⊂ 𝑁, 𝑆 ′ ⊂ 𝑁, называется сечением сети, если выполнено: 𝑆 ∪ 𝑆′ = 𝑁 𝑆 ∩ 𝑆′ = ∅ 𝑠 ∈ 𝑆, 𝑠 ′ ∈ 𝑆 ′ Пропускной способностью сечения 𝑆, 𝑆 ′ называется 𝑢 𝑆, 𝑆 ′ . 13 Сечение 𝑆, 𝑆 ′ , 𝑆 ⊂ 𝑁, 𝑆 ′ ⊂ 𝑁 с минимальной пропускной способностью называется минимальным сечением. Задачи Прямая задача (о максимальном потоке) В сети 𝑁, 𝑢 построить максимальный поток и найти мощность этого потока. Двойственная задача (о минимальном сечении) В сети 𝑁, 𝑢 найти минимальное сечение и вычислить его пропускную способность. 14 Лемма 1 (Свойство потока и сечения) Пусть 𝑓 – произвольный поток в 𝑁, 𝑢 , а 𝑆, 𝑆 ′ – произвольное сечение в 𝑁. Тогда мощность 𝑓 не превосходит 𝑢 𝑆, 𝑆 ′ : 𝑓 𝑠, 𝑁 ≤ 𝑢 𝑆, 𝑆 ′ 15 Лемма 2 (Достаточное условие оптимальности) Если мощность какого либо потока 𝑓 совпадает с пропускной способностью некоторого сечения 𝑆, 𝑆 ′ , 𝑆 ⊂ 𝑁, 𝑆 ′ ⊂ 𝑁, то этот поток является максимальным, а данное сечение – минимальным. 16 Теорема (о максимальном потоке и минимальном сечении) В произвольной сети 𝑁, 𝑢 существует максимальный поток 𝑓: 𝑁 × 𝑁 → 𝑍 и минимальное сечение 𝑆, 𝑆 ′ , 𝑆 ⊂ 𝑁, 𝑆 ′ ⊂ 𝑁, при этом мощность максимального потока совпадает с пропускной способностью минимального сечения, т.е. 𝑓 𝑠, 𝑁 = 𝑢 𝑆, 𝑆 ′ . 17 Понятие пути, ненасыщенного потоком  Пусть 𝑓: 𝑁 × 𝑁 → 𝑍, – поток в сети 𝑁, 𝑢 . Будем говорить, что ребро 𝒙, 𝒚 не насыщено потоком 𝒇, если 𝑓 𝑥, 𝑦 < 𝑢 𝑥, 𝑦 .  Путём 𝑷 𝒔, 𝒔′ из исток в сток будем называть последовательность рёбер вида: 𝑃 𝑠, 𝑠 ′ = 𝑠, 𝑥1 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 , 𝑠 ′ .  Будем говорить, что путь не насыщен 18 относительно потока, если каждое ребро не насыщено относительно этого потока. Доказательство теоремы о максимальном потоке Пусть 𝑓 – максимальный поток. Докажем, что существует минимальное сечение 𝑆, 𝑆′ , 𝑓 𝑠, 𝑁 = 𝑢 𝑆, 𝑆′ . 𝑆 – множество узлов в сети, которые можно достичь из 𝑠 по ненасыщенному относительно потока 𝑓 пути. Возможны два случая: 19 1. 𝑠′ ∉ 𝑆 2. 𝑠′ ∈ 𝑆 Случай 1: 𝑠′ ∉ 𝑆 ⟹ 𝑠 ′ ∈ 𝑁\𝑆 = 𝑆′ ⟹ 𝑆, 𝑆′ – сечение. Покажем, что это сечение – минимальное, т.е. 𝑓 𝑠, 𝑁 = 𝑢 𝑆, 𝑆′ . От противного: пусть 𝑓 𝑠, 𝑁 < 𝑢 𝑆, 𝑆′ . 20 Случай 2: 𝑠′ ∈ 𝑆 ⟹ существует ненасыщенный путь 𝑃 𝑠, 𝑠′ относительно потока 𝑓. Найдём 𝜹 = 𝒎𝒊𝒏 𝒖 𝒙, 𝒚 − 𝒇 (𝒙, 𝒚) > 𝟎. (𝒙,𝒚)∈𝑷 Строим новый поток по правилу:  f ( x, y )   , ( x, y )  P  f1   f ( x, y )   , ( y, x)  P  f ( x, y ), ( x, y )  P , ( y, x)  P  21 Алгоритм построения максимального потока и минимального сечения 22 1. Построить произвольный поток (можно нулевой): 𝑓0 в сети 𝑁, 𝑢 . 2. Построить множество достижимости 𝑆0 множество вершин, которые могут быть достигнуты из 𝑠 по пути, ненасыщенныму потоком 𝑓0 . Алгоритм построения максимального потока и минимального сечения 3. Если 𝑠 ′ ∉ 𝑆0 , то поток 𝑓0 – максимален, и сечение 𝑆0 , 𝑆0′ , 𝑆0′ = 𝑁\𝑆0 , – минимальное сечение в сети. 4. Если 𝑠 ′ ∈ 𝑆0 , то от 𝑠 к 𝑠 ′ имеется ненасыщенный путь, на который можно наложить дополнительный поток 𝛿0 , получив новый поток : 𝑓1 = 𝑓0 + 𝛿0 большей мощности, который строят по правилу: 23 Алгоритм построения максимального потока и минимального сечения a) Находим ненасыщенный путь 𝑃0 𝑠, 𝑠 ′ относительно потока 𝑓0 . b) Вычисляем величину 𝛿0 = min 𝑢 𝑥, 𝑦 − 𝑓0 (𝑥, 𝑦) > 0. (𝑥,𝑦)∈𝑃0 c) Вычисляем новый поток по правилу:  f 0 ( x, y )   0 , ( x, y )  P0  f1   f 0 ( x, y )   0 , ( y, x)  P0  f ( x, y ), ( x, y )  P , ( y, x)  P  0 24 5. Переходим к п. 1 алгоритма, но с потоком 𝑓1