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

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

     Или другой пример:

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

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

     Но  дело в том, что время ожидания врача отдельными больными не суммируется: слишком долгое ожидание одного из них не компенсируется почти мгновенным обслуживанием другого. Чтобы избежать таких неприятностей, можно дополнить показатель эффективности добавочными требованиями, чтобы фактическое время ожидания врача было не больше какого предельного значения f₀. Поскольку время ожидания величина случайная, нельзя просто потребовать, чтобы выполнялось условие F≤ f₀, но можно потребовать, чтобы это условие выполнялось с большой вероятностью, настолько большой, чтобы событие F≤ f₀ было практически достоверным. Пусть k=0,995 и потребуем, чтобы вероятность P(F≤ f₀ ) ≥ k.

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

     Особенно  осторожными надо быть с "оптимизацией в среднем", когда речь идет об единичной операции.

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

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

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

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

     Оптимальное решение (от лат. оptimum – «наилучшее») – наилучший среди возможных вариант решения поставленной задачи. Следует помнить, однако, что оптимальность любого решения носит относительный характер: данное решение будет наилучшим, но с точки зрения того набора ограничений, который лежит в основе формулировки рассматриваемой задачи. Оптимальность, при этом, означает экстремальное (минимальное или максимальное) значение критериального показателя (суммы показателей), относительно которого оценивается полученный вариант решения.

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

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

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

     Случайное явление – такое явление, которое  при неоднократном воспроизведении одного и того же опыта протекает каждый раз несколько по иному.

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

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

     Для решения  задач стохастического  программирования обычно надо знать  статистические характеристики исследуемой  системы – ее математическое ожидание,  дисперсию, среднее квадратическое отклонение, коэффициент вариации, закон ее распределения, представляемый в двух формах: плотность данного распределения (f(x)) и функцию распределения (F(x)). Плотность распределения случайной величины f(x) показывает вероятность появления каждого конкретного значения случайной величины, а интегральная функция F(x) – дает возможность определить вероятность появления случайной величины х≤а, скажем валовой региональный продукт меньше или равный конкретному значению.

     Нелинейные  стохастические задачи обычно решаются в М-постановке или в Р-постановке.

     М-постановка – максимизация (минимизация) среднего значения целевой функции, а Р-постановка – максимизация вероятности получения  максимального (минимального) значения целевой функции.

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

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

     2. Задачи стохастического программирования

     2.1. Подходы к моделированию задач 

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

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

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

     К анализу многоэтапных задач стохастического  программирования сводятся формальные исследования численных методов планирования производства и развития экономической системы. 

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

     Как и в любой задаче, основным её этапом является постановка задачи. На этапе постановки задачи необходимо:

• описать задачу,
• определить цели моделирования,
• проанализировать объект или процесс.

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

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

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

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

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