Многокритериальные решения при объективных моделях. (Лекция 3) презентация

решения: сколько строить ракет?
5. Разные типы проблем 6. Два пространства 7. Многокритериальный анализ экономической политики 8. Две трудности для ЛПР 9. Исследование решений на множестве Э-П 10. Постановка многокритериальной задачи линейного программирования 11. Человеко-машинные процедуры 12. Весовые коэффициенты важности критериев 13. Классификация ЧМП 14. Прямые человеко-машинные процедуры 15. Процедуры оценки векторов 16. Процедуры поиска удовлетворительных значений критериев 17. Пример применения метода STEM: как управлять персоналом

Исследование операций - сложившаяся научная дисциплина, хорошо известная в современном мире.
Как определяет Е. С. Вентцель [1], под исследованием операций понимают применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности.
Основными этапами решения любой задачи в исследовании операций являются:
1) построение модели;
2) выбор критерия оптимальности;
3) нахождение оптимального решения.
Для подхода исследования операций характерны следующие особенности.
Используемые модели носят объективный характер.
Построение моделей рассматривается в рамках исследования операций как средство отражения объективно существующей реальности.
Когда модель, правильно отражающая действительность, найдена, критерий оптимальности установлен, оптимальное решение может быть получено единственно возможным образом.

Когда модель, правильно отражающая действительность, найдена, критерий оптимальности установлен, оптимальное решение может быть получено единственно возможным образом.
2. Руководитель получает научно обоснованное решение. По заказу руководителя аналитик исследует организацию, внешнюю среду и пытается построить адекватную модель. В этой работе сам ЛПР чаще всего не нужен.
3. Существует объективный критерий успехов в применении методов исследования операций. Если проблема, требующая решения, ясна и критерий определен, то аналитический метод сразу показывает, насколько новое решение лучше старого.

пассажиров по различным маршрутам. Руководство компании определяет, какие самолеты (по вместительности) и сколько самолетов должны обслуживать различные маршруты. Считается, что известны потоки пассажиров между разными городами и общее число имеющихся самолетов различного типа. Требуется распределить самолеты по маршрутам так, чтобы минимизировать расходы на их обслуживание.
Задача о назначениях. Предполагается, что необходимо распределить заданное число работ среди исполнителей так, чтобы каждый исполнитель выполнял одну работу. Стоимость выполнения каждой из работ каждым исполнителем известна. Нужно распределить работы так, чтобы суммарная стоимость их выполнения была минимальной. Словесному описанию этих двух задач соответствует четкое математическое описание, представляющее собой математическую модель.

Рассмотрим описанную выше обобщенную транспортную задачу. Добавим к критерию минимальных расходов на обслуживание самолетов вполне естественные критерии максимума прибыли и максимума комфорта для пассажиров. Если есть три критерия, то необходимо согласовать их. Какое соотношение между оценками по критериям является наилучшим? Нужна дополнительная информация, которая может быть получена только от руководства авиакомпании.
Обратимся теперь к задаче о назначениях. Возьмем часто встречающийся случай, когда работы неодинаковы по своей важности, а исполнители различаются по качеству выполняемой работы [3]. Тогда к приведенному выше критерию минимальной стоимости можно добавить критерий качественного выполнения наиболее важных работ. Если есть уже два критерия, по которым следует оценивать качество распределения исполнителей по работам, то необходимо как-то согласовать их.
Какое отклонение от минимума стоимости оправдывает высококачественное выполнение важных работ? Ответ на этот вопрос не вытекает из сформированной модели. Этот ответ вообще не может быть получен объективным образом. Информация о компромиссе может быть дана людьми, принимающими решения, на основе их опыта и интуиции. Эти и многие им подобные задачи имеют следующую характерную особенность: модель, описывающая множество допустимых решений, объективна, но качество решения оценивается по многим критериям.

принятию решений при двух критериях является метод «стоимость—эффективность». Он был разработан в конце 50-х годов в США для решения военных задач. В годы ракетно-ядерной гонки США — СССР одной из основных была задача о достаточности системы нападения для преодоления защиты потенциального противника.
Метод «стоимость—эффективность» состоит из трех основных этапов:
1) построения модели эффективности;
2) построения модели стоимости;
3) синтеза оценок стоимости и эффективности.
Пример типичной модели, используемой в методе «стоимость— эффективность» для анализа вариантов построения военно-технических систем. Модель состоит из двух частей — модели стоимости и модели эффективности. Эти модели используются для выбора военной системы с определенным числом ракет. Модель стоимости представляет зависимость общей стоимости от количества ракет, а модель эффективности — зависимость вероятности поражения целей от количества ракет. Обе модели в данном случае можно рассматривать как объективные: они строятся на базе фактических данных, надежного статистического материала. Однако выходные параметры этих моделей не объединяются посредством заданной зависимости; используется суждение руководителя, который определяет предельные значения стоимости, необходимые значения эффективности.

как они направлены на принципиально разные проблемы принятия решений, существующие в окружающем нас реальном мире. Эти принципиальные различия стремились подчеркнуть авторы множества классификаций проблем принятия решений.
Так, в известной классификации, предложенной в 1958 г. в статье Г. Саймона и А. Ньюэлла [5], выделяются так называемые хорошо и слабоструктуризованные проблемы.
Хорошо структуризованные, или количественно сформулированные проблемы — те, в которых существенные зависимости выяснены настолько хорошо, что могут быть выражены в числах или символах, получающих в конце концов численные оценки.
Слабоструктуризованные, или смешанные проблемы — те, которые содержат как качественные, так и количественные элементы, причем качественные, малоизвестные и неопределенные стороны проблем имеют тенденцию доминировать.
Можно сказать, что типичные проблемы исследования операций являются хорошо структуризованными.
По-иному обстоит дело в многокритериальных задачах. Здесь часть информации, необходимой для полного и однозначного определения требований к решению, принципиально отсутствует. Исследователь часто может определить основные переменные, установить связи между ними, т. е. построить модель, адекватно отражающую ситуацию. Но зависимости между критериями вообще не могут быть определены на основе объективной информации, имеющейся в распоряжении исследователя.
Типичными неструктуризованными проблемами являются проблема выбора профессии, проблема выбора места работы и многие другие проблемы выбора. Слабоструктуризованные и неструктуризованные проблемы исследуются в рамках научного направления, называемого принятием решений при многих критериях.

Решение теперь можно назвать субъективным, хотя в процессе решения используются объективные модели. Характерной особенностью многокритериальных задач с объективными моделями является одновременное рассмотрение двух пространств - пространства переменных, используемых при построении модели, и пространства критериев.
Приведем иллюстративный пример: построим нарочито простую модель с двумя параметрами и двумя критериями. Из множества переменных, описывающих экономическую систему современного государства, выберем два: х\ — увеличение объема денежной массы; хг — увеличение количества рабочих мест.
Предположим, что определенное количество рабочих мест может быть создано без увеличения объема денежной массы, но дальнейшее их увеличение пропорционально объему денежной массы. Введем два критерия: Ci — уменьшение безработицы (в %); Сг - увеличение ВНП (в %). Заметим, что при одном критерии оптимальное решение очевидно. При большом числе переменных и одном критерии решение может быть найдено при помощи стандартных программ линейного программирования.
Пусть критерии связаны с переменными следующими зависимостями: Ci= 0,1л:, + 0,9x2; С2= 0,5xi + 0,5x2. Эти зависимости позволяют построить допустимую область изменения значений критериев S при изменении переменных. Область S зависит от уравнений связи между переменными и критериями. В реальных задачах число переменных велико (до десятков тысяч), а число критериев невелико (обычно не более 10). ЛПР работает с критериями, определяя свои требования к качеству решения и анализируя область S. Отметим еще раз, что область S появляется только в многокритериальных задачах.

построенной в начале 70-х годов.
Эта модель представляет собой совокупность линейных уравнений и ограничений. Некоторые переменные в модели были управляющими, т. е. могли быть изменены ЛПР. При определенных значениях управляющих переменных получаем одно из возможных решений.
Качество решений оценивалось по четырем критериям: Ci - увеличение валового национального продукта (в %); С2 - уменьшение инфляции (в %); Сз - уменьшение безработицы (в %); С4 - уменьшение дефицита внешней торговли (млрд финских марок).
Используя специальные человеко-машинные процедуры (см. далее), несколько ЛПР получали при помощи макроэкономической модели различные варианты экономической политики. Наилучшие значения по всем критериям одновременно не достижимы.
Модель, т. е. совокупность зависимостей между многочисленными переменными, описывающими экономику Финляндии, не позволяет получить такое решение. Это означает, что соответствующая точка лежит за пределами области допустимых значений. Действительно, первый вариант дает минимальное значение инфляции, но отрицательный прирост ВНП и большую безработицу. Второй и третий варианты допускают большую инфляцию. Они приводят к росту ВНП, но вырастает и дефицит внешней торговли. Эти противоречия отражают типичный характер вариантов многокритериальных решений. Для окончательного выбора нужен компромисс: приходится чем-то пожертвовать, чтобы что-то получить.

хорошие значения по критериям достижимы одновременно. Сделать это совсем не просто. В отличие от иллюстративного примера, число переменных, описывающих область D допустимых значений, равно сотням и тысячам. Получая каким-то из способов (см. далее) решение задачи, ЛПР видит соотношения между критериями.
Для поведения ЛПР типичны попытки достичь «всего сразу (т. е. получить наилучшие значения по всем критериям одновременно). Результаты таких попыток позволяют понять, чего можно достичь и чего нельзя.
Наряду с этим ЛПР вырабатывает компромисс между оценками по критериям, определяя желательное для него отношение между ними в точке решения. Выработка такого компромисса достигается тоже путем проб, ошибок и затрат времени.
На первых этапах решения ЛПР обычно стремится к идеальному результату, но потом, с опытом, его притязания становятся более реалистичными.

построения пространства Э-П и организации работы ЛПР на этом множестве.
Из современных направлений исследований, идущих по этому пути, необходимо выделить два подхода.
Первый из них связан с визуализацией множества Э-П и предоставлением ЛПР возможности проводить анализ на плоскостях пар критериев при фиксированных значениях других критериев. Этот подход получил название метода достижимых целей [13].
Другой подход применяется в тех случаях, когда ЛПР может восстановить по совокупности критериальных оценок, а также по другим параметрам целостный облик альтернативы. Эта ситуация характерна обычно для деятельности конструктора. Предъявление решений, находящихся на множестве Э-П, помогает конструктору в поиске новых эффективных конструкций механизмов и машин [14 ].

ЛПР стали ясны, можно сформулировать многокритериальную задачу линейного программирования.
Дано: область D допустимых значений переменных, определяемая совокупностью линейных равенств и неравенств;
критерии Ci, оценивающие качество решения. Т
ребуется: найти решение X в области D, при котором достигаются наиболее приемлемые значения по всем критериям.
Иначе говоря, нужно найти такие критериальные оценки, при которых достигается максимальное значение априори неизвестной функции полезности ЛПР. Эта задача решается с помощью человеко-машинных процедур.

наилучшего решения, являются человеко-машинные процедуры (ЧМП), представляющие собой процедуры общения ЛПР и компьютера.
Они состоят из совокупности шагов, каждый из которых включает в себя фазу анализа, выполняемого ЛПР, и фазу расчетов, выполняемых компьютером.
Различные ЧМП отличаются друг от друга содержанием и способом выполнения каждой из фаз. Первые из разработанных ЧМП основаны на использовании информации об относительной важности критериев

Фаза расчетов (компьютер):
• используя полученную от ЛПР на предыдущем шаге информацию, проводит дополнительные расчеты;
• вычисляет решение, соответствующее последней информации ЛПР;
• вырабатывает вспомогательную информацию для ЛПР.
Фаза анализа (ЛПР):
• оценивая предъявленное решение (или совокупность решений), определяет, является ли решение (одно из решений) приемлемым; если да, то ЧМП окончена; в противном случае ЛПР анализирует вспомогательную информацию;
• сообщает дополнительную информацию, с помощью которой компьютер вычисляет новое решение. Существует большое количество ЧМП [3], [7].

критериев в один с помощью так называемых весовых коэффициентов важности критериев. Идея такого объединения состоит в том, что ЛПР назначает числа (часто по численной шкале 1-100), представляющие для него ценность рассматриваемого критерия.
Считается, что ЛПР может назначить такие числа. Далее, весовые коэффициенты нормируются на основе условия (2). Существует лемма [8], утверждающая, что для линейной задачи любое эффективное, находящееся на множестве Э—П решение может быть представлено в виде (1), т. е. в виде весов, умноженных на частные критерии. Следовательно, формально задача сводится к нахождению весов.
Возникла идея, что эти веса можно получить от ЛПР оперативно.
Если ЛПР затрудняется в начале процесса решения (до изучения области D) сразу назвать эти веса, то можно построить ЧМП следующего содержания: ЛПР назначает первоначальные веса, смотрит на решение и корректирует веса до получения удовлетворительного результата.

получаемой от ЛПР на фазе анализа.
Первая группа ЧМП - прямые ЧМП, в которых ЛПР непосредственно назначает веса критериев и корректирует их на основе полученных решений.
Для второй группы ЧМП задача ЛПР состоит в сравнении многокритериальных решений. Эта группа называется ЧМП оценки векторов.
Третья группа требует от ЛПР наложения ограничений на значения критериев и, следовательно, на область допустимых значений. ЧМП этой группы называются ЧМП поиска удовлетворительных решений.
Перед тем как перейти к рассмотрению ЧМП каждой группы, следует указать на общие предварительные этапы, встречающиеся во многих ЧМП. Вектор таких (недостижимых одновременно) значений помогает ЛПР оценить пределы возможного.

может искать наилучшее решение путем непосредственного назначения ряда параметров (например, весов критериев) и сравнения получающихся решений.
В качестве примера прямых ЧМП рассмотрим процедуру SIGMOP (последовательный генератор информации для многоцелевых задач [9]).
В ней ЛПР пытается найти хорошее решение путем назначения весов критериев (wi) и уровней допустимых значений по всем критериям одновременно (Ci>ii).
Далее на фазе расчетов компьютер определяет новую область D допустимых значений переменных и находит в ней значение глобального критерия (1), а также всех отдельных критериев. Значения всех критериев, не удовлетворяющих условиям, наложенным ранее, предъявляются ЛПР.
После этого ЛПР меняет веса и ограничения в любой последовательности до тех пор, пока процедура не даст ему приемлемого решения.
Если критериев мало (два-три), то данная процедура может быть достаточно удобной. Однако при возрастании числа критериев для ЛПР становится все сложнее оценить влияние на получаемые решения каждого из весов и каждого из ограничений. Поэтому, количество прямых ЧМП сравнительно невелико.

может непосредственно сравнивать решения, предъявляемые ему в виде векторов в критериальном пространстве, и систематически искать в этом пространстве наилучший вектор.
Одной из наиболее известных ЧМП оценки векторов является процедура Дайера-Джиофриона (Д—Д) [10]. Она начинается с выбора какой-либо точки в критериальном пространстве.
В этой точке ЛПР определяет градиент глобальной целевой функции. Один из критериев считается опорным. Берется небольшое изменение значения этого критерия (в сторону улучшения) от начального. Перед ЛПР ставятся вопросы типа: какое изменение по иному критерию эквивалентно заданному изменению опорного критерия? Ответы ЛПР определяют вектор (направление), вдоль которого изменение глобального критерия будет наиболее эффективным.
Вдоль этого направления делается шаг определенной длины значения и получаются новые значения по всем критериям. Совокупность этих значений (вектор) предъявляется ЛПР вместе с первоначальным решением (соответствующим начальной точке). Далее перед ЛПР ставится вопрос: какое из решений лучше? Если лучше новое решение (назовем его Yi), то делается еще шаг вдоль этого же направления и вычисляется решение Уг. Далее Yi и Y2 предъявляются ЛПР. Если Y2 лучше, то делается еще шаг в прежнем направлении, и т. д. Если Y2 лучше, чем Yi , то в точке Y2 определяется новый градиент (направление) изменения глобальной целевой функции и т. д.
Процедура заканчивается, если ЛПР признает очередное решение вполне для него удовлетворительным. В отличие от прямых методов в ЧМП Д-Д наблюдается систематический поиск, помогающий ЛПР выбрать наилучшее решение. Уязвимым местом ЧМП оценки векторов является предположение, что ЛПР может безошибочно определять градиент целевой функции. Отмечалось, что, работая с малыми приращениями критериев, ЛПР будет постоянно совершать ошибки.

поиска наилучшего решения. Однако такой поиск осуществляется по-иному: в порядке очереди определяется приемлемое значение по каждому из критериев.
Примером ЧМП поиска удовлетворительных значений критериев служит процедура STEM - одна из первых ЧМП [11]. Она предназначена для решения многокритериальных задач линейного программирования, одной из которых как раз и является многокритериальная транспортная задача (см. выше).

если значения каких-то двух столбцов близки для каждой из строк (кроме строк, содержащих единицы в этих столбцах), то два соответствующих критерия сильно зависимы, так как изменения всех иных критериев (кроме этих двух) одинаково влияют на эти два критерия. Можно выявить также и противоречивые критерии: высокая оценка по одному сопровождается низкой оценкой по другому. Такая информация весьма полезна для ЛПР, изучающего возможности, предоставляемые областью D допустимых значений.
2. Вычисляются индексы критериев. Индекс критериев может быть назван коэффициентом внимания, которое следует уделять критерию при поиске решения. Действительно, если при оптимизации по другим критериям значение данного критерия близко к наилучшему, то ему вряд ли стоит уделять внимание. Наоборот, критерию, сильно зависящему от изменений других критериев (ai мало), должны соответствовать большие значения индекса. Индексы называют иногда техническими весами потому, что в отличие от весов wi они не назначаются ЛПР, а вычисляются.
3. Производится оптимизация по глобальному критерию.

критерию (4). Затем ему задается вопрос: все ли компоненты вектора yi имеют удовлетворительные значения? Если да, то решение получено. Если нет, то ЛПР указывает один критерий с наименее удовлетворительным значением.
2. ЛПР просят назначить для критерия с наименее удовлетворительным значением пороговое значение при достижении которого можно признать этот критерий имеющим удовлетворительное значение. Условие добавляется к совокупности линейных равенств и неравенств, определяющих область D допустимых значений переменных. Таким образом, возникает уже новая область допустимых значений. На этом фаза анализа заканчивается.
Следующий шаг начинается с фазы расчетов при новой области допустимых значений и т.д. При достижении удовлетворительных для ЛПР значений по всем критериям ЧМП останавливается.

предложена модель, характеризующая изменения со временем состава персонала большой организации и продуктивности ее работы [12].
Модель использовалась для прогнозирования последствий различных вариантов управления кадрами организации. Проверялись разные стратегии приема на работу и повышения в должности через два, три и четыре года. В качестве переменных модели рассматривалось количество сотрудников, назначенных на различные должности в определенные периоды времени.
Использовались четыре критерия, представляющих собой линейные функции от переменных:
общее удовлетворение кадров (SA);
фактическая эффективность работы кадров (EF);
стоимость приема на работу дополнительных сотрудников (ЕВ);
стоимость нехватки кадров по отношению к прогнозируемым потребностям (ЕС),
в модель были заложены следующие зависимости:
эффективность работы сотрудника линейно зависит от отношения оценки его возможностей Q к оценке требований t, предъявляемых должностью к сотруднику;
удовлетворение сотрудника во время пребывания на определенной должности сначала возрастает до максимального значения, а затем со временем уменьшается до первоначального значения также в зависимости от отношения Q к t. С математической точки зрения проблема представляла собой задачу линейного программирования с четырьмя критериями качества, 350 переменными и 200 ограничениями. Не имелось никакой априорной информации о сравнительной важности критериев.
Для решения был использован метод STEM [11]. На первом этапе решения в области допустимых значений была осуществлена оптимизация по каждому из критериев. Затем при помощи линейного преобразования истинных значений критериев к значениям в интервале (0,1) (нормирования) был выполнен переход к относительным значениям критериев.

С помощью этих методов исследования операций:
а) разрабатываются модели, описывающие объективную реальность,
б) определяется единственный критерий оптимальности решения;
в) рассчитывается оптимальное решение.
Существенное отличие проблем принятия решений от проблем исследования операций состоит в наличии многих критериев оценки качества решения. Компромисс между критериями может быть найден только на основе предпочтений ЛПР. Существует особый класс задач принятия решений, в которых модели имеют объективный характер (как в задачах исследования операций), но качество решений оценивается по многим критериям. Эти задачи могут быть названы многокритериальными задачами с объективными моделями. Они находятся на границе между исследованием операций и принятием решений.
Одним из первых многокритериальных методов является метод «стоимость-эффективность». Он включает в себя два этапа:
• построение моделей стоимости и эффективности;
• синтез оценок стоимости и эффективности.
На втором этапе используются подходы.
• оптимизация по одному критерию при заданном ограничении по второму,
• построение множества Э-П
Средством решения многокритериальных задач с объективными моделями являются человеко-машинные процедуры (ЧМП). ЧМП представляют собой циклический процесс взаимодействия ЛПР и компьютера. Каждый шаг ЧМП состоит из фазы анализа, выполняемой ЛПР, и фазы расчетов, выполняемой компьютером.
Можно выделить три группы ЧМП: 1) прямые, основанные на выборе коэффициентов важности критериев; ЧМП сравнения векторов; 3) ЧМП поиска удовлетворительных значений критериев.
Одной из первых ЧМП является STEM, основанная на идее последовательного наложения ограничений на критерии.

стоимость-эффективность
Синтез стоимости –эффективности
Хорошо и слабо структурированные проблемы
Пространство переменных и критериев
Человеко-машинные процедуры
Трудности ЛПР в ЧМП
Прямые ЧМП
ЧМП оценки векторов
ЧМП поиска удовлетворительных решений
Процедура STEM