Теория принятия решений, страница 7

(принцип уравнивания Ю.Б. Гермейера). В сделанныхпредположениях пусть x0 − оптимальное распределение ресурса в задаче(I). Тогда для x0 выполнено следующее необходимое и достаточное условие:32найдется такое целое k, 1 ≤ k ≤ n, что(fi (x0i ) = fk (x0k ) < fk+1 (0), i = 1, ..., k − 1,x0i = 0, i = k + 1, ..., n.(1)Если f1 (0) = f2 (0) = ... = fn (0), то k = n. Во всех случаях оптимальноераспределение ресурса x0 единственно.Замечание. Оптимальное распределение ресурса предполагает его выделение нескольким слабым пунктам с выравниванием эффекта по этимпунктам.Доказательство.

Необходимость. Заметим, что оптимальное распределение x0 существует, поскольку функция min fi (xi ) непрерывна на ком1≤i≤nпакте M0 . Определим число k из условияfk (0) ≤ min fi (x0i ) < fk+1 (0).1≤i≤n(2)Если k = n, то второе неравенство в (2) отсутствует. Нетрудно видеть, чтоуказанное k всегда найдется. Действительно, в силу монотонности функцийfi (t) справедливо неравенствоf1 (0) ≤ min fi (x0i ).1≤i≤nПоэтому число min fi (x0i ) принадлежит одному из полуинтервалов1≤i≤n[fi (0), fi+1 (0)), i = 1, ..., n.Здесь при fi (0) = fi+1 (0) соответствующий интервал пуст, а fn+1 (0) полагается равным ∞.Пусть k < n. Покажем, что x0i = 0, i = k + 1, ..., n. Предположим, чтопри некотором i1 ≥ k + 1 x0i1 > 0.

Определим следующий вектор z :zi =( 0xi1 − ε,x0i1i = i1 ,ε, i 6= i1 , ε > 0.+n−1При малом ε > 0 вектор z принадлежит M0 . Действительно, его компоненты при ε ∈ (0, x0i1 ) положительны, а их сумма равна A.Используя монотонность функций fi (t), получим, что при i 6= i1fi (zi ) > fi (x0i ) ≥ min fi (x0i ),1≤i≤nа при i = i1(2)fi1 (zi1 ) > fi1 (0) ≥ fk+1 (0) > min fi (x0i ).1≤i≤nОтсюда min fi (z) > min1≤i≤n1≤i≤nfi (x0i ),что противоречит оптимальности x0 .33Докажем, что fi (x0i ) = min fi (x0i ) при i = 1, ..., k. Предположим про1≤i≤nтивное. Тогда найдется такой номер i1 ≤ k, что fi1 (x0i1 ) > min fi (x0i ).

Пока1≤i≤nжем, что x0i1 > 0. Действительно, в противном случае min fi (x0i ) < fi1 (0) ≤1≤i≤nfk (0), что противоречит (2).Итак, x0i1 > 0. Возьмем определенное выше распределение z. Как и раньше, при i 6= i1 выполнено неравенство fi (zi ) > min fi (x0i ), а неравенство1≤i≤nfi1 (zi1 ) = fi1 (x0i1 − ε) > min fi (x0i ) будет выполнено при малом ε > 0,1≤i≤nпоскольку функции fi (t) непрерывны. Отсюда, как и выше, получаем противоречие.

Условие (1) доказано.Достаточность. Пусть стратегия x0 ∈ M0 удовлетворяет условию (1).Покажем, что x0 − оптимальное распределение ресурса. Возьмем произвольную стратегию x ∈ M0 , отличную от x0 . Поскольку суммы компонентэтих векторов равны A, существует такой номер j, что xj < x0j . Отсюда следует, что x0j > 0. Поэтому min fi (xi ) ≤ fj (xj ) < fj (x0j ) = min fi (x0i ), т.е.1≤i≤n1≤i≤nx0 − оптимальное распределение ресурса. Единственность оптимальногораспределения x0 следует из последнего строгого неравенства.Рассмотрим алгоритм поиска оптимального распределения ресурса. Берем последовательно k = n, n − 1, ..., 1 и решаем систему уравненийfi (x0i ) = C, i = 1, ..., k, x0i = 0, i = k + 1, ..., n,nXx0i = A(3)i=1относительно неизвестных C, x01 , ..., x0n . Если полученное решение имеет неотрицательные компоненты x0i и при k < n выполнено неравенство C <fk+1 (0), то x0 − оптимальное распределение ресурса.

В противном случаеуменьшаем значение k и вновь решаем систему.Часто встречается оптимизационная задача видаmin max fi (xi ) = max fi (x0i ).x∈M0 1≤i≤n1≤i≤nЗдесь предполагается, что каждая функция fi (t) убывает, ее значение можно интерпретировать как величину ущерба при вложении ресурса в количестве t.Пример.

Оптимизация структуры страхового портфеля. Страховая компания проводит массовое страхование по нескольким видам рисков. Пустьxi − число договоров, заключенных по i-у виду страхования, а ξij − случайная величина иска по j-у договору, j = 1, ..., xi . Будем считать, чтослучайные величины ξij независимы, каждая из них имеет математическоеожидание mi и дисперсию Vi .

Величина mi − это стоимость полиса безнадбавок за риск и текущих расходов компании. Пусть θi − относительнаярисковая надбавка, которая взимается с целью обезопасить страховую компанию от разорения. Стоимость полиса при этом возрастает до величиныxiPmi (1 + θi ). Пусть ξi =ξij − суммарный иск со стороны клиентов по i-уj=134виду страхования. Надбавка θi выбирается из условия, состоящего в том,что событие1()def ξi − xi mixi mi θi≥ √{ξi ≥ xi mi (1 + θi )} = Yi = √xi Vixi Viдолжно выполняться с малой вероятностью α. При больших xi случайнаявеличина Yi имеет стандартное нормальное распределение с нулевым математическим ожиданием и единичной дисперсией. Указанное событие выполнено с требуемой вероятностью α, если правая часть неравенства равнаквантилю yα функции распределения нормального закона1Φ(y) = √2πZye−x22dx,−∞т.е.

yα находится из уравнения 1 − Φ(yα ) = α. Отсюда получаем формулыдля относительных рисковых надбавок по каждому виду страхования√Vi yαθi (xi ) = √, i = 1, ..., n.xi miПусть A − общее число договоров. Вектор x ∈ M0 отражает структурустрахового портфеля. Здесь допускается нецелое число договоров xi . Рассмотрим задачу min max θi (xi ). Чем меньше наибольшая относительнаяx∈M0 1≤i≤nрисковая надбавка, тем более конкурентно-способна страховая компания.Перейдем теперь к задаче дискретного максимина:max min fi (xi ) = min fi (x∗i ).x∈M00 1≤i≤n1≤i≤n(I)0Здесь fi (t) − возрастающие функции целого аргумента.Положим I = {1, ..., n} и для x ∈ M00 определим множествоI(x) = Arg min fi (x).i∈IОбозначим через |I(x)| число элементов множества I(x).Теорема 3.9.

Пусть x∗ − такое оптимальное распределение ресурсовзадачи (I)0 , при котором величина |I(x∗ )| минимальна среди всех оптимальных распределений. Тогда необходимо выполнено условие:если x∗j > 0, то min fi (x∗i ) ≥ fj (x∗j − 1).1≤i≤nУсловие (3) является достаточным условием оптимальности.1 Егоназывают техническим разорением по i-у виду страхования.35(3)Замечание. Условие (3) показывает, что при положительной компонентеx∗j величина fj (x∗j ) близка к min fi (x∗i ). Это дискретный аналог принципа1≤i≤nуравнивания.Доказательство. Необходимость. Пусть x∗ − указанное в условии теоремы оптимальное распределение ресурса задачи (I)0 .

Предположим, чтоусловие (3) не выполнено. Тогда найдется такой номер j, что x∗j > 0 иfj (x∗j − 1) > min fi (x∗i ). Отсюда следует, что j ∈/ I(x∗ ). Возьмем номер1≤i≤nl ∈ I(x∗ ) и определим новое распределение z ∈ M00 :∗xj − 1, i = j,zi = x∗l + 1, i = l, ∗xi ,i 6= j, l.Тогда fl (zl ) > fl (x∗l ), fj (zj ) > min fi (x∗i ). Отсюда следует, что min fi (zi ) >1≤i≤n1≤i≤nmin fi (x∗i ) ⇒ min fi (zi ) = min fi (x∗i ), так как x∗ − оптимальное рас-1≤i≤n1≤i≤n1≤i≤nпределение ресурса. Итак, распределение z также оптимально. При этомI(z) = I(x∗ )\{l}, что противоречит определению x∗ .Достаточность.

Пусть условие (3) выполнено. Возьмем произвольное x ∈M00 , x 6= x∗ . Тогда найдется такой номер j, что x∗j > xj . Отсюда x∗j > 0 и(3)min fi (x∗i ) ≥ fj (x∗j − 1) ≥ fj (xj ) ≥ min fi (xi ).1≤i≤n1≤i≤nИтак, x∗ − оптимальное распределение ресурса.Рассмотрим алгоритм поиска оптимального распределения задачи (I)0 .Пусть x(1) − произвольное распределение ресурса. Допустим, что алгоритмпроработал до k-го шага и мы получили распределение x(k) .

Если для x(k)выполнено условие (3), то по теореме 3.9 оно и будет искомым оптимальнымраспределением. Допустим, что для x(k) условие (3) не выполнено. Тогда(k)найдется такой номер j, что xj > 0 и fj (x∗j − 1) > min fi (x∗i ). Определим1≤i≤nновое распределение x(k+1) = z, как это сделано в доказательстве теоремы3.9. При этом нужно заменить x∗ на x(k) . Могут возникнуть два случая:1) I(x(k) ) = {l}.

Тогда(k+1)min fi (xi1≤i≤n(k)) > min fi (xi ).1≤i≤n2) |I(x(k) )| > 1. Тогда(k+1)min fi (xi1≤i≤n(k)) = min fi (xi ), но |I(x(k+1) )| < |I(x(k) )|.1≤i≤nТаким образом, на каждом шаге алгоритма либо увеличивается значение функции минимума, либо сокращается множество I(x(k) ). Отсюда следует, что алгоритм закончит работу через конечное число шагов, посколькумножество M00 содержит конечное число элементов.36На практике в качестве начального берут распределение x(1) , близкое коптимальному распределению соответствующей непрерывной задачи.Пример. Рассмотрим задачу нахождения max0 min ix2i , гдеx∈M0 1≤i≤4M00 = {x ∈ E 4 |4Xxi = 10, xi ≥ 0, xi ∈ Z, i = 1, 2, 3, 4}.i=1Для решения применим указанный алгоритм.

Возьмем начальное распределение x(1) = (4, 3, 2, 1). Все вычисления сведем в таблицу22(1)(1) 2(1)(2)(2) 2(2)i xii xi − 1xii xii xi − 1i xi1416939423188318832123212341402164Здесь I(x(1) ) = {4} и условие (3) для x(1) ) не выполнено при j = 1. Далее,I(x(2) ) = {1} и условие (3) выполнено. Итак, x(2) − оптимальное распределение ресурса.Упражнение. Найдите оптимальное распределение ресурса в соответствующей непрерывной задаче.Рассмотрим еще одну непрерывную задачу:maxx∈M0nXfi (xi ) =i=1nXfi (x0i ).(II)i=1Пример интерпретации задачи. Инвестор распределяет капитал A по n проектам, где fi (t) − прибыль, получаемая от вложения капитала t в i-й проект.В отличие от задачи (I), функции fi (t) необязательно возрастающие.

Предположим, что они дифференцируемы на отрезке [0, A].Теорема 3.10.(Лемма Гиббса). Пусть x0 − оптимальное распределениересурса в задаче (II). Тогда найдется такое число λ, что выполнено следующее необходимое условие:(fi0 (x0i ) = λ, x0i > 0,(1)fi0 (x0i ) ≤ λ, x0i = 0.Если функции fi (t) вогнуты, то (1) является достаточным условиемоптимальности. Если дополнительно известно, что функции fi (t) дваждыдифференцируемы иf10 (0) ≥ f20 (0) ≥ ... ≥ fn0 (0), fi00 (0) < 0, i = 1, ..., n,то найдется такой номер l, чтоx0i > 0, i = 1, ..., l, x0i = 0, i = l + 1, ..., n.37Замечание.

Условие (1) является принципом уравнивания для производных fi0 (t). Последнее утверждение означает, что при упорядоченности производных fi0 (0) по убыванию вложение ресурса в первые пункты наиболееэффективно.Доказательство. Необходимость. Пусть x0 − оптимальное распределение ресурсов в задаче (II), а x0i > 0. Возьмем произвольный номер j 6= i иопределим функцию от εXϕ(ε) = fi (x0i − ε) + fj (x0j + ε) +fk (x0 ).k6=i,jна отрезке [0, x0i ].