Смекни!
smekni.com
Экономико-математическое моделирование

Автоматизированная система управления санаторным комплексом. Подсистема Диетпитание (стр. 12 из 28)

Каждый элемент

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

Возможные структуры БАС определяются иерархией отношений между классамиобъектов-альтернатив.

Последовательная БАС

Дляпоследовательной сети последовательный алгоритм навигации может быть реализовандвумя базовыми способами.

1. Прохождениесети реализуется  последовательно,  начиная  с первого  a1 и заканчивая последним аN блоками. Алгоритм обращается к блоку a1,просматривает его содержимое и через транзитные вершины передаетрезультат.  Далее переходит к следующему блоку.  В итоге образуется некоторыйвершинный маршрут  Мj =(a1j, ..., anj,..., aNj),который и представляет данные о результате решения.  Если какое-то решениенесовместно, то выявляется причина не­совместимости и ищется новое решение.

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

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

Пусть задан кортеж атрибутов (множествоальтернатив):

А= {an: (n= 1, 2, …, n)}. Осуществим последова­тельную генерацию исходов А* = {an*:(n = 1, 2, …, n)} для каждой из альтернатив с помощью последовательной БАС.

БАС с последовательной стратегией предс­тавлена на рис. 3.7.

 
 
 

Рис. 3.7.Пример последовательной разомкнутой трехблочной БАС

 
 
 

Рис.3.8.Пример последовательной замкнутой трехблочной БАС

В последовательных БАС генерируемые альтернативные решения соединяются в одну связку с генерирующими следующего ЭБА попарно. В результате вершины А*n и Аn+1 сливаются в одну Аn+1.

 

ПараллельнаяБАС

При алгоритмес параллельной организацией навигации воз­можныкак минимум две схемы:

•     одноуровневый алгоритм;

•     двухуровневый алгоритм.

Одноуровневый алгоритм

По схеме одноуровневого алгоритма все элементы сети связаны друг с другом и включают координирующую и исполнительную функции. Одноуровневый алгоритм являетсядецентрализованной схемой навигации.

Рис. 3.9. Параллельнаяодноуровневая структура БАС

На рисунке 3.9 связь реализуется через общую транзитивную вершину (раздельный вход и выход).

Можно замкнуть параллельную БАС через:

-  вершины транзита и рекурсии;

-  включить вкачестве дополнительной некоторую вер­шину                     агрегирования.

При параллельной генерации решений в каждом блоке БАi работает свой  алгоритм формирования исходов. Алгоритмы работают одновременно,  и матрица альтернативных решений заполняет­ся построчно.

Двухуровневый алгоритм

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

Подпись: Выход

Рис. 3.10. Параллельная двухуровневая структура БАС

3.1.3. Маршруты наБАС

Применение блочно-альтернативныхсетей

 длярешения различного рода задач (анализ, синтез, классификация и т.д.) основанона использовании их свойства порождать множество альтернативных маршрутов МN. При описании допустимых множеств маршрутов  МN на сетях
,целесообразно исходить из блочной структуры альтернативной сети.

В БАСиспользуется вершинный тип маршрутов. С точки зрения сети маршрутыподразделяются на внутриблоковые и сетевые. Послед­ние, в свою очередь,формируются из внутриблоковых и межблоковых.

Внутриблоковый –это такой маршрут МiN 

  МN  (i = 1, …, n), который тем или иным образом связывает две соседниевершины (
) первого ранга, принадлежащие i-му блоку. Другими словами, внутриблоковый маршрутформируется как   последовательность вершин, связанных определенным отношением.

Межблоковые –маршруты МilN , которые связывают некоторые пары вершин первогоранга {(

), i = 1, …, n;  k = 1, 2, …, n;
 }. Межблоковые  маршруты используются приформировании циклов, и, следовательно, связываемые вершины (
) для таких маршрутов отождествляются.                            

Прииспользовании БАС для решения конкретных задач могут возникать ситуации, когдатот или иной внутриблоковый маршрут МiN   формируется неоднозначным образом. При этомвозможны три случая:

1) внутриблоковый маршрут МiN   проходится один раз слева направо;

2) внутриблоковый маршрут МiN для маршрута  МN  является запрещенным;

3) внутриблоковый маршрут МiN должен быть пройден неоднократно.

Всоответствии с названными случаями, определим три типа маршрутов: ациклические AMiN, транзитные ТMiN и циклические СMiN.

Ациклические маршруты

Наиболеепростыми маршрутами МN  

 
 являютсяациклические  (или незамкнутые) AMiN.

Ациклическиймаршрут (АМi) формируется какпоследовательность

вершинсовместно с отношением между вершинами:

AMi : (Ai, rij , aij),                                         

где  Аi - атрибут;

rij - определяет отношение между атрибутом ивершиной-значе­нием aij;

aij- значение атрибута Аi.

Полноепредставление внутриблокового маршрута по схеме ис­ток-сток будет представлятьсобой объединение:

AMi : (Аi , rij ,aij) U(aij ,rji ,A*i),                          

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

AMi: (Аi, aij, A*i).       

Аналогичнодля маршрута, проходящего через транзитивную верши­ну:

АMiT: (Ai, rT, A*i),                                        

чтоэквивалентно записи

AMiT:(Ai, T,A*i).                                                 

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

,между блоками (
,
) или по сети
 в целом.
 
назад
читать дальше
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
НАПИШИТЕ НАМ
Copyright © Smekni.com. All rigths reserved.