А. Кофман и Р. Фор. Займемся исследованием операций (стр. 7 )

x1 + x2 + x3 = A.

Так получают функцию F1,2,3 (A) и так далее.

В обсуждавшейся задаче и в математическом описании, изложенном выше, природа ограничений - а в действительности единственного ограничения (1) - позволяет при последовательной оптимизации действовать в произвольном порядке; далеко не всякая задача обладает, как можно подозревать, этим свойством. Очень часто природа ограничений диктует необходимость действовать в одном или нескольких частных порядках и запрещает другие. Говорят, что задача последовательных решений сильно упорядочена, если действовать можно лишь в одном порядке или ему обратном. Если же, сверх того, можно действовать лишь в одном направлении, тогда говорят, что задача сильно упорядочена и сильно ориентирована; последнее особенно важно, когда рассматриваются состояния (положения), определяемые посредством случайной величины. Можно еще мыслить себе пошаговую оптимизацию по двум или даже больше переменным одновременно, но интерес к динамическому программированию быстро утрачивается из-за проистекающих в результате этого усложнений.

Формулы (2) можно обобщить на тот случай, когда на каждой фазе оптимизации рассматривается не одна переменная, а совокупность переменных, или вектор состояния. Именно так, например, можно разыскивать в каждый данный момент оптимум для экономической системы, где участвуют многочисленные взаимосвязи между производством и потреблением, причем можно принимать решение относительно вектора состояния или какого-нибудь другого вектора, от которого он зависит; шаг за шагом удаляясь в будущее или - в зависимости от природы задачи - возвращаясь во времени назад, вычисляют оптимум относительно рассматриваемого экономического горизонта.

Свойства динамического программирования являются следствиями некоторого общего принципа, названного Беллманом принципом оптимальности: «Некоторая политика оптимальна, если в течение данного периода, каковы бы ни были предшествующие решения, решения, которые остается принять, образуют относительно результатов предшествующих решений оптимальную политику».

ГЛАВА 3. Фабрикант кукол (Цепь Маркова. Проблема последовательных решений).

На оживленном перекрестке транспортных магистралей Мехико, когда красный сигнал светофора подвергает ваше терпение утомительному испытанию, вас атакуют молодые продавцы-акробаты; они с удивительной ловкостью проскальзывают между автомобилями, подвергаясь большому риску... но мексиканцы так любят опасность! Эти молодые люди предлагают вам интересные вещи всякого рода: автомобильные детали, лотерейные билеты, плоды манго, когда позволяет сезон, а также кукол, о которых нам и хотелось бы рассказать.

Мексиканские куклы называются «титерес»; являясь развлечением для детей, они, несомненно, способны предоставить небольшую передышку родителям. Однако особенно замечательны они полным юмора подбором персонажей, взятых из мексиканского фольклора, одного из самых увлекательных и самых богатых в мире, по мнению великих путешественников. Как не восхищаться этими ярко раскрашенными марионетками с такими смешными лицами, как не завязать знакомство с ловкачом Люпе, одним из лучших продавцов!

При покупке первой марионетки Люпе думал, что он имеет дело с гринго (не переводите это слово как «американец», так как сами мексиканцы тоже американцы! Гринго - это человек с Севера, с кучей долларов). При второй покупке он сказал себе: «Какой оригинал!»; при третьей: «Вот коллекционер!» Во время четвертой встречи он заключил, что имеет дело с очень богатым гринго, который, однако, настолько оригинален, что передвигается в маленьком европейском автомобиле... Его расположение проявилось только тогда, когда он заметил свою ошибку и, выпив кока-кола, насильственно сделанного национальным напитком страны, согласился дать адрес своего дяди Мануэля, художника, фабриканта, отца скромного семейства из четырнадцати детей: что за очаровательный человек! Мы уверены, что если бы авиационные компании были бы более великодушны в вопросах багажных тарифов, вы обязательно привезли бы из вашего будущего путешествия в Мексику чемодан, наполненный этими замечательными куклами!

Производство и продажа кукол - предмет достаточно серьезный, чтобы заинтересовать инженера, занимающегося управлением и экономикой. Справедливо, что сеньор Мануэль имел свои собственные взгляды на этот вопрос. Но мы узнали об этом, только когда он решился наконец открыть причину своих забот: мексиканец не выставляет напоказ свои несчастья.

Сеньор Мануэль продает свою продукцию двадцати парням, подобным Люпе. Каждую неделю он производит только один тип кукол; если кукла имела успех, он решает выпускать этот же тип и на следующей неделе; в противном случае он выпускает новую модель. Его экономический горизонт[17] ограничивается неделей. Мануэль небогат и мало хозяйствен; он подчиняет

Рис. 3.1.

свое производство только результатам предшествующей недели. И если он производит только одну модель сразу, то это потому, что такие продавцы, как Люпе, не имеют времени предоставить выбор своим вечно спешащим клиентам - автомобилистам, несмотря на нескончаемую продолжительность красного сигнала. Именно поэтому предлагается одна и только одна модель, а нераспроданные остатки сохраняются для возможных посетителей фабрики.

Каждое утро по понедельникам Мануэль выбирает модель для производства согласно правилам, указанным выше.

Предположим, что в понедельник L1 он оценил продукцию предыдущей недели S0 как успешную; опишем простой схемой возможное будущее (рис. 3.1).

Вот таким образом случайности продажи подсказывают новый и оригинальный вывод: искусство и коммерция не так далеки друг от друга, как полагают некоторые!

Возможно, мексиканцев обвинят в беззаботности, но нужно признать, что они замечательно наблюдательны. Мануэль заметил следующее: если одна неделя привела к успеху и если продолжают выпускать те же куклы, то следующая неделя обеспечит успех с шансом один из двух. Если неделя обернулась неудачей и если выпускают новую модель, семь шансов из десяти за то, что следующая неделя принесет успех. Все это может показаться весьма произвольным; однако зачем покупателям кукол противостоять некоторым законам торговли и экономики в той мере, в какой мы их знаем и в какой они нам не кажутся противоречивыми?

Используя понятие вероятности, случайное будущее, образованное следующей неделей, можно схематизировать следующим образом (табл. 3.1):

Таблица 3.1

	Неделя Si + 1
успех	неудача
Неделя Si	успех	0,5	0,5
неудача	0,7	0,3

Числа 0,5; 0,5; 0,7; 0,3 являются вероятностями.

Таблица 3.1 дает вероятности изменения состояния среди двух состояний производства Мануэля: успеха и неудачи.

Рисунок 3.2 дает другое представление всех возможных изменений состояния - с помощью графа.

Рис. 3.2.

Сеньору Мануэлю неизвестно (а если бы он это и знал, то, вероятно, обратил бы на это столько же внимания, сколько на выеденное яйцо), что математики изучили свойства таких случайных последовательностей. Последовательный процесс, соответствующий случайностям продажи и решениям о производстве этих кукол, составляет часть очень важного класса последовательных случайных процессов: цепей Маркова. Покинем на время Мексику, чтобы заняться работами этого великого современного[18] русского математика. Конечно, мы все упростим, насколько возможно.

Обозначим через Е1 состояние, соответствующее успеху, через Е2 - состояние, соответствующее неудаче. В соответствии с табл. 3.1 и рис. 3.2, вероятности изменения состояния, т. е. вероятности перехода от некоторой недели Si к следующей Si + 1, записывают с помощью удобных индексных обозначений следующим образом:

Е1 → Е1 Е1 → Е2 Е2 → Е1 Е2 → Е2,

p11 = 0,5 p12 = 0,5 p21 = 0,7 p22 = 0,3.

Чтобы записать эти вероятности перехода совместно, удобно использовать таблицу, которую они образуют и которая называется матрицей. Пусть P - следующая матрица:

P = .

Предположим, что Мануэль начал свое управление с того, что зарегистрировал успех в течение недели S0; какова вероятность добиться успеха на протяжении недели S1? Как мы отметили, она равна 0,5; следовательно, вероятность неудачи также равна 0,5. Обозначим через P1(1) и Р2(1) вероятности, соответствующие концу первой недели. Мы имеем

P1(1) = 0,5 P2(1) = 0,5

(вероятность успеха) (вероятность неудачи)

Если эти вероятности известны, чему будут равны вероятности успеха и неудачи к концу второй недели? Обозначим эти вероятности через P1(2) и P2(2):

P1 (2) = P1(1)·0,5 + P2(1)·0,7 = 0,5·0,5 + 0,5·0,7 = 0,60;

(вероятность успеха)

P2(2) = P1(1)·0,5 + P2(1)·0,3 = 0,5·0,5 + 0,3·0,5 = 0,40.

(вероятность неудачи)

Таким же образом выразим вероятности успеха и неудачи к концу третьей недели:

P1(3) = P1(2)·0,5 + P2(2)·0,7 = 0,60·0,50 + 0,40·0,70 = 0,58;

P2(3) = P1(2)·0,5 + P2(2)·0,3 = 0,60·0,50 + 0,40·0,30 = 0,42.

Продолжая вычисления, получим

P1(4) = 0,584 P1(5) = 0,5832 P1(6) = 0,58336,

P2(4) = 0,416 P2(5) = 0,4168 P2(6) = 0,41663

и далее находим, что, каково бы ни было n,

Проведем снова все эти вычисления, предполагая, что неделя S0 соответствовала неудаче.

Соответствующие вероятности обозначим с помощью штрихов ':

P’1(1) = 0,7; P’2(1) = 0,3;

P’1(2) = 0,56; P’1(3) = 0,588; P’1(4) = 0,5824;

P’2(2) = 0,44; P’2(3) = 0,412; P’2(4) = 0,4176;

P’1(5) = 0,58352; P’1(6) = 0,583296; …

P’2(5) = 0,41648; P’2(6) = 0,416704; …

Таким образом, вероятности

P’1(n) = P1(n) и P’2(n) = P2(n)

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

Мануэль заметил это равновесие и поздравил себя с этим; ему достаточно, чтобы для достаточно большого числа недель вероятность успеха была бы ощутимо больше, чем вероятность неудачи. Этим он зарабатывает на жизнь себе и своему многочисленному семейству.

Чрезвычайно важно признать возможность равновесия в экономической системе; это справедливо как для мелкого фабриканта кукол, так и для целой нации. Впрочем, разве жизнь человека не находится в колебании между двумя тенденциями: авантюрой и равновесием? Жизнь предприятия такова же - и слава богу.

Несколько стаканов пульке развязали Мануэлю язык. Он сделал массу наблюдений относительно прошлого своего маленького предприятия.

Обычно когда две недели подряд приводят к успеху, его доход достигает 500 песо; успех, за которым следует неудача, дает доход только в 150 песо; успех, следующий за неудачей, - 200 песо; и дважды неудача - убыток 400 песо. Таким образом, обозначая через r11, r12, r21, r22 соответствующие доходы в порядке, данном выше, мы имеем

Е1 → Е1 Е1 → Е2 Е2 → Е1 Е2 → Е2,

r11 = 500 r12 = 150 r21 = 200 r22 = –400.

Как изменяется при этих условиях доход Мануэля, если вести накапливающую запись доходов по мере того, как проходят недели? Чтобы сделать наши объяснения более точными, обозначим датой n - 1 начало недели n; таким образом, дата 0 соответствует началу недели 1, дата 1 соответствует концу недели 1 и началу недели 2, дата 2 соответствует концу недели 2 и началу недели 3 и т. д.

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

Для первой недели, от даты 0 до даты 1, мы имеем:

= p11×r11 + p12×r12 = 0,5·500 + 0,5·150 = 325,

 = p21×r21 + p22×r22 = 0,7·200 + 0,3· (–400) = 20.

Для двух недель, от даты 0 до даты 2, будем иметь:

= p11×+ p12×+ p11×r11 + p12×r12,

= p21×+ p22×+ p21×r21 + p22×r22.

Эти формулы немного сложнее, они заслуживают объяснения. Предположим, что в момент 0 имеет место состояние Е1 (рис. 3.3). От даты 0 до даты 1 математическое ожидание дохода равно

p11×r11 + p12×r12.

Теперь в момент 1 возможны состояния Е1 или Е2. Если имеет место состояние Е1, математическое ожидание дохода равно

p11×(p11×r11 + p12×r12) = p11.

Если же мы находимся в состоянии Е2, этот доход равен

p12×(p21×r21 + p22×r22) = p12.

Этот доход соответствует интервалу между датами 1 и 2.

Рис. 3.3.

Заметим, что, не предполагая, какое из состояний - Е1 или Е2 - окажется в момент 2, мы можем написать математическое ожидание дохода между датами 1 и 2 следующим образом:

p11×+ p12×.

Те же рассуждения нужно применить для объяснения . Подставляя численные значения, мы получаем:

= 0,5·325 + 0,5·20 + 325 = 497,5;

= 0,7·325 + 0,3·20 + 20 = 253,5.

Аналогичное рассуждение дают нам и :

= p11×+ p12× + p11×r11 + p12×r12 =

= 0,5·497,5 + 0,5·253,5 + 325 = 700,5;

= p21×+ p22×+ p21×r21 + p22×r22 =

= 0,7·497,5 + 0,3·253,5 + 20 = 444,3;

и так далее:

= 897,4; = 1095,52; = 1293,396;

= 643,64; = 841,272; = 1039,2456.

……..

Можно доказать, что разность

- 

стремится к следующему значению, когда N неограниченно возрастает:

Для большого числа недель N будем иметь [19]:

= 197,916 N + 105,902,

= 197,916 N - 148,264.

Средний еженедельный доход Мануэля будет равен соответственно

Когда , и стремятся к пределу

–r = 197,916.

Таким образом, Мануэль в среднем заработает для своей семьи 197,916 песо в неделю.

Будучи осторожным торговцем, он задался естественным вопросом - как увеличить свой доход? Он попытался действовать различными способами, из которых мы рассмотрим только два следующих: 1) распространять среди клиентуры автомобилистов маленькие картонные картинки - изображения кукол - в надежде, что на следующий день при том же красном сигнале они возымеют желание купить какую-нибудь куклу; 2) снизить продажную цену примерно на 10%. Очевидно, такие решения влияют на еженедельный доход. Исследуя результаты его прошлых наблюдений, можно построить приведенную ниже таблицу. Конечно, можно было бы вообразить много других решений, но в целях упрощения мы изучим только указанные возможности. Обозначим буквами различные решения:

P1 - решение не распространять картинки после успеха;

P2 - решение распространять картинки после успеха;

Q1 - решение не изменять цену после неудачи;

Q2 - решение снизить цену на 10% после неудачи.

Из сведений, собранных Мануэлем, были извлечены следующие значения, для которых мы сохраним прежние индексные обозначения и, кроме того, введем индекс вверху для обозначения величин, соответствующих различным решениям:

P1: p11(1) = 0,5; p12(1) = 0,5; r11(1) = 500; r12(1) = 150;

P2: p11(2) = 0,6; p12(2) = 0,4; r11(2) = 400; r12(2) = 200;

Q1: p21(1) = 0,7; p22(1) = 0,3; r21(1) = 200; r22(1) = -400;

Q2: p21(2) = 0,8; p22(2) = 0,2; r21(2) = 100; r22(2) = -800.

Отметим, что в случаях Р2 и Q2 речь идет, естественно, о чистом доходе, учитывая новые стоимости и цену.

Рис. 3.4. Пример возможной «истории» управления Мануэля за несколько недель.

Пунктир соответствует оптимальному управлению, которое мы выясним далее.

Те из наших читателей, которые привыкли к матричным обозначениям, запишут:

P (1) = , R (1) = 

P (2) = , R (2) = 

Рисунок 3.4 дает пример управления на несколько недель при этих условиях.

Каждую неделю нужно принимать решения, какую политику (т. е. какой набор решений) для множества из N недель следует принять, так чтобы доход, накопленный за N недель, был максимальным. Точнее, какая политика обеспечивает максимальное математическое ожидание дохода за N последовательных недель.

Чтобы провести эти вычисления, нужно обратиться к динамическому программированию; каким образом - мы увидим дальше.

Сначала нужно уточнить, что для осуществления такого процесса оптимизации нужно начать с N, т. е. с последней недели, затем возвратиться к (N - 1)-й, далее к (N - 2)-й... и так далее до первой недели.

Введем обозначения:

- математическое ожидание недельного дохода от даты N - 1 до даты N, когда в дате N - 1 зарегистрирован успех предыдущей недели;

- соответствующее выражение для случая неудачи в предшествующей неделе;

- математическое ожидание полного дохода за 2 недели от даты N - 2 до даты N, когда дате N - 2 предшествовал успех;

- то же выражение, когда дате N - 2 предшествовала неудача.

Определим аналогичным образом

и т. д.

до тех пор, пока не станет N – 20 = 0, если управление Мануэля было предусмотрено на N = 20 недель.

Оптимальное управление для одной недели (от даты N - 1 до даты N).

Имеем

Если в момент N - 1 Мануэль находится в ситуации Е1 , он должен выбрать в этот момент решение Р1, чтобы иметь оптимальную ситуацию от N - 1 до N:

Если в момент N - 1 Мануэль находится в ситуации Е2, он должен выбрать в этот момент решение Q1, чтобы иметь оптимальную ситуацию от N - 1 до N.

Посмотрим теперь, как найти оптимум для двух недель от даты N - 2 до даты N - 1.

Оптимальное управление на две недели (от даты N - 2 до даты N).

Сравним рис. 3.3 и 3.5. Последующее рассуждение аналогично; но для того чтобы вычислить затем и остальные математические ожидания доходов для 3, 4, ... недель, нужно каждый раз исследовать эти значения, сравнивая результаты различных возможных решений.

Рис. 3.5.

Таким образом, Мануэль должен будет выбрать в качестве значения большую из следующих величин [20]:

и

которые равны

0,5·325 + 0,5·20 + 325 = 497,5

и

0,6·325 + 0,4·20 + 320 = 523.

Следовательно, он должен выбрать в момент N - 2 решение Р2, если предшествующая неделя была успешной, и тогда управление от N - 2 до N будет оптимальным и приведет к доходу 523.

Поэтому

= 523.

Если в момент N - 2 вместо E1 имеет место ситуация Е2, аналогичное вычисление [21] дохода приведет к сравнению величин

и

;

вычисляя, получаем

0,7·325 + 0,3·20 + 20 = 253,5,

0,8·325 + 0,2·20 - 80 = 184.

Таким образом, в момент N - 2 он должен выбрать решение Q1 , если предшествующая неделя была неудачной, и тогда управление от N - 2 до N будет оптимальным и даст доход 253,5.

Следовательно,

= 253,5.

Оптимальное управление на три недели (от даты N - 3 до даты N).

Тот же самый процесс далее повторяется; чтобы вычислить , нужно сравнить

и

что приводит к значению

= max (713,5; 735,2) = 735,2;

и нужно выбирать P2; аналогично

= max (462,15; 389,1) = 462,15

и нужно выбирать Q1.

Продолжая таким же образом, находим, предполагая, что N = 20:

Оптимальное уравнение для n недель	Полный средний доход	Оптимальное решение
n = 4	= 945,98	P2
	= 673,28	Q1
n = 5	= 1156,90	P2
	= 884,17	Q1
…	…	…
n = N = 20	= 4320,33	P2
	=4047,60	Q1

Наконец, оптимальное управление для 20 недель (от даты 0 до даты 20 в предположении, что Мануэль прекращает свое производство и свою торговлю после 20 недель, какова бы ни была ситуация в дате 18) будет следующим. Для всех дат 0, 1, 2, 3, ... 18:

а)  если предшествующая неделя была успешной - выбирать Р2;

б)  если предшествующая неделя была неудачной - выбирать Q1.

Для даты 19:

а)  если предшествующая неделя была успешной - выбирать P1;

б)  если предшествующая неделя была неудачной - выбирать Q1.

Следуя такой политике, Мануэль заработает 4320,33 песо за 20 недель, если первой неделе предшествовал успех и 4047,60, если ей предшествовала неудача.

Вместо того чтобы ограничиться 20 неделями, можно продолжить вычисления дальше, и, каково бы ни было число недель, мы снова получим политику, определенную выше.

Как мы уже ранее сделали, мы можем заняться вычислением среднего еженедельного дохода, полагая

Можно доказать [22], что

Для 20 недель управления находим

Когда N растет, разность  -  стремится к нулю; это можно быстро заметить, продолжая вычисления для более чем 20 недель.

Наконец, придерживаясь политики Р2, Q1 для всех недель, за исключением последней, и Р1, Q1 для последней, Мануэль в среднем заработает в неделю 210,91 песо вместо 197,91[23].

Таким образом, связывая теорию марковских цепей с динамическим программированием (можно видеть, что для перехода от управления одной неделей к двум неделям, затем к трем неделям и т. д. ... мы непосредственно применили принцип оптимальности Беллмана, рассмотренный в гл. 2), возможно исследовать различные задачи управления в условиях неопределенности и находить оптимальную политику (или оптимальные политики).

Краткое изложение теории цепей Маркова.

Пусть система может принимать некоторое число состояний E0, E1 ... , Ek, .... Изменения состояний происходят в определенные моменты 0, 1, 2, ... , n,.....Если pk (п) обозначает вероятность состояния Ek в момент n, состояние системы в момент п можно представить вектором состояния

где все pk (п) заключены между нулем и единицей и сумма всех вероятностей для каждого момента n

равна 1.

Пусть любой паре состояний (Ei, Ej) можно сопоставить вероятность перехода pij, которая равна вероятности того, что если система в момент n находилась в состоянии Ei, то в момент n + 1 она будет находиться в состоянии Ej. Тогда