Консалтология Общая теория консалтинга (стр. 46 )

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

- корректировки полученной структуры сети путем введения допол­нительных связей между пунктами с целью получения живучей сети электросвязи;

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

Формально консультационную задачу по формированю рекомендаций синтеза структуры первичной сети связи можно представить в виде следующей задачи математического программирова­ния. Задана матрица расстояний D=|dij| размерности п×n между всеми п пунктами данного региона. Необходимо определить такую структуру сети, которая обеспечивала бы связь между всеми пунктами региона по критерию минимальной стоимости. При этом будем считать, что стоимость канала связи между пунктами i и j пропорциональна рас­стоянию dij между ними.

Введем псевдобулевы переменные:

Задача синтеза оптимальной структуры сети связей по критерию

минимальной стоимости заключается в определении таких переменных xij {0, 1}, которые обращали бы в минимум целевую функцию

при ограничениях

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

Пример 9.9. Консультационная задача формирования рекомендаций осуществления посинтеза структуры памяти специализированной ЭВМ. Требуется синтезировать структуру внутренней памяти (СОЗУ— ОЗУ—ПЗУ) специализированной ЭВМ, работающей в режиме реаль­ного времени, совместно с определением необходимого пакета объектных программ и их размещением в различных блоках системы памяти.

Пусть ЭВМ ориентирована на решение множества задач (заявок)

С={с1, ..., сп}, причем каждая задача ciC встречается с относительной частотой gi, и пусть на множестве С задано его разбиение на подмно­жества Cl, l=l, 2,…,u, (u≤n), тaк что в подмножество ClC входят только те задачи сCl, которые имеют l- й приоритет, причем чем меньше l, тем выше приоритет.

Дли решения поступающих в ЭВМ задач имеется множество алго­ритмов = {L1, ..., Lp), p≤п, no отношению к которым множество С разбито на подмножества C(Li) C таким образом, что если сC (Li).

то задача может быть решена с помощью алгоритма Li. Каждый

из алгоритмов Li может быть реализован тi методами, т. е. для каждой сl можно записать множество упорядоченных пар Ll = {(i, j)},

i=1, 2,…, p, j =1, , 2,…, ml, где любая пара (i, j) описывает метод решения зада­чи сl. Каждый из методов (i, j)Ll характеризуется: способом хране­ния программы (в ОЗУ или ПЗУ); числом требующихся ячеек аij ОЗУ или ПЗУ для записи программ; числом bij ячеек СОЗУ для хранения чaсто встречающихся данных и промежуточных результатов и числом hij ячеек ОЗУ для хранения исходных данных при обработке заявки сl в реальном времени; количеством ресурса k, где под ресурсами будем понимать габариты, массу, стоимость, число используемых яче­ек или панелей, потребляемую мощность и т. д. Поскольку программы могут храниться как в ПЗУ, так и в ОЗУ, это влияет на время реализа­ции программы, надежность и оперативность в смене программ. Часть параметров, например, время решения задачи, стоимость, габариты, по­требляемая мощность и др., подчиняется условиям аддитивности, в то время как такие параметры, как надежность, диагностическая воз­можность, ремонтопригодность и др., являются неаддитивными.

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

В частности, в качестве критерия оптимальности можно выбрать суммарный объем ОЗУ и ПЗУ, который требуется для хранения про­грамм и данных и который следует минимизировать.

Дадим математическое описание задачи. Введем псевдобулевы пе­ременные:

Для ЭВМ, работающих в реальном времени (время реализации ал­горитмов строго ограничено и задаче соответствует свой алгоритм ре­шения Li, (р=п), задачу выбора набора программ для реализации

множества алгоритмов можно сформулировать следующим образом (при этом заменим соответствующие обозначения Li на индекс i): ми­нимизировать целевую функцию

(9.128)

при временных ограничениях на реализацию алгоритмов

(9.129)

при ограничениях на аддитивные параметры

(9.130)

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

(9.131) Здесь — математическое ожидание времени реализации алгоритма Li j-м методом; gi — относительная частота появления алгоритма в об­щей программе работы ЭВМ; Rk, В, Н — ограничения на k-й ресурс, объем СОЗУ и ОЗУ соответственно; Tl— максимально допустимое вре­мя реализации задач, имеющих l-й приоритет.

Задача (9.128) — (9.131) также является задачей дискретного про­граммирования с псевдобулевыми переменными. Подставляя в целевую функцию задачи оптимизации другие параметры, в частности стоимость, время решения задач, энергетические и другие параметры системы па­мяти, можно оптимизировать структуру системы памяти ЭВМ по соот­ветствующим критериям.

Рассмотренная задача может быть использована для синтеза тех­нических и программных средств САК.

9.13. Последовательные методы в задачах консультирования сложных проблем

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

При консультировании сложных проблем довольно эффективными оказываются последовательные методы ана­лиза и синтеза.

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

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

Последовательные алгоритмы синтеза основаны на на­ращивании структуры путем добавления по определенным правилам элементов к некоторому начальному элементу.

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