численные методы. Задача принятия решений общая постановка, примеры
 Скачать 1.64 Mb.
|
|
§ 4. Задача выбора Задача выбора, как показано в § 1, является частным случаем более общей задачи принятия решений  , когда исходное множество альтернатив  известно.Задача выбора называется простой, если ее решение  может быть найдено непосредственно (например, указано ЛПР). Для решения простых задач выбора не требуется использования специальных алгоритмов. В противном случае задачу выбора сводят к математической задаче выбора. Математическая задача выбора Будем считать, что ЛПР известны: – множество альтернатив,  – множество функций выбора, которые могут быть построены на ; дополнительные свойства функции выбора, которые позволяют сузить множество возможных функций выбора до  ;  – множество тех подмножеств множества , на которых известны значения функции выбора ( , где  – множество подмножеств ). Пара  задает описание функции С. Причем, случай  и  соответствует отсутствию информации о функции С, случай  соответствует полному описанию функции.Математической задачей выбора назовем тройку  , где – множество альтернатив;  ;  известны для всех  .Решением задачи является множество  . Задача разрешима, если  однозначно определяется по множеству  и значениям С на всех  . При  задача разрешима и ее решением является известное  . Ведем на множестве два следующих отношения эквивалентности  и  :1)    для всех ;2)  .Рассмотрим фактормножества множества по введенным отношениям:  ,  . Будем говорить, что фактормножество  вложено в  , если для любого класса эквивалентности  найдется класс эквивалентности  такой, что   .Справедлива следующая теорема. Теорема 3. Математическая задача выбора разрешима тогда и только тогда, когда фактормножество вложено в .Алгоритм 2 (алгоритм решения математической задачи выбора) 1. Сформировать множество  .Занумеровать все функции выбора, входящие в  :  . Если  , перейти к шагу 9. Иначе перейти к шагу 4.Положить  .Положить i=2. Если  , то перейти к шагу 8. Иначе – к шагу 9.Если  , то  , перейти к шагу 6. Иначе – к шагу 8.Останов. Множество A является решением задачи .Останов. Задача неразрешима.Задача выбора на основе скалярной и общей скалярной функции выбора Функция выбора С на называется общей скалярной функцией, если существует числовая функция  такая, что  , и скалярной, если  – инъективная функция, т.е.  при  .Функция выбора С является общей скалярной функцией тогда и только тогда, когда она порождена сильно транзитивным антирефлексивным бинарным отношением. Заметим, что функция , участвующая в определении общей скалярной и скалярной функции определена с точностью до строго положительного монотонного преобразования. Другими словами, если  – монотонно возрастающая функция и  ,  , то  , .Введем бинарное отношение  :  . Утверждение 1. Скалярная функция выбора совпадает с предпочтением по бинарному отношению  .Докажем справедливость утверждения, т.е. что выполнено равенство:  ,  , где  . ……………….Итак, пусть рассмотрим произвольное подмножество  . Докажем, что  Пусть  = . Тогда  для любого  . А следовательно,  не выполнено, тогда  , т.е.  . Обратное включение множеств  доказывается аналогично.Таким образом, если  – скалярная функция, то задача выбора сводится к отысканию . (4)Однако чаще функция  в явном виде не задана. В силу утверждения 1 в этом случае задача (4) является математической задачей выбора, в которой состоит из некоторых двухэлементных подмножеств, а  .Упражнения к § 4 Основные упражнения 1. Рассмотрим задачу выбора, в которой  . Известно, что  ,  и – нормальная функция выбора. Построить математическую задачу выбора. Является ли она разрешимой?2. Рассмотрим задачу выбора, в которой  . Известно, что ,  ,  ,  ,  ,  и – нормальная функция выбора. Построить математическую задачу выбора. Является ли она разрешимой?II. Дополнительные упражнения 1. Пусть , – множество функций выбора, являющихся объединением двух скалярных функций; – все двухэлементные подмножества . Показать, что математическая задача не является разрешимой. (Указание: рассмотреть следующие четыре скалярные функции выбора: ,  ,  ; ,  ,  ;  ,  ,  ; ,  ,  и  ,  ) |