ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13043
Скачиваний: 110
221
4. Если
2
1
m
υ
υ
<
+ +
…
, то сравнить
1
O
с
2
1
m
O
O
−
+ +
…
. Если условие
2
1
1
m
υ
υ
−
<
+ +
…
все еще выполняется, то сравнить
1
O
с
2
2
m
O
O
−
+ +
…
и т. д., до тех
пор, пока
1
O
не станет предпочтительнее остальных или пока не завершится срав-
нение
1
O
с
2
3
O
O
+
, тогда следует возвратиться к этапу 3.
5. После того как величины
i
υ
найдены, нормализовать их, разделив на
1
m
i
i
υ
=
∑
.
Предположения, лежащие в основе этой процедуры, следующие:
С каждым исходом мы сопоставляем действительную неотрицательную величину.
Если
i
O
предпочтительнее
j
O
, то
i
j
υ υ
>
.
Если
i
O
и
j
O
равнозначны, то
i
j
υ υ
=
.
Если исходам
i
O
и
j
O
соответствуют значения
i
υ
и
j
υ
, то исходу
i
j
O O
+
соот-
ветствует значение
i
j
υ υ
+
. Это предположение несправедливо, если
i
O
и
j
O
взаим-
но исключающие друг друга исходы.
Когда имеется большое число исходов, эта процедура очень трудоемка. К тому
же она не формирует единственную шкалу и с ее помощью нельзя справиться с за-
дачами иерархического типа. В [82] использован метод непосредственного сравне-
ния
n
объектов. Во-первых, объекты располагаются в ряд по порядку от наиболее
предпочтительного к наименее предпочтительному. Сравниваются наиболее пред-
почтительный объект со вторым по предпочтительности, второй с третьим и т. д.,
при этом каждый раз этому отношению приписываются численные значения. По за-
вершении процесса число 1 приписывается наименее предпочтительному из
n
объ-
ектов и для получения веса
(
)
1
n
−
-го объекта 1 умножается на отношение, полу-
ченное в результате сравнения
(
)
1
n
−
-го с
n
-м объектом, и т. д., продвигаясь в об-
ратном направлении и получая относительную шкалу оценок для
n
объектов. В этом
методе отсутствует способ оценки согласованности.
Сопоставление исходов с функциями целей. В [40, 43] предлагается под-
ход, основанный на использовании теории аддитивной полезности, что означает
выполнение условия: полезность целого равна сумме полезностей, приписываемых
его частям. Если все цели
j
O
соответствующим образом определены и для каждого
плана измерен его вклад в реализацию каждой цели, то результаты могут быть за-
писаны в следующем матричном виде:
Цели
План
1
O
2
O
…
j
O
…
n
O
1
u
11
x
12
x
…
1 j
x
…
1n
x
2
u
21
x
22
x
…
2 j
x
…
2n
x
…
…
i
u
1
i
x
2
i
x
…
ij
x
…
in
x
…
…
m
u
1
m
x
2
m
x
…
mj
x
…
mn
x
222
Каждому плану
i
u
приписывается вектор целей
(
)
1
2
,
,
,
i
i
in
x x
x
…
. Нужно взвесить
планы для определения того, который следует использовать. Согласно теории по-
лезности общая мера вклада
i
u
(которую обозначим
( )
i
V u
) получается как функ-
ция
n
-мерного вектора
(
)
1
2
,
,
,
i
i
in
x x
x
…
, т. е.
( )
(
)
1
2
,
,
,
i
i
i
in
V u
V x x
x
=
…
. Используя ус-
ловие аддитивности
( )
1
2
i
i
i
ij
in
V u
υ
υ
υ
υ
=
+
+ +
+ +
…
…
,
можно получить, что значение цели для каждого плана определяется как произве-
дение относительной важности цели
( )
j
O
υ
на полезность численной меры
ij
x
, обо-
значенной через
( )
ij
x
υ
. В наших обозначениях
( ) ( )
ij
j
ij
O
x
υ
υ
υ
=
.
Оценка
( )
ij
X
υ
. Первой попыткой оценки
( )
ij
x
υ
можно считать использование
линейных функций полезности, которые нормализованы так, что получают значение
от 0 до 1. Для целей, меры которых прямо пропорциональны уровням полезности
(например, вклад в национальный доход), можно считать
( )
1
m
ij
ij
ij
j
x
x
x
υ
=
=
∑
,
а для тех целей, которые обратно пропорциональны уровням полезности (например,
вклад в загрязнение окружающей среды)
( )
(
)
(
)
1
1
1
1
1
m
ij
ij
m
i
ij
i
x
x
n
x
υ
=
=
−
=
−
∑
∑
.
Оценка
( )
j
O
υ
. 1. Методы ранжирования.
( )
j
O
υ
ранжируются, от наименьшего к
наибольшему так, что
( ) ( )
( )
1
2
,
,
,
n
O
O
O
υ
υ
υ
…
, где номера целей соответствуют ран-
гам. Иногда эксперта просят перенумеровать цели в порядке убывания предпочти-
тельности. Существуют и другие методы упорядочивания – разновидности этого ме-
тода.
2. Метод непосредственного оценивания. Целям могут быть приписано бесконеч-
ное или конечное число дискретных значений, например числа от 0 до 10. Для каж-
дого
( )
j
O
υ
эксперта просят оценить важность данной цели. Эксперту может быть
дозволено выбирать точки с учетом десятых долей, например 2,7, и он может при-
писать одно и то же значение из шкалы более чем одной цели.
3. Метод сопоставления исходов с целями (описан выше).
4. Полусуммы. Допустим, что
( )
( )
1
n
O
O
O
υ
υ
<
<
<
…
. Основная идея подхода за-
ключается в образовании цепочки половинных значений следующим образом. Нач-
нем с
k
, близкого к
n
, и оценим такое
j
, что
( ) ( )
( )
2
j
j
k
O
O
O
υ
υ
υ
+
+
=
и положим
( )
( ) ( )
1
1/ 2
j
k
O
O
υ
υ
+
=
. Повторим процесс, заменив
( )
k
O
υ
на
( )
1
j
O
υ
+
, и продолжим
формирование цепочки половинных значений до тех пор, пока это будет возможно.
Сглаженная кривая, проходящая по цепочке половинных значений, может быть ис-
пользована в качестве оценки искомой функции полезности. Например, допустим,
что тридцать целей были ранжированы следующим образом:
223
( )
( )
( )
1
2
30
0
O
O
O
υ
υ
υ
<
<
<
<
…
.
Допустим
( ) ( )
( )
22
24
30
O
O
O
υ
υ
υ
+
=
,
( ) ( )
( )
17
19
23
O
O
O
υ
υ
υ
+
=
,
( ) ( )
( )
9
11
18
O
O
O
υ
υ
υ
+
=
,
( ) ( )
( )
2
4
10
O
O
O
υ
υ
υ
+
=
.
Используя цепь половинных значений
( ) ( ) ( ) ( ) ( )
30
23
18
10
3
,
,
,
,
O
O
O
O
O
υ
υ
υ
υ
υ
и
полагая
( )
3
1
O
υ
=
, можно получить графическую оценку функции полезности.
5. Методы упорядоченной метрики. Допустим,
( )
( )
( )
1
2
0
n
O
O
O
υ
υ
υ
<
<
<
<
…
, то-
гда ранжирование по упорядоченной метрике в бинарном случае будет ранжирова-
нием смежных разностей
( )
1
0
O
υ
−
,
( ) ( )
2
1
O
O
υ
υ
−
,
( ) ( )
3
2
O
O
υ
υ
−
, …,
( ) (
)
1
n
n
O
O
υ
υ
−
−
.
В одном случае о разностях
( )
i
O
υ
можно судить непосредственно; в другом, на-
пример, можно сравнить
( ) ( )
2
1
O
O
υ
υ
−
и
( ) ( )
4
3
O
O
υ
υ
−
, сравнивая
( ) ( )
1
4
O
O
υ
υ
+
с
( ) ( )
3
2
O
O
υ
υ
+
. Сравнение производится непосредственно, когда одно и то же
( )
i
O
υ
присутствует в обеих разностях, например при сравнении
( ) ( )
3
2
O
O
υ
υ
−
с
( ) ( )
2
1
O
O
υ
υ
−
.
6. Метод кривых безразличия. Во многих задачах желательно определить функ-
цию полезности или ценности распределения ресурсов на различные виды деятель-
ности и максимизировать ее при ограничивающих условиях, которые могут быть на-
ложены на имеющиеся величины в связи с их ценой и денежными фондами. Однако
обычно такую функцию построить трудно и вместо нее определяют кривые безраз-
личия для пар видов деятельности в обход численного подхода. Чтобы построить
такую кривую, экспертам задают вопросы для определения компромиссов между
двумя сравниваемыми показателями. На кривой безразличия значения обоих пока-
зателей имеют одинаковую ценность. Здесь получаются двумерные кривые, с помо-
щью которых должна быть получена некоторая многомерная поверхность и на ней
найден максимум. Недостатком метода является потеря количественной информа-
ции.
Методы последовательного исключения
Лексикографический порядок. Термин «лексикографический» отражает ана-
логию между этим методом и методом упорядочивания слов в словаре. При лексико-
графическом подходе требуется ранжирование показателей по важности, а значе-
ния показателей располагаются на шкале порядка. После того как важнейший пока-
затель выбран, может быть определена альтернатива, имеющая наивысшее значе-
ние по этому показателю. Если такая альтернатива одна, то ее выбирают и процеду-
ра заканчивается. Если по определенному показателю имеется несколько альтерна-
тив с одним и тем же наивысшим значением, то они сравниваются по второму по
важности показателю. Процесс продолжается таким образом до тех пор, пока не бу-
дет выявлена единственная альтернатива, или пока не будут проверены все показа-
тели.
Недостатком лексикографического порядка является то, что бесконечно малое
приращение одной из компонент не перевешивает больших приращений других. Бо-
лее слабым критерием является принцип оптимальности по Парето. Одна альтерна-
тива превосходит вторую, если она превосходит ее, по крайней мере, по одной ком-
поненте и не хуже второй по любой другой компоненте. Если альтернатива удовле-
224
творяет этому свойству относительно всех других альтернатив, то ее называют па-
рето-оптимальной.
Методы математического программирования
Глобальная функция цели. Здесь главная задача – свести вместе многие цели
для оптимизации результата при ограничениях
в рамках линейного программирования. Идея заключается в том, чтобы исполь-
зовать выпуклую комбинацию этих функций цели при различных параметрах и ре-
шить в итоге задачу параметрического программирования. Мы получаем конечное
семейство решений, соответствующих мозаике из ячеек пространства параметров.
Для выбора решения, которое представляется наиболее приемлемым, используют
суждения.
Цели в ограничениях; целевое программирование. Все глобальные опти-
мумы являются в более широком контексте локальными оптимумами. Мы знаем, что
решения оптимальны только в ограниченном контексте. Оптимальное решение – это
не та стратегия, которой нужно следовать, это дополнительная информация, кото-
рую следует учесть в контексте большой системы, для которой данная задача явля-
ется компонентой. В большинстве случаев наша цель – максимизация прибыли всего
производства. Это создает впечатление, что у нас только одна цель – прибыль. Но
предположим, что принята более широкая точка зрения, включающая несколько от-
дельных целей, которые нельзя легко объединить в одну оптимизируемую функцию.
Например, можно рассмотреть уровни производства для двух разных изделий, для
которых получены наибольшие чистая и общая прибыль, а также состояние денеж-
ных средств при некоторых ограничениях на ресурсы.
Безусловно, вряд ли решение, которое максимизирует чистую прибыль, будет
таким же, что максимизирует и две другие цели. Чтобы разрешить неопределен-
ность большей цели, следует заново определить, является ли вообще максимизация
нашей целью.
В действительности мы добиваемся не максимизации или минимизации при при-
нятии решений по линии поведения, а скорее «удовлетворения». Последнее означа-
ет определение целей и поиск такого распределения, которое предлагает наилуч-
шую перспективу достижения этих целей. Это выражает смысл целевого программи-
рования.
Рассмотрим следующий пример:
цель 1:
1
2
60
50
1500
x
x
+
=
(цель – чистая прибыль);
цель 2:
1
2
2
4
80
x
x
+
≤
;
цель 3:
1
2
3
2
60
x
x
+
≤
,
1
2
,
0
x x
≥
;
1
x
и
2
x
– количество единиц изделий 1 и 2 соответственно; 80 и 60 – соответст-
венно время работы машин
A
и
B
, которое не может быть превышено. Эти три це-
ли несовместимы. Для решения проблемы несовместимости принимаем высший при-
оритет цели 1, следующий по величине приоритет будет у цели 2, а затем у цели 3.
Припишем следующие точные значения приоритетам:
цель 1 следует удовлетворить как можно лучше, каковы бы ни были результаты
приближения к целям 2 и 3;
как только цель 1 достигнута, следует удовлетворить цель 2 как можно лучше
при условии, что это не поставит под угрозу реализацию цели 1;
как только цель 2 достигнута, следует удовлетворить цель 3 как можно лучше
при условии, что это не поставит под угрозу реализацию цели 2.
Итак, задача ставится следующим образом:
минимизировать
225
(
)
1
1
1
2 2
3 3
P d
d
P d
P d
−
+
+
+
+
+
+
,
при условиях
1
2
1
1
60
50
1500
x
x
d
d
−
+
+
+
−
=
,
1
2
2
2
2
4
80
x
x
d
d
−
+
+
+
−
=
,
1
2
3
3
3
2
60
x
x
d
d
−
+
+
+
−
=
,
и неотрицательности всех переменных. Здесь
i
d
−
и
i
d
+
– переменные нехватки и из-
лишка соответственно.
Если
1
P
,
2
P
и
3
P
рассматриваются как коэффициенты переменных, то мы будем
иметь дело с несоизмеримыми вещами, так как
1
d
−
и
2
d
+
измеряются в деньгах, а ос-
тальные переменные – в часах. Чтобы устранить эту трудность, будем считать, что
1
P
,
2
P
и
3
P
– ярлыки, определяющие порядок приоритета соответствующих целей, а
не коэффициенты. Итак, вычислить
(
)
1
1
1
P d
d
−
+
+
означает: во-первых, сделать
1
1
d
d
−
+
+
возможно малым при единственном условии – неотрицательности всех пе-
ременных. Вычислить
2 2
P d
+
означает: сделать
2
d
+
возможно малым, не угрожая реа-
лизации первой цели, и так далее для
3 3
P d
+
. Считается, что соотношения приорите-
тов
1
P
,
2
P
и
3
P
таково, что
1
P
намного больше
2
P
, которое, в свою очередь, намного
больше
3
P
.
Связь между целевым программированием и иерархиями проходит через концеп-
цию согласованных сценариев в планировании. В сложной ситуации планирования
применение иерархического подхода позволяет получить обобщенный сценарий, ко-
торый устраивает всех лиц, принимающих решение. Однако этот сценарий должен
быть реалистическим и совместимым со всеми размерностями задачи. Например,
реалистический означает, что мы не можем использовать ресурсов больше, чем
имеем. Совместимый означает, что цели не должны быть конфликтующими. Если
определить сценарий посредством вектора состояния переменных –
X
, а множество
переменных решения обозначить через
Y
, то сценарий
(
)
,
X Y
является согласо-
ванным, если
( )
X
g Y
=
, где
g
– модель процесса формирования системы, т. е. фи-
зических потоков в системе. Метод собственного значения и принцип иерархической
композиции могут быть использованы для построения обобщенного сценария, пере-
менные состояния которого принимают значение
R
. Если
R
не может быть получе-
но в виде функции от переменных решения, т. е. в форме
( )
*
g Y
, где
*
Y
– конкрет-
ное подмножество решений задачи, то
R
не согласованно, и тогда используется це-
левое программирование для пересмотра целей планирования, представляемых
R
.
В частности, предположим, что
A
– матрица прямых затрат заданной экономиче-
ской системы. Пусть
X
– валовая продукция, а
Y
– конечный спрос. Известно, что
(
)
1
X
I A
Y
−
=
−
. Предположим, что значение переменной состояния
*
X
обеспечива-
ет некоторый уровень потребления определенного ресурса, стоимость, зависящую
от технологии, а также эмиссию полютантов при этой технологии. Общие коэффици-
енты воздействия и модель «вход–выход»
D
воспроизводят процесс функциониро-
вания системы. Имеем
*
X
DX
=
при
(
)
1
X
I A
Y
−
=
−
. Чтобы величины
R
обобщен-
ного сценария были согласованны, должно соблюдаться следующее условие: