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

14.1).6g(x)f (x)-xx0Рис. 14.1.Функция h(x0 ) не дифференцируема. В точке x0 существуют два направления, задаваемые векторами α = (1) и −α.Упражнение. Покажите, чтоdh(x0 )dh(x0 )= g 0 (x0 ),= −f 0 (x0 ).dαd(−α)26Теорема 3.6. Пусть x ∈ D ⊂ E m , где D − открытое множество в E m ,а y принадлежит метрическому компакту N. Предположим, что функцииF (x, y), Fx0 i (x, y), i = 1, ..., m определены и непрерывны на D × N. Тогда влюбой точке x ∈ D по любому направлению α ∈ E m существует производная функции минимума W (x), которая имеет видmXdW (x)= minαi Fx0 i (x, y),dαy∈N (x)i=1(1)где N (x) = Arg min F (x, y).y∈NЗамечание. Формула (1) показывает, что, с некоторой оговоркой, операции взятия минимума и производной по направлению перестановочны.

Вправой части формулы (1) вместо N фигурирует N (x).Доказательство. Заметим, что N (x) − компакт как замкнутое подмножество компакта N. Рассмотрим x ∈ D и произвольный вектор α ∈ E m .Пусть xk = x + εk α, εk > 0, lim εk = 0 − последовательность векторов,k→∞сходящаяся к x. Запишем последние равенства векторов в координатах:xki − xi = εk αi , i = 1, ..., m, k = 1, 2, ...

Необходимо доказать существованиепределаW (xk ) − W (x),limk→∞εkзадаваемого формулой (1). Рассмотрим последовательность y k ∈ N (xk ), k =1, 2, ... и любое y ∈ N (x). ТогдаW (xk ) − W (x)F (xk , y k ) − F (x, y)==εkεkF (xk , y k ) − F (xk , y) + F (xk , y) − F (x, y)≤εkmP(xki − xi )Fx0 i (x + θk (xk − x), y)F (xk , y) − F (x, y)i=1≤==εkεkmX=αi Fx0 i (x + θk (xk − x), y),=i=1где 0 < θk < 1. Отсюда, пользуясь непрерывностью функций Fx0 i (x, y), получим оценку для верхнего пределаmW (xk ) − W (x) X≤αi Fx0 i (x, y), ∀ y ∈ N (x).k→∞εki=1limОтсюдаmXW (xk ) − W (x)αi Fx0 i (x, y).≤ mink→∞εky∈N (x)i=1lim27(2)Для завершения доказательства достаточно установить аналогичное неравенства для нижнего предела:mXW (xk ) − W (x)lim≥ minαi Fx0 i (x, y).εy∈N(x)k→∞ki=1(3)По определению нижнего предела существует такая подпоследовательностьkl , l = 1, 2, ..., чтоW (xk ) − W (x)W (xkl ) − W (x)= lim.l→∞ε klεkk→∞limВ силу компактности множества N без потери общности можно считать, чтоlim y kl = y ∗ ∈ N.

Покажем, что y ∗ ∈ N (x). Действительно, F (xkl , y kl ) ≤l→∞klF (x , y), ∀ y ∈ N. Переходя в этом неравенстве к пределу при l → ∞,получим F (x, y ∗ ) ≤ F (x, y), ∀ y ∈ N ⇒ y ∗ ∈ N (x). Далее, имеемW (xkl ) − W (x)F (xkl , y kl ) − F (x, y ∗ )==εklε kl=F (xkl , y kl ) − F (x, y kl ) + F (x, y kl ) − F (x, y ∗ )≥ε klF (xkl , y kl ) − F (x, y kl )=≥εkl=mXmPi=1(xki l − xi )Fx0 i (x + θkl (xkl − x), y kl )ε kl=αi Fx0 i (x + θkl (xkl − x), y kl ),i=1где 0 < θkl < 1. Перейдем в полученном неравенстве к пределу при l → ∞и получимmmXW (xk ) − W (x) X≥αi Fx0 i (x, y ∗ ) ≥ minαi Fx0 i (x, y).εky∈N (x)k→∞i=1i=1limНеравенство (3) доказано.

Утверждение теоремы следует из неравенств (2)и (3), которые могут выполняться только как равенства.Пример. Рассмотрим в E 3 функциюW (x1 , x2 , x3 ) = min ϕj (x1 , x2 , x3 ),1≤j≤32где ϕ1 = x21 + x22 + x23 , ϕ2 = x102 , ϕ3 = cos(πx1 ) + x2 + 10x3 .Найдем производную функции W (x) в точке x0 = (2, −2, 1) по направлению α = (−3, 2, −1).

Здесь можно воспользоваться формулой (1), посколькумножество N = {1, 2, 3} превратить в метрическое пространство, задав на28нем метрику. Имеем ϕ1 (x0 ) = 9, ϕ2 (x0 ) = 210 , ϕ3 (x0 ) = cos(4π) − 2 + 10 = 9.Отсюда N (x0 ) = {1, 3}. Далееϕ01 (x0 ) = (4, −4, 2), ϕ03 (x0 ) = (0, 1, 10),dW (x0 )= −22.dαПерейдем к выводу необходимых условий для максиминной стратегии.(α, ϕ01 (x0 )) = −22, (α, ϕ03 (x0 )) = −8 ⇒Следствие теоремы 3.6. Пусть M0 − выпуклый компакт в E m , а L(x0 )− множество допустимых направлений в точке x0 ∈ M0 ,е x0 ∈ M0 − максиминная стратегия. Тогда в условиях теоремы 3.6выполнено следующее необходимое условие:supmin 0mXα∈L(x0 ) y∈N (x ) i=1αi Fx0 i (x0 , y) ≤ 0.(4).Доказательство. Функция W (x) достигает в точке x0 ∈ M0 наибольшегозначения.

ПоэтомуW (x0 + εα) − W (x0 )dW (x0 )= lim≤ 0 ∀ α ∈ L(x0 ),ε→+0dαεпоскольку при малых ε > 0 вектор x0 +εα принадлежит M0 по определениюдопустимого направления α.Теперь займемся упрощением условия (4) для частных случаев. ПустьM0 = [a, b] − отрезок.Теорема 3.7. Пусть функции F (x, y), Fx0 (x, y) непрерывны на множествеD × N, где D − интервал, содержащий отрезок M0 = [a, b], а N − компактметрического пространства. Тогда для максиминной стратегии x0 ∈ M0выполнено хотя бы одно из следующих трех условий:а) x0 = a или x0 = b;б) найдутся y 1 6= y 2 ∈ N (x0 ) = Arg min F (x, y);y∈Nв) N (x0 ) = {y 1 } и Fx0 (x0 , y 1 ) = 0.Замечание.

Теорема обобщает необходимые условия для точки максимума x0 дифференцируемой функции на отрезке: либо точка x0 являетсяконцом отрезка, либо производная функции в точке x0 равна нулю.Доказательство. Пусть x0 − оптимальная стратегия. Если выполненыусловия 1) или 2), то все доказано. Пусть условия 1) и 2) не выполнены, т.е.a < x0 < b и N (x0 ) = {y 1 }.

Покажем, что обязательно выполнено условие3). Из формулы (4) следует, что для двух допустимых направлений α = (1)и −α выполнены неравенстваdW (x0 )dW (x0 )= 1 · Fx0 (x0 , y 1 ) ≤ 0,= (−1) · Fx0 (x0 , y 1 ) ≤ 0.dαd(−α)29Следовательно, Fx0 (x0 , y 1 ) = 0.Следствие. Пусть в условиях теоремы 3.7N = {y ∈ E n | cj ≤ yj ≤ dj , j = 1, ..., n}− параллелепипед евклидова пространства E n , в любой точке которого существуют производные Fy0 j (x, y), j = 1, ..., n.

Тогда для максиминной стратегии x0 ∈ M0 = [a, b] выполнено хотя бы одно из следующих двух условий:1) ∃ y 1 ∈ N (x0 ) :Fx0 (x0 , y 1 )(x0 − a)(x0 − b) == Fy0 j (x0 , y 1 )(yj1 − cj ))(yj1 − dj ) = 0, j = 1, ..., n.(5)2) ∃ y 1 6= y 2 ∈ N (x0 ) :F (x0 , y 1 ) = F (x0 , y 2 ), Fy0 j (x0 , y 1 )(yj1 − cj )(yj1 − dj ) == Fy0 j (x0 , y 2 )(yj2 − cj )(yj2 − dj ) = 0, j = 1, ..., n.(6)Доказательство. По теореме 3.7 для x0 выполнено одно из условийа),б) или в). Покажем, что из а) или в) следует условие 1). Поскольку y 1 ∈N (x0 ), то min F (x0 , y 1 ||yj ) = F (x0 , y 1 ).

Теперь остается воспользоватьсяcj ≤yj ≤djнеобходимыми условиями для точки минимума yj1 функции F (x0 , y 1 ||yj ) наотрезке [ci , dj ]. Из них получаем уравненияFy0 j (x0 , y 1 )(yj1 − cj ))(yj1 − dj ) = 0, j = 1, ..., n.Далее, из б) следует условие 2).Отметим особенности полученных необходимых условий. В системе (5)число уравнений n + 1 совпадает с числом неизвестных x0 , y11 , ..., yn1 . Поэтому можно надеяться, что система (5) имеет конечный набор решений. Всистеме (6) число уравнений 2n + 1 также совпадает с числом неизвестныхx0 , y11 , ..., yn1 , y12 , ..., yn2 .Можно следующим образом использовать эти необходимые условия.

Сначала находим все решения систем (5) и (6). Пусть первые компоненты x0этих решений образуют множество M0∗ , а соответствующие компонентыy 1 , y 2 образуют множество N ∗ . Тогда x0 ∈ Arg max∗ min∗ F (x, y).x∈M0 y∈NПример. Пусть F (x, y) = −(x − y + y 3 )2 , M0 = N = [−1, 1].По смыслуF (x, y) − квадрат отклонения (со знаком минус) величины x от значения30функции ϕ(x) = y − y 3 . График функции ϕ(x) изображен на рис.

1.ϕ(x)6√1/ 31- x√−1/ 301Рис. 15.1Здесь()√ 1/ 3 , x < 0()√N (x) =± 1/ 3 , x = 0()√ − 1/ 3 , x > 0.При y ∈ N (x) Fx0 (x, y) = −2(x − y − y 3 ) 6= 0. Поэтому для максиминнойстратегии система а) не выполнена,следовательно,выполнена система б).()Имеем M0∗ = {−1, 0, 1}, N ∗ =±√13− √13√13(F (x, y))M0∗ ×N ∗,!22−1  − 1 + √3!2= 0  − √23!22+1 − 1 − √3!2− 1−√23!2 .− √23!2 − 1 + √23Отсюда x0 = 0 − максиминная стратегия. Отметим, что в этом примеревыполнено условие 2), а условие 1) для x0 не выполнено.Легко построить пример, где, наоборот, для максиминной стратегии x0выполнено условие 1), а условие 2) не выполнено. Пусть, например, функция31F (x, y) строго выпукла по y.

В этом случае при любом x ∈ M0 множествоN (x) состоит из единственного элемента.§15. Задачи оптимального распределения ресурсов.В этом параграфе мы рассмотрим некоторые задачи оптимального распределения ресурсов. Будут сформулированы условия оптимальности, атакже указаны алгоритмы поиска оптимальных распределений ресурсов.Пусть i = 1, ..., n, − номера n пунктов, по которым оперирующая сторонараспределяет ресурс. Через fi (t) обозначим функцию, определяющую эффект от вложения ресурса в количестве t в i-й пункт.

Вектор x = (x1 , ..., xn )задает стратегию распределения реcурса. При этом на i-й пункт направляется ресурс в количестве xi .Будем рассматривать два вида задач: непрерывные, где ресурс предполагается бесконечно-делимым, и дискретные, где ресурс − штучный, а Aи xi − целые числа. Для непрерывной задачи множество стратегий имеетвидnXM0 = {x ∈ E n |xi = A, xi ≥ 0, i = 1, ..., n},i=1а для дискретной −M00 = {x ∈ E n |nXxi = A, xi ≥ 0, xi ∈ Z, i = 1, ..., n},i=1где Z − множество целых чисел.Рассмотрим следующую непрерывную задачу:max min fi (xi ) = min fi (x0i ).x∈M0 1≤i≤n1≤i≤n(I)По смыслу оперирующая сторона стремится максимизировать свертку вида min fi (xi ), т.е.

минимальный эффект от вложения ресурса. Это отвеча1≤i≤nет социалистическому принципу: "чтобы не было бедных". Максиминнуюстратегию x0 будем называть оптимальным распределением ресурса.Задачу (I) будем рассматривать в предположении, что все функции fi (t)непрерывны и возрастают на отрезке [0, A]. Кроме того, без потери общности будем считать, чтоf1 (0) ≤ f2 (0) ≤ ... ≤ fn (0).Будем условно говорить, что первый пункт является слабейшим: если пунктам не выделяется ресурс, то эффект на первом пункте будет наименьшим.Теорема 3.8.