Модели динамического программирования

 

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

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

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

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

Типичными областями применения моделей динамического программирования при принятии решений являются:

• Разработка правил управления запасами, устанавливающих момент пополнения запасов и размер пополняющего заказа.

• Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию.

• Определение необходимого объема запасных частей, гарантирующего эффективное использование дорогостоящего оборудования.

• Распределение дефицитных капитальных вложений между возможными новыми направлениями их использования.

• Выбор методов проведения рекламной кампании, знакомящей покупателя с продукцией фирмы.

• Систематизация методов поиска ценного вида ресурсов.

• Составление календарных планов текущего и капитального ремонта сложного оборудования.

• Разработка долгосрочных правил замены выбывающих из эксплуатации основных фондов.

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

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

 

Модели сетевого планирования.

 

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

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

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

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

 

 

Теория вероятностей.

 

Теория вероятностей предлагает пути уменьшения неопределенности, именно поэтому важно ею овладеть. Начало теории вероятностей было положено в середине XVII века, когда французские математики Блез Паскаль и Пьер Ферма по заказу известных игроков в азартные игры разработали математическую модель, описывающую вероятность исходов в играх, зависящих от случая. При игре в "кости", рулетку, как и при опросах, исследованиях (физических, экономических, социологических и т.д.), результаты меняются от раза к разу даже при сохранении неизменных условий.

Деловые люди принимают решения в таких же условиях. Специалист по маркетингу никогда не сможет точно предсказать объемы реализации нового товара. Так же, как, заключая пари, невозможно предвидеть, выиграешь или проиграешь. И в том, и в другом случае присутствует неопределенность.

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

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

Эксперимент - один или несколько опытов. Например, бросание монеты 7раз.

Исход - возможный результат эксперимента.

Вероятность - числовая характеристика степени возможности появления какого-либо случайного события при тех или иных определенных, могущих повторяться неограниченное число раз условиях.

В качестве иллюстрации рассмотрим бросание монеты. Существует два возможных исхода - "орел" и "решка". С какой вероятностью будет выпадать "решка"? Бросим монету 10 раз, а результаты запишем. А потом увеличим число экспериментов до 100, 1000 и так далее. В каждом эксперименте будем определять отношение интересующих нас событий к общему числу опытов в эксперименте.

Так в каждом эксперименте будет определяться частота появления того или иного события (например, появления "орла"). Возможные результаты могут быть таковы. По мере увеличения числа бросков выявляется стремление частоты появления "орлов" к определенной величине. В данном примере их доля - 0,643 при точности трех знаков после запятой.

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

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

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

1.Числовое значение вероятности находится в интервале от 0 до 1, включая концы интервала, то есть 0 < р < 1.

2.Сумма вероятностей всех возможных исходов эксперимента (вероятность полной группы событий) равна 1, то есть Zp = 1. Полную группу событий, например, образуют все опыты по бросанию монеты, включающие выпадение как "орла", так и "решки" (строго говоря, также и падение монеты "на ребро", что, впрочем, практически невероятно).

Таким образом, значение вероятности, приближающееся к 1, свидетельствует о большей определенности рассматриваемого события (значение р = 1 соответствует достоверному событию, например, вероятность того, что день сменит ночь). И наоборот - уменьшающееся к нулю значение вероятности сигнализирует об увеличении неопределенности события (значение р = 0 соответствует невозможному событию, например, вероятность, того, что подброшенный на Земле камень упадет на Солнце).

 

Модели теории игр.

 

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

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

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

Эти задачи и составляют проблематику теории игр, поскольку упрощенная математическая модель конфликтной ситуации представляет собой игру. Основные научные разработки теории игр связывают с именем американского математика Джона фон Неймана (1903 - 1957) и его книгой "Теория игр и экономическое поведение". Игра может быть определена следующим образом:

1.Имеется n конфликтующих сторон (лиц), принимающих решения, интересы которых не совпадают.

2.Заданы правила, определяющие набор допустимых стратегий, известные игрокам.

3.Существует точно определенный набор конечных состояний, которыми заканчивается игра (например, выигрыш, ничья, проигрыш).

4.3аранее определены и известны всем игрокам платежи, соответствующие каждому возможному конечному состоянию.

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

Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, в противном случае она называется игрой с ненулевой суммой. Примером игры с ненулевой суммой является карточная игра с участием "банкира", т.е. лица, которое держит банк и забирает часть выигрыша себе. В играх с нулевой суммой для полного задания игры достаточно указать выигрыш одного из игроков. Если обозначить а – выигрыш одного из игроков, b - выигрыш другого, то для игры с нулевой суммой b == - а, поэтому достаточно рассматривать, например, а.

Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход - это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход - это случайно выбранное действие (например, выбор карты из перетасованной колоды).

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

Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуацию). Это означает, что игрок выбрал определенную стратегию, которая может быть задана в виде списка правил или программы для компьютера. Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае.

Для того чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, то есть один из игроков должен получить максимальный выигрыш, когда второй игрок придерживается своей стратегии. В то же время, второй игрок должен иметь минимальный проигрыш, если первый игрок придерживается своей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны также удовлетворять условию устойчивости, то есть любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре.

Если игра повторяется достаточно много раз, то игроков может интересовать не выигрыш или проигрыш в каждой конкретной игре, а средний выигрыш (проигрыш) во всех партиях.

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

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