Логическая структура программы

 

Разработанное по заданию программное средство состоит из двух основных логических модулей:

· Модуль, реализующий всю основную логику приложения и содержащий в своей основе методы реализации алгоритма метода Нелдера-Мида.

· Модуль графического интерфейса, содержащий все элементы взаимодействия пользователя с программой и осуществляющий представление на экране информации, сформированной посредством класса.

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

x1 = Convert.ToDouble(textBox2.Text);

           x2 = Convert.ToDouble(textBox3.Text);

           func = textBox1.Text;

           vpx1 = Convert.ToDouble(textBox5.Text);

           vpx2 = Convert.ToDouble(textBox4.Text);

           step = Convert.ToDouble(textBox6.Text);

           ogran = textBox9.Text;

           fun = new double[1000];

           mainx1 = new double[1000];

           mainx2 = new double[1000];

Если данные являются корректными, то происходит преобразование набора введенных в поля коэффициентов в необходимый для работы программы формат – массив чисел с запятой:

fun = new double[1000];

           mainx1 = new double[1000];

           mainx2 = new double[1000];

Далее метод, листинг которого приведен в приложении A, производит все необходимые вычисления и возвращает на вывод пользователю подробное решение задачи.

Также интерес к рассмотрению в данном пункте представляют методы, реализующие часть алгоритма метода Нелдера-Мида:

· Метод исследующего поиска.

// Шаг 1. Инициализация

       count = 0;

       fun[count] = regexpr(x1, x2);

       textBox8.AppendText("Вычислим значение функции в т. (" + x1 + "," + x2 + "). f=" + fun[count] + Environment.NewLine);

       mainx1[0] = x1;

       mainx2[0] = x2;

       textBox8.AppendText("-----------------------------------------------------------------------------" + Environment.NewLine);

       proverka = 1;

       f_old = fun[count];

       // Шаг 2. Исследующий поиск

       shag2:

       textBox8.AppendText("Исследующий поиск: " + Environment.NewLine);

       iflag = false;

       proverka = proverka + 1;

       // исследующий поиск x1

       xt1 = x1 + vpx1;

       ipoisk(xt1, x2, 0);

       // исследующий поиск x2

       xt2 = x2 + vpx2;

       ipoisk(x1, xt2, 1);

       if (iflag == false)

       { // исследующий поиск x1 в противоположном направлении

           xt1 = x1 - vpx1;

           ipoisk(xt1, x2, 0);

           // исследующий поиск x2 в противоположном направлении

           xt2 = x2 - vpx2;

           ipoisk(x1, xt2, 1);

       }

       // Шаг 3. Проверка успеха исследующего поиска

       if (iflag == true)

           goto predshag5;

       else

           goto shag4;

       predshag5:

           count = count + 1;

           mainx1[count] = x1;

           mainx2[count] = x2;

           fun[count] = regexpr(mainx1[count], mainx2[count]);

           textBox8.AppendText("x" + count + "=(" + x1 + "," + x2 + ")=" + fun[count] + Environment.NewLine);

           textBox8.AppendText("-----------------------------------------------------------------------------" + Environment.NewLine);

Изначально за ведущий столбец принимается первый столбец таблицы, а затем происходит поочередное сравнение оценок других столбцов, и, если оценка другого столбца больше, данный столбец становится ведущим. Сравнение реализуется при помощи цикла for.

· Поиск по образцу.

kp1_old = mainx1[count-1];

           kp2_old = mainx2[count-1];

       shag5:

           kp1 = mainx1[count] + (mainx1[count] - kp1_old);

           kp2 = mainx2[count] + (mainx2[count] - kp2_old);

           f = regexpr(kp1, kp2);

           proverka = proverka + 1;

           if (proverka > 100)

               goto konec2;              

           textBox8.AppendText("Поиск по образцу:" + Environment.NewLine);

           textBox8.AppendText("p(" + kp1 + "," + kp2 + ")=" + f + Environment.NewLine);

                    // Шаг 6. Исследующий поиск после поиска по образцу

           textBox8.AppendText("Исследующий поиск после поиска по образцу: " + Environment.NewLine);

           f_old = f;

           iflag = false;

           x1 = kp1;

           x2 = kp2;

           // исследующий поиск x1

           xt1 = x1 + vpx1;

           ipoisk(xt1, x2, 0);

           // исследующий поиск x2

           xt2 = x2 + vpx2;

           ipoisk(x1, xt2, 1);

           if (iflag == false)

           { // исследующий поиск x1 в противоположном направлении

               xt1 = x1 - vpx1;

               ipoisk(xt1, x2, 0);

               // исследующий поиск x2 в противоположном направлении

               xt2 = x2 - vpx2;

               ipoisk(x1, xt2, 1);

           }

           if (iflag == false) goto shag4;

           textBox8.AppendText("f^k+1 = " + f + Environment.NewLine);

           textBox8.AppendText("f^k = " + fun[count] + Environment.NewLine);

               

           // Шаг 7. Выполняется ли неравенство f(x^(k+1))<f(x^k)?

               

           if (f < fun[count])

           {

               kp1_old = kp1;

               kp2_old = kp2;

               fkm1 = regexpr(kp1, kp2);

               count++;

               mainx1[count] = x1;

               mainx2[count] = x2;

               fun[count] = regexpr(mainx1[count], mainx2[count]);

               textBox8.AppendText("x^k-1(" + kp1_old + "," + kp2_old + ")=" + fkm1 + Environment.NewLine);

               textBox8.AppendText("---- x" + count + "=(" + x1 + "," + x2 + ")=" + fun[count] + "----" + Environment.NewLine);

               textBox8.AppendText("-----------------------------------------------------------------------------" + Environment.NewLine);

               goto shag5;

           }

           else

           {

               x1 = mainx1[count];

               x2 = mainx2[count];

               goto shag4;

           }

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

 

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

 

При запуске программы отображается главное окно (Рисунок 5), в котором происходит ввод исходных данных и последующее отображение решения задачи.

 

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

 

Если работа с программой вызывает затруднения, обратите внимание на справку в нижней части окна.

Далее вводятся значения в поля ввода. Сначала вводится выражение для целевой функции, потом параметры симплекса, начальные значения (начальная точка), точность и максимальное количество итераций. На рисунке 6 показана программа с заполненными полями ввода:

Рисунок 6 – Пример заполнения полей ввода.

 

Следующим после заполнения полей ввода действием является нажатие кнопки “Пуск” программы. Сразу после этого в поле вывода, расположенном в правой части окна, будет представлено решение задачи (Рисунок 7):

 

Рисунок 7 – Вывод программой решения задачи.

 

Заключение

 

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

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

Симплекс-метод Нелдера-Мида является очень эффективным алгоритмом поиска экстремума функции многих переменных, не накладывающим ограничений на гладкость функции. На каждой итерации алгоритма производится как правило одно-два вычисления значений функции, что чрезвычайно эффективно если эти вычисления очень медленны. Кроме того, алгоритма очень прост в реализации. Главным же его недостатком является отсутствие теории сходимости и наличие примеров, когда метод расходится даже на гладких функциях.

Разработанное по заданию программное средство, имеющее в своей основе алгоритм метода Нелдера-Мида, позволяет автоматизировано решать задачи нелинейного программирования и предоставлять результат в удобном для пользователя виде с использованием графического интерфейса.

Непосредственные результаты исследований по данной теме курсовой работы выглядят следующим образом:

§ Сформирована постановки задачи нелинейного программирования (ЗНП) и изучена математическая модель;

§ Проведен сравнительный обзор методов покоординатной оптимизации, позволяющих решать данный класс задач оптимизации;

§ Рассмотрен алгоритм работы метода Нелдера-Мида;

§ Разработан программный продукт, позволяющий автоматизировано решать ЗНП;

§ В процессе разработки получены теоретические и практические навыки использования изученного алгоритма.

 

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

 

1. Белецкая С.Ю. Технология автоматизированного решения задач оптимизации: учеб. пособие / С.Ю. Белецкая. – Воронеж: ВГТУ, 2009. – 179 с.

2. Белецкая С.Ю. Математические методы поиска оптимальных решений: учеб.пособие / С.Ю. Белецкая. – Воронеж: ВГТУ, 2006. – 200 с.

3. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР / Д.И. Батищев, Я.Е. Львович, В.Н. Фролов. – Воронеж: ВГТУ, 1997. – 416 с.

4. Банди Б. Основы линейного программирования / Б. Банди. – М.: Радио и связь, 1989. – 86 с.

5. Пантелеев А.В. Методы оптимизации в примерах и задачах: учеб.пособие / А.В. Пантелеев, Т.А. Летова. – М.: Высш. шк., 2002. – 544 с.

6. Галеев Э.М. Оптимизация: Теория, примеры, задачи. – М.: Либрком, 2010. – 336 с.

7. Гончаров. В.А. Методы оптимизации: учеб.пособие / А.В. Гончаров. – М.: Высшее образование, 2009. – 191 с.

8. Васильев Ф.П. Методы оптимизации. – М.: Факториал пресс, 2002. – 824 с.

9. Шилд Г. Java 8. Полное руководство – 9-е изд. – CПб.: Издательский дом "Вильяме", 2015. – 1 376 с.

 

 

ПРИЛОЖЕНИЕ A

(обязательное)

 

Form1.cs

 

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

using info.lundin.math;

 

namespace Method_Hook_Jeeves

{

public partial class MainForm: Form

{

   string ogran;

   double f; // функция f(x1,x2)

   double x1, x2, xt1, xt2; // точки

   double vpx1, vpx2; // вектор приращения

   double step; // коэффициент уменьшения шага

   double acc; // точность

   string func; // строка для сохранения функции

   Boolean flag; //флаг проверки

   double[] fun; //массив хранящий значения функций

   int count; //счетчик

   Boolean xflag; //переменная отражает успех или неудачу исследующего поиска x1,x2

   double f_old; // переменная нужна для сравнения новой функции

   double fkm1; // значение предыдущей функции

   Boolean iflag; // флаг отражает был ли весь поиск успешным или нет

   double[] mainx1, mainx2; //массивы хранящие базовые точки

   double kp1, kp2, kp1_old, kp2_old; // точки, построенные при движении по образцу

 

   private void button2_Click(object sender, EventArgs e)

   {

       this.Width = 652;

   }

 

   private void button1_Click(object sender, EventArgs e)

   {

       this.Width = 387;

   }

 

   double ftest,x1test,x2test; // функция для проверки поля

   int proverka; // счетчик для предотвращения зацикливания

 

   public MainForm()

   {

       InitializeComponent();

   }

 

   private void calculation_Click(object sender, EventArgs e)

   {

       // параметры формы

       try

       {

           x1 = Convert.ToDouble(textBox2.Text);

           x2 = Convert.ToDouble(textBox3.Text);

           func = textBox1.Text;

           vpx1 = Convert.ToDouble(textBox5.Text);

           vpx2 = Convert.ToDouble(textBox4.Text);

           step = Convert.ToDouble(textBox6.Text);

           ogran = textBox9.Text;

           fun = new double[1000];

           mainx1 = new double[1000];

           mainx2 = new double[1000];

           flag = true;

           if (step <= 1)

           {

               MessageBox.Show("Шаг должен быть > 1", "Неверные данные", MessageBoxButtons.OK, MessageBoxIcon.Warning);

               flag = false;

           }

           acc = Convert.ToDouble(textBox7.Text);

           if (acc >= 1 || acc < 0)

           {

               MessageBox.Show("Точность должна быть <1 и >0", "Неверные данные", MessageBoxButtons.OK, MessageBoxIcon.Warning);

               flag = false;

 

           }

           try

           {

               x1test = x1;

               x2test = x2;

               ExpressionParser parser = new ExpressionParser();

               parser.Values.Add("x1", x1test);

               parser.Values.Add("x2", x2test);

               ftest = parser.Parse(textBox1.Text);

           }

           catch

           {

               MessageBox.Show("Возникла ошибка при вычислении функции", "Неверные данные", MessageBoxButtons.OK, MessageBoxIcon.Warning);

               flag = false;

           }

           if (flag == true) start();

 

       }

       catch (FormatException)

       {

           MessageBox.Show("Введены некорректные данные в поля параметров", "Неверные данные", MessageBoxButtons.OK, MessageBoxIcon.Warning);

       }

          

   }

 

   public double regexpr(double x, double y)

   {

       ExpressionParser parser = new ExpressionParser();

       parser.Values.Add("x1", x);

       parser.Values.Add("x2", y);

       return parser.Parse(textBox1.Text);

 

   }

 

   public Boolean uspex(double a, double b)

   {

       if (a < b)

           return true;

       else

           return false;

   }

 

   public void ipoisk(double xodin, double xdva, int p)

   {

       f = regexpr(xodin, xdva);

       xflag = uspex(f, f_old);

       if (p == 0)

           textBox8.AppendText("Фиксируя переменную x" + (p + 1) + "=" + xdva + ", дадим приращение x" + Environment.NewLine);

       else

           textBox8.AppendText("Фиксируя переменную x" + (p + 1) + "=" + xodin + ", дадим приращение x" + Environment.NewLine);

       textBox8.AppendText("f(" + xodin + "," + xdva + ")= " + f + " < " + f_old + "? " + xflag + Environment.NewLine);

       if (xflag == true)

       {

           if (p == 0)

               x1 = xt1;

           else

               x2 = xt2;

          // f_old = f;

           iflag = true;

       }

           

   }

 

 

   public void start()

   {

       // Шаг 1. Инициализация

       count = 0;

       fun[count] = regexpr(x1, x2);

       textBox8.AppendText("Вычислим значение функции в т. (" + x1 + "," + x2 + "). f=" + fun[count] + Environment.NewLine);

       mainx1[0] = x1;

       mainx2[0] = x2;

       textBox8.AppendText("-----------------------------------------------------------------------------" + Environment.NewLine);

       proverka = 1;

       f_old = fun[count];

       // Шаг 2. Исследующий поиск

       shag2:

       textBox8.AppendText("Исследующий поиск: " + Environment.NewLine);

       iflag = false;

       proverka = proverka + 1;

       // исследующий поиск x1

       xt1 = x1 + vpx1;

       ipoisk(xt1, x2, 0);

       // исследующий поиск x2

       xt2 = x2 + vpx2;

       ipoisk(x1, xt2, 1);

       if (iflag == false)

       { // исследующий поиск x1 в противоположном направлении

           xt1 = x1 - vpx1;

           ipoisk(xt1, x2, 0);

           // исследующий поиск x2 в противоположном направлении

           xt2 = x2 - vpx2;

           ipoisk(x1, xt2, 1);

       }

       // Шаг 3. Проверка успеха исследующего поиска

       if (iflag == true)

           goto predshag5;

       else

           goto shag4;

       predshag5:

           count = count + 1;

           mainx1[count] = x1;

           mainx2[count] = x2;

           fun[count] = regexpr(mainx1[count], mainx2[count]);

           textBox8.AppendText("x" + count + "=(" + x1 + "," + x2 + ")=" + fun[count] + Environment.NewLine);

           textBox8.AppendText("-----------------------------------------------------------------------------" + Environment.NewLine);

       // Шаг 5. Поиск по образцу

           kp1_old = mainx1[count-1];

           kp2_old = mainx2[count-1];

       shag5:

           kp1 = mainx1[count] + (mainx1[count] - kp1_old);

           kp2 = mainx2[count] + (mainx2[count] - kp2_old);

           f = regexpr(kp1, kp2);

           proverka = proverka + 1;

           if (proverka > 100)

               goto konec2;  

           

           /*if (f >= fun[count])

             {

               kp1 = kp1_old;

               kp2 = kp2_old;

               f = regexpr(kp1, kp2);

           }*/

 

           textBox8.AppendText("Поиск по образцу:" + Environment.NewLine);

           textBox8.AppendText("p(" + kp1 + "," + kp2 + ")=" + f + Environment.NewLine);

               

           // Шаг 6. Исследующий поиск после поиска по образцу

           textBox8.AppendText("Исследующий поиск после поиска по образцу: " + Environment.NewLine);

           f_old = f;

           iflag = false;

           x1 = kp1;

           x2 = kp2;

           // исследующий поиск x1

           xt1 = x1 + vpx1;

           ipoisk(xt1, x2, 0);

           // исследующий поиск x2

           xt2 = x2 + vpx2;

           ipoisk(x1, xt2, 1);

           if (iflag == false)

           { // исследующий поиск x1 в противоположном направлении

               xt1 = x1 - vpx1;

               ipoisk(xt1, x2, 0);

               // исследующий поиск x2 в противоположном направлении

               xt2 = x2 - vpx2;

               ipoisk(x1, xt2, 1);

           }

           if (iflag == false) goto shag4;

           textBox8.AppendText("f^k+1 = " + f + Environment.NewLine);

           textBox8.AppendText("f^k = " + fun[count] + Environment.NewLine);

               

           // Шаг 7. Выполняется ли неравенство f(x^(k+1))<f(x^k)?

           

           if (f < fun[count])

           {

               kp1_old = kp1;

               kp2_old = kp2;

               fkm1 = regexpr(kp1, kp2);

               count++;

               mainx1[count] = x1;

               mainx2[count] = x2;

               fun[count] = regexpr(mainx1[count], mainx2[count]);

               textBox8.AppendText("x^k-1(" + kp1_old + "," + kp2_old + ")=" + fkm1 + Environment.NewLine);

               textBox8.AppendText("---- x" + count + "=(" + x1 + "," + x2 + ")=" + fun[count] + "----" + Environment.NewLine);

               textBox8.AppendText("-----------------------------------------------------------------------------" + Environment.NewLine);

               goto shag5;

           }

           else

           {

               x1 = mainx1[count];

               x2 = mainx2[count];

               goto shag4;

           }

   // Шаг 4. Проверка на окончание поиска

       shag4:

           

       if (Math.Sqrt(vpx1*vpx1+vpx2*vpx2) <= acc)

       {

 

           textBox8.AppendText("Неравенство выполняется: " + Math.Sqrt(vpx1 * vpx1 + vpx2 * vpx2) + "<=" + acc + Environment.NewLine);

           goto konec;

       }

       else

       {

           vpx1 = vpx1 / step;

           vpx2 = vpx2 / step;

           textBox8.AppendText("dX1=" + vpx1 + " dX2=" + vpx2 + Environment.NewLine);

           goto shag2;

       }

   konec:

       textBox8.AppendText("Ответ: x(" + kp1 + ";" + kp2 + "),f(x)=" + f_old);

   konec2:

       textBox8.AppendText("Верное решение найдено");

 

   }

}

}