Eng | Rus | Ukr | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Исследование операций
|
04.10.2008
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
9.3. ЗАДАЧИ НЕЧЕТКОГО МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯКлассификация и общая характеристика.Во многих случаях задачу принятия решений в общем виде можно описать множеством допустимых выборов (альтернатив) и заданным на этом множестве отношением предпочтения, которое отображает интересы лица, принимающего решение. Как правило, это отношение является бинарным, то есть позволяет сравнивать попарно лишь две альтернативы. В этом случае задача принятия решений заключается в выборе допустимой альтернативы, которая является лучшей среди всех альтернатив для заданного отношения предпочтения. Отношение предпочтения на множестве альтернатив можно описать двумя способами: 1) с помощью функции полезности (utility function); 2) в виде бинарного отношения предпочтения. Функция полезности обычно имеет вид отображения множества альтернатив на числовую ось. Не всякое отношение предпочтения и не на всяком множестве альтернатив можно описать функцией полезности. В некоторых случаях это отношение удается описать с помощью конечного набора функций полезности, и тогда соответствующие задачи принятия решений являются многокритериальными. Задачи принятия решений, в которых используются функции полезности, являются задачами математического программирования. Оптимальным решением в таких задачах является выбор допустимой альтернативы, на которой функция полезности принимает максимальное значения. Нечеткость в постановке задачи математического программирования может содержаться как при описании множества альтернатив, так и при описании функций полезности. Задачи, в которых нечетко описано множество альтернатив и (или) функции полезности, называют задачами нечеткого математического программирования [20, 26, 37]. Анализируя задачи НМП, можно выделить два разных подхода к их решению. При первом подходе, впервые предложенном Р.Беллманом и А.Заде [65], задача НМП формулируется как задача выполнения нечеткой цели при нечетких ограничениях, причем решение задается пересечением нечетких множеств цели и ограничений. При втором подходе предполагается, что решения должны выбираться подобно тому, как это делается в задачах многокритериальной оптимизации. Рассматриваются лишь такие решения (альтернативы), которые не доминируются строго никакими иными альтернативами, то есть выбираются эффективные альтернативы в понимании Парето. Такие решения используют аппарат нечетких отношений преимущества. Задача достижения нечетко определенной цели
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
0 |
0.1 |
0.4 |
0.8 |
1.0 |
0.7 |
0.4 |
0.2 |
0.1 |
0 |
|
0.3 |
0.6 |
0.7 |
1 |
0.9 |
0.8 |
0.5 |
0.3 |
0.2 |
0 |
|
0.2 |
0.4 |
0.6 |
0.7 |
0.9 |
1 |
0.8 |
0.6 |
0.4 |
0.2 |
Тогда для решения получаем функцию принадлежности , а решение интерпретируется так: должен быть близким 5 (табл. 9.3).
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
0 |
0.1 |
0.4 |
0.7 |
0.9 |
0.7 |
0.4 |
0.2 |
0.1 |
0 |
Это решение можно интерпретировать как нечетко сформулированную инструкцию. При таком представлении остается неопределенность, какую же альтернативу следует выбрать, то есть надо разрешить эту неопределенность. Существуют различные способы разрешения этой неопределенности. Наиболее распространенный из них, предложенный Л.Заде, состоит в выборе альтернативы, имеющей максимальную степень принадлежности нечеткому решению, то есть альтернатива определяется из условия:
.
Такие альтернативы называются максимизирующими.
Задача математического программирования в общем виде формулируется так:
при ограничениях ,
где - целевая функция, - ограничение.
При моделировании реальных задач в такой форме нечеткость может проявиться в форме нечеткого описания функций , и параметров, от которых они зависят, и самого множества . Подобное описание ситуации может отражать, например, недостаточность информации об этой ситуации или служить формой приближенного описания ситуации, достаточной для решения поставленной задачи.
Формы нечеткого описания бывают различными. Соответственно существуют разные классы задач нечеткого математического программирования. Приведем некоторые типичные классы задач НМП [20].
Задача 1. Максимизация заданной обычной функции на заданном нечетком множестве допустимых альтернатив .
Для решения этой задачи предлагается провести нормировку функции следующим образом:
,
причем рассматривается как функция принадлежности нечеткого множества цели ЛПР. Значение этой функции интерпретируется как степень достижения цели при выборе альтернативы . Это позволяет применить к решению указанной задачи подход Беллмана - Заде. Требуется найти такую альтернативу , для которой достигается
, (9.3.3).
Можно проверить, что задачу отыскания этой альтернативы можно сформулировать следующим образом:
при ограничениях: . (9.3.4)
Задача 2. Нечеткий вариант стандартной задачи математического программирования.
Пусть задана следующая задача НМП:
. (9.3.5)
Нечеткий вариант этой задачи получается если:
1) смягчить ограничения, то есть допустить возможность их нарушения с той или иной степенью;
2) вместо максимизации функции можно стремиться достичь некоторого заданного значения этой функции, причем различным отклонениям от следует приписывать различные степени допустимости. Эту задачу можно записать так:
, (9.3.6)
где знак означает нечеткое выполнение соответствующих неравенств.
Один из возможных подходов к формализации подобных нечетко сформулированных задач состоит в следующем. Пусть -заданная величина целевой функции , достижение которой считается достаточным для выполнения цели принятия решений, и пусть ЛПР задает два порога и такие, что неравенства означают сильное нарушение соответствующих неравенств . Тогда можно ввести следующие нечеткие множества цели и ограничений:
(9.3.7)
(9.3.8)
где - некоторые функции , описывающие степень выполнения соответствующих неравенств с точки зрения ЛПР. В результате исходная задача оказывается сформулированной в форме задачи достижения нечеткой цели и к ней можно применить подход Беллмана-Заде.
Задача 3. Нечетко описанная целевая функция, то есть задано отображение , где - универсальное множество альтернатив, - числовая ось.
Здесь функция при каждом фиксированном - это нечеткое описание оценки результата выбора альтернативы, то есть нечеткая оценка альтернативы . Кроме того, задано нечеткое множество допустимых альтернатив с функцией принадлежности . К такой постановке сводится весьма широкий класс задач НМП. Это наиболее известная постановка задачи НМП.
Задача 4. Задана обычная целевая функция и система ограничений , причем параметры в описаниях функций заданы в форме нечетких множеств. Например, для линейной функции имеют вид
,
где параметры являются элементами нечетких множеств с функциями принадлежности . Указанный класс задач можно свести к задачам типа 1 или 3.
Задача 5. Функции , заданы с точностью до нечетко определенных параметров , которые являются элементами нечетких множеств с заданными функциями принадлежности . Этот класс задач можно свести к задачам типа 3.