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

 
 

 

Содержание 

Введение 3

1.Задачи математического моделирования 4

1.1.Виды программирования 4

1.2.Специфика стохастического программирования 6

1.3.Разновидности задач моделирования и подходов к их решению 7

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

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

2.2.Методы решения задач стохастического программирования 13 
2.3.Пути решения задач 15

2.4.Формальная постановка стохастической задачи 17

Заключение 18

Список  литературы 19

 

      Введение 

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

     Математическое  моделирование – это теоретико-экспериментальный метод позновательно-созидательной деятельности, метод исследования и объяснения явлений, процессов и систем (объектов-оригиналов) на основе создания новых объектов – математических моделей.

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

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

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

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

 

      1. Задачи математического моделирования

     1.1. Виды программирования 

     Математическое  программирование, в целом, занимается исследованием нескольких типов  задач: самые простые из них –  детерминированные и одноцелевые.

     К математическому программированию относится:  

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

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

• Геометрическое программирование

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

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

Нас же интересует такой подход к решению задач как стохастическое программирование.

 

      1.2. Специфика стохастического программирования 

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

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

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

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

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

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

        
1.3. Разновидности задач моделирования и подходов к их решению

 

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

     Их можно разделить на:

• принятие решений в условиях определенности - исходные данные - детерминированные;
• принятие решений в условиях неопределенности - исходные данные - случайные величины.

 

     Классификация задач оптимизации

     А по критерию эффективности:

• одноцелевое принятие решений (один критерий эффективности);
• многоцелевое принятие решений (несколько критериев эффективности).

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

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

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

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

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