Необходимое условие локального безусловного экстремума во внутренних точках

⇐ ПредыдущаяСтр 4 из 4

Если дифференцируемая функция имеет локальный экстремум во внутренней (не бесконечной) точке , то ее градиент в этой точке равен нулю.

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

Пример.

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

4. Способы определения условного экстремума

Пусть требуется решить задачу на отыскание условного экстремума:

(1)

Существуют два подхода к решению.

4.1. Выражение одной переменной через другие.

Можно выразить из условий (1) некоторые переменные через другие и подставить в функцию. Получим задачу на безусловный экстремум.

Достоинства подхода:

Ø снижается число переменных;

Ø снижается число уравнений;

Ø подход интуитивно понятен.

Недостатки:

Ø навязывается неравнозначность переменных (основные и зависимые);

Ø после исключения сложно проанализировать влияние условий;

Ø очень часто не удается явно выразить одну переменную через другие.

Последний недостаток оказывается критичным и непреодолимым при сложных зависимостях.

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

Для каждого ограничения вводится неизвестный множитель . После этого ищется безусловный экстремум для функции Лагранжа:

То есть записываются условий:

второй столбик условий, очевидно, является системой условий (1).

Недостатки подхода:

Ø подход интуитивно не очевидный;

Ø увеличивается количество неизвестных и количество уравнений;

Ø сложные зависимости остаются в системе.

Достоинства:

Ø всегда удается записать всю систему уравнений до того, как приходится выражать одну переменную через другие, следовательно, такой подход универсален;

Ø множители Лагранжа имеют четкий смысл и позволяют проанализировать влияние ограничений.

Смысл множителей Лагранжа. Множитель Лагранжа, определенный для ограничения, показывает относительное изменение оптимального значения целевой функции при изменении правой части ограничения. То есть, если правая часть какого-либо из ограничений (1) изменится на некоторое значение, то и оптимальное значение функции тоже изменится. Отношение изменения функции к малому изменению ограничения равно множителю Лагранжа.

Кроме этого, множителя Лагранжа продолжают играть важную роль для задач нелинейного программирования, когда вместо ограничений равенствами (1) присутствуют ограничения соответствующими неравенствами ( вместо ). Тогда ненулевой множитель Лагранжа означает выполнение в оптимальном случае соответствующего ограничения как равенства и имеет такой же смысл как для равенств. Нулевой множитель Лагранжа говорит о том, что в оптимальном случае соответствующее ограничение выполнено как строгое неравенство.

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

5. Теорема Куна-Таккера для задачи нелинейной оптимизации.
Простейшая интерпретация и способ применения

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

Для задачи нелинейного программирования:

(2)

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

1) равенство нулю градиента функции в этой точке;

2) отсутствие градиента функции в точке;

3) равенство нулю хотя бы одного из ограничений (2);

4) бесконечная точка.

Заметим, что равенство нулю ограничений (2) достигается на границе области.

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

1) найти градиент функции;

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

3) определить все точки, где градиент не существует; в тех из них, которые удовлетворяют ограничениям, вычислить значение функции (если возможно);

4) определить максимальные и минимальные значения функции на границах области;

5) исследовать функцию на бесконечности, найти там максимальное и минимальное значение функции;

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

В общем случае проделать эти операции очень непросто. В п.п. 2) и 3) градиент может быть равен нулю или не существовать в бесконечном количестве точек – например на линии или на поверхности в многомерном пространстве. Пункт 4) вообще приводит к самостоятельной задаче поиска условного экстремума. Исследование функции на бесконечности – тоже нетривиальная задача.

Специфика задач экономики и управления заметно упрощает применение этих операций.

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

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

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

Разбор примера задачи нелинейной оптимизации

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

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

Как видно из данных примера, весь анализ можно провести в терминах количества рабочих. Обозначим через число рабочих на предприятии. Так как мы не можем уволить более 30 человек из имеющихся 70, то переменная ограничена снизу: .

Выпуск продукции пропорционален численности и равен м³ в мес. Доход от продажи в месяц тогда равен:

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

(3)

Если не нанимать новых сотрудников, то будет выполняться условие , а месячные расходы равны:

Если нанять новых рабочих, то . Из этого количества рабочих 70 будут «старых», а – «новых». Тогда месячные расходы будут складываться из затрат на «старых» по 80 тыс. руб. на человека и затрат на новых по тыс. руб. на человека. Суммарные затраты составят:

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

(4)

Прибыль комбината (без учета постоянных расходов) равна разнице между доходами (3) и переменными расходами (4) и запишется в виде:

(5)

Таким образом, математически задача формулируется так: найти , при котором функция прибыли (5) имеет максимум.

Очевидно, функция (5) меняется непропорционально искомой переменной и задача является нелинейной.

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

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

(6)

Как видно из выражения (6), производные на втором и третьем интервалах совпадают, но между ними при производная не существует, так как функция терпит разрыв.

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

Рассмотрим интервал . На нем имеем уравнение:

Решая уравнение, находим

Однако данное значение не попадает в интервал: . Значит, на указанном интервале нулей производной нет.

Рассмотрим интервал . На нем имеем уравнение:

Решая уравнение, находим

Данное значение принадлежит рассматриваемому интервалу: . Таким образом, является корнем производной.

Рассмотрим интервал . На нем имеем уравнение:

Решая уравнение, находим

Это значение не принадлежит рассматриваемому интервалу: . Значит на указанном интервале нулей производной нет.

Итак, производная равна нулю только в точке . Определим значение функции в этой точке:

То есть наняв 100 рабочих получим прибыль, равную 11400 тыс. руб.

3) Определим точки, где производная не существует. Это все точки границ интервалов. Найдем в них значение функции:

Если останутся прежние 70 рабочих, то прибыль будет 11133 тыс. руб.

Наняв 150 рабочих получим прибыль, равную 11195 тыс. руб.

4) Единственной границей области в данном случае является . При этом значении:

То есть при 40 работниках прибыль будет равна 9449 тыс. руб.

5) Поведение функции на бесконечности можно не рассматривать, как в задачах экономики. Однако, если это сделать, то получим:

Как и ожидалось, нанимая неограниченное количество рабочих будем получать неограниченные убытки.

6) Из всех найденных значений целевой функции выберем самое большое. Собираем все значения вместе:

Как видно, наибольшее значение достигается при .

Таким образом, оптимальное управленческое решениебудет таким:

Ø Необходимо привлечь к работе всего 100 человек: 70 уже имеющихся и 30 новых. В этом случае мы получим наибольшую прибыль, равную 11 миллионов 400 тысяч рублей.

Ответить на вопросы, поставленные перед собой новым руководителем, можно так:

Ø Имеющееся количество рабочих не оптимально. Необходимо нанять еще 30 человек. Нанимать рабочих до 150 человек не выгодно, так как получаемая субсидия вместе с ростом доходов не компенсирует полученный рост расходов.

Сделаем еще несколько замечаний.

Ø Если мы сравним суммы прибыли при текущем количестве рабочих (11 млн. 133 тыс. руб.) и оптимальным (11 млн. 400 тыс. руб.), то видно, что прибыль меняется всего на 267 тыс. руб. или менее чем на 3%. Необходимо как следует проанализировать, стоит ли менять сложившийся вариант работы ради таких незначительных изменений. Для анализа необходимо уже будет учесть постоянные издержки. Если они велики, то прибыль с их учетом становится значительно меньше и дополнительные 267 тыс. руб. в месяц являются уже существенным выигрышем.

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

Графическая интерпретация решения.

Построим на одном графике все три функции, описываемые уравнениями (4), (5), (6) (см рис. 1).

Рис. 1. Графики зависимости экономических показателей
от количества рабочих

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

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

Методика и специфика решения задач
нелинейной оптимизации в MS Excel

Задачу оптимизации нелинейной функции (6) можно было бы решить не путем анализа с использованием производной, и используя инструмент «Поиск решения» в MS Excel.

Если реализовать вычисления функции (6) по значению переменной в ячейке (см. рис. 2), то можно определить оптимально значение переменной в этой ячейке.

Рис. 2. Реализация вычисления функции прибыли в MS Excel

Для оптимизации используем инструмент «Поиск решения». Настраиваем параметры поиска решения (рис. 3) следующим образом:

Рис. 3. Настройка инструмента «Поиск решения»

· в поле «Оптимизировать целевую функцию» указываем ячейку, где реализована формула для прибыли;

· в поле «До» указываем «Максимум»;

· в поле «Изменяя ячейки переменных» указываем ячейку, предназначенную для значения переменной ;

· в поле «В соответствии с ограничениями» добавляем ограничение невозможности большого увольнения ;

· состояние поля «Сделать переменные без ограничений неотрицательными» в нашей задаче безразлично, так как единственная переменная ограничена;

· в поле «Выберите метод решения» выбираем «Поиск решения нелинейных задач методом ОПГ» (так как наша задача нелинейная).

Нажав кнопку «Найти решение» получаем форму «Результаты поиска решения» (рис. 4). Убедившись, что в этом окне написано «Решение найдено. Все ограничения и условия выполнены», выбираем «Сохранить найденное решение» и нажимаем кнопку «Ок».

Рис. 4. Форма «Результаты поиска решения»

В ячейке переменной получаем оптимальное решение (рис. 5).

Рис. 5. Значения переменных после оптимизации

Как видим, нам удалось найти правильное решение автоматически.

Замечание: небольшое отличие значения в ячейке для искомой переменной от точного (получилось вместо ) обусловлено численной реализацией метода поиска. Это значение можно смело округлить с заданной точностью.

Важно отметить такую специфику решения нелинейных задач в MS Excel. Поиск решения методом ОПГ ищет значения переменных от начального заданного, обеспечивая постоянное улучшение результата с текущего места. Такая реализация приводит к поиску локального, а не глобального экстремума. Так, «начав» поиск от 70 рабочих мы нашли оптимальное значение 100 человек. Начав же, например, со 160 человек, получим «оптимальное» количество 150 (рис. 6). Выбрав же вначале 200 человек можно снова прийти к оптимальному значению 100.

Рис. 6. Изменение решения при смене начального приближения

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

Задание для самостоятельного решения

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

В задании данной темы:

;

– последняя цифра номера зачетной книжки;

– предпоследняя цифра номера зачетной книжки.

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

Задание

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

· Цена продажи одного станка равна млн. руб.

· Постоянные издержки фирмы равны млн. руб., переменные издержки равны млн. руб.

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

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

Ø Сформулируйте оптимальное экономико-управленческое решение в имеющихся условиях.

Ø Дайте экономическое обоснование полученного решения.

Ø Приведите сравнение предлагаемого Вами плана выпуска станков с используемым ранее вариантом. Обоснуйте необходимость изменений.

Ø Приведите график зависимости прибыли от количества выпускаемой продукции. Обоснуйте свое решение с помощью графика.

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

1. Исследование операций в экономике: учеб. пособие / под ред. Н.Ш. Кремера – 2-е изд., перераб. и доп. – М.: Юрайт, 2010. – 430с.

2. Юкаева, В. С. Принятие управленческих решений: учебник / В.С.Юкаева, Е.В.Зубарева, В.В.Чувикова – М.: " Дашков и К", 2012. – 324с.

3. Дорогов, В. Г. Введение в методы и алгоритмы принятия решений: Учебное пособие / В.Г.Дорогов, Я.О.Теплова. – М.: ИД ФОРУМ: ИНФРА-М, 2012. - 240 с. – режим доступа http: //znanium.com.

4. Фатхутдинов, Р. А. Управленческие решения: Учебник / Р.А. Фатхутдинов. − М.: ИНФРА-М, 2010. − 344 с. – режим доступа http: //znanium.com.

5. Соколов, А. В. Методы оптимальных решений. В 2 т. Т. 1. Общие положения. Математическое программирование: Учебное пособие / Соколов А.В., Токарев В.В. − М.: ФИЗМАТЛИТ, 2011. – 564 с.

6. Токарев, В.В. Методы оптимальных решений. В 2 т. Т.2. Многокритериальность. Динамика. Неопределенность.: Учебное пособие / Токарев В.В. – М.: ФИЗМАТЛИТ, 2011. – 420 с.

7. Арсеньев, Ю.Н. Принятие решений. Интегрированные интеллектуальные системы: Учеб. пособ. / Ю.Н. Арсеньев, С. И. Шелобаев, Т. Ю. Давыдова. – М.: Издательство ЮНИТИ-ДАНА, 2003. – 270с.

8. Балдин, К.В. Управленческие решения: Учебник / Балдин К.В., Воробьев С.Н., Уткин В.Б.. – М.: «Дашков и К°», 2012. - 496 с.

Электронные ресурсы:

9. Стандарт ФГОС ВПО

10. Иванов, Л. Н. Анализ стратегических решений (эвристика) / Л.Н. Иванов. – М.: ИЦ РИОР: ИНФРА-М, 2010. – 177 с. – режим доступа http: //znanium.com.

11. Дружелаускайте, Е. В. Искусство правильного принятия решений / Е.В. Дружелаускайте. – М.: Форум, 2009. – 176 с. – режим доступа http: //znanium.com.

12. Строева, Е. В. Разработка управленческих решений: Учебное пособие / Е.В. Строева, Е.В. Лаврова. – М.: НИЦ Инфра-М, 2013. – 128 с. – режим доступа http: //znanium.com.

13. Маркова, В. Д. Стратегический менеджмент: понятия, концепции, инструменты принятия решений: Справочное пособие / В.Д. Маркова, С.А. Кузнецова. - М.: ИНФРА-М, 2012. - 320 с. – режим доступа http: //znanium.com.

14. Бражко, Е. И. Управленческие решения: Учебное пособие / Е.И. Бражко, Г.В. Серебрякова, Э.А. Смирнов. – М.: РИОР, 2008. - 126 с. – режим доступа http: //znanium.com.

15. Ломакин, А. Л. Управленческие решения: учебное пособие / А.Л. Ломакин, В.П. Буров, В.А. Морошкин. – М.: Форум, 2009. - 176 с. – режим доступа http: //znanium.com.

16. Смирнов, Э. А. Управленческие решения: Учебник для вузов / Э.А. Смирнов. – М.: ИЦ РИОР, 2009. – 362 с. – режим доступа http: //znanium.com.

17. Сайт материалов кафедры высшей математики ИЭУП (Казань) http: //www.ieml-math.narod.ru

18. Электронные учебники системы дистанционного обучения Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики http: //de.ifmo.ru/bk_netra/select.php

19. Управление экономическими системами. Электронный научный журнал http: //www.uecs.ru/

20. Официальные обучающие материалы Microsoft по Excel и другим офисным программам http: //office.microsoft.com/ru-ru/excel-help

21. Задачи оптимизации в MS Excel http: //exsolver.narod.ru/

22. Решение прикладных задач в MS Excel http: //citforum.ru/pp/excel70.shtml

⇐ Предыдущая 1 2 34