Реализация программы расчета задачи симплекс-метода

• СОДЕРЖАНИЕ
• 1. ПОСТАНОВКА ЗАДАЧИ
• 2. ОПИСАНИЕ АЛГОРИТМОВ
• 3. ПЕРЕЧЕНЬ ИДЕНТИФИКАТОРОВ
• 4. КРАТКОЕ ОПИСАНИЕ ПРОГРАММЫ
• 5. БЛОК-СХЕМА АЛГОРИТМА
• 5.1 Блок-схемы процедур
• 5.1.1 iteration
• 5.1.2 Newton
• 5.1.3 HalfDivide
• 5.1.4 Chordes
• 6. ПРОВЕРКА СЧЕТА ПО ПРОГРАММЕ
• ЗАКЛЮЧЕНИЕ
• ЛИСТИНГ ПРОГРАММЫ
• 1. ПОСТАНОВКА ЗАДАЧИ

Дано уравнение:

[0,1]

Сравнить методы деления отрезка пополам, хорд, касательных и итераций, поочередно используя их для решения одного и того же уравнения. Независимо от метода заканчивать построения, как только будет получено такое приближение x, для которого |f (x)|< ?,? = 0,01; 0,001;…10^-7. Для каждого из методов построить диаграмму и график изменения числа потребовавшихся приближений при переходе от одного значения? к другому и вывести данные числа в виде таблицы в файл.

2. ОПИСАНИЕ АЛГОРИТМОВ

МЕТОД ДЕЛЕНИЯ ОТРЕЗКА ПОПОЛАМ

Пусть дано уравнение f (x)=0, функция f (x) непрерывна на интервале [a, b]. Условие f (a)* f (b)<0 указывает тогда на наличие хотя бы одного корня на этом отрезке.

Поделим отрезок [a, b] пополам точкой c, координата которой c=(a+b)/2 и вычислим значение функции f©.

Возможны два случая:

а) f (a)*f (c)>0, т. е. значения функции на концах отрезка [a, c] одинаковы по знаку; тогда корень уравнения находится на отрезке [c, b] и отрезок [a, c] можно исключить из дальнейшего рассмотрения, перенеся точку a в точку c: a=c; f (a)=f© (рис. а);

б) f (a)*f (c)<0, т. е. значение функции на концах отрезка [a, c] противоположны по знаку; тогда корень находится на отрезке [a, c] и отрезок [c, b] можно исключить из дальнейшего рассмотрения, перенеся точку b в точку c: b=c (рис. б).

После исключения правой или левой половины отрезка продолжают деление пополам до тех пор, пока длина оставшегося интервала [a, b] не станет меньше некоторой заданной малой величины? , т. е. |b-a|

МЕТОД ХОРД

Нелинейная функция f (x) на отделенном интервале [а, b] заменяется линейной, в качестве которой берется хорда — прямая, стягивающая концы нелинейной функции. Эта хорда определяется как прямая, проходящая через точки с координатами (а, f (а)) и (b, f (b)). Имея уравнение хорды: у = cx + d, можно легко найти точку ее пересечения с горизонтальной осью, подставив в уравнение у = 0 и найдя из него x. Естественно, в полученной таким путем точке x₁ не будет решения, ее принимают за новую границу отрезка, где содержится корень. Через эту точку с координатами (x₁, f (x₁)) и соответствующую границу предыдущего интервала опять проводят хорду, находят x₂ и т. д. несколько раз, получая последовательность: х₃, х₄, х₅ …, сходящуюся к корню.

Алгоритм метода зависит от свойств функции f (х). Если f (b) f" (b)>0, то строящаяся на каждом этапе хорда имеет правый фиксированный конец и тогда алгоритм будет выглядеть так:

при этом последовательность х₁, х₂, х₃… будет приближаться к корню слева.

Если f (a) f''(a) > 0, то строящаяся при каждом этапе хорда имеет левый фиксированный («закрепленный») конец и алгоритм выглядит следующим образом:

при этом последовательность х₁, х₂, … будет приближаться к корню справа.

Условием прекращения пополнения последовательности является: |х_i+1 -х_i|

МЕТОД НЬЮТОНА

Идея, на которой основан метод, аналогична той, которая реализована в методе хорд, только в качестве прямой берется касательная, проводимая в текущей точке последовательности. Уравнение касательной находится по координате одной точки и углу наклона (значение производной). В качестве начальной точки в зависимости от свойств функции берется или левая точка: x₀ = а (если f (а) f" (a) > 0), или правая точка: x₀ = b (если f (b) f" (b)>0).

Алгоритм записывается следующим образом:

Условием прекращения пополнения последовательности является: |х_i+1 -х_i|

МЕТОД ИТЕРАЦИЙ

Предварительно исходное уравнение f (x) = 0 преобразуют к виду: f (х) = х, что является частным случаем более общей структуры: g (x) = f (x). Затем выбирают начальное значение х₀ и подставляют его в левую часть уравнения, но f (х₀) ≠ х₀, поскольку х₀ взято произвольно и не является корнем уравнения. Полученное уравнение f (х₀) = х₁ рассматривают как очередное приближение к корню. Его снова подставляют в левую часть уравнения f (х₁) и получают следующее значение х₂ (х₂= f (х₁)) и т. д., в общем случае х_i+1 = f (х_i). Получающаяся таким образом последовательность: х₀, х₁, х₂, х₃, х₄,… при определенных условиях может сходиться к корню х*.

Условием сходимости является |f'(х)| < 1 на [а, b].

Условием прекращения пополнения последовательности является: |х_i-х_i+1|

3. ПЕРЕЧЕНЬ ИДЕНТИФИКАТОРОВ

Модуль Form1 (форма программы)

отрезок хорда итерация идентификатор

Объекты формы

Процедуры формы Form1

1. newton — процедура решения уравнения методом касательных

2. iteration — процедура решения уравнения методом итераций

3. HalfDivide — процедура решения уравнения методом половинного деления

4. Chordes — процедура решения уравнения методом хорд

5. ShowNotice — процедура для вывода сообщения успешного решения поставленной задачи

6. Button1Click — реакция на нажатие кнопки «Решить». Вызов основных процедур и заполнение таблицы вывода, а также гистограмм.

7. FormCreate — процедура, которая заполняет шапку таблиц, задает разметку и начальные действия объектов при старте программы.

4. КРАТКОЕ ОПИСАНИЕ ПРОГРАММЫ

Входными данными являются:

— уравнение вида ;

— a — левое значение заданного промежутка;

— b — правое значение заданного промежутка;

Рассмотрим алгоритм работы программы.

При запуске программы пользователь видит на экране первую форму программы, на которой располагается заданное уравнение и поля для ввода промежутков (рис. 1).

Рисунок 1. Главная форма программы

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

Рисунок 2. Необходимые поля для заполнения

После ввода данных на форме необходимо нажать на кнопку Решить. После нажатия кнопки пользователь увидит сообщение о решенной задаче

Рисунок 3. Сообщение об успешном решении задачи

После нажатия кнопки ОК пользователь увидит на форме таблицу с результатами работы программы и 4 графика, соответствующие заданию:

Рисунок 4. Форма с выполненным заданием и результатами

5. БЛОК-СХЕМА АЛГОРИТМА

5.1 Блок-схемы процедур

5.1.1 iteration

5.1.2 newton

5.1.3 HalfDivide

5.1.4 Chordes

6. ПРОВЕРКА СЧЕТА ПО ПРОГРАММЕ

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

ЗАКЛЮЧЕНИЕ

В данном курсовом проекте я реализовал программу расчета задачи симплекс — метода. Программа была написана мной на объектно-ориентированном языке С++ в среде разработки Borland C++ Bulder 6. Данная среда программирования довольно широко охватывает потребности объектно-ориентированного программирования — она не только имеет огромный набор уже готовых компонентов, созданных в ней же самой, но и позволяет легко создавать свои объекты. Благодаря этой особенности, все компоненты сторонних разработчиков ничем не отличаются от стандартного набора и не требуют особых ухищрений, при добавлении их в среду и использовании в ней.

ЛИСТИНГ ПРОГРАММЫ

#include

#pragma hdrstop

#include

#include

#include «Unit1.h»

#pragma package (smart_init)

#pragma resource «*.dfm»

#define ABS (A) ((A) >= 0? (A): -(A))

TForm1 *Form1;

__fastcall TForm1: TForm1(TComponent* Owner)

: TForm (Owner)

{

}

double fs (double x)// первая производная

{

return 15*x*x-1;

}

double f (double x) // исходное уравнение

{

return 5*x*x*x-x-1;

}

long double f1(long double x) // сжимающая функция

{

return x*x;

}

void newton (double a, double b)// касательные

{

double c, cnext, c1;

double ex[6] = { 0.01, 0.001, 0.0001, 0.1, 0.1, 0.1 };

int i, count=0;

c=(a+b)/2; // подсчитал первое и нулевое значение

cnext=c-(f (c)/fs (c));

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

{

while (ABS (cnext-c)>ex[i])

{

c=cnext;

cnext=c-(f (c)/fs (c));

count++;

}

Form1->StringGrid1->Cells[3][i+1]=IntToStr (count);

}

}

void iteration (double a, double b)

{

long double x, xnext;

long double ex[6] = { 0.01, 0.001, 0.0001, 0.1, 0.1, 0.1 };

int i, count=0;

x=(a+b)/2;

xnext=f1(x);

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

{

while (ABS (xnext-x)>=ex[i])

{

x=xnext;

xnext=f1(x);

count++;

}

Form1->StringGrid1->Cells[4][i+1]=IntToStr (count);

}

}

void HalfDivide (double a, double b)

{ double c;

int i, count=0;

double epsilon;

double ex[6] = { 0.01, 0.001, 0.0001, 0.1, 0.1, 0.1 };

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

{

while (ABS (b-a)>ex[i])

{

c=(a+b)/2.0;

if (f (a)*f (c)<0.0)

{

b=c;

}

else

{

a=c;

}

count=count+1;

}

Form1->StringGrid1->Cells[1][i+1]=IntToStr (count);

}

}

void Chordes (double a, double b)

{ int i, count=0;

double ex[6] = { 0.01, 0.001, 0.0001, 0.1, 0.1, 0.1 };

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

{

while (ABS (b-a)>ex[i])

{

a = b — ((b — a) * f (b)/(f (b) — f (a)));

b = a — ((a — b) * f (a)/(f (a) — f (b)));

count++;

}

Form1->StringGrid1->Cells[2][i+1]=IntToStr (count);

}

}

void ShowNotice ()

{

MessageDlg («Задача решена», mtInformation, TMsgDlgButtons () << mbOK, 1200);

}

void __fastcall TForm1: Button1Click (TObject *Sender)

{

int i, j;

double c;

int count=0;

double a, b;

a=StrToFloat (Edit3->Text);

b=StrToFloat (Edit4->Text);

iteration (a, b);

Chordes (a, b);

HalfDivide (a, b);

newton (a, b);

ShowNotice ();

Label1->Visible=true;

Label3->Visible=true;

Label4->Visible=true;

Label5->Visible=true;

for (i=1;i<=StringGrid1->RowCount-1;i++)

{

Series1->AddXY (i, StrToInt (StringGrid1->Cells[1][i]), clBlack);

Series8->AddXY (i, StrToInt (StringGrid1->Cells[3][i]), clBlack);

Series5->AddXY (i, StrToInt (StringGrid1->Cells[2][i]), clBlack);

Series2->AddXY (i, StrToInt (StringGrid1->Cells[4][i]), clBlack);

}

Form1->StringGrid1->Visible=True;

Form1->Chart1->Visible=True;

Form1->Chart2->Visible=True;

Form1->Chart3->Visible=True;

Form1->Chart4->Visible=True;

}

//ShowNotice ();

void __fastcall TForm1: FormCreate (TObject *Sender) // внешний вид таблицы, а также разметка и действия обьектов при старте формы

{

int i;

Form1->StringGrid1->ColCount=5;

Form1->StringGrid1->RowCount=7;

Form1->StringGrid1->Cells[1][0]="Метод половинного деления" ;

Form1->StringGrid1->Cells[2][0]="Метод хорд" ;

Form1->StringGrid1->Cells[3][0]="Метод касательных" ;

Form1->StringGrid1->Cells[4][0]="Метод итераций" ;

Form1->StringGrid1->Cells[0][1]="0.01″ ;

Form1->StringGrid1->Cells[0][2]="0.001″ ;

Form1->StringGrid1->Cells[0][3]="0.0001″ ;

Form1->StringGrid1->Cells[0][4]="0.1″ ;

Form1->StringGrid1->Cells[0][5]="0.1″ ;

Form1->StringGrid1->Cells[0][6]="0.1″ ;

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

Form1->StringGrid1->ColWidths[i]=175;

Form1->StringGrid1->RowHeights[0]=30;

Form1->StringGrid1->ColWidths[0]=100;

Edit1->Clear ();

Edit3->Clear ();

Edit4->Clear ();

}