467

Градієнтний метод числової оптимізації задач нелінійного програмування

Лабораторная работа

Информатика, кибернетика и программирование

Застосування градієнтного методу, коли обмеження на область зміни змінних х відсутні. Застосування градієнтного методу, коли наявні обмеження на область зміни змінних х. ознайомлення з градієнтним методом числової оптимізації, набуття навиків розв’язку та аналізу задач нелінійного програмування градієнтним методом.

Украинкский

2013-01-06

1.16 MB

130 чел.

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ  УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Кафедра АСУ

Звіт

із лабораторної роботи №13

«Градієнтний метод числової оптимізації                                                                                          задач нелінійного програмування»

з дисципліни

“Математичні методи дослідження операцій”

Виконав:

студент групи КН – 22

Приступа Олег

Прийняв:

старший викладач Балич Б.І.

Львів – 2012


Мета роботи: ознайомлення з градієнтним методом числової оптимізації, набуття навиків  розв’язку та аналізу задач нелінійного програмування градієнтним методом.

  1.  Короткі теоретичні відомості

Градієнтні методи належать до наближених числових методів розв’язування задач нелінійного програмування, оскільки дають точний розв’язок за нескінченне і лише в окремих випадках за скінченне число кроків. З їх використанням  можна розв’язувати будь-яку задачу нелінійного програмування, знаходячи, як правило, лише локальний екстремум. Тому застосування цих методів дає найбільший ефект для розв’язування задач випуклого програмування, де локальний екстремум є одночасно і глобальним.

1.1.  Застосування градієнтного методу, коли обмеження на область зміни змінних х відсутні

Розглянемо задачу максимізації функції f(х), коли обмеження на область зміни змінних х відсутні. Пошук екстремального значення функції f(х) можна починати з будь-якого допустимого розв’язку, наприклад, з точки хk = (x1k; ...; хпk).

Градієнтом f(x) функції f(х) в точці хk називається вектор, координатами якого є значення в цій точці частинних похідних першого порядку відповідної змінної, тобто

                                          

Градієнт функції в цій точці вказує напрямок найшвидшого зростання функції  f (х).

Переміщення з точки хk вздовж градієнту в нову точку хk+1 відбувається по прямій, рівняння якої

                                         .                                           (1)

де k  числовий параметр, від величини якого залежить довжина кроку переміщення . Величина k, при якій досягається найбільший приріст функції, може бути визначена з необхідної умови екстремуму функції

                                                                                    (2)

Чергову точку   хk+1  визначаємо після обчислення параметру  k  (для цього підставляємо значення  k     в формулу (1) на пошуковій траєкторії). В цій ( хk+1 ) точці знову знаходимо градієнт, а рух відбувається далі по прямій хk+2 = хk+1 + k+1f(xk+1) у напрямку нового градієнту f (xk+2) до точки хk+2, в якій досягається найбільше значення функції f(х) в цьому напрямку і т.д. Розв’язування триватиме доти, поки не буде досягнута точка х*, в якій градієнт функції дорівнює нулю. В цій точці х* цільова функція f(х*) і буде набувати максимального значення.

Приклад 1. Нехай потрібно визначити точку максимуму функції , коли процес розв’язування розпочинається з точки x0 = (4;4).

Розв’язування. Знайдемо частинні похідні функції  f(x)

; .

Градієнт функції в точці х0 буде

.

Перемістимось з точки  х0  вздовж градієнту  f(х0) в нову точку х1:

х1 = x0 + λ0 f (х0) = (4; 4) + 0 (–6; –4) = (4 – 6 0; 4 – 4 0).

Градієнт функції в точці х1 дорівнює

f (х1) = [2 – 2 (4 – 60); 4 – 2 (4 – 40)] = (– 6 +120; – 4 + 80).

З необхідної умови екстремуму одержуємо рівняння

,

звідки = 0,5.

Оскільки   ,    то знайдене значення х1 є точкою максимуму функції f (х1).

Враховуючи = 0,5, визначимо координати точки х1 на пошуковій траєкторії

х1 = (4 – 6·0,5; 4 – 4·0,5) = (1; 2)

та градієнт f (х1) в цій точці х1        f (х1) = (2 – 2·1; 4 – 2·2) = (0; 0).

Оскільки градієнт f (x1) має нульові координати, робимо висновок про те, що х1 = (1; 2) є точкою, в якій цільова функція досягає максимального значення  f(х1) = 2·1+ 4·2 – 1– 4 = 5                               ( в початковій точці f(x0) = – 8 ).

На мал. 1 наведена графічна інтерпретація даної задачі.

Мал. 1.

1.2.  Застосування градієнтного методу, коли наявні обмеження на область зміни змінних х

Тепер розглянемо випадок розв’язування задачі нелінійного програмування з обмеженнями. Припустимо, що задача полягає в наступному: необхідно знайти максимум функції  f(х) за обмежень

                                                                     ,  ,                                                         (3)

,.

Крім того, будемо вважати, що функція  f(х) є  ввігнутою диференційованою функцією.

При розв’язуванні подібних задач трапляються два випадки:

1) цільова функція має єдиний екстремум, і він знаходиться всередині області допустимих розв’язків. Тоді процес розв’язування задачі (пошук оптимальної точки х*) нічим не відрізняється від уже розглянутого;

2) цільова функція набуває свого екстремального значення в точці, що знаходиться на границі допустимої області. В цьому випадку послідовність розв’язування задачі наступна. Якщо початкова точка  хk лежить всередині допустимої області (всі обмеження виконуються як строгі нерівності), то переміщуватися потрібно в напрямку градієнту. Але координати чергової точки  повинні задовольняти обмеженням (3), тобто повинні виконуватись нерівності

                                                             (4)

Розв’язуючи систему (4) лінійних нерівностей, знаходимо проміжок  допустимих значень параметру , при яких точка x1 буде належати допустимій області. Значення , яке одержується в результаті розв’язування рівняння (2)

                                        ,

повинно належати проміжку . Якщо значення  виходить за межі проміжку, то за  приймається . При цьому чергова точка пошукової траєкторії опиняється на граничній гіперплощині, що відповідає нерівності системи (4), виходячи з якої при розв’язанні системи отримано значення .

Якщо початкова точка хk лежить на граничній гіперплощині (або чергова точка пошукової траєкторії опинилась на граничній траєкторії), то напрямок переміщення визначається із розв’язку наступної допоміжної задачі математичного програмування:

                                                                                   (5)

                                                                                                              (6)

для тих і, при яких

                                                ,                                                              (7)

                                                   ,                                                              (8)

де ;  .

Умова (7) визначає належність точки хk границі допустимої області. Умова (6) означає те, що переміщення з точки хk по вектору rk буде відбуватися всередину допустимої області або по її границі, а умова (8) необхідна для обмеження величини rk. Для наступної точки пошукової траєкторії

знаходиться значення параметра . При цьому використовується необхідна умова екстремуму:

.

Процес розв’язування припиняється при досягненні точки, в якій

.

Приклад 2. Максимізувати  за таких обмежень

,

Оптимізаційний пошук почати з точки x0 = (1; 0,5).

Розв’язування. Точка x0 = (1; 0,5) лежить всередині допустимої області, значення функції в точці x0  f(x0) = 8,75. За напрямок переміщення в наступну точку  x1  приймаємо напрямок градієнту  в точці x0 = (1; 0,5).

Градієнт у точці х0 дорівнює . Виходячи з цього, можна записати координати наступної точки

.

Визначимо проміжок допустимих значений для параметру , при яких точка x1 буде належати допустимій області. В цьому випадку система нерівностей (4) має вигляд

З розв’язку цієї системи знаходимо проміжок . Розв’язавши рівняння

,

визначимо значення параметру , при якому приріст функції досягає найбільшої величини. Але значення не належить проміжку, тому приймаємо .

Нова точка x1 = (1,36; 0,95) знаходиться на граничній прямій, яка визначається другим обмеженням–нерівністю (тією нерівністю, якій відповідає значення ). В точці x1 значення функції. Оскільки точка х1 лежить на граничній прямій, то напрямок переміщення в наступну точку х2 визначаємо за вектором r1 (рух в напрямку градієнта виводить з допустимої області). Для визначення координат вектора r1 запишемо допоміжну задачу (5) – (8):

максимізувати

за обмежень

;

.

Система рівнянь цієї задачі має два розв’язки: (0,5568;–0,8352) і (–0,5568; 0,8352). Підставляючи ці розв’язки у функцію , одержуємо, що максимальне значення функції і досягається при (–0,5568; 0,8352), тобто переміщуватися з х1 треба вздовж вектору                               r1 = (–0,5568; 0,8352)  по другій граничній прямій (мал. 2). Координати наступної точки х2 дорівнюють

,

а градієнт

.

Знову визначаємо проміжок допустимих значень параметра , при яких точка х2 буде належати допустимій області.

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

.

З використанням необхідної умови екстремуму

отримуємо . Але значення  не належить проміжку , тому приймаємо . Нова точка х2 = (1,36-0,557х1.01; 0,95+0,835х1,01)=(0,8; 1,8) лежить на перетині двох граничних прямих, які відповідають першій і другій нерівностям системи обмежень. У цій точці функція набуває значення

.

Визначимо напрямок переміщення з точки х2 – вектор r2 = (r21; r22):

максимізувати

за обмежень

;

.

Система рівнянь задачі має розв’язок r2 = (0; 0). Підставляючи одержаний розв’язок у функцію T, дістаємо, що максимум T = 0, а це означає те, що х2 є точкою максимуму цільової функції в допустимій області, тобто х2 = х* і max f (х*) = 12,68. Як видно з мал. 2, лінія рівня f(х)дотикається до границі допустимої області в точці х2.

Мал. 2

  1.  Порядок роботи:

Номер завдання відповідає порядковому номеру студента в деканатському журналі старости.

  1.   Розв’язати аналітично задану задачу нелінійного програмування, супроводжуючи розв’язок графічною ілюстрацією.
  2.   Побудувати блок-схему алгоритму рішення задачі.
  3.  Реалізувати алгоритм на одній з мов програмування та відшукати оптимальний розв’язок задачі.

Індивідуальне завдання:

Варіант 20

 


Розвязування задачі аналітично

Блок схема алгоритму:

Лістинг програми на С#:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace Gradient

{

   public partial class Form1 : Form

   {

       public Form1()

       {

           InitializeComponent();

       }

       private void button1_Click(object sender, EventArgs e)

       {

           gradient();

       }

       

       double[] x1= new double[1000];

       double[] x2 = new double[1000];

       double err = 0.0001;

       double ak = 0.05;

       double func(double x1, double x2)

       {

        return 4*x1*x1 + x2*x2 - 4*x1 + 2*x2;

       }

       double funcdx1(double x1, double x2)

       {

        return 8*x1 - 4;

       }

       double funcdx2(double x1 ,double x2)  

       {

        return 2*x2 + 2;

       }

       void gradient()

       {

        double xpr1 = 0, xpr2 = 0, funpro = 0;

        int i = 0;

           double xnt1 = double.Parse(textBox1.Text);

           double xnt2 = double.Parse(textBox2.Text);

           richTextBox1.Text = "№ " + "\t X1  " + "\t   X2 " + "\t   F( X1; X2)" + "\n";

           do

        {

         i++;

         xnt1 = xpr1-ak*funcdx1(xpr1, xpr2);

         xnt2 = xpr2-ak*funcdx2(xpr1, xpr2);

         funpro = funcdx1(xnt1, xnt2)+funcdx2(xnt1, xnt2);

         xpr1 = xnt1;

         xpr2 = xnt2;

               richTextBox1.Text += i.ToString("") +

                  "      " + xnt1.ToString("0.000000") + "      " + xnt2.ToString("0.000000")

                  + "      " + func(xnt1, xnt2).ToString("0.000000") + "\n";

               

        } while( Math.Abs(funpro) > err);

           label6.Text = "Minimum in:  ( " + xnt1.ToString("0.00") + " ; " + xnt2.ToString("0.00") + " )"+ "\n      F(x1,x2)=   " + func(xnt1, xnt2).ToString("0.00");

       }

       private void вихідToolStripMenuItem_Click(object sender, EventArgs e)

       {

           this.Close();

       }

       private void проПрограмуToolStripMenuItem_Click(object sender, EventArgs e)

       {

           AboutBox1 a = new AboutBox1();

           a.Show();

       }

   }

}

Форма Form1.cs

Форма AboutBox1.cs

Реалізація:


СПИСОК ЛІТЕРАТУРИ

1. Барінський А.Ф. і ін. Математичне програмування та дослідження операцій. – Л.: Інтелект- Захід, 2008. – 588с.: іл.

2. Барінський А.Ф. і ін. Математичне програмування. – Л.: Інтелект-Захід, 2004. – 448с.: іл.

3. Зайченко Ю.П. Дослідження операцій. – К.: ДМК Пресс, 2006. – 576с.: іл.

4. Долженков В.А., Колесников Ю.В. Microsoft Excel 2000. – СПб.: БХВ-Петербург, 2001. – 1088с.

5. Кудрявцев Е.М. Mathcad 2000 Pro. – М.: ДМК Пресс, 2001. – 576с.

6. Таха Хэмди А. Введение в исследование операций, 6-е издание: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 912с.: ил.

7. Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посіб. — К.: КНЕУ, 2003. — 452 с.

Висновок: на цій лабораторній роботі я ознайомився з градієнтним методом числової оптимізації, набув навиків розв’язку та аналізу задач нелінійного програмування градієнтним методом та розробив конкурентоспроможну програму оптимізації градієнтним способом.


 

А также другие работы, которые могут Вас заинтересовать

84019. Билеты по философии 329 KB
  Философия как общая методология. Метафизика и диалектика в истории философии. Зарождение и развитие философии и ее исторические типы. Особенности философского знания. Философское мировоззрение и его основные проблемы. Материализм и идеализм как основные направления в философии...
84020. Хоторнский эксперимент 22.3 KB
  Мейо Уорнер Фриц Ротлисбергер Вильям Диксон и другие исследовали влияние объективных факторов освещение оплата перерывы на производительность труда в пригороде Чикаго Хотторне Hwthorne. На первой стадии эксперимента учёные обнаружили что улучшение условий освещения резко увеличивает производительность труда но и ухудшение условий освещения также привело к улучшению производительности труда На второй стадии исследования учёные обнаружили что с течением времени производительность возвращалась на прежний уровень причём начинали...
84021. Теоретические взгляды Г. Мюнстерберга, их значение 21.85 KB
  Мюнстерберга их значение Самой пожалуй важной сферой интересов Мюнстерберга выступила индустриальная психология понимавшаяся им чрезвычайно широко в его работах на эту тему освещались проблемы профориентации в частности с применением психодиагностических процедур управления персоналом повышения трудовой мотивации и производственной дисциплины преодоления негативного влияния монотонного труда и т. Мюнстерберг доказывал что наилучший способ повысить производительность труда подбирать работникам должности которые соответствуют их...
84022. Бихевиоризм и теоретические воззрения А. Маслоу 23.23 KB
  Маслоу А́брахамМасло́у Авраам Масло́в англ. Широко известна иногда приписываемая Маслоу так называемая Пирамида Маслоу диаграмма иерархически представляющая человеческие потребности. Его модель иерархии потребностей нашла широкое применение в экономике занимая важное место в построении теорий мотивации и поведения потребителей Бихевиоризм и психоанализ или дефицитарные психологии как называл их Маслоу избегали многих культурных социальных и индивидуальных аспектов проявления человека таких как креативность любовь альтруизм...
84023. М.П. Фоллет и идеи гармонии труда и капитала 23.73 KB
  Фоллет и идеи гармонии труда и капитала М. Фоллет привнесла в изучение предприятий бизнеса и менеджмента концепции которые она разработала на основе знаний политологии и личного практического опыта приобретенного во время работы на руководящих должностях в общественной сфере деятельности. Фоллет мышление и практическое действие являются не изолированными видами деятельности а составляющими единого процесса в котором каждая из них может предшествовать другой и иметь по сравнению с ней большее или меньшее значение. Фоллет предлагает...
84024. Новые тенденции в развитии современной теории менеджмента 17.06 KB
  Интеграционные процессы как во внутренней среде так и во внешней во внешней среде интеграция бывает вертикальная холдинг и горизонтальная ФПГ ассоциация объединение.
84025. Вклад Д. Макгрегора в развитие идей поведенческой школы менеджмента 24.84 KB
  Макгрегора в развитие идей поведенческой школы менеджмента В начале 50х годов МакГрегор впервые сформулировал свои идеи об управлении которые в 1960 году были опубликованы в его главном труде TheHumnSideofEnterprise Человеческая сторона предприятия. МакГрегор утверждал что существует два вида менеджмента персонала первый из которых основывается на теории X а второй на теории Y. К сожалению отмечает МакГрегор в условиях современного индустриального общества интеллектуальный потенциал человека используется не полностью....
84026. Вклад П. Друкера в развитие мировой управленческой мысли 23.5 KB
  Друкера в развитие мировой управленческой мысли Живя и работая в Лондоне Питер Друкер выпускает свои первые книги 1939 и 1942 гг. Идеи высказанные Друкером в данных работах заинтересовали одного из руководителей Дженерал Моторс который пригласил его провести исследование высшего управленческого звена компании и основных принципов его функционирования. На основе данного исследования и опыта работы в консалтинговых проектах выполнявшихся им для других крупных корпораций Дженерал Электрик Сиарс Робак Друкер выпустил еще две работы:...
84027. Паркинсон С.Н. и его теоретические мировоззрения 24.1 KB
  Обратное этому утверждение гласит, что: «самым занятым является тот человек, который имеет свободное время». Причины разрастания работы заключаются в желании чиновников «множить число подчиненных, а не соперников» и «создавать работу друг для друга»