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

В данной задаче т—п переменных могут быть выбраны произволь­но, в частности взяты равными нулю. Это дает возможность проиллю­стрировать задачу геометрически в т—п-мерном пространстве Ет-п. В этом пространстве каждой точке Х(r) соответствует совокупность чи­сел xr1,....., xrт—п равных проекции вектора, проведенного из начала

координат в точку Х(r), на координатные оси пространства Ет-п.

Функция F(x1, ..., хт) в каждой точке пространства имеет опреде­ленное значение, следовательно, пространство Ет-п является скаляр­ным полем критерия оптимальности F(Х) и функций ограничений θi(Х). Функциям ограничений (9.6) соответствуют граничные гиперповерхности (в частном случае — гиперплоскости). Ограничениям (9.7) соответст­вуют гиперплоскости, выделяющие в пространстве определенную про­странственную область. Если ограничения (9.6) и (9.7) представляют собой выпуклую область, то решения задачи оптимизации будут соответствовать такой точке этой области со скалярным полем критерия F(X), в которой критерий F(X) принимает минимальное значение. Поясним вышесказанное на примере.

Пример 9.1. Имеется следующая задача нелинейного программиро­вания: минимизировать целевую функцию

F(X) = х1-х2, (9.9)

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

(9.10)

Введя дополнительные переменные х3, х4 и х5, (9.10) превратим в систему уравнений, которую разрешим относительно этих введенных пе­ременных. При этом получим

(9.11)

В данной задаче число переменных т = 5, число уравнений п = 3, тогда т—п=2, что дает возможность дать геометрическую интерпре­тацию задачи в пространстве Е2, т. е. на плоскости.

Поскольку все переменные должны быть положительными:

хj≥0, j=1,2,3,4,5 (9.12)

каждое из неравенств (9.12) определяет некоторую допустимую область в пространстве Е2. Так, неравенство х1≥0 определяет верхнюю полу­плоскость, неравенство х4≥0— полуплоскость, лежащую по одну сто­рону от прямой 2х1—х2+1=0, а именно ту, которая содержит начало координат. Область, соответствующая x4<0, является запрещенной, и ее удобно отметить (на рис. 9.1, а она отмечена штриховкой).

Рис. 9.1. Допустимая и запрещенная полуплоскости (а) и область су­ществования задачи нелинейного программирования (б)

Подобные построения для всех xi приведены на рис. 9.1, б. Облас­тью существования задачи является область OABCD. В рассматривае­мом примере функция (9.9) принимает минимальное значение на гра­нице допустимой области в точке В.

Отметим ряд особенностей задачи нелинейного програм­мирования с нелинейной целевой функцией. В общем случае заранее нельзя сказать о расположении точки, в которой функция F(X) принимает максимальное или минимальное значение. Эта точка может находиться как на границе до­пустимой области, так и внутри нее. Функция F(X) может достигнуть экстремального значения как в одной точке, так и на некотором множестве (гиперлинии или гиперповерх­ности).

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

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

9.2. Структурный синтез и параметрическая оптимизация формируемых рекомендаций

Задача синтеза формируемых рекомендаций включает в себя создание структуры КП и расчет ее параметров. Эти две части синтеза будем называть структурным и параметрическим синтезом формируемых рекомендаций.

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

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

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

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

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

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

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

Пример 9.2. Задача компоновки. Под задачами компоновки пони­мают задачи разбиения множества D = {d1, ..., dn} из п элементов на ряд непересекающихся подмножеств Dk, k=1,2,…,N, чтобы при этом вы­полнялись заданные ограничения и достигался экстремум некоторой функции качества F(X).

При заданном числе N подмножеств разбиения задача компоновки формулируется следующим образом:

F(X)→min;

(9.13)

где Dk D — множество элементов, принадлежащих k-му подмножест­ву разбиения.

Общее число разбиений

при условии, что мощность каждого подмножества Dk является заданной, т. е.