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

Автор работы: Пользователь скрыл имя, 10 Сентября 2011 в 15:16, курсовая работа

Описание работы

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

Содержание работы

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Файлы: 1 файл

курсач.docx

— 141.59 Кб (Скачать файл)
 
 

             Таблица 3

БП св. чл. у5 Y2 у8
у4 7,727273 -1 -6,09091 0,727273
у1 -2,18182 0,272727 0,272727 -0,18182
y6 7,363636 -0,54545 -4,54545 0,363636
y7 -9,36364 0,545455 1,545455 -0,36364
у3 -0,06061 0,090909 0,090909 0,272727
F -27,0909 4,636364 14,63636 1,909091
 

             Таблица 4

БП св. чл. у6 у2 у8
у4 7 -2 3 0
у1 1,5 1 -2 0
у5 2,833333 -1,83333 8,333333 -0,66667
y7 2 1 -3 1
у3 1,166667 0,166667 -0,66667 0,333333
F 35,5 8,5 24 5
 

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

         у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) = 2x1-3x2-0.5x12-x22+0.5x1x2, при ограничениях: 3x1 + x2 < 3, x1 + 2x2 < 2, x1 > 0, x2 > 0, методом наискорейшего спуска.

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

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

,

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

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

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

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

     

 

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

     

     

 

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

     

 

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

 Пусть  

     

 

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

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

       
 
 
 
 
 
 
 
 
 
 
 

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

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

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

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

,

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

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

,

,

 

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

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

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

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

 

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

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

 

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

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

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

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

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

 

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

 

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

     Вычисляется составляющие вектора  градиента в точке  х1

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

         
 
 
 
 
 
 

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

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

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

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

     

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

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

 

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

2x1 - 3x2 - 0.5x12 - x22 + 0.5x1x2 + λ1 (
)+λ2(
) 

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

 

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

 

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

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

 

                                   Таблица 1

БП св. чл. Небазисные  переменные
X1 X2 λ1 λ2
V1 -2 -1 0,5 -3 -1
V2 3 0,5 -1 -1 -2
W1 3 3 1 0 0
W2 2 1 2 0 0

Информация о работе Методы оптимизации