Турунтаев Л.П. Теория принятия решений

111

недоминируемых альтернатив множества (X , µQ ) описывается функцией принадлежности

µQí .ä. (x) =1− SUP[µR ( y, x) −µR (x, y)] , x X .

y X

Алгоритм решения задачи состоит из следующих шагов. 1. Строим нечеткое отношение Q1 (пересечение исходных

отношений). В качестве функции принадлежности Rj по критерию j между x и y возьмем

	1, ï ðè (x, y) R		j	;
µj
	(x, y) =	(x, y) Rj .
	0, ï ðè

Тогда пересечению этих множеств соответствует функция принадлежности

µQ1 (x, y) = min{µ1(x, y), ..., µm (x, y)}.

Определяем нечеткое подмножество недоминируемых альтернатив в множестве (X ,µQ1 )

µQí .1ä. (x) =1− SUPy X µQ1 ( y, x) −µQ1 (x, y) .

2. Строим нечеткое отношение Q2 (свертка отношений)

m

µQ2 (x, y) = ∑λ j µ j (x, y)

j=1

и определяем нечеткое подмножество недоминируемых альтернатив в множестве (X ,µQ2 )

µQí .2ä. (x) =1− SUPy X µQ2 ( y, x) −µQ2 (x, y) . 3. Находим пересечение множеств µQí .1ä. и µQí .2ä.

µí .ä.(x) = min{µQí .1ä. (x), µQí .1ä. (x)} .

4. Рациональным считаем набор альтернатив из множества

X í .ä. ={x / x X , µí .ä. (x) = SUP µí .ä. (x′)}.

x′ X

112

Наиболее рациональным следует считать выбор альтерна-

тивы из множества X í .ä. , имеющий максимальную степень недоминируемости.

Последнее отношение упорядочивает альтернативы по степени недоминируемости.

Решение примера

1. Строим нечеткое отношение Q1

Q1 = R1 I R2 I R3,

µQ1 (xi , x j ) = min{µ1(xi , x j ), µ2 (xi , x j ), µ3 (xi , x j )} ,

1

1

0

µ

Q1

(x , x

j

) =

0

1 0

.

i

0

0

1

Находим подмножество недоминируемых альтернатив в

множестве (X ,µQ )

1

µQí .ä. (xi ) =1− SUP ( µQ

(x j

, xi ) −µQ

(xi , x j )) ,

i, j , i ≠ j

;

1

x j X

1

1

µí .ä. (x ) =1− SUP µ

Q1

(x , x ) −µ

Q1

(x , x ),

µ

Q1

(x , x ) −µ

Q1

(x , x )

=

Q1

1

2 1

1 2

3 1

1 3

=1− SUP[0 −1,

0 −0] =1;

µí .ä. (x ) =1− SUP µ

Q1

(x , x ) −µ

Q1

(x , x ), µ

Q1

(x , x ) −µ

Q1

(x , x )

=

Q1

2

1 2

2 1

3 2

2 3

=1− SUP[1−0,

0 −0] = 0;

µí .ä.(x ) =1− SUP µ

Q1

(x , x ) −µ

Q1

(x , x ),µ

Q1

(x , x ) −µ

Q1

(x , x )

=

Q1

3

1 3

3 1

2 3

3 2

=1− SUP[0 −0,

0 −0] =1.

Тогда µQí .ä.

(x) =

x1

x2 x3

.

1

1

0

1

2. Строим отношение Q2

113

m

1

(µ1(xi , x j ) +µ2 (xi , x j ) +µ3 (xi , x j ))

µQ2

(xi , x j ) = ∑λ j µj

(xi , x j ) =

;

3

j=1

1

1

1/ 3

µ

Q2

(x

, x

j

) =

2/ 3

1

1/ 3

.

i

1/3

1/3

1

Находим подмножество недоминируемых альтернатив в

множестве (X ,µQ

)

=1− SUP (

2

(xi , x j )) i, j ,

µQí .ä.

µQ

(x j

, xi ) −µQ

i ≠ j ;

2

2

2

µí .ä.

(x ) =1− SUP

µ

Q2

(x , x ) −µ

Q2

(x , x ), µ

Q2

(x , x ) −µ

Q2

(x , x )

=

Q2

1

2 1

1 2

3 1

1 3

=1− SUP[2 / 3 −1,

1/3 −1/ 3] =1;

µí .ä.

(x ) =1− SUP µ

Q2

(x , x ) −µ

Q2

(x , x ),µ

Q2

(x , x ) −µ

Q2

(x , x )

=

Q2

2

1 2

2 1

3 2

2 3

=1− SUP[1−2 / 3,

1/3 −1/ 3] = 2 / 3;

µí .ä.

(x ) =1− SUP

µ

Q2

(x , x ) −µ

Q2

(x , x ),µ

Q2

(x , x ) −µ

Q2

(x , x )

=

Q2

3

1 3

3 1

2 3

3 2

=1− SUP[1/3 −1/3,

1/3 −1/3] =1;

µQí .ä.

(x) =

x1 x2 x3

.

2

1 2/3

1

3. Результирующее множество недоминируемых альтерна-

тив есть пересечение множеств µQí .ä.

и µQí .ä. .

1

2

µQí .ä. (x) =

x1 x2 x3

.

2

1

0

1

Отсюда заключаем, что в данном примере рациональным следует считать выбор альтернатив x1 (обучить своего сотруд-

ника) либо x3 (заключить договор с другой организацией), имеющей максимальную степень недоминируемости.

Контрольные вопросы

1. Какие виды неопределенности встречаются в задачах принятия управленческих решений?

114

2.Укажите основные критерии выбора решений при вероятностной неопределенности состояний внешней среды.

3.В каких случаях применяется критерий минимума дисперсии оценочного функционала?

4.Каков алгоритм принятия решений при линейной упорядоченности наступления состояний внешней среды?

5.Назовите способы принятия решений при отсутствии информации о состоянии внешней среды.

6.Укажите основные критерии принятия решений в условиях противодействия внешней среды.

7.Чем отличаются критерии Гурвица, Вальда и Сэвиджа?

8.Чем отличается расплывчатая неопределенность от вероятностной?

115

6 ЭВРИСТИЧЕСКИЕ ПРОЦЕДУРЫ ЗАДАЧ ПРИНЯТИЯ РЕШЕНИЙ

6.1 Человеко-машинная процедура STEM

Одной из первых ЧМП была разработана процедура STEM [28, 35]. Она предназначена для решения многокритериальных задач линейного программирования.

Пусть X = (x1, x2 , ..., xn ) — вектор переменных задач;

n

yi(X ) = j=1 j x j , i=1, n (6.1)

—целевая функция по критерию i, определяемая на множестве переменных X и векторе C, значение которой необходимо максимизировать.

Пусть множество допустимых значений X ограничено системой Ω: ∑ c

A X = B ,	(6.2)
X ≥ 0,
где A — матрица (d ×n);
B — вектор-столбец размерностью (n ×1) .

Пусть Y0 (X ) — общая функция предпочтений (функция полезности) на множестве целевых функций yi (x) определяется в виде взвешенной суммы критериев.

m

Y0 (X ) = ∑ αi yi(X ).

i=1

Необходимо найти вектор (аргумент) X, максимизирующий совокупность целевых функций yi (X ) при наиболее предпочти-

тельном соотношении их значений в точке решения X и удовлетворяющей системе ограничений (6.2), то есть необходимо найти решение

m

X = arg max ∑ αi yi(X ) .

X Ω i=1

Решение этой задачи — вектор X следует искать во множестве Парето-эффективных решений, а требование нахождения

κ).

116

наиболее предпочтительного (неявно выраженного) соотношения между значениями критериев со стороны лица, принимающего решение, в человеко-машинных процедурах выражается, как правило, в большинстве своем в поиске весовых коэффициентов αi целевых функций.

Поскольку назначение весовых коэффициентов является для ЛПР сложной операцией, то в человеко-машинной процедуре STEM определение αi поручается ЭВМ.

Задача многокритериальной оптимизации представляется как задача поиска удовлетворительного (компромиссного) ре-

шения, формализуемого в виде условий
yi(x) ≥ µi, i=1, 2,…, m,	(6.3)

где µi — пороговые значения критериев, выделяющие множество удовлетворенных решений и назначаемые ЛПР.

Так как удовлетворительное значение порога µi в общем случае зависит от значений других критериев yk(x),i ≠ k, то ус-

ловия (6.3) корректируются в ходе человеко-машинной процедуры по мере анализа новых альтернатив и изменения предпочтений ЛПР о множестве допустимых решений.

Человеко-машинная процедура STEM состоит из следующих фаз: оптимизации — Aτ −Cτ (выполняются на ЭВМ) и ана-

лиза — Dτ − Eτ (выполняются ЛПР, τ — номер итерации):

Шаг Aτ .

1. Вычисляется матрица Y τ = yνκ ,

где yνκ — значение целевой функции по критерию ν , найден-

ное на решении X κ , то есть yνκ = yν(X

Решение X κ определяется в результате решения локальной задачи оптимизации целевой функции по k-му критерию yκ(X ) в текущей области допустимых решений Ω, то есть

X κ = arg max y	κ	(X )
X Ω

Ω на первой итерации определяется системой уравнений (4.2). На последующих итерациях к ней будет добавляться по одному

117

ограничению вида (6.3), накладываемого на наиболее не удовлетворяющий критерий.

2. Нормируется матрица Y ′τ = y′νκ

y′νκ = ( yνκ − mν) /( yκκ − mν),

где mν = min yνκ ; 0 ≤ y′νκ ≤1.

Очевидно, что для диагональных элементов y′νκ =1.

3. Рассчитывается система весовых коэффициентов αi критериев i:

(1−η1) /(1−ηi) = α1/ αi ; i = 2, …, N; ∑αi =1 ;

i

где ηi = min y′iκ или, ηi = y′i ,

где y′i — среднее значение элементов i-ой строки (исключая

максимальный).

Шаг Bτ .

1. Определяется вектор компромиссного решения X τ на итерации τ , максимизирующий функцию полезности

m

Y 0(X τ) = ∑αi yi (X τ) .

i=1

2. Вычисляется вектор критериальных оценок Pτ = ( y1(X τ), y2(X τ),..., ym(X τ)) , соответствующий компромисс-

ному решению X τ .

Шаг C τ .

Формируется сообщение ЭВМ на итерации τ

ωτ ={Pτ, yτ},

где yτ = ( y11, y22,..., ymm) — вектор критериальных оценок, соответствующий идеальным решениям y1(x1), y2(x2),..., ym(xm).

Шаг Dτ .

Оценивается предлагаемое решение на основании сопоставления векторов Pτ и yτ.

118

Если ЛПР считает это решение удовлетворительным, завершается процедура, иначе переход к шагу Eτ .

Шаг E τ .

ЛПР указывает, какой из критериев в векторе Pτ имеет наименее удовлетворительное значение, и устанавливает желаемую величину порога удовлетворенности µi (i — номер не-

удовлетворяющего критерия). Таким образом, информация ЛПР имеет вид:

ωτ ={i,µi}.

Перейти к шагу Aτ+1 (размерность матрицы Y τ+1 умень-

шится на единицу, так как критерий i «уйдет» в область ограничений).

Пример

Обратимся к задаче определения плана выпуска продукции, рассмотренной в разделе 4.1. Добавим еще один критерий определения плана: минимизация суммарного времени простоя оборудования (максимизация загрузки оборудования). В целом, необходимо определить план производства столов и шкафов с учетом трех критериев:

1) максимизация дохода от реализации продукции (в руб-

лях)

y1 = c1 x1ï + c2 x2 ,

где x1ï — план выпуска столов, предназначенных для продажи,

x2 — план выпуска шкафов, предназначенных только для

продажи; 2) максимизация выпуска столов для нужд всего предпри-

ятия (в штуках)

y2 = x1Ñ ,

где x1Ñ — план выпуска столов, предназначенных для собствен-

ных нужд предприятия; 3) максимизация загрузки оборудования (в часах)

		119
		2
		y3 = ∑t j x j ,
		j=1
где x1	= xÏ	+ xÑ;
	1	1
t j	— время изготовления одного продукта j-ого вида (час).

Пусть время изготовления одного стола t1 = 30 минут, время изготовления одного шкафа t2 =80 минут.

Решением задачи определения плана выпуска продукции с учетом только первого критерия является вектор

X 1 = (xÏ	, xÑ, x2) = (517; 0; 156), то есть столов на продажу сле-
1	1
дует производить в количестве xï		= 517 штук, столов для соб-
	1
ственных нужд — не производить		xÑ =0, шкафов — произво-
		1

дить в количестве x2 =156 штук. Значение первого критерия

y1(X 1) =375500 рублей.

Решением задачи с учетом только второго критерия является вектор X 2 =(0;700;0), то есть столов (для собственных нужд

предприятия) следует производить в количестве x1Ñ =700 штук. Значение второго критерия y2(X 2) =700 штук.

Решением задачи с учетом только третьего критерия является множество решений X 3 = (λ 279;(1−λ) 279;268) , то есть

столов в общей сумме следует производить xÏ					+ xÑ =279 штук
(0 ≤ λ ≤1 ), а шкафов — в количестве			1		1
	x2 =268 штук. Значением
третьего критерия является величина	y (	) =		1	279 +	4	268 =
	3	X 3	2		3

=497 часов.

Процедура STEM включает следующие шаги.

Шаг A1 .

1. Рассчитывается матрица Y1 (табл. 6.1)

y11 = y1(X 1) = ∑c j x j = c1 x1Ï + c2 x2 =

j

= 500 517 + 750 156 = 375500 рублей;

120

y12 = y1(X 2) = 500 0 + 750 0 =0 рублей;

y13 = y1(X 3) = (500 279 λ + 750 268) рублей.

При λ =1, то есть если все столы пустить на продажу, y13 =

= 340500 рублей. При λ =0, то есть если все столы оставить для нужд предприятия, y13 =201000 рублей. Таким образом,

340500 ≤ y13 ≤ 201000 .

y21 = y2(X 1) = x1Ñ = 0 штук,

y22 = y2(X 2) = 700 штук,

y23 = y2(X 3) = (1−λ) 279 штук.

То есть y23 изменяется от 0 до 279 штук 0 ≤ y23 ≤ 279 .

	y31	= y3(X 1) = ∑t j x j =					1		517 +	1	0 +	4	156 = 466.5 час.
						2				2		3
				j
	y32	= y3(X 2) =		1	700 +	4			0 = 350		час.
				2		3
	y (		) =497час.
	33		X 3

Таблица 6.1 — Значение критериев при различных оптимальных решениях

		Решения X = (x1П; x1С; x2)
	Критерии
		X1 = (517;	X 2 = (0;	X 3 = ( λ 279;
		0;156)	700;0)	(1– λ )279; 268)
y1 (тыс.руб.)		375.5	0	201 ÷ 340.5
y2	(шт.)	0	700	0 ÷ 279
y3	(час)	466.5	350	497

2. Нормируем матрицу Y1 по каждому из критериев, приняв y13 =(201+340.5)/2=270.75 рублей и y23 =[2792]=139 штук.