Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2018-01-03 | 187 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!