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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Файлы: 1 файл

курсач.docx

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

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

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

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

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

по курсу

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

на тему

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

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

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

Минск 2011 

 

     Содержание 

     Введение 

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

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

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

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

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

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

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

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

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

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

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

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

     Заключение 

     Литература   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Введение 

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

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

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

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

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

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

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

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

         F(x) = -х1+4х2+3х3-5х4+2х5 (max) 

         1+3х2+2х3-2х45 <12

         12+4х34 >10

         2+3х5 <15

         xi > 0, i = 1.5 

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

         1+3х2+2х3-2х456<12

         12+4х34 –х7>10

         2+3х58 <15 

             4х1+3х2+2х3-2х456 <12

          -5х12-4х347 <-10           (-1)

             2х2+3х58<15 

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

                  Таблица 1

БП св. чл. X1 Х2 Х3 Х4 Х5
Х6 12 4 3 2 -2 -1
Х7 -10 -5 1 -4 1 0
Х8 15 0 2 0 0 3
F 0 1 -4 -3 5 -2
             
             
  Таблица 2
БП св. чл. X1 Х6 Х3 Х4 Х5
Х2 4 1,333333 0,333333 0,666667 -0,66667 -0,33333
Х7 -14 -6,33333 -0,33333 -4,66667 1,666667 0,333333
Х8 7 -2,66667 -0,66667 -1,33333 1,333333 3,666667
F 16 6,333333 1,333333 -0,33333 2,333333 -3,33333
             
             
             
             
Таблица 3
БП св. чл. X1 Х6 Х3 Х4 Х8
Х2 4,636364 1,090909 0,272727 0,545455 -0,54545 0,090909
Х7 -14,6364 -6,09091 -0,27273 -4,54545 1,545455 -0,09091
Х5 1,909091 -0,72727 -0,18182 -0,36364 0,363636 0,272727
F 22,36364 3,909091 0,727273 -1,54545 3,545455 0,909091
             
             
Таблица 4
БП св. чл. X1 Х6 Х2 Х4 Х8
Х3 8,5 2 0,5 1,833333 -1 0,166667
Х7 24 3 2 8,333333 -3 0,666667
Х5 5 0 0 0,666667 0 0,290759
F 35,5 7 1,5 2,833333 2 1,166667
 

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

         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) = -х1+4х2+3х3-5х4+2х5 (max) 

         1+3х2+2х3-2х45 <12

         12+4х34 >10

         2+3х5 <15

         xi > 0, i = 1.5 

         F(y) = 12у1-10у2+15у3 (min)

         -4х1-3х2-2х3+2х45 > -12       (-1)

         12+4х34 > 10

         -2х2-3х5 > -15                            (-1) 

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

     
АТ= -4 5 0
-3 -1 -2
-2 4 0
2 -1 0
1 0 -3
     
А= -4 -3 -2 2 1
5 -1 4 -1 0
0 -2 0 0 -3
 

                                       

                           

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

         1-5у2 ≥ -1

         12+2у3 ≥ 4

         1-4у2 ≥ 3

         -2у12 ≥ -5

         1+3у3 ≥ 2 

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

         1-5у2 +у4 ≥ -1

         12+2у35 ≥ 4

         1-4у26 ≥ 3

          -2у127 ≥ -5

         1+3у38 ≥ 2 

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

             Таблица 1

БП св. чл. y1 y2 y3
y4 -1 4 -5 0
y5 4 3 1 2
y6 3 2 -4 0
y7 -5 -2 1 0
y8 2 -1 0 3
F 0 12 -10 15

             Таблица 2

БП св. чл. y1 у2 у8
y4 -1 4 -5 0
у5 -8 3,666667 1 -0,66667
y6 3 2 -4 0
y7 -5 -2 1 0
у3 0,666667 -0,33333 0 0,333333
F 10 -17 10 5

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