О природе неопределенности и переменных критериях в задачах разбиения

Показано, що ситуація невизначеності в задачах розбиття виникає внаслідок особливостей структури множини розбиттів n-елементної множини (аргумента цільової функції) на підмножини, структури вхідної інформації, способу моделювання цільової функції. Для виходу із цієї ситуації пропонується формулювати...

Full description

Saved in:

Bibliographic Details
Published in:	Проблемы управления и информатики
Date:	2009
Main Author:	Тимофеева, Н.К.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2009
Subjects:	Методы обработки информации
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/210616
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	О природе неопределенности и переменных критериях в задачах разбиения / Н.К. Тимофеева // Проблемы управления и информатики. — 2009. — № 5. — С. 88-99. — Бібліогр.: 26 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860263579168538624
author	Тимофеева, Н.К.
author_facet	Тимофеева, Н.К.
citation_txt	О природе неопределенности и переменных критериях в задачах разбиения / Н.К. Тимофеева // Проблемы управления и информатики. — 2009. — № 5. — С. 88-99. — Бібліогр.: 26 назв. — рос.
collection	DSpace DC
container_title	Проблемы управления и информатики
description	Показано, що ситуація невизначеності в задачах розбиття виникає внаслідок особливостей структури множини розбиттів n-елементної множини (аргумента цільової функції) на підмножини, структури вхідної інформації, способу моделювання цільової функції. Для виходу із цієї ситуації пропонується формулювати додаткові цільові функції та в процесі розв’язання задачі вводити змінні критерії. It is shown that a situation of uncertainty in the partition problems arises as a result of the special structure of a set partitioning an n-element set into subsets (argument of objective function), structure of input data, method of modeling of objective function. For a way out of this situation formulation of additional objective functions and introduction of variable criteria in the process of solving the problem are suggested.
first_indexed	2025-12-17T12:04:21Z
format	Article
fulltext	© Н.К. ТИМОФЕЕВА, 2009 88 ISSN 0572-2691 МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ УДК 519.14+519.816+519.863 Н.К. Тимофеева О ПРИРОДЕ НЕОПРЕДЕЛЕННОСТИ И ПЕРЕМЕННЫХ КРИТЕРИЯХ В ЗАДАЧАХ РАЗБИЕНИЯ Введение. Для класса задач разбиения исследуется ситуация неопределенно- сти, которая возникает при разных обстоятельствах, а именно: при неполной вход- ной и текущей информации, особенностях структуры множества разбиений (аргу- мента целевой функции), способа моделирования целевой функции. Предлагается выход из этой ситуации путем введения переменных критериев, учитывающих до- полнительную текущую информацию, которая генерируется при моделировании прогнозируемых результатов и которую невозможно задать по условию. Понятие «задачи разбиения» объединяет широкий класс задач (как дискрет- ных, так и непрерывных), аргументом целевой функции в которых является раз- биение n-элементного множества на подмножества. Это — компоновка, кластери- зация, классификация, самообучение, покрытие, разбиение геометрической по- верхности, разрезание графов и т.д. Целевая функция в них формулируется по-разному, подходы к их решению также разные. Эта проблема чрезвычайно разветвленная и существует в самых разнообразных отраслях человеческой дея- тельности (см., например, [1–19]). Несмотря на то что задачи разбиения исследуются не одно десятилетие, их точная математическая постановка еще не разработана. Как правило, формальную постановку некоторых задач из этого класса проводят в терминах математической статистики или с использованием терминологии теории бинарных отношений. Условие неопределенности в задачах комбинаторной оптимизации рассматрива- ется в работах [7, 20–22] для случая с нечеткой входной информацией. Но не- определенность, связанная с особенностями структуры входной информации или структуры аргумента целевой функции, для этих задач изучена недостаточно. Сложность задач разбиения заключается в том, что результат их решения не всегда зависит лишь от входной информации. К тому же в задачах с нечеткими входными данными кроме количества операций, затрачиваемых на отыскание глобального решения, необходимо учитывать и меры сходства, которые здесь иг- рают основную роль и от правильного выбора которых в значительной степени зависит сам результат, а полученное по смоделированной целевой функции гло- бальное решение не всегда соответствует цели исследования. Иначе говоря, воз- никает ситуация неопределенности, связанная с моделированием целевой функ- ции и неполной входной и текущей информацией. Для определения факторов, от которых зависит оптимальное решение, сфор- мулируем задачи разбиения в терминах теории комбинаторной оптимизации. Постановка проблемы. Сначала сформулируем общую математическую по- становку задачи комбинаторной оптимизации. Задачи этого класса задаются од- ним или несколькими множествами, например A и B, элементы которых могут Проблемы управления и информатики, 2009, № 5 89 иметь любую природу. Назовем эти множества базовыми. Существует два типа таких задач. В первом типе каждое из этих множеств можно представить в виде графа, вершинами которого являются их элементы, а каждому ребру поставлено в соответствие число ,Rcrl  которое называют весом ребра (R — множество ве- щественных чисел). Это значит, что между элементами этих множеств существу- ют связи. Величины ,rlc назовем входными данными и зададим их матрицами. В задачах второго типа между элементами заданного множества связей не суще- ствует, а весами выступают числа ,Rv j  в соответствие которым поставлены не- которые свойства этих элементов и числовые значения которых задаются конеч- ными последовательностями. Числа ,jv как и ,rlc являются входными данными и определяют значение целевой функции. Количество базовых множеств и способ задания входных данных характеризуют особенность любой из этих задач. Из элементов одного из заданных множеств, например ,Aal  },,...,1{ nl образует- ся комбинаторное множество W — совокупность комбинаторных конфигураций определенного типа (перестановки, выборки разных типов, разбиения и т.д.). На элементах Ww вводится целевая функция ).(wF Необходимо найти элемент w множества ,W для которого целевая функция принимает оптимальное значе- ние при выполнении заданных ограничений. Задачи разбиения характеризуются четкой или нечеткой входной информаци- ей, а также способом ее задания. Аргументом целевой функции в них служит разби- ение n-элементного множества на подмножества (рассматриваем разбиение на не- пересекающиеся классы). Разбиением n-элементного множества },...,{ 1 naaA  на  подмножеств (блоков) назовем множество подмножеств ),,( 1 kkk kwww    та- кое, что ,...1 Aww kk k    ,k sw ,k s k p ww  ,sp  },,...,1{, ksp  },...,1{ nk  — количество подмножеств в .kw Подмножество ,),...,( 1 k s aawk s   ,Aar  },,...,1{ nr может иметь от 1 до n элементов }).,...,1{( nk s  Верхний индекс k в kw обозначает порядковый номер разбиения в множестве всех воз- можных разбиений ,W },,...,1{ qk q — количество kw в .W Два разбиения kw и iw назовем изоморфными, если ik  и для любого подмножества kk p ww  найдется подмножество ,ii s ww  для которого .i s k p  Подмножество WW k   назовем подмножеством изоморфных разбиений, если его элементы — изоморфные разбиения. Множество W состоит из подмно- жеств изоморфных разбиений .kW  По количеству подмножеств и количеству в них элементов разбиения kw де- лятся на четыре типа [23]. К первому типу относятся ,kw количество элементов во всех подмножествах которых различно. Количество элементов в подмноже- ствах k sw разбиения второго типа одинаково. В разбиение третьего типа входят два и больше подмножеств, которые содержат один элемент, и хотя бы одно под- множество должно содержать больше чем один элемент. В разбиение четвертого типа входят два и больше подмножеств, количество элементов в которых одина- ково, при этом одно из подмножеств должно иметь наибольшее количество эле- ментов по сравнению с другими. 90 ISSN 0572-2691 Поиск оптимального решения в задачах разбиения проводится как на всем множестве W (кластеризация, классификация, таксономия), так и на подмноже- стве kW  (компоновка, задача о куче камней, разрезание графа на непересекае- мые подграфы). Закономерность изменения значений целевой функции в них за- висит от упорядочения комбинаторных конфигураций (аргумента) [24]. Незави- симо от входных данных для определенного упорядочения подмножеств kW  значения целевой функции изменяются одинаково и в процессе решения индиви- дуальной задачи возникает ситуация неопределенности, связанная с особенностя- ми структуры аргумента. Математические постановки задач разбиения разных типов. Уточним та- кие понятия, как критерий и целевая функция. Критерий — признаки или свойства, которые характеризуют определенный объект и являются входными данными. Целевая функция — выражение, которое формулируется на основе заданных критериев с учетом специфики задачи и по которому вычисляется и оценивается результат решения задачи. Как правило, целевую функцию отождествляют с критериями. Но для одних и тех же критериев целевую функцию можно смоделировать по-разному, т.е. оце- нивание проводится по разным выражениям и получается разный результат. Например, оптимизацию проводим по суммарному или среднему значениям весов между элементами базового множества. По способу задания входной информации задачи разбиения разделяются на два типа (І и ІІ). Для задания целевой функции в явном виде структуру вход- ных данных смоделируем функциями натурального аргумента, одна из которых комбинаторная. Рассмотрим задачу типа І, входные данные в которой заданы матрицами. К таким задачам относятся классификация, кластеризация, компоновка, разреза- ние графа на непересекаемые подграфы. Пусть задано одно множество A. Веса элементов ra и ,la lr, },...,,1{ n ,lr  множества A зададим симметрической матрицей C. Для определения на k-м варианте решения задачи наличия элементов ra и la в одном подмножестве введем симметрическую комбинаторную (0, 1)-матрицу ).( kwQ Для варианта kw элемент ,1)( k rl wg если Aar и Aal содержатся в одном подмножестве, и 0)( k rl wg — в противном случае, .)()( kk rl wQwg  Назовем компонентой разбиения kw одно или несколько подмножеств ,kk p ww  объединенных между собой связями. Количество таких компонент в разбиении может быть от одной до .k Представим элементы h наддиагоналей симметрической комбинаторной мат- рицы )( 1wQ числовой функцией ,)( 1 m jf а матрицы C — функцией ,)( 1 mj ,1,1  nh где 1w — первое разбиение в kW  [25]. Комбинаторная функция mkwjf 1)),(( — это числовая функция ,)( 1 m jf которая изменяется в зависимо- сти от ,kw .2/)1(  nnm Функция цели )( kwF для задачи типа І имеет вид ).(),)(()( 1 jwjfwF k m j j k    (1) Проблемы управления и информатики, 2009, № 5 91 На подмножестве изоморфных разбиений комбинаторной матрицей может быть любая из заданных. Задача разбиения заключается в отыскании такого ,* Wwk  для которого целевая функция (1) принимает наибольшее значение. К задачам типа ІІ относятся некоторые задачи разбиения геометрической по- верхности, задача о куче камней и т.д. Сформулируем ее на примере задачи о куче камней [24, 26]. Пусть каждому ja из множества камней },...,{ 1 naaA присвоено положи- тельное число — его вес .jv Необходимо разделить это множество на  частей так, чтобы вес самой тяжелой из куч был наименьшим. В этой задаче задано одно множество },,...,{ 1 naaA между элементами Aa j  которого отсутствуют связи, а входные данные имеют вид конечной по- следовательности n j 1 )( (функцией натурального аргумента), значения которой )( j определяют вес j-го камня. Распределение элементов множества A по подмножествам k sw для k-го варианта решения задачи определим с помощью комбинаторной функ- ции )),),((,,),1((()),(( 11 k n knk wnfwfwjf   где };1,0{)),((  k j wjf ,1)),((  k j wjf если a j-й элемент входит в подмножество ,kk s ww  и 0)),((  k j wjf — в противном случае. Для подмножества k sw значение целе- вой функции вычисляется по выражению (1), а для kw — по выражению .)()),((,,)()),((max)( 11 1 ,1                n j k j n j k j s ww k jwjfjwjfwF k k kk s  Задача о куче камней состоит в отыскании такого ,kw для которого целевая функция на подмножестве WW k  принимает наименьшее значение, т.е. .)(min)( k WWw k wFwF k k    Рассмотрим задачу кластеризации, которая относится к типу І. Кластериза- ция — это способ группирования однородных объектов с целью выделения та- ких однородных кластеров (или «сгустков») этих объектов, чтобы объекты внутри них были похожи друг на друга, а объекты разных кластеров — непохо- жи [1–4]. В дальнейшем под объектами подразумеваем элементы заданного мно- жества }....,,{ 1 naaA Для моделирования целевой функции в задаче кластериза- ции необходимо: а) учесть множество признаков заданных элементов; б) для определения подобия элементов ввести меру сходства; в) определить способ оценки кластера. Рассмотрим эти три условия подробнее. Обозначим множество признаков элементов ,Aar  },,,1{ nr  упорядо- ченным множеством ).,,,( )()()()( 21 t a t a t a t n vvvV  Элементы )()( tt a Vv r  определяют частичные критерии качества, по которым оптимизируется смоделированная целевая функция, },...,,1{ zt  где z — количество частичных критериев. Число- вые значения этих критериев определяются мерой сходства между элементами ra 92 ISSN 0572-2691 множества .A Пусть ),()( rl t aau — элементарная мера сходства между ,la Aar  для t-го критерия. Поскольку критерии могут быть введены как для элементов, так и для кластеров, введем меру сходства ),(~ )( k p k s t wwu между кла- стерами ., kk p k s www  Их числовые значения для t-го критерия, которые назо- вем весами ,, Aaa rl  зададим симметрической матрицей , )()( nn t lr t cC   где ).,(~ )()( rl tt lr aauc При первом способе оценки кластера целевая функция моделируется по опи- санной схеме. Для k-го разбиения при вычислении целевой функции учитываются веса элементов, которые находятся в одном подмножестве. Элементы симметри- ческой (0, 1)-матрицы nn k lr k wgwQ   )()( определяют наличие или отсутствие элементов rl aa , в .kk s ww  Аналогично последовательность элементов h наддиагоналей симметрической матрицы )(tC по t-му признаку представим числовой функцией, а матрицы )( 1wQ — комбинаторной ,)),(( 1 1 m wjf которая изменяется в зависимости от типа разбиений и не зависит от входных данных. По первому способу оценки кла- стера целевая функция приобретает вид (1), т.е. .)(),)(()( )( 1 )( 1 jwjfwF tk m j j kt    (2) Для моделирования целевой функции при втором способе оценки кластера для s-го подмножества kk s ww  определим количество единиц в комбинаторной функции. В [24] доказано, что их количество , !2)!2( !    k s k sk sJ .1k s Запишем среднее значение весов для t-го критерия: .)()),(()( 11 )()( 2 /            k s k s m j tk sj kt JjwjfwF (3) Выражения (2), (3) представляют собой интегральные меры сходства, кото- рые определяют постоянные частичные критерии качества, если сходство уста- навливается между заданными элементами. На подмножестве kW  целевая функция изменяется так, как и на множестве перестановок, которое является множеством изоморфных комбинаторных конфи- гураций. Упорядочим подмножества ,WW k   начиная с 1i и заканчивая .nk  Сформулируем теорему, доказательство которой приведено в [24]. Теорема. Если в задачах разбиения оптимизация проводится по суммарному или среднему значению весов между элементами базового множества, то целевая функция на заданном упорядочении ,WW k   ,,1 nk  — дискретная кусочно- монотонная функция (соответственно неубывающая или невозрастающая). Как следует из теоремы, для заданного упорядочения подмножеств изоморф- ных разбиений (аргумента) смоделированные целевые функции (2), (3) изменяют- Проблемы управления и информатики, 2009, № 5 93 ся одинаково независимо от входных данных, т.е. возникает ситуация неопреде- ленности как для задачи типа І, так и для задачи типа ІІ. Поэтому необходимо вводить дополнительные критерии или целевые функции, например оптимизацию проводить по количеству компонент в разбиении. Обозначим )( k p wS компонен- ту, которая содержится в разбиении .kw Запишем целевую функцию, определя- ющую количество компонент в :kw ,)()( ~ 1 3    kq p k p k wSwF (4) kq~ — количество компонент в .kw В процессе решения задачи значения целевой функции с учетом заданных по условию критериев для всех возможных вариантов kw могут быть одинаковыми, из-за чего создается ситуация неопределенности, связанная со структурой вход- ной информации. Несложно доказать, что использование целевой функции (4) позволяет найти оптимальное решение в данном случае. Для этого необходимо задать дополнительные критерии, которые учитывают непрямые связи между элементами на этапе частичного решения задачи и определяют оптимальное ре- шение на следующих этапах. Поскольку критерии — входные данные, то введе- ние переменных критериев основывается на генерировании в процессе решения задачи дополнительной информации с учетом прогноза будущих результатов. Этой информацией в задачах разбиения могут быть непрямые связи между эле- ментами разных подмножеств (кластеров) разбиения .kw Выход из ситуации неопределенности путем введения в процессе решения задачи переменных критериев рассмотрим на примере задачи компоновки базо- вых элементов в модули, которая решается на подмножестве изоморфных разбие- ний WW k  [10]. Содержательная постановка этой задачи такова. Задано n ба- зовых элементов разных типов, между которыми существуют электрические свя- зи. Необходимо эти элементы распределить по модулям так, чтобы количество связей между последними было минимальным или количество связей между эле- ментами, объединенными в модуле, было наибольшим. По условию, между неко- торыми элементами могут отсутствовать связи. В процессе решения задачи воз- никает ситуация неопределенности, когда значение целевой функции с учетом за- данных критериев для всех возможных вариантов решения одинаково. Поэтому кроме оптимизации решения по целевой функции (1) необходимо найти такой ва- риант разбиения, чтобы количество компонент в нем было наибольшим, т.е. оп- тимизацию следует проводить по выражению (4). Для этого введем дополнитель- ные критерии. Пусть заданы n элементов, которые образуют множество }....,,{ 1 naaA Каждый элемент Aal  принадлежит к одному из K заданных типов. Подмно- жество элементов i-го типа обозначим ,iX },,...,1{ Ki , 1 AX K i i    причем .it XX  Задача компоновки заключается в определении такого разбиения )...,,( 1 kkk kwww   элементов множества A на заданное количество k подмно- 94 ISSN 0572-2691 жеств, для которого целевая функция (1) принимает оптимальное значение и при этом выполняются такие условия: ,k sw ,k p k s ww  Aw k s k s     1 для k srl waa , и ,, i rl Xaa  ,k s k sw  .,1 ks  По первому критерию в процессе решения задачи компоновки находим такой вариант разбиения, для которого суммарное количество заданных по условию связей между подмножествами ,k sw k sw минимальное. Частичная целевая функ- ция в этом случае приобретает вид .)(),)(()( 1 )1( jwjfw k m j j k    (5) Следует заметить, что учет критерия (5) эффективен, когда элементы отно- сятся к одному и тому же типу и имеют прямые связи. На рис. 1 приведен пример объединения элементов одного типа по под- множествам с использованием критерия (5) и учетом количества компонент в разбиении, .,,, 4321 iXaaaa  a1 a3 kw1 а2 a4 kw2 Рис. 1 Рассмотрим случай, когда элементы относятся к разным типам, а относящие- ся к одному типу не имеют прямых связей. В этом случае необходимо вводить другие критерии, которые позволяют учитывать степень непрямой связи для про- извольной пары базовых элементов. Назовем критерии переменными одноразо- выми, если они используются в процессе решения задачи один раз, и переменны- ми многоразовыми, если они используются многократно в итерационном режиме. Учет дополнительных критериев позволяет найти оптимальное решение в случае, когда по критерию (5) для разных вариантов разбиения kw получаем одинаковые значения целевой функции ).( kwF Рассмотрим некоторые из них. Сначала введем понятие частичного разбиения A множества ,A под кото- рым понимаем совокупность подмножеств Awk  ~ таких, что ,k p k s ww  ;~,1, ps ; ~ 1 Aw s k s     ;~ k AAA  \ — подмножество, которое содержит элементы не распределенные между блоками разбиения в случае использования критерия (5). Пусть заданы базовые элементы ,, i rl Xaa  ,~ t r Xa  ,ti  такие, что ,la ,, ~ Aaa rr  ,0lrc ,0~ rrc .0~ rlc Элементы Cccc rlrrrl ~~ ,, определяют ко- личество связей между .,, ~ Aaaa rrl  Введем матрицу ,C  элементы которой .~~ rrrllr ccc  Следовательно, матрица C  определяет количество непрямых свя- зей между элементами одного и того же типа, .,1~,, nrrl  Проблемы управления и информатики, 2009, № 5 95 Элементы h наддиагоналей матрицы C  обозначим числовой функцией )).(...,),1(()( 1 mj m  Частичная целевая функция, которая учитывает не- прямые связи элементов одного и того же типа, приобретает вид ).(),)(()( 1 )2( jwjfw k m j j k    (6) Комбинаторная функция mkwjf 1 ),(( своего значения не изменяет. Пример объединения элементов одного типа по подмножествам с использовани- ем второго критерия, ,,,, ~ 4321 tXaaaa  ,,,, 8765 iXaaaa  ,,,, 1211109 tXaaaa  иллюстрирует рис. 2. a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a1 a2 a5 kw5 kw1 a3 a4 a6 kw6 kw2 a9 a10 a7 kw7 kw3 a11 a12 a8 kw4 kw8 а б a1 а3 a5 * 1 kw a2 a4 а6 * 3 kw * 2 kw * 4 kw a9 а11 a7 * 5 kw a10 a12 а8 * 7 kw * 6 kw * 8 kw в Рис. 2 На рис. 2, б изображен вариант разбиения ,kw в котором четыре компонен- ты, и на рис. 2, в — ,kw в котором две компоненты. Количество связей между их подмножествами одинаковое (четыре). Но для последующего размещения по- лученных модулей на плате и трассировки проводников оптимально разбиение kw с четырьмя компонентами. Таким образом, учет критерия (5) целесообразен в случае, если 0lrc при ,A ., i rl Kaa  Критерий (6) может быть использован при 0lrc и A или .A Но этот критерий неэффективен, если существует такое ,~ l a для ко- торого ,0lrc ,0~~  rl c ,0~  ll c ,0~ rrc ,, i rl Xaa  ., ~~ t rl Xaa  Поэтому необходимо ввести другие критерии, которые учитывали бы эти особенности свя- зей между элементами. Они дадут возможность выбрать лучший вариант компо- новки даже в том случае, если учет критериев (4), (5) приведет к проблеме выбора варианта решения задачи среди разбиений ,kWwk   для которых целевая функ- ция имеет одинаковое значение, т.е. в ситуации неопределенности. Пусть заданы элементы ,,,, ~~ Aaaaa lrrl  ,, i rl Xaa  ., ~~ t rl Xaa  Введем матрицу ,C  элементы которой ,~~ lrrllr ccc  если 0~ rlc и ,0~  lr c или ,~~ rrlllr ccc  если 0~  ll c и ;0~ rrc ,0lrc .0~~  lr c 96 ISSN 0572-2691 Запишем элементы h наддиагоналей матрицы C  числовой функцией ))(...,),1(()( 1 mj m  и определим частичную целевую функцию, которая учитывает непрямую связь между элементами :, Aaa rl  .)(),)(()( 1 )3( jwjfw k m j j k    (7) Матрицы ,,, CCC  которыми задаются входные данные, вычисляются один раз и не изменяются в процессе решения задачи компоновки. Критерии (5)–(7) также учитываются лишь один раз, причем использование каждой оценки начина- ется в том случае, когда с использованием предыдущих критериев для вариантов разбиения kw взвешенная целевая функция принимает одинаковые значения. Пример объединения заданных базовых элементов по подмножествам с использованием третьего критерия, ,,,, 4321 tXaaaa  ,,,, 8765 iXaaaa  ил- люстрирует рис. 3. a1 a5 a2 a6 a3 a7 a4 a8 a1 a2 kw3 kw1 a3 a4 kw4 kw2 a5 a6 a7 a8 a4 a1 3 kw * 1 kw a5 a6 * 4 kw * 2 kw a8 a7 a3 a2 а б в Рис. 3 Разбиение kw содержит две компоненты (рис. 3, б), а kw — одну (рис. 3, в). Количество связей между подмножествами этих разбиений одинаково, но для по- следующего решения задачи вариант разбиения kw оптимален. Если использование частичных критериев (5)–(7) приводит к равнозначным вариантам решения задачи, то для устранения этой ситуации введем переменные многоразовые критерии, которые учитываются в процессе решения задачи много- кратно. Пусть задано ,, Aaa rl  ,0lrc ,, i rl Kaa  Aaa rl ~~ , и ., ~~ k srl waa  Введем матрицу ,C  элементы которой ,~~ lrrllr ccc  если ,0~ rlc 0~  lr c , или ,~~ rrlllr ccc  если ,0~ rrc .0~  ll c Задав элементы h наддиагоналей матрицы C  числовой функцией   m j 1 )( )),(...,),1(( m   получим частичную целевую функцию для переменного мно- горазового критерия в виде вид ).(),)(()( 1 )4( jwjfw k m j j k     (8) На рис. 4 приведен пример объединения элементов по подмножествам с использованием четвертого критерия, ,,,, 4321 tXaaaa  ,,,, 8765 iXaaaa  ,,,, 4321 Aaaaa  .,,, 8765 Aaaaa  Вариант kw на рис. 4, б, как и на рис. 3, б, оптимален. Проблемы управления и информатики, 2009, № 5 97 a1 a5 a2 a6 a3 a7 a4 a8 a1 a2 kw1 kw3 a3 a4 kw2 kw4 a5 a6 a7 a8 a2 a4 1 kw * 3 kw a8 a7 * 4 kw * 2 kw a6 a5 a1 a3 а б в Рис. 4 Для каждого частичного варианта разбиения kw в итерационном режиме формируется матрица ,C  по которой вычисляется функция (8). Все эти критерии не единственно возможные, но они выбраны потому, что в значительной степени определяют качество компоновки. Как критерий выбора при определении пары кандидатов на включение в некоторое подмножество раз- биения kw запишем взвешенную целевую функцию ,)()( )( ~ 1 kl l z l k wwF   где ,0l    z l l ~ 1 1 — взвешенные коэффициенты, z~ — количество целевых функ- ций ,)(l которые образуются на основе переменных частичных критериев. Вы- бором значения l изменяется величина вклада критериев )()( kl w при отыска- нии оптимального решения. Запишем целевую функцию ))(),(),...,(()( )()()1( klkz j k j k wwFwFwF  , по ко- торой найдем оптимальное решение (здесь )(t jF — j-я целевая функция, которая формулируется с учетом t-го постоянного частичного критерия, заданного по усло- вию задачи; )(l — l-я целевая функция, которая формируется на основе перемен- ных частичных критериев, вводимых в процессе решения задачи, },...,,1{ Lj },~...,,1{ zl L — количество целевых функций ). )(t jF Учет постоянных частич- ных критериев эффективен, если оптимизация проводится на подмножестве изо- морфных разбиений. Они могут быть учтены в процессе решения задачи лишь один раз. Переменные частичные критерии вводятся в случае, если появляется ситуация неопределенности. Они могут использоваться как один раз, так и много- кратно в итерационном режиме таким образом: на l-м этапе частичного решения задачи вычисляются непрямые связи между элементами и с учетом вычисленной вспомогательной информации определяется новый вариант решения задачи. Заключение. В задачах разбиения ситуация неопределенности возникает вследствие особенностей структуры множества разбиений, которые являются ар- гументом целевой функции, структуры входных данных, способа моделирования целевой функции, а также вследствие неполноты входной и текущей информации. Для выхода из этой ситуации оценивание результата может проводиться как по одной, так и по нескольким целевым функциям; кроме того, вводятся переменные критерии. Учет заданных по условию постоянных частичных критериев эффекти- вен, когда элементы Aal  одного и того же типа имеют прямые связи. К тому же они могут быть учтены в процессе решения задачи лишь один раз. Перемен- ные частичные критерии вводятся в случае отсутствия прямых связей между эле- 98 ISSN 0572-2691 ментами одного типа, из-за чего возникает ситуация неопределенности. Эти кри- терии позволяют генерировать дополнительную информацию, которая влияет на прогнозирование будущих результатов. Н.К. Тимофієва ПРО ПРИРОДУ НЕВИЗНАЧЕНОСТІ ТА ЗМІННІ КРИТЕРІЇ В ЗАДАЧАХ РОЗБИТТЯ Показано, що ситуація невизначеності в задачах розбиття виникає внаслідок особливостей структури множини розбиттів n-елементної множини (аргумента цільової функції) на підмножини, структури вхідної інформації, способу моде- лювання цільової функції. Для виходу із цієї ситуації пропонується формулю- вати додаткові цільові функції та в процесі розв’язання задачі вводити змінні критерії. N.K. Tymofijeva ON NATURE OF UNCERTAINTY AND VARIABLE CRITERIA IN THE PARTITION PROBLEMS It is shown that a situation of uncertainty in the partition problems arises as a result of the special structure of a set partitioning an n-element set into subsets (argument of objective function), structure of input data, method of modeling of objective function. For a way out of this situation formulation of additional objective func- tions and introduction of variable criteria in the process of solving the problem are suggested. 1. Мандель И.Д. Кластерный анализ. — М. : Финансы и статистика, 1988. — 176 с. 2. Факторный, дискриминантный и кластерный анализ / Дж.-О. Ким, Ч.У. Мьюллер, У.Р. Клекка, М.С. Олдендерфер, Р.К. Блэшфилдж / Под ред. И.С. Енюкова / Пер. с англ. — М. : Финансы и статистика, 1989. — 215 с. 3. Классификация и кластер / Под ред. Дж. Вэн Райзина / Пер. с англ. — М. : Мир, 1980. — 389 с. 4. Жамбю М. Иерархический кластер-анализ и соответствия / Пер. с англ. — М. : Финансы и статистика, 1988. — 342 с. 5. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. — Киев : Наук. думка, 1987. — 262 с. 6. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознава- нию. — Киев : Наук. думка, 2004. — 545 с. 7. Киселева Е.М., Шор Н.З. Непрерывные задачи оптимального разбиения множеств: теория, алгоритмы, приложения. — Киев : Наук. думка, 2005. — 562 с. 8. Киселева Е.М., Жильцова А.А. Необходимые условия оптимальности для непрерывных за- дач разбиения множества в терминах теории функций множества // Проблемы управления и информатики. — 2008. — № 6. — С. 55–66. 9. Дзюбко С.И. Инвариантные конструкции разбиения и некоторые их приложения // Автома- тика и телемеханика. — 2002. — № 3. — С. 129–133. 10. Тимофеева Н.К. Один алгоритм оптимальной компоновки базовых элементов в корпуса интегральных микросхем // Алгоритмы и программы решения задач дискретной оптимиза- ции. — Киев : Ин-т кибернетики АН УССР, 1980. — С. 3–20. 11. Кириченко Н.Ф., Донченко В.С. Псевдообращение в задачах кластеризации // Кибернетика и системный анализ. — 2007. — № 4. — С. 73–92. Проблемы управления и информатики, 2009, № 5 99 12. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри- ческого проектирования. — Киев : Наук. думка, 1986. — 267 с. 13. Елькін О.Б. Математична модель та метод розв’язання задачі розбиття і трасування з урахуванням просторової форми області : Автореф. дис. ... канд. техн. наук. — Харків : Ін-т проблем машинобудування ім. А.М.Підгорного НАН України, 2008. — 19 с. 14. Тимофієва Н.К. Комбінаторика в розпізнаванні мовних сигналів // Мат. Х Міжнар. наук. конф. ім. акад. М. Кравчука. Київ, 13–15 травня 2004 р. — К. : Нац. техн. ун-т України «КПІ», 2004. — С. 528. 15. Тимофієва Н.К. Моделювання цільової функції та підкласи розв’язних задач у проблемі кластеризації // Оброблення сигналів і зображень та розпізнавання образів. ІХ Всеукр. міжнар. конф. Київ, 3–7 листопада 2008 р. — Київ, 2008. — С. 27–30. 16. Hatami P. An approximation algorithm for the total covering problem // Discuss. Math. Graph Theory. — 2007. — 27, N 3. — P. 553–558. 17. Kawasaki H.J. Duality theorem for a three-phase partition problem // Optimiz. Theory and Appl. — 2008. — 137, N 1. — P. 1–10. 18. Ceselli A., Righini G. An optimization algorithm for the ordered open-end bin-paсking problem // Oper. Res. — 2008. — 56, N 2. — P. 425–436. 19. Johnson N.L. Constructions of subgeometry partitions // Bull. Belg. Math. Soc. Simon Stevin. — 2008. — 15, N 3. — P. 437–453. 20. Рощин В.А., Семенова Н.В., Сергиенко И.В. Декомпозиционный подход к решению некото- рых задач целочисленного программирования с неточными данными // Журн. вычисл. ма- тематики и мат. физики. — 1990. — 30, № 5. — С. 786–791. 21. Семенова Н.В. Методы поиска гарантирующих и оптимистических решений задач цело- численной оптимизации в условиях неопределенности данных // Кибернетика и системный анализ. — 2007. — № 1. — С. 103–114. 22. Емец О.А., Роскладка А.А. О комбинаторной оптимизации в условиях неопределенности // Там же. — 2008. — № 5. — С. 35–44. 23. Тимофеева Н.К. О некоторых свойствах разбиений множества на подмножества // УСиМ. — 2002. — № 5. — С. 6–23. 24. Тимофеева Н.К. Зависимость целевой функции задач комбинаторной оптимизации от упо- рядочения комбинаторных конфигураций // Компьютерная математика. — 2005. — № 2. — С. 135–146. 25. Тимофеева Н.К. О некоторых особенностях построения математических моделей задач комбинаторной оптимизации // УСиМ. — 2004. — № 5. — С. 38–45. 26. Романовский И.В. Алгоритмы решения экспериментальных задач. — М. : Наука, 1977. — 352 с. Получено 23.06.2009 Статья представлена к публикации членом редколлегии Ф.Г. Гаращенко.
id	nasplib_isofts_kiev_ua-123456789-210616
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0572-2691
language	Russian
last_indexed	2025-12-17T12:04:21Z
publishDate	2009
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Тимофеева, Н.К. 2025-12-13T11:18:16Z 2009 О природе неопределенности и переменных критериях в задачах разбиения / Н.К. Тимофеева // Проблемы управления и информатики. — 2009. — № 5. — С. 88-99. — Бібліогр.: 26 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210616 519.14+519.816+519.863 10.1615/JAutomatInfScien.v41.i9.30 Показано, що ситуація невизначеності в задачах розбиття виникає внаслідок особливостей структури множини розбиттів n-елементної множини (аргумента цільової функції) на підмножини, структури вхідної інформації, способу моделювання цільової функції. Для виходу із цієї ситуації пропонується формулювати додаткові цільові функції та в процесі розв’язання задачі вводити змінні критерії. It is shown that a situation of uncertainty in the partition problems arises as a result of the special structure of a set partitioning an n-element set into subsets (argument of objective function), structure of input data, method of modeling of objective function. For a way out of this situation formulation of additional objective functions and introduction of variable criteria in the process of solving the problem are suggested. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации О природе неопределенности и переменных критериях в задачах разбиения Про природу невизначеності та змінні критерії в задачах розбиття On nature of uncertainty and variable criteria in the partition problems Article published earlier
spellingShingle	О природе неопределенности и переменных критериях в задачах разбиения Тимофеева, Н.К. Методы обработки информации
title	О природе неопределенности и переменных критериях в задачах разбиения
title_alt	Про природу невизначеності та змінні критерії в задачах розбиття On nature of uncertainty and variable criteria in the partition problems
title_full	О природе неопределенности и переменных критериях в задачах разбиения
title_fullStr	О природе неопределенности и переменных критериях в задачах разбиения
title_full_unstemmed	О природе неопределенности и переменных критериях в задачах разбиения
title_short	О природе неопределенности и переменных критериях в задачах разбиения
title_sort	о природе неопределенности и переменных критериях в задачах разбиения
topic	Методы обработки информации
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/210616
work_keys_str_mv	AT timofeevank oprirodeneopredelennostiiperemennyhkriteriâhvzadačahrazbieniâ AT timofeevank propriroduneviznačenostítazmínníkriteríívzadačahrozbittâ AT timofeevank onnatureofuncertaintyandvariablecriteriainthepartitionproblems

О природе неопределенности и переменных критериях в задачах разбиения

Institution

Similar Items