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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 06.05.2012. Сдан: 2011. Страниц: 7. Уникальность по antiplagiat.ru: < 30%

Описание (план):


 
 
 

Содержание 

Введение 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. Виды программирования 

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

    Линейное  программирование: состоит в нахождении экстремального значения линейной функции многих переменных при наличии линейных ограничений, связывающих эти переменные;
    Нелинейное программирование: целевая функция и ограничения могут быть нелинейными функциями;
    Особым случаем в задачах линейного и нелинейного программирования является случай, когда на оптимальные решения накладывается условие целочисленности. Такие задачи относятся к целочисленному программированию;
    Динамическое программирование: для отыскания оптимального решения планируемая операция разбивается на ряд шагов (этапов) и планирование осуществляется последовательно от этапа к этапу. Однако выбор метода решения на каждом этапе производится с учетом интересов операции в целом;
    Теория графов: с помощью теории графов решаются многие сетевые задачи, связанные с минимальным протяжением сети, построение кольцевого маршрута и т.д.
    Стохастическое линейное программирование
Бывает  много практических ситуаций, когда  коэффициенты ci целевой функции, коэффициенты aij в матрице коэффициентов, коэффициенты ограничений bi - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью. Приходится менять постановку самих задач с учётом этих эффектов и разрабатывать совершенно новые методы их решения. Соответствующий раздел получил название стохастического программирования.
    Геометрическое программирование
Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области. Такие задачи встречаются в задачах раскроя материала для производства каких-то изделий и т.п. Это - еще недостаточно разработанная область математического программирования и имеющиеся здесь алгоритмы в основном ориентированы на сокращение перебора вариантов с поиском локальных минимумов.
    Задачами теории массового обслуживания является анализ и исследование явлений, возникающих в системах обслуживания. Одна из основных задач теории заключается в определении таких характеристик системы, которые обеспечивают заданное качество функционирования, например, минимум времени ожидания, минимум средней длины очереди.
    Теория игр пытается математически объяснить явления возникающие в конфликтных ситуациях, в условиях столкновения сторон. Такие ситуации изучаются психологией, политологией, социологией, экономикой.
Нас же интересует такой подход к решению задач как стохастическое программирование.
 

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

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

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

 
     Модели  принятия оптимальных решений отличаются универсальностью. Их можно классифицировать как задачи минимизации (максимизации) критерия эффективности, компоненты которого удовлетворяют системе ограничений (равенств и/или) неравенств.
     Их можно разделить на:
    принятие решений в условиях определенности - исходные данные - детерминированные;
    принятие решений в условиях неопределенности - исходные данные - случайные величины.
 
     Классификация задач оптимизации
Исходные  данные Переменные Зависимости Задача
Детерминированные Непрерывные Линейные Линейного программирования
Целочисленные Линейные Целочисленного  программирования
Непрерывные, целочисленные Нелинейные Нелинейного программирования
Случайные Непрерывные Линейные Стохастическое  программирование
     А по критерию эффективности:
    одноцелевое принятие решений (один критерий эффективности);
    многоцелевое принятие решений (несколько критериев эффективности).
     Для того, чтобы принимать решение  в условиях неопределенности, необходимо знать каков вид этой неопределенности. По этому признаку можно различать стохастическую (вероятностную) неопределенность, когда неизвестные факторы статистически устойчивы и поэтому представляют собой обычные объекты теории вероятностей - случайные величины (или случайные функции, события и т.д.). При этом должны быть известны или определены при постановке задачи все необходимые статистические характеристики (законы распределения и их параметры).
     В стохастических задачах неизвестные факторы представляют собой случайные величины с какими-то в принципе известными, вероятностными характеристиками - законами распределения, математическими ожиданиями, дисперсиями. Тогда критерий эффективности, зависящий от этих факторов, тоже будет величиной случайной. Максимизировать или минимизировать случайную величину невозможно: при любом решении она остается случайной, неконтролируемой.
     Возникает вопрос, нельзя ли заменить случайные  факторы их средними значениями (математическими  ожиданиями). Тогда задача становится детерминированной и может быть решена обычными методами. Понятно, что решение этого вопроса зависит от того, насколько случайны эти факторы, как мало они откланяются от своих математических ожиданий.
     Приведем  примеры. Например, если мы составляем план снабжения группы предприятий  сырьем, то можно в первом приближении  пренебречь, скажем, случайностью фактической производительности источников сырья (если их производство хорошо налажено). Но, если, например, планируется работа ремонтной мастерской, обслуживающей автобазу, то пренебречь случайностью момента появления неисправностей и случайностью времени выполнения ремонта невозможно.
     В случаях, когда критерий эффективности  остается случайной величиной, можно  в качестве критерия эффективности  взять его среднее значение (математическое ожидание) и выбрать такое решение, при котором этот усредненный  показатель обращается в максимум (минимум). Очень часто именно так и поступают, выбирая в качестве критерия эффективности в задачах, содержащих определенность, не просто доход, а средний доход, не просто время, а среднее время.
     Применение "оптимизации в среднем" дает хорошие результаты, когда речь идет ряде длинных однородных операций, тогда "минусы" в одном случае покрываются "плюсами" в другом. Но возможны случаи, когда такая оптимизация не дает нужного эффекта.
     Или другой пример:
     Организуется  автоматизированная система управления для службы неотложной медицинской помощи большого города. Вызовы, возникающие в разных районах города в случайные моменты, поступают на центральный пульт управления, откуда они передаются на тот или другой пункт неотложной помощи. Требуется разработать такое правило (алгоритм) диспетчерской работы, при котором служба в целом будет функционировать эффективно.
     Прежде  всего нужно выбрать показатель эффективности F. Разумеется, желательно, чтобы время ожидания врача было минимальным. Но время величина случайная и если применить "оптимизацию в среднем", то надо выбрать тот алгоритм, при котором время ожидания минимально.
     Но  дело в том, что время ожидания врача отдельными больными не суммируется: слишком долгое ожидание одного из них не компенсируется почти мгновенным обслуживанием другого. Чтобы избежать таких неприятностей, можно дополнить показатель эффективности добавочными требованиями, чтобы фактическое время ожидания врача было не больше какого предельного значения f0. Поскольку время ожидания величина случайная, нельзя просто потребовать, чтобы выполнялось условие F? f0, но можно потребовать, чтобы это условие выполнялось с большой вероятностью, настолько большой, чтобы событие F? f0 было практически достоверным. Пусть k=0,995 и потребуем, чтобы вероятность P(F? f0 ) ? k.
     Введение  такого ограничения означает, что  из области допустимых решений, исключаются  решения эму не удовлетворяющие. Ограничения такого типа называются стохастическим ограничениями.
     Особенно  осторожными надо быть с "оптимизацией в среднем", когда речь идет об единичной операции.
     Кроме рассмотренных выше, бывают задачи, когда неизвестные факторы не могут быть изучены и описаны  статистическими методами. Это бывает в двух случаях:
    распределение вероятностей для параметров в принципе существует, но к моменту принятия решения не может быть получено;
    распределение вероятностей для параметров вообще не существует.
 
     Наиболее  широко применяются и хорошо изучены  двухэтапные линейные модели стохастического  программирования. Здесь лицо, принимающее решение, предпринимает некоторое действие на первом этапе, после которого происходит случайное событие, оказывающее влияние на результат решения первого этапа. На втором этапе может тогда быть принято корректирующее решение, которое компенсирует любые нежелательные эффекты в результате решения первого этапа.
     Оптимальным решением такой модели является единственное решение первого этапа и множество  корректирующих решений (решающих правил), определяющих, какое действие должно быть предпринято на втором этапе в ответ на каждый случайный результат.
     Оптимальное решение (от лат. оptimum – «наилучшее») – наилучший среди возможных вариант решения поставленной задачи. Следует помнить, однако, что оптимальность любого решения носит относительный характер: данное решение будет наилучшим, но с точки зрения того набора ограничений, который лежит в основе формулировки рассматриваемой задачи. Оптимальность, при этом, означает экстремальное (минимальное или максимальное) значение критериального показателя (суммы показателей), относительно которого оценивается полученный вариант решения.
     Лицо, принимающее решение, должно совершенно точно представлять, в чем состоит оптимальность решения, по какому критерию осуществляется оптимизация. В свою очередь, с помощью целевой функции оптимизации может производиться оценка как желательных, так и нежелательных последствий принимаемых решений.
     В общем виде процесс выработки  оптимального решения прост: определить существо проблемы и поставить цель;  установить относящиеся к делу факты, ограничения и зависимости; в пределах наложенных ограничений собрать как можно больше необходимых данных; провести анализ этих данных; выявить альтернативные решения и оценить их в терминах вреда и пользы; выбрать оптимальное решение.
     При решении детерминированных задач линейного программирования полагается, что все закладываемые величины, например, трудовые ресурсы, сырье, финансы, прибыль являются детерминированными, и нам известны их точные значения. На практике же часто точные значения отмеченных величин отсутствуют, так как по существу эти величины являются случайными.
     Случайное явление – такое явление, которое  при неоднократном воспроизведении одного и того же опыта протекает каждый раз несколько по иному.
     То  есть, случайная величина может принимать то или иное значение, причем заранее неизвестно, какое конкретно. Примером случайной величины может служить любой экономический или политический показатель, например, валовой региональный продукт следующего года, число избирателей, которое прибудет на избирательный участок и так далее. Для решения подобного класса задач разработаны методы стохастического программирования.
     К сожалению,  универсальных методов решения задач стохастического программирования, подходящих для всех классов задач не существует, но, тем не менее, эти задачи успешно решаются с помощью современных статистическо-вероятностных технологий.
     Для решения  задач стохастического  программирования обычно надо знать  статистические характеристики исследуемой  системы – ее математическое ожидание,  дисперсию, среднее квадратическое отклонение, коэффициент вариации, закон ее распределения, представляемый в двух формах: плотность данного распределения (f(x)) и функцию распределения (F(x)). Плотность распределения случайной величины f(x) показывает вероятность появления каждого конкретного значения случайной величины, а интегральная функция F(x) – дает возможность определить вероятность появления случайной величины х?а, скажем валовой региональный продукт меньше или равный конкретному значению.
     Нелинейные  стохастические задачи обычно решаются в М-постановке или в Р-постановке.
     М-постановка – максимизация (минимизация) среднего значения целевой функции, а Р-постановка – максимизация вероятности получения  максимального (минимального) значения целевой функции.
     Роль  стохастических моделей и методов  в исследовании закономерностей  поведения экономических систем и в разработке количественных методов  планирования экономики и управления производством имеет два аспекта  — методологический и вычислительный. И тот и другой связаны с одной из важнейших категорий современной математической логики — с понятием сложности, точнее, с понятиями «сложность алгоритма», «сложность вычислений» и «сложность развития». 
Роль вычислительного аспекта проблемы определяется тем, что планирование, управление и проектирование происходят, как правило, в условиях неполной информации. Рыночная конъюнктура, спрос на продукцию, изменения в состоянии оборудования не могут быть точно предсказаны. В условиях конкурентной экономики дополнительно возникает направленная дезинформация.

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

 

     
     2. Задачи стохастического программирования
     2.1. Подходы к моделированию задач 

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

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

 

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

     Как и в любой задаче, основным её этапом является постановка задачи. На этапе постановки задачи необходимо:
    описать задачу,
    определить цели моделирования,
    проанализировать объект или процесс.
     Постановки  задач стохастического программирования существенным образом зависят от целевых установок и информационной структуры задачи.
     Основные  классы задач, для решения которых  создается вычислительный комплекс, непосредственно или методами стохастического  расширения формулируются как модели стохастического программирования.
     Существует  два типа задач. В задачах первого типа прогнозируются статистические характеристики поведения множества идентичных экстремальных систем. Модели второго типа предназначены для построения методов и алгоритмов планирования и управления в условиях неполной информации.
     Соответствие  формально построенных стохастических моделей содержательным постановкам—решающее условие успешного управления в  условиях неполной информации. Вряд ли могут быть приведены универсальные  рекомендации по выбору информационной структуры модели и статистических характеристик, используемых для формирования целевого функционала задачи и области его определения.
     Анализ  опыта решения практических экстремальных  задач методами математического  программирования свидетельствует  о серьезных успехах этого подхода (и о внедрении данных методов в практику планирования, управления и проектирования) в задачах относительно простой структуры, главным образом одно экстремальных, при не слишком большой размерности задачи, когда число переменных и ограничений (в моделях достаточно общего вида) не превышает сотен или тысяч. Однако методы детерминированного математического программирования не прививаются в системах большой сложности, отвечающих многоэкстремальным задачам или задачам большой размерности.
     До  сих пор нет достаточно конструктивного метода решения общей (даже линейной) двухэтапной задачи стохастического программирования. Стандартные методы выпуклого программирования в общем случае неприменимы для вычисления предварительного плана — решения выпуклой задачи первого этапа.
     Это подсказывает путь алгоритмизации решения  сложных задач в автоматизированных системах управления—замену трудоемких процедур, которые отвечают обоснованным (точным или приближенным) методам решения детерминированных экстремальных задач, относительно простыми «законами управления»—решающими правилами или решающими распределениями стохастического расширения соответствующих задач. 
Платой за упрощение задачи и за переход от громоздких алгоритмов к относительно простым решающим механизмам служат трудоемкая предварительная работа по построению «законов управления» и некоторая потеря эффективности решения задачи в каждом отдельном случае. 
В литературе по стохастическому программированию описаны многочисленные модели выбора решений, сформулированные в терминах стохастического программирования. Разнообразные задачи управления запасами—классические примеры стохастических моделей. Синтез систем массового обслуживания, удовлетворяющих заданным требованиям и оптимизирующих пропускную способность системы или определяемый ею доход, сводится к решению экстремальных стохастических задач.

и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.