Матричные игры: чистые и смешанные стратегии .стохастические методы управления запасами

Теоретическая часть
I. Матричные игры: чистые и смешанные стратегии
1.1. Матричные игры. Двойственная задача линейного программирования
II. Стохастические методы управления запасами.
2.1. Специфика выбора критерия оптимальности
2.2. Управление запасами в условиях неопределенности
2.3. Дихотомический выбор (задача о золотодобыче)
2.4. Марковские процессы принятия решений
Практическая часть.
Заключение
Список использованной литературы

Матричные игры: чистые и смешанные стратегии .стохастические методы управления запасами

Обозначим через Fk(Y) математическое ожидание издержек в k-шаговом процессе при начальном запасе Y и при использовании оптимальной политики.
Очевидно, что затраты на первом шаге процесса при начальном запасе Y равны сумме затрат на производство X единиц продукции, т.е. значению K(X), и ожидаемых затрат на покрытие неудовлетворенного спроса.
Т. к. при S Ј Y + X спрос удовлетворяется полностью, то последние равны
Последующий k-1-шаговый процесс начнется с начальным запасом Y+X-S при S в диапазоне от 0 до Y+X и нулевым начальным запасом при S, превысившим Y+X.
Тогда в соответствии с принципом оптимальности задача минимизации затрат в процессе конечной длительности сводится к рекуррентным соотношениям вида:
Нетрудно построить и другие модификации рассматриваемой задачи. Так, если производимая в текущем сезоне продукция становится готовой для покрытия спроса лишь в следующем сезоне, рекуррентные соотношения преобразуются к виду
В случае же аналогичной задержки на два сезона приходится ввести в рассмотрение функцию двух переменных Fk(Y,Z) как минимум ожидаемых затрат в k-шаговом процессе с начальным запасом Y и объемом производства на предыдущем шаге Z:
Нетрудно обобщить полученные рекуррентные соотношения и на случай бесконечношагового процесса, если прибегнуть к критерию интегрального дисконтированного эффекта. Так для первого из рассмотренных вариантов задачи возникает функциональное уравнение
Если принять K(X) = kX , R(X) = rX при X і 0 и область минимизации ограничить лишь требованием неотрицательности X, то в предположении, что минимум достигается при X > 0, получаем в точке минимума нуль производной по X минимизируемой функции
Дифференцируя F(Y), получаем
и с учетом вышеприведенного выражения имеем F'(Y) = k. Отсюда для точки минимума X=X* имеем
т.е. точка минимума отыскивается решением уравнения
Еcли r > k, то при порядка 1 видим, что X стремится к бесконечности.
Таким образом, оптимальный объем производства совпадает с решением полученного уравнения или равен нулю.
Из приведенного видно, что аналитическое решение для рекуррентных соотношений и функциональных уравнений получить трудно даже в случае простейших исходных функций. Численное решение возможно, но затраты времени будут значительны.
Рассмотрим случай, когда спрос определяется дискретной случайной величиной.
Если обратиться к простейшей задаче управления запасами, которая описывалась рекуррентными соотношениями
Fk(Y)=min{Ck(X)+Hk(Y+X-Sk)+Fk-1(Y+X-Sk)},
то в ситуации, когда Sk принимает значения Sk1, Sk2,..., Skm, c вероятностями Pk1, Pk2,..., Pkm, придется определить Fk(Y) как минимальные ожидаемые затраты производства и хранения в k-шаговом процессе с начальным запасом Y.
Учитывая, что для дискретной случайной величины математическое ожидание равно сумме произведений всех ее возможных значений на соответствующие вероятности, получаем рекуррентные соотношения:
Область минимизации в условиях обязательного покрытия спроса должна учитывать, что
не превышает емкости склада.
Пример. Пусть максимальный объем производства равен 5, емкость склада равна 4, для всех k Hk=1, Ck(X)=13+2X при X>0 и равна 0 при X=0; спрос может быть равен 2 или 4 с равными вероятностями.
Здесь область минимизации определяется условиями 4 Ј Y+X Ј 6 и 0 Ј X Ј 5. Отыскивая
Если в случае детерминированного процесса со спросом 3 для трехшагового процесса с нулевым начальным запасом мы получали оптимальную политику производства по шагам (4, 5, 0), здесь объемы производства несколько выше и равны (5, 4, 1).
Если обратиться к рассмотрению соответствующего бесконечношагового процесса, то функциональное уравнение с учетом дисконтирования имеет вид:
Полагая F(Y)=FY+G/(1-a), где G - средние ожидаемые затраты при оптимальной политике и FY - составляющие затрат, определяемые начальным ресурсом, при a=1 получаем систему функциональных уравнений
где k соответствует Y+X-Si.
Для рассмотренного примера
где область минимизации определяется условиями 0 Ј X Ј 5 и значениями индексов в диапазоне от 0 до 4; в развернутой форме
Если в ранее рассмотренном примере детерминированного процесса оптимальные режимы производства в зависимости от начального запаса были равны (5, 5, 5, 0, 0), то решение этой системы приближением в поведениях дает значения (5, 5, 4, 3, 0).
2.3. Дихотомический выбор (задача о золотодобыче)
Пусть мы настолько состоятельны, что смогли стать обладателями двух золотых приисков А и B с запасами золота соответственно X и Y, но по ряду причин смогли приобрести единственную добывающую машину. При работе на прииске А машина в течение сезона с вероятностью P1 добывает долю R1 имеющегося запаса и с вероятностью 1-P1 ломается навсегда. При работе на прииске B значения вероятностей и доли добычи равны соответственно P2, R2, 1-P2.
Требуется найти оптимальную перестановку машины между приисками, которая максимизирует ожидаемый объем добычи за N сезонов.
Обозначим через Fk(X,Y) максимум математического ожидания суммарного объема добычи за k сезонов при начальных запасах X и Y. Т.к. есть лишь два выбора при установке машины в очередном сезоне, то
Решение полученных рекуррентных соотношений обычным численным методом осложняется двухмерностью искомых функций. На помощь приходит факт, что эти функции обладают свойством однородности F(rX,rY) = rF(X,Y), откуда можно сделать вывод, что оптимальная политика для точки (X,Y) остается оптимальной для всех точек луча из (0,0), проходящего через указанную точку. Следовательно, оптимальная политика определяется соотношением между X и Y.
Если учесть, что при X>>Y оптимальным первым выбором является выбор А, а при Y>>X - выбор B, то легко видеть, что совокупность всех допустимых точек (X,Y) (положительный квадрант плоскости) разбивается на две области оптимального первого выбора .
Возникает вопрос об отыскании граничной линии L, где оба выбора равноценны. При k=1 она определяется элементарно уравнением
P1R1X = P2R2Y. (3)
При k>1 воспользуемся следующими соображениями. Если в точке (X,Y) линии L использовать выбор А, то последующее состояние определяется точкой ((1-R1)X,Y), которая лежит в области первого выбора B. При использовании в точке (X,Y) линии L первого выбора B возникает состояние, определяемое точкой (X, (1-R2)Y), для которой заведомо оптимален первый выбор А.
Следовательно, для точек граничной линии равноценны выборы "AB + оптимальное продолжение" и "BA + оптимальное продолжение" .
Для этих последовательностей выборов находим представления:
Сравнивая оба выражения, получаем искомое уравнение граничной линии при k>1:
P1R1X + P1P2R2Y = P2R2Y + P2P1R1X
или в более изящной форме:
Отсюда возникает простой путь решения. На первом шаге проверяем исходное состояние (точку) на положение относительно граничной линии и запоминаем соответствующий выбор. Отыскиваем координаты очередной точки в соответствии со сделанным выбором и проводим аналогичные действия. На последнем шаге (в оставшемся одношаговом процессе) суждение о выборе определяется линией.
Пример.
Пусть N=5, X=10, Y=20, P1=1/3, P2=1/2, R1=3/4, R2=2/3.
Уравнение граничной линии при k>1 имеет вид
Точка (10, 20) лежит выше граничной линии, что отвечает выбору B. Этот выбор порождает точку (10, (1-2/3)ґ20), т.е. (10, 20/3), принадлежащую области B. Этот выбор, в свою очередь, порождает точку (10,20/9), принадлежащую области А. Выбор А порождает точку (10/4,20/9), лежащую в области B.
В итоге проделанных четырех выборов к последнему шагу возникает точка (10, 20/27), для которой
что соответствует выбору А.
Таким образом, оптимальная последовательность выборов имеет вид {B B A B A}. Что касается значения F5(10, 20), то его можно найти обратным ходом по ранее найденным состояниям:
В случае бесконечношагового процесса соответствующее функциональное уравнение имеет вид:
Аналогичными рассуждениями можно показать, что области A и B первого выбора разделяются линией .
К сожалению, малейшее усложнение задачи многократно увеличивает трудоемкость решения.
Так, если допустить в условиях задачи, что машина выходит из строя не навсегда, а допускает ремонт к следующему сезону.
Здесь при сохранении той же структуры оптимального первого выбора поиск граничной линии нетривиален.
Если обратиться к аналогичной трихотомической задаче
то можно обнаружить, что взаимное положение областей первого выбора может быть различным.
За исключением лишь частных случаев решение такой задачи затруднительно.
2.4. Марковские процессы принятия решений
Пусть некоторая система в любой фиксированный момент t может находиться в одном из n состояний и перейти из этого состояния в любое другое. Пусть вероятность Pt(i,j) перехода в момент t из i-го состояния в j-е не зависит от предыстории системы. Такая система называется марковской.
Обозначив через Xt(i) ожидаемую вероятность того, что в момент t система находится в i -м состоянии, находим ожидаемую вероятность нахождения системы в любом состоянии в любой последующий момент:
Так, если вероятности перехода не зависят от t, определяются матрицей
и в начальный момент система находится в состоянии 1, т.е. X0(1)=1, X0(2)=0, то:
Заметим, что при вероятностях перехода, не зависящих от времени, система обладает свойством стационарности, т.е. функция Xt(j) при t®Ґ асимптотически сходится к функции X(j), удовлетворяющей уравнениям:
Для нашего примера
X(1) = 1/2X(1) + 1/3X(2),
X(2) = 1/2X(1) + 2/3X(2),
откуда с учетом X(1) + X(2) = 1 получаем X(1) = 0.4, X(2)=0.6.
Предположим, что в каждый момент времени выбор вероятностей перехода зависит от некоторой политики (выбора) q и переход сопровождается получением некоторого благоприятного эффекта Rij(q).
Обозначим через Fk(i) ожидаемый эффект функционирования системы, находившейся в начальный момент в i-м состоянии, за k периодов при использовании оптимальной политики. Руководствуясь принципом оптимальности, требующим независимо от начального состояния i и от начального выбора q далее действовать оптимально, т.е. гарантировать максимум ожидаемого эффекта в последующем процессе, приходим к рекуррентным соотношениям вида:

F0(i) = 0, i = 1 . . n.
Для процессов большой длительности использование приведенных рекуррентных соотношений требует существенных затрат времени даже при машинной реализации процесса вычислений. Если учесть, что при независимости значений вероятностей и эффектов от времени процесс обладает свойством стационарности, то в предположении регулярности (возможности прямого или опосредствованного перехода из любого состояния в любое) полагаем для больших k
Fk(i)=Fi+kG, (2)
где G - средний эффект за период и Fi-составляющая суммарного эффекта, определяемая начальным состоянием.
Cистему функциональных уравнений
можно решать приближением в поведениях. Приведенную систему можно получить, если записать уравнение для бесконечношагового процесса с учетом дисконтирования, положить величину дисконтированного эффекта равной Fi + G/(1-a) и принять a=1.
Для иллюстрации марковского процесса принятия решений рассмотрим "задачу о такси" .
Таксист обслуживает окрестности трех городов и может руководствоваться одним из трех выборов: ездить по городу в поисках случайного пассажира, ждать вызова по радио или поехать на стоянку и стать там в очередь.
Для каждого города (i) и каждого выбора (q) известны вероятности поездки в тот или иной город и соответствующие доходы, сведенные в таблице:
Возьмем за начальное поведение q0=(1, 1, 1), т.е. во всех городах придерживаться первого выбора. Для выбранного поведения строим систему n уравнений с n+1 неизвестными
разрешимую с точностью до константы. Для нашего примера:
Полагая, например, F3=0, получаем F1=4/3, F2=7.47 и G = 9.2, т.е. выбранная политика дает средний доход за одну поездку, равный 9.2.
Вычисляем
при всех i и q и найденных значениях Fi:
Выбирая максимальное из значений Ti(q) по q, получаем улучшенное поведение q =(1, 2, 2). Строим и решаем систему уравнений
получая F3=0, F2=-3.88, F1=12.85, G=13.15.
Попытка дальнейшего улучшения дает политику q =(2, 2, 2), для которой F3=0, F2=-1.18, F1=12.86, G=13.34. Очередная попытка улучшения приводит к той же политике, откуда напрашивается вывод о том, что оптимальная политика состоит в использовании второго выбора во всех городах и обеспечивает средний ожидаемый доход за одну поездку, равный 13.34.
Имеется алгоритм, обобщающий рассмотренный выше метод Ховарда приближения в поведениях на случай, когда сеть возможных переходов между состояниями распадается на несколько подсетей, переходы между которыми невозможны .
Практическая часть.
При решении поставленной задачи введем следующую таблицу:
х
у
Запасы
металл
2
5
10000
лист
5
2
10000
доход
30