Метод Пауэлла

 

 

 

Положим d₀ = d_n , i = 0, у⁰ = х⁰, k= 0.

Шаг 2. Найти yⁱ⁺¹ = y ⁱ +t_i d_i где шаг t_i находится в результате поиска ми-нимума функции f(yⁱ+t_id_i) по t_i одним из методов одномерной минимизации.

Шаг 3. Проверить выполнение условий:

а) если i < n -1, положить i= i +1 и перейти к шагу 2;

б) если I = n -1, проверить успешность поиска по n первым направлениям.

Если  у ⁿ = у°, то поиск завершить: х* =yⁿ, иначе положить i=i+1 и перейти к шагу 2;

в) если i = n, проверить успешность поиска по n последним направлениям. Если y ⁿ⁺¹ = у ¹, поиск завершить: х^* = у ⁿ⁺¹, иначе перейти к шагу 4 для построения сопряженного направления.

Шаг 4. Положить х^k+1 = уⁿ⁺¹ и проверить условие окончания:

а) если |||х^k+1 - х^k || | < ε, то поиск завершить: х* = х^k+1;

б) иначе положить: d₀ = d_n = уⁿ⁺¹ - у¹ (новое направление);

(исключается старое направление).

Если  при этом rang (,...,)= n, то новая система направлений линейно независима. В этом случае положить: d_i =d_i , i = 0,1,...,n; k =k +1, i = 0, у⁰ = x^k+i и перейти к шагу 2.

Если  rang(,...,)< n, то новая система направлений линейно зависима. Тогда следует продолжать поиск в старых направлениях. Для этого положить: d_i =d_i , i = 0,1,...,n; у⁰ = x^k+1, k = k + 1, i = 0 и перейти к шагу 2.

 

Рассмотрим  алгоритм метода сопряженных направлений, представленный в виде блок схемы. Алгоритм начинается с ввода данных , где x⁰ - это координата начальной точки, ε – число для окончания алгоритма (ε > 0), d₁ и d₂ -начальные направления поиска (). Выход их алгоритма возможен в трех случаях:

При минимум функции будет найден в т. .

При минимум функции будет найден в т. .

При |||| < минимум функции будет найден в т. .

 

 

Рисунок 1.3 – Продолжение блок схемы алгоритма метода Пауэлла

5.   Пример поиска минимума функции методом Пауэлла

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

1⁰ ) x⁰ = (8; 9)^T, , ε = 0,1, y⁰ = x⁰ = (8;9)^T

i=0, k=0;

2⁰) y¹ = y⁰ +t₀ d₀ = (8;9)^T + t₀ (0;1)^T = (8, 9 + t₀);

f (8, 9 + t₀) = 8³ + (9 + t₀)² – 24 – 2(9 + t₀) + 2 = t₀² + 16t₀ + 553;

t₀ = -8; y¹ = (8;1)^T;

3⁰) Т.к. i < n-1 положим i=1 и перейдем к шагу 2;

2¹) y² = y¹ + t₁ d₁ = (8;1)^T + t₁ (1;0)^T = (8 + t₁;1)^T;

f (8 + t₁;1) = t₁³ + 24t₁² + 189t₁;

t₁ = -7; y² = (1;1);

3¹) i = n-1; y² ≠ y⁰, i =2;

2² ) y³ = y² + t₂ d₂ = (1; 1)^T + t₂ (0;1)^T = (1; 1+t₂);

t₂ = 0; y³ = (1;1)^T;

3²) i = n = 2;

y³ ≠ y¹;

4⁰) x¹ = y³ = (1;1)^T;

Т.к. || (1;1)^T – (8;9)^T || = 10,63 > ε положим = d₂ = y³ – y¹ = (-7;0)^T,

= d₂ = (0;1)^T;

;

 

Новая система  направлений линейно независима.

 

d₀ = = (-7;0)^T;

d₁ = = (0;1)^T;

d₂ = = (-7;0)^T;

i = 0, k = 1, y⁰ = x¹ = (1;1)^T;

2³) y¹ = y⁰ +t₀ d₀ = (1;1)^T + t₀ (-7;0)^T = (1 - 7t₀ ;1);

t_o = 0; y¹ = (1;1);

3³) i < n-1 положим i=1 и перейдем к шагу 2;

2⁴) y² = y¹ + t₁ d₁ = (1;1)^T + t₁ (0;1)^T = (1;1 + t₁)^T;

t₁ = 0; y² = (1;1);

3⁴) i = n-1; y² = y⁰;

x^* = y² = (1;1)^T.

2. Описание  программной части. Выбор среды  программирования

Для создания программного продукта использовалась интегрированная среда разработки приложений с графическим интерфейсом  технологии Win-dows Form Visual Studio 2010 на языке C#.

C# — объектно-ориентированный  язык программирования. Разработан в 1998—2001 годах группой инженеров под руководством Андерса Хейлс-берга в компании Microsoft.

C# относится  к семье языков с C-подобным  синтаксисом, из них его син-таксис наиболее близок к C++ и Java.

Переняв многое от своих предшественников — языков C++, Java, Delphi, Модула и Smalltalk — С#, опираясь на практику их использования, исключает некоторые модели, зарекомендовавшие себя как проблематичные при разработке программных систем, например, C# не поддержи-вает множественное наследование классов (в отличие от C++).

Название «Си  шарп» (До диез) происходит от музыкальной нотации, где знак диез, прибавляемый к основному обозначению ноты, означает повышение соответствующего этой ноте звука на полутон.[4] Это аналогично названию языка C++, где «++» обозначает, что переменная должна быть увеличена на 1.

Вследствие  технических ограничений на отображение (стандартные шрифты, браузеры и  т. д.) и того обстоятельства, что  знак диез ♯​ не представ-лен на стандартной клавиатуре, знак номера # был выбран для представления знака диез при записи имени языка программирования.^[5] Это соглашение отражено в Спецификации Языка C# ECMA-334.^[6] Тем не менее, на практике (например, при размещении рекламы и коробочном дизайне^[7]), Майкрософт использует предназначенный музыкальный знак.

Названия языков программирования не принято переводить, поэтому зачастую язык называют по-английски  «Си шарп».

C# является мощным объектным языком с возможностями наследования и универсализации.

C# является наследником языков С/С++, сохраняя лучшие черты этих популярных языков программирования. Общий с этими языками синтаксис, знакомые операторы языка облегчают переход программистов от C++ к С#.

 

3. Руководство пользователя

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

После запуска  программного продукта приложение примет вид как показано на рисунке 3.1.

 

 

Рисунок 3.1 – Главное окно программы

 

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

 

Рисунок 3.2 – Ввод данных

 

 

При нажатии  на кнопку «Расчитать» будет выведено решение метода Пауэла (рис. 3.3,3.4).

 

 

Рисунок 3.3 – Вывод результата

 

 

Рисунок 3.4 – Вывод результата

 

 

Для сохранения решения задачи нужно нажать на кнопку «Сохранить в файл», после чего откроется диалоговое окно (рис.3.5) для выбора места хранения файла и его (файла) названия. Решение примера будет сохранено в текстовый файл с разрешением *.txt.

 

 

Рисунок 3.5 – Диалоговое окно сохранения файла.

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

Рассмотрим основные фрагменты программного продукта, реализующий «метод Пауэлла».

 

Нахождение экстремума функции f (yⁱ + t_i d_i ) по t_i осуществляется функцией Extremum одним из методов одномерной минимизации: «Фибоначи».

 

private double extremum(double[]u) // u[] это d[]

{

double a = -2 * y[0];

double b = 2 * y[0];

double eps = (b-a)/50;

double l = (b-a)/10;

int g = 0; //счетчик

double s; //y

double w; //z

step_3: s = (a + b - eps) / 2;

w = (a + b + eps) / 2;

if (Function_for_search_extremum(y,u,s) <= Function_for_search_extremum(y, u, w))

{

b = w;

}

else

{

a = s;

}

if (Math.Abs(b - a) <= l)

return (a + b) / 2;

else

{

g++;

goto step_3;

}

}

 

Функция Function_for_search_extremum необходима для нахождения значения функции при поиске экстремума.

 

private double Function_for_search_extremum(double[] y, double[] u, double t)

{

double Fx = Math.Pow((y[0] + t * u[0]), 3) + Math.Pow((y[1] + t * u[1]), 2) - 3 * (y[0] + t * u[0]) - 2 * (y[1] + t * u[1]) + 2;

return Fx;

}

 

 

Для вычисления ранга матрицы используется метод Rang_matrici.

 

private int Rang_matrici(double [,]Matrica)

{

if(Matrica[1,0] != 0)

for (int i = 1; i < 2; i++)

{

double mnojitel = (Matrica[0, 0] / Matrica[i, 0]) * (-1);

for (int j = 0; j < 2; j++)

{

Matrica[i, j] = Matrica[i,j] * mnojitel + Matrica[i-1, j];

}

}

int k;

int y = 0;

for (int i = 0; i < 2; i++)

{

k = 0;

for (int j = 0; j < 2; j++)

{

if (Matrica[i, j] == 0)

k++;

}

if (k == 2)

y++;

}

int rang = 2 - y;

return rang;

}

Запись полученного решения, хранящееся в объекте RichTextBox1, записывается в текстовый файл спомощью функции MenuFileSaveAs().

 

private void MenuFileSaveAs()

{

saveFileDialog1.Filter = "Text files|*.txt";

if (saveFileDialog1.ShowDialog() == DialogResult.OK && saveFileDialog1.FileName.Length > 0)

{

richTextBox1.SaveFile(saveFileDialog1.FileName, RichTextBoxStreamType.UnicodePlainText);

}

}

 

А так же контролируются вводимые данные в элементы управления Text-Box. Пользователь может вводить только цифры и запятую. Проверка осуществляется при нажатии любой клавиши.

 

private void textX0_KeyPress(object sender, KeyPressEventArgs e)

{

if (e.KeyChar != 8 && (e.KeyChar < 48 || e.KeyChar > 57 ))

e.Handled = true;

if (e.KeyChar == 44)

e.Handled = false;

}

 

Выводы

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

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

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

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

- решение заданной  функции методом Пауэлла;

- вывод результата  и ход решения в текстовый  объект;

- вывод ошибок, при условии, что вводимые данные  не корректны;

- запись решения  функции в текстовый файл.

 

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

1.Акулич, И.Л. Математическое программирование в примерах и задачах [Текст] / И.Л.Акулич – Москва 1986.

2.Банди, Б.А. Методы оптимизации вводный курс [Текст] / Б.А.Банди – Москва 1988.

3.Белецкая, С.Ю. Решение задач математического программирования [Текст] / С.Ю.Белецкая – Воронеж 2001.

4.Карманов, В.Г. Математическое программирование Текст] / В.Г.Карманов – Москва 1975.

5. Пантелеев, А.В. Методы оптимизации в примерах и задачах Текст] / А.В.Пантелеев – Москва 2005. – С. 544.

 

Приложение А

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

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;

using System.IO;

using System.Net;

using System.Net.Sockets;

using System.Runtime.Serialization;

using System.Runtime.Serialization.Formatters;

using System.Runtime.Serialization.Formatters.Binary;

 

 

namespace Sopr_Napr

{

    public partial class Form1 : Form

    {

        double[,] Matrica = new double[2, 2];

        double[] x = new double[2];

        double E;

        double[] d1 = new double[2];

        double[] d2 = new double[2];

        double[] d0 = new double[2];

        int i;

        int k;

        int n = 2;

        int j;

        double[] y = new double[2];

        double[] y1 = new double[2];

        double[] y0 = new double[2];

        double[] x_st = new double[2];

        double[] d1_n = new double[2];

        double[] d2_n = new double[2];

        double[] d0_n = new double[2];

 

 

 

        public Form1()

        {

            InitializeComponent();

        }

        private int Rang_matrici(double[,] Matrica)

        {

            if (Matrica[1, 0] != 0)

                for (int i = 1; i < 2; i++)

                {

                    double mnojitel = (Matrica[0, 0] / Matrica[i, 0]) * (-1);

                    for (int j = 0; j < 2; j++)

                    {

                        Matrica[i, j] = Matrica[i, j] * mnojitel + Matrica[i - 1, j];

                    }

                }

            int k;

            int y = 0;

            for (int i = 0; i < 2; i++)

            {

                k = 0;

                for (int j = 0; j < 2; j++)

                {

                    if (Matrica[i, j] == 0)

                        k++;

                }

                if (k == 2)

                    y++;

            }

            int rang = 2 - y;

            return rang;

        }

        private double Function_for_search_extremum(double[] y, double[] u, double t)

        {

            double Fx = Math.Pow((y[0] + t * u[0]), 3) + Math.Pow((y[1] + t * u[1]), 2) - 3 * (y[0] + t * u[0]) - 2 * (y[1] + t * u[1]) + 2;

            return Fx;

        }