МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ЛИНЕЙНЫМИ ФУНКЦИЯМИ КРИТЕРИЕВ НА НЕЧЕТКОМ МНОЖЕСТВЕ АЛЬТЕРНАТИВ часть 1

МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ЛИНЕЙНЫМИ ФУНКЦИЯМИ КРИТЕРИЕВ НА НЕЧЕТКОМ МНОЖЕСТВЕ АЛЬТЕРНАТИВ

МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ЛИНЕЙНЫМИ ФУНКЦИЯМИ КРИТЕРИЕВ НА НЕЧЕТКОМ МНОЖЕСТВЕ АЛЬТЕРНАТИВ часть 1
МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ЛЕКСИКОГРАФИЧЕСКОЙ ОПТИМИЗАЦИИ С ЛИНЕЙНЫМИ ФУНКЦИЯМИ КРИТЕРИЕВ НА НЕЧЕТКОМ МНОЖЕСТВЕ АЛЬТЕРНАТИВ часть 2

Автор: Наталия Семенова, Людмила Колечкина, Алла Нагорная
Аннотация: Рассматривается многокритериальная комбинаторная задача лексикографической оптимизации на нечетком множестве альтернатив с линейными критериями. Исследуются свойства области допустимых решений. Излагается один из возможных подходов к решению многокритериальной комбинаторной задачи с линейными целевыми функциями на нечетком множестве альтернатив.
Ключевые слова: многокритериальная оптимизация, дискретная оптимизация, нечеткое комбинаторное множество, комбинаторное множество перестановок, Парето-оптимальные решения, слабо, строго эффективные решения, нечеткое множества альтернатив, нечеткое мультимножество, функция принадлежности.
ACM Classification Keywords: G2.1 Combinatorics (F2.2), G1.6 Optimization
Conference: The paper is selected from XVth International Conference “Knowledge-Dialogue-Solution” KDS-2 2009, Kyiv, Ukraine, October, 2009.

Введение
При решении многих прикладных задач довольно часто исходная информация для описания математических моделей задана нечетко. Такие ситуации отображают недостаток информации для решения задачи, так как при нечетких условиях и критериях становится проблемным принятие решения. При моделировании реальных задач нечеткость проявляется в форме описания функций и параметров, от которых они зависят.
Нечеткие множества широко используются в различных применениях искусственного интеллекта, теории распознавания образов, принятия решений и др. Во многих практических задачах исследования операций, проектирования сложных систем, возникает необходимость принятия решения с учетом нескольких критериев оптимальности. В то же время достаточно распространенными на практике являются задачи многокритериального выбора, в которых задано конечное множество альтернатив и альтернативы могут оцениваться как количественно, так и качественно. Особенность многокритериальных задач, как способа моделирования, состоит в том, что в условиях многокритериальности выбор наиболее целесообразного решения осуществляется из множества несравнимых альтернатив. Проблема нахождения этого множества имеет большое практическое и теоретическое значение. Кроме того, в реальных задачах экономики мощность множества альтернатив очень велика, что делает проблему принятия решения достаточно сложной. В работе [2] была дана математическая формулировка и приведено аксиоматическое обоснование известного еще с XIX в. принципа Эджворта? Парето для случая четкого отношения предпочтения лица, принимающего решение. Этот принцип является основополагающим при выборе наилучших решений в экономике и технике в тех случаях, когда приходится учитывать сразу несколько целевых функций (критериев). Выяснилось, что он не универсален, а справедлив лишь при решении определенного (хотя и достаточно широкого) класса задач многокритериального выбора. За пределами этого класса его применение рискованно или же вообще недопустимо.
В настоящей работе принцип Эджворта-Парето распространяется на более широкий класс задач многокритериального выбора, в которых множество возможных решений является нечетким.
Различным аспектам теории задач векторной оптимизации посвящены работы многих ученых [1-6]. Как известно, задачи комбинаторной оптимизации, в том числе многокритериальные, могут быть сведены к задачам целочисленного программирования, однако это не всегда оправдано, потому что при этом теряется возможность учета комбинаторных свойств задачи [1], следовательно является целесообразной разработка новых подходов решения задач комбинаторного типа на основе исследования свойств области допустимых решений.
В настоящее время достаточно важны модели, учитывающие нечеткие параметры, как в целевых функциях, так и в ограничениях, заданных на комбинаторных множествах.
В данной статье рассматривается многокритериальная задача с линейными целевыми функциями, а также ее лексикографическая постановка, на нечетко заданной комбинаторной области допустимых решений. Исследованы свойства нечетко заданного комбинаторного множества перестановок, являющегося допустимой областью задачи. Предложен подход к решению изученной многокритериальной задачи.

1. Предварительные сведения. Основные понятия и определения
Нечеткие подмножества отличаются от обычных, или четких множеств тем, что в нечетком подмножестве степень принадлежности элемента множеству может быть любым числом единичного интервала [0,1], а не только одним из двух значений элементов множества {0,1}, как в случае индикаторов обычных подмножеств. Это свойство нечетких подмножеств обеспечивает возможность теоретико–множественного представления реальных неточных понятий, в которых переход от непринадлежности к принадлежности происходит постепенно. Возможность формализации понятий такого типа оказалась очень полезной при разработке принципов искусственного интеллекта ЭВМ, моделирующих процессы мышления человека и др. Независимо от того, что использовать – нечеткие или четкие подмножества, определение степеней принадлежности опирается на некоторые субъективные критерии человека, принимающего решения. Однако если при определении четких подмножеств производится выбор одного из двух чисел – нуля или единицы, то для определения нечетких подмножеств возможности выбора степеней принадлежности намного разнообразнее. В ряде случаев определение подходящих значений степеней принадлежности элементов нечетких множеств приводит к значительным трудностям в работе с нечеткими понятиями.
В данной работе исследуется задача векторной оптимизации, заданная на комбинаторном множестве перестановок, следовательно, необходимо учесть то, что выпуклой оболочкой этого множества является общий перестановочный многогранник, множеством вершин которого есть рассматриваемое комбинаторное множество [6-8]. Изученные свойства комбинаторных множеств и их выпуклых оболочек дают возможность находить решение дискретной комбинаторной задачи как оптимизационной задачи на непрерывном допустимом множестве. На основании установленной взаимосвязи между многокритериальными задачами на комбинаторных множествах и оптимизационными задачами на непрерывном допустимом множестве, появляется возможность применять классические методы непрерывной оптимизации к решению векторных задач на различных комбинаторных множествах, а также развивать новые подходы их решения.
Определим, для дальнейшего изложения обобщение понятий n -выборки, мультимножества и комбинаторного множества перестановок на случай нечетко заданной информации.
Определение 1. Нечетким мультимножеством X, заданным на универсальном мультимножестве X, называется совокупность пар (x,? X ( x)), где x? X, а X ( x) – функция: X > [0,1], которая называется функцией принадлежности мультимножеству X. Значение X ( x) для конкретного x называется степенью принадлежности этого элемента нечеткому мультимножеству X.
Согласно определению, обычные множества образуют подкласс нечетких множеств. Над нечеткими множествами, так же как и над обычными множествами, выполняется ряд операций, таких как объединение, пересечение, декартово произведение, разность и др. Эти же операции имеют место и для нечетких мультимножеств.
Определение 2. Выпуклой комбинацией нечетких множеств множество A с функцией принадлежности вида n A1, A2 ,...An в nRn называется нечеткое? A (x) = ??i?i (x), где ?i? 0, i? Nn, ??i = 1. Нечеткий выпуклый многогранник вершин.
2.Постановка задачи i=1 ?nk ( A) i=1 также можно представить, как выпуклую комбинацию его Обычно под задачей математического программирования понимают задачу отыскания экстремума некоторой целевой функции на допустимом множестве альтернатив. С помощью целевой функции формально представляется одно из основных свойств альтернатив: ценность, полезность, стоимость и др. Нечеткость в постановке задачи математического программирования может содержаться как в описании множества альтернатив, так и в описании целевой функции. Различные формы описания исходной информации обусловливают существование различных формулировок задач нечеткого математического программирования: а) задача достижения нечетко поставленной цели при нечетких ограничениях; б) задача нечеткого математического программирования при нечетком множестве допустимых альтернатив; в) нечеткий вариант стандартной задачи математического программирования со «смягчением» целевой функции и / или ограничений, где вместо задачи оптимизации решается задача удовлетворения цели и соответствующие неравенства для целевой функции и ограничений могут нарушаться; г) задача оптимизации с нечеткими коэффициентами и др.
В данной статье исследуемая задача состоит в максимизации векторной функции F на нечетком евклидовом комбинаторном множестве X’.
Рассматривается многокритериальная задача комбинаторной оптимизации следующего вида: Z (F, X ): max {F ( x) | x? X’? Rn }, F ( x) = ( f1( x),..., fl ( x)), fi: Rn > R, i? Nl, X’? ?, X’? нечеткое подмножество множества X = vert ?nk ( A)? D, ?nk ( A) = conv Pnk ( A),Pnk ( A)? комбинаторное множество перестановок, D? Rn – выпуклый многогранник, нечеткое подмножество X’ = {x,? X’ ( x)}, где x? X, X’ ( x): X > [0,1] – функция принадлежности множеству X. X’ будем называть нечетким множеством альтернатив.
Под максимизацией будем понимать выбор нечеткого подмножества R нечеткого множества X’ которому отвечает наибольшее значение как векторной функции F, так и функции принадлежности? X’ ( x) нечеткому множеству альтернатив. Эти альтернативы в задачах многокритериальной оптимизации в зависимости от способа их сравнения называются эффективными (оптимальными по Парето), слабо эффективными (по Слейтеру), строго эффективными (по Смейлу) и соответственно обозначаются: P(F,X ), Sl (F,X ), Sm(F,X ). Напомним [14], что альтернатива x*? X’ называется эффективной, если не существует иной альтернативы x? X’ такой, что F ( x)? F ( x*), D ( x)?? D ( x*) и хотя бы одно неравенство строгое; слабо эффективной, если ?x? X’: F ( x) > F ( x*), и строго эффективной, если ?x? X’: x? x *, F ( x)? F ( x*). Из определений следует, что Sm(F, X’ )? P(F, X’ )? Sl (F, X’ ). Исходную задачу Z (F, X ) представим в виде (l +1) – критериальной задачи: F ( x) > max,? X’ ( x) > max, x? X.
Под решением задачи с нечетким множеством альтернатив понимаем нечеткое множество с функцией принадлежности: ?( x) = {? X’ (x) x? P(F, X’ ); 0 x? P(F, X’ )}.
Таким образом, нечеткое подмножество решений будет включать в себя те и только те альтернативы универсального множества X, которые дают значения векторной функции принадлежности? X’ ( x), x? X, не улучшаемые одновременно. F (x) и функции Следует отметить, что нечеткий вариант этой задачи означает, что ограничения смягчаются, то есть допускается возможность их нарушения с той или иной степенью.
Пусть P(?) — множество всех эффективных альтернатив (l +1) — критериальной задачи: yi > max, i? Nl,? D (x) > max, F (x, y) ??, x? X, y = ( y1,..., yl )? Y. Таким образом, нечеткое множество решений исходной задачи будет включать в себя те и только те альтернативы со степенью недоминированности не меньше?, которые будут эффективными как по оценкам альтернатив yi, i? Nl, так и по функции принадлежности? D (x) нечеткому множеству альтернатив. Выбор некоторой конкретной из них альтернативы осуществляется с помощью методов многокритериальной оптимизации. Более того, вместо задачи максимизации можно поставить задачу достижения некоторого наперед заданного значения функции цели, соответствующего удовлетворению исходной цели.
3.Подходы к решению задачи Нередко на практике теория оптимизации применяется к неточным моделям, где нет никаких оснований задавать коэффициенты в виде точно определенных чисел. Такое искусственное сужение априорной информации может привести к искажению конечных результатов. Разработка методов решения поставленной задачи Z (F, X ) в условиях нечеткой определенности предполагает знание и использование результатов операций нахождения суммы, произведения, минимума и максимума нечетких величин. При сравнении двух нечетких величин необходимо определение равенства этих величин. Под нечетким числом здесь будем понимать нечеткое множество с областью определения в виде интервала действительной оси R1. Множество всех нечетких чисел, определенных на R1, обозначим через R’1.Пусть x и y — два нечетких числа с носителями S x = (a1, a2 ) и S y = (a1, a2 ) соответственно; a2 > a1, b2 > b1; g: R1? R1 > R1 — некоторая функция. Тогда согласно принципу обобщения нечеткое число D = g ( x, y) определяется функцией принадлежности? D ( z) = sup min{? x (a),? y (b)}. (4) g (a,b)=z a?S x, b?S y Пусть? — одна из четырех арифметических операций: +, -,?, /;g (a, b) = a? b. Тогда формула (4) определяет результат арифметической операции? над нечеткими числами x и y. Если не двух, а n аргументов, то принцип обобщения формулируется аналогично (4). При сравнении двух нечетких величин необходимо определение равенства этих величин. g (?) — функция
Определение 4. Две нечетких величины (два числа) (x1, ?1( x1)) и (x2,? 2 ( x2 )) будем считать равными, если x1 = x2 и ?1( x1) =? 2 ( x2 ).
Определение 5. Если выполняется условие x1? x2, ?1( x1)? ?2 ( x2 ) и одно из этих неравенств строгое, то нечеткая величина (x1, ?1( x1)) больше нечеткой величины (x2,? 2 ( x2 )).
  • +2
  • 4 ноября 2009, 13:27
  • yxom

Комментарии (0)

RSS свернуть / развернуть

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.