Методы оптимизации функции и алгоритмы на графах

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

Содержание

Введение

1. Постановка задачи

2. Теоретическая часть

2.1 Графы и алгоритмы на графах

2.2 Метод Фибоначчи

2.3 Метод наискорейшего спуска

2.4 Метод Рунге-Кутта-Мерсона

2.5 Метод Эйлера

3. Практическая реализация методов

3.1 Входные и выходные данные, их структура и представление в ПЭВМ

3.2 Описание программ

3.2.1 Основная программа реализации дифференцирования методом Эйлера

3.2.2 Основная программа реализации методом Фибоначчи

3.2.3 Основная программа реализации на графах

3.2.4 Основная программа поиска минимума методом наискорейшего спуска

3.2.5 Основная программа для решения системы ОДУ, описывающей простейшую модель экосистемы

4. Результаты работы программ

Заключение

Литература



Введение

В данной курсовой будут рассмотрены методы оптимизации функции и алгоритмы на графах.

В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом:

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

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

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

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



1. Постановка задачи

В рамках курсового проекта необходимо создать обучающую программу на языке Borland С++ реализующую решение на графах, обыкновенных дифференциальных уравнений, системы ОДУ, описывающей простейшую модель экосистемы (модель Лотка-Вольтерра), методы оптимизации. На основе работы программы сделать выводы о эффективности того или иного метода.



2 Теоретическая часть

2.1 Графы и алгоритмы на графах

Задание 1. Составьте программу на С, выполняющую ввод графа (в виде абстрактной структуры или системы дорог, соединяющих населенные пункты). Рекомендуется хранение графа в виде списка инцидентности (допускается использование матрицы смежности или инцидентности)

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

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

2.2 Метод Фибоначчи

Для выбранной функции найдите наибольшее значение методом чисел Фибоначчи.

Последовательность чисел

0,1,1,2,3,5,8,13,21,34,…,

Каждый член которой равен сумме двух предыдущих называется числами Фибоначчи.

Числа Фибоначчи удовлетворяют многим интересным тождествам например:

F_n+1F_n-1-F_n²=(-1)ⁿ (1)

zl^n-2?F_n?zl^n-1 (2)

F_n/F_n-1?zl, при n>7 , (3)

где F_n -число Фибоначчи, а zl-золотое сечение (zl=(1+5^Ѕ)/2).

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

Алгоритм процедуры поиска максимума: Max(a,b)

1. Находим три числа Фибоначчи F_n F_n-1 F_n-2 n>8;

2. Производим шаги 3-4 пока |a-b|>eps

3. y=a+ F_n-2 (b-a)/F_n; z= a+ F_n-1 (b-a)/F_n;

4. если f(y)>f(z) то b=z иначе a=y;

5. Искомый максимум - f((a+b)/2);

2.3 Метод наискорейшего спуска

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



2.4 Метод Рунге-Кутта-Мерсона

Разработайте программу для решения системы ОДУ, описывающей простейшую модель экосистемы (модель Лотка-Вольтерра). Предусмотрите вывод результатов в текстовый файл и ввод коэффициентов системы (a,b,c, a) и начальных условий с терминала.

Автоматическое изменение шага в ходе решения систем дифференциальных уравнений необходимо, если решение требуется получить с заданной точностью. При высокой точности (погрешность ) и решении в виде кривых с сильно различающейся крутизной автоматическое изменение шага обеспечивает уменьшение общего числа шагов в несколько раз, резко уменьшается вероятность числовой неустойчивости, даёт более равномерное расположение точек графика кривых (решений) при их выводе на печать. Данный метод обеспечивает приближённую оценку погрешностей на каждом шаге интегрирования. Погрешность интегрирования имеет порядок h⁵. Этот метод реализуется следующим алгоритмом: Задаём число уравнений N, погрешность е=E, начальный шаг интегрирования h=H и начальное значение y₁₀,…,y_N0. С помощью пяти циклов с управляющей переменной J=1,2,..,N вычисляем коэффициенты:

(7)

(8)

(9)

(10)

(11)

Находим (в последнем цикле) значение (12)

(12)

И погрешность

(13)

Проверяем выполнения условий



(14)

(15)

Если условие (14) не выполняется, то делим шаг h на 2 и повторяем вычисления. Если это условие выполняется и выполняется условие (15), значение x_i+1=x_i+h и Y_j(i+1), то считаем, что решение системы дифференциальных уравнений найдено с заданной точностью. Если условие (15) не выполняется , шаг h увеличивается вдвое и вычисления повторяются.

2.5 Метод Эйлера

Для выбранной функции найдите наибольшее значение взятием производной и решением возникающего уравнения f'(x)=0.

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

Метод численного решения дифференциального уравнения первого порядка

(1)

с начальным условием основан на разложении решения в ряд Тейлора в -окрестности точки :

При отбрасывании всех членов ряда, содержащих производные второго и высших порядков получим:



,

где -правая часть уравнения (1).

Пользуясь значением из разложения в - окрестности точки

получим

(2)

Аналогично продолжая для следующей точки , получим

(3)

Если дано уравнение второго порядка

(4)

с начальными условиями и , то как такое уравне- ние можно свести к системе двух уравнений первого порядка

, (5)

Причем

и .

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

, (6)

где - правая часть уравнения (4).

При достаточно малой величине шага метод Эйлера дает решение с большой точностью, т.к. погрешность решения близка к

решение граф дифференциальный оптимизация



3. Практическая реализация методов

3.1 Входные и выходные данные, их структура и представление в ПЭВМ

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

3.2 Описание программ

3.2.1 Основная программа реализации дифференцирования методом Эйлера

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <math.h>

const eps=1e-9;

float a,b,h,x,y,x0,y0;

float func(float x)

{

return x*x*x*x-18*x*x+5*x-8;

}

int main ()

{

printf(" Input a, b = \n");

scanf(" %f",&a);

scanf(" %f",&b);

printf(" H = \n");

scanf(" %f",&h);

printf("\n\n Metodom Eilera 1-ya proizvodnaya");

x0=0;

y0=1;

x=x0;

y=y0;

while (x<b+eps)

{

y=y0+h*func(x);

y0=y;

printf("\n pri x=%f y=%f",x,y);

x=x+h;

}

getch();

return 0;

}

3.2.2 Основная программа реализации методом Фибоначчи

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <math.h>



double func(double x)

{

return x*x*x*x-18*x*x+5*x-8;

}

double fabio(double *a0, double *b0, int *n0, double eps)

{

int i,n;

double s1;

double s2;

double u1;

double u2;

double fu1;

double fu2;

double a,b;

a=*a0;

b=*b0;

n=*n0;

s1 = (3-sqrt(double(5)))/2;

s2 = (sqrt(double(5))-1)/2;

u1 = a+s1*(b-a);

u2 = a+s2*(b-a);

fu1 = func(u1);

fu2 = func(u2);

for(i = 1; i <= n; i++)

{

if( fu1<=fu2 )

{

b = u2;

u2 = u1;

fu2 = fu1;

u1 = a+s1*(b-a);

fu1 = func(u1);

}

else

{

a = u1;

u1 = u2;

fu1 = fu2;

u2 = a+s2*(b-a);

fu2 = func(u2);

}

printf(" [%d] a= %lf b= %lf \n",i,a,b);

if(fabs(b-a)<eps)

{

break;

}

}

*a0=a;

*b0=b;

*n0=i;

return (a+b)/2.0;

}

int main() {

int n; double x,a,b,eps;

n=100;

printf(" Input a, b = \n");

scanf(" %lf",&a);

scanf(" %lf",&b);

printf(" Eps = \n");

scanf(" %lf",&eps);

x=fabio(&a, &b, &n, eps);

printf("\n [%d] a= %lf b= %lf x= %lf \n",n,a,b,x);

getch();

return 0;

}

3.2.3 Основная программа реализации на графах

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

int N, M;

int **Graf;

void OVS( int Start, int FIFO[], int Label[], int Ignor );

int main()

{

FILE *f;

int *Label;

int *FIFO;

int From, To;

int i, j, k;

f = fopen("f:\\new\\input.txt","r");

fscanf( f, "%d %d", &From, &To );

fscanf( f, "%d %d", &N, &M );

printf( "N(vershin) = %d, M(putej) = %d\n", N, M );

Label = (int*) malloc( N * sizeof(int) );

FIFO = (int*) malloc( N * sizeof(int) );

Graf = (int**) malloc( N * sizeof(int*) );

for( i = 0; i < N; i++ )

Graf[i] = (int*) malloc( N * sizeof(int) );

for( i = 0; i < N; i++ ) {

Label[i] = 0;

FIFO[i] = 0;

}

for( i = 0; i < N; i++ )

for( j = 0; j < N; j++ ) Graf[i][j] = 0;

for( k = 0; k < M; k++ ) {

fscanf( f, "%d %d", &i, &j );

Graf[i][j] = 1;

}

for( i = 0; i < N; i++ )

for( j = 0; j < N; j++ )

printf( "Graf[%d,%d] = %d\n", i, j, Graf[i][j] );

printf("\n");

OVS( From, FIFO, Label, -1 );

printf( "Control poiska v shirinu ot vershiny i = %d \n", From );

for( k = 0; k < N; k++ )

printf( "%d ", Label[k] );

if( Label[To] < 30000 ) {

for( i = 0; i < N; i++ ) {

if( i != From && i != To ) {

OVS( From, FIFO, Label, i );

printf( "\nControl poiska v shirinu bez vershiny i = %d \n", i );

for( k = 0; k < N; k++ )

printf( "%d ", Label[k] );

if( Label[To] > 30000 ) {

printf( "\nVershina: %d", i );

break;

}

}

}

if( i == N )

printf( "\nTakoj vershini net" );

}

else

printf( "\nNet puti mejdu ukazannimi vershinami" );

printf( "\n" );

fclose(f);

getch();

return 0;

}

void OVS( int Start, int FIFO[], int Label[], int Ignor )

{

int z, p, k, cur;

for( z = 0; z < N; z++) {

FIFO[z] = 0;

Label[z] = 32767;

}

p = 0;

k = 1;

FIFO[p] = Start; Label[Start] = 0;

while( p != k ) {

cur = FIFO[p];

p++;

for( z = 0; z < N; z++)

if( Graf[cur][z] == 1 && Label[z] > Label[cur] + 1 && z != Ignor ) {

FIFO[k] = z;

k++;

Label[z] = Label[cur] + 1;

}

}

}

3.2.4 Основная программа поиска минимума методом наискорейшего спуска

#include <math.h>

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

float x,f1,f2,y,x0,y0,x1,y1,e=0.0001,z,d,a;

float f(float x, float y)

{

f1=x*x+y*y-6;

f2=exp(-x)-y;

z=f1*f1+f2*f2;

return z;

}

float d1(float x, float y)

{

d=2*(x*x+y*y-6)*(2*x)+(-exp(-x))*2*(exp(-x)-y);

return d;

}

float d2(float x, float y)

{

d=2*(x*x+y*y-6)*(2*y)+(-1)*(2*(exp(-x)-y));

return d;

}

int main()

{

clrscr();

x0=1;

y0=1;

a=0.1;

while ((fabs(d1(x0,y0))>e/2) && (fabs(d2(x0,y0))>e/2))

{

x1=x0-a*d1(x0,y0);

y1=y0-a*d2(x0,y0);

if (f(x1,y1)>f(x0,y0))

{

a=a/2;

x1=x0-a*d1(x0,y0);

y1=y0-a*d2(x0,y0);

}

x0=x1;

y0=y1;

}

x=x0;

y=y0;

printf ("\n Min fynkcii naydenn s pomoshiy naiskoreishego spyska: ");

printf ("\n x=%f y=%f",x,y);

getch();

return 0;

}

3.2.5 Основная программа для решения системы ОДУ, описывающей простейшую модель экосистемы

#include <stdio.h>

#include <conio.h>

#include <math.h>

const double t = 1e-3;

const double t0=0;

float x1,x2,a,b,c,alpha,tk;

FILE *f11;

double f1 (float x1, float x2 )

{

return((a-b*x2)*x1-alpha*x1*x1);

}

double f2 (float x2, float x1 )

{

return((-c+b*x1)*x2-alpha*x2*x2);

}

int main ()

{

clrscr();

float x,y1,y2,k1,k2,k3,k4,k5,r,h,d1,d2;

printf("\n\r Vvedite a,b,c,alpha,tk,x1,x2:");

printf("\n x1=");

scanf("%f", &x1);

printf("\n x2=");

scanf("%f", &x2);

printf("\n a=");

scanf("%f", &a);

printf("\n b=");

scanf("%f", &b);

printf("\n c=");

scanf("%f", &c);

printf("\n alpha= ");

scanf("%f", &alpha);

printf("\n tk=");

scanf("%f", &tk);

cprintf("\n Metod Runge-Kutta-Mersona");

h=tk/20;

y1=x1;

y2=x2;

f11=fopen("d:\\f1.txt", "w+");

for (a=t0; a<=tk+t; a+=h)

{

printf("\n\n t=%f", a);

k1=h*f1(x1,x2);

k2=h*f1(x1+(1/3)*h,x2+(1/3)*k1);

k3=h*f1(x1+(1/3)*h,x2+(1/6)*k1+(1/6)*k2);

k4=h*f1(x1+(1/2)*h,x2+(1/8)*k1+(3/8)*k3);

k5=h*f1(x1+h,x2+(1/2)*k1-(3/2)*k3+2*k4);

d1=y1+(k1+4*k4+k5)/6;

k1=h*f2(x2,x1);

k2=h*f2(x2+(1/3)*h,x1+(1/3)*k1);

k3=h*f2(x2+(1/3)*h,x1+(1/6)*k1+(1/6)*k2);

k4=h*f2(x2+(1/2)*h,x1+(1/8)*k1+(3/8)*k3);

k5=h*f2(x2+h,x1+(1/2)*k1-(3/2)*k3+2*k4);

d2=y2+(k1+4*k4+k5)/6;

r=(2*k4-3*k3-k5)/10;

if (fabs(r)>tk)

{

h=h/2;

}

if (32*(fabs(r)<tk))

{

h=h*2;

}

printf("\n x1=%f d1=%f ",(a+x1),d1);

printf("\n x2=%f d2=%f ",(a+x2),d2);

fprintf(f11, " t=%f d1=%f d2=%f \n",a,d1,d2);

}

getch();

fclose(f11);

}



4. Результаты работы программ

Графы

График функции для поиска точек её экстремумов

Дифференцирование мотодом Эйлера

Метод Фибоначчи

Метод наискорейшего спуска

Метод Рунге-Кутта-Мерсона



Заключение

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

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



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

1. Бахвалов Н.С. Численные методы. - М.: Наука, 1975.

2. Мудров А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль.-Томск: МП «Раско», 1991.

3. Бахвалов Н.С., Кобельков Г.М, Поспелов В.В. Сборник задач по методам вычислений. - М.: Изд-во МГУ, 1989.

4. Карманов В.Г. Математическое программирование. - М.: Наука, 1984.

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