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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Брестский государственный университет имени А.С. Пушкина»

Математический факультет

Кафедра математического моделирования

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

«Методы решения задач нелинейного программирования»

Выполнила:

студентка 3 курса специальности

«бизнес-администрирование

Руководитель:                                                                                  Дуванова

Ольга Сергеевна

Брест, 2010

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………………. 3

1.      ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ…………………………………………………5

2.      Графический метод решения задач нелинейного программирования с двумя переменными………………6

3.      Метод множителей Лагранжа ……………………………….. 8

4.      ПРИМЕР РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ МНОЖИТЕЛЕЙ

    Лагранжа ……………………………………………………..………....9

5. Градиентный метод……………………………………………...…11

6. Пример решения задачи нелинейного

программирования градиентным методом……………..…12

ЗАКЛЮЧЕНИЕ……………………………………………………………….... 17

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ…………………………... ….19

ВВЕДЕНИЕ

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

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

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

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

Цель данной курсовой работы – отразить использование различных методов  в решении задач нелинейного программирования.

Для достижения цели курсовой работы необходимо выполнить следующие задачи:

      Рассмотреть общую постановку задачи нелинейного программирования;

      Описать графический метод решения задач нелинейного программирования;

      Описать метод множителей Лагранжа для решения задач нелинейного программирования;

      Описать градиентный метод решения задач нелинейного программирования;

      Рассмотреть на примерах вышеперечисленные методы решения задач нелинейного программирования.

19

1. ПОСТАНОВКА ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задачи нелинейного программирования – это задачи, в которых (как и в задачах линейного программирования) требуется найти значения переменных X1, X2,..., Xn, обеспечивающие максимальное или минимальное значение некоторой целевой функции (1.1) при соблюдении системы ограничений (1.2). При этом целевая функция и/или некоторые из ограничений являются нелинейными, т.е. содержат нелинейные составляющие, например, X12, X1X2 т.д.

f (x1, x2, …, xn) → max (min)                                         (1.1)

                                      g1(x1, x2, …, xn) ≥ 0;

                                      g2(x1, x2, …, xn) ≥ 0;

                                               …                                                                   (1.2)

                                      gn(x1, x2, …, xn) ≥ 0

                                      xj  ≥ 0, (j=1,n)

Как и в задачах линейного программирования, любые значения переменных X1, X2, ..., Xn, удовлетворяющие ограничениям задачи, называются допустимыми решениями, а все множество допустимых решений - областью допустимых решений (ОДР). Допустимые значения переменных X1, X2, ..., Xn, при которых целевая функция принимает экстремальное значение, представляют собой оптимальное решение. В задачах нелинейного программирования оптимальное решение может находиться как на границе, так и внутри ОДР.

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

2. Графический метод решения задач нелинейного программирования с двумя переменными

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

Пример.

Найти наибольшее и наименьшее значения функции

f= x2 + y2 - 8x - 6y + 25                                     (2.1)

при наличии ограничений

                                                          x≤3,

y≤6,                                                           (2.2)

2x+y-6≥

Решение. Система ограничений (2.2) задает на координатной плоскости XOY прямоугольный треугольник ABC с прямым углом C (рис. 1 ).

Рисунок 1

Прямые AC, BC и AB определяются уравнениями x=3 , y=6 и y=6-2x соответственно, причем A = (3;0), B = (0;6), C = (3;6).

Выделяя в формуле (2.1) полные квадраты по переменным x и y , преобразуем эту формулу к следующему виду:

f= (x - 4)2 + (y - 3)2                                                               (2.3)

Если ввести новую переменную f1= f, то формула (2.3) примет вид

f12=(x - 4)2 + (y - 3)2                                                            (2.4)

и будет задавать окружности с центром в точке E = (4;3) и радиусами f1.

Опустив из точки E перпендикуляр на прямую AC, получим точку D с координатами { x = 3, y = 3 }, причем длина отрезка ED равна 1.

Теперь найдем длину отрезка EB:

EB=    (4-0)2 + (3-6)2=5 .

Из рис. 1 вытекает, что окружности (2.4) пересекают треугольник ABC тогда и только тогда, когда их радиусы f1 удовлетворяют неравенству 1 ≤ f1 ≤5. В случае f1 = 1 окружность, заданная уравнением (2.4), касается прямой AC в точке D, а в случае f1 = 5 окружность, заданная уравнением (2.4), проходит через точку B.

В случае f1 =1 выполнено соотношение

f = f1 2 =12 = 1,

а в случае f1 = 5 − соотношение

f = f1 2 =52 = 25.

Следовательно, при наличии ограничений (2.2) наименьшее значение функции (2.1) равно 1 и достигается в точке {x = 3, y = 3}. Наибольшее значение функции (2.1) равно 25 и достигается в точке {x =0, y =6}.

Решение Примера завершено.

3. Метод множителей Лагранжа

Метод множителей Лагранжа, метод нахождения условного экстремума функции f (x) , где x принадлежит  Rn, относительно m ограничений φi (x)=0, i меняется от единицы до m.

Составим функцию Лагранжа в виде линейной комбинации функции f и функций φi , взятых с коэффициентами, называемыми множителями Лагранжа — λi:

L(x, λ) = f (x) + ∑ λi φi (x),                                     (3.1)

где λ = (λ1 , . . . , λm).

Множителям Лагранжа можно придать экономический смысл. Если f (x1, x2, …, xn) ­­­– доход, соответствующий плану X=( x1, x2, …, xn), а функция φi (x1, x2, …, xn) – издержки i-го ресурса, соответствующие этому плану, то λi – цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса.

Составим систему из n+m уравнений, приравняв к нулю частные производные функции Лагранжа L(x, λ) по xj и λi.

                                            ∂L(X)   

∂xj      = 0 , j = 1, 2, …, n,

                                                      (3.2)

                                            ∂L(X)

∂λi    = 0 , i = 1, 2, …, m.

Если полученная система имеет решение относительно параметров x'j и λ'i, тогда точка x' может быть условным экстремумом, то есть решением исходной задачи. Заметим, что это условие носит необходимый, но не достаточный характер.

4. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ МНОЖИТЕЛЕЙ Лагранжа

Найти  наибольшее  и  наи­меньшее значения функции

f = 9 х12 + 4 x22 + x32 – (3 x12 + 2 х2 + x32)

при условии, что х1, x2, х3 удовле­творяют уравнению

х12 + х22 + x32 = 1.

Решение. Уравнение связи определяет в пространстве сферу единичного радиуса с центром в начале координат (рис. 2). Так как сфера — замкнутое ограничен­ное множество, то согласно теореме Вейерштрасса функция достигает на ней своего наибольшего и наименьшего значений.

19

Рисунок 2

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

х12 + х22 + x32 – 1 = 0.

Составим функцию Лагранжа:

L(x1, x2, x3) = 9 х12 + 4 x22 + x32 – (3 x12 + 2 х2 + x32)2 + λ(х12 + х22 + x32 – 1).

Найдем частные производные этой функции по х1, x2, х3 , λ.

Lx'1 = 18 х1 – 2 ( 3х12 + 2х22 + х32)6х1 + 2 λ х1 ,

Lx'2 = 8 х2 – 2 ( 3х12 + 2х22 + х32)4х­2 + 2 λ х2 ,

Lx'3 = 2 х3 – 2 ( 3х12 + 2х22 + х32)2х3 + 2 λ х3 ,

L'λ = х12 + х22 + х32 -1.

Приравняв частные производные нулю, получим систему:

х1 ((9 + λ) – 6(3х12 + 2х22 + х32 )) = 0,

х2 ((4 + λ) – 4(3х12 + 2х22 + х32 )) = 0,

х3 ((1 + λ) – 2(3х12 + 2х22 + х32 )) = 0,

х12 + х22 + x32 = 1.

Решая систему, получим стационарные точки, в которых най­дем значения функции f:

1. х1 = х2 = 0; х3 = + 1    =>  f = 0.

2. х1 = 0; х2 =+ 1; х3 =0 =>  f = 0.

3. х1 = + 1; х2 = х3 =0    =>  f = 0.

4. х1 =0; х2 = х3 = + 1/√2   =>  f = 1/4.

5. х1 = + 1/√2; х2 = 0; х3 =+ 1/√2    =>  f = 1.

6. х1 = х2 = + 1/√2; х3 = 0     =>  f = 1/4.

Выберем из всех значений f наибольшее и наименьшее: fнаиб. = 1, а fнаим. =0.

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

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

Градиент любой функции нескольких переменных F(X1,X2,...,Xn) – это вектор, координаты которого представляют собой частные производные этой функции:

grad F = .                            (5.1)

Из высшей математики известно важное свойство градиента: он указывает направление наискорейшего возрастания функции. Вектор -grad F называется антиградиентом функции F и указывает направление ее наискорейшего убывания.

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

1. Определяется некоторое начальное допустимое решение задачи.

2. Выполняется переход от текущего решения к новому решению в направлении градиента (или антиградиента). Величина этого перехода определяется по-разному в зависимости от условий задачи и используемого метода.

3. Определяется разность значений целевой функции для нового и предыдущего решений. Если эта разность мала (не превышает некоторой заданной точности), то найденное решение принимается в качестве оптимального. В противном случае выполняется возврат к шагу 2.

6. Пример решения задачи нелинейного программирования градиентным методом

Рассмотрим один из градиентных методов – метод Франка-Вульфа. Этот метод предназначен для решения задач с линейной системой ограничений и нелинейной целевой функцией. Метод наилучшим образом подходит для решения задач с квадратичной целевой функцией, хотя может применяться и для решения задач с целевыми функциями другого вида.

Решим задачу, используя метод Франка-Вульфа.

Задача. Предприятие выпускает электронные изделия двух типов (изделия A и B). На выпуск изделий расходуется платина и палладий. На одно изделие A требуется 13 г платины и 8 г палладия, на одно изделие B - 6 г платины и 11 г палладия. Предприятие имеет возможность использовать не более 90 г платины и не более 88 г палладия. Изделия A продаются по цене 12 тыс. ден.ед., изделия B – по 10 тыс. ден.ед.