ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Задача определения максимального потока.Рассматривается сеть с одним узлом входа (источник) и одним узлом выхода (сток). Какова максимальная величина потока (количество машин, сообщений, жидкости и т.д.), который может войти в сетевую систему и выйти из нее в заданный период времени? При этом предполагаем, что поток, вытекающий из узла, равен потоку, втекающему в узел. Под пропускной способностью (мощностью) дуги будем понимать верхнее ограничение на поток в этой дуге. Мощность потока может зависеть от его направления. Условное изображение в сети Означает, что мощность потока от узла 1 к узлу 2 равна 6, а мощность от 2 к 1 равна 0. Алгоритм определения максимального потока:
Пример. Система автодорог «Север-Юг», проходящих через Псковскую область, может обеспечить пропускные способности, показанные на приводимой ниже схеме (тыс. автомашин в час).
Каков максимальный поток через эту систему (тыс. автомашин в час)? Сколько автомашин должно проехать по дороге 5-6, чтобы обеспечить максимальный поток? Искомую величину максимального потока положим равной нулю. Выбираем путь 1-3-6. Р=min(6,2)=2. Поэтому мощности потоков на пути 1-3-6 в направлении потока уменьшаем на величину Р=2, а мощности потоков в обратном направлении на пути 1-3-6 увеличим на Р=2. Общий поток станет 0+2=2. Получим: Выбираем путь 1-4-6. Р=min(3,3)=3. Все потоки на пути 1-4-6 в направлении общего потока уменьшаем на 3, а в обратном направлении увеличиваем на 3. Общий поток увеличиваем на 3. Итого, 2+3=5. Получим: Выбираем путь 1-2-5-6. Р=min(2,4,6)=2. Все потоки на пути 1-2-5-6 в направлении общего потока уменьшаем на 2, в обратном увеличиваем на 2. Общий поток увеличиваем тоже на 2. Итого 5+2=7. Получим: Выбираем путь 1-3-4-5-6. Р=min(4,3,1,4)=1. Все потоки на пути 1-3-4-5-6 в направлении общего потока (4,3,1,4) уменьшаем на величину Р=1, а все потоки на этом пути в обратном направлении увеличиваем на Р=1. Итого, общий поток 7+1=8. Получим: Выбираем путь 1-3-4-2-5-6. Р=min(3,2,1,2,3)=1. В прямом направлении уменьшаем на 1, в обратном увеличиваем на 1. Общий поток равен 8+1=9. Получим: Больше не существует путей из узла 1 в узел 6 с мощностью, превышающей 0 на всем пути (Р=0). Следовательно, 9 тыс. – это максимальный поток через сеть. Определим теперь величину и направление потока на каждой дуге, чтобы достичь максимального потока в 9 тыс. автомобилей. Поток проходит по дуге с величиной, равной разнице между первоначальной и конечной мощностями потока. Так, первоначальная мощность дуги 1-2 равна 2, а конечная – 0. Тогда в направлении от узла 1 к узлу 2 поток имеет мощность 2-0=2. Сравнивая конечные и начальные мощности потока для всех дуг сети, мы получаем конечную модель потоков. Задача. Чему равен максимальный поток автомашин для системы автодорог? Рассматривается возможность введения секции 3-4 с пропускной способностью 3 тыс. автомашин в час. На сколько увеличится величина максимального потока автомашин?
Литература Просветов Г.И. Дискретная математика: задачи и решения. – М.: БИНОМ. Лаборатория знаний, 2011. Канцедал С.А. Дискретная математика: учеб. Пособие. – М.:ИД «ФОРУМ»: ИНФРА-М, 2011. Стол Р.Р. Множества. Логика. Аксиоматические теории. – М.: Просвещение, 1968. Андерсон Дж. А. Дискретная математика и комбинаторика. – М.: Вильямс, 2003. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика. – Ростов н/Д: Феникс, Харьков: Торсинг, 2003.
Не нашли, что искали? Воспользуйтесь поиском:
|