Методические указания решения нелинейных оптимизационных профессиональных задач способами математического программирования.
ОГЛАВЛЕНИЕ
TOC \t "Заголовок 1;2;Мой заголовок;1" Введение PAGEREF _Toc412331308 \h 2
Глава 1. Постановка задачи PAGEREF _Toc412331309 \h 3
1.1 Фундаментальные понятия и определение «математического программирования» PAGEREF _Toc412331310 \h 3
2.2 Постановка задачи нелинейного программирования PAGEREF _Toc412331311 \h 4
Глава 2. Некоторые методы решения задач нелинейной оптимизации PAGEREF _Toc412331312 \h 6
3.1 Метод множителей Лагранжа. PAGEREF _Toc412331313 \h 6
3.2 Квадратичное программирование PAGEREF _Toc412331314 \h 10
3.3 Графический метод решения задачи PAGEREF _Toc412331315 \h 15
3.4 Информационные технологии Exsel решения задач нелинейного программирования PAGEREF _Toc412331316 \h 16
Заключение PAGEREF _Toc412331317 \h 19
Литература PAGEREF _Toc412331318 \h 20
ВведениеДанная курсовая работа посвящена изучению возможностей решения нелинейных оптимизационных профессиональных задач способами математического программирования.
Решение данной проблемы имеет большое прикладное значение в области логистики, экономики, техники, математики, в сфере деловых отношений и в науке управления государством, и т.д., а, соответственно, имеет актуальное значение в настоящее время.
Цель курсовой работы - ознакомление с эффективными методами математической обработки нелинейных уравнений и систем уравнений, возникающих при решении задач оптимизации нелинейного программирования.
Задачи курсовой работы:
Изучить специальную литературу по изучению математических методов решения задач нелинейного программирования;
Рассмотреть ключевые понятия:
Математическое программирование;
Задачи нелинейного программирования, их классификация;
Различные методики решения.
Решение задачи нелинейного программирования возможными методами, анализ исследуемых методов;
Реализация оптимального метода в программной среде.
Глава 1. Постановка задачи1.1 Фундаментальные понятия и определение «математического программирования»Математическое программирование – раздел прикладной математики, изучающий методы поиска экстремума функций. Алгоритмы математического программирования используются при решении оптимизационных задач.
По типу целевых функций математическое программирование подразделяется на линейное математическое программирование и нелинейное математическое программирование. В данной курсовой работе рассмотрим задачи нелинейного программирования.
Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейны и (или) целевая функция, и (или) ограничения в виде неравенств или равенств. Задачи нелинейного программирования можно классифицировать в соответствии с видом целевой функции F(x), функциями ограничений и размерностью вектора х (вектора решений).
В общем виде классификация задач нелинейного программирования представлена в таблице 1:
Таблица SEQ Таблица \* ARABIC 1. Классификация задач нелинейного программирования
Вид F(x) Вид функции ограничений Число переменных Название задачи
Нелинейная Отсутствуют 1 Безусловная однопараметрическая оптимизация
Нелинейная Отсутствуют Более 1 Безусловная многопараметрическая оптимизация
Нелинейная или линейная Нелинейные или линейные Более 1 Условная нелинейная оптимизация
Общих способов решения для задач нелинейного программирования не существует. В каждом конкретном случае способ выбирается в зависимости от вида целевой функции F(x).
Многие задачи нелинейного программирования могут быть приближены к задачам линейного программирования, и найдено близкое к оптимальному решению.
Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут не пропорционально количеству закупленных или произведённых товаров.
В целом задачи нелинейного программирования относятся к трудным вычислительным задачам. При их решении часто приходится прибегать к приближенным методам оптимизации. Мощным средством для решения задач нелинейного программирования являются численные методы. Они позволяют найти решение задачи с заданной степенью точности.
2.2 Постановка задачи нелинейного программированияВ общем виде задача нелинейного программирования состоит в определении максимального или минимального значения функции
Z=f(x1, x2,…,xn)при условии, что её переменные удовлетворяют соотношениям:
φx1, x2,…,xn=bii=1,k,φx1, x2,…,xn≤bii=k+1, m,где f и φ – некоторые известные функции n переменных, а bi – заданные числа.
Обычно на некоторые переменные x1, x2, …,xn накладывается условие неотрицательности. Кроме того, ограничением может служить условие целочисленности решения для ряда переменных.
В данной курсовой работе рассмотрим задачу условной нелинейной оптимизации:
Предприятие изготавливает не менее N изделий по двум технологическим способам производства. При производстве одного изделия первым способом его себестоимость равна 3+x1, а вторым - 1+x2, где x1, x2 - объёмы производства продукции по соответствующему технологическому способу. Требуется найти, сколько изделий изготовить по каждому из способов производства, чтобы себестоимость производственной продукции была минимальной.
Глава 2. Некоторые методы решения задач нелинейной оптимизацииЦелевая функция данной задачи имеет вид:
fx1, x2=3+x1x1+1+x2x2→min, или fx1, x2=3x1+x12+x2+x22→min.Минимум этой функции находится при ограничениях:
-x1-x2≤-N;x1≥0;x2≥0.В данной задаче нелинейной является целевая функция, так как содержит неизвестные во второй степени.
Задача нелинейного программирования в общем виде состоит в отыскании такого вектора неизвестных x=(x1,x2,…,xn), который обращал бы в минимум (максимум) функцию
Z=fx1, x2,…,xn,
а так же удовлетворял бы поставленному ограничению
φix1,x2,…,xn=bi,, i=1,m (в данной задаче m=1, n=2).
На переменные x1, x2 накладывается условие неотрицательности.
3.1 Метод множителей Лагранжа.Чтобы найти решение задачи нелинейной оптимизации методом множителей Лагранжа, существует следующий алгоритм:
Оставить функцию Лагранжа;
Найти частные производные этой функции по неизвестным величинам xjj=1,n, λii=1,m, приравнять их к нулю;
Решить полученную систему уравнений и тем самым определить стационарные точки функции Лагранжа;
Среди стационарных точек функции Лагранжа, взятых без координат λii=1,m, выбрать точки, в которых достигается условный экстремум функции f(x), вычислить значения функции в этих точках и выбрать среди них точку с минимальным (максимальным) значением функции.
Функция Лагранжа имеет вид
Lx1, x2,…,xn,λ1, λ2,…,λm=fx1, x2,…,xn+i=1mλiφi(x1, x2,…,xn),
где λ1, λ2,…,λm – множители Лагранжа.
Необходимое условие экстремума сводится к существованию решения системы уравнений, образованной после выполнения пункта 2, а достаточные условия выводятся, если для функций fx1, x2,…,xn и φix1, x2,…,xn, i=1,m, существуют вторые частные производные и они непрерывны. Если функция fx1, x2,…,xn имеет в стационарной точке функции Lx1, x2,…,xn,λ1, λ2,…,λn условный минимум, то в этой точке второй дифференциал ∂2L>0, если же функция имеет условный максимум, то ∂2L<0.
Так как ограничение дано в виде неравенства, задача предусматривает отклонение от алгоритма:
Находят стационарные точки безусловного экстремума целевой функции fx1, x2,…,xn. Для этого определяют частные производные функции fx1, x2,…,xn и приравнивают их к нулю. В результате получают систему n уравнений относительно n переменных. Из всех решений системы выбираем только те точки, которые удовлетворяют системе строгих неравенств:
φix1,x2,…,xn<bi,, i=1,mНаходят точки условного экстремума целевой функции F при условиях: φix1,x2,…,xn=bi,, i=1,mИз найденных точек выбираем подходящие нам по условиям и ограничениям.
Найдём стационарные точки безусловного экстремума целевой функции fx1, x2=3x1+x12+x2+x22 при φix1,x2,…,xn<bi,, i=1,m:
∂f∂x1=3+2x1=0,∂f∂x2=1+2x2=0≡x1=-32,x2=-12 , fx1, x2=-2,5.
φ-32,-12=-2 >-141 – точка не соответствует условиям.
Найдём стационарные точки условного экстремума целевой функции при φix1,x2,…,xn=bi,, i=1,m:
Для рассматриваемой задачи функция Лагранжа следующая:
Lx1,x2,λ= 3x1+x12+x2+x22+λ(N-x1-x2).
Вычислим частные производные функции Лагранжа и приравняем их к нулю:
∂L∂x1=3+2x1-λ=0,∂L∂x2=1+2x2-λ=0,∂L∂λ=N-x1-x2=0.≡2x1-λ=-3,2x2-λ=-1,-x1-x2=-N.Составим расширенную матрицу и решим систему матричным методом:
20-102-1-1-10-3-1-NA=20-102-1-1-10, B=-3-1-N, X=x1x2x3A=2*2*0+-1*0*-1+-1*0*-1—1*2*-1-0*0*0-2*-1*-1=-4A-1=14-14-24-1414-24-24-24-44X=A-1*B
x1x2x3=14-14-24-1414-24-24-24-44*-3-1-N=-3+1+2N43-1+2N46+2+4N4=N-12N+12N+2Решив систему линейных уравнений, получим стационарную точку с координатами x1=N-12, x2=N+12, λ= N+2. f(N-12,N+12)min=N2+4N-12φN-12,N+12=N – точка соответствует условиям.
Рассмотрим достаточные условия экстремума, для чего найдём С=∂2L∂x12=2, D=∂2L∂x22=2, E=∂2L∂x12x22=0. Составим определитель второго порядка ∆=СEED=2002=4>0. Так как ∆>0 и C>0, то точка с координатами x1=N-12, x2=N+12 является точкой минимума.
2664460499745-132080499745 Чтобы произвести пересчёт задачи при изменении N, необходимо только в векторе B изменить значение N, например:
f(244,245)min=120538, f(143,144)min=41758Из решения видно, что чем больше количество производимых изделий, тем выше минимум функции.
Основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы уравнений, к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума. Методы, подразумевающие такое решение, называются непрямыми. Они могут быть применены для весьма узкого класса задач, для которых удается получить линейную или сводящуюся к линейной систему уравнений.
3.2 Квадратичное программированиеДля решения задачи квадратичного программирования
fx=j=1ncjxj+s=1nj=1n∂sjxsxj→minпри ограничениях
j=1naijxj≤bi,i=1,mxj≥0, j=1,nгде s=1nj=1n∂sjxsxj является отрицательно (положительно) полуопределённой квадратичной формой, необходимо:
Составить функцию Лагранжа, она записывается в форме:
Lx1, x2,…,xn,λ1, λ2,…,λm=j=1ncjxj+s=1nj=1n∂sjxsxj+i=1mλi(bi-j=1naijxjВзять частные производные функции Лагранжа и записать их в виде выражений
∂L∂xj≥0,j=1,n,xj∂L∂xj=0,j=1,n,xj≥0, j=1,n,∂L∂λi≥0,i=1,m,λi∂L∂λi=0,i=1,m,λi≥0, i=1,m,– локальных условий Куна-Такера (необходимых и достаточных условий существования седловой точки функции Лагранжа).
Преобразовать неравенства системы в равенства, для чего добавить к левой части ограничений, если оно меньше или равно правой ( вычесть из неё, если оно больше или равно правой части) дополнительные неизвестные wi, i=1,m (vj, j=1,n). В результате система запишется в виде:
∂L∂xj-vj=0, j=1,n,∂L∂λ+wi=0, i=1,m,xjvj=0, j=1,n,λiwi=0, i=1,m,xj≥0, vi≥0, j=1,n; λi≥0, wi≥0, i=1,m.Используя симплекс-метод (метод искусственного базиса), найти координаты седловой точки, решая систему с учётом условий, либо убедиться, что ограничения задачи противоречивы.
Искусственные переменные y 1 вводятся в те уравнения, где это необходимо.
Записать оптимальное решение исходной задачи и вычислить значение целевой функции
Кроме рассмотренного подхода к решению задач квадратичного программирования , существует ряд других методов, таких как: метод Била, метод Баранкина-Дорфмана, метод М.Франка и Ф. Вулфа.
Итак, для решения рассматриваемой задачи, представим функцию в виде fx1,x2=f1x1,x2+f2x1,x2Квадратичная форма f1x1,x2=x12+x22является положительно определённой, а, следовательно, выпуклой. Вторая часть функции f2x1,x2=3x1+x2 является линейной и её можно рассматривать как вогнутую. Ограничение представляет собой также линейную функцию и также может рассматриваться как вогнутое множество.
Так как в задаче квадратичного программирования множество допустимых решений выпукло, то, если целевая функция выпуклая, то любой локальный минимум также и глобальный.
Функция Лагранжа уже была составлена ранее, ей и воспользуемся:
Lx1,x2,λ= 3x1+x12+x2+x22+λ(N-x1-x2)Затем переходим ко второму пункту и составляем частные производные функции Лагранжа c учётом направления оптимизации:
∂L∂x1=3+2x1-λ≥0,∂L∂x2=1+2x2-λ≥0,∂L∂λ=N-x1-x2≤0.x1∂L∂x1=x13+2x1-λ=0,x2∂L∂x2=x2(1+2x2-λ)=0,λ∂L∂λ=λN-x1-x2=0.x1≥0, x2≥0,λ≥0.Приведём к равенствам правые части ограничений посредством ввода дополнительных неизвестных v1, v2, w:
2x1-λ-v1=-3,2x2-λ-v2=-1,x1+x2-w=NИсходя из равенств можно определить:
v1x1=0, v2x2=0, wλ=0.Нахождения базисного решения системы уравнений воспользуемся методом искусственного базиса. Для этого добавим в уравнения системы искусственные неизвестные (равные нулю) y1 и y2 и определим максимальное значение функции F=F1-My1-My2 при ограничениях
2x1-λ-v1+y1=-3,2x2-λ-v2+y2=-1,x1+x2-w=Nи условии неотрицательности всех неизвестных. Разрешив систему относительно базисных неизвестных, получим:
y1=-2x1+λ+v1-3,y2=-2x2+λ+v2-1,w=x1+x2-N.Применяя модифицированные жордановы исключения, решим систему уравнений. Для записи функции F в таблицу подставим вместо y1 и y2 их правые части из последней системы уравнений и получим:
F=F1-M-2x1+λ+v1-3-M-2x2+λ+v2-1=F1-M-2x1-2x2+2λ+v1+v2-4F=F1+M(2x1+2x2-2λ-v1-v2+4)→min-x1 -x2 -λ -v1 -v2 1
y1 2 0 -1 -1 0 -3
y2 0 2 -1 0 -1 -1
W -1 -1 0 0 0 -N
F F1 0 0 0 0 0 0
M -2 -2 2 1 1 4
Разрешающий столбец выбираем по наименьшему отрицательному элементу последней строки, а строку – по наименьшему симплексному отношению. Предпоследняя строка функции при любом разрешающем элементе будет равна нулю, поэтому в последующих расчётных таблицах исключим её, оставляем только М-строку.
-6584951051560aij
ais
arj
ars
(+)
(-)
00aij
ais
arj
ars
(+)
(-)
Разрешающий элемент заменяем на противоположный. Все элементы разрешающего столбца делим на разрешающий элемент и умножаем на (-1), все элементы разрешающей строки делим на разрешающий элемент. Остальные элементы находим по правилу прямоугольника
crs=arsaij-arjaisaij, r,i=1,m, s,j=1,n, r≠i, s≠j.-x1 y2 -λ -v1 -v2 1
y1 2 0 -1 -1 0 -3
x2 0 1/2 -1/2 0 -1/2 -1/2
W -1 1/2 -1/2 0 -1/2 (-2N-1)/2
F M -2 1 1 1 0 3
По условию y2=0, а столбец с нулевым элементом в верхней части таблицы не влияет на значения неизвестных, так как коэффициенты в этом столбце умножаются на нуль. Следовательно, при перемещении нулей в верхнюю часть таблицы, соответствующие столбцы можно опускать.
y1 -λ -v1 -v2 1
x1 1/2 -1/2 -1/2 0 -3/2
x2 0 -1/2 0 -1/2 -1/2
W 1/2 -1 -1/2 -1/2 -N-2
F M 1 0 0 0 0
w -v1 -v2 1
x1 1/2 -1/4 1/4 (N-1)/2
x2 1/2 1/4 -1/4 (N+1)/2
λ -1 1/2 1/2 N+2
F M 0 0 0 0
Оптимальное решение задачи следующее: x1=(N-1)/2, x2=(N+1)/2, λ=N+2, w=0, v1=0, v2=0, y1=0, y2=0. Это решение удовлетворяет условию v1x1=0, v2x2=0, wλ=0.Следовательно точка (x*, λ*)=(N-12,N+12 ,N+2) является седловой точкой функции Лагранжа исходной задачи, x*=(N-12,N+12) – оптимальное её решение.
f(N-12,N+12)min=N2+4N-12Из выведенной формулы видно, что чем выше N, тем выше минимум функции.
При N=141, x1=70, x2=71 является точкой минимума и минимальная себестоимость f(70,71)min=10222.При N=489, x1=244, x2=245 является точкой минимума и минимальная себестоимость f244,245min=120538.
Метод квадратичного программирования является одним из самых лёгких способов решения оптимизационных задач нелинейного программирования.
3.3 Графический метод решения задачиИтак, вспомним условия задачи. Целевая функция имеет вид
fx1, x2=3x1+x12+x2+x22→min.при ограничениях
-x1-x2≤-N;x1≥0;x2≥0.-69850767715001257300192595500144208519704050077470650240ОДР ограничена линейной функцией x1+x2 ≥ N и координатными прямыми, является неограниченным многогранником.
Положив fx1,x2=Q, имеем 3x1+x12+x2+x22=Q, приведём это уравнение к виду (x1+32)2+(x2+12)2=104+Q. Это уравнение окружности с центром в точке О(-32, -12) и радиусом 104+Q. Изменяя значение Q, будем получать окружности различных радиусов, а следовательно и различные значения функции. Но из данной формулы видно, что чем больше значение функции, тем больше радиус найденной окружности. Так как целью задачи является отыскание минимума функции, следовательно решение данной задачи будет находиться в точке соприкосновения окружности и линейной функции ограничения. Так как центр окружности находится в точке О(-32, -12), а вектор функции ограничения постоянен (1,1), то уравнение прямой на которой располагается точка минимума, следующее: x2=x1+1. Так как точка минимума будет находить на пересечении прямой x1+x2 = N и x2=x1+1, то точка с координатами x1=N-12, x2=N+12 является точкой минимума.
f(N-12,N+12)min=N2+4N-12Графическое решение задачи нелинейного программирования подходит не для каждой задачи НЛП. Даже в том случае, если область допустимых решений задачи представлена системой линейных неравенств, оптимальное решение задачи может находиться в любой точке области: на границе или даже внутри области.
3.4 Информационные технологии Exsel решения задач нелинейного программированияРешение задач нелинейного программирования в Exsel осуществляется командой Поиск решения, в которой реализованы два метода: метод Ньютона и метод сопряженных градиентов. В методе Ньютона для определения направления и шага перемещения в новую точку используются вторые производные. Использование вторых производных ведет к большому объему вычислений на каждом шаге итерационного процесса, но сокращает число шагов для достижения оптимального решения. Метод сопряженных градиентов использует только первые производные, что приводит к сокращению объёма вычислений на каждом шаге итерационного процесса, но и к возможному увеличению числа шагов.
Чтобы решить задачу, введём данные в таблицу, подставив вместо N любое положительное число, например 141:
Ограничения и другие показатели Переменные Левая часть ограничений Вид ограничений Правая часть ограничений
x1 x2 Ресурс =C20 =D20 =C14+D14 >= 141
Себестоимость =3*C20+C20*C20 =D20+D20*D20 =C15+D15
1238250662940В ячейках показаны формулы ограничения и целевой функции. Далее осуществляем Поиск решения:
Выставляются параметры:
center2827и полученный результат:
00
,
что соответствует результатам, полученным при решении данной задачи представленными ранее методами.
ЗаключениеДанная курсовая работа была посвящена вопросу о решении оптимизационных задач нелинейного программирования, при этом были использованы метод множителей Лагранжа, метод приведения задачи к виду задачи квадратичного программирования, с использованием метода искусственного базиса и решения симплекс-таблицы методом Жордановых исключений, так же был использован графический метод решения нелинейных задач и показательным было использование информационных технологий Excel для решения оптимизационных задач НЛП.
В первой главе были даны формулировка понятий «математическое программирование», «оптимизационные задачи нелинейного программирования», была описана общая классификация задач НЛП. Так же была представлена общая постановка задачи нелинейного программирования. Был предоставлен пример задачи НЛП для дальнейшего её исследования.
Вторая глава посвящена решению поставленной задачи указанными выше методами. Была составлена математическая модель задачи, представлены общие алгоритмы решения различными методами и решение данной задачи по приведённым алгоритмам.
Цель, поставленная при написании курсовой работы была достигнута – методы решения оптимизационных нелинейных задач были изучены.
ЛитератураЗамков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике. М.: ДИС, 2001.
Костевич Л.С. Математическое программирование. М.:ООО «Новое знание», 2003.
Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие/ Под науч. ред. проф. Б.А. Суслакова. М.: Издательско-торговая корпорация «Дашков и К◦», 2004.