close

Вход

Забыли?

вход по аккаунту

?

Shaporev2

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
С. Д. Шапорев
ПРИНЯТИЕ РЕШЕНИЙ
В УСЛОВИЯХ РИСКА
И НЕОПРЕДЕЛЁННОСТИ
Учебное пособие
УДК 519.6
ББК 22.16
Ш24
Рецензенты:
канддат технических наук, профссор Н. А. Шехунова;
кандидат физико-математических наук, профессор Б. П. Родин
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Шапорев, С. Д.
Ш24Принятие решений в условиях риска и неопределённости:
учеб. пособие / С. Д. Шапорев. – СПб.: ГУАП, 2018. – 139 с.
ISBN 978-5-8088-1306-9
Рассмотрены основные, до сих пор окончательно не решённые вопросы принятия решений в условиях риска и полной неопределённости. Рассмотрены также все математически предшествующие проблемы, в частности идеи и алгоритмы многомерной оптимизации и
многокритериального выбора.
Пособие полезно для знакомства с основными направлениями и
методами многомерной оптимизации и многокритериального выбора; предназначено для магистров технических вузов и читателей, интересующихся проблемами оптимального выбора.
УДК 519.6
ББК 22.16
ISBN 978-5-8088-1306-9
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2018
1. ОСНОВНЫЕ ИДЕИ МАТЕМАТИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
§ 1.1. Общие положения
Любая реальная задача либо производственная, либо социальная
нуждается в математической формализации. Выводы из задачи представляют практический интерес только тогда, когда математическая
модель отображает реальную ситуацию и достаточно совершенна.
Процесс составления математической модели условно можно
представить в виде следующих этапов [1, 2].
1) Изучение объекта (или явления). Здесь важны анализ особенностей функционирования объекта, определение влияющих факторов, изучение характеристик объекта при варьировании условий
его существования, наличие и выбор оптимального критерия – целевой функции.
2) Описательное моделирование. Это фиксация основных связей
и зависимостей объекта по выбранной целевой функции.
3) Математическое моделирование. Создаётся полноценная математическая модель объекта, выраженная математическими формулами. Все условия записываются в виде соответствующей системы
равенств и (или) неравенств. Целевая функция также должна быть
известна полностью.
4) Выбор или создание метода решения. Выбирается либо известный метод, либо создаётся новый. При этом решение задачи может
быть допустимым, т. е. решением, удовлетворяющем выбранным
ограничениям, либо оптимальным, т. е. решением, доставляющем
к тому же экстремум целевой функции.
5) Выбор и написание программы для решения задачи на ЭВМ. Сейчас это неизбежно ввиду объёмности и трудоёмкости решаемых задач.
6) Решение задачи на ЭВМ.
7) Анализ полученного решения. Анализ может быть формальным или содержательным. При последнем в модель могут быть внесены необходимые изменения для её совершенствования.
8) Анализ устойчивости решения. Это необходимый этап. Только
после такого анализа при положительном решении об устойчивости
решения модель можно использовать для расчёта.
Разработка методов решения задач, содержащих целевую функцию и условия ограничения – это раздел математики – математическое программирование.
3
Основой математического программирования является теория
оптимизации, у истоков которой стояли такие учёные как И. Бернулли*, Эйлер**, Лагранж***. Развитие методов математического
программирования породило такие научные дисциплины как исследование операций, сетевые (потоковые) задачи и сетевой анализ.
§ 1.2. Некоторые определения математического анализа,
необходимые для дальнейших вычислений
=
Пусть y f (x1, x2 ,..., xn ), xi ∈ Mi , y ∈ Y.
f ( x1,..., xi −1, xi + ∆xi , xi +1,..., xn )
∂f
= lim
1) Тогда
называется
∂xi ∆xi →0
∆xi
частной производной f по xi.
2) Градиент скалярной функции f ( x1, x2 ,..., xn ) есть векторная
функция точки и определяется следующим образом:
∂f
∂f
∂f
=
i+
j + ... +
k,
gradf ≡ ∇f ( x1,..., x
n)
∂x1
∂x2
∂xn
где i, j, k – орты координатных осей.
3) Скорость изменения скалярной функции f ( x1, x2 ,..., xn )
в произвольном направлении, задаваемым единичным вектором
u= cos αi + cos β j + ... + cos γ k, определяется производной по направлению
∂f
∂f
∂f
∂f
=
cos α +
cos β + ... +
cos γ.
∂u ∂x1
∂x2
∂xn
∂f

При этом
=∇f ⋅ u ⋅ cos ∇f,u è ∇f ⊥ u.
∂u
( )
§ 1.3. Особенности нахождения оптимальных решений
в задачах математического программирования [1]
=
z f=
Для примера рассмотрим
( x, y ) f ( x1, x2 ) – целевую функ0 (неравенств нет).
цию и ограничения равенства ϕ ( x1, x2 ) =
z = f ( x, y ) изображает некоторую поверхность. При нахождении её
экстремума при учёте ограничений необходимо:
*
Иоганн Бернулли (1667–1748) – швейцарский математик и механик.
** Леонард Эйлер (1707–1783) – швейцарский математик.
*** Жозеф Луи Лагранж (1736–1813) – французский математик, механик и
астроном.
4
z
z=f(x1, x2)
C
A
B
E
x2
0
x1 D
ϕ(x1,x2)=0
Рис. 1.1
Рис. 1.1
1) Найти линии пересечения поверхности z = f ( x1, x2 ) и цилин0.
дра с образующей параллельной оси z и направляющей ϕ ( x1, x2 ) =
2) Поиски экстремума z = f ( x1, x2 ).
На рис. 1.1 точки А и В – точки условного экстремума. Они не совпадают с точками безусловного экстремума функции z = f ( x1, x2 )
0 можно вы(точки С, D, E). Если из уравнения связи ϕ ( x1, x2 ) =
разить какую-то одну переменную через другую, то x2 = ψ ( x1 ) и
=
z f ( x1, ψ ( x1 ) ) – функция одной переменной. Тогда её безусловный экстремум будет условным экстремумом для z = f ( x1, x2 ) при
0. Однако часто x2 = ψ ( x1 ) не находиться.
ограничении ϕ ( x1, x2 ) =
В этом случае используется метод множителей Лагранжа. Его суть
такова, пусть
f ( x1, x2 ,..., xn ) ⇒ min(max),

, j 1, p.
n ) 0=
 hj ( x1, x2 ,..., x=
(1.3.1)
Составляется функция Лагранжа
(
)
F x1, x2 ,..., xn , λ1, λ2 ,..., λ p =
p
= f ( x1, x2 ,..., xn ) + ∑ λ j hj ( x1, x2 ,..., xn ), (1.3.2)
j =1
где λ j – неизвестные множители Лагранжа, и задача (1.3.1) на условный экстремум сводится к задаче (1.3.3) на безусловный экстремум.
5
z
f(x1, x2)
M
z
M
A
x2
0
0
D
x2
D
x1
x1
Рис. 1.3
Рис. 1.2
f(x1, x2)
B
 F ( x1, x2 ,..., xn ) ⇒ min(max),

λj =
?

(1.3.3)
Здесь нужно найти экстремум f и определить все λj стандартным
методом математического анализа. При этом могут быть несколько
разных вариантов решения.
На рис. 1.2 точка М – точка безусловного экстремума функции
z = f(x1, x2) одновременно является точкой условного экстремума
рассматриваемой задачи. На рис. 1.4 точка М – граничная и в ней
функция z = f(x1, x2) экстремума не имеет. На рис. 1.3 точка М не
принадлежит области допустимых значений переменных.
z M
f(x1, x2)
Экстремум f
x2
0
D
x1
Рис. 1.4
6
Все эти результаты показывают неоднозначность решения, даже
когда поверхность функции z = f(x1, x2) проста. Наиболее значимые
с практической точки зрения результаты в задачах математического программирования получены для выпуклых функций (как целевых, так и ограничений). Геометрически выпуклая функция всегда
лежит над (под) своими касательными. Аналитически функцию
f(M) называют строго выпуклой на множестве D, если для 0 < λ < 1 и
М1≠М2 выполняется неравенство
f ( λM1 + (1 − λ ) M2 ) < λf ( M1 ) + (1 − λ ) f ( M2 ). (1.3.4)
Существует важный класс задач – задачи выпуклого программирования. Они обладают важным свойством – локальные минимумы z = f(x1, x2,…, xn) являются глобальными (единственными).
§ 1.4. Необходимые и достаточные условия экстремума
в задачах математического программирования [3]
В задачах математического программирования находят локальный минимакс целевой функции. Пусть это x∗, тогда или f(x∗) > ( < )
f(x) для строгого и f(x∗)≥(≤)f(x) для нестрогого минимакса. Если
множество решений D выпукло, то ∇f(x∗) составляет острый угол
ϕ с вектором направленным из x∗ в любую точку x1∈D (рис. 1.5).
π
x – точка, не являющаяся решением задачи, в ней ϕ > , в точке
2
π
x∗ ϕ < . В тех случаях, когда решение x∗ находится внутри области
2
D ∇f(x∗) = 0.
Сформулированные условия являются необходимыми условиями в задаче минимизации дифференцируемой функции f на вы-
Линии уровня
x1
D
∇f x
( )
ϕ
ϕ
∇f(x∗)
x∗
x2
x
Рис. 1.5
7
пуклом множестве D. Если же D имеет вид параллелепипеда и при
этом ai≤xi≤bi, –∞ < ai < bi < + ∞, i = 1, 2,…, m, то из теории матанализа
известно, что данное необходимое условие записывается следующим образом:
( )
 ∂f x∗

= 0, ai < xi∗ < bi ,
 ∂x
i

 ∂f x∗

∗
> 0, x=
ai ≠ −∞, 
i
∂
x
i


∗
 ∂f x
< 0, xi∗= bi ≠ +∞.
 ∂
x
i

( )
(1.4.1)
( )
В общем случае для задачи вида
( )
( )
( )
f x → min(max),


1,m,  gi x ≥ 0, i =

x 0=
, j 1, p
 hj =

(1.4.2)
составляется функция Лагранжа следующего вида
(
) ( )
m
( )
p
( )
L x,u,=
λ f x + ∑ ui gi x + ∑ λ j hj x , =i 1=j 1
(1.4.3)
1, p – множители Лагранжа, определяемые
где ui , i = 1,m, λ j , j =
в задаче вместе с вектором x, при этом все ui должны быть неотрицательными, а λj могут иметь любой знак.
Все возможные частные случаи этой задачи рассмотрены в матанализе и известны. Конкретный встреченный случай можно уточнить в специальной литературе.
Рассмотрим геометрию одного частного случая.
Пусть
 f ( x ) → min,

1,m.
 gi ( x ) ≤ 0, i =
( )
(1.4.4)
m
( )
Тогда в точке минимума имеем ∇ x f x∗ + ∑ ui∗∇ x gi x∗ =
0, т. е.
i =1
антиградиент целевой функции является неотрицательной линей8
∇xg3(x∗)
g3(x)=0
x
D
∇xg1(x∗)
–∇xf(x∗)
g1(x)=0
∇xg1(x∗)
g2(x)=0
x∗
∇xg2(x∗)
–∇xf(x∗)
Рис. 1.6
ной комбинацией градиентов функций, образующих ограничения
в (1.4.4) (рис. 1.6). Из этого рисунка видно, что точка x не может
быть точкой экстремума, так как в ней не выполнено условие того,
что –∇xf(x∗) есть положительная линейная комбинация градиентов
активных ограничений. Все эти условия выполнены в точке x∗.
§ 1.5. Графическое решение задач
математического программирования
Для функции z = f(x1, x2,…, xn) от двух, а иногда и от трёх переменных можно применить графический метод. Рассмотрим следующий пример.
( )
f x = x1 − 2 + x2 − 2 → min,


g x = x1 − x12 ≥ 0,


h x = x12 + x22 − 1= 0.


( )
( )
(1.5.1)
Этот пример очень простой, все области строятся без усилий (см.
рис. 1.7).
Для z = f(x1, x2)→min допустимая область D – это дуга ABC.
Линии уровня целевой функции f(x1, x2) изображены в виде квадратов. Градиент ∇f x направлен в сторону дуги ABC. Функция
f(x1, x2) будет иметь минимальное значение в точке касания линии
( )
9
f(x)=0
2
x12 + x22 = 1 1
A
Линии уровня
x∗
2
B
1
–1
–1
C
x1 = x22
Рис. 1.7
 2 2
,
уровня дуги ABC. Эта точка имеет координаты 
, так как
 2 2 
линии уровня отсекают на осях x1 и x2 равные отрезки, следовательно координаты точки касания равны
( )
( )
2
1 ⋅ cos π 4 =
1 ⋅ sin π 4 =
.
2
Тогда
 2 2
=
fmin x f 
,
 ≈ 2.6.
 2 2 
( )
§ 1.6. Методы безусловной оптимизации
Задачи математического программирования в некоторых случаях можно свести к безусловной минимизации функции f(x), т. е.
поиску локального экстремума этой функции. Если локальный экстремум не является глобальным, то поиск может быть продолжен
с выбором других начальных условий.
а. Методы, использующие только значения функции. В этом
случае используются два класса методов: методы поиска и методы
10
сопряжённых направлений. Все они и их модификации подробно
описаны в соответствующей литературе.
б. Методы, использующие первые производные. Основная идея
этих методов описана в методе Ньютона*. Эти методы называются
в литературе линейными, потому что в разложении f(x) используют
только линейные члены, остальные отбрасываются. Существует довольно много методов (или их модификаций) этого вида. Например:
1) градиентный метод,
2) метод наискорейшего спуска,
3) метод «тяжёлого шарика».
Методы этой группы имеют недостатки, например, информация
из предыдущей итерации не используется в последующей, скорость
сходимости метода сильно зависит от вида функции f(x).
в. Методы переменной метрики. Это вычислительно сложные методы (с точки зрения алгоритма решения). Они используют матрицу
вторых частных производных функции f(x). Достоинством методов
этой группы является то, что они решают задачи большей размерности при вычислении лишь части производных второго порядка по
переменным функции f(x).
г. Методы, использующие вторые частные производные. Фактически – это модификации обобщённого метода Ньютона. Он подробно
описан в литературе. Основной недостаток метода – необходимость
обращения матрицы вторых частных производных функции f(x).
§ 1.7. Характеристика задач стохастического программирования
На практике часто встречаются задачи оптимизации, у которых
исходные параметры являются случайными или неопределёнными. Такие задачи относятся к задачам стохастического программирования [2].
1. Если имеются статистические данные случайных параметров
задачи, позволяющие установить их вероятностные характеристики, то стохастическая задача решается в условиях риска.
2. Если же вероятностные характеристики установить не удаётся, то задача решается в условиях неопределённости.
Все задачи стохастического программирования делятся на одноэтапные, двухэтапные и многоэтапные. В одних задачах решение принимается один раз и в дальнейшем не меняется. Двухэтапные задачи
* Исаак Ньютон (1643–1727) – английский физик, астроном и математик.
11
позволяют уточнять решение по итогам первого приближения. Наконец, многоэтапная задача – фактически находит решение рекуррентным способом (способом последовательных приближений).
Если отклонение в начальных данных задачи приводит к недопустимым последствиям, то такая задача называется жёсткой. Наряду
с задачами в жёсткой постановке существуют задачи с вероятностными ограничениями. В стохастических задачах в отличие от детерминированного случая существенно отличаются понятия допустимого и оптимального решения. В допустимых случаях задача может
не удовлетворять некоторым ограничениям с небольшой величиной
невязки. В таких случаях в целевую функцию включаются штрафы
за невыполнение ограничений, при этом величина штрафов минимизируется. Такая постановка задачи называется нежёсткой.
§ 1.8. Некоторые математические модели задач
стохастического программирования [4]
а) Е-задача. Пусть коэффициенты cj , j = 1.n целевой функции
случайны, а остальные параметры детерминированы. Тогда оптимальное решение находится сведением исходной задачи к детерминированной, где в качестве коэффициентов целевой функции используются матожидания параметров M(cj), j = 1, 2,…, n. Тогда модель имеет вид:

=
M ( f )







n
∑ M ( cj ) xj → min(max),
j =1
n
1,m,
∑ aij xj ≤ bi , i =
(1.8.1)
i =1
xj ≥ 0, j =
1,n.
Если же вероятностные ограничения наложены ещё и на условные неравенства, то математическую модель можно записать в виде
n

=
 M ( f ) ∑ M cj xj → min(max),

j =1


  n
 P  ∑ aij xj ≤ bi  ≥ βi , 0 ≤ β ≤ 1, i =1,m,
  j =1


≥
1,n.
x
j 0, j =

( )
12
(1.8.2)
В общем виде задача (1.8.2) не решена, для конкретного решения
необходимо задать законы распределения величин aij, bi, cj. Если
эти законы заданы они однотипны для всех величин a, b, c, то задача (1.8.2) будет иметь вид
n

=
f ∑ M cj xj → min(max),


j =1
n

1,m,
 ∑ M aij xj + t ( βi ) wi ≤ M ( bi ), i =
 j =1

n
 =
), i 1,m,
∑ σ2 aij x2j + σ2 ( bi =
 wi
j
1
=


xj ≥ 0, j =
1,n.

( )
( )
(1.8.3)
( )
Здесь βi заданный уровень вероятности выполнения i-го ограничения, t(βi) – соответствующая квантиль, t(βi)wi – величина дополнительного ресурса, требуемого для выполнения i-го вероятностного ограничения.
Можно записать ещё несколько формулировок Е-задач.
б) Р-задача. Стохастическая задача в Р постановке формулируется в следующем виде
(
)

P fmin(max) → max,

  n


 P  ∑ aij xj ≤ bj  ≥ βi , i =1,m, 
  j =1


≥
=
0
1,n.
x
,
j

j
(1.8.4)
В этой постановке задачи тоже могут быть различные сочетания
условий дл целевой функции и ограничений.
13
II. ПРОБЛЕМА И ФОРМАЛИЗАЦИЯ ЗАДАЧИ
ПРИНЯТИЯ РЕШЕНИЙ
§ 2.1. Общие положения и формализация задачи
принятия решений
Принятие решений (или выбор) – это действие над множеством
альтернатив, в результате которого это множество уменьшается
вплоть до одной альтернативы, наилучшей по выбранному (принятому) критерию.
Общего алгоритма решения этой задачи нет. Выбор всегда конкретен и в большинстве случаев субъективен.
Выбор может происходить в условиях:
1) определённости, тогда возможны случаи поиска оптимального
решения;
2) неопределённости при данных стохастического типа или полной неопределённости.
Сформулированная задача решается так или иначе только тогда,
когда множество альтернатив не пусто и имеется критерий оценки
каждой альтернативы.
Пусть {χ} – множество альтернатив, {χ}≠∅, а Ф – принцип выбора.
Тогда задачу принятия решений можно записать в виде {{χ}, Ф}→χ∗,
где χ∗ – выбранная (оптимальная) альтернатива. Внешняя среда при
такой процедуре может характеризоваться следующими свойствами.
1) Известны априорные вероятности разных состояний (альтернатив).
2) Известен вид распределений вероятностей состояний, но параметры среды неизвестны, необходима их вероятностная (статистическая) оценка.
3) Состояние среды задано нечётким множеством. На основе этих
данных варианты решения задачи следующие.
а) Оптимальный выбор. {χ} и Ф полностью определены. {{χ}, Ф}→χ∗
находятся по определённому (известному) алгоритму.
б) Просто выбор. Здесь {χ} – определено. Ф – неизвестно (не формализовано). Результат зависит от субъекта, т. е. лица, принимающего решение (ЛПР) и выбирающего критерий Ф. Таким образом,
результат субъективен.
в) Общая задача принятия решения. {χ} – нечёткое множество,
Ф – не определено. К сожалению, это самый распространённый случай в технических задачах. Разные субъекты принимают различ14
ные решения при одинаковых множествах {χ} или рассматривают
разные {χ}1 и {χ}2.
Самая распространённая ситуация – задача в) решается чаще
всего следующим образом.
1) Выбирается или назначается начальное множество альтернатив {χ(0)}, которое
затем итеративно уточняется {χ(0)}→{χ(1)}→…→{χ(n)}.
2) Любая альтернатива χ(i) может быть оценена по объективным
или субъективным критериям, и выбрано более узкое множество
{χ(p)} для дальнейших оценок.
3) Должно существовать некое множество неформализованных принципов выбора {Ф(p)}. В результате будем иметь {χ(0)}→…
→{χ(n1)}→{χ(n2)}→…→{χ(n)}. Это экспертная задача.
§ 2.2. Подходы к принятию решений (принципы выбора) [1, 3]
Как обычно, при решении сложной или плохо формализованной
задачи сначала решается задача декомпозиции, а затем задача композиции. Это принцип системного анализа.
На первом этапе вместо сравнения альтернатив из множества
{χ} сравниваются свойства альтернатив. Это задача иерархической
декомпозиции. Свойства могут также сравниваться различными
способами, например, попарно или на основе выделенных характеристик.
На втором этапе от сравнения свойств переходят к сравнению
самих альтернатив, чьи свойства рассматривались на первом этапе.
Это уже задача композиции.
Пусть Ck{χ(i)} – численная оценка k-го свойства i-ой альтернативы, k = 1,n. Тогда критериальное пространство задачи будет выглядеть следующим образом: C{χ(i)} = {C1{χ(i)}, C2{χ(i)},…, Cm{χ(i)}}. При сравнении двух альтернатив χ(1) и χ(2) предпочтение одной перед другой
выбирается формально из условия Ck{χ(1)}≥Ck{χ(2)}, для всех k = 1,n,
причём хотя бы одно неравенство должно быть строгим.
Графически эта идея иллюстрируется следующим образом (k = 1,
2). Пусть точка, соответствующая i-ой альтернативе, будет началом
координат, тогда если в положительном квадранте этой системы координат не окажется ни одной точки, соответствующей другой альтернативе, то i-я альтернатива не улучшаемая (см. рис. 2.1 а и б).
На рис 2.1, а альтернатива 3 – не улучшаемая, на рис 2.1, б все
четыре альтернативы – не улучшаемые.
15
б)
a)
С2(χ(i))
С2(χ(i))
1
3
2
2
3
1
4
4
С1(χ(i))
С1(χ(i))
Рис. 2.1
Если нет численных оценок переходят к учёту результатов попарного сравнения. Если сравнение возможно для каждой пары
альтернатив по каждому их свойству, то можно все альтернативы
ранжировать по каждому свойству. При этом получается матрица
альтернатив n×m (n-столбцов – число свойств, m-строк – число альтернатив).
Пример 1. Пусть имеются четыре альтернативы χ(1), χ(2), χ(3), χ(4),
каждая с двумя свойствами R1 и R2. Результаты попарного сравнения имеют вид: χ(1)R1χ(4), χ(4)
R1χ(3), χ(3)R1χ(2), χ(4)R2χ(3), χ(3)
С2(χ(i)) 1
R2χ(2), χ(2)R2χ(1). Тогда матрица
4
альтернатив имеет вид:
2
3
3
2
4
1
4
3
Рис. 2.2
2
(i)
1 С1(χ )
 Àëüòåðíàòèâû R1

χ(1)
1


χ(2)
4


(3)
χ
3


χ(4)
2

R2 

4 

3 .

2 

1 
Если опять результаты интерпретировать графически, то
будем иметь следующий рисунок (рис. 2.2). наилучшие альтернативы
здесь 1 и 4. Заметим, что в качестве критерия Ф может быть выбран
при решении общей задачи любой даже субъективный критерий.
Пример 2. Рассмотрим случай, когда распределение вероятностей об элементах состояния среды известны. Пусть P = (p1, p2,…,
16
pn), pj = P(θ = θj), p1 + p2 + … + pn = 1, θj – j-е состояние среды. χ = {χ1, χ1,…,
χm} – m вариантов принятия решений (т. е. альтернатив), θ = {θ1,
θ2,…, θn} – n вариантов состояний среды с известными вероятностями pj = P(θ = θj), Ф = {ϕ1, ϕ2,…, ϕr} – r методов выбора и оценки принятого решения.
Метод выбора численно оценивается функционалом F = {fij}, где
fij – выигрыш либо потеря при принятии решения χi∈χ в состоянии
θj∈θ. Таким образом, ситуация принятия решения характеризуется
тройкой {θ, χ, F}. Матрица значений оценочного функционала будет
иметь вид
 f1,1

f2,1
F =
 ...

 fn,1
f1,2
f2,2
...
fn,2
... f1,m 

... f2,m 
.
... ... 

... fn,m 
Эта матрица или её модификации затем используются в различных критериях принятия решений. Укажем далее некоторые из
них.
§ 2.3. Правила и критерии принятия решений
в условиях неопределённости
Введём разновидность матрицы значений оценочного функционала – матрицу эффективности
→ Ñâîéñòâà
 a11

Aij = ↓
 a21
Àëüòåðíàòèâû  ...

 an1
... a1m 

... a2m 
,
... ... 

... anm 
где по строкам Ai расположены альтернативы i = 1,n, а по столбцам
свойства j = 1,m. aij – элементы, выражающие эффективность системы, т. е. эффективность альтернативы i, по соответствующему
свойству j. Если K(aj) – эффективность j-го свойства, то
1) Критерий среднего выигрыша.
m
Pi aji , i
( ) ∑=
=
K aj
1,n, (2.3.1)
j =1
17
Pi – вероятность i-ой альтернативы. Таким образом, эффективность системы оценивается как матожидание эффективностей по
всем альтернативам. Оптимальной системе будет соответствовать
эффективность
m
=
Kîïò max
=
∑ Pi aji , i 1,n.
j =1
2) Критерий минимакса (критерий Севиджа*).
Этот критерий минимизирует риск. Обозначим
∆K
=
max aj − aji – величину, называемую риском. Тогда
ji
1≤ j ≤m
через
( )
 K=
aj max ∆Kji ,

i


 Kîïò = min  max Kji .
j  i


(2.3.2)
3) Критерий максимакса.
Это самое оптимистическое решение.
( )
 K aj = max ∆Kji , i = 1,n, j = 1,m,

i

Kîïò = max  max Kji .

j  i


(2.3.3)
4) Критерий Лапласа**.
1 n
∑ aji . 1≤ j ≤m n i =1
K = max
(2.3.4)
В этом случае вероятности альтернатив неизвестны и считаются
равновероятными.
5) Критерий Вальда*** (критерий максимина).
K = max min aji . (2.3.5)
1≤ j ≤m 1≤ i ≤n
Этот критерий учитывает наименее благоприятное развитие
каждой альтернативы. Он ориентирован на наихудшие условия,
среди которых и отыскивается наилучший результат.
* Леонард Джимми Севидж (1917–1971) – американский математик и статистик.
** Пьер Симон Лаплас (1749–1827) – французский математик, механик и астроном.
*** Абрахам Вальд (1902–1959) – венгерский математик и статистик.
18
6) Критерий Гурвица*. В нём вводится некоторый коэффициент, называемый «коэффициентом оптимизма», т. е. коэффициент
α (0≤α≤1). В каждом столбце матрицы А есть самая большая оценка
max aji и самая маленькая min aji . Они умножаются на α и 1–α
1≤i ≤n
1≤i ≤n
соответственно и вычисляется их сумма. Оптимальному решению
будет соответствовать решение, на которое приходится максимум
этой суммы, т. е.
( )
K=
aj
max α max aji + (1 − α ) min aji  . 1≤ j ≤m  1≤i ≤n
1≤i ≤n

(2.3.6)
Если α = 0, критерий Гурвица превращается в критерий Вальда.
Это случай крайнего пессимизма. Если же α = 1, то, напротив, получаем случай крайнего оптимизма. Коэффициент α выбирается
субъективно, однако α тем меньше, чем более опасна и неопределённа ситуация.
В литературе можно встретить ссылки и на другие критерии, например, Ходжа-Лемана**, Гермейера***, ММ-критерий, критерий
произведений. Некоторые из этих критериев будут подробнее рассмотрены позднее.
* Адольф Гурвиц (1859–1919) – немецкий математик.
** Вильям Воланс Дуглас Ходж (1903–1975) – английский математик, Рудольф
Леманн (1854–1914) – немецкий математик и астроном.
*** Юрий Борисович Гермейер (1918–1975) – советский математик.
19
III. МЕТОДЫ ОПТИМИЗАЦИИ
§ 3.1. Структура и постановка задачи оптимизации
Формулировку задачи оптимизации формально можно представить таким образом:
1) Представление о параметрах задачи, цели решения и области,
содержащей множество решений.
2) Запись целевой функции как функции параметров задачи.
3) Запись условий, определяющих область допустимых значений
параметров.
Параметры задачи xi , i = 1,n, целевая функция f(x1, x2,…, xn), область допустимых значений xi , i = 1,n определяется либо в виде огра-
( )
( )
ничений (неравенств) gj x ≥ 0, j =
1,m, либо связей hk =
x 0=
, k 1, p
(равенств).
Находится решение
∗
(
x = x1∗ , x2∗ ,..., xn∗
( )
)
T
,
которому соответствует f x ⇒ min(max) при выполнении условий
gj x ≥ 0, j =
1,m, hk =
x 0=
, k 1, p.
а) Условия оптимальности задачи оптимизации.
Типы задач оптимизации определяются условиями оптимальности их решений. Эти условия бывают необходимыми и достаточными.
Необходимое условие (условие А необходимо для выполнения В,
если при выполнении В всегда выполняется А).
Достаточное условие (условие А достаточно для выполнения В,
если при выполнении А всегда выполняется В).
Например, если f(x) имеет в точке x0 экстремум, то f / ( x0 ) = 0 –
необходимое условие. Если же в точке x0 f(x) имеет минимум, то
в окрестности x0 x∈[x0–δ, x0 + δ], δ > 0 выполняется f(x) > f(x0) – достаточное условие.
Имеется пять основных типов вычислительных процедур решения задач оптимизации:
1) Сравнение значений целевой функции на сетке значений аргумента. Оптимальному решению соответствует минимальное
или максимальное значение целевой функции в узлах сетки (см.
рис. 3.1). Шаг сетки может меняться в процессе вычислений.
( )
20
( )
x2
fэкстр
Узлы сетки
Линии уровня
x1
Рис. 3.1
Рис. 3.1
2) Использование необходимых условий экстремума целевой
функции. Обычно это приводит к формированию и решению систем
нелинейных (чаще всего алгебраических) уравнений вида
∂f ( x1, x2 ,..., xn )
= 0=
, i 1,n.
∂xi
3) Использование достаточных условий оптимальности. Чаще
всего формируется вспомогательная задача, множество решений
которой шире множества решений исходной задачи, а критерии оптимальности для этих задач совпадают.
4) Отсечение множества заведомо неоптимальных решений (см.
рис. 3.2). Правила отсечения неоптимальных решений разные для
различных задач оптимизации.
5) Построение оптимизирующей последовательности допустимых решений. Это самый распространённый вариант решения. Вы(0)
бирается одно из допустимых решений x – начальное приближе(1)
ние. Затем строиться последовательность допустимых решений x ,
x
(2)
, …, x
(k)
причём ∆ x
(n +1)
, где x = x
(n)
( ) < f ( x ).
щение ∆ x
(n)
( )
,
D
вы-
( ) > f ( x ),
(n +1)
(n)
(n)
( )
а при поиске maxf x
f x
+ ∆x
при поиске minf x
бирается из условия f x
(n)
(n)
(n +1)
D1
D2
D3
D21
D22
D23
из условия
Чаще всего прира-
является функцией одно-
Рис. 3.2
21
го или нескольких предыдущих приближений, т. е. ∆ x
или ∆ x
(n)
(
=
ϕ x
(n)
,x
(n −1)
).
(n)
( )
=
ϕ x
(n)
§ 3.2. Одномерная и многомерная оптимизация функций
градиентными методами
б) Одномерная оптимизация функций.
К таким методам относятся методы прямого поиска: 1) оптимальный пассивный поиск, 2) метод деления отрезка пополам, 3) метод
Фибоначчи*, 4) метод золотого сечения. Рассмотрим два из них [5].
1) Оптимальный пассивный поиск.
Метод основан на сравнении значений функции f(x), вычисляемых
f(x)
в точках xi , i = 1,n. Все xi – пробные
точки, в них вычисляются значения
f(x1), f(x2),…, f(xn). За fmin принимается точка, в которой f ( xi ) = min f ( xk ).
1≤k≤n
a x1 x2 ...
xn b
(рис. 3.3).
x
Пусть a = x0, b = xn+1, тогда f(xk–
∗
)≥f(x
1
k) и f(xk)≤f(xk+1) если xk = x ,
Рис. 3.3
т. е. x ∈ [ xk−1, xk+1 ].
Отсюда
∗
x − xk ≤ max{xk − xk−1, xk+1 − xk } и x − x ≤ max xi − xi −1 .
1≤i ≤n
Если точки xi расположены на [a, b] равномерно по формуле
∆
, ∆ = b − a, то оценка погрешности будет
xi = a + ih, h =
n +1
∗
b−a
∆
x−x ≤
= .
n +1 n +1
2) Метод золотого сечения.
Термин «золотое сечение» ввёл в употребление Леонардо да
Винч**. Золотым сечением отрезка [a, b] называется такое разбиение его на две части, что отношение длины всего отрезка к длине
его большей части равно отношению длины большей части к длине
меньшей части отрезка, т. е.
* Леонардо Фибоначчи Пизанский (~1170–1250) итальянский математик.
** Леонардо да Винчи (1452–1519) – итальянский художник и учёный.
22
[a,b] = [α,β]
[α,β] [a,α ]
и α= a +
2
3+ 5
( b − a ), β=
a+
2
1+ 5
( b − a ).
При этом точка α осуществляет не только золотое сечение отрезка [a, b], но и отрезка [α, β], т. е.
b − a α − a 1+ 5
= =
.
α−a β−a
2
Аналогично, точка β осуществляет золотое сечение не только отрезка
[a, b], но и отрезка [α, b] (рис. 3.4).
Геометрически ситуация уменьшения исходного отрезка [a, b] на k-м
шаге алгоритма изображена на рис.
3.5. k + 1-я итерация метода золотого
сечения производится следующим
образом:
k
k
α ( ) = a( ) +
k
k
β( ) = a( ) +
2
3+ 5
2
1+ 5
α
a
b
Рис. 3.4
k
a( )
α(
a(
k+1)
k
β( )
k
α( )
a(
k
∆( ) ,
k
∆( ) .
β
k+1)
k+1)
β(
k+1)
α(
k
b( )
k+1)
β(
b(
k+1)
b(
k+1)
k+1)
Рис. 3.5
При этом (см. рис. 3.5) какой бы
из отрезков a( k ) , b( k )  или α( k ) , b( k )  не был выбран за очередной
отрезок локализации, точка x(k+1) (x(k+1 = α(k) или x(k+1) = β(k)) совпадает с одной из точек α(k+1)или β(k+1). Таким образом, на очередном
шаге достаточно вычислить значение функции лишь в одной недостающей точке.
Оценка погрешности метода на k-м шаге равна
2
k
n
n +1
x( ) − x ≤
∆( ) =
∆( ) ,
1+ 5
т. е. метод золотого сечения сходится со скоростью геометрической
прогрессии со знаменателем
2
=
q
≈ 0.62.
1+ 5
в) Методы поиска экстремума функций многих переменных.
23
Все методы этого типа подразделяются на два класса: градиентные и безградиентные [6, 7].
1) Градиентные методы.
В основу градиентных методов положены вычисления и анализ
производных целевой функции. Эти производные, как правило, вычисляются численно, т. е. приближённо. Именно
∂f ( x1, x2 ,..., xn )
∂xi
≈
f ( x1, x2 ,..., xi −1, xi + ∆xi , xi +1,..., xn )
∆xi
.
Градиентом функции f(x1, x2,…, xn) в точке (x1(0), x2(0),…, xn(0)) называется вектор, длина которого равна
(
gradf x1(0) , x2(0) ,..., xn(0)
)
(
 ∂f x(0) , x(0) ,..., x(0)
n
1
1

= ∑
∂xi
i =1 

n
)  .
2



Этот вектор (по длине) равен скорости возрастания целевой функции в исходной точке (x1(0), x2(0),…, xn(0)), а его направление соответствует направлению быстрейшего возрастания целевой функции.
Основная идея всех градиентных методов заключается в следующем: каждая следующая точка minf(x1, x1,…, xn) получается в результате перемещения из предыдущей точки по направлению антиградиента целевой функции (рис. 3.6). Если в результате такого
перемещения f(x1, x1,…, xn) увеличивается, то шаг h уменьшается.
Поиск прекращается, когда, например, gradf x1(k) , x2(k) ,..., xn(k) < ε
или h < ε.
(
x2
f(x1, x2)=4
f(x1, x2)=3
gradf(x1(0) , x2(0) )
f(x1, x2)=2
(x1(0), x2(0))
f(x1, x2)=1
–gradf(x1(0) , x2(0) )
x1
Рис. 3.6
24
)
x2
Постоянный шаг
h1
Переменный шаг
h2
(x1(0), x2(0))
(x1(0), x2(0))
x1
Рис. 3.7
Различают градиентные методы с постоянным и переменным
шагом h (рис 3.7). При использовании методов с переменным шагом
изменение значений x1, x2,…, xn производится по формуле
)
xi(k+1=
xi(k)
−h⋅
(
∂f x1(k) , x2(k) ,..., xn(k)
∂xi
) ,=i
1,n, k= 0,1,2,...
По мере приближения к точке minf(x1, x2,…,xn) абсолютные значения частных производных уменьшаются. Это компенсируется
уменьшением шага h. Градиентный метод имеет несколько распространённых модификаций. Рассмотрим некоторые из них.
1а) Метод наискорейшего спуска.
Этот метод позволяет сокранить общий объём вычислений за
счёт меньшего количества вычислений частных производных целевой функции. Они в этом методе не перевычисляются на каждой
итерации до тех пор, пока не сложится ситуация
(
) (
)
f x1(k+1) , x2(k+1) ,..., xn(k+1) ≥ f x1(k) , x2(k) ,..., xn(k) .
Основные этапы поиска minf(x) методом наискорейшего спуска
таковы:
1) Выбор начального приближения (x1(0) , x2(0) ,..., xn(0) ).
2) Определение значений частных производных целевой функции в этой точке.
3) Изменение значений xi , i = 1,n в соответствии с выражением
(
∂f x1(k) , x2(k) ,..., xn(k)
)
xi(k+1=
xi(k) − h ⋅
(
)
∂xi
gradf x1(k) , x2(k) ,..., xn(k)
)
,=
i 1,n, k
= 0,1,...
25
x2
fmin
(x1(0), x2(0))
x1
Рис. 3.8
4) Если
(
) (
f x1(k+1) , x2(k+1) ,..., xn(k+1) ≥ f x1(k) , x2(k) ,..., xn(k)
)
при n > 0, то начальным приближением становится предыдущая
(k)
точка =
xi(0) x=
i , i 1,n и переходят на пункт 2.
(
) (
)
5) Если f x1(k+1) , x2(k+1) ,..., xn(k+1) ≥ f x1(k) , x2(k) ,..., xn(k) уже при
h
k = 0, то осуществляется дробление шага
=
h
, p > 0 и переходят на
p
пункт 3.
(k)
6) Иначе поиск заканчивается и
=
xi∗ x=
i , i 1,n.
1б) Метод покоординатного спуска.
Этот метод по идее не отличается от предыдущего, но направление к экстремуму происходит поочерёдно по номеру аргумента: по
первому аргументу до начала изменения целевой функции, затем по
второму аргументу и т. д. (рис. 3.8)
Основные этапы в этом методы таковы.
1) Выбор начального приближения (x1(0) , x2(0) ,..., xn(0) ).
2) Выбор направления поиска, т. е. номера аргумента xi, который
подлежит изменению.
3) Вычисление значений
fi/
=
(
∂f x1(k) , x2(k) ,..., xn(k)
)
∂xi
по выбранному аргументу xi. При этом, если fi/ > 0, то f увеличивается если же fi/ < 0, то f уменьшается.
4) Изменение значений аргументов по формуле
26
(
)

 ∂f x(k) , x(k) ,..., x(k) 
n
1
2
 (k+1)


(k)
i 1,n, k= 0,1,...
xi = xi − h ⋅ sign 
,=
∂
x
i






(
k
)
(
k
)
+
1

xj = xj ,=
j 1,2,..., i − 1, i + 1,...,n.

5) Если при текущем шаге в любом из направлений
(
) (
)
f x1(k+1) , x2(k+1) ,..., xn(k+1) ≥ f x1(k) , x2(k) ,..., xn(k) ,
h
то
=
h
, p > 1 и переходят на пункт 4.
p
Все градиентные методы первого порядка обладают следующими недостатками:
1) Они находят только локальный экстремум, ближайший к начальному приближению.
2) Необходимо вычислять fx/ , что увеличивает объём вычислеi
ний и погрешность метода.
3) Застревание алгоритма в «овраге» целевой функции.
§ 3.3. Одномерная и многомерная оптимизация функций
безградиентными методами
1) Безградиентные методы в литературе иногда называются методами нулевого порядка. Можно выделить две группы этих методов.
1) Методы предварительного определения множества допустимых значений аргументов и использование стратегии их перебора
(например, метод сравнения значений целевой функции на сетке
значений аргумента)
2) Методы определения начальных значений аргументов и их последовательного изменения таким образом, чтобы каждая их последующая совокупность приводила либо к меньшему, либо к большему значению целевой функции.
1а) Метод сеток (метод сравнения значений целевой функции на
сетке значений аргументов). Его этапы следующие.
1) Вся область значений аргумента разбивается на отрезки [ai, bi],
( bi − ai )
,
i = 1, 2, …, n, которые делятся на равные части длиной hi =
mi
причём mi выбираются так, чтобы обеспечить одинаковый порядок
чисел hi , i = 1,n (см. рис. 3.9).
27
f(x1, x2)=const
x2
b2
a2
h2
a1
h1
b1
x1
Рис. 3.9
2) Во всех узлах полученной «сетки», т. е. в точках
( a1 + ih1,a2 + jh2 ,...,an + kh=
n ), i
1=
,m1, j 1,m2=
,..., k 1,mn
определяются значения функции f.
3) Выбирается узел сетки, которому соответствует экстремальное значение целевой функции.
4) Если max hi > ε, то вокруг этого узла формируется новая обi =1,n
ласть
ai =xi∗ − hi , bi =xi∗ + hi , i =1,n
и переходят на пункт 2.
Главной проблемой метода является выбор значений mi таких,
чтобы исключить с одной стороны потерю точки экстремума из-за
слишком крупной сетки, с другой стороны обеспечить приемлемый
объём вычислений.
1б) Метод случайных направлений.
В этом методе случайный выбор направления в системе координат x1, x2,…, xn обеспечивается использованием в качестве приращений аргументов xi , i = 1,n случайных чисел p1, p2,…, pn. Величина шага в выбранном направлении будет единичной, если разделить
pi на p =
n
∑ pi2 . При поиске minf(x1, x2,…, xn) метод включает опре-
i =1
деление начальной точки (x1(0) , x2(0) ,..., xn(0) ) и величины рабочего
шага h, выбор случайных чисел p1, p2,…, pn и изменение значений
аргументов целевой функции по формуле
28
x2
p2
p1
p2
(0)
(0)
p1 (x1 , x2 )
x1
Рис. 3.10
)
xi(k+1=
xi(k) − h ⋅
pi
n
,=
i 1,n, k= 0,1,...
∑ p2j
j =1
Если выполняется условие
(
) (
)
f x1(k+1) , x2(k+1) ,..., xn(k+1) < f x1(k) , x2(k) ,..., xn(k) ,
то движение в выбранном направлении с шагом h продолжается.
Если неравенство не выполняется после второго, третьего и т. д. шагов, то определяется новое случайное направление и движение продолжается без смены шага. Если же неудачным оказывается первый же шаг в выбранном направлении, то путём изменения знаков
чисел pi , i = 1,n оно меняется на противоположное, а при повторении ситуации – на новое случайное направление (рис. 3.10). Наконец, величина рабочего шага уменьшается, если
(
) (
f x1(k+1) , x2(k+1) ,..., xn(k+1) < f x1(k) , x2(k) ,..., xn(k)
)
оказывается уже после первого шага в любом из заданного числа
случайных направлений.
Для функции двух переменных f(x1, x2) таких направлений четыре (см. рис. 3.11).
Метод не обеспечивает кратчайшего пути к точке экстремума, но
целевая функция вычисляется единственный раз на каждом шаге
поиска.
29
p2
–p1
p1
p2
–p2
p1
Исходное
направление
–p1
–p2
Противоположное Два перпендикуляр
–
направление
ных направления
Рис. 3.11
1в) Метод деформируемого многогранника (Нелдера* – Мида).
Для f(x1, x2) на плоскости формируется серия правильных треугольников, деформация которых позволяет достичь экстремальной
точки. Делается это следующим образом. В трёх точках исходного
правильного треугольника вычисляется значение целевой функции. Вершина, которой отвечает наибольшее значение функции
исключается, а новая вершина образуется путём симметрического
отражения исключённой вершины. Отражение происходит через
центр тяжести текущего треугольника по формулам

x1(i) = x1(1) + x1(2) + x1(3) − 2x1(i) ,
 ( i)
(1)
(2)
(3)
( i)
x2 = x2 + x2 + x2 − 2x2 , i ∈ [1,2,3].
Процесс перемещения треугольника по плоскости продолжается
до момента, когда значение функции во вновь образованной вершине оказывается наибольшим. В этом случае длина ребра треугольника уменьшается, причём неподвижной остаётся та вершина, которой соответствует наименьшее значение функции (см. рис. 3.12).
x2
6
4
5
3
1, 2, 3 – исходный
треугольник
2
1
(x1(0), x2(0))
x1
Рис. 3.12
* Джон Нелдер (1924–2010) – английский математик и статистик.
30
x1( j) =
x1( j) + x1(k)
, x2( j) =
x2( j) + x2(k)
, j ≠ k, S > 1, S – масштаб уменьS
S
шения. Поиск прекращается в момент выполнения неравенства
max
=i 1,2,3,i ≠ k
{x
(k)
1
}
− x1(i) , x2(k) − x2(i) < ε.
За точку minf(x1, x2) принимается лучшая вершина последнего треугольника.
В n-мерном случае все приведённые формулы приобретают следующий вид. Формируется выпуклый многогранник, имеющий
n + 1 вершину и столько же граней. Если
max
{f ( x
(m) (m)
(m)
1 , x2 ,..., xn
m 1,2,...,n +1
=
)} = f ( x
( j) ( j)
( j)
1 , x2 ,..., xn
),
то положение новой j-ой вершины определяется по правилу
2 n +1
2

xi( j) = ⋅ ∑ xi(m) −  1 +  ⋅ xi( j) , i =1,n.
n m =1
n

Это соответствует отражению худшей вершины через центр тяжести n граней и формированию нового n + 1 – многогранника. Если
во вновь образованной вершине f(k+1) > f(k), то многогранник деформируется, т. е. положение j-й вершины пересчитывается по формуле
xi( j) =
3 (k)  1 3  ( j)
⋅x − −
 ⋅ xi , i = 1,n,
2n i
 2 2n 
где k-я – вершина, которой соответствует наименьшее значение целевой функции.
Поиск экстремума прекращается, когда
max
=j 1,...,n +1,j ≠ k
{x
( j)
i
}
− xi(k) < ε, i =1,n.
В этом методе целевая функция также вычисляется всего один
раз на каждом шаге. Доказано, что движение к экстремуму здесь
очень близко к процессу метода градиентных направлений.
§ 3.4. Методы условной оптимизации [7, 8]
Условная оптимизация – это поиск экстремума функции многих
переменных при наличии ограничений на изменение этих переменных.
31
fmin при g(x1, x2)≥ fmin
x2
fmin
D:g(x1, x2)≥0
g(x1, x2)=0
x1
Рис. 3.13
Основная задача формулируется следующим образом.
Найти вектор
∗
(
x = x1∗ , x2∗ ,..., xn∗
)
T
,
доставляющий min ( max ) f ( x1, x2 ,..., xn ) при условии gj(x1, x2,…,
xn)≥0 (рис. 3.13) причём число m≤n. Самые распространённые (употребительные) методы поиска условного экстремума являются:
1) метод штрафных функций,
2) метод прямого поиска с возвратом,
3) метод возможных направлений,
4) метод сеток.
1а) Метод штрафных функций.
Суть метода заключается в том, что к целевой функции прибавляется так называемая штрафная функция, которая увеличивает
общее суммарное значение при выходе из области ограничений. Таким образом, в методах безусловной оптимизации, в которые переходит метод штрафных функций, рассматривается выражение
F ( x1=
, x2 ,..., xn , λ ) =f ( x1, x2 ,..., xn ) + λϕ ( x1, x2 ,..., xn ),
где ϕ ( x1, x2 ,..., xn ) – штрафная функция, а λ > 0 и выбирается так,
чтобы всюду за пределами области допустимых значений D параметров x1, x2,…, xn выполнялось неравенство
λ
32
∂ϕ ( x1, x2 ,..., xn )
∂xj
>>
∂f ( x1, x2 ,..., xn )
∂xj
, j = 1,n.
y
y=F(x, λ)
g(x)=αx+β=0
D:g(x)≥0
y=f(x)
x
точка min F(x, λ)
Рис. 3.14
Для случая одной переменной геометрически эти условия изображены на рис. 3.14.
Штрафную функцию обычно записывают как сумму функций
ограничений, т. е.
2

  g ( x , x ,..., xn )  , gj < 0,
qj ( x1, x2 ,..., xn ) =   j 1 2
0, gj ≥ 0,

тогда
m
ϕ ( x1, x2 ,..., xn ) =
∑ qj ( x1, x2,..., xn ).
j =1
Если ограничение единственно (как на рис. 3.14), то необходимо
найти минимум функции
2
F ( x=
1, x2 ,..., xn , λ ) f ( x1, x2 ,..., xn ) + k ⋅ λ  g ( x1, x2 ,..., xn )  ,
где
1, g < 0,
=
k 
λ >> 0.
0, g ≥ 0,
Суть метода очень прозрачна. Именно, при выходе за допустимую область D функция ϕ изменяет направление градиента функции F(x1, x2,…, xn, λ) и осуществляет возврат в допустимую область.
Этот возврат осуществляется не оптимально, т. е. не по нормали
к линии ограничений, а под некоторым углом к ней в сторону умень33
Условный экстремум
x2
(x1(0), x2(0))
fmin
(x1(0), x2(0))
D: g(x1, x2)≥
x1
Рис. 3.15
шения значений исходной целевой функции f(x1, x2,…, xn). Метод не
чувствителен к выбору начальной точки.
1б) Метод прямого поиска с возвратом.
Суть этого метода ещё проще, чем предыдущего. При выходе текущей точки при приближении к экстремуму за пределы области
D, вычисления прекращаются, а сама текущая точка принудительно возвращается в область D по направлению векторной суммы градиентов соответствующих функций ограничений gj(x1, x2,…, xn),
j = 1, 2,…, m (рис. 3.15). Этот метод, так же как и предыдущий, не
чувствителен к выбору начальной точки. Таким образом, возврат
в область D выполняется по градиенту функции
m
G ( x1, x2 ,..., xn ) = ∑ dj ( x1, x2 ,..., xn ),
j =2
 gj ( x1, x2 ,..., xn ), gj < 0,
где d ( x1, x2 ,..., xn ) = 
0, gj ≥ 0.

Следовательно, параметры целевой функции должны изменятся
следующим образом
(
∂G x1(k) , x2(k) ,..., xn(k)
)
xi(k+1=
xi(k) + h ⋅
34
∂xj
)
(
(k) (k)
(k)
m  ∂G x1 , x2 ,..., xn

∑
∂xj
j =1 

)




2
.
x2
Ω1
–grad f
Ω0
(x1(i), x2(i))
grad G
g(x1, x2)=0
D: g(x1, x2)≥0
x1
Рис. 3.16
Дробление шага производится в ситуациях, когда значений целевой функции в допустимой области увеличивается. Окончание
вычислений – критерию h < ε.
1в) Метод возможных направлений.
Пусть Ω0 – конус допустимых направлений поиска minf(x1, x2,…,
xn) при условии g(x1, x2,…, xn)≥0, j = 1, 2,…,m. Это все направления,
которые не приводят к выходу из области D в окрестности текущей
точки. Ω1 – конус подходящих направлений – все направления,
вдоль которых функция f(x1, x2,…, xn) убывает в окрестности текущей точки.
Ω0∩Ω1 – конус возможных направлений, т. е. все направления
в окрестности текущей точки, вдоль которых целевая функция f(x1,
x2,…, xn) убывает при выполнении ограничений. Для любой точки
(x1, x2,…, xn), лежащей на поверхности ограничений, в центре конуса Ω1 находится вектор –gradf(x1, x2,…, xn), аналогично в центре
конуса Ω0 – вектор dradG(x1, x2,…, xn), где
m
G ( x1, x2 ,..., xn ) = ∑ dj ( x1, x2 ,..., xn ),
j =2
 gj ( x1, x2 ,..., xn ), gj < 0,
d ( x1, x2 ,..., xn ) = 
0, gj ≥ 0.

Центру конуса возможных направлений будет соответствовать
векторная сумма –gradf и gradG, т. е. направление (рис. 3.16)
35
=
Pi ( x1, x2 ,..., xn )
−
∂f ( x1, x2 ,..., xn )
∂xi
2
∂xi
+
 ∂f ( x1, x2 ,..., xn ) 
 ∂G ( x1, x2 ,..., xn ) 



∑
∂xj
∂xj



j 1 
1=
n
∑
=j
∂G ( x1, x2 ,..., xn )
n
2
,
i = 1,n
В точке условного экстремума f(x1, x2,…, xn) – (x1∗,x2∗,…, xn∗) конус допустимых Ω0 и подходящих Ω1 направлений не пересекаются
(см. рис. 3.16), т. е. конус возможных направлений Ω0∩Ω1 пуст, это
значит, что векторы –gradf и gradG лежат на одной прямой и направлены в разные стороны.
Дробление шага поиска осуществляется, когда движение в центре конуса возможных направлений приводит к возрастанию целевой функции или при этом нарушается одно из ограничений. Обычно шаги в направлении к экстремуму нормализуются, т. е. используется формула
(
∂Pi x1(i) , x2(i) ,..., xn(i)
)
xi(k+1=
xi(k)
+h⋅
(
)
∂xi
)
∂P x(i) , x(i) ,..., x(i)

n
 i 1 2

∑
∂xi 
j =1 


n
2
,=
i 1,n, k= 0,1,...
К сожалению, этот метод чувствителен к выбору начальной точки поиска, ибо за пределами области допустимых значений D возможные направления отсутствуют и алгоритм становится неработоспособным.
1г) Поиск экстремума f(x1, x2,…, xn) при наличии связей.
При наличии связей общая постановка задачи отыскания экстремума целевой функции выглядит
T следующим образом.
∗
Найти вектор x = x1∗ , x2∗ ,..., xn∗ , доставляющий min(nax)f(x1,
x2,…, xn) при условиях hk ( x1, x2 ,..., x=
, k 1, p. Основным метоn ) 0=
дом решения задач подобного типа остаётся метод множителей Лагранжа. С математической точки зрения этот метод решает проблему строго и окончательно.
Метод предусматривает формирование функции Лагранжа
(
36
)
F ( x1=
, x2 ,..., xn , λ ) f ( x1, x2 ,..., xn ) +
p
∑ λk ⋅ hk ( x1, x2,..., xn ),
k =1
где λk = const, k = 1, 2,…, p – множители Лагранжа. Необходимое условие экстремума функции F задаётся следующим образом.
∂F ( x1, x2 ,..., xn )
= 0=
, i 1,n,

∂xi

h x , x ,..., x= 0=
, k 1, p.
n)
 k( 1 2
Тип условного экстремума функции f(x1, x2,…, xn) определяется
знаком полного дифференциала второй степени функции Лагранжа
в точке экстремума, т. е.
n n
d2 F = ∑ ∑ Fx(nx) dxi dxj .
=i 1=j 1
Если d2F < 0, то в тоске
при
d2F > 0 i j
( x1∗,x2∗,...,xn∗ )
T
– условный минимум, при
условный максимум,
d2F = 0 – нет экстремума,
, x2∗ ,..., xn∗ ) – седловая точка.
( x1∗На
практике при решении технических задач метод множителей
T
Лагранжа применяется редко, т. к. обычно нельзя получить выражения частных производных функции F аналитически.
§ 3.5. Задачи линейного программирования [4]
Это задачи предыдущего параграфа со следующей особенностью:
все ограничения – линейные равенства и неравенства, а критерий
оптимальности также линейная функция.
а) Формулировка основной задачи.
Целевая функция или критерий оптимальности в задаче линейного программирования имеет вид
=
F
n
∑ ( cj ⋅ xj ),
j =1
где cj – заданные постоянные коэффициенты значения переменных
xj , j = 1,n должны удовлетворять следующим ограничениям:
37
b1
 a11x1 + a12 x2 + ... + a1n xn =
n

 ........................................ ⇒ ∑ ( aik ⋅ xl ) = bi , i = 1,m, xj ≥ 0, j = 1,n.
a x + a x + ... + a x =
k =1
mn n bm
 m1 1 m2 2
В этих условиях необходимо найти неотрицательное решение системы ограничений, при которых F достигает min(max). В этой задаче m < n, иначе задача может иметь более одного решения. Сама
по себе функция F не имеет экстремумов, поэтому без ограничений
задача лишена смысла. Следовательно, точка экстремума функции
F всегда принадлежит одному или нескольким ограничениям.
Если среди ограничений есть неравенства
n
∑ ( aik ⋅ xk ) ≥ bi ,
k =1
то они превращаются в равенства путём введения дополнительных
неизвестных
n
bi ,
∑ ( aik ⋅ xk ) − xn+i =
k =1
причём переменные xn+i не включаются в целевую функцию.
Степенью неопределённости системы ограничений называют
разность p = n–m.
б) Алгоритм поиска общего решения задачи линейного программирования.
1) Выбираются r базисных неизвестных задачи (r < m, это те неизвестные, при которых определитель системы ограничений не равен
нулю). Остальные неизвестные (n–r – штук) считаются свободными.
2) Система r уравнений с r неизвестными (n–r неизвестных с коэффициентами переносятся в правую часть ограничений) решается.
Решение всегда единственно. В результате получается выражение r
базисных неизвестных через n–r свободных.
3) Свободным неизвестным присваиваются произвольные неотрицательные значения и получаются допустимые решения (x1,
x2,…, xn). Из них выбирается то, по которому получают min(max)F.
в) Геометрическая интерпретация задачи линейного программирования.
При p = 2 решение задачи линейного программирования можно
найти с помощью её геометрического представления.
38
Пример. F = –4x1 + 6x2 + 2x3–4x4 + 7x5 + 3x6⇒min при
4,
2x1 + x2 − x3 =
 x −x +x =
2
4 6,
 1
x + x + x =
2
5 12,
 1
 x +x =
2
6 7,

 xi ≥ 0, i =
1,6,
здесь n = 6, m = 4, p = 2. Матрица коэффициентов системы ограничений имеет вид
 x1

2
1

1
0

x2 x3 x4
1 −1 0
−1 0 1
1 0 0
1 0 0
x5
0
0
1
0
x6 

0
0 .

0
1 
Минор
x3 x4
−1 0
0 1
0 0
0 0
x5
0
0
1
0
x6
0
0 =−1 ≠ 0,
0
1
таким образом, x3, x4, x5, x6 – базисные переменные, а x1 и x2 – свободные. Тогда
x1 ≥ 0,

x3 =−4 + 2x1 + x2 , 
x2 ≥ 0,


 x4 =6 − x1 + x2 ,

2
x
+
 x = 12 − x − x ,
 1 x2 − 4 ≥ 0,
1
2 ⇒
 5

 6 − x1 + x2 ≥ 0,
x6= 7 − x2 ,

12 − x1 − x2 ≥ 0,
 xi ≥ 0,i =

1,6.
 7 − x2 ≥ 0.
Последняя система неравенств относительно свободных переменных определяет множество пар (x1 x2), каждой из которых соот39
x2
x6 =7–x2 =0
7
x3 =12 –x1–x2 =0
x1=0
1
–2
D
x4 =12–x1 +x2 =0
x3 =2x1 +x2–4=0
1
x2=0
6
x1
F=79
Рис. 3.17
ветствует четвёрка неотрицательных значений базисных переменных (x3, x4, x5, x6). Все прямые ограничений делят плоскость на две
части, в одной из них ограничения выполняются, в другой нет. В результате получена область допустимых значений D. Целевая функция, выраженная через свободные переменные, F = 73–3x1–6x2. Это
тоже система параллельных прямых на плоскости (x1 x2). Значений F уменьшается по направлению стрелки (рис. 3.17). Наименьшее значение F достигает в точке M(x1 = 5, x2 = 7) и F(5, 7) = 16. Тогда
x1 = 5, x2 = 7, x3 = 13, x4 = 8, x5 = 0, x6 = 0.
Область D в задаче линейного программирования представляет
собой выпуклый многогранник. Если задача не имеет решения, то
D = ∅, если решение лежит на одной из граней, то задача имеет множество решений.
г) Симплекс-метод решения задачи линейного программирования.
Решение основной задачи линейного программирования, соответствующее одной из вершин многогранника допустимых решений, называется опорным. В каждом из них не менее p неизвестных
равных нулю. Оптимальное решение совпадает с одним из опорных.
Общий алгоритм решения задачи линейного программирования
таков – найти все опорные решения и выбрать из них лучшее с точки зрения целевой функции.
40
Симплекс-метод организует упорядоченный перебор опорных
решений, начиная с некоторого начального. Алгоритм решения по
симплекс-методу таков:
1) Найти произвольные опорные решения задачи и выразить целевую функцию через свободные неизвестные. Если F⇒min и все
коэффициенты в формуле F положительны, то найденное решение – оптимальное.
2) Если решение не оптимальное, то надо перейти к соседнему
опорному решению. Для этого
а) свободная неизвестная, имеющая в выражении для F отрицательный коэффициент, переводится в базисные переменные,
б) в число свободных переменных переводится базисная неизвестная, которая раньше других обращается в нуль при увеличении
свободной неизвестной, переводимой в базисные.
Пункт 2) выполняется до тех пор, пока не будет получено оптимальное решение. Недостаток этого алгоритма – неизвестно как получить исходное опорное решение.
Рассмотрим теперь предыдущий пример. Пусть начальное опорное решение x1 = x2 = 0, т. е. x1 и x2 – свободные переменные, а x3, x4,
x5, x6 – базисные. Тогда
x3= 2x1 + x2 − 4 ≥ 0,
 x =6 − x + x ≥ 0,
 4
1
2

x
=
12
−
x
−
x
1
2 ≥ 0,
 5
 x6 =7 − x2 ≥ 0.
Решение не допустимо, т. к. при x1 = x2 = 0, x3 = –4 < 0.
Пусть теперь x2 и x4 – свободные, а x1, x3, x5, x6 – базисные переменные. Тогда
 x1 =6 − x4 + x2 ≥ 0,
x =+
 3 8 3x2 − 2x4 ≥ 0,

 x5 =6 − 2x2 + x4 ≥ 0,

x6 =7 − x2 ≥ 0.
Здесь все ограничения выполняются, а F = 55–9x2 + 3x4 = 55. Это
не оптимальное решение, так как F можно уменьшить, увеличивая
x2. Переведём x2 в в число базисных переменных. При x4 = 0 и увеличении x2 раньше других неизвестных обращается в нуль x5 (при
x2 = 3). Переведём x5 в свободные переменные. Тогда x4 = x5 = 0,
41
x
x

9 − 4 + 5 ≥ 0,
 x1 =
2
2

x
x
 x =
3 + 4 − 5 ≥ 0,
 2
2
2

x
x =17 − 4 − 1.5x ≥ 0,
5
 3
2

x
x
 x6 =
4 − 4 + 5 ≥ 0.
2
2

F = 28–1.5x4 + 4.5x5. Опять F можно уменьшить, переведя x4 в базисные переменные. При x5 = 0 раньше других обращается в нуль
x6 (при x4 = 8), т. е. x6 переходит в свободные переменные. Теперь
x5 = x6 = 0,
 x1 =5 − x5 + x6 ≥ 0,

x2 =7 − x6 ≥ 0,


x3 =13 − 2x5 + x6 ≥ 0,
 x6 =8 + x5 − 2x6 ≥ 0.
и F = 16 + 3x5 + 3x6. Таким образом, больше F не может быть уменьшено, т. е. найдено оптимальное решение. Fmin = 16, x1 = 5, x2 = 7,
x3 = 13, x4 = 8, x5 = x6 = 0.
§ 3.6. Лабораторная работа №1.
Одномерная оптимизация функций.
1а) Необходимые условия минимума и локализация отрезка
минимизации исходной функции.
Рассмотрим функцию одного переменного y = f(x). В задаче одномерной минимизации её называют целевой функцией. Пусть
x∈X = (–∝, + ∝).
Точка x∈X называется точкой глобального минимума, если
∀x∈X выполняется неравенство f ( x ) ≤ f ( x ). Точка x∈X называется точкой локального минимума, если существует δ – окрестность
точки x, такая, что ∀x∈δ выполняется неравенство f ( x ) ≤ f ( x ) (рис.
3.18).
Здесь x5 и x6 – глобальные экстремумы на [a, b], x1, x2, x3, x4 –
локальные экстремумы на [a, b]. Необходимым условием точки
локального экстремума является выполнение равенства f ′ ( x ) = 0.
42
y=f(x)
x2
a
x1
x6
x3 x4
x5
b
Рис. 3.18
Точка x в этом случае называется стационарной точкой функции
y = f(x).
Большинство алгоритмов минимизации осуществляют лишь
поиск точки локального минимума функции y = f(x). Но чтобы применять подобный алгоритм, вначале надо найти отрезок [a, b], содержащий точку x – точку локального минимума. Этот отрезок
называется отрезком локализации точки x . Не существует общих
методов, позволяющих для любой f(x) найти этот отрезок. В каждом конкретном случае он ищется индивидуальным способом.
Если на отрезке [a, b] существует единственная точка локального
экстремума, то f(x) на отрезке [a, b] называется унимодальной. Унимодальные функции при этом не обязательно должны быть строго
непрерывными (см. рис. 3.19).
Теорема 3.1. Если для ∀x∈[a, b] f ′′(x) > 0, то f(x) унимодальна на
[a, b].
Для сужения отрезка локализации точки минимума унимодальной функции справедлива следующая теорема:
Теорема 3.2. Пусть f(x) унимодальна на [a, b] и a≤α < γ < β≤b. Тогда:
1) если f(α)≤f(β), то x ∈ a,β  ;
2) если f(α)≥f(β), то x ∈ α, b  ;
f(x)
3) если f(α)≥f(γ) и f(γ)≤f(β), то то
x ∈ α,β  .
Выводы этой теоремы вполне очевидны при рассмотрении условий
и следствий на рисунке (рис. 3.19).
В общем случае для любой функции y = f(x) неизвестно, является ли
x1
x2
она унимодальной на [a, b]. В таких
Рис. 3.19
случаях для локализации точки x
43
f(x)
xi+1–xi=h
x2
x3
x4
x1
Рис. 3.20
используют различные нестрогие методы. Например, вычисляют и сравнивают значения f(x0) и f(x1), где x1 = x0 + h.
Если f(x0) > f(x1), то последовательно
вычисляют значения функции в точках xk = x0 + 2k–1·h, k≥2. После обнаружения первой же точки, где f(xk)≤f(xk+1)
за отрезок локализации принимают
[xk–1, xk+1] (рис. 3.20).
1б) Методы прямого поиска. Оптимальный пассивный поиск.
Этот метод основан на сравнении значений функции f(x), вычисляемых в точках x1, x2,…,xn. Метод называется методом прямого
поиска, а точки xi – пробными точками.
Пусть x∈X и x1, x2,…,xn – пробные точки. Вычисляем значения
f(x1), f(x2),…, f(xn). За fmin принимается та точка xi, для которой
f ( xi ) = min f ( xk ). Геометрическая интерпретация метода показа1≤k≤n
на на рис. 3.3. Пусть a = x0, b = xn+1, тогда f(xk–1)≥f(xk) и f(xk)≤f(xk+1),
если xk = x ∗ , то есть x ∈ [ xk−1, xk+1 ]. Отсюда
x − xk ≤ max{xk − xk−1, xk+1 − xk } и x − x ∗ ≤ max xi − xi −1 . (3.6.1)
1≤i ≤n
Если точки x1, x2,…,xn расположены на отрезке [a, b] равномерно
∆
, ∆ = b–a, то метод с тав соответствии с формулой xi = a + ih, h =
n +1
ким выбором кратных точек называется оптимальным пассивным поиском. Оценка погрешности этого метода имеет вид:
b−a
∆
x − x∗ ≤
= .
(3.6.2)
n +1 n +1
1в) Методы прямого поиска. Метод деления отрезка пополам
В этом методе используется принцип последовательного сокращения отрезка локализации, основанной на следующей очевидной
теореме.
Теорема 3.3. Если функция f(x) унимодальна на отрезке [a, b], то
она унимодальна и на любом отрезке [c, d]⊂[a, b].
Пусть [a, b] = [a(0), b(0)].
1. Найдём две симметрично расположенные точки
=
α( )
0
44
0
0
0
0
a ( ) + b( )
a ( ) + b( )
0
=
− δ, β( )
+ δ,
2
2
b−a
– параметр метода.
2
2. Находим f(α(0)), f(β(0)). Если f(α(0))≤ f(β(0)), то
где 0 < δ <
1
1
a( 0 ) ,β( 0 )  ,
x ∈  a ( ) , b( )  =

 

если же f(α(0)) > f(β(0)), то
1
1
 α ( 0 ) , b( 0 )  .
x ∈  a ( ) , b( )  =

 

Эта процедура принимается за очередную итерацию метода деления отрезка пополам. k – ая итерация имеет вид:
1. Находят
=
α( )
k
k
k
k
k
a ( ) + b( )
a ( ) + b( )
k
=
− δ, β( )
+ δ.
2
2
2. Находят f(α(k)), f(β(k)).
3. Отрезок локализации
f(α(k))≤f(β(k)), то
определяют
по
правилу:
если
+1)   ( k ) ( k ) 
a( k+1) , b( k=
a ,β
;

 

если же f(α(k)) > f(β(k)), то (см. рис. 3.21)
a( k+1) , b( k+1)  = α( k ) , b( k )  .

 

k +1
k
k +1
k
В первом случае x ( ) = α( ) , во втором случае x ( ) = β( ) . Если
(n)
(n)
(n)
(n)
(n)
обозначить через ∆ = b –a длину отрезка [a , b ], то справедливо равенство
(n )
n +1) ∆
∆( =
+ δ.
2
a(
k)
α(
a(
a(
k+1)
α(
k+1)
k+1)
β(
k)
β(
α(
k+1)
k+1)
k)
β(
b(
b(
k+1)
b(
k)
k+1)
k+1)
Рис. 3.21
45
Поэтому, если δ мало (δ < ∆(n)), то длина вновь полученного отрезка
почти вдвое меньше предыдущего. Отсюда происходит название метода.
С помощью метода математической индукции можно доказать,
что
(n ) ∆ − 2δ + 2δ. (3.6.3)
∆=
2n
1г) Минимизация функций одного переменного в пакете
Mathcad [5]
В этой лабораторной работе на примере функции y = x3–x + e–x
реализованы формулы предыдущих разделов. Все формулы очень
просты и их применение в тексте лабораторной работы очевидно.
Также просты и используемые программные единицы, реализующие отдельные алгоритмы по этим формулам.
ORIGIN: = 1
Оптимальный пассивный поиск
3
f ( x) := x − x+exp( −x)
a: = 0 b: = 1 ∆: = b–a ∆ = 1 delta: = 10^(–2)
i: = 1..100 xi: = –0.01 + 0.01*i yi: = f(xi)
ymin: = min(y) ymin = 0.14
ymax: = max(y) ymax = 1
xmin: = min(y) xmin = 0
40
f(x) 20
0
−5
0
x
ymax: = max(y) ynax = 0.99
46
5
1
x=
1
1
0
1
1
2
0.01
2
0.98
3
0.02
3
0.96
4
0.03
4
0.94
5
0.04
5
0.921
6
0.05
6
0.901
7
0.06
7
0.882
8
0.07
8
0.863
9
0.08
9
0.844
10
0.09
10
0.825
11
0.1
11
0.806
12
0.11
12
0.787
13
0.12
13
0.769
14
0.13
14
0.75
15
0.14
15
0.732
16
y=
...
16
...
Метод деления отрезка пополам
Loki( a , b , fa , fb , delta) :=
alfa0 ←
( a + b)
− delta
2
beta0 ←
( a + b)
+ delta
2
fa1 ← f ( alfa0)
fb1 ← f ( beta0)
if fa1 > fb1
a1 ← alfa0
b1 ← b
if fa1 ≤ fb1
a1 ← a
b1 ← beta0
 a1 
 
 b1 
47
x1: = delotrpopolam(0,1,delta) x1 = 0.705
i = 1..100 xi: = -5.02 + 0.02*i yi: = f(xi)
1
1
x=
1
- 5
1
28.413
26.948
2
-4.98
2
3
-4.96
3
25.53
4
-4.94
4
24.156
5
-4.92
5
22.827
6
-4.9
6
21.541
7
-4.88
7
20.296
8
-4.86
8
19.093
9
-4.84
9
17.929
10
-4.82
10
16.805
11
-4.8
11
15.718
12
-4.78
12
14.669
13
-4.76
13
13.656
14
-4.74
14
12.678
15
-4.72
15
11.734
16
y=
...
16
x2: = delotrpopolam(-5,-3,delta) x2: = -3.678
Метод фибоначчи
B1: = 1 B2: = 1 i: = 3..100 Bi: = Bi–1 + Bi–2
48
...
Fib1: = Fibb(5) Fib1 = 8
ε: = 10–2 a = 0 b = 1 ε = 0.01
xx: = MetodFibb(a,b,ε) xx = 0.712
a: = -5 b: = -3
xx1: = MetodFibb(a,b,ε) xx1 = -3.679
1
B=
1
1
2
1
3
2
4
3
5
5
6
8
7
13
8
21
9
34
10
55
11
89
12
144
13
233
14
377
15
610
16
...
49
Метод золотого сечения
50
a: = 0 b: = 1
a = 0 b = 1 ε = 0.01
xx2: = ZolotS(a,b,ε) xx2 = 0.712
a: = -5 b: = -3
xx3: = ZokotS(a,b,ε) xx3 = -3.682
Задание № 1. Выбрать функцию по номеру своего варианта из
следующей таблицы и найти её локальные минимумы по четырём
разобранным методам.
Номер
варианта
Функция
Номер
варианта
Функция
1
1
y=
− 1 − x2 + e x
2
6
y=
−1.2x + 0.8x2 + sin 2x
2
=
y xex + sin x
7
3
y =x2 + 5 ( x − sin x )
(
)
2
8
y = x2 e
−
x
5
y=
x2 + tan ( x + 0.1)
51
Номер
варианта
Функция
Номер
варианта
Функция
4
y=
−4 1 − x2 + ex
9
y =x + x2 + cos ( x − 1)
5
1
y = x2 e − x
2
10
y = x2 e− x + cos ( x + 0.5 )
(
)
1д) Минимизация функций одного переменного в пакете Matlab
Как всегда, для пакета Matlab приведём сначала тексты всех подпрограмм, используемых в головной программе. Все приведённые
подпрограммы являются полными аналогами соответствующих
подпрограмм из пакета Mathcad, кроме самой первой (см. пункт 1г).
Первая подпрограмма вычисляет заданную функцию, минимум которой ищется.
function yy = fx(x)
yy=x^3-x+exp(-x);
end
function [a1,b1]=Loki(a,b,fa,fb,delta)
alfa0=(a+b)/2-delta;
beta0=(a+b)/2+delta;
fa1=fx(alfa0);
fb1=fx(beta0);
if fa1>fb1
a1=alfa0;
b1=b;
end;
if fa1<=fb1
a1=a;
b1=beta0;
end;
end
function x=delotrpopolam(a,b,delta)
k=1/(10*delta);
a1=a;
b1=b;
for i=1:k
fa1=fx(a1);
fb1=fx(b1);
[a2,b2]=Loki(a1,b1,fa1,fb1,delta);
a1=a2;
b1=b2;
52
x=(a1+b1)/2;
end;
end
function Bn=Fibb(n)
if (n==1) or (n==2)
Bn=1;
end;
if n==3
Bn=2;
end;
B(1)=1;
B(2)=1;
for i=3:n+1
B(i)=B(i-1)+B(i-2);
end;
Bn=B(n+1);
end
function x=MetodFibb(a,b,eps)
m=1/eps;
d(1)=b-a;
n=1;
for i=3:m
B=Fibb(i);
a1=d(1)/B;
if a1>eps
n=i-1;
end;
end;
alf=a+d(1)*Fibb(n-1)/Fibb(n+1);
bet=a+d(1)*Fibb(n)/Fibb(n+1);
fa(1)=fx(alf);
fb(1)=fx(bet);
ak(1)=a;
bk(1)=b;
for i=1:n
k=i-1;
k0=n-k;
k1=k0–1;
k2=k0+1;
if fa(i)>fb(i)
ak(i+1)=alf;
bk(i+1)=bk(i);
d(i+1)=bk(i+1)-ak(i+1);
alf=bet;
bet=ak(i+1)+d(i+1)*Fibb(k0)/Fibb(k2);
fa(i+1)=fb(i);
fb(i+1)=fx(bet);
53
end;
if fa(i)<=fb(i)
ak(i+1)=ak(i);
bk(i+1)=bet;
d(i+1)=bk(i+1)-ak(i+1);
bet=alf;
alf=ak(i+1)+d(i+1)*Fibb(k1)/Fibb(k2);
fa(i+1)=fx(alf);
fb(i+1)=fa(i);
end;
epsilon=bet-alf;
if epsilon<eps
break;
end;
end;
x=(alf+bet)/2;
end
function x=ZolotS(a,b,eps)
m=1/eps;
d(1)=b-a;
a1=2/(3+sqrt(5));
a2=2/(1+sqrt(5));
alf=a+a1*d(1);
bet=a+a2*d(1);
ak(1)=a;
bk(1)=b;
fa(1)=fx(alf);
fb(1)=fx(bet);
for i=1:m
if fa(i)>fb(i)
ak(i+1)=alf;
bk(i+1)=bk(i);
d(i+1)=bk(i+1)-ak(i+1);
alf=bet;
bet=ak(i+1)+a2*d(i+1);
fa(i+1)=fb(i);
fb(i+1)=fx(bet);
end;
if fa(i)<=fb(i)
ak(i+1)=ak(i);
bk(i+1)=bet;
d(i+1)=bk(i+1)-ak(i+1);
bet=alf;
alf=ak(i+1)+a1*d(i+1);
fa(i+1)=fx(alf);
fb(i+1)=fa(i);
end;
epsilon=bet-alf;
54
if epsilon<eps
break;
end;
end;
x=(alf+bet)/2;
end
Далее следует текст основной программы.
>>
>>
>>
>>
>>
%ОПТИМАЛЬНЫЙ ПАССИВНЫЙ ПОИСК
clear
x=-4.0:0.1:1.0;
y=x.^3-x+exp(-x);
plot(x,y,’-*r’),grid
>> for i=1:100
x1(i)=-0.01+0.01*i;
y1(i)=fx(x1(i));
end;
>> ymin=min(y1)
ymin=0.1396
>> x=0.700
>> %МЕТОД ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ
>> delta=10^(-2);
>> x1=delotrpopolam(0,1,delta)
x1 =0.7053
>> x2=delotrpopolam(-5,-3,delta)
x2 =-3.6781
>> %МЕТОД ФИБОНАЧЧИ
>> a=0;
>> b=1;
>> xx=MetodFibb(a,b,eps);
>> disp(xx)
0.7118
55
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
a=-4;
b=-3;
xx1=MetodFibb(a,b,eps);
disp(xx1)
-3.6701
%МЕТОД ЗОЛОТОГО СЕЧЕНИЯ
a=0;
b=1;
xx2=ZolotS(a,b,eps);
disp(xx2)
0.7123
a=-4;
b=-3;
xx3=ZolotS(a,b,eps);
disp(xx3)
-3.6697
Задание № 2. Выбрать из таблицы на стр. 1–52 свой вариант,
предварительно увеличив его номер на 5, и найти все локальные
минимумы данной функции.
§ 3.7. Лабораторная работа №2.
Многомерная оптимизация функций [6, 7]
В этой работе рассмотрим по одному методу поиска экстремума
функции многих переменных группы градиентных (метод покоординатного спуска) и безградиентных (метод деформированного
многогранника) методов. Суть методов изложена в § 3.2, пункт 1б и
§ 3.3, пункт 1в. Для лучшего понимания текстов приведённых программ в пакетах Mathcad и Matlab приведём подробные алгоритмы
этих методов.
Алгоритм метода покоординатного спуска.
1. Задаётся точность вычислений ε, начальный шаг h0, минималь(0)
но допустимый шаг hmin, точка начального приближения x ∈ R n ,
( ),k = 0.
порядковый номер итерации k = 0 и вычисляется f x
(k)
( ),k =k + 1,i =0.
3. Начинается поиск параллельно оси Ox : i = i + 1, если i > n, то
2. Запоминается f x
(k)
i
переходят к п.10, иначе к п.4
4. Задаётся h = h0 и знак sign = 1.
5. Вычисляется xi( j +1) по формуле xi( j +1) =xi( j) + sign ⋅ h и значе-
(
ние функции в новой точке f x
56
( j +1)
).
6. Если новое значение функции меньше предыдущего, то
( j)
( j +1)
≡ xi( j +1) , f x
≡f x
и переход на п.5, иначе знак sign ме-
( ) (
xi( j)
)
няется на противоположный.
7. Если sign < 0, то переход на п.5, иначе на п.8.
8. Уменьшается величина шага h, h(j+1) = 0.1⋅h(j).
9. Если текущий шаг h < hmin, то переход на п.3, иначе определяется знак sign и на п.5.
10. Проверяются условия достижения заданной точности
(
f x
(k +1)
) − f (x ) < ε
(k)
и если они выполняются, переход на п.11, иначе на п.2.
11. Вычисления завершаются. За точку минимума принимается
последнее значение
x
(k)
( )
( ).
,min f x = f x
(k)
Алгоритм метода Нелдера-Мида.
Параметры: α > 0 – коэффициент отражения (α = 1), β > 0 – коэффициент сжатия (β = 0.5), γ > 0 – коэффициент растяжения (γ = 2).
Пусть
(x
(k)
(k) (k)
, xi ,..., xi(k)
i1
2
m
xi=
– i-я вершина
в Rn
) =,i
T
1,n + 1
на k-м шаге поиска k = 0, 1, 2,…,
( ) = max{f ( x ,x ,...,x )},
где x = x
и f ( x ) = min {f ( x , x ,..., x )}. Пусть также
x – центр тяжести всех вершин многогранника в R . Координаты
(k)
f xh
(k)
h
(k)
l
(k)
i
(k)
1
(k)
1
(k)
2
(k)
2
(k)
n +1
(k)
n +1
n+2
n
этого центра
x
(k)
n +2,j =

1  n +1 (k) 
(k)
 ∑ xij  − xhj
 , j = 1,n.

n  i =1



Над симплексом могут выполняться следующие четыре операции.
1. Отражение – проектирование xh(k) через центр тяжести по
формуле
57
(
)
(k)
(k)
(k)
(k)
xn=
+3 xn +2 + α xn +2 − xh .
(
) ( )
2. Растяжение. Если f xn(k+)3 ≤ f xl(k) , то вектор
растягивается по формуле
(
(x
(k)
n +3
− xn(k+)2
)
)
(k)
(k)
(k)
(k)
xn=
+4 xn +2 + γ xn +3 − xn +2 .
(
) ( )
)
если же f xn(k+)4 < f xl(k) , то xh(k) заменяется на xn(k+4
и процедура
продолжается снова с п.1 при k = k + 1. В противном случае xh(k) за)
меняется на xn(k+3
и осуществляется переход к п.1 при k = k + 1.
3. Сжатие. Если f xn(k+)3 > f xl(k) для всех i≠h, то вектор
xh(k) − xn(k+)2 сжимается по формуле
(
(
)
) ( )
(
)
(k)
(k)
(k)
(k)
x=
n +5 xn +2 + β xh − xn +2 .
)
Затем xh(k) заменяется на xn(k+5
и происходит возврат к п.1 на
k + 1-ом шаге.
1,n + 1
4. Редукция. f xn(k+)3 > f xh(k) все векторы xi(k) − xl(k) , i =
уменьшаются в два раза с отсчётом от xl(k) по формуле
(
) ( )
(
(
)
)
xl(k) = xl(k) + 0.5 ⋅ xi(k) − xl(k) , i = 1,n + 1.
Затем происходит возврат к п.1 на k + 1-ом шаге.
5. Критерий окончания поиска выглядит следующим образом
1
2
2
 1 n +1 
f xi(k) − f xn(k+)2   ≥ ε,

∑


 
 n + 1 i =1 
( ) (
)
)
где xn(k+2
– центр тяжести на k-м шаге.
1а) Многомерная оптимизация в пакете Mathcad.
Метод покоординатного спуска
ORIGIN := 1
ORIGIN := 1
2 −1
f ( x) := −2.8 ⋅ 0.9 + 2.5 ( x1 − 1.1) 2 + 0.38 ⋅ ( x2 + 1.9) 2 −− 11
f ( x) := −2.8 ⋅ 0.9 + 2.5 ( x1 − 1.1) 2 + 0.38 ⋅ ( x2 + 1.9) 2
f ( x) := −2.8 ⋅ 0.9 + 2.5 ( x1 − 1.1 ) + 0.38 ⋅ ( x2 + 1.9 ) 
2
−1
f2 ( x1 , x2 ) := −2.8 ⋅ 0.9 + 2.5 ( x1 − 1.1) 2 + 0.38 ⋅ ( x2 + 1.9) 2 − 1
f2 ( x1 , x2 ) := −2.8 ⋅ 0.9 + 2.5 ( x1 − 1.1 ) + 0.38 ⋅ ( x2 + 1.9 ) 
Ïðîãðàììà âû÷èñëåíèÿ ÷èñåë Ôèáîíà÷÷è
2
58
2
Программа вычисления чисел Фибоначчи
Fibb ( n) :=
Bn ← 1
return
(n
Bn
if
Bn
if n
1) ∨ ( n
2)
Bn ← 2
return
3
B1 ← 1
B2 ← 1
for
i ∈ 3 ..
n+1
Bi ← Bi−1 + Bi−2
Bn ← Bn+1
Bn
Программа минимизации функции одного переменного методом
Фибоначчи
Fibonachi ( a , b , f , v , F , n , j ) :=
while 0 < 1
i←1
v2 ← v
v1 ← v
v1
v2
←a+
rows ( v ) + 1− j
←a+
F
⋅ ( b − a)
F
n− i
F
⋅ ( b − a)
n
rows ( v ) + 1− j
a ← v1
rows ( v ) + 1− j
if f ( v1)
n− ( i+ 1)
n
rows ( v ) + 1− j
b ← v2
F
if f ( v1) < f ( v2)
if f ( v1) > f ( v2)
f ( v2)
a ← v1
rows ( v ) + 1− j
b ← v2
rows ( v ) + 1− j
i←i+ 1
break if
v
v1
rows ( v ) + 1− j
rows ( v ) + 1− j
←
v1
rows ( v ) + 1− j
− v2
rows ( v ) + 1− j
< 0.0001
+ v2
rows ( v ) + 1− j
2
Программа метода покоординатного спуска
Koord_spusk ( a , b , f , v , F) :=
for i ∈ 1 .. 20
for j ∈ 1 .. rows ( v)
vrows( v) +1−j ← Fibonachi ( a , b , f , v , F , 20 , j)
F_Min ← f ( v)
v
v
59
x1 := 0
x2 := 0
0 

0 
x =
i := 1 ..
20
Fi := Fibb ( i)
Minimum := Koord_spusk ( 0 , 50 , f , x , F)

Minimum = 
1.1
 1.49 × 10
i := 1 ..
50
j := 1 ..
50
−4



x1 i := −1 + 0.1 ⋅ i
x2 j := −5 + 0.1 ⋅ j
ff i , j := f2 ( x1 i , x2 j)
f1 ( v) :=
1 
2
⋅ 5 ⋅ ( v1) + 1 ⋅ v1 ⋅ v2 + 1 ⋅ v1 ⋅ v2 + 5 ⋅ ( v2) 2 − ( 10 ⋅ v1 + 1 ⋅ v2)
2
v1 = 2
v2 = 2
2 

2 
v := 
Minimum := Koord_spusk ( −20 , 100 , f1 , v , F)
 2.042 

 −0.208 
Minimum = 
f1 ( Minimum ) = −10.104
60
ff
ff
Метод деформируемого многогранника (Нелдера – Мида).
ORIGIN := 1
2
f ( y) := 4 ⋅ ( y1 − 5) + ( y2 − 6)
:= 1 β := 0.5
 60 
x0 := 

 −34 
α
ε
γ
2
:= 2
:= 0.0000001
n := 2
t := 1
Программа метода Нелдера – Мида
NelderMid( x0 , n , t , α , β , γ , ε , f ) :=
t
d1 ←
n⋅ 2
t
d2 ←
n⋅ 2
⋅( n + 1 + n − 1)
⋅( n + 1 − 1)
〈〉
x 1 ← x0
for i ∈ 1 .. n
for j ∈ 2 .. n + 1
xi , j ← d1 + x0i if j
i+ 1
xi , j ← d2 + x0i otherwise
fin← 1 + ε
t←0
while fin > ε
L← 1
t←t+ 1
61
h← 1
for i ∈ 2 .. n + 1
( )
( )
〈 〉
〈〉
L ← i if f x L > f x i
xi , j ← d2 + x0i otherwise
fin← 1 + ε
t←0
while fin > ε
L← 1
t←t+ 1
h← 1
for i ∈ 2 .. n + 1
( ) ( x〈i〉 )
( ) ( x〈i〉 )
〈L〉
L ← i if f x
> f
〈h〉
h ← i if f x
< f
1 
〈 〉
x n+2 ← ⋅
n 
〈〉
〈 〉
xi −xh
n+1
∑


 i = 1
(
( )


〈n+3〉
〈 〉
〈 〉
〈〉
← x n+2 + α ⋅ x n+2 − x h
x
〈 〉
〈 〉
if f x n+3 < f x L
(
)
(
)
)
( )
〈 〉
〈 〉
〈 〉
〈 〉
x n+4 ← x n+2 + γ ⋅ x n+3 − x n+2
〈h〉
〈n+4〉
〈n+4〉
〈L〉
x ←x
if f x
< f x
〈h〉
〈n+3〉
x ←x
otherwise
〈h〉
〈n+3〉
〈n+3〉
〈h〉
x ←x
if f x
< f x
(
(
)
)
( )
otherwise
〈 〉
〈 〉
〈〉
〈 〉
x n+5 ← x n+2 + β ⋅ x h − x n+2
(
)
〈 〉
〈〉
if f ( x n+5 ) ≥ f ( x h )
for i ∈ 1 .. n + 1
(
〈〉
〈〉 1 〈〉
〈 〉
xi ←xi + ⋅ xi −xL
2
〈〉
〈 〉
x h ← x n+5 otherwise
fin←
1
⋅
n+ 1
n+1
〈〉
〈 〉 2
∑ ( f ( x i ) − f ( x n+2 ) )
i= 1
〈L〉
x
5 
NelderMid ( x0 , n , t , α , β , γ , ε , f) =  
6 5 
NelderMid ( x0 , n , t , α , β , γ , ε , f) = 
6 
5 
Minimize ( f , x0 ) =  
6 
2
f1 ( y) := 100 ⋅ y2 − ( y1) 2 + ( 1 − y1)
 12 
x10 := 12  
x10 :=   5  
 5 
62
2
)
1 

1 
NelderMid ( x10 , n , t , α , β , γ , ε , f1 ) = 
 1.399 

 1.94 
Minimize ( f1 , x10 ) = 
∗
T
Задание № 1. Найти x = ( x1, x2 ,..., xn ) , в котором заданная
функция f(x1, x2,…, xn) из следующей таблицы достигает минимума
или максимума. Номер Вашего варианта – номер Вашей фамилии
в журнале преподавателя.
Номер варианта
Функция f(x1, x2,…, xn)
Вид экстремума
1
x12 + x22 + x32 + x1 − x1 ⋅ x2 − 2x3
Минимум
(0.01x +0.11x )
2
−x1 + 1.4x2 − e
3
( x1 − x22 )
2
2
1
2
2
Максимум
2
+ (1 − x1 ⋅ x2 )
Минимум
( −0.38( x −2.87) −0.58( x −1.11) )
Максимум
5
x12 + 4x22 − 4x1 − 8x2 + 5
Минимум
6
1.06x14 + 0.94x22 + 3.88x1 − 5.16x2
Минимум
7
1.2x1 − 0.9x23 + 1.1x13 + 0.8x2 − 3.1x12 − 2.9x22
Максимум
8
( x1 − 0.94 ) e(1.03x1 ) −
4
1.15e
2
1
(1.12 + e(
2
−0.95x2 )
2
) ⋅ sin ( x )
2
9
( −1.91( x −2.12) −0.45( x −3.91) )
−1.48e
10
2.8 0.9 + 2.5 ( x1 − 1,1) + 0.38 ( x2 + 1.9 )
2
1
(
2
2
2
Минимум
Минимум
)
2 −1
Максимум
1б) Многомерная оптимизация в пакете Matlab.
Метод покоординатного спуска. Для минимизации по каждой
координате использован метод деления отрезка пополам.
>> clear
function yy=ffx(x)
%Вычисление функции двух переменных для
63
%метода покоординатного спуска.
a=0.5*(5*x(1).^2+2*x(1).*x(2)+5*x(2).^2)-(10*x(1)+x(2));
yy=a;
end
function [a1,b1]=Lokif(a,b,x1,m,delta)
%функция делит исходный отрезок локализации
%[a,b] на две части (с точностью примерно %+-2delta)
alfa0=(a+b)/2-delta;
beta0=(a+b)/2+delta;
x1(m)=alfa0;
fa1=ffx(x1);
x1(m)=beta0;
fb1=ffx(x1);
if fa1>fb1
a1=alfa0;
b1=b;
end;
if fa1<=fb1
a1=a;
b1=beta0;
end;
end
function x=delotrpop(a,b,x1,m,delta )
%Находится экстремум функции нескольких
%переменных методом деления отрезка
%пополам. При этом все переменные
%перечисляются по возрастанию их номеров
%(индексов).
k=1/(10*delta);
a1=a;
b1=b;
for i=1:k
[a2,b2]=Lokif(a1,b1,x1,m,delta);
a1=a2;
b1=b2;
x=(a1+b1)/2;
x1(m)=x;
end;
end
function [x,Fmin]=Koord_spusk(a,b,x1,delta)
%Подрорграмма находит экстремум функции
%нескольких переменных методом
%покоординатного спуска.
k=length(x1);
for j=1:k
c=delotrpop(a,b,x1,j,delta);
x1(j)=c;
F_min=ffx(x1);
end;
64
x=x1;
Fmin=F_min;
end
%Далее следует текст основной программы.
>> x0=[-5 5];
>> a=x0(1);
>> b=x0(2);
>> [X,Y]=meshgrid([-1:0.05:2.5]);
>> Z=0.5*(X.^2+2*X.*Y+5*Y.^2)-(10*X+Y);
>> meshc(X,Y,Z)
>> delta=10^(-6);
>> [x2,fm]=Koord_spusk(a,b,x0,delta)
x2 =
1.0000
-0.0000
fm =
-7.5000
Метод деформированного многогранника
>> clear
function yy=ffx(x)
%Вычисление функции двух переменных для %метода покоординатного
спуска.
a=0.5*(5*x(1).^2+2*x(1).*x(2)+5*x(2).^2)-(10*x(1)+x(2));
yy=a;
end
function [V0,y0,dV,dy]=NelderMid(F,V,min1,max1,epsilon)
%Вход -F- функция, вводимая как ‘F’,
%
-V- матрица размера 3*n, содержащая
%исходный симплекс,
%
-min1&max1- минимальное и
%максимальное число итераций,
65
%
-epsilon- допустимое отклонение,
%Выход-V0- вершина для минимума,
%
-y0- значение функции F(V0),
%
-dV- размер окончательного симплекса,
%
-dy- грань ошибки для минимума,
[mm n]=size(V);
% Последовательность вершин.
for j=1:n+1
Z=V(j,1:n);
Y(j)=feval(F,Z);
end
[mm lo]=min(Y);
[mm hi]=max(Y);
li=hi;
ho=lo;
for j=1:n+1
if (j~=lo&j~=hi&Y(j)<=Y(li))
li=j;
end
if (j~=hi&j~=lo&Y(j)>=Y(ho))
ho=j;
end
end
cnt=0;
%Начало алгоритма Нелдера-Мида.
while (Y(hi)>Y(lo)+epsilon&cnt<max1)|cnt<min1
S=zeros(1,n);
for j=1:n+1
S=S+V(j,1:n);
end
M=(S-V(hi,1:n))/n;
R=2*M-V(hi,1:n);
yR=feval(F,R);
if (yR<Y(ho))
if (Y(li)<yR)
V(hi,1:n)=R;
Y(hi)=yR;
else
E=2*R-M;
yE=feval(F,E);
if (yE<Y(li))
V(hi,1:n)=E;
Y(hi)=yE;
else
V(hi,1:n)=R;
Y(hi)=yR;
end
end
else
66
if (yR<Y(hi))
V(hi,1:n)=R;
Y(hi)=yR;
end
C=(V(hi,1:n)+M)/2;
yC=feval(F,C);
C2=(M+R)/2;
yC2=feval(F,C2);
if (yC2<yC)
C=C2;
yC=yC2;
end
if (yC<Y(hi))
V(hi,1:n)=C;
Y(hi)=yC;
else
for j=1:n+1
if (j~=lo)
V(j,1:n)=(V(j,1:n)+V(lo,1:n))/2;
Z=V(j,1:n);
Y(j)=feval(F,Z);
end
end
end
end
[mm lo]=min(Y);
[mm hi]=max(Y);
li=hi;
ho=lo;
for j=1:n+1
if (j~=lo&j~=hi&Y(j)<=Y(li))
li=j;
end
if (j~=hi&j~=lo&Y(j)>=Y(ho))
ho=j;
end
end
cnt=cnt+1;
P(cnt,:)=V(lo,:);
Q(cnt)=Y(lo);
end
% Конец алгоритма Нелдера-Мида.
% Определение размеров симплекса.
snorm=0;
for j=1:n+1
s=norm(V(j)-V(lo));
if (s>=snorm)
snorm=s;
end
67
end
Q=Q’;
V0=V(lo,1:n);
y0=Y(lo);
dV=snorm;
dy=abs(Y(hi)-Y(lo));
end
end
% Начало основной программы.
>> V=[5 -2;7 2;4.5 1]
V =
5.0000
-2.0000
7.0000
2.0000
4.5000
1.0000
>> min1=3
min1 =
3
>> max1=10
max1 =
10
>> epsilon=10^(-3)
epsilon =
1.0000e-03
>> [V0,y0,dV,dy]=NelderMid(‘ffx’,V,min1,max1,epsilon)
V0 =
1.9224
-0.0752
y0 =
-10.0402
dV =
0.3229
dy =
0.0388
Задание № 2. Выбрать из таблицы на стр. 63 вид целевой функции и найти её экстремум по методу Нелдера – Мида. Номер Вашего
варианта abs(n-11), где n – номер Вашей фамилии в журнале преподавателя.
§ 3.8. Лабораторная работа №3.
Задача линейного программирования.
1а) Программирование в пакете Mathcad
Поскольку в пространстве Rn n-мерная плоскость (целевая функция) не имеет экстремумов, то необходимо искать решения в системе ограничений. Это могут быть точки пересечения нескольких
n-мерных плоскостей-ограничений, либо точки какой-то плоскости
(в этом случае задача имеет множество решений).
68
Пример 1. (см. формулировку примера 2 на стр. 73)
ORIGIN := 1
Решение задачи линейного программирования.
Целевая функция
åâàÿ ôóíêöèÿf ( x , y , z) := 9 ⋅ x + 12 ⋅ y + 10 ⋅ z
Ограничения
0.1 ⋅ x + 0.3 ⋅ y + 0.4 ⋅ z ≥ 60
0.2 ⋅ x + 0.4 ⋅ y + 0.2 ⋅ z ≥ 50
0.1 ⋅ x + 0.4 ⋅ y + 0.3 ⋅ z ≥ 12
Необходимо найти минимум целевой функции.
Начальное приближение.
x := 60
y := 50
z := 12
Given
0.1 ⋅ x + 0.3 ⋅ y + 0.4 ⋅ z ≥ 60
0.2 ⋅ x + 0.4 ⋅ y + 0.2 ⋅ z ≥ 50
0.1 ⋅ x + 0.4 ⋅ y + 0.3 ⋅ z ≥ 12
x≥ 0
y≥ 0
z≥ 0
 60 
Minerr ( x , y , z) =  44 


 102 
f ( 60 , 44 , 102) = 2.088 × 10
3
Задание № 1. Сформулировать задачу линейного программирования по данным Вашего варианта и решить её в пакете
Mathcad. Номер Вашего варианта – номер фамилии в журнале
преподавателя.
Варианты заданий (все варианты взяты из работы [1]).
Вариант 1. Цех выпускает три вида продукции из четырёх видов сырья. Определить объём производства каждого продукта, при
котором достигается максимальная прибыль и достаточны запасы
сырья:
69
Вид сырья
Вид
продукции
A
I
II
III
2
2
–1
B
D
Стоимость
одной тонны, тыс.
руб.
4
–1
1
7
3
2
Потребность, тонн
1
–1∗
4
2
–1
–1
Запасы, тонн
4
1
8
∗(–1) –
C
8
побочный продукт в данном процессе.
Вариант 2. Фирма-посредник поставляет компьютеры с трёх
складов в пять магазинов. Число компьютеров на складах, потребности магазинов и стоимости перевозок:
Номер магазина
Номер
склада
1
2
3
4
5
Число
компьютеров на
складе
Затраты на один компьютер, руб.
I
10
0
30
40
20
15
II
50
10
20
30
30
25
III
40
80
10
40
30
20
Потребности магазинов, шт.
20
12
5
8
15
Определить поставки с каждого склада в каждый магазин. При которых суммарная стоимость перевозок минимальна.
Вариант 3. Распределите годовой бюджет рекламной фирмы,
равный 500 тыс.$ по четырём видам рекламы так, чтобы получить
максимальную прибыль.
Средство рекламы
Ограничения на распределения
бюджета
Прибыль, $/$
Телевидение
Не более 40%
10
Радио
Не менее 50% от телевидения
3
Газеты
–
4
Интернет
Не более 20%
6
Вариант 4. Сформировать диету из пяти видов продуктов с необходимым содержанием питательных веществ при минимальных
затратах:
70
Содержание питательных веществ, г/кг
Продукты
Цена одного
кг., руб.
Белки
Жиры
Углеводы
Витамины
Хлеб
2
1
12
2
12
Соя
12
8
0
2
36
Рыба
10
3
0
4
62
Фрукты
1
0
4
6
28
Молоко
2
4
3
2
20
Минимальное содержание в диете, ед.
20
10
30
40
Вариант 5. Спланировать недельные поставки продукции от
каждого поставщика каждому потребителю, при которых транспортные расходы будут минимальными:
Потребители
Поставщики
W1
W2
W3
W4
Недельный
объём производства,
шт.
Стоимость транспорта одна шт., руб.
F1
200
200
200
400
15
F2
300
100
100
300
25
F3
300
600
300
400
20
Недельная потребность, шт.
20
12
5
9
Вариант 6. Сформировать недельный план перевозок подшипников с трёх фабрик четырём ремонтным предприятиям так, чтобы
сумма расходов на перевозку была минимальной:
Ремонтные предприятия
Фабрики
C1
F1
130
170
F2
180
160
F3
120
140
C2
C3
C4
Объём производства,
тыс. шт./нед.
Стоимость перевозки 1 тыс. шт., руб.
170
140
50
160
180
25
190
170
25
Объёмы ремонтов, тыс. шт./нед.
15
20
20
30
Вариант 7. Сформировать недельный план выпуска трёх видов
продукции мебельного цеха, обеспечивающий максимальную прибыль:
71
Затраты труда, чел/час
Виды продукции
Прибыль от продажи,
руб.
Минимальный
выпуск,
шт/неделя
Лесопилка
Сборка
Отделка
Стулья
1
2
1
900
40
Столы
2
4
1
1100
10
4
2
2
1500
5
Шкафы
Резерв рабочей силы, чел./
час/неделя
360
520
220
Вариант 8. Спланировать годовые поставки стали трёх металлургических заводов четырём металлообрабатывающим, минимизировать транспортные расходы:
Металлургические заводы
Металлообрабатывающие
заводы
М1
М2
М3
Стоимость перевозки одной тыс. тонн/руб.
Р1
Р2
Р3
Р4
Годовая потребность,
тыс./тонн
1500
1900
1400
1900
1800
1600
1900
1800
2000
1500
1900
1800
Объём производства, тыс. тонн/год
50
30
20
12
15
25
36
Вариант 9. Составить недельный план выпуска продукции
станкостроительного производства, обеспечивающий максимальную прибыль:
Вид станка
Сверлильный
Фрезерный
Токарный
Необходимое количество комплектующих, шт.
Возможная реализация
I
II
III
1
4
2
10
70
2
3
3
30
80
10
10
8
20
40
Количество доступных изделий, шт.
650
850
650
72
Прибыль, тыс.
руб./шт.
Вариант 10. Определить объём недельного выпуска каждого из
видов продукции цеха сборки бытовой электроники, при котором
достигается максимальная прибыль:
Вид продукции
Музыкальный центр
Телевизор
Видеоплейер
Объём работы, чел./час
Изготовление
частей
Сборка
Проверка
Прибыль от
продажи, тыс.
руб.
2
1
1
1.5
3
2
1
2
3
2
Максимальный объём работ, чел./час/неделя
360
240
180
2.2
0.9
1б) Программирование в пакете Matlab
Решим в пакете Matlab задачу линейного программирования
с помощью подпрограммы
linprog(f, A, b, Aeq, beq, lb, ub, x0, options),
где f – вектор коэффициентов целевой функции; A, b, Aeq, beq – матрицы и вектора коэффициентов нелинейных и линейных ограничений вида Ax ≤ b, Ax =
b, lb, ub – вектора верхних и нижних границ
изменения переменных (если они известны); x0 – вектор начального
приближения, options – параметры управления процессом решения.
Параметры lb, ub, x0, options – не обязательны при обращении
к подпрограмме.
Пример 2. Составить дневной рацион откорма животных, обеспечивающий получение питательных веществ А, Б и С в необходимых объёмах при минимальных затратах. Содержание питательных веществ в кормах и их цены приведены в следующей таблице.
Содержание корма, кг/кг
Питательные
вещества
I
II
III
Норма потребления, кг
А
0.1
0.3
0.4
≥60
Б
0.2
0.4
0.2
≥50
С
0.1
0.4
0.3
≥12
Цена руб./кг
9
12
10
Пусть x, y, z – вес питательных веществ А, Б и С в дневном рационе. Тогда, очевидно
73
f ( x, y, z ) =9x + 12y + 10z ⇒ min,
0.1x + 0.3y + 0.4z ≥ 60,
0.2x + 0.4y + 0.2z ≥ 50,


 0.1x + 0.4y + 0.3z ≥ 12,
 x ≥ 60, y ≥ 50, z ≥ 12.
Программа вычисления имеет вид:
>> clear
>> f=[9 12 10]
f =
9
12
10
>> A=[-1 -1 -1;-0.1 -0.3 -0.4;-0.2 -0.4 -0.2;-0.1 -0.4 -0.3]
A =
-1.0000
-1.0000
-1.0000
-0.1000
-0.3000
-0.4000
-0.2000
-0.4000
-0.2000
-0.1000
-0.4000
-0.3000
>> b=[0;-60;-50;-12]
b =
0
-60
-50
-12
>> lb=zeros(3,1)
lb =
0
0
0
x0 =
60
50
12
>> [x,fval]=linprog(f,A,b,[],[],lb,x0)
Exiting: One or more of the residuals, duality gap, or total relative error
has grown 100000 times greater than its minimum value so far: the
primal appears to be infeasible (and the dual unbounded).
(The dual residual < TolFun=1.00e-08.)
x =
82.3529
73.9496
42.0168
fval =
2.0487e+03
74
Задание № 2. Выбрать вариант из перечня вариантов на стр.
69–73, сформулировать задачу линейного программирования по
этим данным и решить её в пакете Matlab. Номер Вашего варианта
abs(n–11), где n – номер Вашей фамилии в журнале преподавателя.
75
IV. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ
§ 4.1. Задачи многокритериального выбора
В многокритериальных задачах имеются не один, а несколько
разных критериев оценки качества решения. Здесь главная проблема – согласование критериев, т. е. выбор наилучшего соотношения
между оценками по разным критериям. Часто для этого нужна дополнительная информация, которая может быть и субъективной.
Одним из подходов к поиску компромиссного решения задачи
векторной оптимизации является сведение её к скалярной (однокритериальной) оптимизации. Одна из идей такого подхода – перевод всех критериев, кроме одного, в ограничения.
Главный вопрос – как и на каком уровне установить ограничения каждого из критериев, переводимых в ограничения. Ответ на
этот вопрос в общем случае не вытекает из условий задачи, т. е. выбор граничных условий, в общем, произволен, причём чем больше
критериев, тем больше произвола.
При решении задачи многокритериальной оптимизации возникают следующие проблемы:
1) Несравнимость решений. Это форма неопределённости, которая называется «ценностной неопределённостью».
2) Нормализация критериев. Частные критерии зачастую имеют
разный физический смысл. Операция присоединения локальных
критериев к единому (обычно безразмерному) называется нормализацией критериев.
3) Выбор принципа оптимальности. Это основная проблема векторной оптимизации. Все принципы должны отражать идеи устойчивости, выгодности и справедливости.
4) Учёт приоритета частных критериев, т. е. задача определения
их весов.
5) Вычисления оптимума задачи векторной оптимизации. Все
методы векторной оптимизации так или иначе сводят векторный
критерий к скалярному (рис. 4.1).
а). Взвешивание и объединение критериев.
1) Метод взвешенной суммы частных критериев.
T
Все частные критерии zi x , x = ( x1, x2 ,..., xn ) объединяются
в обобщённый критерий
( )
( )
( () ()
( ))
Z x = Ô z1 x , z2 x ,..., zm x ,
76
Методы решения
многокритериальных задач
Методы построения
обобщённых критери
–
ев оптимальности
Методы
последовательной
оптимизации
Методы сужения
области D
Рис. 4.1
который затем оптимизируется. Наиболее распространённым обобщённым критерием является аддитивный критерий – взвешенная
сумма всех частных критериев. Этот критерий записывается в виде
( )
m
( )
Z x = ∑ wi zi x , i =1
(4.1.1)
где wi – весовые коэффициенты, удовлетворяющие условиям 0≤wi≤1,
m
∑ wi = 1. Величина wi определяет важность i- го частного критерия,
i =1
при этом более важному критерию приписывается больший вес.
Как правило, частные критерии имеют различную размерность,
поэтому обобщённый критерий формируется из их нормированных
значений. Наиболее употребительный технический способ нормировки таков:
( )
zi x =
( )
zimax − zi x
zimax − zimin
( )
или zi x =
( )
zi x − zimin
zimax − zimin
.
( )
Нормированные критерии обозначаются через zi x , т. е. аддитивный критерий примет вид
( )
m
( )
Z x = ∑ wi zi x . i =1
(4.1.2)
2) Мультипликативный критерий.
Основой этого критерия является принцип справедливой относительной компенсации. В нём справедливым считается такой компромисс, когда суммарный уровень относительного снижения одного или нескольких критериев не превышает относительного уровня
увеличения других критериев.
77
Математическая формулировка условия оптимальности на основе этого принципа имеет вид
m ∆zi x
= 0,
∑
i =1 zi x
( )
( )
( )
( )
где ∆zi x и zi x – приращение величины i- го критерия и его первоначальное значение соответственно. Так как ∆zi x << zi x , то,
пренебрегая величинами второго порядка и выше, в пределе будем
иметь
m
m ∆zi x
m
∑ z x ≅ ∑ d ln zi x =d ln ∏ zi x =0,
i 1
=i 1=
i =1
i
( )
( )
( )
( ( ))
( )
( )
т. е. обобщённый мультипликативный критерий оптимальности
в самом общем случае имеет вид
( )
m
( )
Z x = ∏ zi x . i =1
(4.1.3)
§ 4.2. Методы определения весовых коэффициентов.
Веса критериев wi – самое проблемное место в процедуре многокритериального анализа. Все wi должны качественно отражать
важности соответствующих частных критериев. Чаще всего веса
назначают, исходя из интуитивного представления о сравнительной важности критериев. Наиболее популярны на практике методы
экспертных оценок.
1) Метод ранжирования.
Пусть экспертиза проводится группой из L экспертов. Метод основан на расстановке частных критериев в порядке их важности по
мнению экспертов. Цифрой 1 обозначается наиболее важный частный критерий, цифрой 2 – следующий по важности и т. д. В результате имеем следующую таблицу. Здесь ранг 1 получает оценку m,
ранг 2 – оценку m–1 и т. д.
Эксперты
1
2
…
L
78
Критерии
z1
z2
…
zm
r11
r21
…
rL1
r12
r22
…
rL2
…
…
…
…
r1m
r2m
…
rLm
L
=
ri ∑
=
rji , i 1,m. Тогда весовые коэфВ нижней строке таблицы
j =1
фициенты будут иметь вид
ri
=
w
=
, i 1,m.
i
m
∑ rj
j =1
Пример. Три эксперта L = 3 оценивают четыре критерия (m = 4)
следующим образом (расстановка критериев).
Места
Эксперты
1
2
3
1
2
3
4
z1
z3
z1
z3
z1
z4
z4
z2
z2
z2
z4
z3
Перейдём теперь к таблице ранжирования критериев по правилу: первому месту – четыре балла, второму – три и т. д.
Критерии
Эксперты
1
2
3
Сумма
z1
z2
z3
z4
4
3
4
11
1
2
2
5
3
4
1
8
2
1
3
6
Таким образрм,
m
4
∑ ri = ∑ ri =
=i 1=i 1
11 + 5 + 8 + 6 = 30,w1 =
w=
3
5
11
= 0.1667,
= 0.3667, w=
2
30
30
8
6
= 0.2667, w=
= 0.2.
4
30
30
2) Метод приписывания баллов.
Здесь эксперты оценивают важность частного критерия по шкале [0–10]. При этом можно приписывать одну и ту же оценку нескольким разным критериям. Пусть hji – балл j-го эксперта для i-го
критерия, тогда вес i-го, установленный j-м экспертом
rji =
hji
m
∑ hji
.
i =1
79
В предыдущем примере имеем
Критерии
Эксперты
z1
z2
z3
Сумма
z4
1
h11 = 10
h12 = 4
h13 = 8
h14 = 6
28
2
h21 = 7
h22 = 5
h23 = 10
h24 = 3
25
3
h31 = 10
h32 = 6
h33 = 5
h34 = 7
28
Тогда веса критериев определятся следующим образом.
Эксперты
Критерии
z1
1
10
2
7
3
10
Сумма
28
25
28
0.9942
z2
4
5
6
28
25
28
0.5572
z3
8
6
28
10
5
z4
3
25
7
28
0.8643
28
25
28
0.5843
Отсюда
4
3, w1
∑ ri = 0.9942 + 0.5572 + 0.8643 + 0.5843 ==
i =1
0.9942
= 0.3314,
3
0.5572
= 0.1857, w3 = 0.2881, w4 = 0.1948.
3
3) Статистическая обработка результатов экспертных оценок.
Статистическая обработка результатов экспертных оценок подобна статистической обработке результатов измерений. Предполагается, что результаты оценок каждого эксперта представляются
как наблюдённые значения некоторой случайной величины. Следовательно, можно найти по формулам математической статистики матожидание и дисперсию оценки каждого i-го критерия. Чем
меньше дисперсия, тем с большей уверенностью можно опираться
на данный критерий.
w2
=
§ 4.3. Методы последовательной оптимизации
1) Метод последовательных уступок.
Основная идея метода такова. Чтобы учесть вклад всех критериев, величины более важных критериев последовательно уменьшаются, величины менее важных – повышаются.
80
Схема алгоритма метода.
а) Все критерии ранжируются по важности. Самый важный критерий z1, менее важный z2 и т.д. до zm. Всего m критериев.
б) Находится решение задачи по критерию z1. Пусть это будет
z1min.
в) Находится решение по следующему по важности критерию z2,
причём в ограничения добавляется условие z1≤ z1min + ∆1, где ∆1 –
уступка по первому критерию.
г) Пункт в) повторяется до критерия zm, причём при заданных
уступках по все уже рассмотренным на предыдущих шагах критериям. Например, на m-ом шаге будем иметь такую формулировку
задачи: найти
z1 ≤ z1 min + ∆1,


z2 ≤ z2 min + ∆2 ,
zmin = min zm ( x ) и 
......................
x∈D

zm −1 ≤ z(m −1) min + ∆m −1.

Величины уступок выбираются эмпирически в пределах 5–10%
от наименьшего значения критерия.
Пример 1. Пусть в D = {0, 4} заданы два критерия z1(x) = (x–1)2 + 1 и
z2(x) = (x–2)2 + 2, которые нужно минимизировать, причём критерий
z1 важнее критерия z2.
Найдём
2
min z1 ( x ), ò. å. z1 (=
x ) min ( x − 1) + 1 .

x∈D 
Минимум z1 достигается в точке z1min = 1, z1(x)min = 1. Пусть величина уступки ∆1 = 0.1 (10% от z1min). Тогда следующая задача минимизации в методе последовательных уступок будет такой: найти

x ∈ {0,4},
2
min z2 (=
x ) min ( x − 2 ) + 2 при 
2


1.1.
( x − 1) + 1 ≤ 1 + 0.1 =
Задача легко сводится к задаче безусловной минимизации и решается методом множителей Лагранжа.
F ( x, λ=
)
2
( x − 2)
(
2
+ 2 + λ ( x − 1)
 ∂F
) 0,
 ∂x= ( x − 2 ) + λ ( x − 1=
− 0.1 , 

 ∂F =( x − 1)2 − 0.1 =0,
 ∂λ
)
⇒z2min = 1.32.
81
f(x)
(x–1) 2 +1
(x –2) 2 +2
2
z1min
z2min
Рис. 4.2
5
Согласно алгоритму, решение, полученное на последнем
этапе, будет оптимальным, т. е.
xopt = 1.32 (рис. 4.2).
Метод последовательных уступок целесообразно применять
в тех задачах, где все частные
критерии упорядочены по степени
важности, причём каждый критеx рий настолько более важен, чем
последующий, что можно ограничиться учётом только попарной
связи критериев с учётом поведения лишь одного следующего кри-
терия.
Недостаток метода – трудности с назначением и согласованием
величин уступок. Эта трудность возрастает с размерностью векторного критерия.
2) Метод равенства частных критериев.
Основной принцип данного метода основан на идее поиска таких
T
значений переменных основной задачи x = ( x1, x2 ,..., xn ) , при которых нормированные значения всех частных критериев с учётом их
весовых коэффициентов будут равны, т. е. wi ⋅ zi x = const, i= 1,m.
Этот же принцип является основным недостатком метода, т. к.
очень трудно даже при небольшом количестве критериев добиться
этого равенства. Метод применяется сравнительно редко.
Пример 2. Рассматривается переносной автомат для забивания
дюбелей в бетонные стены. Требуется определить основные конструкционные параметры автомата – длину его ствола L, число
дюбелей N, если по техническому заданию требуется, чтобы: число
дюбелей N≥12, масса одного дюбеля m = 50 г., масса ствола 1.6 кг/м,
масса корпуса 2 кг, масса автомата ≤6 кг.
При фиксированной величине заряда и массе дюбеля скорость V
его выбрасывания связана с L соотношением
( )
=
V k=
L, k 150
Минимально допустимая скорость
Vmin = 100 ì
82
ì
.
ñåê
ñåê.
Частными критериями здесь являются скорость выбрасывания
и число дюбелей, т. к. чем выше V, тем надёжнее дюбеля проникают
в бетонные стены, а чем больше N, тем удобнее работать. По мнению
экспертов оба критерия V и N имеют одинаковую важность.
Пусть
=
z1 ( N, L ) k=
L, z2 ( N, L ) N. Тогда задача многокритериальной оптимизации будет иметь вид
max F = max(z1, z2 ),
N ≥ 12,


V ≥ 100,

1.6L + 0.05N + 2 ≤ 6.

Построим область D и решим задачу сначала с помощью аддитивного критерия.
Z ( x=
)
2
∑ wi zi ( x ),w=1
i =1
w=
2 1,
так как частные критерии имеют одинаковую важность. Найдём
максимальные значения критериев, достигаемых в области существования проектных решений. Используем массу автомата. Задано
Vmin = 100 м/сек. Длина ствола
2
V

L =  min  ,
 k 
подставим её в уравнение для мас- L
сы автомата, получим Nmax = 66.
L =17/8
Аналогично, если взять N = 12, то max
получим Vmax = 219 м/сек. Теперь
можно построить для задачи область D (рис. 4.3).
Тогда задача оптимизации пе- Lmin =4/9
репишется в виде
k L
N
+
,
Vmax Nmax
1.6L + 0.05N + 2 ≤ 6.
Z(N
=
,L )
D
Nmin =12
Nmax =66 N
Рис. 4.3
Последнее неравенство можно заменить равенством, т. к. Z(N,
L) монотонно возрастающая функция, следовательно, её экстремум
83
достигается на границе. Применим опять метод множителей Лагранжа:
k L
N
F ( N, L
=
,λ )
+
+ λ (1.6L + 0.05N − 4 ).
Vmax Nmax
Отсюда
k
1
 ∂F
.6λ 0,
⋅
+ 1=
=
∂L Vmax 2 L

1
 ∂F
.05λ 0,
+ 0=
=
 ∂N Nmax
 ∂F
4 0.
 = 1.6L + 0.05N −=
 ∂λ
Решение:
λ=−
 0.05Nmax k 
k2
1
, Vopt = −
, Lopt = 

0.05Nmax
2Vmax ⋅ 1.6λ
 3.2Vmax 
Или
λ=−
4
= 0.308, Nopt = 64, Lopt = 0.499 ì, Vopt = 106 ì/ñåê.
13
Решим теперь эту же задачу с помощью мультипликативного
критерия. Здесь
, L ) k L ⋅ N,
Z ( N=
N ≥ 12,


V ≥ 100,

1.6L + 0.05N + 2 ≤ 6.

Используем тот же метод множителей Лагранжа. Получим
F ( N,=
L, λ ) k LN + λ (1.6L + 0.05N − 4 ).
Тогда
 ∂F kN
+ 1=
.6λ 0,
 =
∂L 2 L

 ∂F
=
λ 0,
 = k L + 0.05
 ∂N
 ∂F
= 1.6L + 0.05N −=
4 0.
 ∂λ

84
Отсюда
=
Nopt 53
=
, Lopt 0.83 =
ì, Vopt 137 ì/ñåê.
3) Метод анализа иерархий.
Метод предложен в 70-х годах XX столетия и основан на идее попарного сравнения альтернатив по каждому из критериев. Он включает четыре основных этапа.
а) Построение иерархии.
б) Попарное сравнение альтернатив по каждому из критериев.
в) Взвешивание критериев.
г) Выбор наиболее предпочтительной альтернативы.
Пример. Рассмотрим на конкретном экономическом примере построение иерархии «цель-критерии-альтернатива». Пусть цель: выбор места работы; критерии: z1 – зарплата, z2- квалификация, z3 –
удалённость работы от дома; альтернативы: (1) – ОАО Х1, (2) – ЗАО
Х2, (3) – ОАО Х3.
Парные сравнения альтернатив по каждому из трёх критериев
проводятся по следующей таблице сравнения альтернатив:
Рейтинг
Описание
1
Одинаковое предпочтение
3
Умеренное предпочтение
5
Явное предпочтение
7
Очевидное предпочтение
9
Абсолютное предпочтение
Эта таблица, например, может быть получена методом экспертных оценок.
В результате сравнения альтернатив получена следующая матрица предпочтений альтернатив. По первому критерию (зарплата)
 Àëüòåð
(1) (2) (3) 

 íàòèâû

 (1)
1
5
3 .


1
1 
1
 (2)
5
3

1
 (3)
1 
3 3


Ясно, что по первому критерию ОАО Х1 предпочтительнее всех
остальных (явно и умеренно). Аналогичные матрицы предпочтений
строятся по второму (квалификация) и по третьему (удалённость работы от дома) критериям.
85
По критерию z2
 Àëüòåð
(1) (2) (3) 

 íàòèâû

 (1)
1 1 5 3 ,


 (2)
5
1
3 


1
1
 (3)

1
3
3


по критерию z3
 Àëüòåð
(1) (2) (3) 

 íàòèâû

 (1)
1
3
5 .


1
1
3
 (2)

3


1
1
 (3)

1
5
3


Построенные матрицы нормализуются так, чтобы сумма элементов каждого столбца была равна единице, а затем строится вектор
приоритетов, элементами которого являются средние арифметические значения элементов строк нормализованных матриц. Именно:
по критерию z1
 0.652 0.556 0.692   0.633 

 

 0.130 0.111 0.077  ⇒  0.106 ,
 0.217 0.333 0.231   0.260 

 

по критерию z2
 0.158 0.130 0.429   0.239 

 

 0.790 0.652 0.429  ⇒  0.623 ,
 0.053 0.217 0.143   0.138 

 

наконец, по критерию z3
 0.652 0.692 0.556   0.633 

 

 0.217 0.231 0.333  ⇒  0.260 .
 0.130 0.077 0.111   0.106 

 

При взвешивании критериев, т. е. построении вектора приоритета для критериев, берут вектор средних арифметических значений
86
строк матриц нормализованных предпочтений альтернатив. Для
критерия z1
 0.633 


 0.106 ,
 0.260 


для критерия z2
 0.239 


 0.623 ,
 0.138 


для критерия z3
 0.633 


 0.260 .
 0.106 


Таким образом, вес первого критерия для первой альтернативы
0.633, для второй альтернативы – 0.239, наконец, для третьей –
0.633 и т. п.
Последний этап всего процесса – выбор наиболее предпочтительной альтернативы. В этом случае вычисляется ранг каждой альтернативы с учётом весов критериев. Для этого вес критерия играет
роль весового коэффициента, а веса альтернатив берутся из векторов приоритета. Например, для первой альтернативы ОАО Х1 имеем:
0.633⋅0.633 + 0.239⋅0.106 + 0.633⋅0.260 = 0.591,
для второй альтернативы
ЗАО Х2 – 0.106⋅0.239 + 0.623⋅0.623 + 0.260⋅0.138
= 0.449, наконец, для третьей альтернативы ОАО
Х3 – 0.260⋅0.633 + 0.138⋅0.260 + 0.106⋅0.106 = 0.212.
Таким образом, получены ранги альтернатив, причём ранг первой альтернативы равен 0.591, второй – 0.493, третьей – 0.212.
Иногда проводится проверка согласованности оценок (обычно,
если число альтернатив большое m > 4). Проверка заключается в следующем. Суммы столбцов исходной матрицы сравнений умножаются на элементы соответствующего вектора приоритетов и складыва87
ются. В случае идеальной согласованности эта сумма должна быть
равна числу альтернатив. В нашем случае
(1 + 15 + 1 3) ⋅ 0.633 + (5 + 1 + 3) ⋅ 0.106 + (3 + 1 3 + 1) ⋅ 0.260 =3.06,
далее
3.435,
(1 + 5 + 1 3) ⋅ 0.239 + ( 15 + 1 + 1 3) ⋅ 0.623 + (3 + 3 + 1) ⋅ 0.138 =
(1 + 1 3 + 15) ⋅ 0.633 + (3 + 1 + 1 3) ⋅ 0.260 + (5 + 3 + 1) ⋅ 0.106 =3.052.
§ 4.4. Оптимальность по Парето*∗
T
Пусть для каждого =
решения x ( x1, x2 ,..., xn ) ∈ D определён набор его оценок по всем рассматриваемым критериям:
( z1 ( x ),z2 ( x ),...,zm ( x ))
T
– векторная оценка решения x. Оптимальным считается такое решение, которому соответствует минимальное значение каждого частного критерия zi x , i = 1,m. В обобщённом смысле оптимальность критерия можно трактовать как некоторое сужение области D до D0∈D. В зависимости от характера
описания D0 может оказаться пустым, состоять из одного элемента,
содержать более одного элемента.
Решение x1 доминирует решение x2, если zi x1 ≤ zi x2 ∀i =1,m
и хотя бы для одного j-го критерия zj x1 < zj x2 . Таким образом,
переход от x2 к x1 не приведёт к росту значения какого-либо критерия, но значение одного из критериев точно уменьшится.
Решение, не доминируемое никаким другим решением, называется Парето-оптимальным. Множество таких решений называется
множеством Парето P, P∈D. Итак, множество Парето – это множество таких решений, что ни для одного из них нет доминирующего
решения.
Множество векторных оценок, соответствующих множеству D,
называется критериальным пространством YD, множество Парето – областью компромиссов YP, множество доминируемых решений – областью согласия YC.
В области согласия нет противоречий между частными критериями, т. е. существует решение, оптимальное с точки зрения всех
критериев. В области компромиссов частные решения противоречат
( )
( )
( )
( )
( )
* Вильфридо Парето (1848-1923) – итальянский экономист и социолог.
88
f1, f2
z1, z2
z1
z1 opt
2
z2
P
z2 opt
D
xopt
x
D
5
x
Рис. 4.4
друг другу. т. к. минимум по каждому из них соответствует различным Парето-оптимальным решениям (рис. 4.4). Оптимальные точки, т. е. точки из D, в которых рассматриваемые критерии имеют
экстремум, встречаются редко. Обычно частные критерии бывают
противоречивыми, и экстремум по каждому из них достигается
в различных точках. В этом случае уменьшение одного частного
критерия приводит к увеличению других частных критериев.
Оптимальность по Парето означает, что нельзя дальше улучшать
значения одного из критериев, не ухудшая при этом хотя бы одного
из остальных.
Пример 1. Пусть множество D состоит из 11 решений, оцениваемых двумя критериями. Векторные оценки решений таковы:
z(x1) = (2, 4), z(x2) = (3, 5), z(x3) = (3, 3), z(x4) = (5, 2), z(x5) = (4, 3),
z(x6) = (1, 3), z(x7) = (2, 3), z(x8) = (3, 2), z(x9) = (2, 2), z(x10) = (3, 1),
z(x11) = (2, 1). Критериальное пространство изображено на рис. 4.5.
z2
2
1
6
7
9
┘ min
11
3
5 └ max
8
4
10
z1
Рис. 4.5
89
Множество Парето образуют решения, лежащие на правой верхней
или левой нижней границе области D (выделены кружками). При
поиске максимума множество Парето образуют решения x2, x4, x5,
при поиске минимума решения x6, x11. Для определения множества Парето используют правило «уголка»  или .
Методы построения множества Парето.
Множество Парето в двумерном пространстве критериев называется компромиссной кривой. Построение этого множества достаточно сложная задача даже для очень простого примера. В вычислительной практике часто применяются численные методы построения множества Парето. Например, в области D формируется сетка,
координаты узлов которой задаются датчиком случайных чисел,
вычисляются значения критериев в этих узлах и путём сравнения
их значений строится множество Парето на выбранной сетке.
Рассмотрим простой пример с двумя критериями, т. е. постоим
компромиссную кривую. Компромиссная кривая может состоять
из несвязных отрезков или содержать изолированные точки. Она
представляет собой геометрическое место точек соприкосновения
поверхностей уровня критериев z1(x) = b1 и z2(x) = b2, в которых справедливо равенство gradz1 = -δgradz2, 0≤δ≤∞.
Если z1(x) и z2(x) дифференцируемы, то это эквивалентно системе
уравнений
∂z1
∂z
= −δ 2 , j = 1,n,
∂xj
∂xj
Эта система определяет кривую в пространстве параметров
x1 = ϕ(δ),…, xn = ϕ(δ).
Пример 2. Пусть D = {–0.5≤x1≤0.5, 0≤x2≤1}, z1 ( x1, x2=
) x12 + 4x22 ,
2
2
z2 ( x1, x2 ) = ( x1 + 1) + ( x2 − 1) , z1(x) и z2(x) необходимо минимизировать. Минимум z1(x1, x2) находится, очевидно, в точке x1opt = (0,
0), x1opt∈D; минимум z2(x1, x2) в точке x2opt = (–1, 1)∉D. Условный
минимум z2(x1, x2) находится в точке x2усл = (–0.5, 1) (см. рис. 4.6).
Частные производные
∂z1
∂z
∂z2
∂z
=
=
2=
x1, 1 8x2 ,
2 ( x1 + 1), 2 =
2 ( x2 − 1).
∂x1
∂x2
∂x1
∂x2
Система уравнений
δ
δ
2x1 =−2δ ( x1 + 1),
⇒ x1 =
−
, x2 = ,

δ +1
δ+4
 8x2 =−2δ ( x2 − 1)
90
x2
x2усл
xп
0.20
x1opt
–0.5
0.5
x1
Рис. 4.6
т. е. параметрические уравнения компромиссной кривой для этого
случая в пространстве критериев z1 и z2 имеют вид
2
2
2
2
δ   −4 
δ 


 δ 
z1 ( δ ) =  −
 + 4
 , z2 ( δ ) =  − δ + 1  +  δ + 4  .

 

 δ +1 
δ+4
В пространстве параметров x1 и x2 уравнение компромиссной
кривой можно получить, выразив δ через x1 и x2 и приравняв полученные выражения. Сделав это, будем иметь
x2 = −
x1
.
3x1 + 4
Точка пересечения этой кривой с прямой x1 = -0.5, xп = (–0.5, 0.2),
при этом 0≤δ≤1 и z1(0) = 0, z2(0) = 2, z1(1) = 0.41, z2(1) = 0.89. Таким образом, между точками x1opt и xп компромиссная кривая соответствует уравнению
x2 = −
x1
,
3x1 + 4
а далее совпадает с прямой x1 = -0.5 (см. рис. 4.6).
Численные методы получения множества Парето.
В множестве D выбирается некоторая сетка, координаты которой, например, могут выбирать случайно. В этих координатах вычисляются значения векторного критерия, после чего по правилам
образования множества Парето, строится это множество. Конечно,
всех возможных точек оно не охватывает, но на этой сетке строится
при n→∞ (n – число точек сетки) приближение этого множества.
91
§ 4.5. Способы сужения множества Парето
Выделение множества Парето многокритериальной задачи оптимизации очень часто не является удовлетворительным решением.
Дело в том, что множество Парето почти всегда оказывается слишком большим для оптимального выбора. Таким образом, выделение
множества Парето – лишь предварительный этап оптимизации, и
надо это множество далее сокращать.
Для этого нужна дополнительная информация. Без неё обоснованность сужения множества Парето трудно объяснить. Используются два подхода.
1) Первый подход. Здесь выбор конкретного оптимального решения из множества Парето предоставляется лицу, принимающему
решения.
2) Второй подход. Используются некоторые формализованные
процедуры, о которых речь пойдёт далее.
Оптимально-компромиссным решением называется одно из Парето-оптимальных решений. Для выбора оптимально-компромиссного решения в каждой конкретной многокритериальной задаче
нужно использовать дополнительную информацию, которая осталась неиспользуемой при формировании совокупности критериев.
Рассмотрим некоторые способы сужения множества Парето.
1. Указание граничных значений критериев.
Дополнительная информация в этом случае имеет вид
(
)
(
)
zi xopt ≤ Ci , zj xopt ≥ Cj , i, j =1,m, i ≠ j,
т. е. каждое из чисел Ci, Cj представляет собой верхнюю или нижнюю границу i-го или j-го критерия.
2. Субоптимизация.
В этом случае дополнительная информация указывает на один
из критериев как важнейший и задаёт граничные условия для
остальных.
3. Лексикографическая оптимизация.
Здесь используется операция частичного порядка, т. е. операция
предшествования. Если A  B, то ai≤bi, ai∈A, bi∈B. Критерии упорядочиваются по относительной важности следующим образом ( по
признакам и свойствам) zi  zj  ...  zk , i, j=
, k 1,m, i ≠ j ≠ k. Выбирается важнейший критерий, затем следующий по важности и т. д. до
наименее важного.
92
4. Методы ЭЛЕКТРА.
Предложены в 70-х годах XX века. Здесь отношения предпочтения строятся следующим образом. Для каждого из m критериев
определяется его вес в числовом выражении. Часто весовые коэффициенты нормируются обычным способом.
Для того, чтобы определить, превосходит ли решение xk решение
xl необходимо разбить множество критериев на три подмножества:
а) Критерии, по которым xk превосходит xl .
б) Критерии, по которым xk и xl имеют одинаковые оценки.
в) Критерии, по которым xl превосходит xk.
Затем определяется относительная важность каждого из этих
подмножеств Pkl+ , Pkl= , Pkl− в виде суммы весов всех входящих в них
критериев. Считается, что вариант xk превосходит вариант xl , если
выполняется условие
Pkl+
m
∑ pi
−
> Pkl
m
∑ pi
.
=i 1=i 1
Пример 1. Рассмотрим пример, аналогичный примеру § 4.3, но
решим его на примере сужения множества Парето. В этом примере
опять нужно выбрать оптимальное место работы. Варианты выбора
представлены в табл 4.5.1.
Таблица 4.5.1
Критерий
Зарплата (тыс. руб.)
Отпуск (дни)
Время доступа
(мин.)
Номера вариантов
1
2
3
4
5
6
7
8
9
90
20
50
30
70
36
80
40
40
60
60
30
90
35
60
24
65
35
60
20
40
50
15
10
60
10
40
Очевидно, что при выборе вариантов критерии зарплата и отпуск
следует максимизировать, а критерий время – минимизировать.
Выделим сначала Парето-оптимальные варианты. Всего имеется
девять точек: (90, 20, 60), (50, 30, 20), (70, 36, 40), (80, 40, 50), (40, 60,
15), (60, 30, 10), (90, 35, 60), (60, 24, 10), (65, 35, 40). Координаты этих
критериев сравниваем по правилу xi ≥ xj , yi ≥ yj , zi ≥ zj , i, j =1,9, i ≠ j.
Например,
Варианты 1 и 2 т. е. (90, 20, 60) и (50, 30, 20) не сравнимы, следовательно, вариант 1 не доминирует вариант 2;
93
Варианты 1 и 3 т. е. (90, 20, 60) и (70, 36, 40) не сравнимы, следовательно, вариант 1 не доминирует вариант 3;
Варианты 1 и 4 т. е. (90, 20, 60) и (80, 40, 50) не сравнимы, следовательно, вариант 1 не доминирует вариант 4;
Варианты 1 и 5 т. е. (90, 20, 60) и (40, 60, 15) не сравнимы, следовательно, вариант 1 не доминирует вариант 5;
Варианты 1 и 6 т. е. (90, 20, 60) и (60, 30, 10) не сравнимы, следовательно, вариант 1 не доминирует вариант 6;
Варианты 1 и 7 т. е. (90, 20, 60) и (90, 35, 60) не сравнимы, следовательно, вариант 1 не доминирует вариант 7;
Варианты 1 и 8 т. е. (90, 20, 60) и (65, 35, 40) не сравнимы, следовательно, вариант 1 не доминирует вариант 8;
Варианты 1 и 9 т. е. (90, 20, 60) и (65, 35, 40) не сравнимы, следовательно, вариант 1 не доминирует вариант 9; Вывод: вариант 1 не
доминирует ни один из оставшихся вариантов из множества D.
Варианты 2 и 1 т. е. (50, 30, 20) и (90, 20, 60) не сравнимы, следовательно, вариант 2 не доминирует вариант 1;
Варианты 2 и 3 т. е. (50, 30, 20) и (70, 36, 40) не сравнимы, следовательно, вариант 2 не доминирует вариант 3;
Варианты 2 и 4 т. е. (50, 30, 20) и (80, 40, 50) не сравнимы, следовательно, вариант 2 не доминирует вариант 4;
Варианты 2 и 5 т. е. (50, 30, 20) и (40, 60, 15) не сравнимы, следовательно, вариант 2 не доминирует вариант 5;
Варианты 2 и 6 т. е. (50, 30, 20) и (60, 30, 10) не сравнимы, следовательно, вариант 2 не доминирует вариант 6;
Варианты 2 и 7 т. е. (50, 30, 20) и (90, 35, 60) не сравнимы, следовательно, вариант 2 не доминирует вариант 7;
Варианты 2 и 8 т. е. (50, 30, 20) и (60, 24, 10) не сравнимы, следовательно, вариант 2 не доминирует вариант 8;
Варианты 2 и 9 т. е. (50, 30, 20) и (65, 35, 40) не сравнимы, следовательно, вариант 2 не доминирует вариант 9;
Варианты 3 и 1 т. е. (70, 36, 40) и (90, 20, 60) не сравнимы, следовательно, вариант 3 не доминирует вариант 1;
Варианты 3 и 2 т. е. (70, 36, 40) и (50, 30, 20) не сравнимы, следовательно, вариант 3 не доминирует вариант 2;
Варианты 3 и 4 т. е. (70, 36, 40) и (80, 40, 50) не сравнимы, следовательно, вариант 3 не доминирует вариант 4;
Варианты 3 и 5 т. е. (70, 36, 40) и (40, 60, 15) не сравнимы, следовательно, вариант 3 не доминирует вариант 5;
94
Варианты 3 и 6 т. е. (70, 36, 40) и (60, 30, 10) не сравнимы, следовательно, вариант 3 не доминирует вариант 6;
Варианты 3 и 7 т. е. (70, 36, 40) и (90, 35, 60) не сравнимы, следовательно, вариант 3 не доминирует вариант 7;
Варианты 3 и 8 т. е. (70, 36, 40) и (60, 24, 10) не сравнимы, следовательно, вариант 3 не доминирует вариант 8;
Варианты 3 и 9 т. е. (70, 36, 40) и (65, 35, 40) вариант 3 доминирует вариант 9, вариант 9 исключаем из множества P.
Варианты 4 и 1 т. е. (80, 40, 50) и (90, 20, 60) не сравнимы, следовательно, вариант 4 не доминирует вариант 1;
Варианты 4 и 2 т. е. (80, 40, 50) и (50, 30, 20) не сравнимы, следовательно, вариант 4 не доминирует вариант 2;
Варианты 4 и 3 т. е. (80, 40, 50) и (70, 36, 40) не сравнимы, следовательно, вариант 4 не доминирует вариант 3;
Варианты 4 и 5 т. е. (80, 40, 50) и (40, 60, 15) не сравнимы, следовательно, вариант 4 не доминирует вариант 5;
Варианты 4 и 6 т. е. (80, 40, 50) и (60, 30, 10) не сравнимы, следовательно, вариант 4 не доминирует вариант 6;
Варианты 4 и 7 т. е. (80, 40, 50) и (90, 35, 60) не сравнимы, следовательно, вариант 4 не доминирует вариант 7;
Варианты 4 и 8 т. е. (80, 40, 50) и (60, 24, 10) не сравнимы, следовательно, вариант 4 не доминирует вариант 8;
Варианты 5 и 1 т. е. (40, 60, 15) и (90, 20, 60) не сравнимы, следовательно, вариант 5 не доминирует вариант 1;
Варианты 5 и 2 т. е. (40, 60, 15) и (50, 30, 20) не сравнимы, следовательно, вариант 5 не доминирует вариант 2;
Варианты 5 и 3 т. е. (40, 60, 15) и (70, 36, 40) не сравнимы, следовательно, вариант 5 не доминирует вариант 3;
Варианты 5 и 4 т. е. (40, 60, 15) и (80, 40, 50) не сравнимы, следовательно, вариант 5 не доминирует вариант 4;
Варианты 5 и 6 т. е. (40, 60, 15) и (60, 30, 10) не сравнимы, следовательно, вариант 5 не доминирует вариант 6;
Варианты 5 и 7 т. е. (40, 60, 15) и (90, 35, 60) не сравнимы, следовательно, вариант 5 не доминирует вариант 7;
Варианты 5 и 8 т. е. (40, 60, 15) и (60, 24, 40) не сравнимы, следовательно, вариант 5 не доминирует вариант 8;
Варианты 6 и 1 т. е. (60, 30, 10) и (90, 20, 60) не сравнимы, следовательно, вариант 6 не доминирует вариант 1;
Варианты 6 и 2 т. е. (60, 30, 10) и (50, 30, 20) вариант 6 доминирует вариант 2, вариант 2 исключаем из множества P.
95
Варианты 6 и 3 т. е. (60, 30, 10) и (70, 36, 40) не сравнимы, следовательно, вариант 6 не доминирует вариант 3;
Варианты 6 и 4 т. е. (60, 30, 10) и (80, 40, 50) не сравнимы, следовательно, вариант 6 не доминирует вариант 4;
Варианты 6 и 5 т. е. (60, 30, 10) и (40, 60, 15) не сравнимы, следовательно, вариант 6 не доминирует вариант 5;
Варианты 6 и 7 т. е. (60, 30, 10) и (90, 35, 60) не сравнимы, следовательно, вариант 6 не доминирует вариант 7;
Варианты 6 и 8 т. е. (60, 30, 10) и (60, 24, 10) вариант 6 доминирует вариант 8, вариант 8 исключаем из множества P.
Варианты 7 и 1 т. е. (90, 30, 60) и (90, 20, 60) вариант 7 доминирует вариант 1, вариант 1 исключаем из множества P.
Варианты 7 и 3 т. е. (90, 30, 60) и (70, 36, 10) не сравнимы, следовательно, вариант 7 не доминирует вариант 3;
Варианты 7 и 4 т. е. (90, 30, 60) и (80, 40, 50) не сравнимы, следовательно, вариант 7 не доминирует вариант 4;
Варианты 7 и 5 т. е. (90, 30, 60) и (40, 60, 15) не сравнимы, следовательно, вариант 7 не доминирует вариант 5;
Варианты 7 и 6 т. е. (90, 30, 60) и (60, 30, 10) не сравнимы, следовательно, вариант 7 не доминирует вариант 6;
Итак, выброшены, т. е. доминируются варианты 1, 2, 8, 9. Доминирующие варианты 3, 6, 7. Варианты 4 и 5 никакими вариантами
не доминируются, следовательно, они также входят во множество
Парето. Итак, P = {3, 4, 5, 6, 7} = {(70, 36, 40), (80, 40, 50), (40, 60, 15),
(60, 30, 10), (90, 35, 60)}. При отсутствии информации об относительной важности рассматриваемых критериев сужение полученного
множества невозможно.
Рассмотрим теперь второй подход, который приводит к сужению
множества Парето.
а) Указание нижних границ критериев. Пусть зарплата≥60 тыс.
руб., dотп,≥30 дней, tпоезки ≤40 мин. Варианты, удовлетворяющие этим
дополнительным ограничениям, это варианты 3 и 6. Сделать между
ними окончательный выбор должно лицо принимающее решение.
б) Субоптимизация. Пусть в качестве главного критерия выступает зарплата. Тогда без вариантов оптимальное решение – это вариант 7.
в) Лексикографическая оптимизация. Воспользуемся операцией
предпочтения. Если, например,
a  b, òî ( a1 ≤ b1 ),( a2 ≤ b2 ),...,( an ≤ bn ).
96
Рассмотрим случай Ç  Â  Ä. По этому критерию возможны
следующие случаи:
по критерию З варианты 4 и 7,
по критерию В вариант 4,
по критерию Д вариант 4.
Итог, вариант 4.
5). Метод «идеальной» точки.
В этом методе рассматривается m-мерное пространство m локальных критериев. В пространстве вводится некоторая метрика (часто
это аналог расстояния или стоимости) между вектором, порождённым i-ым локальным критерием и «идеальным» решением.
=
Пусть ai max
=
fi x , i 1,m – точка максимума i-го критерия.
T
Тогда a = ( a1, a2 ,..., am ) – «идеальная» точка. Обычно эта точка
∗
принадлежит области критериев D. Зададим для всех точек x ∈ D
функцию – аналог евклидова расстояния
( )
1
m
2 2
ρ x, a =
 ∑ ( ai xi )  .
 i =1

( )
Тогда за целевую функцию обобщённого критерия метода «идеальной» точки можно взять выражение
m
F= min ∑ λ i ai − f1 ( x ) 
2
i =1
или с учётом нормировки
 ai
min ∑ λ i 
x∈D i =1 

m
2
− fi ( x ) 
 ,
fi(0) 
где fi(0) – норма. Обычно в технологических задачах в качестве начальной точки берут директивные значения параметров, заданные
заказчиком, т. е. данные технического задания. Например, когда все основные условия работоспособности имеют вид равенств
fi(x) = TTi, где TTi – значения технических требований, предъявляемых к i-му критерию. Тогда
( )
 fi x − TTi 
m
λ
F x =
∑ i  f (0)  → min.
i =1 
i

( )
97
Пример 2. Имеются три частных (линейных) критерия
z1 =
f1 ( x1, x2 ) =
−3x1 + 2x2 , =
z2 f2 ( x1, x=
2 ) 4x1 + 3x2 ,
=
z3 f3 ( x1, x=
2 ) 2x1 − 5x2 ,
которые требуется максимизировать. Область D задаётся неравенствами –x1–3x2 + 18≥0, -2x1-x2 + 10≥0, x1≥0, x2≥0. f1(x) достигает максимума a1 = 12 в точке x1(0, 6)∈D, f2(x) достигает максимума a2 = 24
в точке x2(3, 4)∈D, f3(x) имеет максимум a3 = 10 в точке x3(5, 0)∈D.
Составим целевую функцию метода «идеальной» точки:
( )
2
2
F x= 12 − ( −3x1 + 2x2 )  + 24 − ( 4x1 + 3x2 )  +
2
+ 10 − ( 2x1 − 5x2 )  ⇒ min.
Тогда f ( x1, x2 ) = 29x12 + 38x22 − 8x1x2 − 160x1 − 92x2 + 820. Таким
образом, задача оптимизации будет выглядеть так:
min f ( x1, x2 ),
( )
( )
( )
 g1 x =
− x1 − 3x2 + 18 ≥ 0,


−2x1 − x2 + 10 ≥ 0,
 g2 x =

x1 ≥ 0, g4 x =
x2 ≥ 0.
 g3 x =

( )
Это задача квадратичного программирования. Её можно решить
проще, т. к. ограничения здесь не задевают область D (это её границы), можно решить задачу без ограничений (рис. 4.7).
x2
–2x1–x2 +10=0
5
–x1 –3x2 +18=0
D
xmin=xopt
5
10
Рис. 4.7
Рис. 4.7
98
15 x1
По методу Лагранжа
80,
 29x1 − 4x2 =
⇒=
x1 2.97=
, x2 1.52. xmin = xopt∈D,

46,
−4x1 + 38 x2 =
следовательно это и есть решение с ограничениями. В этой точке
f1(xopt) = -5.87, f2(xopt) = 16.44, f3(xopt) = –1.66.
§ 4.6. Лабораторная работа № 4.
Решение задачи многокритериального выбора.
Метод анализа иерархий
Решим в качестве примера задачу выбора лучшей из предложенных альтернатив методом анализа иерархий. Для этого надо пройти
все четыре основных этапа этого метода: построение иерархий, попарное сравнение альтернатив по каждому критерию, взвешивание
критериев и выбор наиболее предпочтительной альтернативы.
Пример. Цель, альтернативы и описания критериев задачи изложены в табл. 4.6.1.
Таблица 4.6.1
Цель, альтернативы
Критерии
Описание предпочтений
Цена: Самая дорогая – нержавеющая
сталь, металлопласт немного дешевле,
Выбор маармированный пластик ещё дешевле,
териала для
чёрная сталь – самая дешёвая.
водопровоДопустимое давление: Самое большое
z
–
цена
за
один
дных труб:
1
у нержавеющей и чёрной стали, у меметр;
(1) – металталлопласта – существенно ниже, у арz2 – допустимое
лопласт;
мированного пластика ещё ниже.
давление;
(2) – армиДолговечность: Самый долговечрованный
z3 – долговечный – металлопласт, немного мепластик;
ность;
нее – нержавеющая сталь, ещё ме(3) – неz4 – внешний
нее – армированный пластик, самая
ржавеющая
вид.
недолговечная – чёрная сталь.
сталь;
Внешний вид: Лучший – у армирован(4) – чёрная
ного пластика, чуть хуже у металлопласталь.
стика, существенно хуже у нержавеющей и чёрной стали.
Очевидно по описанию предпочтений, что критерий z1 нужно
минимизировать, критерии z2, z3, z4 – максимизировать.
Альтернатив задачи – четыре, они описаны в таблице. Перейдём
к парному сравнению альтернатив по каждому из четырёх крите99
риев. Для этого составим таблицу рейтингов и условия о правилах
их определения. Это наиболее субъективная часть метода анализа
иерархий, причём различные подходы к определению рейтингов
альтернатив влияют на итоговый результат лишь незначительно.
Например, таблица рейтингов может быть такой:
Рейтинг
Описание
Базовый уровень – одинаковое
предпочтение
Умеренное предпочтение
Очевидное предпочтение
Абсолютное предпочтение
1
2
3
4
Рейтинг
Описание
Рейтинг
4
Очевидное ухудшение
2
Умеренное ухудшение
1
Базовый уровень
2
Умеренное предпочтение
1
1
Рейтинг
8
4
Очевидное ухудшение
2
Умеренное ухудшение
1
Базовый уровень
1
Умеренное ухудшение
1
Базовый уровень
1
2
Умеренное предпочтение
1
Очевидное предпочтение
3
Описание
Абсолютное ухудшение
2
1
Описание
Таблица рейтингов создаётся экспертами. При решении конкретной задачи субъект, решающий эту задачу, выступает в роли
эксперта, поэтому предложенные выше таблицы могут иметь и
иной вид.
В нашем примере матрицы попарного сравнения альтернатив по
всем четырём критериям будут размерностью 4×4. Присвоим рейтинги альтернатив по всем критериям, считая рейтинги в пределах 1÷4.
z1 критерий:
(1) альтернатива
z1 критерий:
(2) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
1
0.5
4
0.25
(1)
(2)
(3)
(4)
2
1
4
0.5
100
z1 критерий:
(3) альтернатива
z2 критерий:
(4) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
0.5
0.25
1
0.125
(1)
(2)
(3)
(4)
0.5
0.25
1
1
z1 критерий:
(4) альтернатива
z3 критерий:
(1) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
3
2
4
1
(1)
(2)
(3)
(4)
1
0.25
0.5
0.125
z2 критерий:
(1) альтернатива
z3 критерий:
(2) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
1
0.5
4
4
(1)
(2)
(3)
(4)
4
1
2
0.5
z2 критерий:
(2) альтернатива
z3 критерий:
(3) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
2
1
4
4
(1)
(2)
(3)
(4)
4
0.5
1
0.25
z2 критерий:
(3) альтернатива
z3 критерий:
(4) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
0.5
0.25
1
1
(1)
(2)
(3)
(4)
4
2
3
1
101
z4 критерий:
(1) альтернатива
z4 критерий:
(3) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
1
2
0.5
0.5
(1)
(2)
(3)
(4)
3
4
1
1
z4 критерий:
(2) альтернатива
z4 критерий:
(4) альтернатива
Альтернатива
Рейтинг
Альтернатива
Рейтинг
(1)
(2)
(3)
(4)
0.5
1
0.25
0.25
(1)
(2)
(3)
(4)
3
4
1
1
Матрицы попарного сравнения альтернатив тогда будут иметь
следующий вид.
0.5
 1

2
1
По критерию z1 
 0.5 0.25

2
 3
0.5
 1

2
1
по критерию z2 
 0.5 0.25

 0.5 0.25
4
4
1
4
4 0.25 

4 0.5 
,
1 0.125 

4
1 
4

4
,
1

1 
 1 0.25 0.5 0.125 


4
1
2
0.5 
по критерию z3 
,
 4 0.5
1
0.25 


2
3
1 
4
 1

0.5
по критерию z4 
 3

 3
102
2 0.5 0.5 

1 0.25 0.25 
.
4
1
1 

4
1
1 
Перейдём к третьему-четвёртому этапу взвешиванию критериев
и выбору наиболее предпочтительной альтернативы. Вышеприведённые четыре матрицы нормализуются так, чтобы сумма элементов каждого столбца была равна единице. Получим
 0.154

0.308
по критерию z1 
 0.077

 0.462
0.133
0.267
0.067
0.533
0.308
0.308
0.077
0.308
0.133 

0.267 
,
0.067 

0.533 
 0.250

0.500
по критерию z2 
 0.125

 0.125
0.250
0.500
0.125
0.125
0.400
0.400
0.100
0.100
0.400 

0.400 
,
0.100 

0.100 
 0.077

0.308
по критерию z3 
 0.308

 0.308
0.067
0.267
0.133
0.533
0.077
0.308
0.154
0.462
0.067 

0.267 
,
0.133 

0.533 
 0.133 0.182 0.182 0.182 


0.067 0.091 0.091 0.091 
по критерию z4 
.
 0.400 0.364 0.364 0.364 


 0.400 0.364 0.364 0.364 
Построим теперь вектор приоритетов, элементами которого средние арифметические элементов строк нормализованных матриц.
Вектор приоритетов равен:
 0.182 


0.288 
по критерию z1 
,
 0.072 


 0.459 
 0.325 


0.450 
по критерию z2 
,
 0.113 


 0.113 
103
 0.072 


0.288 
по критерию z3 
,
 0.182 


 0.459 
 0.170 


0.085 
по критерию z4 
.
 0.373 


 0.373 
Осталось найти ранги всех четырёх альтернатив и выбрать лучшую из них.
Ранги альтернатив вычисляются следующим образом: значения текущий строки в векторе приоритетов, соответствующей рассматриваемой альтернативе умножаются на число, характеризующее альтернативу в рассматриваемом критерии, т. е.
ri òåê.êðèò. ⋅ nàëò. â òåê.êðèò.. Например, для первой альтернативы будем иметь
0.182⋅0.182 + 0.288⋅0.325 + 0.072⋅0.072 + 0.459⋅0.170 = 0.210,
для второй альтернативы
0.325⋅0.288 + 0.450⋅0.450 + 0.113⋅0.288 + 0.113⋅0.085 = 0.338,
для третьей альтернативы
0.072⋅0.072 + 0.288⋅0.113 + 0.182⋅0.182 + 0.459⋅0.373 = 0.242,
наконец, для четвёртой альтернативы
0.170⋅0.459 + 0.085⋅0.113 + 0.373⋅0.459 + 0.373⋅0.373 = 0.398.
Итак, рейтинги альтернатив поместим в табл. 4.6.2.
Таблица 4.6.2
Альтернатива
Итоговый рейтинг
(1)
0.210
(2)
0.338
(3)
0.242
(4)
0.398
По итогам вычислений метода анализа иерархий самая предпочтительная альтернатива (4), т. е. следует отдать предпочтение чёрной стали в качестве материала для водопроводных труб.
Проведём теперь проверку согласованности полученных оценок.
Эта проверка в данном методе считается необходимой, если число
альтернатив более четырёх. Это проверка принципа транзитивности альтернатив, именно, если (1)→(2) и (2)→(3), то (1)→(3), т. е. если
альтернатива (1) предпочтительнее (2), а (2) предпочтительнее (3), то
(1) должна быть предпочтительнее (3).
104
При проверке суммы столбцов исходной матрицы попарного
сравнения альтернатив умножаются на элементы соответствующего вектора приоритетов и складываются. Результат, т. е. коэффициент согласия, должен быть приблизительно равен числу рассматриваемых альтернатив.
В нашем случае вектора приоритетов равны:
 0.182 


0.288 

z1 критерий
,
 0.072 


 0.459 
 0.072 


0.288 

z3 критерий
,
 0.182 


 0.459 
 0.325 


0.450 

z2 критерий
,
 0.113 


 0.113 
 0.170 


0.085 

z4 критерий
.
 0.373 


 0.373 
Исходные матрицы попарного сравнения альтернатив имеют вид
z1 критерий
0.5
 1

2
1

 0.5 0.25

2
 3
4 0.25 

4 0.5 
⇒(1 + 2 + 0.5 + 3)⋅0.182 + (0.5 + 1 + 0.25 + 2)⋅ 1 0.125 

4
1 
⋅0.288 + + (4 + 4 + 1 + 4)⋅0.0.072 + (0.25 + 0.5 + 0.125 + 1)⋅0.459 = 4.06≈4.
z2 критерий
0.5
 1

1
 2
 0.5 0.25

 0.5 0.25
4
4
1
4
4

4
⇒4⋅0.325 + 2⋅0.450 + 10⋅0.113 + 100.113 = 4.46≠4.⋅
1

1
z3 критерий
 1 0.25 0.5 0.125 


1
2
0.5 
4
⇒13⋅0.072 + 3.75⋅0.288 + 6.5⋅0.182 +  4 0.5
1
0.25 


+1.875⋅0.459 = 4.06≈4.
2
3
1 
4
105
z4 критерий
 1

 0.5
 3

 3
2 0.5 0.5 

1 0.25 0.25 
⇒7.5⋅0.170 + 11⋅0.085 + 2.75⋅0.373 + 4
1
1 

4.26≠4.
4 +2.75⋅0.373 =
1
1 
Вычислим теперь коэффициент согласованности
(λ − n)
CR =
( n − 1)
RI
,
где n – число альтернатив, RI – индекс–рандомизации (см. след
табл.), λ – полученный коэффициент согласия. В нашем случае n = 4,
RI = 0.9, т. е.
n
1
2
3
4
5
6
7
8
9
10
RI
0
0
0.58
0.9
1.12
1.24
1.32
1.41
1.45
1.49
=
CR1
CR3
=
( 4.06 − 4 )
( 4.46 − 4 )
( 4.06 − 4 )
( 4.26 − 4 )
3 0=
=
.022, CR2
0.9
3 0=
.022, CR4
=
0.9
3 0.170,
=
0.9
3 0.096.
=
0.9
Несогласованность оценок считается приемлемой, если она не
превосходит 0.1, в противном случае необходимо проверить корректность выбранных степеней предпочтения (в нашем случае
у второго критерия).
Поскольку процедура назначения рейтингов имеет субъективный характер, мы не будем пересчитывать второй вариант. Итак,
итоговый вывод неизменен: ранги все четырёх альтернатив по методу анализа иерархий равны
 Àëüòåðíàòèâû Ðàíãè 


(1)
0.210 


(2)
0.338 .


(3)
0.242 


(4)
0.398 

106
Таким образом, подходящий вариант материала для водопроводных труб – альтернатива (4) – чёрная сталь.
1а) Программирование в пакете Mathcad
ORIGIN := 1
n := 4
Çàäàíèå
âåêòîðîâ
ðåéòèíãîâ
Задание
векторов
рейтинговàëüòåðíàòèâ
альтернативäëÿ
для всех критериев
âñåõ êðèòåðèåâ
 1 
 2 
 0.5 
3 



0.5 
 4 
R11 := 


 0.25 
 1

0.5
R21 := 
 4

 4
 1

2
R41 := 
 0.5

 0.5

2

1
R22 := 
4

4






 0.5

0.25

R23 :=
 1

 1
 0.5

1
R42 := 
 0.25

 0.25






 
2
4 
 
1 
R14 := 


 0.125 
 4

1
R32 := 
 2

 0.5







0.25 
 1 
R13 := 


 0.5 






 1

0.25
R31 := 
 0.5

 0.125

1 
 4 
R12 := 


















 4

0.5
R33 := 
 1

 0.25
3

4
R43 := 
1

1
 0.5

0.25
R24 := 
 1

 1






4

2
R34 := 
3

1






3

4
R44 := 
1

1


















Исходные матрицы попарного сравнения альтернатив
 1

2
MZ1 := 
 0.5

 3
0.5
4
0.25 
1
4
0.25
1
0.5 
0.125 


 1

2
MZ2 := 
 0.5

 0.5
2
4
 1 0.25 0.5 0.125 


4
1
2
0.5 
MZ3 := 
 4 0.5
1
0.25 


3
1 
2
4
 1

0.5
MZ4 := 
 3

 3

1
0.5
4
4
1
4
0.25
1
4
1
0.25
1
1


2
0.5
0.5 
1
0.25
4
1
0.25 
1 
4
1
1 


107
Вычисление нормализованных матриц попарного сравнения альтернатив
MatrAlt ( A , n) :=
for
i ∈ 1 ..
n
ai ← 0
j ∈ 1 ..
for
n
ai ← ai + Aj , i
a
a := MatrAlt ( MZ1 , n)
b := MatrAlt ( MZ2 , n)
c := MatrAlt ( MZ3 , n)
 4 
 
2 
b=
 10 
 
 10 
 6.5 


3.75 
a=
 13 


 1.875 
i := 1 ..
j := 1 ..
n
MZN1 j , i :=
MZN3 j , i :=
d := MatrAlt ( MZ4 , n)
 13 


3.75 
c=
 6.5 


 1.875 
n
MZ1 j , i
MZN2 j , i :=
ai
MZ3 j , i
MZN4 j , i :=
ci
 0.154

0.308
MZN1 = 
 0.077

 0.462
0.133
0.308
0.133 
0.267
0.308
0.067
0.077
0.267 
0.067 
0.533
0.308
0.533 
 0.077

0.308
MZN3 = 
 0.308

 0.308
0.067
0.077
0.067 



0.267 0.308 0.267 
0.133 0.154 0.133 

0.533 0.462 0.533 
MZ2 j , i
bi
MZ4 j , i
di
 0.25 0.25 0.4

0.5
0.5
0.4
MZN2 = 
 0.125 0.125 0.1

 0.125 0.125 0.1
 0.133

0.067
MZN4 = 
 0.4

 0.4
Вычисление векторов приоритетов
VectPr ( A , n) :=
for
i ∈ 1 ..
n
ai ← 0
for
j ∈ 1 ..
ai ← ai +
a
108
 7.5 


11 
d=
 2.75 


 2.75 
n
Ai , j
n
0.4 

0.4 
0.1 

0.1 
0.182
0.182
0.182 
0.091
0.091
0.364
0.364
0.091 
0.364 
0.364
0.364
0.364 


Pr1 := VectPr ( MZN1 , n)
Pr3 := VectPr ( MZN3 , n)
 0.182 


0.287 
Pr1 = 
 0.072 


 0.459 
Pr2 := VectPr ( MZN2 , n)
Pr4 := VectPr ( MZN4 , n)
 0.325 


0.45 
Pr2 = 
 0.113 


 0.113 
 0.072 


0.287 
Pr3 = 
 0.182 


 0.459 
 0.17 


0.085 
Pr4 = 
 0.373 


 0.373 
Вычисление итоговых рангов альтернатив по методу анализа иерархий
Rang 1 := Pr1 1 ⋅ Pr1 1 + Pr1 2 ⋅ Pr2 1 +
Rang 2 := Pr2 1 ⋅ Pr1 2 + Pr2 2 ⋅ Pr2 2 +
Rang 3 := Pr3 1 ⋅ Pr1 3 + Pr3 2 ⋅ Pr2 3 +
Rang 4 := Pr4 1 ⋅ Pr1 4 + Pr4 2 ⋅ Pr2 4 +
 0.21 

 0.21
 
  0.338
 
Rang = 0.338
 
Rang =  0.242
 0.242
 

 
  0.397
 0.397 
Pr1 3 Pr3 1 + Pr1 4 ⋅ Pr4 1
Pr2 3 Pr3 2 + Pr2 4 ⋅ Pr4 2
Pr3 3 Pr3 3 + Pr3 4 ⋅ Pr4 3
Pr4 3 Pr3 4 + Pr4 4 ⋅ Pr4 4
Проверка согласованности
λ1
:= a ⋅ Pr1
:= b ⋅ Pr2
λ3 := c ⋅ Pr3
λ4 := d ⋅ Pr4
λ2
i := 1 ..
λ2
:= λ1
:= λ2
λ 3 := λ3
λ 4 := λ4
λ1
λ2
n
(λ i−n)
CR i :=
= 4.054
= 4.45
λ3 = 4.054
λ4 = 4.256
λ1
( n−1)
0.9
 0.02 


0.167 

CR =
 0.02 


 0.095 
Задание № 1. Выбрать свой вариант из следующих вариантов заданий и решить задачу многокритериального выбора методом анализа иерархий. Номер Вашего варианта – номер Вашей фамилии
в журнале преподавателя (табл. 4.6.3).
109
110
Покупка автомобиля:
(1) – Suzuki,
(2) – Mitsubishi,
(3) – Honda,
(4) – Toyota
Выбор спутницы
жизни:
(1) – Татьяна,
(2) – Лариса,
(3) – Наталья,
(4) – Ольга.
Выбор дороги:
(1) – Автострада,
(2) – Шоссе,
(3) – Грейдер,
(4) – Просёлок.
1
2
3
Номер
вари- Цель, альтернативы
анта
Описание предпочтений
Стоимость: Suzuki существенно дороже всех, Honda немного дороже
Mitsubishi, Toyota существенно дешевле всех.
z1 – стоимость,
Расходы на обслуживание: Mitsubishi дороже всех, Toyota и Suzuki приz2 – расходы на
мерно равны, Honda дешевле всех.
обслуживание,
Расход бензина: самый высокий у Suzuki, немного меньше у Honda,
z3 – расход бензина,
существенно меньше у Mitsubishi, самый низкий – у Toyota.
z4 –комфорт
Комфорт: самая комфортная – Toyota, чуть менее – Mitsubishi, существенно хуже – Honda, самая некомфортная – Suzuki
Внешность: Лариса – красавица, Татьяна – довольно миловидна, Ольz1 – внешность,
га – симпатична и стройна, Наталья – малопривлекательна.
z2 – финансовые
Финансовые запросы: самые большие у Ольги, чуть менее у Татьяны,
запросы,
выше среднего – у Натальи, ниже среднего – у Ларисы.
z3 – домовитость,
Домовитость: самая хозяйственная – Наталья, чуть менее – Ольга, сущеz4 – характер
ственно менее – Татьяна, ещё менее – Лариса
Расстояние: самое большое на автостраде, чуть меньше – по шоссе, существенно меньше по грейдеру, самое короткое – по просёлку.
Качество покрытия: лучшее – на автостраде, существенно хуже – на
z1 – расстояние,
шоссе, ещё хуже – на грейдере, отсутствует – на просёлке.
z2 – качество поКонтроль: самый жёсткий – на автостраде, на шоссе – почти такой же
крытия,
жёсткий, много мягче – на грейдере, на просёлке – практически отсутz3 –контроль,
ствует.
z4 – ифраструктура
Инфраструктура: самая развитая – на шоссе, чуть менее на автостраде,
существенно менее – на грейдере, на просёлке – практически отсутствует
Критерии
Варианты задач многокритериального выбора
(варианты взяты из работы [1]
Таблица 4.6.3
111
Выбор породы дерева для строительства дачи:
(1) – Берёза,
(2) – Сосна,
(3) – Дуб,
(4) –Лиственница.
Выбор устройства
для работы в социальных сетях:
(1) – Компьютер,
(2) – Ноутбук,
(3) – Планшет,
(4) – Смартфон
Выбор спутника
жизни:
(1) – Анатолий,
(2) – Александр,
(3) – Владимир,
(4) – Денис
4
5
6
Номер
вари- Цель, альтернативы
анта
Описание предпочтений
Цена за один м3: самый дорогой – дуб, лиственница немного дешевле, сосна ещё дешевле, берёза – самая дешёвая.
z1 –цена за один м3, Лёгкость обработки: самая лёгкая в обработке – берёза, сосна – сущеz2 – легкость обственно тяжелее, дуб – ещё тяжелее, самая тяжёлая в обработке – лиработки,
ственница.
z3 – долговечность, Долговечность: самая долговечная – лиственница, чуть менее – дуб,
z4 – водостойкость существенно менее – сосна, самая недолговечная – берёза.
Водостойкость: самая водостойкая лиственница, чуть менее – сосна,
существенно менее – дуб, ещё менее – берёза
Цена: компьютер и ноутбук сравнимы по стоимости, смартфон немного
дешевле, планшет существенно дешевле.
Стоимость обслуживания: самый дорогой – смартфон, планшет немного
z1 –начальная цена,
дешевле, ноутбук – ещё дешевле, самый дешёвый – компьютер.
z2 – стоимость обЁмкость ЗУ: компьютер и ноутбук имеют и внешнюю и оперативную
служивания,
память сравнимой ёмкости, планшет и смартфон – только оперативную
z3 – ёмкость зу,
память, меньшей ёмкости.
z4 – размер экрана
Размер экрана: самый большой – у компьютера, немного меньше – у
ноутбука, существенно меньше – у планшета, самый маленький – у
смартфона
Образование: Денис учится в аспирантуре, Александр закончил технический вуз, Владимир – военное училище, Анатолий – экономический
z1 – образование,
колледж.
z2 – физическая
Физическая подготовка: самый физически крепкий – Владимир, Алекподготовка,
сандр и Денис уступают немного, Анатолий – существенно.
z3 – внешность,
Внешность: Анатолий и Владимир – красавцы, Александр и Денис – доz4 – характер
вольно симпатичны.
Характер: Анатолий – повеса и сердцеед, Александр – оптимист и трудяга, Владимир – лидер и карьерист, Денис – умница и самоед
Критерии
Продолжение табл. 4.6.3
112
z1 – стоимость
пакета,
z2 – скорость,
z3 – служба поддержки,
z4 – качество услуг
z1 – размер стипендии,
z2 – квалификация
преподавателей,
z3 –стоимость жизни в городе,
z4 – престижность
диплома
Выбор университета
для поступления:
(1) – Oxford,
(2) – МГУ,
(3) – ТГУ (Томский),
(4) – Тамбовский
ГУ.
7
8
Критерии
Выбор интернетпровайдера:
(1) – «LanTa»,
(2) – «Ростелеком»,
(3) – «Зелёная
точка»,
(4) – «Комстар-Регионы».
Номер
вари- Цель, альтернативы
анта
Стоимость: самая большая – у «Зелёной точки», немного меньше – у
«Комстар-Регионы», существенно меньше – у «Ростелекома», самая
маленькая – у «LanTa».
Скорость: самый скоростной – «Комстар-Регионы», чуть менее – у
«LanTa», ещё меньше – у «Зелёной точки», самый медленный – «Ростелеком».
Служба поддержки: самая оперативная – у «LanTa», немного хуже – у
«Ростелекома» и «Зелёной точки», самая плохая – у «Комстар-Регионы».
Качество услуг: лучшее качество –у «Зелёной точки», чуть хуже – у
«Ростелекома», ущё хуже – у «Комстар-Регионы», самые некачественные – у «LanTa»
Стипендия: Oxford не платит стипендии студентам, в Тамбовском ГУ
стипендия небольшая, в Томском университете немного больше, в Московском – существенно больше.
Квалификация преподавателей: самые квалифицированные в Oxford′е,
чуть менее квалифицированные в Московском университете, существенно менее в Томском университете, самая низкая квалификация – в
Тамбовском ГУ.
Стоимость жизни: самая низкая в Тамбове, существенно выше в Томске,
горазда выше в Москве, самая высокая в Лондоне.
Престижность диплома: самый престижный – Oxford, немного менее –
Московского университета, существенно менее – Томского, самый непрестижный – Тамбовский ГУ
Описание предпочтений
Продолжение табл. 4.6.3
113
Номер
вари- Цель, альтернативы
Критерии
анта
Выбор санатория
для отдыха:
(1) – «Липецк», г.
z1 – качество лечеЛипецк,
ния,
(2) – «Сосновый
z2 – уровень сербор», Тамбовский
виса,
9
район,
z3 – качество пита(3) – «Лесная
ния,
жемчужина», г.
z4 – расстояния от г.
Котовск,
Тамбова
(4) – «Сосны», г.
Пенза
Качество лечения: самое качественное в «Липецке», чуть хуже в «Соснах», ещё хуже в «Лесной жемчужине», самое некачественное в «Сосновом бору».
Сервис: лучший в «Сосновом бору», немного хуже в «Соснах», существенно хуже в «Липецке» и «Лесной жемчужине».
Питание: самое качественное в «Соснах», немного хуже в «Лесной жемчужине», существенно хуже в «Липецке» и «Сосновом бору».
Расстояние: дальше всего расположены «Сосны», чуть ближе «Липецк»,
«Сосновый бор» и «Лесная жемчужина» совсем рядом с Тамбовом
Описание предпочтений
Окончание табл. 4.6.3
V. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ РИСКА
И НЕОПРЕДЕЛЁННОСТИ [3]
§ 5.1. Принятие решений в условиях риска.
В данном разделе рассматриваются ситуации, когда каждый из
вариантов решения может быть реализован с известной вероятностью (принятие решений в условиях риска) и когда эти вероятности неизвестны (принятие решений в условиях неопределённости).
В качестве критерия принятия решения в задачах экономического
профиля, как правило, используется ожидаемое значение стоимости.
Принятие решений в условиях риска – эта своеобразная игра
с природой. Поведение природы, т. е. среды носит случайный характер. Считается, что существует некоторая вероятностная мера, в соответствии с которой наступают те или иные состояния природы.
Кроме того, принятие решений в условиях риска всегда предполагает, что существует некоторая дополнительная информация о
вероятностных состояниях природы. Если множество состояний
среды Sm конечно, (S = {S1, S2,…, Sm}), то вероятностная мера на этом
множестве может быть задана вероятностным вектором
P = {p1, p2,…, pm}, pj≥0,
m
∑ pj = 1.
j =1
Таким образом, матрица выигрышей (или платежей в зависимости от контекста задачи) может быть представлена в следующем
виде.
Состояния среды и их вероятности
Решения
(альтернативы)
S1
…
Sj
…
Sm
p1
…
pj
…
pm
a1
v11
…
v1j
…
v1m
…
…
…
…
…
…
ai
vi1
…
vij
…
vim
…
…
…
…
…
…
an
vn1
…
vnj
…
vnm
Итак, vij – выигрыш или платёж для решения ai при осуществлении состояния среды Sj. Исходом для игрока, т. е. лица, при114
нимающего решение, при выборе решения ai является случайная
величина
 vi,1,vi,2 ,...,vi,m 
ξi =
,
 p1, p2 ,..., pm 
т. е. сравнение двух решений a1 и a2 сводится к сравнению соответствующих им случайных величин ξ1 и ξ2.
Выбор оптимального решения обычно основывается на одном из
следующих критериев.
1) Критерии Байеса*–Лапласа.
2) Комбинации ожидаемого значения и его дисперсии.
3) Критерий произведения.
4) Наиболее вероятного события в будущем и др.
Рассмотрим сначала на примерах наиболее простые подходы.
а). Построение «дерева решений» и таблицы исходов.
Пример 1. Для финансирования проекта бизнесмену нужно занять сроком на один год 15 млн. руб. Банк ссудит деньги под 15%
годовых или вложит в дело со 100% возвратом сумм, но под 9% годовых. Статистика банка говорит, что 4% клиентов ссуду не возвращают. Давать заём или нет?
При решении подобных задач рекомендуется строить так называемое «дерево решений». Построим его в виде следующей таблицы.
Альтернатива
Действия
А
Дать заём
В
Инвестировать под 9%
Вероятности
Возврат, млн.
руб.
Вернули: 0.96
15×1.15 = 17.25
Не вернули: 0.04
0
1.0
Ожидаемый
доход, млн. руб.
17.25×0.96–
–15 = 1.56
0–15 = –15
15×1.09 = 16.35 16.35–15 = 1.35
Из этой таблицы видно, что ожидаемый доход по альтернативе
А больше, следовательно, нужно выдать заём. По таблице и дереву
решений выбран более вероятный вариант решения, но в действительности ситуация может быть и обратной. Здесь важно знать, насколько используемые вероятности чувствительны к изменению
реальных условий.
б). Функция «полезности».
В приведённом примере критерий оптимальности выражался
в виде реальных денег. Часто бывают ситуации, когда лучше сле* Томас Байес (1702–1761) – английский математик.
115
U
100
–10 +10
a
b
X
Y
c
Z
d
f
–20
e
0
+20
+40
Рис. 5.1
дует использовать «полезность» действий, чем сумму платежей. Например, если предположить, что существует 50% вероятность, что
инвестиция в 20 млн. руб. принесёт прибыль 40 млн. руб. и с той же
вероятностью может быть полностью потеряна. Соответствующая
ожидаемая прибыль равна 40.0⋅0.5–20.0⋅0.5 = 10 млн. руб.
Функция «полезности» как критерий выбора оптимальной альтернативы выражает отношение человека (инвестора) к конкретной ситуации, т. е. здесь к риску выиграть или проиграть определённую сумму.
Пусть U – шкала полезности 0 ≤ U ≤ 100, где нуль соответствует
полезности –20 млн. руб., а 100 – + 40 млн. руб. Если инвестор относится к делу беспристрастно, то результирующая функция – это прямая, соединяющая точки (–20, 0) и (40, 100) – это прямая Y (рис. 5.1).
В этом случае полезность равна денежной оценке результата. Если же
учитывать риск и отказ от риска инвестора, то функция полезности
может принимать вид X, Z или W. Кривая X характеризует осторожность, большую чувствительность к потере, чем к прибыли. При изменении на 10 млн. руб. вправо от точки 0 полезность увеличивается
на длину отрезка [a, b], а влево – уменьшается на длину отрезка [b, c],
при этом |a, b| < |b, c|. Кривая Z, наоборот, характеризует склонность
к риску; при тех же изменениях ±10 млн. руб. движение вправо предпочтительнее движения влево – |d, e| > |e, f|.
В общем случае график оценки полезности риска в зависимости
от его суммы имеет вид удлинённой буквы S, т. е. это кривая W.
К сожалению, процедура определения функции «полезности» имеет большой элемент субъективизма и эмпиризма.
в) Критерий Байеса–Лапласа.
Использование в критериях матожиданий и дисперсий параметров задачи предполагает возможность многократного решения
116
одной и той же задачи, пока не будут получены достаточно точные
расчётные формулы. Это – вероятностный подход.
Если ξi – случайная величина и
1 n
1 n
2
=
a
,
D
ξ
∑ i
∑ ( ai − Mξ ) ,
1
n
n
−
=i 1=i 1
=
Mξ
Dξ
→ 0. Таким
n
образом, использование критерия Байеса–Лапласа справедливо
только тогда, когда если одно и то же решение применяется достаточно большое число раз (n→∞).
Пример 2. Фирма купила станок за 100$. Для его ремонта можно
купить специальное оборудование за 50$ или обойтись старым оборудованием. Если станок выходит из строя, его ремонт со спецоборудованием обходится в 10$, без спецоборудования в 40$. По техзаданию известно, что в течение срока эксплуатации станок выходит
из строя не более трёх раз: не сломаться p1 = 0.3, сломаться один раз
p2 = 0.4, сломаться два раза p3 = 0.2, сломаться три раза p4 = 0.1.
Определить целесообразность покупки специального оборудования.
Решение. Стратегии (альтернативы) лица, принимающего решения две: a1 – покупать спецоборудование и a2 – не покупать его.
Природа (второй игрок) имеет четыре состояния: станок не выйдет из строя, сломается один раз, два раза и три раза. Функция выигрыша – затраты фирмы на покупку и ремонт станка. Эти данные
приведены в следующей таблице.
то по теореме Муавра*–Лапласа при n→∞, a → Mξ,
Решения (альтернативы)
Состояния среды: выход станка из строя
и вероятности этих событий
S1
S2
S3
S4
p1
p2
p3
p4
a1 – не покупать
–100
–140
–180
–220
а2 – купить
–150
–160
–170
–180
Седловая точка решения.
Если задана матрица задачи (как в нашем случае), то её седловая
точка – это наибольший элемент столбца этой матрицы, который
одновременно является наименьшим элементом соответствующей
строки. В этом случае верхняя и нижняя цена стратегии выбора со* Абрахам де Муавр (1667–1754) – английский математик.
117
впадают. Геометрически это означает,
что имеется точка поверхности, являющаяся одновременно минимумом по
одной координате и максимумом по
другой (рис. 5.2). На этом рисунке S –
седловая точка функции z = f(x, y).
В нашем случае седловая точка –
точка с координатой –180. Если использовать решение с седловой точкой,
то следует выбрать решение (альтернативу) а2, здесь затраты на покупку и
z
S
x
y
Рис. 5.2
ремонт минимальны.
Учтём теперь вероятности состояний S1, S2, S3 и S4. Для первого
решения
Mξ1 = –100⋅⋅0.3–140⋅0.4 – 180⋅0.2 – 220⋅0.1 = –144,
для второго
Mξ2 = –150⋅0.3 – 160⋅0.4 – 170⋅0.2 – 180⋅0.1 = –161.
Таким образом, выбирается решение а1.
В игре с природой ориентация на математическое ожидание выигрыша – есть ориентация на средний выигрыш, который случается при многократном повторении данной ситуации. При единичном
испытании ориентироваться на такой результат не следует.
Пример 3. Фирма 1 выставляет на продажу два товара Т11 и Т12,
фирма 2 – три товара Т21, Т22 и Т23. Товары Т11 и Т21 – конкурирующие, товары Т11 и Т23 дополняют друг друга, остальные товары нейтральны. Прибыль фирмы 1 зависит от сочетания товаров,
выставляемых на продажу обоими фирмами. Данные в следующей
таблице.
Состояния среды
Решения
(альтернативы)
S1
S2
S3
p1
p2
p3
a1
8
18
40
а2
18
15
14
При этом известно, что фирма 2 товар Т23 выставляет в три раза
реже Т21 и в четыре раза реже чем Т22. Какой же товар следует поставлять на продажу фирме 1?
118
Решение.
Mξ1 = 8 ⋅ 3 + 18 ⋅ 4 + 40 ⋅ 1 = 17,
8
8
8
Mξ2 = 18 ⋅ 3 8 + 15 ⋅ 4 8 + 14 ⋅ 1 8 = 16.
По этому критерию – оптимальное решение а1, т. е. фирма 1
должна поставлять товар Т11 (выигрыш незначителен). Если составить таблицу с указанием отклонения возможных выигрышей от
их матожиданий и вероятности этих отклонений, то получим
Состояния среды
Решения (альтернативы)
p1 = 3 8
p2 = 4 8
p3 = 1 8
Mξ
a1
–9
1
23
17
а2
2
–1
–2
16
Видно, что при почти равных ожидаемых выигрышей, по разному ведут себя отклонения от ожидаемых выигрышей, для решения
а1 эти отклонения значительны, а для а2 – сравнительно невелики.
Из предыдущего можно сделать следующий вывод: критерий Байеса-Лапласа не является адекватным, в нём должны учитываться
возможные отклонения случайной величины от её математического ожидания.
Решим теперь эту же задачу с дополнительным учётом дисперсии Dξ. Здесь для принятия решения в условиях риска выбор альтернативы а1 приводит к случайной величине ξi, которая характеризуется парой показателей (Mξ, Dξ) или (Mξ, σξ).
Фактически получаем задачу двухкритериальной оптимизации
(по Mξ и по Dξ), причём значение первого критерия Mξ нужно максимизировать, а значение второго Dξ – минимизировать. Вычислим
Dξ1 и Dξ2.
Состояния среды
Решения
(альтернативы)
p1 = 3 8
p2 = 4 8
p3 = 1 8
Mξ
Dξ
σξ
а1
8
18
40
17
203.7
14.27
а2
18
15
14
16
2.0
1.41
Итак, а1 = (17↑, 14.27↓) и а2 = (16↑, 1.41↓). Эти два решения не доминируют друг друга и, следовательно, входят во множество Паре119
то P = {а1, а2} (рис. 5.3). Если бы имелись Mξ и Dξ для каждого решения
15
и для каждого состояния среды, то
a1
множество состояло бы из шести
элементов. В процессе статисти5
ческого эксперимента это можно
a2
принципиально получить.
15
5
Для сужения множества Паa1
рето, как известно, применяются
Рис. 5.3
два подхода: лицо, принимающее
решение на основе неформальных
дополнительных сведений принимает решение и множество Парето
сужается формальными методами.
Рассмотрим второй подход на основе сужения Парето-оптимальных альтернатив.
а) Назначение нижних и верхних границ. Назначим верхнюю
границе по критерию D = 5. Тогда оптимальным будет решение а2.
б) Возьмём в качестве критерия этой задачи функцию вида
f(M, D) = M–λ⋅D, где λ = const, λ≤ ≥0. Это аддитивный критерий оптимальности частных критериев по M и D с весами 1 и –λ. При λ > 0
оценка случайной величины с помощью этого критерия меньше,
чем её среднее значение, т. е. это характерно для лица, принимающего решение, не склонного к риску. Напротив, при λ < 0 оценка
по формуле M–λ⋅D выше чем среднее значение, это характерно для
лица, принимающего решение, склонного к риску.
Пример 4. (Выбор варианта производства товара). Фирма выпускает продукцию шести видов: зонтики (З), куртки (К), плащи (П),
сумки (С), туфли (Т), шапки (Ш). Нужно принять решение, какую
из видов продукции выпускать в течение предстоящего летнего сезона. Прибыль зависит от того, какое будет лето: дождливым, жарким или умеренным. Какой же вариант будет оптимальным? Исходные данные приведены в следующей таблице.
a2
Решения
З
К
П
С
Т
Ш
120
Д
Состояния среды
Ж
У
80
70
70
50
75
35
60
40
50
50
50
75
40
80
60
70
50
60
Нужна информация о вероятностях наступления дождливого,
жаркого и умеренного сезона. Тогда – эта задача принятия решения в условиях риска. Предположим, что вероятности дождливого,
жаркого и умеренного сезона равны 0.2, 0.5 и 0.3. Тогда можно составить следующую исходную таблицу задачи.
Решения
З
К
П
С
Т
Ш
Д, p = 0.2
Состояния среды
Ж, p = 0.5
У, p = 0.3
Случайные величины
80
70
70
50
75
35
60
40
50
50
50
75
40
80
60
70
50
60
ξ1
ξ2
ξ3
ξ4
ξ5
ξ6
Найдём матожидания и дисперсии всех шести случайных величин. Будем иметь следующие данные MЗ = 58, MК = 58, MП = 57,
MС = 56, MТ = 55, MШ = 62.5, DЗ = 196, DК = 336, DП = 61, DС = 84,
DТ = 100, DШ = 231.5, σЗ = 14.0, σК = 18.3, σП = 7.8, σС = 9.2, σП = 10.0,
σШ = 15.2. Составим таблицу значений критериев M и σ для каждой
рассматриваемой альтернативы.
Критерии
Рейтинги
M
σ
З
58
14.0
К
58
18.3
П
57
7.8
С
56
9.2
Т
55
10.0
Ш
62.5
15.2
Представим рассматриваемые решения точками на координатной
плоскости M и σ, получим множество Парето, из которого Парето-оптимальными будут решения З, П,
Ш (рис. 5.4). Окончательный выбор
оптимальной альтернативы из этого
множества должно производить лицо,
принимающее решение, по своим дополнительным критериям.
M
60
С
П
45
З
Ш
Т
К
30
15
5
10 15
20
σ
Рис. 5.4
121
Сужение этого Парето-оптимального множества может быть
проведено по общему принципу доминирования. Проделаем это.
1) аК < aЗ, аК выбрасываем, в множестве Парето помещаем aЗ,
P = {aЗ}.
2) aЗ и aП несравнимы, P = {aЗ, aП}.
3) aЗ доминирует aС, aС выбрасываем.
4) aЗ и aТ несравнимы, P = {aЗ, aП, aТ}.
5) aЗ и aШ несравнимы , P = {aЗ, aП, aТ, aШ}.
6) aП доминирует aТ, aТ выбрасываем, P = {aЗ, aП, aШ}.
7) aП и aШ несравнимы, P = {aЗ, aП, aШ}.
8) aШ не доминирует aЗ aП, P = {aЗ, aП, aШ}.
Итак, множество Парето P = {aЗ, aП, aШ}. Из оставшихся трёх решений оптимальное выбирается только на основе дополнительной
информации.
§ 5.2. Принятие решений в условиях риска
с возможностью проведения эксперимента
Основная проблема подобных задач – незнание лицом, принимающим решения, истинного состояния среды. Все рассмотренные
до сих пор критерии дают лишь способ рационального анализа неопределённости, не устраняя самой неопределённости. Её устранение или хотя бы уменьшение возможно только на основе уточнения
состояния среды.
На практике такое уточнение возможно с помощью сбора дополнительной информации или проведения эксперимента об условиях
среды. Подобного рода эксперимент называется идеальным, если
лицо, принимающее решение, узнаёт истинное состояние среды.
Одна из методик, позволяющая решить эту проблему основана
на формуле Байеса – формуле переоценки вероятностей событий по
результатам опыта. Доказано, что идеальный эксперимент выгоден
тогда и только тогда, когда его стоимость меньше минимально ожиm
даемого риска, т. е. min ∑ ri,j pj > c, ri,j – риски, с – стоимость эксi
j =1
перимента.
Условная вероятность события A при происшествии события B
равна
P( A ⋅ B)
P AB =
.
P( B)
( )
122
Пусть B1, B2,…, Bm – полная группа событий и известны
P Bj , j = 1,m. Если к тому же известны условные вероятности
( )


P  A B , j = 1,m,
j

то условная, т. е. послеопытная вероятность события Bj по формуле
Байеса равна


P Bj ⋅ P  A 
P
B
A
⋅
B
j
j
 Bj 

P
.
=

 =
A
m
P
A
( )


A 
∑ P Bj ⋅ P  Bj 
(
( )
)
j =1
( )
Пусть теперь дана проблема, заданная с помощью матрицы выигрышей (см. табл. на стр. 114). В ней S1, S2,…, Sm – состояния среды,
vi,j – выигрыш игрока по стратегии ai в среде Sj. Известна вероятность P(Sj) = pj, причём, очевидно,
P(Sj)≥0,
m
∑ P ( Sj ) = 1.
j =1
P(Sj) – доопытные вероятности. Проводится некоторый эксперимент. По его результатам наблюдается событие А и известны условные вероятности


P  A S , j = 1,m.
j


Найдём послеопытные (апостериорные) вероятности каждого состояния среды.
Пример. Руководитель поисковой группы нефтяной компании
должен принять решение: бурить нефтяную скважину или нет.
Скважина может оказаться «сухой» (С), т. е. без нефти, «маломощной» (М), т. е. с малым содержанием нефти и «богатой» (Б), т. е.
с большим содержанием нефти. Альтернативами руководителя
группы являются a1 – бурить, a2 – не бурить. Чистая прибыль при
выборе одной из альтернатив в зависимости от возможного типа
скважины приведена в следующей таблице прибылей.
Тип скважины
Альтернатива
С
М
Б
a1
a2
–70
0
50
0
200
0
123
Кроме того, руководителю поисковой группы известно, что в данной местности вероятности сухой, маломощной и богатой скважины таковы: P(C) = 0.5, P(M) = 0.3, P(Б) = 0.2. Руководитель поисковой
группы может провести эксперимент с целью уточнения структуры грунта (состояния среды). Этот эксперимент представляет собой
сейсморазведку, результатом которой будет ответ – какова структура грунта в данной местности. Структура грунта может быть либо
открытой (О), либо закрытой (З). Руководитель группы имеет таблицу результатов экспериментов, проведённых в данной местности.
Тип скважины
Структура грунта
Всего
О
З
С
n1,1 = 45
n1,2 = 5
50
М
n2,1 = 11
n2,2 = 19
30
Б
n3,1 = 4
n3,2 = 16
20
Всего
60
40
100
Эта таблица показывает, сколько раз на грунтах открытой и замкнутой структуры встречались скважины типа С, М и Б.
Проведём анализ данных всех полученных таблиц. Предположим, что проведено n экспериментов, результаты которых – значения дискретных случайных величин X (тип скважины) и Y (структура грунта), которые принимают соответственно значения С, М, Б
и О, З. Обозначим через n1,1 число экспериментов, в которых X = C,
Y = О, через n1,2 – число экспериментов, в которых X = C, Y = З, через
n2,1 – число экспериментов, в которых X = M, Y = O и т.д. В нашем
ni,j ni,j
случае n = 100, n1,1 = 45, n1,2 = 5, n2,1 = 11. Тогда p=
=
. Поi,j
n
100
лучаем таблицу двумерного законы распределения случайной величины (X, Y).
X, тип скважины
Y, структуры грунта
О
З
2
∑ pi,j
j =1
C
p1,1 = 0.45
p1,2 = 0.05
0.50
М
p2,1 = 0.11
p2,2 = 0.19
0.30
Б
p3,1 = 0.04
p3,2 = 0.16
0.20
∑ pi,j
0.60
0.40
1
3
i =1
124
Из этой таблицы следует P(X = C) = P(C) = 0.5, P(X = M) = P(M) = 0.3,
P(X = Б) = P(Б) = 0.2, P(Y = O) = P(O) = 0.6, P(Y = З) = P(З) = 0.4.
Руководитель поисковой группы должен принять одно из следующих решений:
1) Провести эксперимент (сейсморазведку, её стоимость 10 ед.).
2) Если провести сейсморазведку, то как поступить в дальнейшем в зависимости от результатов эксперимента.
Задача стала многошаговой. Опишем её шаги.
Шаг 1. Построим дерево решений. Его ветви соответствуют возможным альтернативам, вершины – возникающим ситуациям.
Альтернативы руководителя группы: α – отказ от эксперимента,
β – проведение эксперимента (сейсморазведки), a1 – бурить, a2 – не
бурить (разведочную скважину). Состояния природы: тип скважины (С, М, Б) и структура грунта (О, З).
Решения принимаются следующим образом. В начальной позиции ход делает руководитель группы: либо выбрать решение α или
решение β. Если он отказался от эксперимента, то игра переходит
в следующую позицию: бурить скважину – альтернатива a1 или не
бурить – альтернатива a2.
Если же в начальной позиции руководитель группы принимает
решение β, то игра переходит к ходу природы, которая выбирает
одно из состояний О или З (рис. 5.5).
–70 50 200
–70
–70 50 200
50 200 P(C) P(M) P(Б)
З
P(C) P(М) P(Б)
a1
a1
О
a2
О
95
a2
a1
0
a2
З
Эксперимент
Без экс.
Начало
–Ход руководителя
– Ход природы
Рис. 5.5
125
Шаг 2. Для каждого решения, которое является ходом природы,
(обозначение ), надо найти вероятность этого хода. Следует в данной ситуации поступать так: для каждой позиции дерева (см. рис.
5.5) существует единственный путь, соединяющей её с корнем дерева
( ). Если это для позиции природы и путь, соединяющий её с корнем дерева, не проходит через позицию эксперимента , то вероятности состояний P(C), P(M), P(Б) являются априорными (доопытными) и находятся из таблицы распределения (X,Y): P(C) = 50/100 = 0.5,
P(M) = 30/100 = 0.3, P(Б) = 20/100 = 0.2.
Если же путь позиции природы проходит через позицию , то
вероятности состояний среды становятся условными вероятностями и находятся по формулам Байеса (стр. 123) и по данным таблицы
распределения (X,Y).
( )
P C
=
O
(
)
=
P ÌO
( )
P Á
=
O
P ( CÏÎ ) 45
P ( CÏÇ ) 5
=
,=
P CÇ
=
,
P(O)
60
P(Ç)
40
( )
P ( ÌÏÇ ) 19
P ( ÌÏÎ ) 11
P Ì
=
,=
=
,
Ç
P(Ç)
40
P(O)
60
( )
P ( ÁÏÎ ) 1
P ( ÁÏÇ ) 16
P Á
=
,=
=
,
Ç
P(O)
P(Ç)
15
40
( )
P(O) = 0.6, P(З) = 0.4.
Шаг 3. Проведём оценку всех позиций дерева решений (см. рис.
5.5). Оценкой позиции служит ожидаемый выигрыш в этой позиции. Этот выигрыш считается по-разному в зависимости от из какого типа события выходят решения (рис. 5.6). Принцип этих рисун-
a1
a2
a3
b1
b2
b3
p2
p1
p3
b
a
a=p 1a1+p 2a2+ p 3a3
b=max(b 1, b 2, b 3)
Рис. 5.6
126
ков очевиден: для позиции природы её оценки представляют собой
ожидаемый выигрыш, а для позиции руководителя группы оценкой служит максимум из всех позиции (рис. 5.6). На рисунке общего дерева (см. рис. 5.5) видно, что в начальной позиции ожидаемая
прибыль без проведения эксперимента (α) – 20 единиц, с проведением эксперимента (β) – 28 единиц. Таким образом, целесообразным
является решение – проведение эксперимента (сейсморазведки).
Далее. если эксперимент покажет, что грунт открытый, то бурение производить не следует, а если замкнутый, то нужно бурить (см.
рис. 5.5).
1 ветвь: −70 ⋅
мента.
2 ветвь: ∅.
5
3
2
+ 50 ⋅ + 200 ⋅
=
20 – без проведения экспери10
10
10
3 ветвь:
3
11
1
−70 ⋅ + 50 ⋅
+ 200 ⋅
=
−30
4
60
15
с проведением эксперимента.
4 ветвь: ∅.
5 ветвь:
1
19
2
+ 50 ⋅
+ 200 ⋅ =
95
8
40
5
с проведением эксперимента.
−70 ⋅
6 ветвь: ∅.
95 единиц прибыли можно получить с вероятность 0.4, т. е. выигрыш 0.4⋅95 = 38 единиц. Следует вычесть расходы на эксперимент
10 ед. Таким образом, общая прибыль 38–10 = 29 единиц.
Деревья решений в отличие от матриц легко поддаются модификации. Их можно дополнить, развить и соответственно отсечь некоторые ветви. Таким образом, можно проследить весь путь решения
от начала до конца дерева решений.
§ 5.3. Лабораторная работа № 5.
Принятие решений в условиях риска
Выбрать лучшую из альтернатив предложенной задачи с использованием информации о вероятностях выбора. Проанализировать
127
чувствительность принятого решения. Исходные данные задачи
приведены в таблице:
Задача,
альтернативы
Вероятности
котировок рынка
Описание условий выбора
Выбор компании для покупки акций
с прибылью:
(1) – Высокая,
(2) – Низкая,
(3) – Средняя.
Котировки рынка:
z1: Возрастают
p = 0.45,
z2: Не изменяются p = 0.25,
z3: Снижаются
p = 0.3.
Сумма вложений – 3 млн. руб.
Рост котировок: (1) – прибыль
65%, (2) – прибыль 30%, (3) – прибыль 50%.
Постоянство котировок: (1) – прибыль 20%,
(2) – прибыль 20%, (3) – прибыль
20%.
Снижение котировок: (1) – потери
50%, (2) – прибыль 5%, (3) – потери 30%.
Построим «дерево решений» этой задачи в виде следующей таблице:
Альтернативы
(1) – выбор компании
с высокой прибылью
(2) – выбор компании
с низкой
прибылью
(3) – выбор компании со
средней
прибылью
Действия
Вероятрынка ности ко(коти- тировок
ровки)
Доход по рынку
(возможный)
Общий
доход по
Доход по рынку (ре- альтернаальный)
тивам при
действии
рынка
z1: 3⋅1.65 = 4.95 4.95⋅0.45 = 2.2275
z1:
возрас- p1 = 0.45 z2: 3·1.20 = 3.60
3.6⋅0.25 = 0.90
тают
z3: 3·(–0.5) = –1.5 –1.5⋅0.30 = –0.45
2.6775
z1: 3·1.30 = 3.90
z2:
не изме- p2 = 0.25 z2: 3·1.20 = 3.60
няются
z3: 3·1.05 = 3.15
3.90⋅0.45 = 1.755
3.60⋅0.25 = 0.90
3.15⋅0.30 = 0.945
3.600
z1: 3·1.50 = 4.50 4.50⋅0.45 = 2.025
z3:
снижа- p3 = 0.3 z2: 3·1.20 = 3.60
3.60⋅0.25 = 0.90
ются
z3: 3·(–0.3) = –0.90 –0.9⋅0.30 = –0.27
2.655
Вывод: наиболее перспективна альтернатива (2) – компания
с низкой доходностью.
128
129
Цены:
z1: снизятся, p1 = 0.25, z2:
повысятся, p2 = 0.3, z3: не
изменятся p3 = 0.45.
Доходность:
z1: упадёт, p1 = 0.45
z2: не изменится, p2 = 0.25
z3: вырастет, p3 = 0.3.
Спрос на книгу в ближайшие три года:
z1: 2000 экз., p1 = 0.1,
z2: 3000 экз., p2 = 0.5,
z3: 4000 экз, p3 = 0.2,
z4: 5000 экз., p4 = 0.2.
Выбор способа
вложения денег:
(1) – банковский
депозит, (2) – золото, (3) – акции.
Планирование
тиража книг на
три года вперёд:
(1) – 2000 экз.,
(2) – 3000 экз.,
(3) – 4000 экз., (4) –
5000 экз.
1
2
3
Вероятности критериев
Планирование посевной компании
(1) – пшеница, (2) –
подсолнечник, (3) –
сахарная свёкла.
Номер
Задача, альтернативы
варианта
Прибыль от продажи – 900 руб. за 1 экз.,
Убытки при не продаже – 400 руб. за 1 экз.,
Убытки от неудовлетворённого спроса – 100 руб. за 1
экз.
Если цены возрастут, урожай пшеницы даст 100 тыс.
руб. чистого дохода, подсолнечника – 200 тыс. руб.,
сахарной свёклы – 300 тыс. руб.
Если цены останутся неизменными, прибыли не будет
совсем.
Если цены понизятся, урожай пшеницы приведёт
к потерям 20 тыс. руб., подсолнечника – 35 тыс. руб.,
сахарной свёклы – 50 тыс. руб.
При снижении доходности прибыль от депозита увеличится на 5%, золото даст убыток в 10%, а акции – прибыль 2 2%.
При неизменной доходности прибыль от депозита увеличится на 7%, золота на 5%, от акций – на 7%.
При росте доходности прибыль от депозита увеличится
на 8%, от золота на 30%, от акций на 20%.
Описание условий выбора
Варианты задач принятия решений в условиях риска
(задание № 1, стр. 132, варианты взяты из работы [1])
130
6
5
4
Вероятности критериев
Выбор потребителя продукции при
дополнительном
проценте брака:
(1) – ≤0.8%,
(2) – ≤1.2%,
(3) – ≤1.4%.
Планирование
дневной закупки
выпечки:
(1) – 100 шт.,
(2) – 150 шт.,
(3) – 200 шт.,
(4) – 250 шт.,
(5) – 300 шт.
Поставщик штрафуется на 10 тыс. руб. за каждый
0.1%. если процент брака выше допустимого.
Если процент брака ниже допустимого, поставщик
получает прибыль – 5 тыс. руб. за каждый 0.1%. Продукция перед отправкой потребителям не проверяется.
Магазин покупает выпечку по 25 руб. за 1 шт., а продаёт по 55 руб. Если продукция не продана, то к концу
дня она может быть реализована по 15 руб. за 1 шт.
Штраф за неудовлетворённый спрос – 10 руб. за 1 шт.
Ежедневный спрос:
z1: 100 шт., p1 = 0.2,
z2: 150 шт., p2 = 0.25,
z3: 200 шт., p3 = 0.3,
z4: 250 шт., p4 = 0.15,
z5: 300 шт., p5 = 0.1.
Стоимость скромной рекламной компании – 200 тыс.
руб., интенсивной – 500 тыс. руб. Если рекламная
компания не проводится вовсе, ожидаемый годовой
доход – 2 млн. руб., в случае её провала – 1 млн. руб.,
в случае скромного успеха 2.5 млн. руб., большого
успеха -5 млн. руб.
Описание условий выбора
Доля брака:
z1: ≤0.8%, p1 = 0.25,
z2: ≤1.2% p2 = 0.4,
z3: ≤1.4%, p3 = 0.35.
Результаты компании:
Выбор рекламной
z1: провал, p1 = 0.3,
компании: (1) – не
проводить, (2) –
z2: скромный успех,
скромная, (3) – инp2 = 0.5,
тенсивная.
z3: большой успех, p3 = 0.2.
Номер
Задача, альтернативы
варианта
131
9
8
Выбор инвестиционного фонда:
(1) – простой,
(2) – специальный,
(3) – глобальный.
Выбор дневной производительности:
(1) – 10 тыс. шт.,
(2) – 12 тыс. шт.,
(3) – 14 тыс. шт.,
(4) – 16 тыс. шт.,
(5) – 18 тыс. шт.,
Прибыль:
рост: (1) – 8%, (2) – 30%, (3) – 20%,
неизменность: (1) – 7%, (2) – 5%, (3) – 7%,
падение: (1) – 5%, (2) – -10%, (3) – 2%.
Кондитерский цех печёт торты себестоимостью 450
руб. за 1 шт. и реализует по 600 руб. за 1 шт. Если торт
не продан, убытки составят 300 руб. за 1 шт.
Штраф за неудовлетворённый спрос – 200 руб. за 1 шт.
Ежедневный спрос:
z1: 10 тыс. шт., p1 = 0.1,
z2: 12 тыс. шт., p2 = 0.2,
z3: 14 тыс. шт., p3 = 0.3,
z4: 16 тыс. шт., p4 = 0.3,
z5: 18 тыс. шт., p5 = 0.1.
Период работы – 10 лет.
Затраты: (1) – 500 млн. руб., (2) – 100 млн. руб., (3) –
420 млн. руб.
Годовой доход:
высокий спрос: (1) – 10 млн. руб., (2) – 2.5 млн. руб.,
(3) – 9 млн. руб.
средний спрос: (1) – 6 млн. руб., (2) – 2.5 млн. руб.,
(3) – 5 млн. руб.
низкий спрос: (1) – 3 млн. руб., (2) – 2 млн. руб., (3) – 2
млн. руб.
Описание условий выбора
Цена акций:
z1: вырастет, p1 = 0.4,
z2: не изменится, p2 = 0.5,
z3: снизится, p3 = 0.1.
Спрос на продукцию:
z1: высокий, p1 = 0.5,
z2: средний, p2 = 0.2,
z3: низкий, p3 = 0.3.
Выбор мощности
производства:
(1) – большая,
(2) – малая,
(3) – увеличение от
малой до большой
через 2 года (при
высоком спросе).
7
Вероятности критериев
Номер
Задача, альтернативы
варианта
Проведём анализ чувствительности рассмотренного примера.
Здесь возможны различные варианты решения. Например, оценим
средние вероятности котировок рынка.
По первой альтернативе 4.95⋅p + 3.60⋅p–1.5⋅p = 2.6775 ⇒p = 0.380.
По второй альтернативе 3.90⋅p + 3.60⋅p + 3.15⋅p = 3.600 ⇒p = 0.338.
Наконец, по третьей альтернативе 4.50⋅p + 3.60⋅p–0.90⋅p = = 2.655 ⇒p = 0.369.
Опять же вычисленная вероятность, средняя по данной альтернативе, ближе к реальной
1 n
1 3
=
pi =
∑
∑ p1 0.333
3i 1
n i 1=
=
=
pòåîð.
для альтернативы (2) – выбор компании для покупки акций – компании с низкой доходностью.
Задание № 1. Выбрать свой вариант из следующих вариантов заданий (см. табл. стр. 129–131) и решить задачу принятия решений
в условиях риска. Номер Вашего варианта – номер Вашей фамилии
в журнале преподавателя.
§ 5.4. Принятие решений в условиях неопределённости [2, 3, 9]
В данном случае вероятности реализаций каждого из вариантов
решения проблемы полностью неизвестны. Наиболее популярный
подход к решению исходной задачи в такой ситуации предусматривает создание таблицы возможных исходов и построение гипотез
относительно вероятностей реализации вариантов решения задачи.
Общий вид такой таблицы при n решениях ai , i = 1,n и m условиях выбора sj , j = 1,m таков:
(
Условия
Решения (альтернативы)
a1
a2
…
an
(
)
)
S1
S2
…
Sm
v(a1, S1)
v(a2, S1)
…
v(an, S1)
v(a1, S2)
v(a2, S2)
…
v(an, S2)
…
…
…
v(a1, Sm)
v(a2, Sm)
…
v(an, Sm)
На практике наиболее часто применяются следующие гипотезы:
1) Все возможные условия выбора равновероятны (критерий Лапласа);
2) Выбор наилучшей альтернативы из наихудших (минимаксный критерий);
132
3) Прогнозирование вероятностей с применением «параметра оптимизма» (критерий Гурвица);
4) Замена таблицы возможных исходов таблицей потерь (критерий Сэвиджа).
а) Критерий Лапласа.
Этот критерий опирается на принцип недостаточного обоснования:
если распределение вероятностей неизвестно, то нет причин считать
их различными. Поэтому полагают, что вероятности условий выбора
1
p =
Sj
=
, j 1,m.
m
( )
Если при этом v(ai, Sj) – прибыль, то лучшим является решение
 1 n
max  ∑ v ai , Sj
i  m j =1

(

),

а если v(ai, Sj) – издержки, то, очевидно, лучшему решению соответствует
 1 n
min  ∑ v ai , Sj
i  m j =1

(

).

Пример. Необходимо выбрать вместимость строящегося стадиона. Варианты: 15, 20, 30 и 35 тыс. человек. Условия выбора – затраты на строительство. Таблица возможных издержек имеет вид (в
зависимости от уровня комфорта):
Вместимость
Издержки (млн. руб.)
15
100
120
160
185
20
120
110
145
170
30
140
145
140
175
35
170
165
150
190
Решение задачи по критерию Лапласа:
Вместимость
Ожидаемые затраты (млн. руб.)
15
(100 + 120 + 160 + 185)/4 = 141.25
20
(120 + 110 + 145 + 170)/4 = 136.25
30
(140 + 145 + 140 + 175)/4 = 150
35
(170 + 165 + 150 + 190)/4 = 168.75
133
Таким образом, по этому критерию оптимальным является стадион
с вместимостью 20 тыс. чел.
Если удаётся спрогнозировать распределение вероятностей возможных исходов, т. е. найти или оценить p Sj , j = 1,m, то лучшим
с точки зрения прибыли будет решение
( )
 n
max  ∑ p Sj ⋅ v ai , Sj
i  j =1

( ) (

),

а с точки зрения издержек решение
 n
min  ∑ p Sj ⋅ v ai , Sj
i  j =1

( ) (

).

Такой метод называется методом Байеса-Лапласа (см. § 5.1).
б) Минимаксный критерий.
Этот критерий основан на консервативном и осторожном подходе. Если таблица возможных исходов содержит данные по получаемой прибыли, то в качестве оптимального выбирается решение


max min v ai , Sj ,
i  j

(
)
а если в таблицу внесены издержки, то


min max v ai , Sj .
i  j

(
)
Рассмотрим результаты предыдущей задачи.
Вместимость
15
20
30
35
Максимальные
издержки
Издержки (млн. руб.)
100
120
140
170
120
110
145
165
160
145
140
150
185
170
175
190
185
170
175
190
Следовательно, и по этому критерию наилучшей альтернативой
является второй вариант.
в) Критерий Гурвица.
Это тот же минимаксный критерий, модифицированный применением «параметром оптимизма» 0≤α≤1. Если v(ai, Sj) доходы, то
оптимальный вариант
134


max α ⋅ max v(ai , Sj ) + (1 − α ) ⋅ min v(ai , Sj ) ,
i 
j
j

а если v(ai, Sj) – издержки, то


min α ⋅ min v(ai , Sj ) + (1 − α ) ⋅ max v(ai , Sj ) .
i 
j
j

При α = 0 критерий Гурвица становится минимаксным, а при
α = 1 – максимаксным, т. е. будет выбираться наилучшая альтернатива из наихудших. Рассмотрим предыдущую задачу. Пусть сначала α = 0.25. Тогда
Вместимость
Издержки (млн. руб.)
Значение критерия Гурвица
15
100
120
160
185
100⋅0.25 + 185⋅(1–0.25) = 163.25
20
120
110
145
170
110⋅0.25 + 170⋅(1–0.25) = 155
30
140
145
140
175
140⋅0.25 + 175⋅(1–0.25) = 166.25
35
170
165
150
190
150⋅0.25 + 190⋅(1–0.25) = 180
Оптимален опять второй вариант. Пусть теперь α = 0.7. Аналогичная таблица имеет вид
Вместимость
Издержки (млн. руб.)
15
100
120
160
185
Значение критерия Гурвица
100⋅0.7 + 185⋅(1–0.7) = 125.5
20
120
110
145
170
110⋅0.7 + 170⋅(1–0.7) = 128
30
140
145
140
175
140⋅0.7 + 175⋅(1–0.7) = 150.5
35
170
165
150
190
150⋅0.7 + 190⋅(1–0.7) = 162
Таким образом, оптимальным стал первый вариант.
г) Критерий Сэвиджа.
Этот критерий формирует таблицу потерь по следующему правилу
{(
)} (
)
 max v a , S − v a , S ,v − äîõîä,
i j
i j
 j
r a i , Sj = 
v a i , Sj − min v a i , Sj , v − ïîòåðè.
j

(
)
(
)
{(
)}
135
Здесь оптимально решение, имеющее минимум потерь. В нашем
случае таблица потерь для данной задачи такова
Вместимость
15
20
30
35
Потери
0
20
40
70
10
0
35
55
Максимальные потери
20
5
0
10
15
0
5
20
20
20
40
70
По критерию Сэвиджа уровень расходов одинаков для первого и
второго варианта стадиона.
136
СПИСОК ЛИТЕРАТУРЫ
1. Карпушкин С. В. Теория принятия проектных решений. Тамбов, 2015. 68 с.
2. Грешилов Л. А. Математические методы принятия решений.
М., Из-во МГТУ им. Баумана, 2006. 583 с.
3. Горбунов В. М. Теория принятия решений. Томск, 2010. 110 с.
4. Костевич Л.С. Математическое программирование. Минск,
Новое знание, 2003. 424 с.
5. Шапорев С. Д. Численные методы вычислительной математики. СПб., ГУАП, 2017. 273 с.
6. Хайруллин В. Р. Методические указания к лабораторно-практическим работам по методам оптимизации. Казань, 2013. 63 с.
7. Маркина М. В., Судакова А. В. практикум по решению задач
оптимизации в пакете Matlab. Нижний Новгород, 2017. 48 с.
8. Ашманов С. А., Тимохов А. В. Теория оптимизации в задачах и
упражнениях. СПб., Лань, 2017. 447 с.
9. Левковский Д. И., Макаров Р. И. Математические методы теории систем. Владимир, 2012. 66 с.
137
СОДЕРЖАНИЕ
1. ОСНОВНЫЕ ИДЕИ МАТЕМАТИЧЕСКОГО
ПРОГРАММИРОВАНИЯ................................................... 3
§ 1.1. Общие положения................................................. 3
§ 1.2. Некоторые определения математического анализа,
необходимые для дальнейших вычислений.............. 4
§ 1.3. Особенности нахождения оптимальных решений
в задачах математического программирования......... 4
§ 1.4. Необходимые и достаточные условия экстремума
в задачах математического программирования......... 7
§ 1.5. Графическое решение задач математического
программирования............................................... 9
§ 1.6. Методы безусловной оптимизации........................... 10
§ 1.7. Характеристика задач стохастического
программирования............................................... 11
§ 1.8. Некоторые математические модели задач
стохастического программирования........................ 12
II. ПРОБЛЕМА И ФОРМАЛИЗАЦИЯ ЗАДАЧИ
ПРИНЯТИЯ РЕШЕНИЙ.................................................... § 2.1. Общие положения и формализация задачи
принятия решений............................................... § 2.2. Подходы к принятию решений (принципы выбора).... § 2.3. Правила и критерии принятия решений
в условиях неопределённости................................. III. МЕТОДЫ ОПТИМИЗАЦИИ.......................................... § 3.1. Структура и постановка задачи оптимизации............ § 3.2. Одномерная и многомерная оптимизация функций
градиентными методами........................................ § 3.3. Одномерная и многомерная оптимизация функций
безградиентными методами................................... § 3.4. Методы условной оптимизации............................... § 3.5. Задачи линейного программирования...................... § 3.6. Лабораторная работа №1.
Одномерная оптимизация функций......................... § 3.7. Лабораторная работа №2.
Многомерная оптимизация функций....................... § 3.8. Лабораторная работа №3.
Задача линейного программирования...................... IV. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ................. § 4.1. Задачи многокритериального выбора....................... § 4.2. Методы определения весовых коэффициентов........... § 4.3. Методы последовательной оптимизации................... § 4.4. Оптимальность по Парето....................................... § 4.5. Способы сужения множества Парето........................ 138
14
14
15
17
20
20
22
27
31
37
42
56
68
76
76
78
80
88
92
§ 4.6. Лабораторная работа № 4.
Решение задачи многокритериального выбора.
Метод анализа иерархий........................................ 99
V. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ РИСКА
И НЕОПРЕДЕЛЁННОСТИ [3]............................................. 114
§ 5.1. Принятие решений в условиях риска....................... 114
§ 5.2. Принятие решений в условиях риска
с возможностью проведения эксперимента............... 122
§ 5.3. Лабораторная работа № 5.
Принятие решений в условиях риска...................... 127
§ 5.4. Принятие решений в условиях неопределённости...... 132
Список литературы........................................................... 137
139
Учебное издание
Шапорев Сергей Дмитриевич
ПРИНЯТИЕ РЕШЕНИЙ
В УСЛОВИЯХ РИСКА
И НЕОПРЕДЕЛЁННОСТИ
Учебное пособие
Публикуется в авторской редакции
Компьютерная верстка А. Н. Колешко
Сдано в набор 03.09.18. Подписано к печати 11.10.18. Формат 60 × 84 1/16.
Усл. печ. л. 8,1. Тираж 50 экз. Заказ № 439.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
0
Размер файла
3 321 Кб
Теги
shaporev2
1/--страниц
Пожаловаться на содержимое документа