WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 11 |

Для того, чтобы условия экстремума были справедливы и в особых случаях, функцию Лагранжа записывают в виде k Q (u1,..., un ) = 0Q (u1,..., un ) + (u1,..., un ), =тогда можно утверждать, что для условного экстремума Q (u1,..., un) необходимо существование таких чисел 0,, одновременно не равных нулю, что в точке предполагаемого решения выполнены условия 0 Q (u1,..., un ) Q (u1,..., un ) Q (u1,..., un ) =... = =... = = 0, u1 u un (u1,..., un) = 0.

Если 0 0, то его можно выбрать положительным числом, обычно полагают 0 = 1, это никак не отражается на решении.

П р и м е р 2.3.

2 Требуется найти минимум функции Q (u1, u2) = u1 + u2 при условии u1 + u2 = 1.

Для решения записывается функция Лагранжа 2 Q (u1, u2) = u1 + u2 + (u1 + u2 -1), для которой уже необходимо определить безусловный экстремум. Необходимое условие экстремума даст следующую систему уравнений:

Q (u1, u2) = 2u1 + = 0;

u Q (u1, u2) = 2u2 + = 0, u откуда u1 = –/2, u2 = –/2. Используя уравнение связи u1 + u2 = 1, получают = –1, u1 = 1/2, u2 = 1/2 и соответственно minQ (u1, u2) = 1/2.

П р и м е р 2.4.

По плану производства продукции предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве u1 изделий первым способом затраты равны (4u1 + u1 ) р., а при изготовлении u2 изделий вторым способом они составляют (8u+ u2 ) р. Определить, сколько изделий каждым из способов следует изготовить, так чтобы общие затраты на производство продукции были минимальными.

Математическая постановка задачи состоит в определении минимального значения функции 2 Q (u1, u2) = 4u1 + u1 + 8u2 + u2 при условиях u1 + u2 = 180, u1 0, u2 0.

Задача может быть решена методом множителей Лагранжа. Для этого без учета требования неотри2 цательности переменных составляется функция Лагранжа Q (u1, u2) = 4u1 + u1 + 8u2 + u2 + (180 - u1 - u2).

Необходимое условие экстремума функции Лагранжа дает Q (u1, u2) = 4 + 2u1 - = 0;

u Q (u1, u2) = 8 + 2u2 - = 0, u - 4 - откуда u1 =, u2 =.

2 - 4 - Подстановка найденных значений в условие u1 + u2 = 180 дает + = 180 и, следовательно, = 2 186 и, соответственно, u1 = 91, u2 = 89.

По вторым частным производным можно показать, что найденная точка доставляет минимум функции Q (u1, u2), т.е. если будет изготовлено 91 изделие первым технологическим способом и 89 изделий вторым технологическим способом, общие затраты будут минимальны и составят Qmin = 17 278 р.

2.4 ОСОБЕННОСТИ РЕАЛЬНЫХ ЗАДАЧ Рассмотренные классические методы анализа предполагают известное аналитическое выражение критерия оптимальности, имеющего производные по всем переменным, и позволяют найти экстремум только внутри области изменения независимых переменных. Реальные задачи решать этими методами практически невозможно, так как они имеют ряд особенностей.

1 Целевая функция не является гладкой, она может быть "колючей" (рис. 2.5), и тогда применять необходимые условия экстремума не представляется возможным.

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

Q Q u1 u2 u3 u4 u5 u1 u2 u3 u4 u u Рис. 2.5 "Колючая" Рис. 2.6 Целевая функцелевая функция ция с минимумом на границе 3 Критерий оптимальности задается алгоритмически, производные тогда можно рассчитывать только численными методами. Примером такого критерия является прибыль, которую нельзя аналитически связать с капиталовложениями.

4 Метод множителей Лагранжа предполагает наличие связей в виде равенств. В реальных задачах существуют ограничения и в виде неравенств.

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

3 НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Математическая формулировка задачи принятия решения, как уже отмечалось, эквивалентна задаче отыскания наибольшего или наименьшего значения функции одной или нескольких переменных.

В большинстве практических задач критерий оптимальности Q (u), где u – вектор управляющих переменных, не может быть записан в явном виде, его значение обычно находится в результате решения системы уравнений математического описания оптимизируемого объекта. На независимые переменные ui, i = 1, n могут быть наложены связи и ограничения как в виде равенств (u) = 0, = 1, m, так и в виде неравенств i (u) 0, i = 1, l, которые, как правило, являются нелинейными и трудно вычислимыми соотношениями. Задачи такого типа являются предметом рассмотрения специального раздела математики, называемого нелинейным программированием. Обычно, решения задач нелинейного программирования могут быть найдены только численными методами.

3.1 ОБЛАСТИ ПРИМЕНЕНИЯ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в сфере деловых отношений и в науке управления государством.

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



Метод "затраты – эффективность" также укладывается в схему нелинейного программирования.

Данный метод был разработан для использования при принятии решений в управлении государством.

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

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

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

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

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

В большинстве методов нелинейного программирования используется идея движения в n-мерном пространстве в направлении оптимума. При этом из некоторого исходного или промежуточного состояния ui осуществляется переход в следующее состояние ui+1 изменением вектора ui на величину ui, называемую шагом.

ui+1 = ui + ui. (3.1) При поиске минимума целевой функции Q (u) для удачно выбранного шага должно выполняться условие Q (ui+1) < Q (ui), в противном случае переход в состояние ui+1 нецелесообразен.

В значительной части методов шаг определяется как некоторая функция состояния ui : ui = ui(ui), и, следовательно, новое состояние можно рассматривать как функцию исходного состояния ui+1 = ui + ui (ui).

В этом смысле шаговые методы поиска оптимума называются итеративными.

Методы нелинейного программирования в зависимости от способа задания шага u подразделяются на три основных класса: 1) градиентные методы; 2) безградиентные методы; 3) методы случайного поиска. Некоторые методы организуются как комбинированные алгоритмы, использующие достоинства методов различных классов. Кроме того различают методы одномерной оптимизации (u-скаляр) и многомерной оптимизации (u-вектор).

Задача нелинейного программирования в общем случае рассматривается в n-мерном пространстве, где наглядное графическое изображение отсутствует, в связи с этим используется следующий прием графического представления.

Если целевая функция Q (u) непрерывна в области U, то вокруг точки uопт всегда можно провести в данной плоскости замкнутую линию, вдоль которой значение Q (u) постоянно (рис. 3.1, а). Эти замкнутые линии называются линиями равного уровня функции Q (u) и отвечают различным значениям Q (u) = q. Вокруг точки uопт можно провести сколько угодно линий уровня, причем каждая из них будет целиком охватывает любую линию, для которой значение целевой функции Q (u) меньше (или больше).

При наличии связи (u) = 0, что в n-мерном пространстве определяет (n – 1)-мерную поверхность, пересечение которой с рассматриваемой поверхностью определяет область (рис. 3.1, б), в которой и ищется оптимальное решение.

Ограничения типа неравенств независимо от их числа наглядно представлены на рис. 3.1, в. Здесь заходить в заштрихованную область нельзя.

а) в) б) 1 (u) = • uопт • • (u) = 2 (u) = Рис. 3.1 Геометрическое представление целевой функции:

а – линии равного уровня; б – линии равного уровня и связи типа равенств;

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

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

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





Эта функция должна быть непрерывно дифференцируемой. Для этого вводится понятие производной по направлению l Q (u) Q (u)-Q (u) = lim, (3.2) l u u u- u где u, u* – точки, расположенные на прямой l. Эта производная (3.2) характеризует скорость изменения функции Q (u) в точке и в направлении l, она может быть выражена через производные по координатам, число которых конечно и равно размерности n. Согласно правилу дифференцирования сложных функций, можно записать n Q(u) = (3.3) Q(u) u.

l u l =Рассмотрим расчет u / l в пространстве двух переменных (рис. 3.2).

duИз прямоугольного треугольника АВС можно записать = cos (u1l), dl du= cos(u2l), dl = (du1)2 + (du2)2. Таким образом, величины u / dl есть не что иное, как направляющие dl косинусы выбранного направления l по отношению к осям координат. Следовательно, (3.3) можно переписать следующим образом n Q (u) Q (u) = cos (uil). (3.4) l u =Если теперь рассмотреть поверхность равного уровня, которая имеет (n – 1) независимых переменных, то в каждой точке этой поверхности, называемой гиперповерхностью, можно провести (n – 1) взаимно перпендикулярных касательных в соответствии с числом измерений этой поверхности. Кроме того, в этой же точке можно провести ось, перпендикулярную всем касательным и, следовательно, направленную по нормали к поверхности. Подобное построение для случая (n = 3) изображено на рис. 3.3.

u B l du A C du uРис. 3.2 К определению направляющих косинусов u3 l Q(u1, u2, u3) = uuРис. 3.3 Система координат, связанная с произвольной точкой поверхности постоянного уровня Касательные и нормаль могут рассматриваться как система координат с началом в выбранной точке поверхности. Данная система координат обладает тем важным свойством, что частные производные от функции Q (u) по направлениям осей равны нулю, так как вдоль этих направлений функция Q (u) сохраняет постоянное значение. В соответствии со сказанным производная по произвольному направлению l запишется как Q(u) Q(u) = cos(ul), (3.5) l u что следует из (3.4), где производные по всем осям, за исключением нормали, оказываются равными нулю.

Максимальное значение cos по абсолютной величине не превышает единицы, аргумент при этом равен нулю, следовательно, направление, по которому производная Q / l имеет максимальное значение, совпадает с направлением нормали к поверхности постоянного уровня функции Q (u). Если теперь Q по направлению нормали отложить вектор длиной равной, то полученный вектор называется граu диентом скалярной функции Q (u) в точке u и обозначается Q (u) (читается "набла ку") или ( gradQ(u) ).

Q(u) Формулу (3.5) можно записать как = l = l Q (u), где l Q (u) – проекция градиента функции Q (u) по направлению l. Отсюда следует, что проекции вектора градиента на оси координат равны производным функции Q (u) по соответствующим пе Q Q Q ременным, т.е. Q (u) =,,...,.

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

3.3 МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ Задача поиска экстремума функции одной переменной возникает при оптимизации целевой функции, зависящей от одной скалярной переменной. Такие задачи входят составной частью во многие итерационные методы решения задач многомерной оптимизации.

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

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

3.3.1 Метод прямого сканирования Задача заключается в локализации экстремума функции одной переменной, заданной на интервале [a, b] с точностью до. При решении этой задачи весь интервал разбивается на участки величиной. В узлах разбиения вычисляются значения функции Q и из них выбирается экстремальное. Этот метод требует больших затрат времени (зависящего от значения ), но главное его преимущество – это определение глобального экстремума. Блок-схема алгоритма поиска Q (x) представлена на рис. 3.4, б.

Q а) a b u б) Начало ввод a, b, x = a вычисление Q(x) x = x + да x = a нет да Q < Qmin Qmin = Q; xmin = x нет да x < b нет вывод xmin, Qmin Останов Рис. 3.4 Локализация экстремума методом сканирования:

а – геометрическая интерпретация; б – блок-схема алгоритма 3.3.2 Метод половинного деления Естественным и наиболее распространенным на практике методом поиска экстремума функции одной переменной является метод последовательного деления отрезка пополам. Этот метод был известен еще в древней Греции как метод дихотомии.

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке [a, b] с точностью. Отрезок [a, b] делится пополам и вычисляются значения функa + b ции Q (x1) = F1 и Q (x2) = F2 в точках x1,2 = ±.

2 На основе анализа значений F1 и F2 вдвое уменьшается интервал неопределенности и процесс повторяется пока b – a >. Блок-схема этого метода приведена на рис. 3.5, б.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 11 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.