Задачи оптимизации

Рис. 20. Табличная модель задачи о назначениях примера 3.8

Модель оптимизации рекламной кампании

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

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

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

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

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

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

Пример 3.9

32

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

Рекламное агентство располагает информацией о снижении степени воздействии рекламы при ее многократном повторении. В частности, в агентстве считают, что на дневном радио эффективность первых 10 рекламных объявлений можно оценить 60 баллами, а всех последующих – 40 баллами. Таблица эффективности рекламных объявлений в различных СМИ приведена ниже.

Фирма-производитель стирального порошка сформулировала и некоторые дополнительные условия: а) в каждом СМИ должно быть размещено не более 25 объявлений; б) общими усилиями всех СМИ объем продаж должен возрасти на 1 800 000 единиц товара; в) не мене четверти всех рекламных объявлений должно быть сделано на вечернем ТВ.

Решение

Сформулированная задача является типичной задачей линейного программирования. Для ее решения введем шесть переменных xi , yi , i 1, 2, 3 . Пере-

менные xi описывают число рекламных объявлений на радио ( i 1), телевидении ( i 2 ) и в газете ( i 3), если их число не превышает 10, величины yi – чис-

ло рекламных объявлений на радио ( i 1), телевидении ( i 2 ) и в газете (i 3), если их число превышает 10.

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

60 x1 40 y1 80 x2 55 y2 70 x3 35 y3 max .

Ограничения на количество объявлений запишутся в виде x1 y1 25; x2 y2 25; x3 y3 25 ,

поскольку в каждом из СМИ не может появиться более 25 объявлений.

33

Объем средств, затраченных на рекламную кампанию, подсчитать достаточно легко, поскольку известна стоимость одного объявления в различных СМИ. Выполняя подсчеты, получаем бюджетное ограничение

1700 (x1 y1) 2 800 (x2 y2 ) 1 200 (x3 y3) 72 000 .

Всоответствии с требованием заказчика число продаж в результате реклам-

ной компании должно возрасти на 1 800 000 единиц. Поэтому имеем еще одно ограничение:

30 000 (x1 y1) 60 000 (x2 y2 ) 45 000 (x3 y3) 1 800 000.

Требование размещения не менее четверти рекламных объявлений на вечернем ТВ, приводит нас к ограничению

x2 y2 0,25 (x1 y1 x2 y2 x3 y3 ) .

Количество рекламных объявлений должно быть целым числом. Поэтому при введении данных в программу Поиск решения нужно добавить еще и это ограничение.

Следует помнить, что если переменные задачи являются целыми величина-

ми, то программа Поиск решения Excel не генерирует отчет по устойчивости.

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

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

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

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

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

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

34

Пример 3.10

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

жайшие четыре месяца ( i 1, 2, , 4 ). Пусть затраты на производство одной тонны полиуретана составляют Ci тыс. рублей, а максимальный объем производства полиуретана по месяцам ограничен и равен Ki тонн в месяц. Производ-

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

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

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

Решение

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

Составим уравнение материального баланса, позволяющего вычислить количество продукции, хранящееся на складе в течение i го месяца. Пусть xi – количе-

ство полиуретана, произведенного в i й временной период. Тогда в течение первого месяца товарный запас на складе будет равен I1 I0 x1 d1 . Товарный запас

второго месяца

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

i 1

После того как мы вывели уравнение (3.24), описывающее поведение товарных запасов, легко записать математическую модель задачи:

Поставленная задача (3.25) является типичной задачей линейного программирования и может быть достаточно легко решена с помощью программы По-

иск решения.

35

Используя численные значения удельных затрат производства

и необходимого объема поставок и производственных мощностей по месяцам,

требуется составить оптимальный план производства полиуретана, если на первое января запас полиуретана на складе составлял 15 тонн.

Табличная модель задачи после нахождения оптимального решения приведена на рис. 21.

Рис. 21. Табличная модель задачи динамического программирования

Следует сказать несколько слов и об отчете по устойчивости для этой модели, приведенном на рис. 22. Если используется простое ограничение на значение оптимизируемых переменных ( xi Ki в нашем случае), то в отчете по устойчи-

вости теневые цены для этих ограничений помещаются в столбце нормированная стоимость, а информация о допустимом диапазоне теневых цен для этих ограничений не выводится. Таким образом, если увеличить на одну тонну производственные мощности в январе, то общие затраты уменьшатся на 1,7 тыс. рублей. Требует дополнительных пояснений и столбец Целевой коэффициент отчета по устойчивости. Приведенные здесь значения Excel вычисляет самостоятельно. Смысл целевого коэффициента при переменной состоит в том, что он показывает, насколько увеличится значение целевой функции при увеличении оптимального значения переменной на единицу. В этом легко убедиться на практике. Оптимальное значение производства полиуретана в январе – 60 тонн, а суммарные затраты равны 4 776,45 тыс. рублей. Если в качестве оптимального значения за январь подставить число 61 и пересчитать суммарные затраты, то получим новое

36

значение – 4 805,50. Разность этих чисел как раз и равна 29,05 – целевому коэффициенту при переменной объема производства в январе.

Рис. 22. Отчет по устойчивости для динамической модели

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

Нелинейные оптимизационные модели

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

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

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

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

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

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

37

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

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

Более того, модели нелинейного программирования можно разбить на два класса: класс моделей, которые поддаются оптимизации, и класс моделей, которые можно пытаться оптимизировать.

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

Напомним, что выпуклым называется множество, для которого точки отрезка, соединяющего любую пару точек множества, принадлежит этому множеству.

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

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

Для случая, когда все ограничения задачи нелинейного программирования имеют форму неравенств, справедливо следующее утверждение: множество до-

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

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

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

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

Пример 3.11

Завод производит две марки телевизоров – «Фотон» и «Рубин». Сборочный конвейер позволяет собирать 70 телевизоров марки «Фотон» и 50 телевизоров марки «Рубин». Цех А производит телевизионные трубки, причем на производство одной трубки для телевизора «Рубин» затрачивается 2 ч работы оборудования. Для производства одной трубки телевизора «Фотон» затраты времени зависят от объема производства и определяются формулой 1 0,1 x2 (ч.), где x2

38

– объем выпуска телевизоров марки «Фотон». Суточная норма работы оборудования в этом цехе не может превышать 120 ч. Цех Б выпускает корпуса телевизоров, причем для изготовления одного корпуса для телевизоров обеих марок затрачивается 1 ч работы оборудования. Суточная продолжительность работы оборудования в этом цехе не может превышать 90 ч. Цена оптовой продажи P (долл. США) телевизоров обеих марок зависит от спроса и определяется формулами PФ 314 1,9 x1 , PР 243 0,14 x2 , где x1, x2 – суточные объемы вы-

пуска телевизоров. Удельные затраты на производство телевизоров «Фотон» и «Рубин» составляют 210 и 230 долларов соответственно.

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

Решение

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

(314 1,9 x1 210) x1 (243 0,14 x2 230) x2 max . (3.26)

Запись ограничений также не представляет особого труда: x1 70, ограничение на выпуск телевизоров Фотон;

x2 50, ограничение на выпуск телевизоров Рубин;

(1 0,1 x1) x1 2 x2 120, ограничение на рабочее время в цехе А;

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

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

Табличная модель решения задачи приведена на рис. 23.

39