Турунтаев Л.П. Теория принятия решений. Учебное пособие томск 2007 Томский межвузовский центр
 Скачать 1.57 Mb.
|
|
6 ЭВРИСТИЧЕСКИЕ ПРОЦЕДУРЫ ЗАДАЧ ПРИНЯТИЯ РЕШЕНИЙ 6.1 Человеко-машинная процедура STEM Одной из первых ЧМП была разработана процедура STEM [28, 35]. Она предназначена для решения многокритериальных задач линейного программирования. Пусть 1 2 ( , , ..., ) n X x x x = — вектор переменных задач; 1 ( ) n j j j X y c x i = = ⋅ ∑ , i=1, n (6.1) — целевая функция по критерию i, определяемая на множестве переменных X и векторе C, значение которой необходимо мак- симизировать. Пусть множество допустимых значений X ограничено сис- темой Ω : A X B ⋅ = , (6.2) X ≥ 0, где A — матрица ( ); d n × B — вектор-столбец размерностью ( 1) n × . Пусть 0 ( ) Y X — общая функция предпочтений (функция полезности) на множестве целевых функций ( ) i y x определяется в виде взвешенной суммы критериев. 0 1 ( ) ( ). m i i i Y X X y = = ⋅ ∑ α Необходимо найти вектор (аргумент) X, максимизирующий совокупность целевых функций ( ) i y X при наиболее предпочти- тельном соотношении их значений в точке решения X и удовле- творяющей системе ограничений (6.2), то есть необходимо най- ти решение 1 arg max ( ) m i i i X X X y = ∈Ω = ∑ α Решение этой задачи — вектор X следует искать во множе- стве Парето-эффективных решений, а требование нахождения 116 наиболее предпочтительного (неявно выраженного) соотноше- ния между значениями критериев со стороны лица, принимаю- щего решение, в человеко-машинных процедурах выражается, как правило, в большинстве своем в поиске весовых коэффици- ентов i α целевых функций. Поскольку назначение весовых коэффициентов является для ЛПР сложной операцией, то в человеко-машинной процеду- ре STEM определение i α поручается ЭВМ. Задача многокритериальной оптимизации представляется как задача поиска удовлетворительного (компромиссного) ре- шения, формализуемого в виде условий ( ) , i i x y ≥ µ i=1, 2,…, m, (6.3) где i µ — пороговые значения критериев, выделяющие множе- ство удовлетворенных решений и назначаемые ЛПР. Так как удовлетворительное значение порога i µ в общем случае зависит от значений других критериев ( ), , k x i k y ≠ то ус- ловия (6.3) корректируются в ходе человеко-машинной проце- дуры по мере анализа новых альтернатив и изменения предпоч- тений ЛПР о множестве допустимых решений. Человеко-машинная процедура STEM состоит из следую- щих фаз: оптимизации — C A τ τ − (выполняются на ЭВМ) и ана- лиза — D E τ τ − (выполняются ЛПР, τ — номер итерации): Шаг A τ 1. Вычисляется матрица y Y τ νκ = , где y νκ — значение целевой функции по критерию ν , найден- ное на решении X ∗ κ , то есть ( ). y y X ∗ κ νκ ν = Решение X ∗ κ определяется в результате решения локальной задачи оптимизации целевой функции по k-му критерию ( ) X y κ в текущей области допустимых решений Ω , то есть arg max ( ) X y X X ∗ κ κ ∈Ω = Ω на первой итерации определяется системой уравнений (4.2). На последующих итерациях к ней будет добавляться по одному 117 ограничению вида (6.3), накладываемого на наиболее не удовле- творяющий критерий. 2. Нормируется матрица y Y τ νκ ′ = ′ ( ) /( ), y y y m m ν ν νκ νκ κκ ′ = − − где min y m ν νκ = ; 0 1. y νκ ′ ≤ ≤ Очевидно, что для диагональных элементов 1. y νκ ′ = 3. Рассчитывается система весовых коэффициентов i α кри- териев i: 1 1 (1 ) /(1 ) / i i − − = η η α α ; i = 2, …, N; 1 i i = α ∑ ; где min i i y κ ′ = η или, i i y′ = η , где i y′ — среднее значение элементов i-ой строки (исключая максимальный). Шаг B τ 1. Определяется вектор компромиссного решения X τ на итерации τ , максимизирующий функцию полезности 0 1 ( ) ( ) m i i i y Y X X τ τ = = ⋅ α ∑ 2. Вычисляется вектор критериальных оценок 1 2 ( ( ), ( ),..., ( )) m y y y P X X X τ τ τ τ = , соответствующий компромисс- ному решению X τ Шаг C τ Формируется сообщение ЭВМ на итерации τ { } , y P τ τ τ = ω , где 11 22 ( , ,..., ) mm y y y y τ = — вектор критериальных оценок, со- ответствующий идеальным решениям 1 2 1 2 ( ), ( ),..., ( ). m m y y y x x x Шаг D τ Оценивается предлагаемое решение на основании сопос- тавления векторов P τ и . y τ 118 Если ЛПР считает это решение удовлетворительным, за- вершается процедура, иначе переход к шагу E τ Шаг E τ ЛПР указывает, какой из критериев в векторе P τ имеет наименее удовлетворительное значение, и устанавливает желае- мую величину порога удовлетворенности i µ (i — номер не- удовлетворяющего критерия). Таким образом, информация ЛПР имеет вид: { } ,i i τ = µ ω Перейти к шагу 1 A τ+ (размерность матрицы 1 Y τ+ умень- шится на единицу, так как критерий i «уйдет» в область ограни- чений). Пример Обратимся к задаче определения плана выпуска продукции, рассмотренной в разделе 4.1. Добавим еще один критерий опре- деления плана: минимизация суммарного времени простоя обо- рудования (максимизация загрузки оборудования). В целом, не- обходимо определить план производства столов и шкафов с уче- том трех критериев: 1) максимизация дохода от реализации продукции (в руб- лях) ï 1 2 2 1 1 x y c c x = ⋅ + ⋅ , где ï 1 x — план выпуска столов, предназначенных для продажи, 2 x — план выпуска шкафов, предназначенных только для продажи; 2) максимизация выпуска столов для нужд всего предпри- ятия (в штуках) Ñ 1 2 y x = , где Ñ 1 x — план выпуска столов, предназначенных для собствен- ных нужд предприятия; 3) максимизация загрузки оборудования (в часах) 119 2 3 1 j j j y t x = = ∑ , где Ï Ñ 1 1 1 ; x x x = + j t — время изготовления одного продукта j-ого вида (час). Пусть время изготовления одного стола 1 30 t = минут, вре- мя изготовления одного шкафа 2 80 t = минут. Решением задачи определения плана выпуска продукции с учетом только первого критерия является вектор Ï Ñ 1 2 1 1 ( , , ) x x x X ∗ = = (517; 0; 156), то есть столов на продажу сле- дует производить в количестве ï 1 517 x = штук, столов для соб- ственных нужд — не производить Ñ 1 x =0, шкафов — произво- дить в количестве 2 x =156 штук. Значение первого критерия 1 1 ( ) y X ∗ =375500 рублей. Решением задачи с учетом только второго критерия являет- ся вектор 2 X ∗ =(0;700;0), то есть столов (для собственных нужд предприятия) следует производить в количестве Ñ 1 x =700 штук. Значение второго критерия 2 2 ( ) y X ∗ =700 штук. Решением задачи с учетом только третьего критерия явля- ется множество решений 3 ( 279;(1 ) 279;268) X ∗ = λ ⋅ − λ ⋅ , то есть столов в общей сумме следует производить Ï Ñ 1 1 x x + =279 штук (0 1 ≤ λ ≤ ), а шкафов — в количестве 2 x =268 штук. Значением третьего критерия является величина 3 3 1 ( ) 279 2 y X ∗ = ⋅ + 4 268 3 ⋅ = =497 часов. Процедура STEM включает следующие шаги. Шаг 1 A . 1. Рассчитывается матрица 1 Y (табл. 6.1) Ï 1 1 2 2 1 11 1 ( ) j j j y y c x c x c x X ∗ = = ⋅ = ⋅ + ⋅ = ∑ = 500 517 750 156 375500 ⋅ + ⋅ = рублей; 120 2 12 1 ( ) y y X ∗ = = 500 0 750 0 ⋅ + ⋅ =0 рублей; 3 13 1 ( ) y y X ∗ = = (500 279 750 268) ⋅ ⋅ λ + ⋅ рублей. При 1, λ = то есть если все столы пустить на продажу, 13 y = = 340500 рублей. При λ =0, то есть если все столы оставить для нужд предприятия, 13 y =201000 рублей. Таким образом, 340500 13 201000 y ≤ ≤ Ñ 1 1 21 2 ( ) 0 y y x X ∗ = = = штук, 2 22 2 ( ) y y X ∗ = = 700 штук, 3 23 2 ( ) (1 ) 279 y y X ∗ = = − λ ⋅ штук. То есть 23 y изменяется от 0 до 279 штук 23 0 279 y ≤ ≤ 1 31 3 ( ) j j j y y t x X ∗ = = = ∑ 1 1 4 517 0 156 2 2 3 ⋅ + ⋅ + ⋅ = 466.5 час. 2 32 3 ( ) y y X ∗ = = 1 4 700 0 350 2 3 ⋅ + ⋅ = час. 3 33 ( ) y X ∗ = 497час. Таблица 6.1 — Значение критериев при различных оптимальных ре- шениях Решения ) ; ; ( 2 С 1 П 1 x x x X = Критерии = ∗ X 1 (517; 0;156) = ∗ X 2 (0; 700;0) = ∗ X 3 ( ⋅ λ 279; (1– λ )279; 268) y 1 (тыс.руб.) 375.5 0 201 ÷ 340.5 y 2 (шт.) 0 700 0 ÷ 279 y 3 (час) 466.5 350 497 2. Нормируем матрицу 1 Y по каждому из критериев, приняв 13 y =(201+340.5)/2=270.75 рублей и [ ] 23 279 2 y = = 139 штук. 121 1 0 0.72 0 1 0.2 0.79 0 1 72 0 ) 0 5 375 ( 75 270 13 = − = ′ y 2 / 0 ) 0 700 ( 139 23 = − = ′ y ) 350 497 ( ) 350 5 466 ( 31 − − = ′ y = = 116.5:147=0.79 3. Рассчитываются весовые коэффициенты i α . 1 2 1 0.36 1 0.1 − α = − α ; 1 3 1 0.36 1 0.395 − α = − α ; 1 2 3 1. + + = α α α 0.9 1 α – 0.64 2 α =0; 0.605 1 α – 0.64 3 α =0; 1 2 3 1 + + = α α α Решая эту систему уравнений, получаем: 1 α =0.3; 2 α =0.42; 3 α =0.28. Шаг 1 B . 1. Определяется решение по глобальному критерию 0 Y 3 0 1 ( ) i i i X y Y = = ∑ α Решая задачу линейного программирования 0.3 Ï 2 1 500 750 375500 x x + ⋅ +0.42 Ñ 1 700 x ⋅ +0.28 → ⋅ + + ⋅ 497 33 1 ) ( 5 0 2 С 1 П 1 x x x max при ограничениях на ресурсные параметры: 0.06 Ï 1 x 0.06 C 1 x + 0.07 2 x ≤ 42; 0.04 Ï 1 x + 0.04 Ñ 1 x +0.085 2 x ≤ 34; (*) 0.035 Ï 1 x +0.035 Ñ 1 x +0.12 2 x ≤ 42; Ï Ñ 2 1 1 , , 0 x x x ≥ , Ï Ñ 2 1 1 , , x x x — целые. Получим компромиссное решение Ñ X с координатами Ï 1 x =0; Ñ 1 x =517; 2 x =156. 2. Вектор критериальных оценок 1 P для решения Ñ X 122 { } Ñ Ñ Ñ 1 1 2 3 ( ); ( ); ( ) y y y P X X X = ={117 тыс. руб.; 517 шт.; 466.5 час}. Шаг 1 C . Формируется сообщение ЭВМ для ЛПР 1 ω : Критерии Вектор оценок y 1 y 2 y 3 Вектор y 1 идеальных решений X ∗ 375.5 тыс. руб. 700 шт. 497 час Вектор P 1 компро- миссных решений 117 тыс. руб. 517 шт. 466.5 час Шаг 1 D . ЛПР оценивает компромиссное решение по значениям кри- териев. Если оно считает это решение удовлетворительным, то процедура поиска на этом заканчивается. Иначе, переходим на следующий шаг. Шаг 1 E . ЛПР указывает, какой из критериев в векторе 1 P имеет наименее удовлетворительное значение. Пусть оно указывает на критерий 1 и устанавливает порог в 300 тыс. руб., то есть дает сообщение 1 = ϖ {1; 300 тыс. руб.}. Переходим на шаг 2 A . Шаг 2 A . 1. Рассчитывается матрица 2 Y Решения ) ; ( 2 ; С 1 П 1 x x x X = Критерии = ∗ X 2 (0;700;0) = ∗ X 3 ( λ 279;(1– λ )279;268) y 2 (шт.) 700 0 ÷ 279 y 3 (час) 350 497 123 2. Нормируем таблицу 2 Y по каждому из критериев, при- няв 23 y =139 шт. 1 0 2 Y = ′ 0 1 3. Рассчитываются весовые коэффициенты 2 α и 3 α : 2 α =0.5; 3 α =0.5. Шаг 2 B . 1. Определяется решение по глобальному критерию 3 0 2 ( ) i i i X y Y = = α ∑ Решаем задачу 0.5 Ñ 1 700 x ⋅ +0.5 Ï Ñ 2 1 1 0.5 ( ) 1.33 497 x x x ⋅ + + ⋅ ⋅ → max при ограничениях на ресурсные параметры (*) и на значение критериальной функции 1 y 500 Ï 1 x +750 2 x ≥ 300000. Получим новое компромиссное решение Ñ X с координата- ми Ï 1 x =365; Ñ 1 x =152; 2 x =156. 2. Вектор критериальных оценок 2 P для решения Ñ X { } Ñ Ñ Ñ 2 1 2 3 ( ); ( ); ( ) y y y P X X X = ={300 тыс. руб.; 152 шт.; 466.5 час}. Шаг 2 C . Формируется сообщение для ЛПР 2 ω . Критерии Вектор оценок y 1 y 2 y 3 X ∗ идеальных решений 375.5 тыс. руб. 700 шт. 497 час X С компромиссных решений 300 тыс. руб. 152 шт. 466.5 час 124 Шаг 2 D . ЛПР оценивает полученное решение. Если оно считает это решение удовлетворительным, то процедура поиска решения заканчивается, иначе, повторяются шаги 2 3 3 3 3 , , , , C E A B D . 6.2 Метод порогов несравнимости «ЭЛЕКТРА» В методе «ЭЛЕКТРА» [18] разработана процедура много- критериального выбора наиболее предпочтительных объектов, включающая следующие этапы. 1. Для каждого из критериев вводится дискретная шкала возможных значений этого критерия, весовые коэффициенты критериев. 2. Для каждого из критериев строится граф, вершинами ко- торого являются отдельные объекты множества, а дуги указы- вают на отношение доминирования между объектами в соответ- ствии с данным критерием. 3. С учетом важности критериев и предпочтительности объ- ектов вычисляются матрицы значений специальных коэффици- ентов, называемых индексами согласия и несогласия. 4. Для каждой пары объектов ( , ) x y X ∈ считается установ- ленным отношение превосходства, скажем х над у, если значе- ние соответствующего индекса согласия больше некоторого по- рогового значения, а индекс несогласия — меньше соответст- вующего порогового значения. 5. Строится обобщенный граф превосходства, структура ко- торого зависит от выбранных пороговых значений. Рассмотрим следующую задачу. Пусть Х представляет со- бой множество абитуриентов, принимающих участие в конкурс- ных экзаменах при поступлении в технический вуз. На основа- нии проведенных экзаменов необходимо отобрать лучших кан- дидатов. Состав дисциплин и возможные способы оценки аби- туриентов по дисциплинам могут варьироваться согласно спе- цифическим особенностям вуза. Рассмотрим этапы процедуры «ЭЛЕКТРА». 1. В качестве примера рассмотрим оценки трех абитуриен- тов по трем дисциплинам в пятибалльной шкале (табл. 6.2). 125 Таблица 6.2 — Оценки вступительных экзаменов Абитуриенты Дисциплина Математика Физика Литература x 5 3 4 y 5 4 3 z 4 5 3 Обозначим: , , x y z X ∈ — множество оцениваемых объектов; i x — оценка объекта x по критерию , 1,3; i i = i c — весовой коэффициент критерия ; 3 , 1 , = i i 0 1(10,100, ...). i c < < Пусть 1 2 3 5, 3, 2. c c c = = = 2. Для каждого критерия i строим граф ( , ), i i G X V = где i V — множество дуг графа i G (рис. 6.1). Дуга в графе i G из вершины х в вершину у существует, если i i x y ≥ Равенство оце- нок i i x y = в графе влечет наличие двух дуг из х в у и из у в х. ( , ) , 1,3. i i i x y V x y i ∈ ⇔ ≥ = Построим объединенный граф 0 0 ( , ), G X V = где 3 0 3 i i V V = = I есть пересечение трех графов с дугами i V (рис. 6.2). В нашем примере 0 V = {Ø}, т.к. в трех графах нет дуг, одновременно сов- |