Читайте также:
|
Целочисленное программирование — разновидность математического программирования, подразумевающая, что искомые значения должны быть целыми числами.
Целочисленное программирование – один из наиболее молодых, перспективных и быстро развивающихся разделов математического программирования. Можно перечислить большое количество разнообразных задач планирования экономики, организации производства, исследования конфликтных ситуаций, синтеза схем автоматического регулирования, которые формально сводятся к выбору лучших, в некотором смысле, значений параметров из определенной дискретной совокупности заданных величин. К ним можно отнести и экстремальные комбинаторные задачи, возникающие в различных разделах дискретной математики.
Целочисленные задачи математического программирования могут возникать различными путями.
1. Существуют ЗЛП, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач – транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).
2. Толчком к изучению целочисленных задач в собственном смысле слова явилось рассмотрение ЗЛП, в которых переменные представляли физически неделимые величины. Они были названы задачами с неделимостью. Таковы, например, задачи об оптимизации комплекса средств доставки грузов, о нахождении минимального порожнего пробега автомобилей при выполнении заданного плана перевозок.
3. Другим важным толчком к построению теории целочисленного программирования стал новый подход к некоторым экстремальным комбинаторным задачам. В них требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями
50. Динамическое программирование. Принцип оптимальности Беллмона.
Динамическое программирование – математический метод оптимизации, суть которого состоит в отыскании оптимального решения путем выполнения вычислений в несколько этапов (шагов).
Принцип Оптимальности: Каким бы не было состояние системы S, перед очередным этапом, надо выбирать управление на этом этапе так, что бы выигрыш на данной шаге плюс оптимальный выигрыш на всех последующих шагах был max.
Принцип решения ДП:
1. Выбрать параметры, характеризующие состояние системы S, перед каждым шагом.
2. Расчленить операцию на этапы (шаги)
3. Выяснить набор шаговых управлений x1 для каждого шага и налагаемые на них ограничения.
4. Определить какой выигрыш приносит на i-шаге управление xi, записать функцию выигрыша.
5. Определить, как изменяется состояние под влиянием управления xi, на i-шаге.
6. Записать основное рекуррентное уравнение ДП, выражающее условный оптимальный выигрыш (начиная с i-шага и до конца)
7. Произвести условнуюоптимизацию последнего m-шага.
8. Произвести условную оптимизацию m-1, m-2 шагов, для каждого указать условное оптимальное управление
9. Произвести безусловную оптимизацию управления. Взять оптимальное управление на Первом шаге изменить состояние системы для вновь найденного состояния и так до конца.
51. Имитационное моделирование. Метод Монте-Карло, область применения
Имитационное моделирование — это метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему и с ней проводятся эксперименты с целью получения информации об этой системе. Экспериментирование с моделью называют имитацией (имитация — это постижение сути явления, не прибегая к экспериментам на реальном объекте). Выделяют следующие основные классы имитационных моделей:
1.Непрерывные
2.Дискретные
3.Пространственные
В случае непрерывных моделей предметная область описывается совокупностью динамических связей, отражающих развитие процесса во времени в форме реккурентных соотношений.
Модель воспроизводит поведение объекта за определенный период времени. В этом смысле имитационная модель является динамической, значение всех переменных входящих в имитационную модель вычисляются в каждый момент модельного времени. Затем через определенный интервал на основе старых значений вычисляются новые значения переменных.
Дискретный тип модели описывает потоки случайных событий, проходящих через сложную совокупность путей и узлов, направлен на исследование стационарных установившихся процессов.
В случае пространственных моделей рассматриваются процессы, происходящие в пространстве на плоскости или в объеме
ДЛЯ ПОСТРОЕНИЯ ИМИТАЦИОННЫХ МОДЕЛЕЙ используются переменные типов – фонд (объем искомого продукта, оценка некоторых вероятностей), поток (объем количества продукта который поступает или извлекается из соответствующего фонда в единицу модельного времени), время, конвертор
Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а: М(Х)=а.
Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое и принимают x в качестве оценки (приближённого значения) a* искомого числа a:
Поскольку метод Монте-Карло требует проведения большого числа испытаний, его часто называют методом статистических испытаний. Теория этого метода указывает, как наиболее целесообразно выбрать случайную величину Х, как найти её возможные значения. В частности, разрабатываются способы уменьшения дисперсии используемых случайных величин, в результате чего уменьшается ошибка, допускаемая при замене искомого математического ожидания а его оценкой а*.
52. Метод Монте-Карло. Сущность, оценка погрешности,область применения.
Оценка погрешности метода Монте-Карло.
Пусть для получения оценки a* математического ожидания а случайной величины Х было произведено n независимых испытаний (разыграно n возможных значений Х) и по ним была найдена выборочная средняя, которая принята в качестве искомой оценки:. Ясно, что если повторить опыт, то будут получены другие возможные значения Х, следовательно, другая средняя, а значит, и другая оценка a*. Уже отсюда следует, что получить точную оценку математического ожидания невозможно. Естественно возникает вопрос о величине допускаемой ошибки. Ограничимся отысканием лишь верхней границы d допускаемой ошибки с заданной вероятностью (надёжностью) g:.
Интересующая нас верхняя грань ошибки d есть не что иное, как «точность оценки» математического ожидания по выборочной средней при помощи доверительных интервалов. Рассмотрим следующие три случая.
1. Случайная величина Х распределена нормально и её среднее
квадратичное отклонение d известно.
В этом случае с надёжностью g верхняя граница ошибки, (*)
где n число испытаний (разыгранных значений Х); t – значение аргумента функции Лапласа, при котором, s - известное среднее квадратичное отклонение Х.
2. Случайная величина Х распределена нормально, причём её среднее квадратическое отклонение s неизвестно.
В этом случае с надёжностью g верхняя граница ошибки
, (**)
где n – число испытаний; s – «исправленное» среднее квадратическое отклонение, находят по таблице приложения 3.
3. Случайная величина Х распределена по закону, отличному от нормального.
В этом случае при достаточно большом числе испытаний (n>30) с надёжностью, приближённо равной g, верхняя граница ошибки может быть вычислена по формуле (*), если среднее квадратическое отклонение s случайной величины Х известно; если же s неизвестно, то можно подставить в формулу (*) его оценку s – «исправленное» среднее квадратическое отклонение либо воспользоваться формулой (**). Заметим, что чем больше n, тем меньше различие между результатами, которые дают обе формулы. Это объясняется тем, что при распределение Стьюдента стремится к нормальному.
Из изложенного следует, что метод Монте-Карло тесно связан с задачами теории вероятностей, математической статистики и вычислительной математики. В связи с задачей моделирования случайных величин (в особенности равномерно распределённых) существенную роль играют также методы теории чисел.
Дата добавления: 2015-04-11; просмотров: 90 | Поможем написать вашу работу | Нарушение авторских прав |