d9e5a92d

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

N^ = {ю|ш;да0^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?0, г' = Т^; = w{wr l = T~L}. (1.32)
i = i
В частном случае, когда частные критерии оптимальности располагаются (ранжируются) в порядке убывания важности (?і ^ ?2 ^ - ' область Dw принимает следующий вид:
N
= {w | ш. ш0 0, i = T7W; ?а/. = /?;
=1
w.wl+l, 1 = 0^1}. (1.33)
Если область Dw непуста, то информация (1.24) непротиворечива. В этом случае весовые коэффициенты w е Dw будем называть согласованными с качественной информацией [33].
Качественная информация может быть представлена в виде ориентированного графа G (/, ?2), где I множество вершин, соответствующих частным критериям, ?2 множество ребер, соединяющих (-ю вершины с /-й тогда и только тогда, когда выполняется соотношение Q. }¦ Qf. В дальнейшем будем считать, что информационные сообщения (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. и wjt связанных
бинарным отношением Q. ^ Q/t с помощью параметра 1: о)/
w. \twr (1.34)
CD ? ? (D
S=1
а) отсутствие информации (1.30)
О ----- ’
ф
CD2
0-------51
sU
CD s
б) линейное упорядочение критериев по важности
В этом случае приходим к области допустимых значений весовых коэффициентов вида
= {w I и0 ? 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 вычислены.
В следующей главе рассмотрим вопросы назначения весовых коэффициентов важности для допустимых областей их изменения
Dlw (1.30), D*m (1.32), Dbw (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 Dw weDWi=l
где
Dw= {w I Wj Z w0 Z 0, / = T7N;
N (0/
Y wi = #; w. - %i ¦ wr * 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 *
где
qk = qk(.R,w0,N) =
х[?(дс)(4гл-+ V , i6/* ,Г#'
о)]
+ X ?(*)
tel\Ik
¦it
(2.11)
Wn
Доказательство
Доказательство проведем по индукции по слоям.
1. Пусть в графе предпочтений имеется всего один первый слой (S = 1). В этом случае справедливость теоремы очевидна. Поскольку бинарные отношения предпочтения на множестве частных критериев отсутствуют, то соотношения (2.8)(2.11) сводятся к выражению
qr = max { X * Q, (*)} = we Ц /e/ ' '
= max {[/? - (IV- 1) а0] - Qf (х) + w0 ¦ ??*(*)}. (2.12)
/€/ *€/\/
Из (2.12) видно, что для S 1, так как I. = / и = 1 для всех / = 1,..., IV, сформулированная теорема справедлива:
wr= R - (N - 1)100. Wj wQ, /= 1, IV, j* г. (2.13)
2. Пусть теорема справедлива для k слоев, т. е. для любой вершины 1 из слоев 1,..., k получим
qt (R, wQ, Nk) qr(R,w0,Nk) для всех ie Jk, (2.14)
где Jk множество вершин на первых к слоях, Nk = | Jk |, до(. вычисляются по формулам (2.8)(2.11).
Докажем справедливость теоремы для (к + 1)-го слоя. Рассмотрим произвольную вершину / из (k + 1)-го слоя. Эта вершина соединена в общем случае дугами с несколькими вершинами из первых к слоев графа предпочтений {t,,.... іт } так, что
І} = It u /, и ... и І( u j = /у и /, (2.15)
I S iKy
соединяющие дуги имеют номера кр t - 1,.... m;.; /у множество вершин, из которых есть путь в вершину /, включая ее саму. Оценим значение обобщенного критерия Fz (w, Q (х)):
Fz (w, Q (x)) = Yjwk'Qk + wj' (¦*-
(2.16)
*e
Для первого слагаемого можно применить сформулированную теорему, положив
R- Шу, ш,, W = (2.17)
Тогда для выражения (2.15) можно записать
Fz(w,Q(x))Z qr (R, до, N) + w,Q/(x) = f(wj), (2.І8)
где
{R- w. wj ¦ Yj'ii) ¦
f (wj) = X {Qt (*) ¦ [
IK
IS /
tel
(2.19;
‘',4
(2.20)
/ / доп до, ? max { до, -l. }. 0 1 V
Функция (2.19) является линейной относительно параметра до(.,
поэтому она достигает своего максимального значения в одной из граничных точек: либо в точке Wj = ш0, либо в точке
ад. = max {ад, - ?*}= ад. (2.21)
Непосредственной подстановкой граничных точек ад0 и ад в (2.19) получим
/(ад0)= qr(R,Nk+ 1 ,ад0);/(ад)= qj(.R,Nk + 1 ,wj. (2.22) Следовательно,
Fz (ад, Q (ж)) = max {qf (R, Nk + 1 ,wa); qj(R, Nk+ 1, ад„) . (2.23)
Если qr qp то условие (2.10) выполняется в первых k слоях и выражения (2.8)(2.11) справедливы и для (k + 1)-го слоя. Если qr qf, то в качестве индекса г принимаем индекс /-й вершины. В этом случае выражение (2.8) также имеет место, так как для всех he І}
а величины R, определяются через выражения (2.9) и (2.7) соответственно, что и требовалось доказать.®
В частном случае линейной упорядоченности по важности частных критериев оптимальности область допустимых значений весовых коэффициентов имеет следующий вид:
N
Dw= {ад | аду ад0 0, / = T77J; ? w. = R-,
i= i
(2.27)
В этом случае решением задачи (2.1) является вектор ?о* с компонентами, определяемыми следующими выражениями:
(2.28)
(2.29)
(2.30)
(2.31)
(Л'-^)/Х?*+ і= Ь2.....г,
, к = 1
Кі -W0, і = r+ 1 N-,
где
R'= R- ovX^ 0,
=i
а индекс г определяется из соотношения
q. = max qk, r 1kN k
k 1 t * N f f
Qk = X [?, (*) - (-5L + C- - М + X 0* (*) - w0 - К
,=i x^; ,=t+i
/=i
Выражения (2.28)(2.31) аналогичны результату, полученному в работе [2].
При отсутствии дополнительной уточняющей информации, т. е. при?{ = l,t= Т7Т, получим область допустимых значений коэффициентов важности вида
(Of
Dw = {w\ w.w00,i = ТТЛ; X w.^ w., I = TTT}. (2.32)
/=i
. і е I;,
е /\/Л;
В этом случае решением задачи (2.1) является вектор w* с компо-R - (N - nr)- wQ
(2.33) где индекс г определяется из соотношения
(2.34)
qr = max q., r 1 k?N к
R- (N- nt)wn
??,(*)
? Qt (x).
(2.35)
+ wn
e/U
ie /.
Выражения (2.33)-(2.35) нетрудно получить из выражений
(2.8)-(2.11), учитывая, что все величины определенные выражением (2.6), равны единице. Выражения (2.33)-(2.35) аналогичны результату, полученному в [5]. Там же показано, что для случая линейной упорядоченности частных критериев оптимальности при отсутствии уточняющей информации ?, т. е. области допустимых значений весовых коэффициентов важности Dw вида
D3W = {ш | wQ 0, і = 1, N;
N _
Xwi= Л; w. wl+ j, i= 1 ,N- 1}, (2.36)
i = i
оптимальным решением экстремальной задачи (2.1) является вектор w* с компонентами
R- (N- г) -w0 . т_
a/f‘ = г ’ _ (2.37)
te;0, i= r+ 1 ,N,
где индекс г определяется из соотношения
а= шах о., (2.38)
r ]k?N к
qk = R~ {N~k k)W IQ, (*) + w0-^Qt (x). (2.39)
i=i =*+i
Выражения (2.37)-(2.39) нетрудно получить из выражений
(2.28)(2.31), подставив значения = 1, i, k е /.
При отсутствии дополнительной качественной информации (2.3) и области допустимых значений коэффициентов важности вида [5]
N
Dlw= {w|w(2: w0 0, i = T7N\ Yjwt = Я) (2.40)
i=i
оптимальным решением экстремальной задачи (2.1) является вектор tv с компонентами
(2.41)
(2.42)
. _ f/? - (N - 1) - cv0, i = r,
W‘ ~ [tv0, i = TTN, i * r,
где индекс г определяется из соотношения
ч'=іШк(х)-

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


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



(2.47)
где
_ п СО/ _
Dw = {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/Qj (x)}.
5. Проводим корректировку значений w'j для вершин более высоких слоев:
w'j = max {w'j, maxwk}, kel j
где I'j множество вершин, в которые есть путь из вершины /.
6. Полагаем s = s 1. Если s = 0 (т. е. рассмотрены все слои), то переходим к п. 7, в противном случае повторяем вычисления с п. 4.
7. Вычисляем итоговые значения весовых коэффициентов по формуле
w* = R- w'j/ (X w\).
Для доказательства корректности данного алгоритма докажем следующую лемму.
Лемма 2.1. Вектор весовых коэффициентов w, построенный с помощью алгоритма 1, обладает следующим свойством: для любой вершины / е Is, принадлежащей s-му слою (s 1) и такой, что
всегда найдется вершина k е І? принадлежащая нижнему по отношению к s-му слою (t s), такая, что
wkxk = F и wk = wp т. е. для которой xk Xj.
Доказательство
Пусть вектор w построен по алгоритму 1. Тогда для всех вершин самого нижнего (5-го) слоя, согласно пунктам 4 и 7, получим
до( х{ = F для всех I е Is.
Рассмотрим произвольную вершину / е Is (S 1) такую, что Wj Xj F. Построим путь из вершины / е Ig в вершину I е fs следующим образом (построение такого пути всегда возможно в силу определения слоя). Среди всех вершин множества найдем
такую вершину jv что
w, = max до..
7 kelj *
Если і\ не принадлежит то выбираем следующую вершину j2 такую, что до, = max до.
и так до тех пор, пока не найдем вершину I, принадлежащую нижнему (s-му) слою:
W{ Wj ... Wj Wj Wj,
где / e Is,l e Is, wt xt = F, Wj Xj F. Согласно построению весового коэффициента до, по алгоритму 1 возможно два случая.
Случай 1. Для всех k = /,, /2,..., jm имеем wk xk F. Тогда из построения алгоритма 1 следует, что
до. = до. = ... = до. = до. = до.,
'т ' Л '
т. е. требуемая по лемме k-я вершина нижнего слоя определена ею является вершина I е Is.
Случай 2. Найдется такая вершина /0 6 {..., jm}, что
Wj Xj = F и wk xk 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п и да, xt F для / е / \ Ітіп. Предположим от противного, что имеется вектор да' е Dw, который является оптимальным решением задачи (2.47)-(2.48):
min (да', х.) = F F. (2.49)
1 /А7 11
Так как F' F, то
w'j да4 для всех k е /т1п. (2.50)
Покажем, что в этом случае будет иметь место и система неравенств да'7? Wj для всех /е /\/ш1п.
Действительно, предположим, что найдутся такие / е / \ /т1п, что да'7 да^. Так как / е Is, s 1, то согласно лемме 1 найдется вершина / е Ір t s, такая, что
да,х,= F я w,= wjt I в /ш1п.
Таким образом, получаем, что да', да'7 wf= да,, т. е. да', да, для всех I € /т|п, что противоречит условию (2.50). Следовательно,
да'7 да7 для всех /е І\ітіп. (2.51)
Просуммировав по / от 1 до N значения w'j и or и учитывая неравенства (2.50) и (2.51), получим, что
X w'k + X "'/ X wk + X ®/ - (2.62)
*в/Ы. *6/mta /еЛ/ші„
Так как вектора ю' и w принадлежат области dw, то их сумма
равняется величине R. Тогда из неравенства (2.52) следует, что R R. Полученное противоречие говорит о том, что сделанное предположение неверно и, следовательно, вектор w, построенный с помощью алгоритма 1, является оптимальным решением экстремальной задачи (2.47)-(2.48). Что и требовалось доказать.*
Рассмотрим обобщение задачи (2.47)(2.48) на случай w{ w0 0, і = 1, N, где w0 R/N:
w* (.x) = arg { max\F , (w, Q (x))} = toe Dw
= arg {max min (w,Q(x))}, (2.53)
weDw 1 iN
где
Dw= {да|ш(. w0 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 w0, то полагаем w*j = w'j, j е Г и задача решена; в противном случае переходим к п. 4.
4. Для каждой вершины т е Г, для которой выполняется условие w'm ш0, осуществляем следующие действия:
а) полагаем w'm = wQ, R' = R' - ш0;
б) исключаем вершину т из рассмотрения, для этого полагаем Г = І\т и из множества ?2' исключаем дуги, инцидентные вершине т (если они есть).
После выполнения указанных действий для всех вершин, в которых выполнилось условие w'm wQ, повторяем вычисления с п. 2.
Для доказательства корректности алгоритма 2 докажем следующую лемму.
Лемма 2.2. Операция исключения вершины т из графа G (/, ?2) на 4-м шаге алгоритма 2 не изменяет частичное попарное отношение предпочтения на множестве /'.
Доказательство
Дуга (і, /) в графе G (/', ?2') качественно соответствует соотношению wi Wp i, j e /'. Возможны два случая.
Случай 1. Если подлежит исключению вершина /, то в этом случае согласно шагу 4 алгоритма 2 Wj= wQ и из построения области
Dw следует соотношение Wp
Случай 2. Если подлежит исключению вершина і, то в этом случае выполняется соотношение ад0 w. Wp и вершина / также будет исключена на этом же шаге алгоритма и будет выполнено wo ~ wi ~ wp что является частным случаем w. Wp Из этого следует, что исключение вершины m на 4-м шаге алгоритма 2 не изменяет попарное частичное отношение предпочтения на множестве /'.¦
Теорема 2.3. Вектор весовых коэффициентов хи*, построенный с помощью алгоритма 2, является оптимальным решением задачи
w* (х) = arg { шах Fmln {w, Q (ж))} =
WE Dw
= arg { max min (w, Q (x))}, (2.55)
гveDw ]tN
где
N
Dw = {тг/|ю. w0 0, i= T7W; Y,wi=
= i Wf Wp l= ITT}.
(2.56)
Доказательство
Обозначим через / множество вершин, исключенных из рассмотрения в шаге 4 алгоритма 2.
1. Покажем, что ?о* допустимый вектор,
а) Очевидно, что для всех / е Г выполняется условие w]= до0,
а для всех / е Д/ в силу шага 3 алгоритма 2 выполняется условие w* до0.
Следовательно,
W* Ш0, / G /.
б) Обозначим через г мощность множества Тогда
N
= z + х wr
1=1 /е 1 }е І\І
В силу построения алгоритма
X а) = ш0 - (ЛГ - г); /6 г
Y,wj= Я'= Я - (N- г) ¦ до0.
/ € / \ /
Следовательно,
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: до! до0 и до^ = до0.
Ситуация 3. Если і е Г и / е /, то до* = до* = до0, следователь-нJ, условие (2.58) также выполняется.
Таким образом, доказано, что до* допустимый вектор задачи v2.55H2.56).
2. Покажем, что до* оптимальный вектор.
Допустим (от противного), что существует вектор до (до * до*) такой, что
mm {до - Q. (х)} min {до* - Qt (де)}. i?iN ‘ ‘ 1iN
Тогда для і е / из шага 4 алгоритма 2 следует, что
- Q, (*) * Щ - Qf (х), і е



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