MOR2014

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

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

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

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

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

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

61

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

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

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

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

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

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

ваться из затрат на «старых» по 80 тыс. руб. на человека и затрат на новых по80 20 100 тыс. руб. на человека. Суммарные затраты составят:

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

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

62

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

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

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

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

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

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

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

1000x 80 0 .

63

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

Однако данное значение не попадает в интервал: 156,25 40;70 . Значит на

указанном интервале нулей производной нет.

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

Таким образом, x 100 является корнем производной. Рассмотрим интервал 150 x . На нем имеем уравнение:

1000x 100 0 .

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

Это значение не принадлежит рассматриваемому интервалу: 100 150; .

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

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

P 100 2000100 100 100 1400 20000 10000 1400 11400 .

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

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

В точке x 70 функция имеет излом, но остается непрерывной. Ее значения с обеих сторон совпадают и равны:

P 70 200070 80 70 16733 5600 11133.

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

В точке x 150 функция имеет скачек. Ее значения разные с двух сторон.

64

При x 150 предел будет равен:

lim P x 2000150 100 150 1400 24495 15000 1400 10895.

x 150 0

При x 150 предел будет равен:

lim P x P 150 2000150 100 150 1700 24495 15000 1700 11195 .

x 150 0

Таким образом, наняв 150 рабочих получим прибыль, равную 11195 тыс. руб. Замечание 1. В данной задаче из условия целочисленности числа рабочих

можно было не искать значения пределов, а проверить значение прибыли при 150 и 149 рабочих.

Замечание 2. Из экономического смысла задачи очевидно, что предел справа (когда субсидия будет выплачена) будет лучше, чем предел слева (без субсидии).

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

P 40 200040 80 40 9449 .

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

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

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

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

P 40 9449 ,

P 70 11133 ,

P 100 11400 ,

P 150 11195,

P .

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

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

65

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

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

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

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

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

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

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

Построим на одном графике все три функции, описываемые уравнениями

(4), (5), (6) (см рис. 1).

66

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

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

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

67

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

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

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

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

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

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

68

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

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

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

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

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

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

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

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

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

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

69

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

Замечание: небольшое отличие значения в ячейке для искомой переменной от точного (получилось x 100,0000003 вместо x 100 ) обусловлено чис-

ленной реализацией метода поиска. Это значение можно смело округлить с заданной точностью.

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

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

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

70