Сущность нелинейного программирования.

Экономическая постановка и общий вид

Математической модели задач линейного программирования.

      В экономике и управлении имеется определённый ряд задач нелинейного характера, т. е. показатели нелинейно зависят от факторов. В данном классе задач выделятся 3 основных направления:

1) Дробно-линейное программирование.

  Z =

Например, рентабельность  

2) Квадратическое программирование.

 Здесь целевая функция может содержать квадраты переменных и (или) их произведения.

3) Выпуклое программирование.

Множество является выпуклым, если отрезки, соединяющие любые 2 точки из этого множества.

Этот класс считается наиболее простым. У него целевая функция не линейна, но выпукла, а ограничения линейны. Или же обратная задача (целевая функция линейна; ограничения – не линейны и выпуклы).

Z = C₁x₁ + C₂x₂ + … + C_nx_n min (max)

1) X₁

2)

Z = f(x₁, x₂, …, x_n) min(max)

x₁, x₂, …

Геометрическая интерпретация задач

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

                                                1 y

x² + y² = 1                                             

Z = f (x, y) max          -1           1 х

                                  

                                                  

                                                -1

 

    

                  Глобальный оптимум

 

 

Если область дополнительных значений (О. Д. З.) нелинейна и не выпукла, то появляется понятие локального оптимума и глобального оптимума.

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

В линейном программировании базисное и оптимальное решения содержат столько переменных, сколько ограничений имеется в данной задаче. Для нелинейного программирования данная закономерность не соблюдается.

 

Методы решения задач нелинейного

Программирования.

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

1) Детерминированные

2) Статические.

 

I. Детерминированные методы:

1) Градиентный (нормаль/перпендикуляр к касательной)

2) Метод наискорейшего спуска (подъёма)

3) Графический метод.

II. Статистические методы:

1) Метод Монте-Карло (случайных испытаний).

2) Метод случайного поиска.

3) Метод статистического градиента.

 

Рассмотрим пример использования графического метода из группы Ι.

    Задача: необходимо спроектировать склад прямоугольной формы по критерию минимум строительных затрат.

 

b=x a=y

780 у.руб.

                   

            

                  200у. руб.

                      

Z = (780*x + 200*y)*2 min

x > 0, y > 0

x  35(м)      xy  1000(м²)

         y

 

100

 

 

62,5

 

       

   40

    30

 

 

                 10  16                    35              X

 

 

Тангенс угла наклона целевой функции = первой производной от нелинейного ограничения.

tg

y^’ =                

-3,9 = -1000 / х²

      х = 16       у =

Градиентные методы.

    Эти методы применяются для решения задач выпуклого программирования, у которых ограничения линейные, а целевая функция нелинейна и выпукла. Идея метода довольно проста, а процесс вычислений довольно сложен.

y

 

 

 

 

                                            Z = f(x) max

 

 

                                             x

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

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

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