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

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

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

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

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

по курсу

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

на тему

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

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

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

Минск 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