НАЗНАЧЕНИЕ ВЕСОВЫХ КОЭФФИЦИЕНТОВ ВАЖНОСТИ

N^ = {ю|ш_;да₀^0. = T7W; ?/, = #}- (1.30)
i= 1
1.3. Анализ и использование качественной информация об относительной важности частных критериев
Будем считать, что от ЛПР получена дополнительная качественная информация, устанавливающая для некоторых L пар частных
критериев (необязательно для всех допустимых пар) предпочтение
і-го критерия над /-м на всем множестве D допустимых решений:
со, = {?,- }¦ Q,}. / = Т7Х N (N - 1)/2. (1.31)
Информация (1.31) является качественной, так как из нее следует, что і-й критерий важнее /-го критерия, но нельзя сказать, во сколько раз. Тогда качественная информация (1.31) в соответствии с соотношением (1.24) позволяет определить область допустимых значений весовых коэффициентов w следующим образом:
, . _ со/ _
Ег_и = {т8|а,.?да₀?0, г' = Т^; = w_{w_r l = T~L}. (1.32)
i = i
В частном случае, когда частные критерии оптимальности располагаются (ранжируются) в порядке убывания важности (?і ^ ?₂ ^ - ' область D_w принимает следующий вид:
N
= {w | ш. ш₀ 0, i = T7W; ?а/. = /?;
=1
w.w_l+l, 1 = 0^1}. (1.33)
Если область D_w непуста, то информация (1.24) непротиворечива. В этом случае весовые коэффициенты w е D_w будем называть согласованными с качественной информацией [33].
Качественная информация может быть представлена в виде ориентированного графа G (/, ?2), где I множество вершин, соответствующих частным критериям, ?2 множество ребер, соединяющих (-ю вершины с /-й тогда и только тогда, когда выполняется соотношение Q. }¦ Q_f. В дальнейшем будем считать, что информационные сообщения (1.31) удовлетворяют условию транзитивности, то есть в графе G (/, ?2) отсутствуют замкнутые циклы.
Разобьем все вершины I графа G (/, ?2) на слои следующим образом: к первому слою (s = 1) отнесем те вершины, в которые не входит ни одна дуга; ко второму слою (з = 2) те и только те вершины, в которые входят дуги из вершин первого слоя; к третьему слою (з = 3) те и только те вершины, в которые входят дуги из вершин первого и второго слоев, и т. д. При этом у вершин последнего слоя (s = SN) не будет ни одной выходной дуги.
В частном случае отсутствия качественной информации (1.31) граф G (/, ?2) не будет иметь ни одной дуги и будет представлять собой совокупность из N точек (рис. 2, а).
В частном случае линейной упорядоченности по важности частных критериев оптимальности (рис. 2, б) граф G (/, ?2) будет иметь число слоев, равное числу вершин (S = N).
Для набора парных сравнений частных критериев по важности:
®1 = (*?2 ^ Ю2 = ? ^ @5 Ь М3 = { @3 ^ ^6
= {@4 ^ Qj}; ®5= {@5 ^ Qg}; ®g= {Qg ^ Qg};
граф G (/, ?2) приведен на рис. 2, в.
Для каждой вершины і е { 1,..., N}, соответствующей частному критерию Q., введем следующие параметры: /. множество вершин
графа G (/, ?2), из которых имеется путь в вершину і, включая ее саму; п. мощность множества І_г Тогда в частном случае отсутствия
качественной информации (1.31) получим І.= {і}, п. = 1, і = 1, N\ а в частном случае линейной упорядоченности по важности частных критериев получим I. = { 1,.... і}; п₍ = і, і= 1, N.
В некоторых случаях ЛПР имеет возможность уточнить информацию о взаимосвязях весовых коэффициентов w. и w_jt связанных
бинарным отношением Q. ^ Q_/t с помощью параметра 1: о)/
w. \_tw_r (1.34)
CD ? ? (D
S=1
а) отсутствие информации (1.30)
О ----- ’
ф
CD2
0-------51
sU
CD s
б) линейное упорядочение критериев по важности
В этом случае приходим к области допустимых значений весовых коэффициентов вида
= {w I и₀ ? 0, i = T7W;
N (О/
Y,wi= R’ Щ* ^Iwp i = T7X. 1 }- (1.35)
=1
Введем следующие обозначения.
Пусть р произвольный путь в графе G (/, ?2) [32]: р = {/_р /_п(р)}, где I. дуга, входящая в путь р;п(р) число дуг в пути р. Обозначим через Р* множество всех путей из вершины і в вершину k. Тогда введем величины 'к
и ^ следующим образом:
Іі =
(1.36)
(1.37)
max* П ?- если * 0;
Up
1, если Р? = 0, для всех i, k е /; І = ™axif-
А € У ЯФІ
Нетрудно видеть, что является обобщенной оценкой относительной важности частного критерия і в условиях качественной информации (1.31).
'к
Приведем пример вычисления величин и ?_f.
Для всех дуг графа, изображенного на рис.2, в введем уточняющие
'у
коэффициенты / = 176. Вычисление величин ^ и \_х приведено на рис. 3.
'к
Нетрудно видеть, что величины и %. можно легко вычислить с помощью следующего алгоритма.
1. Полагаем s = S; = 0, k, i е {1.....N}.
2. Для всех вершин k, принадлежащих слою s, полагаем 1.
3. Полагаем s s 1. Если s = 0 (т. е. все слои пройдены), то переходим к п. 5. В противном случае переходим к п. 4.

Номер дуги /	Уточняющий коэффициент
1	1.2
2	2
3	1
4	1.3
5	1.3
6	2

<

p>

Вершины 7	Величины при pf Ф 0	Величины
1	-	1
2	?5 = 1.2-1.3 = 1.56;^ = 1.2	1.56
3	?*3 = 2; = 1; ?® = тах{2 - 1.3; 1 - 2} = 2.6	2.6
4	?1 = 1-5	1-5
5	?*5 = 1.3	1.3
6	?*6=2	2
7	-	1
8	-	1

Рис. 3. Пример уточнения качественной информации о предпочтениях
4. Для каждой вершины k, принадлежащей слою s, выполняем
следующие действия. Пусть У* множество вершин слоя (s + 1), в которых есть дуга из вершины k. Тогда для каждой вершины
/ € У* полагаем
'і
5* = где I - номер дуги (k, /);
І‘к = }-
/ € J
и повторяем все вычисления с п. 3.
*к
5. Для всех для которых выполняется условие 0, к,
'k *k **
і 6 {1,,N}, полагаем %_t 1. Все величины и %_t вычислены.
В следующей главе рассмотрим вопросы назначения весовых коэффициентов важности для допустимых областей их изменения
Dl_w (1.30), D*_m (1.32), Db_w (1.33) и Z)* (1.35) при различных типах
обобщенных критериев F (tv, Q (х)) с помощью решения экстремальной задачи (1.28).

Глава 2 НАЗНАЧЕНИЕ ВЕСОВЫХ КОЭФФИЦИЕНТОВ ВАЖНОСТИ ПРИ РАЗЛИЧНЫХ ТИПАХ ОБОБЩЕННЫХ КРИТЕРИЕВ

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

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

Вычисление весовых коэффициентов важности при использовании аддитивного обобщенного критерия оптимальности

Рассмотрим решение задачи определения весовых коэффициентов важности w, принадлежащих области допустимых решений ?* (1.35), при использовании аддитивного критерия оптимальности (1.16)
N
w (ж) = arg { max Fj. (w, Q (ж))} = arg { max Y wt ?,(*)}- (2.1) we D_w weD_Wi=l
где
D_w= {w I Wj Z w₀ Z 0, / = T7N;
N (0/
Y wi = #; w. - %i ¦ w_r * 1. L = T7X}. (2.2)
f=i
При фиксированных значениях варьируемых параметров ж е D значения векторного критерия Q (ж) определены.
х 6 D значения векторного критерия Q (х) определены.
Будем считать, что качественная информация о предпочтениях на множестве критериев
(*, = {?, ?,}. l = Tj:N(N- 1)/2, (2.3)
может быть представлена в виде ориентированного графа G (/, Q), где I множество вершин, соответствующих частным критериям; Q множество ребер, соединяющих і-ю вершину с /-й тогда и только тогда, когда выполняется соотношение Q. }- Qj.
Для каждой вершины і е {1,.... N}, соответствующей частному критерию Q_{, введены следующие параметры: I. множество вершин
графа G (/, ?2), из которых имеется путь в вершину і, включая ее саму; л, мощность множества /_;. Тогда в частном случае отсутствия качественной информации о важности частных критериев получим
= {*'}. л,= 1, і = 1, N, (2.4)
а для линейной упорядоченности по важности частных критериев /, = {1.....і}, л,= 1, і 1, N. (2.5)
Пусть р произвольный путь в графе G (/, Q): р = {І_? .... /_п(р)), где 1₍ дуга, входящая в путь р, п (р) число дуг в пути р. Обозначим
через множество всех путей из вершины і в вершину к. Тогда *k
величины ^ и определяются следующим образом: (2.7)
тах* П */ если ф
Р^Рі _Ыр
1, если Pj = 0, для всех і, к е /;
рх/5-'
k* і
Для экстремальной задачи (2.1)(2.2) может быть сформулирована следующая теорема.
Теорема 2.1. Оптимальным решением задачи (2.1)(2.2) является вектор хи* с компонентами
Af
/ //
^'o iG/r5
*е/
Г
О- іе/\/_г;
(2.8)
w_{ = *
где
(2.9)
*=і
при этом величины ^ вычисляются с помощью выражений (2.6)-(2.7) соответственно, а индекс г определяется из соотношения
q = max а., (2.10)
r )kzN *
где
q_k = q_k(.R,w₀,N) =
х[?(дс)(4гл-+ V , i6/* ,Г#'
о)]
+ X ?(*)
tel\I_k
¦it
(2.11)
W_n
Доказательство
Доказательство проведем по индукции по слоям.
1. Пусть в графе предпочтений имеется всего один первый слой (S = 1). В этом случае справедливость теоремы очевидна. Поскольку бинарные отношения предпочтения на множестве частных критериев отсутствуют, то соотношения (2.8)(2.11) сводятся к выражению
q_r = max { X * Q, (*)} = we Ц _/e/ ' '
= max {[/? - (IV- 1) а₀] - Q_f (х) + w₀ ¦ ??*(*)}. (2.12)
/€/ *€/\/
Из (2.12) видно, что для S 1, так как I. = / и = 1 для всех / = 1,..., IV, сформулированная теорема справедлива:
w_r= R - (N - 1)100. Wj w_Q, /= 1, IV, j* г. (2.13)
2. Пусть теорема справедлива для k слоев, т. е. для любой вершины 1 из слоев 1,..., k получим
q_t (R, w_Q, N_k) q_r(R,w₀,N_k) для всех ie J_k, (2.14)
где J_k множество вершин на первых к слоях, N_k = | J_k |, до₍. вычисляются по формулам (2.8)(2.11).
Докажем справедливость теоремы для (к + 1)-го слоя. Рассмотрим произвольную вершину / из (k + 1)-го слоя. Эта вершина соединена в общем случае дугами с несколькими вершинами из первых к слоев графа предпочтений {t,,.... і_т } так, что
І_} = I_t u /, и ... и І₍ u j = /у и /, (2.15)
I S iKy
соединяющие дуги имеют номера к_р t - 1,.... m_;.; /у множество вершин, из которых есть путь в вершину /, включая ее саму. Оценим значение обобщенного критерия F_z (w, Q (х)):
F_z (w, Q (x)) = Yjwk'Qk + wj' (¦*-
(2.16)
*e
Для первого слагаемого можно применить сформулированную теорему, положив
R- Шу, ш,, W = (2.17)
Тогда для выражения (2.15) можно записать
F_z(w,Q(x))Z q_r (R, до, N) + w,Q_/(x) = f(wj), (2.І8)
где
{R- w. w_j ¦ Yj'ii) ¦
f (wj) = X {Q_t (*) ¦ [
IK
IS /
tel
(2.19;
‘',4
(2.20)
/ / до_п до, ? max { до, -l. }. 0 1 V
Функция (2.19) является линейной относительно параметра до₍.,
поэтому она достигает своего максимального значения в одной из граничных точек: либо в точке Wj = ш₀, либо в точке
ад. = max {ад, - ?*}= ад. (2.21)
Непосредственной подстановкой граничных точек ад₀ и ад в (2.19) получим
/(ад₀)= q_r(R,N_k+ 1 ,ад₀);/(ад)= q_j(.R,N_k + 1 ,wj. (2.22) Следовательно,
F_z (ад, Q (ж)) = max {q_f (R, N_k + 1 ,w_a); qj(R, N_k+ 1, ад„) . (2.23)
Если q_r qp то условие (2.10) выполняется в первых k слоях и выражения (2.8)(2.11) справедливы и для (k + 1)-го слоя. Если q_r q_f, то в качестве индекса г принимаем индекс /-й вершины. В этом случае выражение (2.8) также имеет место, так как для всех he І_}
а величины R, определяются через выражения (2.9) и (2.7) соответственно, что и требовалось доказать.®
В частном случае линейной упорядоченности по важности частных критериев оптимальности область допустимых значений весовых коэффициентов имеет следующий вид:
N
D_w= {ад | ад_у ад₀ 0, / = T77J; ? w. = R-,
i= i
(2.27)
В этом случае решением задачи (2.1) является вектор ?о* с компонентами, определяемыми следующими выражениями:
(2.28)
(2.29)
(2.30)
(2.31)
(Л'-^)/Х?*+ і= Ь2.....г,
, к = 1
Кі -W₀, і = r+ 1 N-,
где
R'= R- ovX^ 0,
=i
а индекс г определяется из соотношения
q. = max q_k, r 1kN k
k ₁ t * N _{f f}
Q_k = X [?, (*) - (-5L + C- - М + X 0* (*) - w₀ - К
,=i x^; ,=t+i
/=i
Выражения (2.28)(2.31) аналогичны результату, полученному в работе [2].
При отсутствии дополнительной уточняющей информации, т. е. при?_{ = l,t= Т7Т, получим область допустимых значений коэффициентов важности вида
(Of
D_w = {w\ w.w₀0,i = ТТЛ; X w.^ w., I = TTT}. (2.32)
/=i
. і е I;,
е /\/_Л;
В этом случае решением задачи (2.1) является вектор w* с компо-R - (N - n_r)- w_Q
(2.33) где индекс г определяется из соотношения
(2.34)
q_r = max q., r 1 k?N к
R- (N- n_t)w_n
??,(*)
? Q_t (x).
(2.35)
+ w_n
e/U
ie /.
Выражения (2.33)-(2.35) нетрудно получить из выражений
(2.8)-(2.11), учитывая, что все величины определенные выражением (2.6), равны единице. Выражения (2.33)-(2.35) аналогичны результату, полученному в [5]. Там же показано, что для случая линейной упорядоченности частных критериев оптимальности при отсутствии уточняющей информации ?, т. е. области допустимых значений весовых коэффициентов важности D_w вида
D3_W = {ш | w_Q 0, і = 1, N;
N _
Xwi= Л; w. w_l+ j, i= 1 ,N- 1}, (2.36)
i = i
оптимальным решением экстремальной задачи (2.1) является вектор w* с компонентами
R- (N- г) -w₀ . _т_
a/_f‘ = г ’ _ (2.37)
te;₀, i= r+ 1 ,N,
где индекс г определяется из соотношения
а= шах о., (2.38)
r ]k?N к
q_k = R~ {N~_k k)W IQ, (*) + w₀-^Q_t (x). (2.39)
i=i =*+i
Выражения (2.37)-(2.39) нетрудно получить из выражений
(2.28)(2.31), подставив значения = 1, i, k е /.
При отсутствии дополнительной качественной информации (2.3) и области допустимых значений коэффициентов важности вида [5]
N
Dl_w= {w|w₍2: w₀ 0, i = T7N\ Yjwt = Я) (2.40)
i=i
оптимальным решением экстремальной задачи (2.1) является вектор tv с компонентами
(2.41)
(2.42)
. _ f/? - (N - 1) - cv₀, i = r,
W‘ ~ [tv₀, i = TTN, i * r,
где индекс г определяется из соотношения
ч'=іШк(х)-

Вычисление весовых коэффициентов важности при использовании обобщенного логического свертывания частных критериев оптимальности

Рассмотрим решение задачи
w (ж) = arg { max F (tv, Q (ж))}, (2.43)
we D_w
где
N
D_w = {tvlo^S w₀ 0, / = 1, N\ ?iv,= R\
i= 1
w_t?1 w_p l= T7X}, (2.44)
при использовании обобщенных логических критериев оптимальности двух типов:
обобщенного критерия максимальной осторожности
Fmin (w. Q (*)) =, min {w. Q. (ж)}; (2.45)
1 tN
обобщенного критерия максимального риска
Fmax Q (* = ,га.ах {, Q_t (*) }- (2-46)
1 iN
Для нахождения весовых коэффициентов w₍ (ж), і = 1, N, при использовании обобщенного критерия вида (2.45) и в случае условия неотрицательности весовых коэффициентов важности Wj 0, т. е. решения задачи
w* (ж) = arg { max F_mln (tv, Q (ж))} = tve D_w
= arg { max min (w, Q (*))}, we

(2.47)
где
_ п СО/ _
D_w = {u I w_{ ? 0, i = 1, N; Y,wi= R’ wi - wj, I = TT}, (2.48)
может^быть применен следующий алгоритм.
Алгоритм 1
1. Граф отношений предпочтения G (/, Q) разбиваем на слои s = 1,5.
2. Каждой вершине / графа G (I, Q) приписываем начальное значение w'j =0, / = 1, N.
3. В качестве первого слоя рассматриваем самый нижний слой, т. е. полагаем s =* S.
4. Для каждой вершины s-ro слоя полагаем
w'. = max {w'., R/Q_j (x)}.
5. Проводим корректировку значений w'j для вершин более высоких слоев:
w'j = max {w'j, maxw_k}, kel j
где I'j множество вершин, в которые есть путь из вершины /.
6. Полагаем s = s 1. Если s = 0 (т. е. рассмотрены все слои), то переходим к п. 7, в противном случае повторяем вычисления с п. 4.
7. Вычисляем итоговые значения весовых коэффициентов по формуле
w* = R- w'j/ (X w\).
Для доказательства корректности данного алгоритма докажем следующую лемму.
Лемма 2.1. Вектор весовых коэффициентов w, построенный с помощью алгоритма 1, обладает следующим свойством: для любой вершины / е I_s, принадлежащей s-му слою (s 1) и такой, что
всегда найдется вершина k е І_? принадлежащая нижнему по отношению к s-му слою (t s), такая, что
w_kx_k = F и w_k = w_p т. е. для которой x_k Xj.
Доказательство
Пусть вектор w построен по алгоритму 1. Тогда для всех вершин самого нижнего (5-го) слоя, согласно пунктам 4 и 7, получим
до₍ х_{ = F для всех I е I_s.
Рассмотрим произвольную вершину / е I_s (S 1) такую, что Wj Xj F. Построим путь из вершины / е I_g в вершину I е f_s следующим образом (построение такого пути всегда возможно в силу определения слоя). Среди всех вершин множества найдем
такую вершину j_v что
w, = max до..
7 kelj *
Если і\ не принадлежит то выбираем следующую вершину j₂ такую, что до, = max до.
и так до тех пор, пока не найдем вершину I, принадлежащую нижнему (s-му) слою:
W_{ Wj ... Wj Wj Wj,
где / e I_s,l e I_s, w_t x_t = F, Wj Xj F. Согласно построению весового коэффициента до, по алгоритму 1 возможно два случая.
Случай 1. Для всех k = /,, /₂,..., j_m имеем w_k x_k F. Тогда из построения алгоритма 1 следует, что
до. = до. = ... = до. = до. = до.,
'т ' Л '
т. е. требуемая по лемме k-я вершина нижнего слоя определена ею является вершина I е I_s.
Случай 2. Найдется такая вершина /₀ 6 {..., j_m}, что
Wj Xj = F и w_k x_k F для всех k e {/„ - 1,j\ }. Тогда из алгоритма 1 следует, что
W! = ?і= - - - = ¦/. wr
т. е. искомой (А-й вершиной нижнего слоя) будет вершина /. Что и требовалось доказать.®
Лемма 1 позволяет доказать следующую теорему.
Теорема 2.2. Вектор весовых коэффициентов да, построенный с помощью алгоритма /, является оптимальным решением экстремальной задачи (2.47)(2.48).
Доказательство
Пусть вектор да построен с помощью алгоритма 1. Тогда
min (да, х.) = F.
11N 1 1
Причем Wj Xj = F для / е /_ш1п и да, x_t F для / е / \ І_тіп. Предположим от противного, что имеется вектор да' е D_w, который является оптимальным решением задачи (2.47)-(2.48):
min (да', х.) = F F. (2.49)
1 /А7 11
Так как F' F, то
w'j да₄ для всех k е /_т1п. (2.50)
Покажем, что в этом случае будет иметь место и система неравенств да'₇? Wj для всех /е /\/_ш1п.
Действительно, предположим, что найдутся такие / е / \ /_т1п, что да'₇ да^. Так как / е I_s, s 1, то согласно лемме 1 найдется вершина / е І_р t s, такая, что
да,х,= F я w,= w_jt I в /_ш1п.
Таким образом, получаем, что да', да'₇ w_f= да,, т. е. да', да, для всех I € /_т|п, что противоречит условию (2.50). Следовательно,
да'₇ да₇ для всех /е І\і_тіп. (2.51)
Просуммировав по / от 1 до N значения w'j и or и учитывая неравенства (2.50) и (2.51), получим, что
X w'k + X "'/ X wk + X ®/ - (2.62)
*в/Ы. *6/_mta /еЛ/ші„
Так как вектора ю' и w принадлежат области d_w, то их сумма
равняется величине R. Тогда из неравенства (2.52) следует, что R R. Полученное противоречие говорит о том, что сделанное предположение неверно и, следовательно, вектор w, построенный с помощью алгоритма 1, является оптимальным решением экстремальной задачи (2.47)-(2.48). Что и требовалось доказать.*
Рассмотрим обобщение задачи (2.47)(2.48) на случай w_{ w₀ 0, і = 1, N, где w₀ R/N:
w* (.x) = arg { max\F , (w, Q (x))} = toe D_w
= arg {max min (w,Q(x))}, (2.53)
weD_w 1 iN
где
D_w= {да|ш₍. w₀ 0, i= T7N; ^wi=
=i
w. Wj, 1= 1, L}. (2.54)
Для решения этой задачи может быть построен следующий алгоритм.
Алгоритм 2
1. Полагаем Г = / = {1.....N}\ R’ = R; fl' = ?2.
2. Для графа предпочтений G (Г, Q') с помощью алгоритма 1 с параметром R’ = R находим значение w'., j е Г.
3. Если для всех j е Г выполняется условие w'j w₀, то полагаем w*j = w'j, j е Г и задача решена; в противном случае переходим к п. 4.
4. Для каждой вершины т е Г, для которой выполняется условие w'_m ш₀, осуществляем следующие действия:
а) полагаем w'_m = w_Q, R' = R' - ш₀;
б) исключаем вершину т из рассмотрения, для этого полагаем Г = І\т и из множества ?2' исключаем дуги, инцидентные вершине т (если они есть).
После выполнения указанных действий для всех вершин, в которых выполнилось условие w'_m w_Q, повторяем вычисления с п. 2.
Для доказательства корректности алгоритма 2 докажем следующую лемму.
Лемма 2.2. Операция исключения вершины т из графа G (/, ?2) на 4-м шаге алгоритма 2 не изменяет частичное попарное отношение предпочтения на множестве /'.
Доказательство
Дуга (і, /) в графе G (/', ?2') качественно соответствует соотношению w_i Wp i, j e /'. Возможны два случая.
Случай 1. Если подлежит исключению вершина /, то в этом случае согласно шагу 4 алгоритма 2 Wj= w_Q и из построения области
D_w следует соотношение Wp
Случай 2. Если подлежит исключению вершина і, то в этом случае выполняется соотношение ад₀ w. Wp и вершина / также будет исключена на этом же шаге алгоритма и будет выполнено wo ~ wi ~ wp что является частным случаем w. Wp Из этого следует, что исключение вершины m на 4-м шаге алгоритма 2 не изменяет попарное частичное отношение предпочтения на множестве /'.¦
Теорема 2.3. Вектор весовых коэффициентов хи*, построенный с помощью алгоритма 2, является оптимальным решением задачи
w* (х) = arg { шах F_mln {w, Q (ж))} =
WE D_w
= arg { max min (w, Q (x))}, (2.55)
гveD_w ]tN
где
N
D_w = {тг/|ю. w₀ 0, i= T7W; Y,wi=
= i Wf Wp l= ITT}.
(2.56)
Доказательство
Обозначим через / множество вершин, исключенных из рассмотрения в шаге 4 алгоритма 2.
1. Покажем, что ?о* допустимый вектор,
а) Очевидно, что для всех / е Г выполняется условие w]= до₀,
а для всех / е Д/ в силу шага 3 алгоритма 2 выполняется условие w* до₀.
Следовательно,
W* Ш₀, / G /.
б) Обозначим через г мощность множества Тогда
N
= z + х wr
1=1 /е 1 }е І\І
В силу построения алгоритма
X а) = ш₀ - (ЛГ - г); /6 г
Y,wj= Я'= Я - (N- г) ¦ до₀.
/ € / \ /
Следовательно,
N
(2.57)
Yjw)= R- (N - r)- w0+ (N~ r) - wo ~ Я. /=1
в) Для каждого соотношения
(О/ __
ш. Wp 1= 1, L, (2.53)
может иметь место одна из трех возможных ситуаций.
Ситуация 1. Если і е / \ Г и / е I \ /, то условие (2.58) выполняется в силу шага 3 алгоритма 2.
Ситуация 2. Если і е /V и / е /, то условие (2.58) выполни ется в силу шага 4 алгоритма 2: до! до₀ и до^ = до₀.
Ситуация 3. Если і е Г и / е /, то до* = до* = до₀, следователь-нJ, условие (2.58) также выполняется.
Таким образом, доказано, что до* допустимый вектор задачи v2.55H2.56).
2. Покажем, что до* оптимальный вектор.
Допустим (от противного), что существует вектор до (до * до*) такой, что
mm {до - Q. (х)} min {до* - Q_t (де)}. i?iN ‘ ‘ 1iN
Тогда для і е / из шага 4 алгоритма 2 следует, что
- Q, (*) * Щ - Qf (х), і е

Содержание раздела

---