Нелинейные модели управления

Имеется много данных об успешном использовании моделей линейного программирования в различных задачах управления. Однако анализ моделей линейного программирования может вызвать сомнения в адекватности строго линейных моделей многим реальным ситуациям. Легко может создаться впечатление, что при линейном подходе игнорируются такие явления, как: эффективность или неэффективность укрупнения операций в многопродуктовых моделях, отсутствие аддитивности объемных показателей при составлении химических смесей; влияние объема реализации на цену реализации, а, следовательно, на выручку от реализации, то есть имеется множество задач, в которых предположение о линейности целевой функции и ограничений оказывается некорректным. В ряде ситуаций удается достаточно эффективно линеаризовать нелинейные компоненты модели. Однако построить хорошее линейное приближение практически невозможно, если существует широкий диапазон допустимых решений, и мы не имеем представления о характере оптимального решения.

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

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

К задачам нелинейного программирования обычно относят задачи следующего типа

f(x₁, x₂, . . ., x_n) ® max (3.32)

при ограничениях:

h_k(x₁, x₂, . . . , x_n) = 0 (k = 1, 2, . . . K) – ограничения-равенства, (3..33)

g_i(x₁, x₂, . . . , x_n­) £ 0 (i = 1, 2, . . . m) – ограничения-неравенства.

Здесь функции f(x₁, x₂, . . ., x_n), h_k(x₁, x₂, . . . , x_n), g_i(x₁, x₂, . . . , x_n­) (или хотя бы какая-нибудь одна из них) представляют собой действительные нелинейные функции n действительных переменных.

Естественно, может решаться как задача максимизации целевой функции, так и минимизации, ограничения могут быть как в форме неравенств, содержащих знак "£", так и знак "³" (тем более что математически это легко достигается умножением обеих частей неравенства на –1).

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

1) эмпирически полученные соотношения, такие, как непропорциональные изменения затрат, выхода продукции, показателей качества;

2) структурно полученные соотношения, к которым относятся постулируемые физические явления, а также выведенные математически или установленные руководством правила поведения.

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

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

Нелинейность включается в модели управления и в других случаях, например, в следующих:

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

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

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

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

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

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

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

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

Рассмотрим задачу планирования производства n видов продукции при условии, что производство k-того вида продукции связано с постоянными затратами в размере M_k. Величина M_k постоянных затрат не зависит от объема производства этого вида продукции. Кроме постоянных затрат, имеются переменные затраты на производство, пропорциональные объему выпуска продукции. При этом стоимость производства единицы продукции k-того вида равна c_k, так что, если k-тый вид продукции производится в объеме x_k, то переменные затраты равны c_kx_k. Допустим, что имеется m видов ресурсов, и при производстве единицы продукции вида k расходуется a_ik единиц ресурса i-того вида. Кроме того, известно, что имеется возможность реализации не более d_k единиц продукции k-того вида по цене p_k рублей. Запас ресурсов i-того вида ограничен величиной b_i (i = 1, 2, . . ., m). Требуется определить оптимальные пропорции производства (объемы выпуска каждого вида продукции) с целью получения максимальной прибыли.

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

(3.34)

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

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

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

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

Z = – ® max (3.35)

Ограничения по i-тому виду ресурсов можно записать следующим образом

(i = 1, 2, . . .m) (3.36)

Ограничения, связанные с размером спроса, имеют вид

x_k £ d_kd_k, k = 1, 2, . . ., n (3.37)

Ограничения на переменные задачи

x_k ³ 0, d_k = 0 или d_k = 1 для всех k (3.38)

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

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

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

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

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

Группа товара Вид рекламы	Мебель	Компью-теры	Парфю-мерия	Ткани	. . .	Автомо-били
Газета	c11	c12	c13	c14	. . .	c1n
Радио	c21	c22	c23	c24	. . .	c2n
Телевидение	c31	c32	c33	c34	. . .	c3n
. . .	. . .	. . .	. . .	. . .	. . .	. . .
Щитовая реклама	cm1	cm2	cm3	cm4	. . .	cmn

Матрица эффективности рекламы

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

В качестве управляющих переменных задачи выбираем искомые объемы вложений средств в рекламу x_ik, где индекс i (i = 1, 2, . . ., m) соответствует виду рекламы, а индекс k (k = 1, 2, . . ., n) отвечает определенной группе товара. Итак, число переменных в задаче m´n, а сумма всех переменных, то есть сумма вложений в рекламу, не может превышать установленной величины V.

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

Математическая модель такой задачи имеет вид

® max (3.39)

при ограничениях

£ V (3.40)

x_ik ³ 0 (i = 1, 2, . . ., m; k = 1, 2, . . ., n)

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

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

Группа товара Вид рекламы	Мебель	Компью-теры	Парфю-мерия	Ткани	Автомо-били
Газета
Радио
Телевидение
Щитовая реклама

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

® max

£ 2000 (3.41)

x_ik ³ 0 (i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5)

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

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

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

Группа товара Вид рекламы	Мебель	Компью-теры	Парфю-мерия	Ткани	Автомо-били
Газета	0,0	0,0	0,0	0,0	0,0
Радио	0,0	0,0	0,0	0,0	0,0
Телевидение	0,0	0,0	0,0	0,0	2000,0
Щитовая реклама	0,0	0,0	0,0	0,0	0,0

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

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

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

Будем считать, что такие зависимости по каждому виду рекламы для каждой группы товара получены. Представим, что в результате исследования зависимости прибыли P_ik, получаемой при реализации k-того товара, рекламируемого i-тым видом рекламы, от величины объемов вложений x_ik в соответствующую рекламу, получен график, изображенный на рис.3.9. График показывает, что прибыль P_ik линейно возрастает до величины вложений

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

(3.42)

где .

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

F(x_ik) = ® max, (3.43)

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

£ V

x_ik ³ 0 (i = 1, 2, . . ., m; k = 1, 2, . . ., n)

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