49170 (Стохастическое программирование)

Федеральное государственное образовательное учреждение среднего профессионального образования

«Омский промышленно-экономический колледж»

КУРСОВАЯ РАБОТА

по дисциплине «Математические методы»

Тема: «Стохастическое программирование»

Выполнил:

Коркунов Илья Андреевич

3 курс, БП 1 - 117

Руководитель:

Белгородцева Наталья Александровна

Оценка:________________

Дата защиты:___________

2010

Содержание

Введение

Обзор литературы

1. Понятие о стохастическом программировании

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

3. Решение задач СТП

Заключение

Список используемой литературы

Введение

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

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

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

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

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

Обзор литературы

При написании курсовой работы мною были использованы следующие источники:

Введение было написано с использованием сайта: http://ru.wikipedia.org/wiki/ Стохастическое программирование. Я взял информацию с этого сайта, потому что она была изложена в этой статье, раскрыто и доходчиво.

Для раскрытия первого вопроса из темы курсовой работы “ Понятие о стохастическом программировании ” практически вся информация взята с книги «Математические методы и модели для менеджмента» / Глухов В.В., здесь были рассмотрены основные понятия, взяты определения такие как: какие задачи относятся к задачам стохастического программирования, суть стохастической М-постановки целевой функции. Так же информация была дополнена с книги «Математические методы в программировании» / Агальцов В.П. В книге Глухова «Математические методы и модели для менеджмента» была очень доступно изложена информация и потому я её и использовал. Информация про «Детерминированная постановка задач стохастического программирования» была взята с сайта http://matesha.ru/book/lp8.php, там был описан алгоритм этого вопроса, но очень понятно.

При рассмотрении вопроса «Решение задач СТП» так же была использована книга «Математические методы и модели для менеджмента» / Глухов В.В. Так же была использована книга «Исследование операций в экономике»:

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

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

1. Понятие о стохастическом программировании

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

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

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

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

В задаче линейного программирования:

1.1

заданные величины сj, аij,,bi, dj, Dj. Часто на практике величины cj, aij bj, могут быть случайными. Так, если bi — ресурс, то он зависит от ряда факторов. Аналогично, сj — цены — будут зависеть от спроса и предложения, aij — расходные коэффициенты — от уровня техники и технологии. Задачи, в которых сj, аij,,bi — случайные величины, относят к задачам стохастического программирования. Переход от чистых стратегий к смешанным расширяет область определения задачи. Достижимый максимум целевой функции может при этом только увеличиться, а достижимый минимум — только уменьшиться. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи.

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

Стохастическая постановка целевой функции может быть двух видов: М-постановка и Р-постановка.

При М-постановке случайная величина заменяется ее математическим ожиданием и задача сводится к оптимизации детерминированной целевой функции:

1.2

г де сj — математическое ожидание случайной величины сj.

При Р-постановке целевая функция будет иметь вид:

• при максимизации целевой функции:

1.3

обозначает максимизацию вероятности того, что случайная величина ∑ cj xj будет не меньше некоторого значения r;

• при минимизации целевой функции:

1.4

обозначает максимизацию вероятности того, что случайная величина ∑ cj xj будет не больше некоторого значения r.

Наиболее распространены СТП-постановки в вероятностных ограничениях вида:

1.5

где аi j , bi — случайные величины; ai — заданные уровни вероятности.

Так, ограничение (а) означает, что вероятность соблюдения неравенства

1.6

должна быть не меньше, чем ai. Аналогичный смысл и других ограничений.

Для случая, когда вероятностные ограничения представлены в виде типа (а), задачу СТП можно записать при М-постановке:

1.7

При Р-постановке:

• в случае максимизации целевой функции

1.8

• в случае минимизации целевой функции

1.9

где cj , ai j , bi — случайные величины.

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

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

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

программирования

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

Для решения задачи стохастического программирования в Р-постановке и с вероятностными ограничениями переходят к детерминированному эквиваленту.

Для целевой функции детерминированный эквивалент имеет вид:

• при минимизации целевой функции

2.1

• при максимизации целевой функции

2.2

где σ2j — дисперсия случайной величины сj Решение таких задач затруднительно, поэтому далее рассматриваем целевая функция только в М- постановке. Детерминированный эквивалент вероятностного ограничения типа (а)

2.3

может быть сведен к виду:

2.4