6.1. Постановка оптимизационных задач

Отметим, что оптимальность — это лишь попытка отразить оценочное, субъективное, свойство через некоторое количественное соотношение, т. е. выразить количественно то качество, которое желательно придать моделируемой задаче. Количественная оценка существенных свойств модели, режимов ее работы или внешней среды, в которой она функционирует, определяется значениями множества переменных. Входные переменные представляются вектором. X — (жі, Ж2,..., хп). Они характеризуют свойства внешней по отношению к модели среды, оказывающей влияние на ее функционирование. Внутренние переменные (переменные состояния) — величины, которые характеризуют состояние отдельных элементов модели; обозначим, их вектором. Z = (zi, Z2,..., zr). Величины, характеризующие свойства модели в целом и определяющие степень выполнения ею своего назначения, называют выходными переменными. Их обозначают вектором.

У = (Уі,У2, - ■ ■ ,Ут)-

Выражения, отображающие зависимость между входными и выходными переменными, а. также переменными состояния, называют математическим описанием модели решаемой задачи [113, 159]:

Их можно представить в форме:

Выражение (6.1) представляет собой отображение (или соответствие) между множествами переменных X, Y, Z, которое можно получить на основе одной из моделей. Таким образом, под моделью будем понимать зависимость F, которая в общем случае может быть некоторым алгоритмом, оператором, функцией, правилом, инструкцией и т. п., которые позволяют определить значения выходных переменных, не обращаясь к реальному объекту (системе), для которого решается задача.

Условно модель F можно представить как ее структуру St и вектор параметров С = (сі, С2,..., с&):

Создание модели осуществляется в два этапа:

•    структурного синтеза, когда определяется структура St, т. е. вид элементов, из которых состоит модель и отношения между ними;

•    параметрического, связанного с определением численных значений параметров модели С = (с\, с2,..., с&).

По известной структуре описания задачи и значениям векторов X и Z создают физические или математические модели F и на их основе определяют оценки значений вектора Y. Процедуры анализа систем обычно выполняют методом моделирования. Одновариантный анализ включает задачи статики и динамики в частотной области. Многовариантный анализ заключается в определении изменений вектора Y при заданных изменениях векторов X и Z. Многовариантный анализ включает анализ чувствительности и статистический анализ. При анализе чувствительности оценивают влияние внутренних и внешних переменных на выходные переменные путем расчета коэффициентов чувствительности. Статистический анализ заключается в определении вида закона распределения и расчете параметров распределения вектора Y при заданных статистических значениях о распределении случайных векторов X и Z.

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

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

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

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

Эмпирические математические модели строят на основе опыта ЛПР

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

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

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

Полной математической моделью называют модель, которая получается непосредственным объединением моделей в общую укрупненную систему. Тогда аппроксимацию полной математиче ской модели называют макромоделью [159]. Она описывает объекты при укрупненном рассмотрении элементов.

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

Алгоритмическая математическая модель задает отношение или соответствие между выходными внутренними и внешними переменными, записанными в форме алгоритмов.

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

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

Дискретные математиче ские модели — это модели, в которых все переменные и параметры — дискретные величины.

Опишем теперь требования, предъявляемые к математическим моделям. Основными являются адекватность, точность, степень универсальности и экономично сть.

Адекватность математиче ской модели — это соответствие модели моделируемой задаче или процессу принятия решений, причем адекватность рассматривают по тем свойствам модели, которые для ЛПР являются наиболее важными в данный момент времени. Под адекватностью математической модели также понимают способность отображать ее заданные свойства с текущей погрешностью £т, не выше заданной погрешности £3. Математическая модель называется адекватной по вектору У, если погрешность расчета на ее основе значений выходных параметров уі е Y не превышает заданных. Как известно, адекватность математиче ской модели обычно рассматривают в ограниченной области изменения входных переменных. Эту область называют областью адекватности математиче ской модели. В ней выполняется неравенство \еі\ ^ Еіу9, где Еі — относительная погрешность определения переменной уі, возникающая из-за приближенного характера математиче ской модели; Еі 9 — допустимая погрешность (еі 9 ^ 0) [159].

Отметим, что любая математиче ская модель описывает лишь некоторое подмножество свойств задачи, поэтому ее точность определяется как степень совпадения значений переменных реального объекта и значений тех же переменных, полученных на основе исследуемой математиче ской модели. При определении точности математиче ских моделей важно определять их погрешности. Пусть, как и выше, Y = (уі, у2,..., уп) — вектор выходных переменных; уі^ — эталонное значение выходной переменной, определенное на основе экспертных оценок; Уіумм — значение і-й выходной переменной, рассчитанное на модели. Тогда относительную погрешность Еі при

расчете выходной переменной определяют следующим образом:

Погрешность модели для всех значений переменных будет представлять вектор е = (£і, £2, • • •, £п), где п — число выходных переменных. Отметим, что значения погрешности, полученные таким образом, зависят от свойств математической модели, особенностей решаемых задач и достоверности экспертных оценок. В этой связи при решении новых практических задач необходимо пересматривать оценки точности математической модели.

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

Экономичность математиче ской модели обычно характеризуют затратами вычислительных ресурсов ЭВМ при их реализации. Основными из таких ресурсов являются машинное время Тм и объем используемой памяти Ѵм = Ѵоп + Ѵвн, где Von — объем оперативной памяти; Ѵвн — объем внешней памяти. Отметим, что так как Ѵвн ѴЬп, то при анализе затрат памяти в большинстве случаев оценку можно вести по Ѵвн- Очевидно, что чем меньше Тм и Ѵм, тем математическая модель считается экономичнее. Величину Тм определяют как усредненное число операций 7Ѵ, выполняемых при однократном обращении к модели. Величину Ѵм определяют, в основном, числом В переменных математиче ской модели. Сравнение математических моделей по экономичности состоит в сравнении значений N и В.

Запишем алгоритм построения математической модели:

1.   Определение свойств решаемой задачи, которые должны отобразиться в модели. Основным здесь является определение перечня выходных переменных уі £ Y и входных переменных Xj £ X.

2.   Выбор структуры модели St в виде схем, «во спринимаемых» Л ПР. Установление взаимно однозначного соответствия и правил однозначного преобразования схем в математические соотношения.

3.   Решение задачи идентификации, при которой определяются численные значения параметров модели С = (сі, С2,...,с&) для заданной структуры модели.

4.   Выбор тестовых задач и на их основе определение погрешности. Если она больше допустимого значения то осуществляется переход к 2 с выбором новой структуры математиче ской модели; если меньше, то — переход к 5.

5.   Определение значений q min и q max. (Это способствует правильному выбору результатов принятия решений.)

6.   Конец работы алгоритма.

Заметим, что задача идентификации в алгоритме ставится как экстремальная. Найти пііпео (С) при С = (сі, С2,..., с&), с\ Е С в, где С в — область, в которой выбирают значения параметров математической модели; £о — обобщенная оценка погрешности математической модели. Для нахождения min £q (С) применяют методы математического программирования, эвристического поиска, эволюционные и генетические алгоритмы.

Отметим, что для получения математиче ской модели используются неформальные и формальные методы. Неформальные методы применяются на разных иерархических уровнях для построения элементов моделей. Они включают в себя анализ и изучение закономерностей процессов и явлений, принятие различных ограничений, допущений и упрощений. В настоящее время для этих целей начинают использоваться эвристические алгоритмы и динамические ЭС [41, 116, 159]. Построенные математические модели элементов можно применять итерационно как строительные блоки при построении иерархических математических моделей систем из этих элементов. При построении математиче ских моделей практических задач, в основном, используются неформальные и эвристические методы на основе нечетких множеств, многоагентных, самоорганизующихся систем и нетрадиционных алгебр логики и эволюционного моделирования [17-19,144].

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

Приведем неравенство для параметров задачи:

где cfM — номинальное значение параметра модели q, которое считается его математическим ожиданием; Si — допуск на значение данного параметра, который определяется как половина интервала со значением с“ом в центре.

Обозначим вектором ір = (^і,..., срг) множество параметров состояния ір С С, которые, являясь случайными величинами, влияют на значения выходных переменных. Кроме того, обозначим вектором ф = (фі, , • • •

..., фк) совокупность параметров состояния ф С С, которые, являясь нечеткими величинами, влияют также на значения выходных переменных. При этом фі = (cj, fii), где fi-i — функция принадлежности элемента Сі к множеству ф, т.е. Ці : ф —[0,1]. Тогда математическое описание модели примет вид:

Нечеткий модифицированный алгоритм построения математического

описания задачи можно представить в следующем виде:

1.   Определение существенных с точки зрения ЛПР свойств задачи, которые необходимо отразить в ее математическом описании.

2.   Разделение выбранных свойств на внешние, внутренние, неконтролируемые (случайные) и выходные переменные.

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

4.   Построение математиче ского описания в виде модели.

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

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

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

8.   Конец работы алгоритма.

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

здесь zг“, zf — соответственно нижнее и верхнее предельно допустимое значения для г-й управляемой переменной, а г — число управляемых переменных.

В процессе принятия решений стремятся выбирать значения вектора управляемых переменных, принадлежащего области поиска Z G Dz, таким образом, чтобы удовлетворить требования ЛПР. При формализации задачи удовлетворение требований сводится к выполнению системы соотношений между выходными переменными yj и их предельно допустимыми по техническому заданию значениями yj и yf, называемыми условиями работоспособности.

Область пространства управляемых переменных, в которой выполняются все условия работоспособности, называют областью работоспособности Dr. Тогда множество D = Dz f] Dr называется областью допустимых решений. Область D может оказаться выпуклым или невыпуклым множеством, которое может быть одно связным или многосвязным.

В случае невыпуклого множества D его необходимо разбивать на выпуклые подмножества D\,D2 причем Di |J D2 U • • • U = D,

aD1f]D2f]...f]Dk = 0. Как отмечено в [113], введение области Dr позволяет оценивать процент годных вариантов на основе определения вероятности условий работоспособности:

Вычисление статистического показателя Pz, в котором отражается случайный if и нечеткий ф характер параметров, может быть определен методом Монте-Карло или генетическим алгоритмом. Область D определяет множество всех работоспособных вариантов решений задачи, каждый из которых однозначно описывается вектором управляемых переменных ze D. Одна из проблем принятия решений — реализовать процедуру выбора из различных работоспособных вариантов, одного или некоторого множества, предпочтительных с точки зрения ЛПР.

Принимая предварительное решение, ЛПР дихотомически разбивает область D на два подмножества: D = D± \J D2. В подмножество Dі включаются отобранные по заданному критерию варианты решения, а. в D2 — все отклоненные варианты, причем D\ f] D2 = 0, но на каждой итерации принятия решения ряд вариантов могут переходить из D\ в D2 и наоборот.

Модифицированный процесс построения математиче ской модели нечетких процедур принятия решений в общих чертах следующий:

•    выбор параметров в качестве управляемых переменных;

•    построение области допустимых решений D;

•    задание механизмов эволюции и выбора правил генерации в области D работоспособных вариантов и определение подмножеств Dі и D2.

Сравнение работоспособных вариантов при принятии решений производится на основе бинарных четких и нечетких (расплывчатых) отношений предпочтения, определенных на множетсве D. Для сравнения вариантов принятия решений вводится критерий оптимальности Q — количественный показатель, характеризующий качество модели, с помощью которого осуществляется измерение одного наиболее важного для объекта свойства.

Под инженерной оптимизационной задачей понимается задача, в которой необходимо найти решение, в некотором смысле наилучшее или оптимальное. Отметим, что наилучшего решения во всех смыслах быть не может. Оно может быть принято оптимальным на основе критерия (меры оценки исследуемого явления) или ЦФ. Существует большое число оптимизационных задач и они могут иметь различный характер. Однако постановка, но не решение, всех оптимизационных задач имеет много аналогий [111-114, 159].

Во-первых, при постановке оптимизационных задач часто указывается исходное множество альтернативных вариантов решений. Из этого множества решений и выбирается оптимальное. Это исходное множество решений называется пространством решений. В дальнейшем его будем обозначать через М.

Во-вторых, некоторые решения априорно отвергаются в качестве «плохих» решений. Другими словами, в пространстве решений задаются ограничения, которым должны удовлетворять оптимальные решения. Эти ограничения выделяют в пространстве решений М некоторое подмножество М’ тех решений, которые удовлетворяют заданным ограничениям D. Как отмечалось выше, это — множество допустимых решений.

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

где і?+ — множество неотрицательных вещественных чисел.

Зная функцию Q, можно реализовать процедуру сравнения вариантов решений. При этом решение т Е М! лучше, чем решение т' Е М', если Q (т) < Q (т!). В этом случае говорят, что оптимизационная задача состоит в минимизации критерия Q, т. е. требуется найти такое допустимое решение т" Е М', что

Итак, оптимизационную задачу запишем в виде кортежа длины три: (М, D, Q), где М — пространство решений; D — ограничения, выделяющие в М область допустимых решений М' CM; Q : М' —» і?+ — критерий оптимизации. Требование оптимизации Q (т) —» min или Q (т) max. Решение т” Е М\ удовлетворяющее требованию оптимизации, называется оптимальным [111, 114].

Оптимизационная задача удовлетворяет двум основным требованиям: должны существовать как минимум два решения; надо знать, в каком смысле искомое решение должно быть наилучшим. Выбор задачи заканчивается ее содержательной постановкой. Модель описывает зависимость между исходными данными и искомыми величинами. Математическая модель оптимизационной задачи состоит из трех составляющих: целевой функции, ограничений, граничных условий. Часто классификацию оптимизационных задач проводят по трем основным характеристикам: область применения; содержание задачи; класс математиче ских моделей [111].

Обычно в области применения задачи делят на задачи управления, принятия решений, проектирования.

По содержанию можно выделить следующие виды задач:

•    распределение ресурсов;

•    оптимизация параметров объектов;

•    оптимизация структуры интеллектуальных ИС;

•    оптимизация процесса функционирования интеллектуальных ИС;

•    проектирование интеллектуальных ИС;

•    конструирование интеллектуальных ИС;

•    оптимизация технологического проектирования интеллектуальных ИС и др.

Классификацию математических моделей проводят: (а) по элементам модели; (Ь) по искомым переменным; (с) по зависимостям, описывающим ЦФ, ограничениям и граничным условиям. При этом выделяют модели [111]. Для а: детерминированные; случайные. Для Ь: непрерывные; дискретные. Для с: линейные и нелинейные.

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

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

•    при заданном результате минимизировать используемые ресурсы.

Максимум и минимум ЦФ в оптимизационных задачах объединяют

определением экстремума. Наибольшее или наименьшее значение функции без учета того, где находится такое значение — внутри заданного интервала или на его границе, называют не экстремумом, а оптимумом. Оптимум — более общее понятие, чем экстремум. Экстремум есть не у всех функций, а в оптимизационных задач оптимум есть всегда. Оптимум может быть локальным и глобальным. Глобальным максимумом (минимумом) называют такой максимум (минимум), который больше (меньше) всех остальных. В общем случае определение глобального оптимума при решении оптимизационной задачи сводится к нахождению всех локальных оптимумов, если это возможно, и выбора из него наилучшеш с точки зрения заданной ЦФ.

Оптимальное решение ж* Е D называется точкой локального минимума (локальным решением), если Ух Е d(x*,e) истинно высказывание Q(x*) ^ ^ Q(ж), здесь d(x*, г) — г-окрестность точки х. Оптимальное значение х* Е D называется точкой глобального минимума (глобальным решением), если ни в одной другой точке области допустимых решений функция Q(x) не принимает меньших значений: Q(x*) ^ Q(x) Мх Е D. Следовательно, глобальный минимум — это наименьший из всех локальных минимумов.

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

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

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