Информационные системы менеджмента - Бажин И.И

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

3.Выручка от реализации продукции. Спрос на продукцию компании мо­ жет существенно зависеть от цен реализации: чем ниже цена продукта, тем больше объем реализации, несмотря на аналогичное снижение цен, производи­ мое конкурентами. Следовательно, выручка от реализации продукции не изме­ няется пропорционально цене, и это обстоятельство должно отражаться в целе­ вой функции модели с помощью нелинейного слагаемого. Для иллюстрации примем, что х(р) есть объем реализации, зависящий от цены р. Тогда выручка от реализации выражается зависимостью рх(р). Пусть на представляющем для нас интерес интервале изменения р установлено, что функция объема реализа­ ции от цены линейна, то есть имеет вид х(р) = ар + Ь. Тогда слагаемые в целе­

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

4.Уровень страховых запасов. В большинстве математических моделей, используемых для общефирменного планирования, длительность отрезков пла­ нового периода редко составляет менее трех месяцев и часто превышает год и более. В таких "многопериодных" моделях (часто называемых динамическими) обычно предусматривается условие наличия страховых запасов, которые долж­ ны выполнять роль компенсатора колебаний еженедельного объема реализа­ ции. В этих моделях применяется, в частности, следующий подход: уровень страхового запаса предполагается зависимым как от прогнозируемого объема реализации, так и от степени использования производственных мощностей, обу­ словленной этим прогнозом. Так, например, пусть с - максимально возможный недельный объем производства рассматриваемого продукта, s - прогнозируе­ мый средненедельный объем реализации этого продукта и ns - уровень страхо­ вого запаса продукта, где п - число недель, зависящее от коэффициента ис­ пользования производственных мощностей s/c. Для примера предположим, что администрация приняла следующую зависимость для определения количества недель n: n = m + k(s/c). Тогда уровень страхового запаса представляет собой

квадратичную функцию прогнозируемого средненедельного уровня реализации, имеющую следующий вид: [ms + (k/c)s2]. Этот уровень может входить как в ряд ограничений, так и в целевую функцию.

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

современных программных средствах эффективных алгоритмов нелинейной оп­ тимизации (например, методов Ньютона и сопряженных градиентов - в Micro­ soft Excel). Поэтому нет необходимости жертвовать точностью и реалистично­ стью модели ради ее линеаризации, а следует стараться поточнее отразить процессы в моделируемом объекте, не обходя никакие нелинейности.

Преобразование нелинейной модели в задачу

целочисленного линейного программирования

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

Рассмотрим задачу планирования производства п видов продукции при ус­ ловии, что производство k-того вида продукции связано с постоянными затрата­ ми в размере Mk. Величина Мк постоянных затрат не зависит от объема произ­ водства этого вида продукции. Кроме постоянных затрат, имеются переменные затраты на производство, пропорциональные объему выпуска продукции. При этом стоимость производства единицы продукции k-того вида равна ск, так что, если k-тый вид продукции производится в объеме хк, то переменные затраты равны ckxk. Допустим, что имеется m видов ресурсов, и при производстве еди­ ницы продукции вида к расходуется aik единиц ресурса i-того вида. Кроме того, известно, что имеется возможность реализации не более dk единиц продукции k-того вида по цене рк рублей. Запас ресурсов i-того вида ограничен величиной b| (i = 1, 2, . . ., m). Требуется определить оптимальные пропорции производства (объемы выпуска каждого вида продукции) с целью получения максимальной прибыли.

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

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

Нелинейность вида (3.34) делает нелинейной целевую функцию. Однако этого можно избежать, используя булевы ( 0 - 1 ) переменные, что трансформи­ рует исходную задачу в модель целочисленного линейного программирования.

Пусть булева переменная 5к соответствует принятию решения о производ­ стве к-того вида продукции. Другими словами,

[1, если производится к - тын вид продукции [О, если не производится к - тын вид продукта!

Таким образом, значение булевой переменной связано со значением хк, то есть §к = 1, если хк > 0 и 5ц = 0 при хк = 0. Тогда целевая функция примет вид

Заметим, что значение хк может быть положительным только при 8к = 1; в этом случае производство к-того вида продукции ограничено величиной спроса dk. Если же k-тый вид продукции не производится, то 8к = 0, и спрос на этот про­ дукт автоматически не учитывается в ограничениях. В целевую функцию модели включаются постоянные затраты, которые так же "обнуляются", если соответст­ вующий вид продукции не производится.

Полученная модель (3.35) - (3.38) представляет собой так называемую

смешанную задачу целочисленного программирования, где управляющие переменные хк могут принимать любые неотрицательные значения, а дополни­ тельные булевы переменные 8к -только целочисленные значения 0 или 1. Дос­ тоинство полученной модели в том, что исходная нелинейность задачи в виде условного перехода (3.34) здесь исключается и трансформируется в дополни­ тельные целочисленные переменные. Такая трансформация упрощает решение задачи в среде информационных технологий, в частности, дает возможность при проведении расчетов в Microsoft Excel не использовать в оптимизационной за-

даче логические функции, а лишь ввести целочисленные (0 или 1) дополнитель­ ные переменные задачи.

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

в нелинейную модель

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

Вприведенной матрице элементы cik выражают прибыль (руб.), образую­ щуюся на каждый вложенный рубль, финансирующий i-тый вид рекламы для рекламирования товара k-той группы.

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

вложений средств в рекламу xik, где индекс i (i = 1, 2, . . ., m) соответствует виду рекламы, а индекс к (к = 1, 2, . . ., п) отвечает определенной группе товара. Итак, число переменных в задаче mxn, а сумма всех переменных, то есть сумма вложений в рекламу, не может превышать установленной величины V.

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

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

Матрица эффективности рекламы (долл.прибыли/долл.затрат)

Математическая модель задачи в соответствии с (3.30) - (3.40) имеет вид

45

'SZc u<x ik^m a x

Здесь cik - элементы представленной числовой матрицы эффективности, а Xjk - искомые объемы денежных вложений (в долларах) в каждый вид рекламы по каждой группе товара.

Результаты решения этой задачи с использованием Microsoft Excel пред­ ставлены ниже в матрице оптимальных значений искомых параметров.,

Оптимальные объемы затрат на рекламу (долл.)

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

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

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

показывает, что прибыль Pik линейно возрастает до величины вложений

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

где х"

Тогда максимизируемая целевая функция с учетом нелинейности (3.42) мо­ жет быть записана в виде суммарной прибыли, содержащей в качестве компо­ нентов нелинейности вида (3.42)

асистема ограничений, как и ранее, имеет вид (3.40)

шп

i=l k = l

xi k >0 (i = 1,2,..., m; k = 1,2,..., n)

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

Матрица предельных значений прибыли

3.9.МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

Типичными областями применения моделей динамического программиро­ вания при принятии решений являются:

•Разработка правил управления запасами, устанавливающих момент пополнения запасов и размер пополняющего заказа.

•Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на про­ дукцию.

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

•Распределение дефицитных капитальных вложений между возмож­ ными новыми направлениями их использования.

•Выбор методов проведения рекламной кампании, знакомящей поку­ пателя с продукцией фирмы.

•Систематизация методов поиска ценного вида ресурсов.

•Составление календарных планов текущего и капитального ремонта сложного оборудования.

•Разработка долгосрочных правил замены выбывающих из эксплуата­ ции основных фондов.

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

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

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

3.9.1.ОБЩИЕ ПРИНЦИПЫ ДИНАМИЧЕСКОГО

ПРОГРАММИРОВАНИЯ

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

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