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

Поскольку x0 − оптимальное распределение ресурса, ϕ(ε)достигает на отрезке [0, x0i ] наибольшего значения в точке ε = 0. Поэтомуϕ0 (0) ≤ 0 илиfj0 (x0j ) ≤ fi0 (x0i ).(2)Если x0j > 0, то, меняя местами i и j, получим неравенствоfj0 (x0j ) ≥ fi0 (x0i ).(3)Из (2) и (3) следует, что fj0 (x0j ) = fi0 (x0i ) = λ, т.е. при положительных вложениях ресурса в пункты i и j значения соответствующих производныхсовпадают. Из (2) следует, что fj0 (x0j ) ≤ λ при всех j. Условие (1) доказано.Достаточность.

Пусть функции fi (t) вогнуты и распределение ресурса x0удовлетворяет условию (1). Возьмем произвольное распределение x ∈ M0 .Из вогнутости функций fi (t) имеем неравенство:nX(fi (xi ) − fi (x0i )) ≤i=1nXfi0 (x0i )(xi − x0i ).i=1x0iЕсли> 0, то подставим в последнее выражение fi (x0i ) = λ, а если x0i = 0,то xi − x0i = xi ≥ 0 и производную fi (x0i ) оцениваем сверху величиной λ. ВрезультатеnXfi0 (x0i )(xi − x0i ) ≤nXi=1Итак,nPi=10fi (xi ) ≤λ(xi − x0i ) = λ(A − A) = 0.i=1nPi=1fi (x0i )) при любом x ∈ M0 , что и доказывает оптималь-ность x .Предположим, чтоf10 (0) ≥ f20 (0) ≥ ... ≥ fn0 (0), fi00 (0) < 0, i = 1, ..., n.Предположим, что найдется такой номер i, что x0i = 0, x0i+1 > 0.

Тогда(1)00fi0 (x0i ) = fi0 (0) ≤ λ = fi+1(x0i+1 ) < fi+1(0).3800Последнее неравенство следует из условия fi+1(0) < 0. Поэтому fi0 (0) <0fi+1 (0) (противоречие).Пример. Задача поиска объекта.Объект прячется в n возможных областях с номерами i = 1, ..., n. Если он находится в i-ой области и поиск в ней ведется в течение времениt, то условная вероятность его обнаружения равна 1 − e−µi t , где µi > 0.Обозначим через pi известную априорную вероятность нахождения объекта в i-й области.

Пусть A − общее время поиска объекта. Стратегия поискаx = (x1 , ..., xn ) ∈ M0 означает, что объект в области i ищется в течение вреnPмени xi . Тогдаpi (1−e−µi xi ) − полная вероятность обнаружения объекта,i=1которую необходимо минимизировать.Определим функции fi (t) = pi (1 − e−µi t ) и решим задачу (II)0 . Заметим,что fi00 (t) = −pi µ2i (1 − e−µi t ) < 0. Следовательно, функции fi (t) являютсявогнутыми. Упорядочим значения производных в нуле fi0 (0) = pi µi :p1 µ1 ≥ p2 µ2 ≥ ... ≥ pn µn .В соответствии с леммой Гиббса найдется такой номер l, чтоx0i > 0, i = 1, ..., l, x0i = 0, i = l + 1, ..., n.Запишем условие (1)(fi (x0i ) = λ, i = 1, ..., l,fi (x0i ) ≤ λ, i = l + 1, ..., n.(1)Получаем систему уравнений Отсюда находимx0i =1ln(pi µi )−ln λ, i = 1, ..., l.µiµi(2)Складывая эти равенства, получимA=lXln(pk µk )k=1µk− ln λlX1.µkk=1Отсюда найдем ln λ и после подстановки в (2) находим!!−1llXln(pi µi )1 X ln(pk µk )10xi =−−A, i = 1, ..., l.µiµiµkµkk=1k=1Поскольку произведения pi µi упорядочены, для того чтобы компонентыx0i , i = 1, ..., l, были положительными, достаточно потребовать выполнениянеравенства x0l > 0 илиA>lXln(pk µk )k=1µk− ln(pl µl )lX1.µkk=139(4)Необходимо также проверить неравенстваfi (0) = pi µi ≤ λ, i = l + 1, ..., n,или pl+1 µl+1 ≤ λ, поскольку pi µi упорядочены.

Последнее неравенство прологарифмируем и подставим выражение для!!−1llXXln(pk µk )1.ln λ =−Aµkµkk=1k=1В результате получимllXX1ln(pk µk )ln(pl+1 µl+1 )≤− A.µkµkk=1k=1Добавим к обеим частям выражение ln(pl+1 µl+1 )(µl+1 )−1 и в результатеполучим неравенствоA≤l+1Xln(pk µk )k=1µk− ln(pl+1 µl+1 )l+1X1.µk(5)k=1Итак, номер l выбирается из условий (4),(5), либо l = n.

Заметим, чтонеравенство (4) выполнено при l = 1. Нетрудно видеть, что выражениеlXln(pk µk )k=1µk− ln(pl µl )lX1µkk=1не убывает по l. Исследование модели полностью завершено.Рассмотрим дискретный аналог задачи (II) :max0x∈M0nXfi (xi ) =nXfi (x∗i )(II)0 .i=1i=1Здесь fi (t) − возрастающие функции целого аргумента. Пусть, кроме того,выполнено следующее условие вогнутости:если xi > 0, то fi (xi ) ≥ 0.5(fi (xi + 1) − fi (xi − 1)) илиfi (xi ) − fi (xi − 1) ≥ fi (xi + 1) − fi (xi ).(1)Неравенство (1) означает, что разность между значениями функции fi всоседних точках не возрастает.Теорема 3.10.

(Критерий Гросса). В сделанных предположениях пустьx∗ − оптимальное распределение ресурса в задаче (II)0 . Тогда для x∗ выполнено необходимое и достаточное условие:x∗j > 0 ⇒ fj (x∗j ) − fj (x∗j − 1) ≥ max [fi (x∗i + 1) − fi (x∗i )].i≤i≤n40(2)Замечание. При положительном x∗j разность fj (x∗j ) − fj (x∗j − 1), представляющая собой дискретную производную, близка к правой части неравенства (2).

Таким образом, условие (2) представляет собой дискретныйаналог принципа уравнивания для производных.Доказательство. Необходимость. Пусть x∗ − оптимальное распределениересурса в задаче (II)0 . Покажем, что выполнено условие (2). Предположимпротивное, т.е. найдется такой номер j, что x∗j > 0 иfj (x∗j ) − fj (x∗j − 1) < max [fj (x∗i + 1) − fi (x∗i )] = fl (x∗l + 1) − fl (x∗l ).i≤i≤nЗаметим, что l 6= j, поскольку при l = j нарушалось условие (1) для функции fj в точках x∗j . Определим вектор z :∗xj − 1, i = j,zi = x∗j + 1, i = l, ∗xi ,i 6= j, l.Последнее неравенство можно переписать в видеfj (x∗j ) + fl (x∗l ) < fj (x∗j − 1) + fl (x∗l + 1).ОтсюдаnPi=1fi (x∗i ) <nPfi (zi ), что противоречит определению x∗ .i=1Достаточность.

Пусть для распределения ресурса x∗ выполнено условие(2). Возьмем любое распределение x ∈ M00 , x 6= x∗ . Докажем, чтоnXfi (xi ) ≤nXfi (x∗i ).(3)i=1i=1Положимλ = max [fi (x∗i + 1) − fi (x∗i )].i≤i≤nПокажем, что при всех i выполнено неравенствоfi (x∗i ) − fi (xi ) ≥ λ(x∗i − xi ).(4)Складывая неравенства (4), получим (3) и завершение доказательства. Рассмотрим два случая1) x∗i > xi . Тогда x∗i > 0. Из условия (2) fi (x∗i )−fi (x∗i −1) ≥ λ.

Посколькуразности не возрастают, получим еще неравенстваfi (x∗i − 1) − fi (x∗i − 2) ≥ λ,··· ···fi (x∗i− 1) − fi (x∗i − 2) ≥ λ.Всего x∗i − xi неравенств. Складывая эти неравенства, получим fi (x∗i ) −fi (xi ) ≥ λ(x∗i − xi ).412) xi > x∗i . По определению λ имеем fi (x∗i + 1) − fi (x∗i ) ≤ λ. Посколькуразности не возрастают получим еще неравенстваfi (x∗i + 2) − fi (x∗i + 1) ≥ λ,··· ···fi (xi ) − fi (xi − 1) ≥ λ.x∗iВсего xi −неравенств. Складывая эти неравенства, получим fi (xi ) −fi (x∗i ) ≤ λ(xi − x∗i ) или (4).Упражнения.

1. Сформулируйте аналоги теорем 3.10 и 3.11 для непреnnPPрывной и дискретной задач на минимум minfi (xi ) и min0fi (xi ).x∈M0 i=1x∈M0 i=12. На основе критерия Гросса разработайте алгоритм решения задачи(II)0 . Докажите, что этот алгоритм сходится за конечное число шагов.42.