Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2018-01-03 | 186 |
5.00
из
|
Заказать работу |
|
|
Система обозначений в потоковых задачах.
Ориентированный граф определяется множеством узлов и множеством дуг, которые связывают эти узлы. Узел i является элементом множества узлов N = [1, 2, 3,..., i,..., n]. Дугу можно определить как упорядоченную пару узлов (i,j) или как, скажем, элемент К, списка дуг M = [1, 2, 3,..., k,..., m].
Moi = [k|ok=i] - список дуг, которые выходят из узла i;
MTi = [k|tk=i] - список дуг, которые входят в узел i.
Поток.
Потоками по дугам сети называют множество чисел fk, определенных на дугах k.
При описании потоков в сетях основным является условие сохранения потока в узлах, т.е. равенства потока, входящего в данный узел, потоку, выходящему из данного узла. Для стандартных задач о потоках в сети поток сохраняет свою величину при прохождении по дугам сети.
Вектор потока.
Вектор потока определяется как
'
где верхний индекс "штрих" означает операцию транспонирования данной вектор-строки, т.е. является вектор столбцом.
Стоимость.
Стоимость hk(fk) является функцией только потока по дуге k и не зависит от потоков по другим дугам сети. Во многих потоковых задачах требуется найти поток минимальной стоимости. При этом цель состоит в минимизации суммы дуговых стоимостей (целевой функции);
В дальнейшем будут рассматриваться линейные функции стоимости.
Линейная функция стоимости
hk(tk)=hkfk
а тогда
Пропускная способность.
Величина Ск, определяющая верхнюю границу потока по дуге k, называется пропускной способностью дуги k:
fk£Ck
Вектор пропускной способности
С = [C1, C2,..., Cm]'
можно использовать для записи набора ограничений по пропускной способности;
f<C.
Ограничение на поток снизу.
При моделировании многих ситуаций, встречающихся на практике, обычно требуется, чтобы поток по дуге был не меньше некоторой заданной величины. В этом случае для каждой дуги определяется параметр ck, называемый нижней границей потока по дуге, и вводится ограничение fk³ck или в векторном виде
|
f³ c.
Внешние потоки.
Внешние потоки входят в сеть или покидают ее в узлах. В большинстве сетевых моделей внешние потоки отражают связь изучаемой системы с внешним миром, и поэтому очень важно адекватно описывать эти потоки.
В моделях используются внешние потоки в узле двух типов: фиксированный и свободный потоки.
Пусть bi - фиксированный внешний поток в узле i. Будем говорить, что поток bi входит в узел i, если bi>0, и выходит из сети, если bi<0. Все фиксированные внешние потоки заданы и полностью учитываются в любом допустимом решении задачи о потоке в сети.
Свободный внешний поток в узле i, fsi пересчитывается в процессе выполнения соответствующих алгоритмов. Направление этого потока и границы изменения его значений определяются параметром узла i, bsi - пропускной способностью узла для свободного потока. Если величина bsi положительна (отрицательна), то поток fsi входит в сеть (покидает сеть) и должно выполняться ограничение 0£fsi£|bsi|
Иногда в узлах вводится параметр hsi - стоимость единицы внешнего свободного потока. В этом случае стоимость внешнего свободного потока для всех узлов добавляется к целевой функции
Свободные потоки можно представить иначе, используя параметры дуг, а не узлов. При этом в сеть вводится свободный узел n, в котором не требуется выполнения условия сохранения потока. Для положительного свободного потока fsi вводится дуга из свободного узла n в узел i. Для отрицательного свободного потока строится дуга в свободный узел n из узла i. Пропускная способность этой дуги полагается равной |bsi|, а стоимость - hsi.
Условие сохранения потока.
Для допустимого вектора потока выполняется условие сохранения потока во всех узлах сети, за исключением свободного узла. Если пока не рассматривать фиксированные внешние потоки, а свободный узел и свободные дуги определить как в предыдущим пункте, то окажется, что все потоки являются потоками по дугам (дуговыми потоками). В этом случае условие сохранения потока в каждом узле гласит: полный поток, выходящий из узла, минус полный поток, входящий в узел, равен фиксированному внешнему потоку в данном узле.
|
Для стандартной задачи условие сохранения потока в произвольном узле i можно записать в алгебраическом виде:
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!