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

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×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,1

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

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

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,1

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

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

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,1

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

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

3.5 Сообщения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include «stdafx.h»

#include

#include

#include

#include

#include

//—————————————————————————————————;

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Введен неверный интервал! nn»);

system («pause»);

exit (1);

}

system («cls»);

break;

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

case '2':

system («cls»);

system («echo —————————————————————————————»);

printf («Введите коэффициэнт при X⁵:t»);scanf («%lf» ,&a0);

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

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

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

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

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

system («cls»);

break;

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

case '3':

system («cls»);

system («echo —————————————————————————————»);

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

if (t<0.1)

{

printf («nВведена неверная точность! nn»);

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)nn», B);

printf («Точность:t»);

out («%lfnn», t);

printf («Ответ:nn»);

out («MAX (x)=t%lgn», func (mx, a0, a1,a2,a3,a4,a5));out («x=t%lgnn», mx);

out («MIN (x)=t%lgn», func (mn, a0, a1,a2,a3,a4,a5));out («x2=t%lg», mn);

getch ();

system («cls»);

break;

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

case 'e':

printf («nnДля выхода из программы нажмите любую клавишу…»);

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

{

B=xn;

xn=x1;

L=B-A;

}

else if (f2

{

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.