3. Порядок выполнения работы

   1. Изучить теоретические положения;

   2. Составить алгоритм и фрагмент программы решения задачи на языке Паскаль

   3. Ответить на контрольные вопросы;

   4. Оформить отчет.

4. Содержание отчета

   1. Номер и название работы;

   2. Цели и задачи работы;

   3. Конспект теоретических сведений;

   4. Ответы на контрольные вопросы;

   5. Результаты и выводы.

5. Контрольные вопросы:

   1. Какие системы выделяют для систем управления (СУ) неинтегрированными сетями?

   2. Что является компонентом системы управления ЦСИО?

   3. На какие две группы разделяются внутренние переменные применительно к задаче оптимизации?

   4. Под технической эффективностью ЦСИО принято понимать?

   5. К техническим показателям ЦСИО, объединяемым в триаду «скорость, точность, надежность», относятся?

   6. Какие показатели являются трудноформализуемыми в практике структурно-сетевого проектирования?

Лабораторная работа №2 графовая трактовка задачи оптимизации

1. Цели и задачи самостоятельной работы:

Ознакомление с областями применения пакетов прикладных программ; с понятием структурно-сетевых задач. Приобретение навыков построения графовой трактовки задачи оптимизации.

2. Теоретические сведения.

При построении средств проектирования ЦСИО первосте­пенное значение приобретает показатель функциональной пол­ноты ППП и простоты перехода от одной постановочной аль­тернативы к другой, т. с. перенастройки ППП.

Различают две области применения ППП, предназначенные для структурно-сетевой оптимизации ЦСИО: задачи подготов­ки и последующего принятия решений, выполняемые в режи­ме «вопрос - ответ» и оперирующие укрупненной сетевой ин­формацией; задачи типового структурно-сетевого проектирова­ния, нацеленные на детальную проработку проекта ЦСИО.

Остановимся на задачах принятия структурно-сетевых ре­шений.

Лицо, принимающее решение (ЛПР) в части структурной и архитектурной организации перспективных ЦСИО, на пер­воначальных этапах проектирования интересует не единичное точное решение, заключающееся в поиске графа сети, а целый комплекс вопросов, из которых основными являются:

про­верка технического задания (ТЗ) на непротиворечивость;

оцен­ка степени выполнимости ТЗ;

обоснование выбора критериев оптимальности, системы ограничений и отдельных условий; оценка предельно достижимых значений надежностных, веро­ятностно-временных и стоимостных характеристик проектируемой ЦСИО;

определение степени иерархичности, характера разветвленности, связности и других интегральных топологи­ческих характеристик; выбор наиболее предпочтительной кон­цепции построения ЦСИО;

расчет оптимального типажа ТСС, в том числе средств ТО и управления потоками, или определе­ние требований к ним по надежности, быстродействию и т. п.;

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

определение оптимальной этапности внедрения сети;

выявление «узких» по тому или иному показателю звеньев сети и выработка предложений по их расширению.

Традиционный подход к разработке средств автоматизации проектирования, базирующийся на схеме «задача—модель— алгоритм», в данном случае представляется малопривлека­тельным. Необозримое количество задач и их модификаций, определенная трудоемкость воплощения их в вычислительные программы, не меньший объем затрат по сопровождению ППП приводят к созданию громоздкой информационно-математиче­ской базы САПР сетей связи.

На самом же деле ЛПР нужна компактная вопросно-ответ­ная система, пригодная для эксплуатации на ограниченных машинных ресурсах ПЭВМ.

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

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

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

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

Подобные логические методы полезно применять и при раз­работке методического обеспечения ППП. В методе ПАВЛА все проблемы на любой стадии принятия решений рассматри­ваются в шести аспектах, каждый из которых составляет часть целого. Применительно к задачам принятия структурно-сете­вых решений они включают: результат, время, ресурсы, метод, место, обоснование, которые дополняются вопросами что?, по­чему?, где?, когда?, какой(ие)?, как?, сколько? и т. п. На базе их комбинаций в сочетании с другими элементами предметной области формируются вопросы: какой метод решения следует избрать?, почему выбран именно этот метод?, как можно отыскать решение иначе? и т. п. Удовлетворительные ответы на вопросы должны быть получены только проверкой альтер­нативных вопросов. Процедуру обоснования выбора решения постоянно сопровождается постановкой дополнительных во­просов: как можно устранить, скомбинировать, стандартизиро­вать, модифицировать, упростить?

Главным в этом методе становится дисциплина мышления, которая пополняет индивидуальный фонд эвристических прие­мов, интуицию и опыт ЛПР, открывает видение многовариант­ности проблемной ситуации, даст набросок титульного списка задач для разработчика ППП. Если в ЭС новые знания выво­дятся из имеющихся с помощью непроцедурных методов, то применительно к САПР аналогичную задачу можно свести к решению последовательности задач оптимизации и анализа, логическая последовательность выполнения которых выбирает­ся либо по усмотрению ЛПР, либо с помощью таблицы реше­ний (ТР). ТР взаимоувязывают условия, правила, дей­ствия и позволяют определить логику выбора решений. Другие достоинства ТР состоят в простоте выявления ошибок в логи­ке выбора решений; пропущенных вариантов; повторяющихся правил; возможности декомпозиции сложной проблемы на подпроблемы; модифицируемости и наглядности представле­ния информации.

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

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

По аналогии с неинтегрированными сетями связи задачу оптимизации структуры (ЗОС) ЦСИО представим совокупно­стью следующих частных задач.

1. Выбор топологии графа (ВТГ), интерпретирующего структуру сети. Решение сводится к определению оптималь­ного числа вершин абстрактного (без привязки к местности) графа и сетки линий (ребер), соединяющих вершины.

2. Выбор пропускных способностей (ВПС). Решение со­стоит в выборе из заданного дискретного ряда пропускных способностей КС и производительностей УК по определенно­му правилу,

3. Расчет подсистемы ТО. Позволяет получить оптималь­ное число ЦТО, оценить дополнительные эффекты и задержки, вносимые подсистемой ТО.

4. Оценка стоимостных и вероятностно-временных характе­ристик отдельных УК, КС, подсетей и ЦСИО в целом. Эта задача нацелена на расчет интегральных и дифференциальных показателен проекта.

5. Поиск оптимального местоположения (ПОМ) УК- Реше­ние задачи позволяет определить реальную пространственную топологию сети, т. е. привязать вершины графа, найденного по результатам ВТГ, к конкретным географическим пунктам.

6. Расчет показателей подсистемы управления потоками. Включает распределение потоков (РП) и ограничение нагруз­ки (ОН). Распределение потоков. Решение сводится к поиску оптимальных маршрутов передачи потоков информации и рас­чету интенсивностей потоков в отдельных КС, УК И на марш­рутах. Ограничение нагрузки. Позволяет рассчитать допусти­мые пороги по внешнему трафику, количество блокируемых абонентов и т. д. для проектов с невыполненными требова­ниями по качеству обслуживания пользователей ЦСИО.

Формирование множества структурно-сетевых задач (ССЗ) основывается на принципе модифицируемости базовой ССЗ, в качестве которой выбирается задача оптимизации структуры ЦСИО с заданной алгоритмикой функционирования по стои­мостному критерию при ограничении на ВВХ. Каждой частной задаче ставится в соответствие проектный оператор. Под про­извольной ССЗ донимается некоторая задача оптимизации или анализа ЦСИО, опирающаяся на тот же набор проектных операторов, что и базовая ССЗ, и отличающаяся от нее хотя бы по одному из приведенных ниже факторов: набору входных данных, составу вектора управляемых переменных, избранным критериям оптимальности и функциям-ограничениям.

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

Произвольную ССЗ в каноническом виде представим фор­мализмом

(2.1)

где —множество данных; —множество управляемых пе­ременных; — множество неуправляемых переменных; — множество выходных переменных; — множество частных задач (проектных операторов), составляющих ССЗ; — граф, определяющий отношения между элементами вышеперечис­ленных множеств.

Предполагается, что область допустимых значений задает­ся системой ограничений

(2.2)

где — число функций-ограничений.

Система включает следующие ограничения:

• структурно-топологические, обусловливаемые необходи­мостью учета структуры и пропускной способности первичной сети;

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

• экономические (на капитальные затраты, эксплуатацион­ные расходы);

• эксплуатационные (нормы по качеству обслуживания поль­зователей);

• по топологической и физической реализуемости проекта.

Применительно к базовой ССЗ иерархических сетей связи компоненты (2.1) раскрываются через следующие параметры

— вектор, включающий в свой состав чис­ло классов входящего потока, число оконечных пунктов (ОП) , , с разбивкой по типам, объемно-временные характеристики потоков передаваемой информации;

— функцию, описывающую характер информационно­го тяготения ОП;

• — данные о размерах территории и характере распре­деления ОП;

методы коммутации, маршрутизации, ограничений нагрузки и другие протокольные механизмы;

типов центров коммутации пакетов (сообщений, каналов), различающихся стоимостью , производительностью (канальной емкостью для КК), коэффициентом готовности , интенсивностью восстановления

типов каналов связи, различающихся функцией стоимо­сти , коэффициентом готовности , интенсивностью восстановления

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

, вектор, включающий число ступеней иерархии , топологию , подсетей -и ступени иерархии, топологию межуровневых подсетей, — число УК (Кд) -го типа на -й ступени иерархии,

— число КС -го типа на -й ступени иерархии, число КС -го типа в межуровневой подсети с индексом

_t —число ЦТО -го типа на -и ступени иерархии, а так­же элементы маршрутных таблиц и таблиц ограничения на­грузки, координаты К.ц и УК;

вектор —для однокритериальной задачи фактические го­довые приведенные затраты П{ ) на сеть в целом;

вектор . представляющий собой систему ограничений на среднесетевую задержку сообщения (па­кета) -го приоритета;

вероятность своевременной доставки сообщения (паке­та) -го приоритета;

связность , в числе непересекающихся по вершинам пу­тей;

диаметр графа , интерпретирующего структуру.

Удобным аппаратом записи ССЗ являются граф-схемы (ГС), вершины которых соответствуют проектным операторам, а ребра — операндам, т. е. переменным, над которыми выпол­няются операции. В соответствии с принятой классифи­кацией переменных введен базовый набор операндов: входная величина, управляемая переменная, неуправляемая перемен­ная, выходная переменная — критерий, выходная перемен­ная— лимиттер, выходная переменная — неуправляемая.

Введем пять типов операторов:

— начальный оператор, соответствующий подготови­тельным операциям, например вводу исходных данных;

— нециклический оператор-преобразователь, заключаю­щийся в расчете показателен с помощью однократного обра­щения к одной или нескольким формулам (алгоритму);

— циклический оператор-преобразователь, основанный на многократном выполнении оператора или его компонен­тов;

— оператор-распознаватель, выполняющий операцию перехода по условию;

— конечный оператор, соответствующий выводу резуль­татов расчета.

Предполагается, что в ГС нет дуг, заходящих в начальный оператор, и нет дуг, исходящих из оператора останова.

Рис.2.1 Графовая трактовка задачи оптимизации структуры

На рис.2.1 представлена упрощенная ГС базовой ССЗ. Оператор имеет информационные связи со всеми операто­рами, кроме конечного. Последовательность выполнения про­цедур может быть различной, например ВТГ—РП--ВПС— ПОМ. Далее рассчитываются показатели ТО и интегральные характеристики, проверяется условие останова. В зависимости от «логического наполнения» оператора возможны: возврат к задаче перераспределения пропускных способностей ТСС; внесение изменений в топологию сети; обращение к подалгоритму расчета плана ограничения нагрузки. После этого осу­ществляется еще один цикл вышеупомянутых процедур. При более детальном изображении ГС соединения между операторами представляются мультиребрами, каждое из ко­торых соответствует тому или иному операнду. Конкретизация операндов достигается выбором тех или иных проектных опе­раторов и математических моделей. Любая иная ССЗ может быть получена из базовой путем проведения преобразований над ГС.

К классу допустимых преобразований относятся следую­щие.

1. Исключение циклов из операторов класса , что соот­ветствует преобразованию оптимизационной задачи в задачу анализа. Например, если —это РП, то его аналог — это расчет ВВХ на сети с фиксированными, заранее заданными маршрутами.

2. Перемещение элементов множеств из одно­го в другое. Приведем ряд примеров. Перевод входной вели­чины (удельной абонентской нагрузки) в разряд неизвестных приводит ЗОС к двухкритериальной задаче «стоимость — пропускная способность». Фиксацией управляемой перемен­ной числа УК получается ЗОС для заданного числа стан­ционных средств. В частных случаях могут быть получены:

некритериальная ССЗ, для которой множество пусто, а сформулированы лишь целевые требования либо ( —номер ограничения);

неоптимизационная (расчетная) ССЗ, для которой множе­ство пусто, а решение сводится к однократному расчету по формулам (алгоритмам);

ССЗ безусловной минимизации (без ограничений);

многокритериальная ССЗ, имеющая мощность множества больше 1;

ССЗ раздельной оптимизации, если ее ГС не связана;

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

3. Добавление новых операторов и опера плов.

Предполагается, что порождаемые таким способом ССЗ корректны в семантическом и морфологическом отношении, а вопросы существования, единственности, устойчивости и схо­димости решения доказаны.

Поскольку на этапе формулировки вопроса (постановки ССЗ) участвует ЛПР, вероятно, следует исключить появление ССЗ, для которых множество пусто, а в качестве критерия оптимальности задается какой-нибудь нереальный показа­тель, например площадь территории сети.

ССЗ, порождаемые на данной перестановочной модели, группируются в три класса:

Таблица 2.1

Тип ССЗ	Наименование ССЗ	Тип ССЗ	Наименование ССЗ
ЗОС и смежные задачи	Семейство однокритериальных ЗОС по стоимостному критерию Семейство однокритериальных ЗОС по критерию, отличному от стоимости (производительности, пропускной способности, средней задержке и т.п.) Семейство многокритериальных ЗОС Оптимизация структуры сети связи в развитии Декомпозиция сетевых требований Минимизация численности обслуживающего персонала	Субзадачи Метазадачи	Расчет плана РП для фиксированной структуры Синтез топологии графа Выбор оптимального типажа оборудования Расчет допустимых порогов по внешнему трафику Анализ чувствительности Выбор или выделение эффективных областей использования методов коммутации (алгоритмов повышения достоверности маршрутизации и ограни- чения нагрузки) Оптимизация структуры сети связи в развитии

1. задачи, смежные с базовой ССЗ;

2. субзадачи, решаемые при некоторых фиксированных компонентах вектора X базовой ССЗ;

3. метазадачи, являющиеся многоэтапными ССЗ, для ко­торых ЗОС является всего лишь компонентом.

В табл.2.1 приводятся наиболее распространенные в практи­ке структурно-сетевого проектирования ССЗ.