Размещено на http://www.allbest.ru/

Содержание

Вступление

1. Математическая формулировка задачи

2. Выбор метода решения и постановка задачи

3. Описание алгоритма решения задачи

4. Описание программы

5. Описание методики решения задачи по разработанной программе на основе контрольного примера

Заключение

Литература

Вступление

Метод ветвей и границ - общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является комбинаторным (алгоритм перебора) с отсевом подмножеств множества допустимых решений, не содержащих оптимальных решений. Метод был впервые предложен Ленд и Дойг в 1960 г. для решения задач целочисленного линейного программирования.

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

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

конкретных задач и поэтому заметно отличаются друг от друга. Однако

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

1. Математическая формулировка задачи

Пример: Методом Монте-Карло приближённо вычислить интеграл:

где область интегрирования определяется следующими неравенствами:

Размещено на http://www.allbest.ru/

Интеграл дан в приведенном виде, т. е. Область интегрирования расположена в единичном квадрате

Для решения задачи воспользуемся таблицей случайных чисел и следующими вычислениями:

Отсюда

,

и, следовательно, с формулы:

имеем:

Если приближенно принять

то получим:

2. Выбор метода решения и постановка задачи

алгоритм оптимизация комбинаторный дискретный

Использовать метод Монте-Карло рациональнее, так как его легче реализовать, и он требует меньшего количества вычислений.

Таким образом: метод решения задачи - метод Монте-Карло.

Постановка задачи - вычислить определённый интеграл методом Монте-Карло.

3. Описание алгоритма решения задачи



4. Описание программы

Программа реализации алгоритма написана на языке Paskal.

Таблица переменных

Переменная	Назначение	Тип
a	Верхняя граница интеграла	array [0…20]of real
b	Нижняя граница интеграла	array [0...20] of real
pp	Рабочая переменная	array [0...20] of real
pl	Рабочая переменная	array [0...20] of real
pc	Результат	array [0...20] of real
pt	Рабочая переменная	array [0...20] of real
int	Рабочая переменная	char
z	Рабочая переменная	array [0...20] of real
S1	Уровень значимости	real
S2	Рабочая переменная	real
S3	Рабочая переменная	real
dh	Переменная для определения результата	real
h	Переменная для определения результата	real
e	Рабочая переменная	real
i	Переменная цикла	Integer
j	Переменная цикла	Integer
n	Счетчик цикла	Integer

program kurs;

uses crt;

var x,y,pp,pl,pc,pt,z:array [0..20] of real;

s1,s2,s3,dh,h,e:real;

i,j,n:integer;

int: char;

begin

clrscr;

textcolor(9);

writeln(' РАСЧОТНО-ГРАФИЧЕСКАЯ РАБОТА');

writeln(' ВЫЧИСЛЕНИЕ ИНТЕГРАЛОВ МЕТОДОМ МОНТЕ-КАРЛО.');

textcolor(green);

writeln(' ВЫПОЛНИЛА СТУДЕНТКА 3-ГО КУРССА');

writeln(' ЛИЗОГУБ ВАЛЕНТИНА ВИКТОРОВНА');

textcolor(green);

writeln('Введите нижнюю границу интегрирования ');

readln(a);

writeln('Введите верхнюю границу интегрирования ');

readln(b);

n:=10;

writeln('Введите точность интегрирования ');

readln(e);

textcolor(10);

writeln('Введите интеграл');

readln(int);

textcolor(13);

writeln('Вычисление интеграла ');

writeln(' ')

for i:=1 to 2 do begin

x[0]:=a;

h:=(b-x[0])/(i*n);

for j:=1 to n*i do x[j]:=x[j-1]+h;

for j:=0 to n*i do y[j]:=sqrt(1+x[j]*x[j]*x[j]){cos(x[j]*x[j])};

s1:=0;

s2:=0;

for j:=1 to round(i*n/2) do s1:=s1+y[2*j-1];

for j:=1 to round(i*n/2-1) do s2:=s2+y[2*j];

z[i]:=(h/3)*(y[0]+y[i*n]+4*s1+2*s2);

end;

textcolor(yellow);

writeln('По методу Монте-Карло интеграл равен:');

write(' pc=',z[i]:0:3);

dh:=abs(z[2]-z[1])/15;

writeln(', погрешность:',dh:14:10);

pp[1]:=0;

pl[1]:=0;

pc[1]:=0;

pt[1]:=0;

pp[2]:=1;

pl[2]:=1;

pc[2]:=1;

pt[2]:=1;

while((abs(pp[1]-pp[2])/3>e) and (abs(pl[1]-pl[2])/3>e) and (abs(pc[1]-pc[2])/3>e) and (abs(pt[1]-pt[2])/3>e)) do begin

for i:=1 to 2 do begin

h:=(b-x[0])/(n*i);

for j:=1 to n*i do begin

x[j]:=x[j-1]+h;

y[j]:=sqrt(1+x[j]*x[j]*x[j]);

end;

s1:=0;

s2:=0;

s3:=0;

for j:=1 to n*i do begin

s1:=s1+y[j-1];s2:=s2+y[j];

s3:=s3+sqrt(1+(sqrt(x[0]+h*(j-1)+h/2)))

end;

pp[3-i]:=h*s2;

pl[3-i]:=h*s1;

pc[3-i]:=h*s3;

pt[3-i]:=h*((y[0]-y[i*n])/2+s1*y[0]);

end;

n:=n+1;

end;

textcolor(20);

write('Для выхода из программы нажмите ENTER...');

readln;

end.

5. Описание методики решения задачи по разработанной программе на основе контрольного примера

Данная программа разработана на основе метода Монте-Карло. Исходными данными являются верхние, нижние границы интегрирования и погрешность интегрирования. В начале программы нас просят ввести верхнюю и нижнюю границы интегрирования - это могут быть любые числа, которые вводятся с клавиатуры. Наша задача состоит в том, чтобы определить приближенное значение интеграла с гарантированно малой оценкой погрешности. Для этого мы выбираем точность интегрирования из таблицы случайных чисел, равномерно распределённых на отрезке [0;5]

0,57705	1,35483	2,11578	3,65339	4,66674
0,71618	1,09393	2,93045	3,93382	4,99279
0,73710	1,30304	2,93011	3,05758	4,24202
0,70131	1,55186	2,42844	3,00336	4,94010
0,16961	1,64003	2,52906	3,88222	4,60981
0,53324	1,20514	2,09461	3,98585	4,13094
0,43166	1,00188	2,99602	3,52103	4,35193
0,26275	1,55709	2,69962	3,91827	4,64560
0,05926	1,86977	2,31311	3,07069	4,64559
0,66289	1,31303	2,27004	3,13928	4,68008

Вводим одно из этих чисел, затем вводим интеграл и считаем интеграл по формуле:

После чего получаем результат, который выводится на экран. После результата выводится погрешность. Для выхода из программы нужно нажать ENTER.

Контрольный пример

РАСЧОТНО-ГРАФИЧЕСКАЯ РАБОТА

ВЫЧИСЛЕНИЕ ИНТЕГРАЛОВ МЕТОДОМ МОНТЕ-КАРЛО

Введите нижнюю границу интегрирования

0

Введите верхнюю границу интегрирования

9

Введите точность интегрирования

0,57705

Введите интеграл

(2x2+4x+9) d x

ВЫЧИСЛЕНИЕ ИНТЕГРАЛА

По методу Монте-Карло интеграл равен

рc=40.256, погрешность 0,0001579347

ДЛЯ ВЫХОДА ИЗ ПРОГРАММЫ НАЖМИТЕ ENTER…..

Введите нижнюю границу интегрирования

0

Введите верхнюю границу интегрирования

9

Введите точность интегрирования

1,35483

Введите интеграл

(2x2+4x+9) d x

ВЫЧИСЛЕНИЕ ИНТЕГРАЛА

По методу Монте-Карло интеграл равен

рc=40.256, погрешность 0,0001579498

ДЛЯ ВЫХОДА ИЗ ПРОГРАММЫ НАЖМИТЕ ENTER…..

Введите нижнюю границу интегрирования

0

Введите верхнюю границу интегрирования

9

Введите точность интегрирования

2,11578

Введите интеграл

(2x2+4x+9) d x

ВЫЧИСЛЕНИЕ ИНТЕГРАЛА

По методу Монте-Карло интеграл равен

рc=40.256, погрешность 0,0001579627

ДЛЯ ВЫХОДА ИЗ ПРОГРАММЫ НАЖМИТЕ ENTER…..

Введите нижнюю границу интегрирования

0

Введите верхнюю границу интегрирования

9

Введите точность интегрирования

3,65339

Введите интеграл

(2x2+4x+9) d x

ВЫЧИСЛЕНИЕ ИНТЕГРАЛА

По методу Монте-Карло интеграл равен

рc=40.256, погрешность 0,0001579828

ДЛЯ ВЫХОДА ИЗ ПРОГРАММЫ НАЖМИТЕ ENTER…..

Введите нижнюю границу интегрирования

0

Введите верхнюю границу интегрирования

9

Введите точность интегрирования

4,66674

Введите интеграл

(2x2+4x+9) d x

ВЫЧИСЛЕНИЕ ИНТЕГРАЛА

По методу Монте-Карло интеграл равен

рc=40.256, погрешность 0,000157996

ДЛЯ ВЫХОДА ИЗ ПРОГРАММЫ НАЖМИТЕ ENTER…..

По результатам мы видим, что с уменьшением точности погрешность увеличивается.

Проверка

Из выше проведённых примеров мы убедились, что метод Монте-Карло вычисляет точнее интеграл чем мы вычисляем его в ручную

Заключение

Часть пользователей предубеждена против метода Монте-Карло вследствие того, что малость погрешности метода обеспечивается лишь с некоторой вероятностью, и вследствие этого отрицает правомерность его использования. Поэтому применение метода Монте-Карло вызвано обстановкой, когда трудно надеяться на получение приближенного значения интеграла с гарантированно малой оценкой погрешности. После проведения контрольного примера мы убедились, что с уменьшением точности погрешность интегрирования растёт.

Литература

1. Математические методы в технологических исследованиях / Рыжов Э.В., Горленко О.А. Отв. ред. Гавриш А.Г.; АН УССР. Ин-т сверхтвердых материалов, Киев: Наук. думка, 1996. - 184с.

2. Методы анализа данных: Подход, основанный на методе динамических сгущений; Пер. с фр./ Кол. авт. под рук. Э. Дидэ. Под ред. и с предисловием С.А. Айвазяна и В.М. Бухштабера. - М.: Финансы и статистика, 1985 - 357с.

3. Оптимизация технологических процессов в машиностроении. Душинский В.В. Пуховский Е.С. Радченко С.Г. Под общ. ред. канд. техн. наук Г.Э. Таурита "Техника", 1977, 176с.

Размещено на Allbest.ru

...