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

Министерство  образования Республики Беларусь 

Белорусский государственный университет информатики  и радиоэлектроники 

Кафедра систем управления 
 
 
 
 
 
 
 

Курсовая  работа 

по курсу

Математические  основы теории систем 

на тему

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

Выполнил:                                                                Бальцевич А.В. 
 

Проверил:                                                                 Стасевич Н.А. 
 
 
 
 

Минск 2011 

 

     Содержание 

     Введение 

     1 Линейное программирование

     1.1 Прямая задача линейного программирования

     1.2 Двойственная задача линейного  программирования

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

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

     ограничений методом наискорейшего спуска 

     2.2 Найти максимальное значение функции, без учета

     ограничений методом Ньютона - Рафсона

     2.3 Найти максимальное значение функции, с учетом

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

     2.4 Найти максимальное значение функции, с учетом

     системы ограничений методом Куна - Такера

     Заключение 

     Литература   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Введение 

      Методы  оптимизации - это раздел вычислительной математики, объединяющий методы и  алгоритмы решения задач оптимизации  функций, а также обосновывающие применение этих методов теоретические  результаты.                                                         Линейное программирование дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Одним из обобщений линейного программирования является дробно-линейное программирование. В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи: если и — выпуклые функции, то такую задачу называют задачей выпуклого программирования; если, то имеют дело с задачей целочисленного (дискретного) программирования.

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

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

     1 Линейное программирование 

     1.1 Прямая задача  линейного программирования 

       Найти максимальный план х^* и экстремальное значение функций F(x). Построить задачу, двойственную к исходной, решить ее и сравнить решения прямой и двойственной задачи.

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

     Определим значение целевой функции,  при  следующих условиях-ограничений. 

     F(x) = -х₁+4х₂+3х₃-5х₄+2х₅ (max) 

     4х₁+3х₂+2х₃-2х₄-х₅ <12

     5х₁-х₂+4х₃-х₄ >10

     2х₂+3х₅ <15

     x_i > 0, i = 1.5 

     Для построения первого опорного плана  систему неравенств приведем к системе уравнений путем введения дополнительных переменных. 

     4х₁+3х₂+2х₃-2х₄-х₅ +х₆<12

     5х₁-х₂+4х₃-х₄ –х₇>10

     2х₂+3х₅ +х₈ <15 

             4х₁+3х₂+2х₃-2х₄-х₅ +х₆ <12

          -5х₁+х₂-4х₃+х₄ +х₇ <-10           (-1)

             2х₂+3х₅ +х₈<15 

     На  основании вышеизложенного составляем симплекс – таблицы

                  Таблица 1

 

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

     x1=x2=x4=x6=x8=0, 

     x3=8,5; x5=5; x7=24; F=35,5, 

     F(X) = 3*8.5 + 2*5 = 35.5 

     x*=0; 0; 8,5; 0; 5 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      1.2 Двойственная задача  линейного программирования 

     Составим  двойственную задачу относительно прямой задачи

                  

     F(x) = -х₁+4х₂+3х₃-5х₄+2х₅ (max) 

     4х₁+3х₂+2х₃-2х₄-х₅ <12

     5х₁-х₂+4х₃-х₄ >10

     2х₂+3х₅ <15

     x_i > 0, i = 1.5 

     F(y) = 12у₁-10у₂+15у₃ (min)

     -4х₁-3х₂-2х₃+2х₄+х₅ > -12       (-1)

     5х₁-х₂+4х₃-х₄ > 10

     -2х₂-3х₅ > -15                            (-1) 

     Составляем  матрицу и транспонируем ее:

             

                                       

                           

     Составляем  уравнения из матрицы 

     4у₁-5у₂ ≥ -1

     3у₁+у₂+2у₃ ≥ 4

     2у₁-4у₂ ≥ 3

     -2у₁+у₂ ≥ -5

      -у₁+3у₃ ≥ 2 

     Для построения первого опорного плана  систему неравенств приведем к системе уравнений путем введения дополнительных переменных 

     4у₁-5у₂ +у₄ ≥ -1

      3у₁+у₂+2у₃ +у₅ ≥ 4

      2у₁-4у₂ +у₆ ≥ 3

      -2у₁+у₂ +у₇ ≥ -5

      -у₁+3у₃ +у₈ ≥ 2 

     На  основании вышеизложенного составляем симплекс – таблицы 

     Таблица 1

     Таблица 2

 
 

             Таблица 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