Дисциплина: МЕТОДЫ ОПТИМИЗАЦИИ

Электронные гипертекстовые методические указания студентам
для выполнения практических и лабораторных работ с помощью программы MathCAD

Автор: Коднянко В.А.
 

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

      График этой функции показан на рис. 2.1.

Рис.2.1. Зависимость затрат Z от доли p работающих, прошедших оздоровление

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

     Очевидно решением является такое значение p, при котором достигается минимум функции Z(p).

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

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

     Для решения задач поиска максимума и минимума функции будем использовать аппарат программы Mathcad, а именно встроенные функции Minimize и Maximize. Эти функции используют градиентные и квазиньютоновские численные методы поиска экстремума функции. В общем случае градиентом функции называют вектор с координатами, равными частным производным по соответствующим аргументам. Градиент указывает направление наибольшего возрастания функции. Противоположное направление называется антиградиентом, оно показывает направление наискорейшего убывания функции. В точке экстремума градиент равен нулю. Двигаясь по градиенту (антиградиенту) можно достичь максимума (минимума) функции. В этом состоит сущность градиентного метода оптимизации. Квазиньютоновские методы основаны на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента.

     Рассмотрим функцию f(x), которая показана на рис. 2.2.

Рис. 2.2. График функции одной переменной

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

2.1. Нахождение локальных минимумов функции   

     Найдем, к примеру, локальный минимум функции, который лежит в интервале -1< x < 0. Для этого запишем и выполним несколько операторов, которые расположены на рис. 2.3 справа от графика функции.

Рис. 2.3. Поиск локального минимума функции

     Сначала зададим начальное приближение для аргумента. Его следует выбрать вблизи экстремума. Например, можно положить x = -1. Затем следует обратиться к функции Minimize, указав первым аргументом имя функции, а вторым - начальное значение аргумента. Результат вычисления аргумента в точке минимума будет помещен в переменную p. Дальше можно вывести значение аргумента (для этого следует набрать "p=" (кавычки набирать не нужно) и программа сама покажет результат в виде числа) и значение функции в точке минимума (следует набрать "f(x)="). Если набрать оператор "x=", то можно убедиться, что в переменной x по-прежнему остается начальное значение аргумента. В результате получен минимум функции в точке p = -0.714, который равен f(x) = -4.439.

     Теперь найдем какой-нибудь другой локальный минимум функции. Например тот, который лежит в диапазоне 1 < x < 3. В качестве начального значения аргумента для поиска этого минимума можно задать, например, x = 2. Результат показан на рис. 2.4.

Рис. 2.4. Неудачный поиск локального минимума функции

     Как видно из рис. 2.4, метод вновь показал нам уже ранее найденный экстремум. То есть безусловный метод оптимизации не позволил получить желаемый результат.

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

Рис. 2.5. Метод условной минимизации функции

     Результат минимизации показан на рис. 2.5. Как видим, теперь желаемый локальный минимум найден и он находится в точке x = 2.136; f(x) = 0.04.

     Если провести оптимизацию издержек Z(p) рассмотренной выше задачи, то получим следующий результат (рис. 2.6):

Рис. 2.6. Оптимизация затрат

     Полученный результат свидетельствует, что наименьшие издержки Z(p) = 0.74 имеют место в том случае. когда доля работающих, прошедших оздоровление p = 0.636. То есть при оптимальной доле p приведенные издержки Z предприятия можно уменьшить на (1-0.74)*100 = 26%.

2.2. Нахождение локальных максимумов функции   

     Нахождение максимума проводится аналогично, только вместо функции Minimize применяется функция Maximize. Найдем, к примеру, локальный максимум функции, который находится в диапазоне 0 < x < 2. Результат показан на рис. 2.7. Искомый локальный максимум находится в точке x = 0.873; f(x) = 5.686.  

Рис. 2.7. Метод условной максимизации функции

      Экстремумом функции называют ее наибольшее или наименьшее значение. Наибольшее значение называется максимумом, наименьшее – минимумом. Экстремум достигается в некоторой точке x =  x0 и для него характерно f(x) ≥  f(x0) – для минимума и f(x) ≤  f(x0) – для максимума. Если область изменения аргумента ограничена, то экстремум может иметь место на границе и приведенные условия могут не выполняться. Различают локальные и глобальные экстремумы. На некотором интервале изменения аргумента функция f(x) может иметь несколько локальных экстремумов. Наибольший из локальных максимумов называется глобальным экстремумом-максимумом, а наименьший из локальных минимумов – глобальным экстремумом-минимумом. Функция одной переменной, имеющая в интервале исследования один максимум (минимум), называется унимодальной.

2.3. Поиск экстремума функции посредством составления собственной программы

Рассмотрим задачу численного нахождения минимума функции на интервале x (a, b) с абсолютной погрешностью e. Для этого  применим метод дихотомии.

Суть метода такова (рис. 1). Сначала найдем середину интервала x = (a+b)/2 и вычислим  в  близких  друг  к  другу  точках x₁ = x-e и x₂ = x+e два значения функции f₁ = f(x₁) и f₂ = f(x₂). Если окажется f₁ < f₂, то функция в середине отрезка возрастает и, следовательно, дальнейший  поиск  ее минимума следует  вести в интервале (a, x₁), положив b = x₁. Если f₁ > f₂, то функция в середине отрезка убывает и поиск минимума следует вести в интервале (x₂, b), положив a = x₁. Таким образом, за два вычисления функции область поиска уменьшается примерно вдвое. К уменьшенному интервалу (a, b) вновь применим описанные действия. Процесс будем повторять до тех пор, пока длина интервала (a, b) не станет меньше заданной погрешности e.

Рис. 2.8. Геометрическая интерпретация метода дихотомии

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

Запрограммируем метод дихотомии. Текст функции Dichotomy приведен ниже (новый уровень операторов и строку добавляют командой AddLine панели Programming).

В качестве примера снова рассмотрим функцию . Ее график приведен на рис. 2.9.

Рис. 2.9. График функции

Нетрудно видеть, что на интервале (0, 2) функция имеет 3 локальных минимума. Один из них лежит в интервале (0,3; 1), второй в интервале  (1; 1,5) и третий в интервале (1,5; 2). Найдем их, используя функцию Dichotomy с погрешностью 0,0001. Получим следующие результаты:

Этим мы нашли абсциссы минимумов. Зная их, легко найти сами минимумы функции. Для этого составим такие операторы:

Чтобы модифицировать функцию под алгоритм поиска максимума функции, достаточно а программе поменять знак ">" на знак "<" в операторе сравнения значений функции. Внесем это изменение в программу и, указав интервалы отделения максимумов, найдем видимые на графике  рис. 2 максимумы исследуемой функции:

2.4. Экстремум функции нескольких переменных

Вычисление экстремума функции нескольких переменных может быть выполнено при помощи уже известных нам функций Minimize и  Maximize. В качестве примера рассмотрим следующую функцию двух переменных:

.

Построим ее график. Для этого на наборной панели График щелкнем на значке . При этом получим заготовку будущего графика. Она выглядит примерно так, как показано на рис. 2.10.

Рис. 2.10. Заготовка объемного графика функции

Примечание. Если у Вас ноутбук и на нем не выводятся графики поверхности или 3D графики в MathCAD, то положение можно исправит. Одна из причин не отображения графиков поверхности или 3D графиков это "Качество цветопередачи". Чтобы Вы смогли увидеть интересующий вас график, заходим в Панель управления операционной системы Windows. Далее выбираем Оформление, Экран, Разрешение экрана. А теперь находим ссылку в "Дополнительные параметры". В появившемся окне выбираем закладку "Монитор". Скорее всего у Вас в списке "Качество цветопередачи" (опция, расположенная внизу окна) по умолчанию установлено в True Color (32 бита). Для устранения неполадок надо выбрать High Color(16 бит) и нажать на кнопку OK или Применить.

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

В левый нижний заполнитель внесем имя функции (f).  При этом сразу получим график рассматриваемой функции:

Рис. 2.11. Нередактированный график функции f(x,y)

Немного приукрасим его. Щелкните дважды на графике. При этом откроется окно Формат 3D графика (рис. 2.12). 

Рис. 2.12. Окно Формат 3D графика

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

Рис. 2.13. Отредактированный график функции f(x,y)

Видно, что функция  f(x,y) в пространстве переменных x, y имеет выраженный минимум. Чтобы найти его запишем приблизительные начальные значения аргументов минимума и оператор его вычисления:

Это означает, что минимум функции f(x,y) найден а точке x = 0,5 и y = 0,6.

2.5. Индивидуальные задания для выполнения работы № 2

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

№	Функция	Интервал	№	Функция	Интервал
1.		[-5; 2]	2.		[-3; 2]
3.		[-6; 4]	4.		[2; 8]
5.		[-3; 5]	6.		[-5; 4]
7.		[-2; 5]	8.		[2; 8]
9.		[1; 7]	10.		[1; 7]

Возврат к меню