Теория выбора
и принятия решений

DjVu

      ПРЕДИСЛОВИЕ
      Процессы принятия решений лежат в основе любой целенаправленной деятельности. В экономике они предшествуют созданию производственных и хозяйственных организаций, обеспечивают их оптимальное функционирование и взаимодействие-в научных исследованиях — позволяют выделить важнейшие научные проблемы, найти способы их изучения, предопределяют развитие экспериментальной базы и теоретического аппарата; при создании новой техники — составляют важный этап в проектировании машин, устройств, приборов, комплексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере — используются для организации функционирования и развития социальных процессов, их координации с хозяйственными и экономическими. Оптимальные (эффективные) решения позволяют достигать цели при минимальных затратах трудовых, материальных и сырьевых ресурсов. Вопросы принятия эффективных управленческих решений выделены как особо важные в материалах XXVI съезда КПСС. Таким образом, анализу и методам принятия эффективных решений уделяется большое внимание.
      Методы поиска оптимальных решений рассматривают в разделах классической математики, связанных с изучением экстремумов функций, в математическом программировании. Однако решение здесь — математический объект, основным свойством которого является то, что он доставляет экстремум заданной функции или функционалу. Зачастую оценка решения производится по одному аспекту или критерию. На практике решение нужно оценивать с различных точек зрения, учитывая физические (габариты, вес), экономические (стоимость, ресурсоемкость), технические (реализуемые функции) и другие аспекты. Это требует построения моделей оптимизации решений одновременно по нескольким аспектам или критериям. Такие модели разрабатывают в теории выбора и принятия решений. Здесь при постановке задачи уже не достаточно построить оптимизируемые функционалы. Требуется ввести принцип оптимальности, который определяет понятие оптимального решения. Поскольку оптимальность решения даже в одной и той же ситуации может пониматься по-разному, вид принципа оптимальности в моделях принятия решений заранее не фиксируют.
      Именно в этом состоят основные особенности задач принятия решений.
      Элементы теории выбора и принятия решений в той или иной форме включаются в. учебные программы по широкому кругу специальностей: прикладной математике, технической кибернетике, автоматизированным системам управления, экономической кибернетике, автоматизации проектирования и другим.
     
      Части I, II раскрывают сущность теории выбора и принятия решений и демонстрируют возможности использования ее результатов. Часть III показывает возможность объединения аппарата теории выбора и принятия решений с классическим аппаратом оптимизации на примере решения многокритериальных задач оптимального управления.
      Уровень изложения материада предполагает знакомство с математическими дисциплинами в объеме программы технических вузов. Специальные понятия и приемы поясняются там, где это необходимо. Упражнения повышенной трудности отмечены звездочкой; особо трудные упражнения — двумя звездочками. Список литературы не является исчерпывающим, а содержит только источники на русском языке. В конце каждой главы даны ссылки на рекомендуемую литературу из общего списка. Не все приводимые факты сопровождаются доказательствами; некоторые доказательства опущены, поскольку они выходят за рамки пособия; простые доказательства предлагаются в качестве упражнений.
      В каждой главе использована своя нумерация формул, рисунков, утверждений, теорем, без указания номера части и главы. При ссылках на результат из другой главы той же части применяется двойная нумерация, где первая цифра указывает номер главы. При ссылке на результаты из другой части используется тройная нумерация. Например, формула (II.5.27) обозначает формулу (27) из главы 5 части II.
      Пользоваться пособием следует по-разному, в зависимости от цели читателя. Начинать во всех случаях нужно с введения. Общее представление о задачах оптимизации, выбора и принятия решений можно получить, прочитав §§ 1.1.1, 1.1.6, 1.2.1, 1.2.2,
      1.3.1, 1.5.1, II.3.1, И.4.1, II.4.2; о многокритериальных задачах оптимального управления — прочита⧧ 1.1.1, 1.1.6, 1.3.1, III.1.1, III.1.2, III.2.1, III.2.2, 111.3.1, III.3.2, III.4.1, III.4.2; о прикладных задачах оптимизации и оптимального управления — прочитав §§ 1.1.1, 1.1.6, II.4.1, И.4.2, II.7.1, II.7.2, III.1.1 111.4.1, III.5.1 — III.5.5. При таком чтении доказательства утверждений и теорем можно опустить, сосредоточив внимание на постановках задач, их свойствах, идеях решения. В случае появления понятий, не определенных в указанных параграфах, их следует найти, воспользовавшись предметным указателем, приведенным в конце пособия.
      Для более детального знакомства с теорией выбора следует прочесть всю часть I, а также §§ II.4.1, II.4.2 и главы II.5 — II.7, с теорией многокритериального оптимального управления — главы 1.1, 1.3, II.4 и всю часть III. Читателю, интересующемуся алгоритмами, достаточно прочитать по алгоритмам подготовки решений главу II.3, используя в качестве справочного материал части I и глав II.1 и II.2; по алгоритмам выбора — главы II.4 и II.6, используя в качестве справочного материал части I.
      Для выработки систематического навыка постановки, исследования и решения рассматриваемых задач необходимо изучение всего материала пособия и выполнение предложенных в нем упражнений (кроме наиболее сложных).
      Пособие рассчитано в первую очередь на студентов старших курсов, аспирантов и преподавателей вузов. Теоретические разделы полезны для специалистов по системному анализу и исследованию операций. Прикладные разделы могут представить|интерес для консультантов и разработчиков алгоритмов.
      Авторы глубоко благодарны члену-корреспонденту АН СССР С. С. Шаталину, сотрудникам возглавляемой им кафедры математических методов анализа экономики МГУ и профессору Ю. П. Иванилову за высказанные замечания и рекомендации, которые позволили улучшить состав, структуру и методическую целостность настоящего пособия, а также коллегам по работе С. С. Порошину и. А. В. Щербакову за помощь при подготовке рукописи.
      И. М. Макаров, Т. М. Виноградская, А. А. Рубчинский, В. Б. Соколов
     
      ВВЕДЕНИЕ
      Теория выбора и принятия решений исследует математические модели процессов принятия решений и их свойства. Основной в ней является задача принятия решений, которая соответствует широкому кругу практических ситуаций. Приведем примеры.
      На предприятии освободилась должность главного инженера. Задача директора — назначить главного инженера.
      Строительному тресту поручено выполнить комплекс работ. Задача управляющего трестом — распределить работы по строительным управлениям.
      Транспортному агентству необходимо перевезти заданный объем грузов. Задача диспетчера — определить маршрут перевозок.
      В рассмотренных и других сходных ситуациях общим является следующее. Имеется множество вариантов (кандидатов на должность, назначений работ, маршрутов); нужно выделить и» него некоторое подмножество, в частном случае — один вариант. Выделение требуемых вариантов производится на основе представления директора, управляющего, диспетчера об их качестве. Представление о качестве вариантов характеризуют принципом оптимальности.
      Указанные элементы — множество вариантов и принцип оптимальности — позволяют ввести следующие понятия. Задачей принятия решений назовем пару <2, ОП>, где|2 — множество вариантов, ОП — принцип оптимальности; решением задачи <2, ОП> — множество 20П <= 2, полученное с помощью [принципа оптимальности ОП.
      Отсутствие хотя бы одного из указанных элементов лишает смысла задачу в целом. Если нет множества 2, то выделять решение 20П не из чего, Если нет принципа оптимальности, та найти решение невозможно.
      Математическим выражением принципа оптимальности ОП служит функция выбора Соп. Она сопоставляет любому подмножеству X = Q его часть Con (X). Решением 20П исходной задачи является множество С0П (2).
      Задачи принятия решений различают в зависимости от имеющейся информации о множестве 2 и принципе оптимальности ОП. В общей задаче принятия решений как 2, так и- ОП могут быть неизвестными. Информацию, необходимую для выделения 20П, получают в процессе решения. Задачу с известным 2 назовем задачей выбора, задачу с известными 2 и ОП — общей задачей оптимизации. Таким образом, задача выбора и задача оптимизации являются частными случаями общей задачи принятия решений. Особенность развиваемого здесь подхода к решению задачи выбора состоит в том, что он в общем случае не требует полного восстановления принципа оптимальности, а позволяет ограничиться только информацией, достаточной для выделения 20П. Общая задача оптимизации может не предполагать максимизации одной или нескольких числовых функций. Ее смысл состоит в выделении множества лучших элементов, т. е. в вычислении значения С0П (2) при заданных 2 и С Если Соп — скалярная функция выбора на множестве 2 то получаем обычную оптимизационную задачу.
      Элементы множества 2 называют альтернативами или вариан тами Принцип оптимальности задает понятие лучших альтерна тив лучшими считают альтернативы, принадлежащие Соп(2).
      В практических задачах альтернативы обладают многими свойствами оказывающими влияние на решение. Пусть некоторое свойство альтернатив из 2 выражается числом, т. е. существует отображение ф: 2- Тогда такое свойство называют критерием, а число ф (х) — оценкой альтернативы х по критерию. Одновременный учет отдельных свойств может быть затруднительным. При этом выделяют группы свойств, которые агрегируют в виде аспектов. Аспект представляет собой сложное свойство альтернатив которое одновременно учитывает все свойства, входящие в соответствующую группу. В частном случае аспект может являться критерием. (...)
      определении маршрута перевозок альтернативами являются оазличные маршруты. Диспетчер учитывает следующие свойства поотяжениость, загрузка, энергоемкость, безопасность стоимость техническое обслуживание и ряд других.Техническое обслуживание на данном маршруте зависит от числа и расположения станций обслуживания, их мощности, загрузки и сроков выполнения оемонтных работ. Таким образом, техническое обслуживание является аспектом, агрегирующим указанные свойства. Стоимость маршрута складывается из стоимости топлива, стоимости обслуживания транспортных средств, зарплаты водителей за время пути и других составляющих, т. е. стоимость также является аспектом. Однако возможность вычисления стоимости указывает на то, что данный аспект можно рассматривать как критерий. Протяженность маршрута измеряется в километрах, т. е. выражается числом и поэтому является критерием.
      Процесс решения задачи <Q, ОП> организуют по следующей схеме: формируют множество Q, т. е. подготавливают альтернативы, а затем решают задачу выбора. При назначении на должность сначала готовят список кандидатов, а затем назначают лицо из этого списка. В процессе формирования множества Q используют условия возможности и допустимости альтернатив, которые определяются конкретными ограничениями задачи. При этом считают известным универсальное множество Q всех мыслимых альтернатив. Задача формирования Q является задачей выбора <Qy, ОПх>, где ОПх — принцип оптимальности, выражающий условия допустимости альтернатив. Множество Й=С0П1(Ц,), полученное в результате решения указанной задачи выбора, называют исходным множеством альтернатив (ИМА). При назначении на должность в качестве Q рассматривают всех специалистов. Условия допустимости определяются конкретными обязанностями, предусмотренными должностью, зарплатой и другими факторами.
      Итак, общая задача принятия решений сводится к решению двух последовательных задач выбора. В процессе решения этой задачи участвуют: лицо, принимающее решение, эксперты, консультанты.
      Лицом, принимающим решения (ЛПР), называют человека, имеющего цель, которая служит мотивом постановки задачи и поиска ее решения. ЛПР, являющееся компетентным специалистом в своей области и обладающее опытом деятельности в ней, наделено необходимыми полномочиями и несет ответственность за принятое решение. В задаче принятия решений основная функция ЛПР состоит в выделении 20п. В рассматриваемых процедурах принятия решений ЛПР дает информацию о принципе оптимальности.
      Экспертом (Э) называют специалиста, имеющего информацию о рассматриваемой задаче, но не несущего непосредственной ответственности за результат ее решения. Эксперт дает оценки альтернатив, необходимые для формирования ИМА и решения задачи выбора.
      Консультантом *) (К) называют специалиста по теории выбора и принятия решений. Консультант разрабатывает модель исходной задачи, процедуру принятия решения, организует работу ЛПР и экспертов при поиске решения.
      В простейших случаях задачу <Q, ОП> решает непосредственно ЛПР без использования специальных процедур. Однако часто
      *) Консультанты называются также исследователями, аналитиками, членами рабочей группы и др.
      требуются математические модели и методы, которые помогают ЛПР получать обоснованные эффективные решения. Изложению теории построения таких моделей и методов посвящено настоящее пособие.
      - Как и в других случаях, прикладные результаты, теории выбора и принятия решений имеют вид алгоритмов решения исследуемых задач. Часть приводимых далее алгоритмов может быть реализована вручную. В общем случае реализация алгоритмов предусматривает использование ЭВМ, оснащенных терминалами и соответствующим математическим обеспечением для диалогового режима работы.
      Алгоритмы, которые рассматриваются в части II настоящего пособия, могут быть использованы для" построения диалоговых систем принятия решений широкого назначения, алгоритмы из части III — для построения специализированных диалоговых систем решения задач управления.
     
      ЧАСТЬ I
      ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ВЫБОРА АЛЬТЕРНАТИВ
      В части I рассмотрен математический аппарат, который позволяет формализовать понятия лучшей альтернативы и сравнения альтернатив в задачах принятия решений. Аппарат рассчитан на использование в условиях, когда отсутствует единое понятие лучшей альтернативы (которое всегда присутствует в математических задачах оптимизации), и позволяет изменять содержание понятия оптимальности в зависимости от условий конкретной задачи. При этом в главах 1, 2 будут описаны общие конструкции (бинарные отношения и функции выбора); в главах 3, 4 — конструкции в критериальном пространстве; в главе 5 — взаимосвязи общих и частных конструкций в виде соответствующих декомпозиций.
     
      Г л а в а 1 БИНАРНЫЕ ОТНОШЕНИЯ
      Простейшая ситуация, которая позволяет сделать обоснованный выбор из нескольких объектов, возникает, когда задан один «критерий качества», позволяющий сравнить любые два объекта, четко указать, какой из них лучше, и выбрать тот (или те), на котором этот критерий достигает максимального значения (подробнее об этом см. § 2.5). Однако в большинстве реальных ситуаций выделить один такой критерий не удается; более того,часто вообще трудно выделить критерии.Тем не менее для некоторых пар объектов можно указать, какой из объектов пары лучше (предпочтительней) другого. В таких случаях говорят, что эти два объекта находятся в бинарном отношении. Понятие бинарного отношения позволяет формализовать операции попарного сравнения. Поэтому оно широко используется в теории выбора. В § 1 даны примеры и определение бинарных отношений; в § 2 рассмотрены методы задания отношений; в § 3 введены операции над отношениями; в § 4 описаны свойства отношений; в § 5 — основные классы отношений; в § 6 — понятие оптимума по отношению.
      1. Понятие бинарного отношения
      Что такое отношение, "проще всего пояснить примерами. Рассмотрим суждения, которые выражают взаимосвязи между некоторыми, объектами: «Иван — брат Петра»; «Татьяна старше Александра»; «Киев южнее Москвы»; «Железо тяжелее воды»; «Слово «ночь» и слово «день» содержат одинаковое число букв». Эти пять предложений выражают отношения разного типа. Однако можно заметить сходство в характере отношений, утверждаемых первым и пятым предложениями. Они говорят о том, что некие два объекта принадлежат общему классу: сыновей общих родителей, слов с фиксированным числом букв. Второе, третье и четвертое отношения имеют то общее, что выражают некоторый порядок объектов в системе.
      В дальнейшем эта разница между отношениями того и другого типа будет четко определена. Первый и пятый пример — это отношения эквивалентности, определяющие разбиения множества объектов на классы подобных друг другу. Остальные три примера — это отношения порядка, устанавливающие относительное расположение объектов в системе.
      Важно обратить внимание на тот факт, что во всех пяти примерах четко выделяются названия объектов (Иван, Киев и т. д.) и названия отношений (брат, старше, южнее и др.). Если вместо названия данного объекта подставить в предложение название другого объекта, то возможны следующие ситуации: 1) отношение опять будет выполнено; 2) отношение перестанет выполняться; 3) отношение потеряет смысл. Так, если в четвертое предложение вместо Олова «железо» подставить слово «свинец», то суждение останется справедливым. Если в третье предложение вместо слова «Москва» подставить «Ашхабад», то оно перестанет быть верным. Если же в третье предложение вместо слова «Москва» подставить «железо», то суждение потеряет смысл. В отличие от первых четырех, в пятое предложение можно подставить любые слова, поскольку для любого слова имеет смысл говорить о числе букв. Здесь сама форма суждения ограничивает класс объектов — объектами отношения могут быть только слова.
      Итак, говорить об отношении можно только тогда, когда мы умеем выделять множество объектов, на которых это отношение определено. Отношение может быть определено не только для пар объектов, но и для троек, четверок и т. д. Например, отношение «составлять экипаж лодки-восьмерки» выполняется для некоторых групп из восьми людей. Это отношение следует отличать от отношения «входить в экипаж одной и той же лодки-восьмерки», определенного для пар людей. Пример трехместных (или тернарных) отношений дают алгебраические операции. Отношение «образовывать произведение» имеет смысл для троек чисел <х, у, z> и выполняется в том случае, когда
      Мы будем рассматривать бинарные отношения, т. е. отношения, которые могут выполняться (или не выполняться) между двумя объектами из одного и того же множества. Поэтому в дальнейшем будем говорить об отношениях, имея в виду только бинарные отношения.