MOR2014

Qопт Q1 36 платьев. Остальные параметры находим по формулам (2) – (5).

опт Qопт 36 0,75мес. 0,75 30дн. 22,5дня

48

qзак tд 0,167 48 8 платьев.

Вывод: при имеющейся системе скидок выгодно пользоваться первой скидкой. Необходимо организовать поставки ровно по 36 платьев примерно каждые 22 – 23 дня (с частотой 4/3 поставки в месяц). Заказ необходимо делать в момент, когда в наличие осталось 8 платьев. Суммарные расходы на поставку и хранение платьев составят примерно 254,55 тыс. руб. за 2 месяца.

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

51

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

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

400 20 b 30 a ; C 100 10a 5b ;

K 40 5b 3a ; tд 2 a b ;

s 40 5a 10b ; T 1 a b ;

P 3 a ;

1

P2 8 a b ; Q1 b 2a 10 ; Q2 80 a 3b ;

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

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

Объем продаж магазина «Ткани» составляет рулонов в год. Величина спроса равномерно распределяется в течение года (365 дней). Цена закупки одного рулона равна C тыс. руб. За доставку и оформление заказа владелец магазина должен заплатить K тыс. руб. Время доставки заказа от поставщика составляет tд дней. Издержки хранения составляют s руб. в день за один рулон.

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

1.Рассмотреть случай поставок без скидок.

2.Определить оптимальные параметры работы системы управления запасов при следующих скидках:

Следует ли владельцу магазина воспользоваться одной из скидок, предоставляемых поставщиком? Каковы при этом будут размер заказа и общие затраты на управление запасами?

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

52

Выписать основные параметры и привести их к одним единицам измерения.

Решить задачу и дать четкие ответы на все вопросы.

53

ТЕМА 3. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ

Основные понятия задач нелинейной оптимизации

Задачи нелинейной оптимизации относятся к задачам принятия решений в полностью детерминированных условиях при наличии непропорциональных связей каких-либо параметров от искомых переменных.

Таким образом, в этих задачах обязательно:

известна зависимость функции выигрыша (например, прибыли) от искомого плана;

известны зависимости всех ограничивающих факторов от искомого плана;

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

В качестве примера рассмотрим такую задачу.

Пример

На лесозаготовительном комбинате работает 70 человек. Основными переменными расходами являются суммарные расходы на каждого работника (заработная плата, налоги, страховки, затраты на спецодежду и т.п.). Эти расходы равны 80 тыс. руб. в месяц. Каждый работник за месяц обеспечивает производство 25 м3 древесины. Доход от продаж древесины составляет примерно 16,5 – 17 миллионов рублей в месяц.

На предприятие приходит новый директор, который ставит вопрос о возможности оптимизации работы. Изучив ситуацию, он устанавливает следую-

лагаемой на продажу в месяц.

Имеются дополнительные рабочие, желающие работать на нашем предприятии на тех же условиях, что и имеющиеся сотрудники. Но необходимо организовывать доставку новых сотрудников к месту работ. Затраты на доставку новых рабочих составят 20 тыс. руб. в месяц на человека.

Уволить более 30 человек нельзя.

Администрация региона согласна безвозмездно субсидировать предприятие в размере 300 тыс. руб. в месяц, если на нем будет создано не менее 150 рабочих мест.

54

Таким образом, перед директором встают такие вопросы:

Оптимально ли имеющееся количество рабочих?

Нужно ли нанять новых рабочих, а возможно стоит уволить кого-то из имеющихся?

Имеет ли смысл нанимать большее количество рабочих для получения субсидии?

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

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

1)доход нелинейно зависит от производства;

2)расходы на рабочих меняют коэффициент пропорциональности после 70 человек;

3)имеется разрыв функций – при найме от 150 человек предприятие получает субсидию.

55

Основы теории решения задач нелинейной оптимизации

1. Понятия глобального, локального и условного экстремумов

1)точка x удовлетворяет условиям (1);

2)для любой другой точки (любой или из малой окрестности точки x ), удовлетворяющей системе (1) справедливо условие:

1.4. Глобальный, локальный и условный минимумы записываются аналогично, только знак меняется на .

Заметим, что целью решения задач оптимизации является именно набор переменных x x1 , x2 , , xn , а не максимальное или минимальное значение

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

56

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

2. Понятие градиента

Градиент – вектор (набор) частных производных от функции по ее аргументам:

Градиент как вектор, вычисленный в точке, показывает направление наискорейшего роста функции в этой точке.

Градиент равен нулю когда все его компоненты равны нулю.

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

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

Если дифференцируемая функция F x1, x2 , , xn имеет локальный экс-

тремум во внутренней (не бесконечной) точке x* , то ее градиент в этой точке равен нулю.

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

Пример.

F x, y 3xy x2 2 y3 .

grad F F ; F 3y 2x; 3x 6 y2 .x y

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

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

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

57

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

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

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

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

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

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

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

Недостатки:

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

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

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

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

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

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

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

58

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

60