Принятие решений на основе метода Монте-Карло
Автор работы: Пользователь скрыл имя, 15 Июля 2013 в 16:26, лабораторная работа
Описание работы
Целью работы является изучение эффективности применения метода Монте-Карло для поддержки принятия решений в производственно-экономических задачах. Метод Монте-Карло представляет собой универсальный метод,
применяемый для приближенного решения задач самых различных классов: вероятностных и детерминированных, дискретных и непрерывных, задач моделирования и оптимизации и т.д.
Содержание работы
1. Краткие теоретические сведения
Задание
Варианты полиномов
Файлы: 1 файл
Базы знаний и поддержка принятия решений в САПР
Лабораторная работа №1
ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ МЕТОДА МОНТЕ-КАРЛО
Целью работы является изучение эффективности применения метода Монте-
Карло для поддержки принятия решений в производственно-экономических
задачах.
1. Краткие теоретические сведения
Метод Монте-Карло представляет собой универсальный метод,
применяемый для приближенного решения задач самых различных классов:
вероятностных и детерминированных, дискретных и непрерывных, задач
моделирования и оптимизации и т.д.
Вероятностные задачи – это любые задачи, связанные с анализом
случайных
явлений
(случайных
событий,
величин,
процессов).
Детерминированные задачи – это задачи, в постановке которых нет никаких
случайных факторов.
Дискретные задачи – это задачи, в которых все анализируемые величины
могут принимать значения только из некоторого конечного множества
допустимых значений. Непрерывные задачи – это задачи, в которых
анализируемые величины могут принимать любые значения из некоторого
диапазона (этот диапазон может быть как ограниченным, так и
неограниченным).
Задачи моделирования – это задачи, связанные с имитацией некоторого
объекта (например, сложной технической системы) или явления (например,
процесса развития отрасли) с целью определения его характеристик. Задачи
оптимизации – это задачи, в которых требуется выбор лучшего из нескольких
возможных вариантов решения.
Большинство практических задач не могут быть однозначно отнесены к
одному из приведенных выше классов, а содержат элементы, характерные для
нескольких из этих классов.
В данной работе основное внимание уделяется применению метода
Монте-Карло для решения детерминированных задач поддержки принятия
решений. Решение данных задач методом Монте-Карло основано на
многократном случайном выборе вариантов решений и их сравнении. При
достаточном количестве испытаний (т.е. вариантов решения, выбранных
случайным образом) находится решение, близкое к оптимальному (во многих
случаях находится оптимальное решение).
Метод Монте-Карло основан на применении псевдослучайных
равномерно распределенных чисел (ПСЧ). Расчет (розыгрыш) ПСЧ
выполняется
по
специальным
алгоритмам, позволяющим
получать
бесконечную последовательность таких чисел. Эти алгоритмы разработаны
таким образом, что ПСЧ всегда принимают значения из диапазона от нуля до
единицы. При этом ПСЧ обладают следующими свойствами:
-равномерность: ПСЧ могут принимать значения из любой части
диапазона (0;1) с одинаковой частотой;
-случайность:
в
последовательности
ПСЧ
нет
какой-либо
закономерности;
-независимость: любое из значений ПСЧ не зависит от предыдущих ПСЧ.
Все это позволяет рассматривать ПСЧ как случайные величины,
распределенные по равномерному закону в диапазоне от нуля до единицы.
Алгоритмы для получения ПСЧ реализованы практически во всех языках
программирования и во многих прикладных программах обработки данных.
Например, в языке Паскаль для получения ПСЧ используется функция
RANDOM, в табличном процессоре EXCEL – функция СЛЧИС. Одна из
возможных реализаций ПСЧ приведена в приложении. ПСЧ применяются для
многократного случайного выбора вариантов решения задачи. Из этих
вариантов выбирается лучший. Чтобы найти вариант решения, достаточно
близкий к оптимальному, обычно требуется выбрать много вариантов решения
(от нескольких десятков до тысяч). Поэтому применение метода Монте-Карло
возможно только с использованием программных средств.
Во многих случаях данные задачи могут быть решены другими
(аналитическими) методами, позволяющими найти точное оптимальное
решение. Это могут быть методы линейного программирования, динамического
программирования, поиска экстремумов функций многих переменных и т.д.
Однако применение точных аналитических методов, как правило, возможно
только для задач небольшой размерности (с небольшим количеством
ограничений, переменных и т.д.). Для реальных задач применение
аналитических методов нередко оказывается невозможным из-за большого
объема сложных вычислений. Реализация и применение таких методов (даже с
использованием компьютера) оказывается пpактически невозможным или
нецелесообразным. Поэтому во многих случаях применение метода Монте-
Карло может оказаться единственно возможным способом решения задачи.
Алгоритм поиска решения на основе метода Монте-Карло полностью зависит
от конкретной задачи.
Рассмотрим пример. На предприятие поступает некоторое сырье для
переработки. Известно, что примерно 15% партий сырья имеют повышенное
содержание примесей и требуют дополнительной очистки. Часть сырья
подвергается контролю при поступлении на предприятие (входной контроль);
остальное сырье поступает на переработку без входного контроля. Затраты,
связанные с контролем качества одной партии сырья, составляют 8 руб. Если
при контроле обнаруживается повышенное содержание примесей, то партия
подвергается очистке; затраты на очистку составляют 40 руб. Если партия с
повышенным содержанием примесей не подвергалась входному контролю, то
необходимость ее очистки обнаруживается в ходе переработки; в этом случае
затраты на очистку составляют 70 руб. Требуется найти, какая часть сырья
должна подвергаться входному контролю, чтобы общие затраты на контроль и
очистку были минимальными.
Для решения данной задачи выполним моделирование процесса контроля
и очистки сырья при различных долях контролируемых партий сырья: от 0
(входной контроль не выполняется) до 100% (контролируется все сырье) с
шагом 5%. Предположим, что доля контролируемых партий сырья равна
некоторой заданной величине, например, 5%. Смоделируем процесс контроля и
очистки большого количества партий сырья (например, десяти тысяч) и
определим величину затрат на эти операции. Обозначим долю контролируемых
партий как P (в данном случае Р=0,05). Моделирование осуществляется по
следующему алгоритму.
1. Разыгрываются два ПСЧ: R1 и R2. Величина R1 будет использоваться
для имитации отбора контролируемых партий, а R2 – для имитации наличия
(или отсутствия) повышенного содержания примесей.
2. Если R1<P, то будем считать, что смоделировано поступление партии
сырья на контроль. Общие затраты при этом увеличиваются на 8 руб. (это
величина затрат на контроль одной партии). Если при этом R2<0,15 (где 0,15 –
доля партий, имеющих повышенное содержание примесей), то будем считать,
что смоделировано наличие повышенного содержания примесей в проверяемой
партии. В этом случае общие затраты увеличиваются на 40 руб. Если R1>P
(партия сырья не поступает на контроль), и при этом R2<0,15 (партия имеет
повышенное содержание примесей), то смоделировано обнаружение
повышенного содержания примесей при переработке сырья. Затраты
увеличиваются на 70 руб.
Шаги 1 и 2 повторяются многократно, например, 10000 раз (это означает
моделирование контроля и очистки 10000 партий сырья). Подсчитываются
общие затраты на контроль и очистку. В таблице 1 приведен пример десяти
испытаний (моделирование контроля и очистки десяти партий).
Таблица 1
Номер
испытания
R1
Контроль
R2
Повышенное
содержание
примеси
Затраты на
данную
партию
Общие
затраты
1
0,0795
да
0,3780
нет
8
8
2
0,0593
да
0,7602
нет
8
16
3
0,2847
нет
0,8197
нет
0
16
4
0,6133
нет
0,5766
нет
0
16
5
0,9595
нет
0,0981
да
70
86
6
0,2410
нет
0,5962
нет
0
86
7
0,2978
нет
0,6458
нет
0
86
8
0,9762
нет
0,0523
да
70
156
9
0,4523
нет
0,8153
нет
0
156
10
0,4286
нет
0,8400
нет
0
156
Аналогично следует выполнить моделирование при других долях
контролируемых партий сырья (от 0 до 100% с шагом 5%).
Приведем программную реализацию данного алгоритма на языке
Паскаль. Основные константы и переменные программы:
n – количество испытаний (количество обрабатываемых партий);
zatr_cont – затраты на контроль одной партии сырья;
zatr_o1 и zatr_o2 – затраты на очистку партии при обнаружении
повышенного содержания примеси в ходе контроля и в процессе переработки
соответственно;
primes – доля партий сырья, имеющих повышенное содержание примеси;
p – доля контролируемых партий;
proc – доля контролируемых партий сырья, выраженная в процентах
(например, если proc=5, то p=0,05);
r1,r2 – ПСЧ;
sum_zatr – общие затраты на контроль и очистку всех партий.
program control;
uses crt;
const n=10000;
zatr_cont=8;
zatr_o1=40;
zatr_o2=70;
primes=0.15;
var p,r1,r2,sum_zatr: real;
proc,i: integer;
begin
clrscr;
proc:=0;
while proc<=100 do
begin
p:=proc/100;
sum_zatr:=0;
for i:=1 to n do
begin
r1:=random; r2:=random;
if r1<p then sum_zatr:=sum_zatr+zatr_cont;
if (r1<p) and (r2<primes) then sum_zatr:=sum_zatr+zatr_o1;
if (r1>=p) and (r2<primes) then sum_zatr:=sum_zatr+zatr_o2;
end;
writeln(‘Процент контроля: ‘,proc, ' Затраты на 10000 партий:
‘,sum_zatr:10:2);
proc:=proc+5;
end;
end.
Результаты моделирования процесса контроля и очистки сырья
приведены в таблице 2.
Таблица 2
Процент контроля
Затраты на 10000 партий
0
112280
10
105432
20
109976
30
115378
40
121354
50
118078
60
126554
70
129020
80
132382
90
137690
100
139120
Таким образом, предприятию следует подвергать входному контролю
10% партий сырья. При этом затраты на контроль и очистку сырья будут
минимальными.
Задание
На
предприятие
радиоэлектронной
промышленности
поступают
комплектующие изделия – резисторы с номиналом невысокой точности (15%).
Известно, что примерно А% резисторов не подходит для изготовления
продукции и требуют дополнительной подгонки. Чтобы выявить такие
резисторы, необходим входной контроль. Стоимость контроля одного
резистора составляет B руб. Стоимость подгонки составляет C руб. Если
резистор установили в изделие, то стоимость его замены составляет D руб.
Требуется найти, какую часть резисторов необходимо подвергнуть входному
контролю, чтобы общие затраты на контроль и подгонку были минимальными.
Псевдослучайные числа формируются на основе LFSR с заданным
полиномом.
Таблица 3 – Варианты задания
Вариант
A, %
B
C
D
№
полинома
1
5
2
50
150
5
2
5
3
55
145
7
3
10
4
60
140
9
4
10
5
65
135
11
5
15
6
70
130
13
6
15
7
50
125
15
7
20
8
55
120
2
8
20
9
60
115
4
9
25
2
65
110
6
10
25
3
70
105
8
11
7
4
50
100
10
12
7
5
55
95
12
13
17
6
60
90
14
14
17
7
65
85
1
15
19
8
70
80
3
Варианты полиномов
1. X^32+X^30+X^28+X^27+X^25+X^22+X^21+X^20+X^19+X^18+X^12+X^10+X^9+X^6+1
2. X^32+X^30+X^29+X^26+X^25+X^24+X^23+X^20+X^18+X^9+X^5+X^1+1
3.
X^32+X^28+X^27+X^26+X^23+X^22+X^21+X^20+X^19+X^18+X^17+X^12+X^9+X^5+
+X^4+X^2+1
4. X^32+X^30+X^28+X^25+X^24+X^23+X^21+X^20+X^19+X^18+X^17+X^13+X^11+X^9+
+X^5+X^4+X^3+X^1+1
5. X^32+X^31+X^30+X^29+X^27+X^26+X^25+X^24+X^23+X^21+X^20+X^17+X^16+X^14+
+X^12+X^9+X^8+X^7+1
6.
X^32+X^31+X^30+X^29+X^27+X^25+X^23+X^21+X^20+X^19+X^13+X^10+X^7+X^6+
+X^5+X^4+X^3+X^1+1
7. X^32+X^30+X^28+X^27+X^25+X^24+X^23+X^21+X^20+X^19+X^18+X^16+X^15+X^14+
+X^8+X^6+X^5+X^3+1
8.
X^32+X^29+X^27+X^26+X^25+X^23+X^21+X^17+X^16+X^15+X^13+X^12+X^8+X^5+
+X^4+X^3+1
9.
X^32+X^31+X^27+X^26+X^23+X^22+X^19+X^18+X^17+X^16+X^15+X^12+X^9+X^8+
+X^6+X^5+X^4+X^3+X^2+X^1+1
10. X^32+X^31+X^30+X^29+X^27+X^24+X^23+X^22+X^18+X^9+X^7+X^6+X^3+X^2+1
11. X^32+X^31+X^30+X^28+X^27+X^24+X^23+X^21+X^18+X^16+X^15+X^13+X^12+X^11+
+X^10+X^9+X^7+X^6+X^5+X^2+1
12. X^32+X^29+X^28+X^23+X^22+X^21+X^16+X^13+X^10+X^6+X^5+X^4+1
13. X^32+X^31+X^26+X^25+X^24+X^22+X^21+X^20+X^19+X^16+X^13+X^12+X^8+X^2+1
14. X^32+X^28+X^22+X^21+X^20+X^19+X^18+X^16+X^10+X^8+X^7+X^3+1
15. X^32+X^30+X^27+X^26+X^25+X^23+X^22+X^21+X^20+X^19+X^18+X^17+X^13+X^6+
+X^5+X^4+1
Пример LFSR с порождающим полиномом X^32+X^28+X^27+X^1+1
1
2
27
28
29
30
31
32
Информация о работе Принятие решений на основе метода Монте-Карло