8556
.pdfэто вызывает хотя бы незначительное увеличение важных по уровню приоритета ча-
стных критериев оптимальности. Этот недостаток в какой-то мере удаётся устранить в методе последовательных уступок.
Вернемся к нашему примеру 1Ошибка! Источник ссылки не найден..
Рассмотрим случай, когда 1-й критерий признается более важным, чем 2-й.
1-й шаг.
Решаем:
f1 ( x ) 2* ( x 3 )2 1 min
1 x 7
D1 : x* = 3
В данном случае процедура завершается и второй критерий на результат не влияет.
Несмотря на указанные недостатки, в тех случаях, когда какой-либо критерий имеет значительный приоритет, полученное этим методом решение может оказаться удовлетворительным.
Метод последовательных уступок
Этот метод следует отнести к человеко-машинным процедурам, так как только знание физической сущности задачи может привести к приемлемому результату.
Метод представляет собой последовательную итерационную процедуру.
1-й шаг.
Решается задача:
f1 ( x ) min
G( x ) 0
x1 - решение однокритериальной задачи 1 - го шага.
2-й шаг.
Решается задача:
f2 ( x ) min
G( x ) 0
31
f1 ( x ) f1 ( x1 ) 1
Получили снова однокритериальную задачу.
1 - величина уступки по 1-му критерию, вводимая постановщиком задачи.
Очевидно, что, если 1 мало, полученное решение на втором шаге мало изме-
нит предыдущее решение.
Замечание. На этом шаге также, как и на любом другом, вновь сформулиро-
ванная задача может и не иметь решения. Это обусловливается неудачным подбо-
ром уступок.
Если 1 велико, а это имеет место, когда по критерию f1 ( x ) требования не очень жесткие, то влияние критерия f1 ( x ) на все остальные - не очень велико.
Свойства метода:
1)при 1 0 обеспечивается минимальное значение 1-го критерия за счет всех осталь-
ных;
2)чем больше уступки по предыдущим критериям, тем больше выигрывают после-
дующие критерии;
3)на каждом шаге делается несколько проб для выяснения влияния уступок на сле-
дующий критерий;
4)компромиссное решение зависит от величины всех уступок / 1 , ... , k 1 /;
5)решение получается разным при изменении порядка предпочтения при одних и тех же значениях уступок / D1 , D2 , ..., Dk 1 /;
6)метод последовательных уступок не всегда приводит к получению оптимального по Парето решения.
Продемонстрируем метод последовательных уступок на нашем примере 1: 1-й шаг.
Решаем:
f1 ( x ) 2* ( x 3 )2 1 min 1 x 7
x1 3 f1 (x1 ) = 1
Положим 1 0,1 .
32
2-й шаг.
Решаем:
f2 ( x ) ( x 5 )2 2 min 1 x 7
f1 ( x ) 2* ( x 3 )2 1 1,1
Положим x2 3,2236
Близость x2 к x1 неслучайна, она обусловлена малым значением уступки 1 .
Можно рассмотреть и свести в таблицу с результаты решения задачи 1 при различ-
ных значениях уступок 1 или 2 , что позволит составить некоторое представление о влиянии на решение величин уступок, а также порядка следования критериев.
Метод равенства частных критериев
Равноценными считаются критерии, когда отсутствует информация о важности этих
критериев, и в то же время они не соизмеримы, то есть имеют разную физическую |
|||||||||
размерность. |
|
|
|
|
|
|
|||
Решается задача min f i (x) , где |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x D |
|
|
|
|
|
|
D D1 |
, |
|
|
|
|
|
|
D |
|
|
|
|
|
|
|
||
D |
1 |
{ x Rn |
: f |
1 |
(x) f |
2 |
(x) ... f |
k |
(x)} |
|
|
|
|
|
|
Если изобразить это графически, то мы получим:
f 2
D1
нет решений |
f 1 |
33
f2
D1
Dk
Dk - область Парето. |
f1 |
Решение не является эффективной точкой.
f2
D1
Dk
Dk - область Парето. |
f1 |
Получено решение, являющееся эффективной точкой.
В общем случае решение может не являться эффективной точкой (не принадлежать области компромиссов), может вообще не быть решений.
Пример.
Решим следующую задачу:
f1 ( x ) 2* ( x 3 )2 1 min |
|
f2 ( x ) ( x 5 )2 2 min, |
x R1 |
D {x : 1 x 7} |
|
Решается задача
min |
f i (x) , |
|
|
|
|
|
|
|
|
- |
|
|
|
|
|
|
|
|
|
x D |
|
|
|
|
|
|
|
|
|
где |
|
|
, D { x R1 |
|
|
|
|
|
(x)} . |
D D D |
1 |
: f |
1 |
(x) |
f |
2 |
|||
|
|
1 |
|
|
|
|
|||
Найдем вначале множество |
D1 , |
для этого найдем такие x , для которых функции |
|||||||
f1 ( x ) и f 2 (x) равны. |
|
|
|
|
|
|
f1 ( x ) f 2 (x)
2( x 3 )2 1 (x - 5)2 2
34
x 2 - 2* x - 8 0
Решая квадратное уравнение, получаем:
x1 4
x2 - 2 .
Следовательно:
D1 { x R1 : x 4 или x - 2}
Найдем теперь .
Ответ:
|
--- |
f 1 (x* ) 3, |
i 1, 2 . |
Метод квазиравенства частных критериев оптимальности
Исходная задача многокритериальной оптимизации сводится к задаче
min f i (x) |
|
|
|
|
|
|
|
|
|
|
|
|
|
x D |
|
|
|
|
|
|
где |
|
|
|
|
|
|
|
D D1 |
, |
|
|
|
|
D |
|
|
|
|
||
|
{ x Rn |
|
|
|
--- |
|
D1 |
: |
f i (x) - f j (x) |
; |
i, j 1, k ; |
i j} |
Мы задаем некоторую «уступку» , чтобы разность критериев не превышала
по абсолютной величине заданной .
Пример.
Решим следующую задачу:
f1 ( x ) 2* ( x 3 )2 1 min |
|
f2 ( x ) ( x 5 )2 2 min, |
x R1 |
D {x : 1 x 7} |
|
эта задача сводится к:
min |
fi (x) , |
|
|
|
|
__ |
|
|
|
|
|
x D |
|
|
|
|
|
где |
|
, |
D1 { x R1 : |
|
} . |
D D D1 |
f1 (x) - f 2 (x) |
||||
|
|
|
|
|
35 |
Возьмем для примера величину уступки 0,3 .
Решим неравенство |
|
f 1 (x) - f 2 (x) |
|
0,3 . |
||
|
|
|||||
|
2* ( x 3 )2 1 - (x - 5)2 - 2 |
|
|
0,3 |
||
|
|
|
После упрощения получаем:
x 2 - 2* x - 8 0,3
После решения вышеуказанного неравенства получаем:
|
{ x R1 : 1 - |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
D |
|
9,3 x 1 |
8,7 или |
1 |
8,7 x 1 9,3 } |
|||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D D1 |
{ x R1 : |
|
|
|
|
|
|
|
|
|
|
|
|
||||
D |
1 8,7 |
|
x 1 9,3 |
} |
|
|
|
|||||||||||
Найдем теперь min |
f i (x) . |
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x D |
|
|
|
|
|
|
|
|
|
|
|
|
||
Ответ: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x* 1 8,7 |
3,95 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
f1 (x* ) 2,8 |
|
f 2 (x* ) 3,1 |
|
|
f(x) 2,8 . |
Метод гарантированного результата или метод минимакса
Этот метод заключается в том, что исходная задача многокритериальной оптимиза-
ции сводится к задаче
min max |
f i (x) - f i* |
||
* |
|||
x D |
|
||
i 1,k |
f i |
||
|
f i* min f i ( x )
x D
полученное решение и будет приниматься за решение исходной задачи многокрите-
риальной оптимизации.
Пример.
Решим следующую задачу:
f1 ( x ) 2* ( x 3 )2 1 min |
|
f2 ( x ) ( x 5 )2 2 min, |
x R1 |
D {x : 1 x 7} |
|
эта задача сводится к задаче
36
min |
max |
f i (x) |
|
- |
f i* |
, |
|
f i* |
min f i ( x ) |
|
x D |
i 1,2 |
f i* |
|
|
|
|
x D |
|||
f1 ( x ) 2* ( x 3 )2 1 |
f1* 1 |
|||||||||
f 2 ( x ) ( x 5 )2 2 |
f 2* 2 |
|
||||||||
|
|
|
|
|
|
(x - 5) |
2 |
|
|
|
|
|
|
|
2 |
; |
|
|
|
||
max 2* ( x 3 ) |
|
|
2 |
|
. |
|
||||
i 1,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
2.( x |
3 )2 |
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
( x |
5 )2 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
x |
|
Найдем точки пересечения двух функций. |
2( x 3 )2 |
(x - 5)2 |
|
2 |
||
|
3* x 2 - 14 * x 11 0
Решая квадратное уравнение, получаем:
x1 1
x2 113 .
Ответ: x* 113
- гарантированная точка, является эффективной.
37
2.3.2. Раздел 2. Оптимизация в условиях неопределенности и риска
Задачи принятия решений (ЗПР) классифицируют по трём признакам:
1)по количеству целей управления и соответствующих им критериев оптималь-
ности ЗПР делят на одноцелевые, или однокритериальные (скалярные), и мно-
гоцелевые, или многокритериальные (векторные);
2)по наличию или отсутствию зависимости критерия оптимальности и ограниче-
ний от времени ЗПР делят на статические (не зависящие от времени) и дина-
мические (зависящие от времени).
Динамическим ЗПР присущи две особенности:
a)критерием оптимальности в динамических ЗПР является не функция, как в ста-
тических ЗПР, а функционал, зависящий от функции времени;
b)в составе ограничений обычно присутствуют так называемые дифференциаль-
ные связи, описываемые дифференциальными уравнениями;
3)по наличию случайных и неопределённых факторов этот признак называется
«определённость–риск–неопределённость». ЗПР подразделяют на три больших подкласса:
a)принятие решения в условиях определённости, или детерминированные ЗПР.
Они характеризуются однозначной детерминированной связью между приня-
тым решением и его исходом;
b)принятие решений при риске, или стохастические ЗПР. Любое принятое реше-
ние может привести к одному из множества возможных исходов, причём каж-
дый исход имеет определённую вероятность появления. Предполагается, что эти вероятности заранее известны лицу, принимающему решение;
c)принятие решений в условиях неопределённости. Любое принятое решение может привести к одному из множества возможных исходов, вероятности по-
явления которых неизвестны. Общая постановка однокритериальной статиче-
ской задачи принятия решений в условиях риска.
38
Каждая выбранная стратегия управления в условиях риска связана с множест-
вом возможных исходов, причём каждый исход имеет определённую вероятность появления, известную заранее человеку, принимающему решение.
При оптимизации решения в подобной ситуации стохастическую ЗПР сводят к детерминированной. Широко используют при этом следующие два принципа: искус-
ственное сведение к детерминированной схеме и оптимизация в среднем.
В первом случае неопределённая, вероятностная картина явления приближённо заменяется детерминированной. Для этого все участвующие в задаче случайные факторы приближённо заменяются какими-то неслучайными характеристиками этих факторов (как правило, их математическим ожиданием).
Приём «оптимизация в среднем» заключается в переходе от исходного показа-
теля эффективности Q, являющегося случайной величиной, к его усреднённой, ста-
тической характеристике, например, к его математическому ожиданию. «Искусст-
венное сведение к детерминированной схеме» представляет собой детермизацию на уровне факторов, а «оптимизация в среднем» – на уровне показателя эффективности.
Отметим принципиальное различие между стохастическими факторами, приво-
дящими к принятию решения в условиях риска, и неопределёнными факторами,
приводящими к принятию решения в условиях неопределённости. И те, и другие приводят к разбросу возможных исходов результатов управления. Но стохастиче-
ские факторы полностью описываются известной стохастической информацией, эта информация и позволяет выбрать лучшее в среднем решение. Применительно к не-
определённым факторам подобная информация отсутствует.
В общем случае неопределённость может быть вызвана либо противодействием разумного противника, либо недостаточной осведомлённостью об условиях, в кото-
рых осуществляется выбор решения.
Принятие решений в условиях разумного противодействия является объектом исследования теории игр. Теория игр рассматривает пути оптимизации поиска нуж-
ного решения в условиях неопределенности. Теория статистических решений (крат-
ко – теория решений) отличается от теории игр тем, что рассматривает неопреде-
39
ленность ситуации без конфликтной окраски – никто никому сознательно не проти-
водействует. В задачах теории статистических решений неизвестные условия опера-
ции зависят не от сознательно действующего «противника», а от объективной неза-
интересованной действительности, которую в теории статистических решений при-
нято называть «природой», «поведение» которой неизвестно. Эти ситуации часто называются «игры с природой».
С этой целью в теории решений вводится понятие риска. Риском лица, прини-
мающего решение по использованию определенной стратегии (технологии) в неоп-
ределенных условиях называется разность между выигрышем (результатом, показа-
телем эффективности), который получился бы, если бы были известны условия, и
выигрышем, который получится при неопределенности условий. Следовательно,
возникают две постановки задачи по выбору решения, два возможных сценария: при одном нам желательно получить максимальный выигрыш, при другом – минималь-
ный риск. Оптимально, конечно, максимальный выигрыш при минимальном риске.
Можно попробовать манипулировать в пределах наших знаний возможными ходами природы, уменьшая степень неопределенности, но это далеко не всегда возможно.
Можно принять решение по использованию максимального числа технологий, каж-
дая из которых уменьшает риск. Но только суммирование технологий не приводит к суммированию выигрышей.
Итак, принимая решения, выбирая технологию, необходимо задаться вопросом,
что необходимо получить: максимальный выигрыш при достаточно высоком риске,
максимально снизить риск при относительно невысоком результате или выбрать
«золотую середину».
Теория статистических решений предлагает несколько критериев оптимально-
сти выбора решений. Выбор того или иного критерия неформализуем, он осуществ-
ляется человеком, принимающим решения, субъективно, с учетом собственного опыта, интуиции и т. п. Рассмотрим эти критерии.
1.Максиминный критерий Вальда. Предполагается что второй игрок – природа максимально агрессивна и делает все, чтобы результат (выигрыш) был ми-
40