Методы оптимизации

 
 

             Таблица 3

 

     Таблица 4

 

     Оптимальный план можно записать так:   

     у6=у2=у8=0,   

     y4=7; у1=1,5; у5=13,5; y7=2; у3=1,17; F=35,5, 

     F(у) = 12•1,5  + 15•1,17 = 35,5 

     у*=1,5; 0; 1,17; 

 Находим соответствие прямой и двойственной задачей   
 
 
 
 
 
 
 
 
 
 

     2 Нелинейное программирование  

     2.1 Найти максимальное значение функции, без учета ограничений метод наискорейшего спуска 

     Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, при ограничениях: 3x₁ + x₂ < 3, x₁ + 2x₂ < 2, x₁ > 0, x₂ > 0, методом наискорейшего спуска.

     Начальная точка Х⁰ = [4/5, 3/5].

     В данном методе очередная точка при  поиске максимума функции вычисляется  по формуле k

,

где - градиент функции характеризует направление движения;  

       х^k - текущие значение точки экстремума;

       α^k – параметр характеризующий длину шага.  

     На  первом шаге движение осуществляется из точки х⁰ вдоль вектора в новую точку х¹: 

     

 

     Величина  шага α^k на любом шаге выбирается из условия обеспечения экстремума функции в рассматриваемом направлении. Подставляя координаты точки х¹ в функцию F(x), получим:   

     

     

 

     В результате после первого шага координаты очередной точки получаются равными 

     

 

     Вычисляется . Если ( ), поиск прекращается и считается, что х^* = х¹, если нет, переходим к шагу 2.

 Пусть  

     

 

     Поскольку заданная точность выполняется, то дальнейший поиск прекращаю.

     Область допустимых значений представлена на рисунке - 2.1 

       
 
 
 
 
 
 
 
 
 
 
 

Рисунок 4.1 Область допустимых значений 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     2.2 Найти максимальное значение функции, без учета ограничений метод Ньютона – Рафсона 

     Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, методом Ньютона - Рафсона. Начальная точка Х⁰ = [4/5, 3/5].

     Очередная точка поиска вычисляется в соответствии с выражением 

,

где Н(х) – матрица Гесса функции F(х);

       Н^-1(х) – обратная по отношению к Н(х) матрица.

,

,

 

где detH – определитель матрицы;

      AdjH – присоединения к Н матрица (транспонированная матрица                                                                                                                     алгебраических дополнений).

      Находим алгебраические дополнения матрицы  Н: m_ij, тогда                    ,  ,  ,  .

      Соответственно: 

 

      Следовательно, в точке х¹ = [10/7, -8/7] функция F(x) достигает максимального значения F_max = 35,5 
 
 
 
 

     2.3 Найти максимальное значение функции, с учетом системы ограничений метод доступных направлений Зойтендейка

 

     Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, при ограничениях: 3x₁ + x₂ < 3, x₁ + 2x₂ < 2, x₁ > 0, x₂ > 0, методом допустимых направлений Зойтендейка.

     Начальная точка Х⁰ = [4/5, 3/5].

     Находим направление вектора градиента  в точке х⁰, 

тогда координаты очередной точки 

      Определяем  интервал допустимых значений для параметра  α⁰, при которых точка х¹ будет принадлежать ОДЗП. Для этого координат точки х¹ подставляем в ограничения задачи 

 

      Выбираем  наиболее сильные из полученных условий, тогда 

 

      Находим величину которая обеспечивает максимум функций F(x). Процедура полностью совпадает с первым шагом решения задачи методом наискорейшего спуска, поэтому . Это значение не принадлежит найденному интервалу, поэтому принимается, что . Координаты точек х¹ и значение градиента функции в этой точке определяется выражениями: 

     _{Вычисляется составляющие вектора  градиента в точке  х¹,} 

      Направление вектора  перпендикулярно направлению S¹ , следовательно, данная точка х¹ =[ 1, 0 ] обеспечивает максимум функции F(x).  

         
 
 
 
 
 
 

Рисунок 3.1 Область допустимых значений

     2.4 Найти максимальное значение функции, с учетом системы ограничений Метод Куна – Таккера 

     Найти максимальное значение функции F(x) = 2x₁-3x₂-0.5x₁²-x₂²+0.5x₁x₂, при ограничениях: 3x₁ + x₂ < 3, x₁ + 2x₂ < 2, x₁ > 0, x₂ > 0, используя условия теоремы Куна - Таккера.

     Составляется  функция Лагранжа: 

     

где g(х) – левые части ограничений, приведенные к нулевой правой части;

       λ_j – неопределенные множители Лагранжа: 

 

      Точка экстремума является седловой точкой с максимумом по х и минимумом по λ, поэтому ограничения приведены к виду : 

2x₁ - 3x₂ - 0.5x₁² - x₂² + 0.5x₁x₂ + λ₁ ( )+λ₂( ) 

      Условия теоремы Куна – Таккера записываются следующим образом: 

 

      Частные производные функции Лагранжа определяются выражением:

 

      Для приведения неравенства к виду равенств вводятся дополнительные неотрицательные переменные V и W. Одновременно свободные члены переносятся в правую часть тогда:

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

 

                                   Таблица 1