Дуги являются трубами пропускной способностью равной их весу, Вершины узлами сопряжения труб. Графы такого типа обычно называются сетями.

Объекты, перемещаемые по дугам таких графов, называются единицами потока.

Количество единиц потока, перемещаемых по дуге, называется потоком в дуге.

Дуги являются ориентированными, т.е. единицы потока могут перемещаться только в одну сторону.

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

С помощью моделей данного типа (сетевых моделей) решаются задачи:

Расчет характеристик потоков в трубах.

Расчет характеристик транспортных систем города.

Расчет характеристик грузопотоков в производстве.

Характеристики сети

Cij - Пропускная способность дуги ij . Это количество единиц потока, которые может пропустить дуга. Больше этой величины поток в дуге не может принимать значения .

Fij - Величина потока по дуге. Это количество единиц потока, перемещаемых по дуге.

Div ( V ) . Количество потока вытекающего из вершины V.

. Вершины истоки - S. Это вершины, у которых. Div < 0. Если вершин истоков несколько, то их сводят в одну, соединяя с мнимым источником S₀ дугами бесконечной пропускной способности .

. Вершина называется стоком - T, если Div > 0.

. Вершины промежуточные Div=0

Количество потока , вытекающего из истока = втекающему в сток.

Стандартный сетевой граф должен иметь одну вершину сток и одну вершину исток. Если по условию задачи существует несколько вершин истоков или стоков, то делается следующее преобразование:

- вводится общий мнимый исток S0

- S0 соединяется дугами с частными вершинами истоками

- для частных вершин истоков устанавливается нулевой порождаемый поток

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

- порождаемый поток в общей вершине истоке устанавливается равным бесконечности

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

Пропускная способность сетевого графа определяется с одной стороны пропускной способностью составляющих дуг, с другой их последовательностью соединения.

Пропускная способность определяет величину установившегося потока в сети, т.е. когда единицы потока достигли стока и подача единиц из истока не ограничена.

Кроме установившегося, различают начальный поток сети - это поток, в котором не все единицы достигли стока, и конечный поток-это поток, когда подача единиц потока в истоке прекращена, однако в сети единицы потока еще присутствуют.

1. Графический

2. С помощью двух матриц смежности C и F

Исходные данные.

С(N,N) - матрица смежности, задающая пропускную способность дуг графа.

Алгоритм поиска максимального потока построен на поиске увеличивающих цепей для какого-либо начального потока.

Цепь является увеличивающей, если она состоит из дуг, позволяющих увеличить достигнутый в ней результирующий поток. Дуги, позволяющие увеличить результирующий поток в цепи, называются допустимыми. Дуга является допустимой, если поток в ней совпадает с направлением цепи и имеет значение меньшее, чем пропускная способность. Такие допустимые дуги называются согласованными. Величина, на которую согласованная дуга позволяет повысить поток по цепи рассчитывается как разность между ее пропускной способностью и достигнутой величиной потока.

Кроме того, допустимой является дуга, в которой поток совпадает с направлением цепи. Такие допустимые дуги называются несогласованными. Величиной, на которую позволяет увеличить поток в цепи несогласованная дуга является достигнутое в ней значение потока.

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

Задаться любым потоком, можно нулевым, т.е. потоком в котором во всех трубах поток нулевой f ij = 0.

По любому алгоритму поиска найти увеличивающую цепь, соединяющую источник и сток.

Если такая цепь есть то: пересчитать потоки, передаваемые по ее дугам, c учетом достигнутой величины увеличения . Переход к п.1, иначе: переход к п.2

Подсчитать W - величину потока, вытекающего из истока

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

Лучшие результаты обеспечивают алгоритмы, в которых для поиска увеличивающей цепи используется методы направленного поиска цепи с наименьшей длинной (алгоритм Дейкстры), где в качестве критерия оптимальности принимается величина наибольшего увеличения результирующего потока. Критерий "Макси-мина".

Это модели, которые представлены с помощью правил следующего вида: ЕСЛИ-ТО. Такая модель позволяет, во-первых, простой и точный механизм использования знаний, во-вторых, представить знания с высокой однородностью, которое описывается по единому синтаксису.

(t1,...,tn )/ t, где ti - посылки, t - заключение

Системы продукции состоят из трех элементов:

1) Набор правил, которые используются, как база знаний

2) Рабочая память, где хранятся посылки отдельных задач, а также результаты вывода

3) Механизм логического вывода (рис. 1)

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

2) Условная часть правила №1 считается ложной и механизм вывода переходит к правилу №2

3) Условная часть правила №2 истинна и механизм вывода переходит к заключительной части «дорога-ухабистая»

4) Заключительная часть правила №2 заносится в рабочую память

5) После просмотра всех правил производится их вторичное применение, начиная с первого за исключением тех, которые уже применялись.

6) При повторном сопоставлении правила №1 его условная часть становится истинной и механизм вывода выполняет его заключительную часть

7) Заключительная часть правила №1 заносится в рабочую область, и это правило исключается из дальнейшего согласования «использовать-джип»

8) Правил для сопоставления не остается и система останавливается.

Обратный вывод - способ, при котором на основании фактов исследуется возможность применения правил. Исходная ситуация - «использовать-джип»

1) Определяется правило, в котором в заключительной части содержится целевой факт.

2) Т.к. образец «намерение-отдых» условной части занесен в рабочую память, то для достижения цели необходимо подтвердить «дорога-ухабистая»

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

4) Применяется правило №2. Это правило истинно

5) Рабочая память пополняется образцом «дорога-ухабистая»

Вариант использования Use Case соответствует реализации одного из требований к системе. Отображается в среде Rational Rose в виде овала

Объекты, это программные сущности, включающие в себя некоторые данные и поведение, методы (сервисы, согласно методологии MSFW).

Объекты являются экземплярами, реализацией некоторых классов, описывающих объекты определенного типа.

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

Однако выявление объектов является и самостоятельной задачей определяющей особенности программной реализации классов.

При проектировании системы на этапе логического проектирования согласно методологии RUP и MSF определение объектов опережает определение классов, однако на некоторых этапах проектирования эти процессы могут идти параллельно.

Обычно при использовании среды Rationl Rose используется следующая последовательность шагов.

1. Выявляется объект. Объект включается в модель.

2. На основе выявленных объектов определяются классы в системе. Классы включаются в модель.

3. Существующие ранее определенные объекты системы связываются с определенными классами в системе. Корректируются атрибуты и операции объекта так чтобы они соответствовали атрибутам и операциям класса

4. Объекты и классы могут добавляются в модель ИС при ее дальнейшей доработки.

Как объекты, так и классы системы, в зависимости от типа выполняемых функций подразделяются на три группы.

1. Объекты, (классы) сущности

2. Объекты(классы) граничные

3. Объекты, классы управляющие.

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

Выявление объектов сущностей на основе анализа сценариев вариантов использования.

Для выявления объектов можно проанализировать сценарии описывающие потоки событий вариантов использования.

Каждое действие в сценарии описывается как тройка.

[<существительное1>] <глагол><существительное2>.

Где <глагол> определяет выполняемое действие,

<существительное2> - указывает на объект на которой это действие направлено или который является результатом этого действия,

<существительное1> - указывает на объект который выполняет данное действие.

<существительное2> и <существительное1> в описании действий в сценарии могут быть актерами, объектами или их атрибутами. Отделение объектов от их атрибутов можно произвести на основании наличия у них поведения. Объекты обычно обладают некоторым поведением, то есть составом операций.

Выявление объектов сущностей при построении диаграмм деятельности

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

Объекты на диаграмме деятельности отображаются в виде потоков объектов.

То есть объектов на который влияет деятельность. Или объектов, данные которого используются в деятельности. Аналогично можно отобразить связь деятельности с объектом в котором она реализована как операция.

Однако необходимо отметить, что не все объекты могут быть выявлены на основе сценариев или диаграмм деятельности.

Таким образом при построении диаграммы деятельности необходимо проследить

Граничные объекты и классы обеспечивают взаимодействие между внешней средой и внутренними элементами системы. Они соответствуют формам приложения, отчеты, средства доступа к одних объектов системы к другим.

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

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

На ранней стадии проработки управляющие объекты добавляются для каждой пары актер-вариант использования. ПРи дальнейшем анализе управляющие объекты(классы) могут исключаться, объединяться разделяться.