Ирина Эланс

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

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

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

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

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

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

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

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

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

Выполнила:

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

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

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

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

Брест, 2010

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ…………………………... ….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). Так как сфера — замкнутое ограниченное множество, то согласно теореме Вейерштрасса функция достигает на ней своего наибольшего и наименьшего значений.

Рисунок 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 тыс. ден.ед.

Величины себестоимости изделий (т.е. затраты на их выпуск) зависят от объема их производства и приближенно описываются следующими формулами:

• себестоимость одного изделия A: 7+0,2X1, где X1 - объем производства изделий A;

• себестоимость одного изделия B: 8+0,2X2, где X2 - объем производства изделий B.

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

Предварительно найдем градиент целевой функции:

grad E = =(5-0,4X1, 2-0,4X2).

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

13X1 + 6X2 ≤ 90;

8X1 + 11X2 ≤ 88;

X1, X2 ≥ 0.

E = 5X1 + 2X2 → max.

Решив эту задачу, получим начальное допустимое решение: X1(0) =6,923, X2(0)=0. Найдем значение целевой функции для этого решения: E(0) = 5·6,923 --0,2·6,9232 + 2·0 - 0,2·02 = 25,03.

Необходимо также задать требуемую точность решения задачи (ε). Зададим ее равной 500 ден.ед., т.е. будем считать, что решение найдено, если переход к новому решению приводит к увеличению целевой функции не более чем на 500 ден.ед. В данной задаче целевая функция выражается в тысячах ден.ед., поэтому ε=0,5.

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

Франка-Вульфа.

Итерация 1

1. Определяется градиент целевой функции в точке ОДР, соответствую-

щей текущему решению:

grad E (X(0))= (5-0,4·6,923; 2-0,4·0) = (2,2; 2).

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

13X1 + 6X2 ≤ 90;

8X1 + 11X2 ≤ 88;

X1, X2 ≥ 0.

f = 2,2X1 + 2X2 → max.

Решение этой задачи следующее: X*1 =4,863, X*2 = 4,463. Это означает, что поиск нового решения будет выполняться в направлении от точки X(0)= =(6,923; 0) к точке X*= (4,863; 4,463).

3. Составляются уравнения для перехода к новому решению:

X1(1) =X1(0)+ λ (X1*- X1(0));

X2(1) =X(0)+ λ (X2*- X2(0)),

где λ – коэффициент, задающий величину перемещения от текущего решения к новому решению в направлении точки X*. Этот коэффициент определяется на следующем шаге.

Для рассматриваемого примера эти уравнения имеют следующий вид:

X1(1) = 6,923 + λ(4,863-6,923) = 6,923 – 2,06λ;

X2(1) = 0 + λ(4,463-0) = 4,463λ.

4. Определяется коэффициент λ. Этот коэффициент находится таким образом, чтобы переход к новому решению обеспечивал максимальное значение целевой функции. С этой целью уравнения для перехода к новому решению, построенные на шаге 3, подставляются в целевую функцию E. В результате целевая функция представляется как функция от коэффициента λ:

E = 5(6,923 – 2,06λ) - 0,2(6,923 – 2,06λ)2 + 2·4,463λ - 0,2(4,463λ)2 =

= -4,8 λ2 +4,3λ + 25.

Значение λ находится из условия экстремума целевой функции, т.е. из условия dE/dλ=0:

dE/dλ=-9,6λ + 4,3 = 0.

λ=0,448.

Примечания:

1. Если значение λ, найденное из уравнения dE/dλ=0, оказывается больше единицы, то принимается λ=1. Это означает, что экстремум целевой функции в направлении, задаваемом градиентом, находится за пределами ОДР. В этом случае новое решение должно находиться на границе ОДР (т.е. в точке X*), но не выходить за нее.

2. Если уравнение dE/dλ=0 не имеет решений (например, не зависит от λ), то также принимается λ=1.

5. Из уравнений, составленных на шаге 3, определяется новое решение:

X1(1) = 6,923 – 2,06·0,448 = 6;

X2(1) = 4,463·0,448 = 2.

Определяется значение целевой функции для полученного решения:

E(1) = 5·6 - 0,2·62 + 2·2 - 0,2·22 = 26.

6. Проверяется условие окончания поиска решения. Для этого определяется разность значений целевой функции для нового и предыдущего решения: ΔE = |E(1) –E(0)| = |26-25,03| = 0,97. Эта величина сравнивается с заданной точностью ε. Если ΔE ≤ ε, то текущее решение принимается в качестве оптимального. В данном случае ΔE = 0,97, ε = 0,5. Таким образом, условие окончания поиска решения не выполняется. Требуется следующая итерация.

Итерация 2

1. Определяется градиент целевой функции в точке ОДР, соответствующей текущему решению:

grad E (X(1))= (5-0,4·6; 2-0,4·2) = (2,6; 1,2).

2. Определяется угловая точка ОДР, соответствующая предельно допустимому перемещению от текущего решения в направлении градиента. Для этого решается следующая задача линейного программирования:

13X1 + 6X2 ≤ 90;

8X1 + 11X2 ≤ 88;

X1, X2 ≥ 0.

f = 2,6X1 + 1,2X2 → max.

Решение этой задачи следующее: X1*=4,863, X2* = 4,463.

3. Составляются уравнения для перехода к новому решению:

X1(2) = 6 + λ(4,863-6) = 6 – 1,137λ;

X2(2) = 2 + λ(4,463-2) = 2 + 2,463λ.

4. Определяется коэффициент λ из условия экстремума целевой функции:

E = 5(6 – 1,137λ) - 0,2(6 – 1,137λ)2 + 2(2 + 2,463λ) - 0,2(2 + 2,463λ)2 =

= -1,5λ2 + 26.

dE/dλ=-3λ = 0.

λ=0.

5. Из уравнений, составленных на шаге 3, определяется новое решение:

X1(2) = 6 – 1,137·0 = 6;

X2(2) = 2 + 2,463·0 = 2.

Определяется значение целевой функции для полученного решения:

E(2) = 5·6 - 0,2·62 + 2·2 - 0,2·22 = 26.

6. Проверяется условие окончания поиска решения. Определяется разность значений целевой функции для нового и предыдущего решения:

Δ E = |E (2)-E (1)| = 0. Так как ΔE ≤ ε, оптимальное решение найдено: X1=6, X2=2. Оптимальное значение целевой функции E=26.

Таким образом, предприятию следует выпустить 6 изделий типа A и 2 изделия типа B. Такой план производства обеспечит предприятию максимальную прибыль в размере 26 тыс ден.ед.

Примечания:

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

2. В рассмотренном примере решалась задача с целевой функцией, подлежащей максимизации. Если требуется минимизация целевой функции, то задача решается точно так же. Единственное отличие состоит в том, что целевая функция W в задаче, решаемой на шаге 2,также подлежит минимизации

ЗАКЛЮЧЕНИЕ

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

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

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

Применение экономико-математических методов и моделей позволяет существенно улучшить качество планирования и получить дополнительный эффект без вовлечения в производство дополнительных ресурсов.

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

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

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

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

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

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

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

СпиСОК ИСПОЛЬЗуемых ИСТОЧНИКОВ

1. Бодров В.И Математические методы принятия решений / В.И. Бодров, Т.Я. Лазарева, Ю.Ф. Мартемьянов. – Тамбов: Издательство ТГТУ, 2004. – 83 с.

2. Самаров К. Л. Функции нескольких переменных. Нелинейное программирование / К. Л. Самаров. – М. : ООО «Резольвента», 2009. – 26 с.

3. Исследование операций в экономике / под. ред. Н.Ш. Кремера . – М. : Юнити, 2000. – 408 с.

4. Ковалев В.В. Финансовый анализ: методы и процедуры / В.В. Ковалев. – М.: Финансы и статистика, 2002. – 560 с.

5. Смородинский С.С. Оптимизация решений на основе методов и моделей математического программирования / С.С. Смородинский, Н.В. Батин. – Минск: БГУИР, 2003. – 136 с.

Методы решения задач нелинейного программирования 📙 Курсовая → 🆔 129036