Курсовая работа: Стохастическое программирование
В задачах прикладной математики можно различать детерминированные и стохастические задачи. В процессе решения последних развилась обширная в настоящее время математическая дисциплина — теория вероятностей.
Вместе с тем вероятностные методы по существу применялись до сих пор исключительно к решению задач дескриптивного типа Оптимизационные стохастические задачи начали разрабатываться только в последнее десятилетие. Сказанное относится и к стохастическим вариантам задач оптимального программирования.
Тем не менее, стохастическое оптимальное программирование является весьма важной и перспективной ветвью прикладной математики уже хотя бы потому, что «на практике принятие решений всегда происходит в условиях той или иной неопределенности. Ясно также, что задачи стохастического программирования оказываются существенно сложнее соответствующих детермированных вариантов.
В задаче линейного программирования:
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