Разработка программы для оптимизации функции одной переменной методом дихотомии

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

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

Оглавление

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

1.1 Общие сведения

1.2 Функциональное назначение

1.3 Описание логической структуры

1.4 Используемые технические средства

1.5 Вызов и загрузка

1.6 Входные и выходные данные

2. Описание применения

2.1 Назначение программы

2.2 Условия применения

2.3 Описание задачи

2.4 Входные и выходные данные

3. Руководство программиста

3.1 Назначение и условия применения программы

3.2 Характеристики программы

3.3 Обращение к программе

3.4 Входные и выходные данные

3.5 Сообщение

4. Описание контрольного примера

5. Листинг программы

Библиографический список

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

1.1 Общие сведения

Программа: «Оптимизация функции одной переменной методом дихотомии»

Программное обеспечение, необходимое для функционирования программы:

Операционная среда Windows 95/98/Me/2k/XP

Microsoft Visual Studio 2005

Среда разработки - Microsoft Visual Studio 2005

Программа написана на языке C++

1.2 Функциональное назначение

Программа предназначена для поиска минимума и максимума функции на заданном интервале. Используется для функций вида с максимальной степенью х, равной 5.

1.3 Описание логической структуры

Алгоритм:

Положим, что x_n = . Длина отрезка L = (|B| - |A|). Вычислим f(x_n).

x₁ = A + ,x₂ = B - . Вычисляем f(x₁) и f(x₂).

Если f(x₁) < f(x_n), то исключаем интервал [x_n,B], для этого B = x_n, x_n = x₁. Переход к шагу 5. Иначе к шагу 4.

Если f(x₂) < f(x_n), то исключаем интервал [A_,x_n] для этого A = x_n, x_n = x₂. Переход к шагу 5. Иначе исключаем интервалы [A_,x₁] [x_2,B], для этого A = x₁, B = x₂.

Вычисляем L = B - A. Если L ? е, то конец алгоритма. Иначе переход к шагу 2.

Окончание алгоритма включает в себя x* = x_m, f (x*) = f(x_m)

Логическая структура:

5 функций:

1. main() - главная функция

Основные задачи:

- Диалог с пользователем

- Ввод коэффициентов, интервала и точности

- Вывод результата

2. menu() - функция, типа void. Назначение - текст главного меню программы.

3. out() - функция, типа void. Назначение - вывод данных на экран.

4. dihotomy() - функция, типа double. Назначение - выполнение алгоритма.

5. func() - функция, типа double. Назначение - функция f(x).

Связь программы с другими программами:

Операционная система

Файловая система

1.4 Используемые технические средства

При написании программы использовался компьютер:

Процессор - Intel Core 2 Duo E8400, 4050 MHz (9 x 450)

ОЗУ - 4096Мб.

Видеоадаптер - ATI Radeon HD 4850 (512 Мб)

Минимальный набор периферийного оборудования.

Минимальные требования:

Процессор Intel Pentium II.

Наличие не менее 16Mб ОЗУ.

Наличие не менее 1Мб свободного дискового пространства.

SVGA - графический адаптер.

Минимальный набор периферийного оборудования.

1.5 Вызов и загрузка

Для начала работы программы необходимо запустить файл dichotomy.exe

1.6 Входные и выходные данные

Входные данные:

1. Коэффициенты функции (a0,а1,а2,a3,а4,а5) - действительные числа

2. Интервал поиска - действительные числа

3. Точность - пользователь может указать точность большую 0,000001

Выходные данные:

Значение максимума и минимума.

2. Описание применения

2.1 Назначение программы

Программа предназначена для поиска минимума и максимума функции на заданном интервале. Используется для функций вида с максимальной степенью х, равной 5.

2.2 Условия применения

Минимальные требования:

Процессор Intel Pentium II.

Наличие не менее 16Mб ОЗУ.

Наличие не менее 1Мб свободного дискового пространства.

SVGA - графический адаптер.

Минимальный набор периферийного оборудования.

Программное обеспечение, необходимое для функционирования программы:

Операционная среда Windows 95/98/Me/2k/XP

Microsoft Visual Studio 2005

2.3 Описание задачи

Задача:

Найти минимум и максимум функции на заданном интервале для функций вида с максимальной степенью х, равной 5.

Математическая постановка и решение задачи:

Одним из методов оптимизации является метод дихотомии.

Положим, что x_n = . Длина отрезка L = (|B| - |A|). Вычислим f(x_n).

x₁ = A + ,x₂ = B - . Вычисляем f(x₁) и f(x₂).

Если f(x₁) < f(x_n), то исключаем интервал [x_n,B], для этого B = x_n, x_n = x₁. Переход к шагу 5. Иначе к шагу 4.

Если f(x₂) < f(x_n), то исключаем интервал [A_,x_n] для этого A = x_n, x_n = x₂. Переход к шагу 5. Иначе исключаем интервалы [A_,x₁] [x_2,B], для этого A = x₁, B = x₂.

Вычисляем L = B - A. Если L ? е, то конец алгоритма. Иначе переход к шагу 2.

Окончание алгоритма включает в себя x* = x_m, f (x*) = f(x_m)

2.4 Входные и выходные данные

Входные данные:

1. Коэффициенты функции (a0,а1,а2,a3,а4,а5) - действительные числа

2. Интервал поиска - действительные числа

3. Точность - пользователь может указать точность большую 0,000001

Выходные данные:

Значение максимума и минимума.

3. Руководство программиста

3.1 Назначение и условия применения программы

Назначение программы:

Программа предназначена для поиска минимума и максимума функции на заданном интервале. Используется для функций вида с максимальной степенью х, равной 5.

Минимальные требования:

Процессор Intel Pentium II.

Наличие не менее 16Mб ОЗУ.

Наличие не менее 1Мб свободного дискового пространства.

SVGA - графический адаптер.

Минимальный набор периферийного оборудования.

Программное обеспечение, необходимое для функционирования программы:

Операционная среда Windows 95/98/Me/2k/XP

Microsoft Visual Studio 2005

3.2 Характеристики программы

Для выполнения программы требуется сравнительно небольшой промежуток времени.

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

3.3 Обращение к программе

Для начала работы программы необходимо запустить файл dichotomy.exe

3.4 Входные и выходные данные

Входные данные:

1. Коэффициенты функции (a0,а1,а2,a3,а4,а5) - действительные числа

2. Интервал поиска - действительные числа

3. Точность - пользователь может указать точность большую 0,000001

Выходные данные:

Значение максимума и минимума.

3.5 Сообщения

Сообщения, выводимые пользователю:

(1) Введен неверный интервал!

Причины возникновения:

- левая граница больше правой

- левая граница равна правой

(2) Введена неверная точность!

Причины возникновения:

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

4. Описание контрольного примера

В качестве контрольного примера рассмотрим работу программы с функцией f (x) = 2 + 3 - 2 + 4+ 8

Интервал поиска: [-6; 7]

Точность: 0,01

Результат обработки контрольного примера (Рис.1)

Проверим правильность расчетов:

Минимум функции (Рис.2)

Таким образом, графически проверена правильность вычислений.

5. Листинг программы

#include "stdafx.h"

#include <locale.h>

#include <stdlib.h>

#include <conio.h>

#include <math.h>

#include <stdio.h>

//-------------------------------------------------------------------

void menu();

void out(const char*,double);

double func(double,double,double,double,double,double,double);

double dihotomy(double,double,int,double,double,double,double,double,double,double);

//-------------------------------------------------------------------

void main()

{

setlocale(LC_ALL, "rus");

system("color 71");

double A,B,t,a0,a1,a2,a3,a4,a5,mn,mx;

char NumberOfAction;

int resultCase=1;

while(resultCase!=0)

{

do

{

menu();

NumberOfAction=getch();

}

while (NumberOfAction!='1' && NumberOfAction!='2' && NumberOfAction!='3' && NumberOfAction!='4' && NumberOfAction!='e');

switch (NumberOfAction)

{

//case '1' (ввод интервала)

case '1':

system("cls");

system("echo ----------------------------------------------------------");

printf("Введите интервал поиска:");

printf("\nA:\t");scanf("%lf",&A);

printf("B:\t");scanf("%lf",&B);

if (A==B || A>=B)

{

printf("\nВведен неверный интервал!\n\n");

system("pause");

exit(1);

}

system("cls");

break;

//case '2' (ввод коэффициэнтов)

case '2':

system("cls");

system("echo ----------------------------------------------------------");

printf("Введите коэффициэнт при X^5:\t");scanf("%lf",&a0);

printf("\nВведите коэффициэнт при X^4:\t");scanf("%lf",&a1);

printf("\nВведите коэффициэнт при X^3:\t");scanf("%lf",&a2);

printf("\nВведите коэффициэнт при X^2:\t");scanf("%lf",&a3);

printf("\nВведите коэффициэнт при X:\t");scanf("%lf",&a4);

printf("\nВведите коэффициэнт C:\t\t");scanf("%lf",&a5);

system("cls");

break;

//case '3' (ввод точности)

case '3':

system("cls");

system("echo ----------------------------------------------------------");

printf("Введите точность:\t");scanf("%lf",&t);

if (t<0.000001)

{

printf("\nВведена неверная точность!\n\n");

system("pause");

exit(1);

}

mx=dihotomy(A,B,-1,a0,a1,a2,a3,a4,a5,t);

mn=dihotomy(A,B,1,a0,a1,a2,a3,a4,a5,t);

system("cls");

break;

//case '4' (вывод ответа на экран)

case '4':

system("cls");

system("echo ----------------------------------------------------------");

printf("Интервал:");

out("\t(%lg,",A);out("%lg)\n\n",B);

printf("Точность:\t");

out("%lf\n\n",t);

printf("Ответ:\n\n");

out("MAX(x)=\t%lg\n",func(mx,a0,a1,a2,a3,a4,a5));out("x=\t%lg\n\n",mx);

out("MIN(x)=\t%lg\n",func(mn,a0,a1,a2,a3,a4,a5));out("x2=\t%lg",mn);

getch();

system("cls");

break;

//case 'e' (exit - выход)

case 'e':

printf("\n\nДля выхода из программы нажмите любую клавишу...");

getch();

exit(1);

break;

}

}

}

//-------------------------------------------------------------------

void menu()

{

system("echo ----------------------------------------------------------");

system("echo Кнопка 1 - Ввод интервала");

system("echo Кнопка 2 - Ввод коэффициэнтов");

system("echo Кнопка 3 - Ввод точности");

system("echo Кнопка 4 - Вывод ответа на экран");

system("echo ----------------------------------------------------------");

system("echo Кнопка e - Выход");

system("echo ----------------------------------------------------------");

}

//-------------------------------------------------------------------

void out(const char *format,double value)

{

printf(format,value);

}

//-------------------------------------------------------------------

double func(double x,double a0,double a1,double a2,double a3,double a4,double a5)//F(x)

{

return (a0*x*x*x*x*x + a1*x*x*x*x + a2*x*x*x + a3*x*x + a4*x + a5);

}

//-------------------------------------------------------------------

double dihotomy(double A, double B, int m,double a0,double a1,double a2,double a3,double a4,double a5,double t)//дихотомия

{

double L=abs(B-A);

double xn=(A+B)/2;

while (L>t)

{

double fn=m*func(xn,a0,a1,a2,a3,a4,a5);

double x1=A+L/4;

double x2=B-L/4;

double f1=m*func(x1,a0,a1,a2,a3,a4,a5);

double f2=m*func(x2,a0,a1,a2,a3,a4,a5);

if(f1<fn)

{

B=xn;

xn=x1;

L=B-A;

}

else if(f2<fn)

{

A=xn;

xn=x2;

L=B-A;

}

else if((f1>=fn) && (f2>=fn))

{

A=x1;

B=x2;

L=B-A;

}

}

return xn;

}

Библиографический список

программа функция оптимизация листинг

Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. -- 8-е изд. -- М.: Лаборатория Базовых Знаний, 2000.

Ананий В. Левитин Глава 11. Преодоление ограничений: Метод деления пополам. -- М.: «Вильямс», 2006. -- С. 476-480.

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