Написание программ с использованием методов прямого перебора и половинного деления

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

Содержание

Введение

1. Основные понятия

2. Сравнительный анализ прямого перебора и половинного деления

2.1 Метод прямого перебора

2.2 Ручной счёт

2.3 Метод половинного деления

2.4 Шаги исследования

2.5 Ручной счёт

3. Окно работающей программы

4. Вывод

5. Блок-схема программы

6. Код программы

Заключение

Список использованной литературы



Введение

В последнее время во всех областях целенаправленной человеческой деятельности интенсивно развиваются и широко применяются специальные научные методы выработки оптимальных решений, которые принято называть исследованием операций.

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



1. Основные понятия

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

Цель исследования операций - определить, как необходимо организовать работу системы (объекта, процесса), чтобы её (его) функционирование обеспечивало максимальный эффект, выработать соответствующие научно обоснованные решения и рекомендации по оптимальному функционированию системы на основе использования практически всех существующих методов анализа и синтеза (оптимизации) систем ЭВМ.

В настоящее время уже выделился определённый класс задач, эффективно решаемых в рамках исследования операций: распределительные; управление запасами; замены оборудования; упорядочения и согласования; выбора оптимальных режимов движения; массового обслуживания; состязательные; поиска и другие.

Решение задач исследования операций предполагает выполнение следующих основных этапов:

1) постановки задачи и выбора критерия оптимизации;

2) выявления основных особенностей, взаимосвязей и количественных закономерностей исследуемой системы;

3) построения математической модели системы (процесса);

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

Основные методы исследования математической модели:

1) аналитический;

2) исследование системы (процесса) с помощью численных методов и ЭВМ;

3) исследование системы (процесса) методами случайного поиска.

Аналитический метод, как правило, даёт наглядную картину исследуемой системы (процесса) и характеризующих ее (его) параметров. Однако построение математической модели - трудная задача, но, несмотря на это, данный метод широко используется при решении многих практических задач исследования операций.

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

Среди численных методов наибольшее распространение получили: для унимодальных функций одной переменной методы дихотомии, Фибоначчи и золотого сечения; для функций нескольких переменных методы поочерёдного изменения параметров, градиентный, наискорейшего спуска, математического программирования и т.д.

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

К методам случайного поиска (статическим методам) относятся ненаправленный случайный поиск (метод Монте-Карло), направленный случайный поиск без самообучения (поиск с парными пробами, линейный поиск, нелинейный поиск и т. д.), направленный поиск с самообучением.

Оптимизация - это выбор лучшего варианта из множества возможных. Выбор осуществляется в соответствии с принятыми критериями. Если понятие оптимизации ограничить практическими задачами, то можно выделить два основных направления:

1) получение желаемого эффекта при минимальных затратах для его получения;

2) получение максимального эффекта при использовании имеющихся ресурсов.

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

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

Критериальный выбор характерен для случаев, когда определён весь перечень критериев и есть вся необходимая информация по этим критериям по технической системе. На основе этой информации выбирается требуемый вариант Т.С. Это самый достоверный вид выбора, но для сбора требуемой информации требуется достаточно большой период времени и ресурсов.

Волевой выбор. Осознанный и ответственный выбор в условиях неполной информации по комплексу критериев. Принятие решения в этом случае связано с «дилеммой руководителя», который проявляется в следующем:

1) Заполнение отсутствующей информации за счёт интуиции, профессионализма эрудиции и других личных качеств разработчика, принимающего решение.

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

Случайный выбор (метод проб и ошибок). Используется при полном отсутствии информации о проектируемой Т.С. и решение принимается случайным образом.



2. Сравнительный анализ прямого перебора и половинного деления

половинный деление программа схема

Передо мной была поставлена задача написать программу, в которой я бы использовала 2 метода: прямого перебора и половинного деления и сравнила их.

2.1 Метод прямого перебора

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

Известна функциональная зависимость целевой функции от управляемых параметров. Необходимо найти экстремум целевой функции.

y = f (x₁, x₂, x₃….x_n)

Задаётся шаг изменения управляемых параметров, он же точность(погрешность), изменение управляемого параметра и далее управляемые параметры рассчитываются по формуле:

x_i= x₀+k_i*?x (k_i=0, 1, 2, 3…n)

x₀ - начальная точка поиска, k - шаг алгоритма

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

Достоинства:

1) Возможность нахождения глобального экстремума;

2) Независимость алгоритма от вида и характеристики целевой функции;

3) Простота алгоритма.

2.2 Ручной счёт

f(x)=-x²+4x+8- целевая функция;

[1 ;4] - интервал исследования;

?x=1 - точность;

x₀=2

f (x₀) = -4+8+8=12;

1) x₁=3;

y=f (x)= 12;

y₁=f(x)=11;

y>y_1;

2) x₂=2+2*1=4;

y=f(x)=12;

y₂=f(x₂)=8;

y>y_2;

3) x₃=2+3*1=5;

y=f(x)=12;

y₃=f(x₃)=8;

y>y₃.

х_opt=2, а y_max=12

2.3 Метод половинного деления

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

1) Выбираем наименьший интервал изменения управляемого параметра ?x.

2) Исходный интервал делим пополам.

3) Слева и справа от точки деления вычисляем х₁ и х₂ по формулам:

,

.

где b и a конец и начало исследования интервала.

4) Вычисляем значение целевой функции в т. х₁ и х₂.

5) Сравниваем значения между собой и основываясь на свойствах унимодальных функций отбрасываем из рассмотренного соответствующего интервала т. х₁ или х₂ принимаем новые значения в зависимости от отброшенного интервала.

6) На оставшемся интервале пункты 2-5 повторяем до тех пор, пока .

Достоинства:

Простота и эффективность при нахождении экстремума.

Недостатки:

Ищет только локальный экстремум.

Ручной счёт

f(x)=-x²+4x+8 - целевая функция;

[1 ;4] - интервал исследования;

?x=1 - точность;

1) x₀=(1+4)/2=2>?x

x₁=2+0.5=3.5

x₂=2-0.5=1.5

f(x₁)=-12.25+4*3.5+8=9.75

f(x₂)=-2.25+4*1.5+8=11.75

f(x₁)< f(x₂) ->(1.5…4) - новая граница

2) x₀=(1.5+4)/2=2.75

x₁=2.75+0.5=3.25

x2=2.75-0.5=2.25

f(x₁)=-10.56+13+8=10.44

f(x₂)=-5.0625+9+8=11.94

f(x₁)< f(x₂)->(3.25…4)- новая граница

3) x₀=(2.25+4)/2=3.625

x₁=2.25+0.5=2.25

x2=2.25-0.5=1.75

f(x₁)=-7.56+11+8=11.44

f(x₂)=-3.0625+7+8=11.93

f(x₁)< f(x₂)->(2.25…4)- новая граница

И так далее, пока новый интервал исследования не будет меньше или ровняться Х.

x_opt=2, y_max=11,93



3. Окно работающей программы

При открытии программы появляется окно (см. рис.1)

При запуске программы окно имеет вид (см. рис. 2):

Вводятся необходимые значения (см. рис.3).



Результат счёта (см. рис. 4).



4. Вывод

Обе программы вполне эффективны при поиске экстремума.

Точность:

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

Скорость:

В методе прямого перебора эффективность поиска прямо пропорциональна числу расчетов, в методе дихотомии эффективность возрастает с ростом количества шагов экспоненциально. Таким образом, для первого метода количество шагов равно 301, а для второго - 46.

Надёжность:

Оба метода являются достаточно надёжными при поиске экстремума функции.



5. Блок-схема программы

1) Мы открываем приложение.

2) Задаём переменные, которые берут участие во всей программе.

3) Задаётся функция.

4) Задаётся первый алгоритм, и ищется по нему экстремум.

5) Задаётся второй алгоритм для поиска экстремума.

6) Задаются названия столбцов и ячеек.

7) Выводятся на экран результаты счёта.

8) Конец программы.



6. Код программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls, Buttons;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

Edit1: TEdit;

Edit2: TEdit;

Label1: TLabel;

BitBtn1: TBitBtn;

Edit3: TEdit;

Label2: TLabel;

procedure FormCreate(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

k1, k2:integer;

implementation

{$R *.dfm}

function f(x:real):real;

begin

result:=-(x*x)+4*x+8;

end;

function MaxMin(a,b,e:real):real;

var

x0, xi:real;

k,i:integer;

begin

k1:=0;

k:=round((b-a)/e);

x0:=a;

for i:=0 to k do

begin

xi:=x0+i*e;

if f(x0)<f(xi) then

x0:=xi;

k1:=k1+1;

end;

result:=x0;

end;

function Dihotomiya(a,b,e:real):real;

var

x1, x2, a1, b1:real;

begin

a1:=a;

b1:=b;

k2:=0;

while (e<abs(b1-a1)) do

begin

x1:=abs(b1+a1)/2-(e/2);

x2:=abs(b1+a1)/2+(e/2);

if f(x1)<f(x2) then

a1:=x1

else

if f(x1)>f(x2) then

b1:=x2

else

if f(x1)=f(x2) then

begin

a1:=x1;

b1:=x2;

end;

k2:=k2+1;

end;

result:=abs(a1+b1)/2;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

StringGrid1.Cells[0,0]:='метод';

StringGrid1.Cells[0,1]:='прямого перебора';

StringGrid1.Cells[0,2]:='Дихотомии';

StringGrid1.Cells[1,0]:='Х опт';

StringGrid1.Cells[2,0]:='У макс';

StringGrid1.Cells[3,0]:='Дельта х';

StringGrid1.Cells[4,0]:='К';

end;

procedure TForm1.BitBtn1Click(Sender: TObject);

var

x1, x2,a,b,e: real;

begin

a:=strToFloat(Edit1.Text);

b:=strToFloat(Edit2.Text);

e:=strToFloat(Edit3.Text);

x1:=MaxMin(a, b, e);

x2:=Dihotomiya(a, b, e);

StringGrid1.Cells[1,1]:=FloatTostr(x1);

StringGrid1.Cells[2,1]:=FloatTostr(f(x1));

StringGrid1.Cells[3,1]:=FloatTostr(e);

StringGrid1.Cells[4,1]:=FloatTostr(k1);

StringGrid1.Cells[3,2]:=FloatTostr(e);

StringGrid1.Cells[1,2]:=FloatTostr(x2);

StringGrid1.Cells[2,2]:=FloatTostr(f(x2));

StringGrid1.Cells[4,2]:=FloatTostr(k2);

end;

end.



Заключение

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

Оба алгоритма имеют свои плюсы и минусы, но выбор алгоритма следует выбирать, выходя из имеющихся данных



Список использованной литературы

1. Кудрявцев Е.М. Исследование операций в задачах, алгоритмах и программах. - М.: Радио и связь, 1984. - 184 с.

2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. -- М.: Мир, 1985.-214с.

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