Ограничение =1 также автоматически вытекает из способа определения q)

через Wjt. (Проверьте!) Таким образом, задачу можно записать в следующем виде.

т К

Максимизировать Е = vf wa

при ограничениях

= 1 *=1

т К

11 , =1,

-1 *=i

wlt>0, i = l,2,...,m; к = 1,2,-,К.

Сформулированная задача представляет собой задачу линейного программирования с переменными w,t. Покажем, что ее оптимальное решение автоматически гарантирует, что q\ = 1 для одного k при любом i. Заметим, что в задаче линейного программирования имеется т независимых уравнений (одно уравнение, соответствующее я = яР, избыточно). Следовательно, задача должна включать т базисных переменных. Однако можно показать, что wlt должно быть строго положительным по меньшей мере при

одном k для каждого /. Из этих двух утверждений можно заключить, что величина

может принимать только два значения (0 или 1), что и требовалось доказать. (Фактически полученный выше результат показывает также, что я, = X*-ivt<* =VV > где k - альтернатива, соответствующая wjt > 0 .)

Пример 19.4.1

Ниже приведена формулировка задачи садовника без дисконтирования в виде задачи линейного программирования.

Максимизировать £ = 5,3w + 4,7wl2 + 3w2l + 3,lw22 - w31 + 0,4w32 при ограничениях

vvM + w12-(0,2wM + 0,3wl2 +0,lw22 + 0,05w32) = 0,

w2l + w22 -(0,5wu +0,6w]2 + 0,5w2] + 0,6w22 + 0,4w32) = 0, w31 + w32 -(0,3wn + 0,lwl2 + 0,5w2l + 0,3w22 + w3, + 0,55w32) = 0, w + w,2 + w2l + w22 + w3l + wi2 = 1, wlt 2. 0 при любых i и к.

Оптимальным решением является wn= w2l= w3l = 0, w12= 0,1017, w22 = 0,5254 nw32 = 0,3729. Это означает, что q] =q\=q] = \. Таким образом, оптимальная стратегия требует выбора альтернативы 2 (к = 2) при /= 1, 2 и 3. Оптимальное значение Е равно 4,7x0,1017 + 3,1x0,5254 + 0,4x0,3729 = 2,256. Интересно отметить, что положитель-

ные значения wlk в точности равны значениям я соответствующим оптимальной стратегии, определенной с помощью метода полного перебора в примере 19.3.1, что доказывает непосредственную взаимосвязь между двумя методами решения.

Рассмотрим теперь марковскую задачу принятия решений с дисконтированием. В подразделе 19.3.2 эта задача описывается рекуррентным уравнением

/(/) = maxU + a£pj/(y) , / = l,2,...,m.

Это уравнение эквивалентно следующему:

/(/) > cC£,P-,f{j) + v., для всех ink ,

при условии, что при любом i функция f(i) достигает минимального значения. Рассмотрим теперь целевую функцию

минимизировать Z./()>

где bt (> 0 при всех i) - произвольные константы. Можно показать, что оптимизация этой функции (при ограничениях в виде приведенных выше неравенств) дает, что и требуется, минимальное значение f(i). Таким образом, задачу можно записать следующим образом.

Минимизировать ZV()

при ограничениях

/(О aZPijfU) - v> при любыхи *.

/(/) не ограничены по знаку, / = 1,2,...,т. Двойственной к приведенной выше задаче является задача

т К

максимизировать ZZV*W>*

при ограничениях

К т К

*=1 1=1 *=1

и>0при ( = l,2,...,w; к = 1,2,...,К.

Пример 19.4.2

Рассмотрим задачу садовника с коэффициентом дисконтирования а = 0,6. Если положить Л, = Ъг = b3 = 1, то двойственную задачу линейного программирования можно записать в следующем виде.

Максимизировать 5,3wM + 4,7w12 + 3w21 + 3,lw22 - w + 0,4w,2

УПРАЖНЕНИЯ 19.4

1. Сформулируйте указанные ниже задачи в виде задач линейного программирования.

a) Задача упражнения 19.3.2.1.

b) Задача упражнения 19.3.2.2.

c) Задача упражнения 19.3.2.3.

19.5. ПРИЛОЖЕНИЕ: ОБЗОР ТЕОРИИ ЦЕПЕЙ МАРКОВА

Рассмотрим дискретные моменты времени {tk}, k = l, 2.....и пусть - случайная величина, характеризующая состояние системы в момент tk. Семейство случайных величин } образует стохастический процесс. Состояния в момент

времени tk, в которых может находиться в этот момент система, формируют полную и взаимно исключающую группу событий. Число состояний системы может быть конечным или бесконечным. Так, например, распределение Пуассона

P (t) =-Ц и = 0,1,2,...

представляет стохастический процесс с бесконечным числом состояний. Здесь случайная величина п соответствует числу наблюдаемых событий в интервале от 0 до t (начальным моментом считается 0). Таким образом, состояния системы в любой момент t задаются случайной величиной п = 0, 1, 2, ...

Еще одним примером может служить игра с k подбрасываниями монеты. Каждое испытание (подбрасывание монеты) можно рассматривать как некоторый момент времени. Полученная последовательность испытаний образует случайный процесс. Состоянием системы при любом испытании является либо герб , либо решка .

В данном разделе приводятся сведения о таких случайных процессах, как марковские процессы и марковские цепи. Цепь Маркова является частным случаем марковских процессов. Цепи Маркова используются при изучении краткосрочного и долгосрочного поведения стохастических систем с дискретным множеством состояний.

19.5.1. Марковские процессы

Марковский процесс описывает поведение стохастической системы, в которой наступление очередного состояния зависит только от непосредственно предшест-

при ограничениях

w + w,2-0,6[0,2wn + 0,3wl2 + 0,lw22 + 0,05w32] = l,

w21 +w22 -0,6[0,5wn + 0,6wl2 + 0,5w2, + 0,6w22 + 0,4w32] = l, Wj, + w32 -0,6[0,3wn + 0,lwl2 + 0,5w21 + 0,3w22 + w3P + 0,55w32] = 1, wlk > 0 при любых / и к.

Оптимальным решением будет w12 = w2] = w3] = 0, wn= 1,5678, w22 = 3,3528 и w32 = 2,8145. Из этого решения следует, что оптимальной стратегией является {1,2,2}.