Т2 Аналитические представления

Необходимо определить максимально совместную подсистему уравнений и неравенств (1) по критерию

max C(x),	C(x) Ф (x) ,				(2)
(x)
где – вектор, составленный	из		характеристических		функций i
уравнений и неравенств ( i 1,	если i-ое уравнение или				неравенство
выполняется, в противном случае			i 0);	Ф( ) –	монотонная
положительно определенная числовая функция булевых переменных .
В частном случае критерий (2) имеет вид
	m
C(x) j j (x) ,					(3)
	j 1
где j – весовые коэффициенты, удовлетворяющие условиям
			m
j j 0,		j 1.

j 1

Решение системы уравнений и неравенств (1) по критерию (3) позволяет выделить среди всех максимально совместных подсистем системы (1) такую подсистему, которая обладает максимальным суммарным весом. Другими словами, в данном случае выделяется максимально совместная подсистема, наиболее важная с точки зрения решаемой предметной задачи. При равенстве весов решение задачи (1), (3) выделяет максимально совместную подсистему с максимальным числом уравнений и неравенств. В общем случае, когда рассматривается задача (1), (2), соответствующее решение позволяет выделить максимально совместную структуру уравнений и неравенств, оптимальную по обобщенному критерию (2).

______________________________

Общая процедура решения поставленной задачи непрерывнодискретного программирования состоит из двух частей: переборного алгоритма и решающего алгоритма. Переборный алгоритм осуществляет поиск максимально совместной подсистемы уравнений и неравенств, оптимальной по критерию (2). Решающий алгоритм осуществляет решение подсистем уравнений и неравенств по квадратичному критерию.

Рассмотрим решающий алгоритм с использованием квадратичного критерия.

В этом случае частные квадратичные критерии для уравнений и неравенств формируются в виде функций потерь

	q (x) 0,5	f	i	(x) 2	,	i I	ур	,
	i								(4)
	qi (x) 0,5	fi (x) 2				, i Iнер ;

где

137

			(x), если fi (x) 0;
fi	fi
	(x)				(x) 0.
		0,	если f
				i

Соответствующие частные производные по компонентам вектора иметь вид

	dik	(x) fi	(x)	fi	(x)	, i I ур	,
				xk

dik (x) fi (x) fi (x) , i Iнер .

xk

Далее, введем оценки перспективных частных направлений решений по отдельным соотношениям системы (1)

	1,		при			fik (x)			, dik (x) 0,
ik
	(x)	0,	при			fik (x)	,
	1,		при			fik (x)			, dik (x) 0,	i I ур ;

где – заданная точность решения задачи;

	1,		при fik (x) 0,	dik (x) 0,
ik			при fik (x) 0,
	(x)	0,
			при fik (x) 0,	dik (x) 0,	i Iнер .
	1,

х будут

(5)

поиска

(6)

(7)

Кроме того, введем частные направления поиска решений

	1,		переменная xk	возрастает,
k		0,	переменная xk	неизменна,	(8)
			переменная xk	убывает.
	1,

В целом некоторое l-ое направление поиска характеризуется вектором направлений δ(l), компоненты которого представляют собой частные

направления δk(l) по k-ым переменным хk.
В	l-ом	направлении	поиска	ожидаемое	значение

характеристической функции i-го соотношения системы (1) определяется условиями

1,	если k	ik		k	(l) 0,
iож (l)					(l) 0.	(9)
0,	если k ik k

Соответственно ожидаемое значение целевой функции (2) в l-ом направлении поиска

Cож (l) Ф ож (l) ,

(10)

Реальное значение целевой функции в l-ом направлении поиска определяется как решение системы уравнений и неравенств (1) по квадратичному критерию

138

min Qож (l; x), Qож (l; x) iож (l) fi (x) 2		iож (l) fi (x) 2 , (11)
(x)	i I ур	i Iнер

Решение задачи (11) можно выполнить, например, градиентным методом на основе рекуррентного соотношения

			iож (l) fi
xr	xr 1			(xr 1) grad fi (xr 1)
		i I ур

где – коэффициент релаксации, grad

iож (l) fi (xr 1)	grad fi	(xr 1)	, (12)
i Iнер

– градиент функции fi (xr 1 ) .

В результате решения поставленной задачи на основе рекуррентного соотношения (12) будет получено реальное значение целевой функции (2) в l-ом направлении поиска

C р (l) Ф р (l) .	(13)
Рассмотрим далее переборный алгоритм	поиска оптимального

решения реализующий метод ветвей и границ. Алгоритм состоит из следующих шагов.

Шаг 0. Рассматривается вся система уравнений и неравенств (1) в

целом. При этом принимаются начальные условия: i ож 1. На основе
			i
данных условий вычисляется	ожидаемое	значение	целевой	функции:
Cож (l0 ) Ф ож (l0 ) . Далее,	на основе	решения	задачи	(11) (13)

определяется точка максимально совместного решения x0 и вычисляется реальное значение целевой функции: C0p Ф р (x0 ) . Затем на основе

соотношений (9) определяется таблица перспективных направлений поиска решений

Tab0 { iож (l)}, Cож (l): l L0, Cож (l) C0p .

Здесь L0 множество перспективных направлений поиска решений, определяемых в локальной точке x0 , для которых ожидаемое значение

целевой функции больше реально достигнутого: Cож (l) C0p .

Шаг 1. В таблице перспективных направлений поиска решений Tab0 выбирается наиболее перспективное направление l1 , которое обладает

наибольшим	ожидаемым	значением	целевой	функции
Cож (l1 ) Ф	ож (l1 ) и для которого реальное		значение целевой функции

еще неизвестно. Далее, на основе решения задачи (11) (13) определяется

точка максимально совместного решения x1	и вычисляется	реальное
значение целевой функции: C1p Ф р (x1 ) .	Полученное	реальное

значение целевой функции сравнивается с ранее полученным значением C0p и определяется рекорд реального значения: Cmaxp max C0p , C1p . Затем

139

на основе соотношений (9) определяется таблица перспективных направлений поиска решений

Tab1 { iож (l)}, Cож (l): l L0 L1, Cож (l) Cmaxp .

Таблица Tab1 включает в себя подмножество перспективных направлений предыдущей таблицы Tab0 , удовлетворяющих условию Cож (l) Cmaxp , и новые направления поиска, определяемые соотношениями (9) в локальной точке x1 .

Шаг s. В таблице перспективных направлений поиска решений Tabs 1 выбирается наиболее перспективное направление ls , которое обладает наибольшим ожидаемым значением целевой функции Cож (ls ) Ф ож (ls ) и для которого реальное значение целевой функции

еще неизвестно. Далее, на основе решения задачи (11) (13) определяется

точка максимально совместного решения xs	и вычисляется	реальное
значение целевой функции: Csp Ф р (xs ) .	Полученное	реальное

значение целевой функции сравнивается с ранее полученным значением Csp 1 и определяется рекорд реального значения: Cmaxp max Csp 1, Csp .

Затем на основе соотношений (9) определяется таблица перспективных направлений поиска решений

Tab { ож (l)}, Cож (l): l L L , Cож (l) C p .

s i s 1 s max

Таблица Tabs включает в себя подмножество перспективных направлений

предыдущей таблицы	Tab	, удовлетворяющих условию	Cож (l) C p	, и
	s 1		max

новые перспективные направления поиска, определяемые соотношениями

(9) в локальной точке xs .

Конечный шаг. В таблице перспективных направлений поиска решений Tabn нет перспективных направлений, для которых реальное

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

______________________________

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

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

выполнены,	ЛПР	формулирует	предпочтения,	определяющие
		140

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

С математической точки зрения целевая функция представляет собой отображение

1					т	,
C ,		( 1, 2 , ... n )
где
1,	если y	j	D	;
			j
j	если y j D j ;				j 1, 2, ..., n.
0,

Здесь каждое j-ое условие описывается вектором своих параметров y j .

Само условие представляется в виде области допустимых значений параметров D j . Характеристическая функция условия j определяет факт

принадлежности вектора параметров y j соответствующей области допустимых значений D j .

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

реальное значение целевой функции C р (lп ) будет меньше ожидаемого

Cmaxож . Поэтому полученное решение x1opt будет являться частным.

Дальнейшее развитие процесса решения задачи может осуществляться на основе двух подходов.

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

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

Второй подход основывается на следующем.

141

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

2 C .

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

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

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

совокупности полученных частных решений {x1opt , x2opt , ... } не будут

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

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

2.6.Познавательные схемы

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

Особенностью подхода, развиваемого в данной работе при

рассмотрении

познавательных

схем,

является

использование

142

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

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

	{B , B , . . . , B } s C ,			(1)
	1 2	n
где B1, B2 , . . . , Bn	- составляющие детали сложного объекта C ;
s - действие сборки сложного объекта из составляющих его деталей.
Другой	пример,	структурное	представление	научно-

исследовательской деятельности на основе элементарных актов интеллектуальной коммуникации

qu	(2)
Th Rh ,
где Th – тема исследования, qu – вопрос по теме исследования,	Rh –

ответ на вопрос по теме исследования.

Стрелочные диаграммы типа (1), (2) с формальной точки зрения можно рассматривать как совокупности некоторых абстрактных объектов с заданными на них действиями, представляемых стрелками. Отличие алгебраических диаграмм от простых схем действий состоит в том, что здесь для стрелок, представляющих действия, определены алгебраические операции: инверсии, композиции и др.43

Так операция инверсии стрелки f :

A f B ,

приводит к обратной стрелке f 1 :

1

A f B .

Операция композиции стрелок f , g :

A f B , B g C ,

приводит к результату, который аналитически представляется как g f :

43 Понятие стрелочной диаграммы следует рассматривать в математическом смысле, принятым в алгебраической теории категорий. В этом случае объекты диаграммы и стрелки, называемые также морфизмами, имеют строгое математическое определение. Сама диаграмма имеет смысл алгебраической системы. В такой интерпретации структурное представление познавательной деятельности в виде абстрактной алгебраической системы можно рассматривать как математическую модель реальных концептуальных систем, отражающую их определенные структурные свойства. Подобное представление является весьма общим и охватывает широкий класс формализованных логических систем. Подробно данные вопросы освещены, например, в работе: Голдблатт, Р. Топосы. Категорный анализ логики / Р. Голдблатт. - М.: Мир,

1983. - 488 с. (Goldblatt, R. TOPOI. The categorial analysis of logic / R. Goldblatt: NorthHolland Publishing Company, 1979. – 488 р.).

143

A f B g C .

Свойство коммутативности состоит в том, что если разные пути действия стрелок в диаграмме имеют одинаковые начало и конец, то для коммутативной диаграммы совокупные действия стрелок в указанных путях равны. Например, если в диаграмме имеются два пути действия стрелок с совпадающими началом и концом:

	A B C , A C ;
	f	g	h
тогда h g	f .
Также постулируется для каждого объекта B диаграммы
существование единичной или тождественной стрелки 1B : B B , так что
выполнено правило тождества
– для	любых стрелок	f	g
		f : A B и g : B C справедливы
равенства
	1B	f f ,	g 1B g ,
т.е.	A B B A B ,
	f	1B	f
	B B C B C .
	1B	g	g

С учетом сказанного алгебраическую диаграмму можно формально определить как совокупность абстрактных объектов с заданными на них

стрелками, удовлетворяющими приведенным выше свойствам44:

D {A, B, C, ...}, {f , g, h, ...}> .

Диаграмма	Dop 45	называется	двойственной	(дуальной,
противоположной)	по отношению к диаграмме D , если			множества

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

справедливо равенство D Dop . Действие операции перехода от исходной диаграммы D к двойственной диаграмме Dop можно представить в виде упорядоченной пары диаграмм (D, Dop ) . Обозначим объединение

диаграмм Daut D Dop . Диаграмма Daut будет самодвойственной. Действие операции перехода от исходной диаграммы D к

самодвойственной диаграмме Daut можно представить упорядоченной тройкой (D, Dop , Daut ) .

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

45Верхний индекс ор представляет здесь сокращение английского слова opposite

–противоположный, соответственно aut - сокращение слова autodual.

144

На множествах диаграмм определяются операции с диаграммами, которые называются функторы. Особенностью функторов является то, что они состоят из совокупности двух отображений: (i) отображения множества объектов исходной диаграммы во множество объектов результирующей диаграммы, (ii) отображения множества стрелок исходной диаграммы во множество стрелок результирующей диаграммы46. Например, контравариантный функтор меняет направление стрелок исходной диаграммы на противоположное направление; забывающий функтор отображает совокупность множеств, наделенных некоторой структурой, в совокупность множеств, лишенных соответствующей структуры и др. Таким образом, функтор представляет собой формальную операцию над диаграммами (алгебраическими структурами), в которую вовлечены не только объекты, входящие в диаграмму (алгебраическую структуру), но и связи объектов. Подобные операции будем называть

структурными операциями.

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

_____________________________________

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

47 Использование алгебраических категорий в системных исследованиях с целью изучения структурных свойств формализованных представлений является известным подходом. Так в работе [Arbib, M.A. Foundations of system theory: decomposable systems / M.A. Arbib, E.G. Manes // Automatica. – 1974. – 10. – P. 285-302; русск. пер.: Арбиб, М.А.

Основания теории систем: разложимые системы / М.А. Арбиб, Э.Дж. Мейнс // Математика, новое в зарубежной науке: под. ред. А.Н. Колмогорова, С.П. Новикова. – Вып.14. – Математические методы в теории систем.- М.: Мир, 1979. – С. 7-48] алгебраические категории были использованы для доказательства двойственности (дуальности) понятий достижимости и наблюдаемости для линейных систем. В

работе [Mesarovic, M.D. General Systems Theory: Mathematical Foundations / M.D. Mesarovic, Y. Takahara. – New York, San Francisco, London: Academic Press, 1975; русск.

пер.: Месарович, М. Общая теория систем: математические основы / М. Месарович, Я. Такахара. - М.: Мир, 1978. – С. 255-284] алгебраические категории были использованы для строгой доказательной классификации категорий динамических систем.

145

Используя стрелочные диаграммы можно построить, например,

следующую схему системной познавательной деятельности

A

1	2	п		c	(3)
{B1, B2, . . . , Bn}			s		C .

Здесь A, {Bi}, C – представления о предметах деятельности; { i}, s, c – операции над представлениями.

Логическая интерпретация диаграммы (3) следующая:

A – исходное представление о предметах познавательной деятельности в целом (абстрактная целостность), например, абстрактное представление о предмете в целом до проведения исследований, раскрывающих его конкретные свойства; исходная идея исследования; исходная тема исследования и т.п.

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

{Bi} – частные представления о предметах деятельности

(конкретные логические части), например, содержание частных результатов исследования предметов;

C – логически полное представление о предметах деятельности (конкретное логическое целое), например, знание о предметах, полученное на основе логического объединения частных результатов исследования по заданной теме;

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

c – операция конкретизации, например, действия по формированию конкретного целостного представления о предметах на основе совокупных результатов исследований, проведенных по заданной теме.

Диаграмма (3) естественно отражает определенные структурные особенности системного исследования. Действительно, на начальном этапе исследования предмет исследования внешне выступает как нечто целое. Целое является по своей сути абстрактным, так как не отражает детали структуры предмета. Поэтому следующим этапом исследования является разложение (анализ) предмета на частные составляющие (части, детали, элементы) с целью выявления его структуры. Заключительным этапом

146