Матрица предельных значений прибыли
 |
| Группа товара Вид рекламы | Мебель | Компью-теры | Парфю-мерия | Ткани | Автомо-били |
| Газета | |||||
| Радио | |||||
| Телевидение | |||||
| Щитовая реклама |
Решение задачи выполнено в Microsoft Excel, нелинейность целевой функции описана с использованием логических функций. Результаты представлены матрицей оптимальных параметров
Оптимальные объемы затрат на рекламу (долл.)
| Группа товара Вид рекламы | Мебель | Компью-теры | Парфю-мерия | Ткани | Автомо-били |
| Газета | 113,5 | 106,2 | 103,6 | 0,0 | 290,6 |
| Радио | 66,7 | 200,0 | 96,8 | 0,0 | 155,2 |
| Телевидение | 0,0 | 136,6 | 84,6 | 0,0 | 119,1 |
| Щитовая реклама | 2,2 | 100,0 | 200,0 | 103,2 | 121,6 |
Как видим, в нелинейной постановке задача оптимизации имеет нетривиальное решение, которое показывает, сколько средств и по какому направлению рекламирования необходимо выделить, а по каким направлениям финансирование рекламы нецелесообразно. Легко убедиться, что суммарные затраты на рекламу не превышают выделенных руководством 2000 долларов. Величина прибыли при полученных оптимальных объемах финансирования рекламы составляет 67,2 тыс.долларов.
|
Если в результате упомянутых маркетинговых исследований установлено, что эффективность финансирования рекламы описывается иной зависимостью (например, в виде кривой, представленной на рис.3.10), то постановка нелинейной задачи при этом не изменится, другим станет лишь вид аналитической зависимости целевой функции. Для случая, когда кривая, представленная на рис.3.10, может быть аппроксимирована зависимостью
,
целевая функция нелинейной модели оптимизации объемов затрат на рекламу запишется в виде
® max, (3.44)
а ограничения, как и ранее, имеют вид (3.40).
МОДЕЛИ ДИНАМИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
Важным свойством оптимальных решений, получаемых на основе описанных в предыдущих разделах математических моделей, является их устойчивость во времени. Ясно, что во многих задачах основные параметры и ограничения, такие, как сырьевые и людские ресурсы, доход с единицы продукции, меняются во времени, что определяет динамический характер таких задач. Действительно, увеличение длительности планового периода может существенно повлиять на правильность текущего выбора. Это наглядно было видно в рассмотренной задаче распределения средств на рекламу.
Следует отметить, что динамическая задача не сводится полностью к задаче оптимизации для последовательных периодов времени, рассматриваемых изолированно друг от друга. Так, например, если, решая задачу рационального выбора ингредиентов для комбикорма, фермер допускает некоторое ослабление требований к составу пищевой смеси в течение одного периода, рассчитывая на компенсацию в последующие периоды, когда будут более благоприятны цены на компоненты корма, то возникает типичная задача динамического программирования. При этом очевидно, что в такой оптимизационной задаче не удастся представить модель как простую совокупность невзаимосвязанных задач оптимизации для каждого периода времени.
Общим для всех моделей этой категории является то, что текущие управляющие решения "проявляются" как в период, относящийся непосредственно к моменту принятия решения, так и в последующие периоды. Следовательно, наиболее важные экономические последствия проявляются в разные периоды, а не только в течение одного периода. Такого рода экономические последствия, как правило, оказываются существенными в тех случаях, когда речь идет об управляющих решениях, связанных с возможностью новых капиталовложений, увеличения производственных мощностей или обучения персонала с целью создания предпосылок для увеличения прибыльности или сокращения издержек в последующие периоды.
Типичными областями применения моделей динамического программирования при принятии решений являются:
n Разработка правил управления запасами, устанавливающих момент пополнения запасов и размер пополняющего заказа.
n Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию.
n Определение необходимого объема запасных частей, гарантирующего эффективное использование дорогостоящего оборудования.
n Распределение дефицитных капитальных вложений между возможными новыми направлениями их использования.
n Выбор методов проведения рекламной кампании, знакомящей покупателя с продукцией фирмы.
n Систематизация методов поиска ценного вида ресурсов.
n Составление календарных планов текущего и капитального ремонта сложного оборудования.
n Разработка долгосрочных правил замены выбывающих из эксплуатации основных фондов.
Процессы принятия решений, которые выражаются упомянутыми выше моделями, отражают динамику изменяющихся экономических условий и, с этой точки зрения, могут быть отнесены к числу микроэкономических. Эти модели весьма важны, поскольку во многих реально функционирующих системах еженедельно требуется принимать тысячи подобных решений. Вместе с тем, отражая реальную динамику функционирования системы, они позволяют тем самым осуществить более реалистичное долгосрочное планирование.
Небольшое наставление. Общей особенностью всех моделей динамического программирования является то, что здесь задача принятия решений сводится к получению рекуррентных соотношений. Если читатель никогда не пользовался подобными формализованными методами для решения задач, то связанная с этим система математических обозначений может в начальной стадии вызвать некоторые затруднения, преодолеть которые помогут приводимые ниже советы.
Текст рекомендуется прочесть не менее двух раз. При первом чтении следует постараться понять смысл поставленной задачи и хорошо ознакомиться с условными обозначениями. При втором чтении больше внимания целесообразно уделять деталям постановки, в том числе и характеру математических выражений. Необходимо внимательно ознакомиться с численными примерами и проверить правильность расчетов во всех тех случаях, когда это рекомендуется в тексте. Наконец, необходимо проявить терпение и не жалеть времени на изучение материала. Быстро усвоить методы динамического программирования удается далеко не всем. Однако, если следовать приведенным советам, то после рассмотрения нескольких примеров в какой-то момент наступает "озарение", и в дальнейшем читатель уже не испытывает трудностей в понимании смысла и формализации задач динамического программирования.
2.9.1. ОБЩИЕ ПРИНЦИПЫ ДИНАМИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
Из изложенного ранее становится ясно, что все задачи математического программирования в зависимости от вида целевой функции и ограничений могут быть разделены на ряд классов, каждый из которых характеризуется своими методами решения. К примеру, линейное программирование изучает класс задач, в которых и целевые функции, и ограничения линейны.
В силу сложности реальных задач оптимизации и отсутствия эффективного инструмента решения их в общем виде, на определенном этапе развития исследования операций велись поиски простых и доступных для "ручной" технологии методов решения таких задач. Решение многих задач математического программирования может быть упрощено, если развернуть процесс планирования (решения) поэтапно, то есть использовать метод динамического программирования. Идея метода в том, что отыскание точек оптимального решения целевой функции многих переменных заменяют многократным поиском точек экстремума одной переменной или небольшого числа переменных.
Динамическое программирование есть поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируют только один шаг. Причем управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. Динамическое программирование – это планирование с учетом перспективы, с учетом интересов всей задачи.
Несмотря на то, что основные идеи динамического программирования направлены на приведение сложной задачи к набору простых, что при наличии современных средств информационных технологий может представиться неэффективным, изучение этих методов в настоящей книге – это не "дань истории", а важное методологическое исследование. Использование методов динамического программирования позволяет осмысленно структурировать реальную задачу долгосрочного планирования с учетом меняющихся во времени условий осуществления проекта.
В задачах, решаемых методом динамического программирования, значение целевой функции (оптимизируемого критерия) для всего процесса получают простым суммированием частных значений fi(x) того же критерия на отдельных шагах, то есть
f(x) = 
(3.45)
Если критерий (или функция) f(x) обладает этим свойством, то его называют аддитивным (аддитивной).
Во многих практических задачах критерий f(x) аддитивен. Если в первоначальной постановке задачи критерий неаддитивен, то постановку задачи надо изменить так, чтобы он стал аддитивным. К примеру, если рассматривается критерий f(x), представленный в виде произведения выигрышей, достигаемых на отдельных этапах f(x) = f1(x)×f2(x)×. . . ×fm(x) (такой критерий называют мультиплексным), то можно просто преобразовать его к аддитивному, прологарифмировав выражение для f(x)
lgf(x) = 
Обозначим V º lgf(x), Vi º lgfi(x). Получим новый критерий V = 
, обладающий свойством аддитивности и имеющий тот же оптимум, что и f(x).
Рассмотрим общую схему решения задач с аддитивным критерием. Процесс управления состоит из m шагов. На каждом i-том шаге управление xi переводит систему из состояния Si-1, достигнутого в результате (i-1)-го шага, в новое состояние Si, которое зависит от состояния Si-1 и выбранного управления xi:
Si = Si(Si-1, xi).
Здесь существенно, чтобы новое состояние Si зависело только от состояния Si-1 и управления xi и не зависело от того, каким образом система пришла в состояние Si-1. В крайнем случае, это достигается увеличением числа состояний системы (в понятие "состояние системы" вводят те параметры, от которых зависит будущий результат).
В теории динамического программирования, если рассматривают стратегии, зависящие только от текущего состояния, оптимальную стратегию характеризуют очень просто.
Принцип оптимальности
Оптимальная стратегия обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение, последующее решение должно определять оптимальную стратегию относительно состояния, полученного в результате предыдущего решения.
Рассмотрим задачу о максимизации целевой функции f(x) на m-шаговом процессе.
Под влиянием управлений x1, x2, . . . , xm система переходит из начального состояния So в конечное Sкон. За m шагов получают выигрыш (значение целевой функции)
f(x) = 
(3.46)
где fi(Si-1, xi) – выигрыш на i-том шаге.
Принцип оптимальности позволяет заключить, что при любом начальном управлении x1 имеет место соотношение
f(x) = f1(S0, x1) + [f2(S1, x2) + . . . + fm(Sm-1, xm)] =
= f1(S0, x1) + fm-1[Sm-1(S0, x1)] (3.47)
Поскольку соотношение (3.47) справедливо для всех начальных решений x1, то, чтобы найти максимальный выигрыш, надо найти максимум по x1 значения f(x). Это приводит к основному функциональному уравнению динамического программирования – к рекуррентной формуле динамического программирования (РДП)
fm(S0) = 
f(x) = [f1(S0, x1) + fm-1[Sm-1(S0, x1)]]; m ³ 1 (3.48)
Выражение (3.48) означает, что, зная f0(S), можно вычислить f1(S), зная f1(S), – f2(S) и т.д. Такая вычислительная процедура именуется рекуррентным алгоритмом, а выражение (3.48) – рекуррентной формулой или рекуррентным соотношением.
Согласно этому выражению, алгоритм получения решения в динамическом программировании можно определить как последовательность функций выигрыша или же как последовательность стратегий {xn(S0)}. Эти последовательности определяют друг друга – в этом и состоит смысл рекуррентных соотношений. Причем имеется только одна последовательность оптимальных значений целевой функции, хотя, в принципе, могут иметь место различные оптимальные стратегии, которые приводят к тому же максимальному выигрышу.
В динамическом программировании, планируя многоэтапную операцию, управление на каждом шаге выбирают с учетом будущего. И только на одном шаге – последнем – такой необходимости нет. Этот последний шаг можно спланировать так, чтобы он приносил наибольшую выгоду.
Планируя оптимальным образом последний шаг, к нему присоединяют предпоследний и находят согласно основной рекуррентной формуле наибольший выигрыш на этих двух шагах и т.д. Поэтому в динамическом программировании процесс разворачивается от конца к началу. А как спланировать последний шаг, если мы не знаем, каков результат предпоследнего? Для этого делают различные предположения о том, чем закончится предпоследний шаг, и для каждого предположения выбирают управление на последнем, которое запоминают до конца решения задачи. Такое оптимальное управление, выбранное при определенном условии о том, каков результат предыдущего шага, называют условным оптимальным управлением.
Алгоритм динамического программирования
1.На выбранном шаге задаем набор (определяемый условиями-ограниче-ниями) значений переменной, характеризующей последний шаг, возможные состояния системы на предпоследнем шаге. Для каждого возможного состояния и каждого значения выбранной переменной вычисляем значения целевой функции. Из них для каждого исхода предпоследнего шага выбираем оптимальные значения целевой функции и соответствующие им значения рассматриваемой переменной. Для каждого исхода предпоследнего шага запоминаем оптимальное значение переменной (или несколько значений, если таких значений больше одного) и соответствующее значение целевой функции. Получаем и фиксируем соответствующую таблицу.
2.Переходим к оптимизации на этапе, предшествующем предыдущему (движение "вспять"), отыскивая оптимальное значение новой переменной при фиксированных найденных ранее оптимальных значениях следующих переменных. Оптимальное значение целевой функции на последующих шагах (при оптимальных значениях последующих переменных) считываем из предыдущей таблицы. Если новая переменная характеризует первый шаг, то переходим к п.3. В противном случае повторяем п.2 для следующей переменной.
3.При данном в задаче исходном условии для каждого возможного значения первой переменной вычисляем значение целевой функции. Выбираем оптимальное значение целевой функции, соответствующее оптимальному(ым) значению(иям) первой переменной.
4.При известном оптимальном значении первой переменной определяем исходные данные для следующего (второго) шага и по последней таблице – оптимальное(ые) значение(ия) следующей (второй) переменной.
5.Если следующая переменная не характеризует последний шаг, то переходим к п.4. Иначе переходим к п.6.
6.Формируем (выписываем) оптимальное решение.
Изложенные принципы и рассмотренная процедура могут быть проиллюстрированы на конкретных примерах при решении последующих задач.
2.9.2. ЗАДАЧА ОБ ОПТИМАЛЬНОЙ ЗАГРУЗКЕ
ТРАНСПОРТНОГО СРЕДСТВА
Рассмотрим конкретную задачу целочисленного линейного программирования, которая успешно может быть решена методом динамического программирования. Изложение задачи с использованием определенных числовых данных не нарушает общности подхода, давая вместе с тем возможность на конкретном материале полнее ощутить особенности изложенного метода.
Представим, что в самолет требуется погрузить 4 вида предметов (предметы будем считать неделимыми), чтобы сумма эффективностей этих предметов (например, стоимость) была максимальной. Грузоподъемность самолета равна W. Пусть P1, P2, P3, P4 – масса соответствующей единицы различных предметов; V1, V2, V3, V4 – соответствующая эффективность каждого предмета; x1, x2, x3, x4 – число предметов различных видов, взятых на борт самолета (управляющие переменные).
Целевая функция математической модели задачи может быть записана в виде
= x1V1 + x2V2 + x3V3 + x4V4 ® max (3.49)
Ограничение по допустимой загрузке самолета имеет вид
= x1P1 + x2P2 + x3P3 + x4P4 £W (3.50)
Математическую модель вида (3.49) – (3.50) часто называют "задачей о рюкзаке" из-за следующей гипотетической ситуации. Турист, собираясь в поход, должен решить, какие предметы взять с собой. Каждый предмет имеет свою массу и свою ценность. Требуется, чтобы общая масса рюкзака с выбранными предметами не превышала некоторой заданной массы, а общая ценность выбранных предметов была максимальной.
Для определенности примем, что W = 83; P1 = 24, P2 = 22, P3 = 16, P4 = 10; V1 = 96, V2 = 85, V3 = 50, V4 = 20 условных единиц.
Применим для решения задачи многошаговый процесс принятия решения (динамическое программирование). Согласно общей схеме будем решать задачу в два этапа. На первом этапе найдем возможные оптимальные варианты планов (решений) при последовательной оптимизации по одной переменной, а на втором этапе выберем из этих "заготовок" оптимальное решение нашей задачи.
Первый этап. Он будет содержать 4 шага.
На шаге 1 находим возможные оптимальные варианты загрузки самолета только предметами первого вида. Нам необходимо найти и запомнить значения x1 и соответствующую им максимальную стоимость груза f1(W) при различных возможных значениях W. В этом случае максимальная эффективность груза составляет
f1(W) = (x1V1)
при условии x1P1 £ W, x1 = 0, 1, 2, 3, . . .. Так как x1 £W/P1, то для нахождения максимума f1(W) надо x1 взять возможно большим, то есть x1 = [W/P1] – наибольшее целое число, не превосходящее W/P1, и, таким образом,
f1(W) = [W/P1]×V1 (3.51)
Зададимся значениями W с некоторым шагом и найдем для них x1 и f1(W). Очевидно, если грузоподъемность самолета меньше 24 ед., то ни одного предмета первого вида погрузить нельзя. При грузоподъемности от 24 до 47 ед. можно погрузить 1 ед. предметов первого вида и т.д. Результаты представим в виде таблиц. Значения W, f1(W) и x1 приведены в таблице 3.9.1.
Таблица 3.9.1
| W | f1(W) | x1 | W | f1(W) | x1 | |
| 0. . . 23 | 48 . . . 71 | |||||
| 24 . . . 47 | 72 . . . 87 |
В таблице принят более широкий предел для W – до 87 ед.
Проведем оптимизацию на шаге 2. Рассмотрим эффективность загрузки, если самолет загружается предметами и первого, и второго типов.
Максимальную эффективность загрузки обозначим f2(W). Если погружено x2 предметов второго типа, то масса предметов первого типа должна быть не больше W – P2x2. Максимальная эффективность загрузки предметами первого типа при этом составляет
f1(W – x2P2) = 
(x1V1)
при условии x1 £ W – x2P2, x1 = 0, 1, 2, . . ., а общая эффективность загрузки
f12 = x2V2 + f1(W – x2P2)
Тогда
f2(W) = 
{x2V2 + f1(W – x2P2)};
(3.52)
0 £ x2 £ [W/P2]
Максимум этого выражения ищут только по x2. Но мы не знаем, какая грузоподъемность W может потребоваться для предметов второго типа. Поэтому необходимо рассмотреть выражение (3.52) для различных значений W от 0 до 83. При вычислении f1(W – x2P2) воспользуемся уже полученными результатами (табл.3.9.1).
Например, возьмем W = 46 ед. Для x2 возможны значения 0, 1, 2. Соответствующая эффективность от предметов второго типа равна 0, 85, 170, а для предметов первого вида остается грузоподъемность 46, 24, 2 ед. Из табл.3.9.1 для W = 46, 24, 2 ед. находим f1(W) = 96, 96, 0 ед. Складываем соответствующие значения 0+96 = 96 ед., 85+96 = 181 ед., 170+0 = 170 ед. и выбираем наибольшее – 181 ед. Оно получено при x2 = 1. Для W = 46 заносим в табл. 3.9.2 x2 = 1; f2(W) = 181. Результаты вычислений f2(W) и x2 приведены в табл. 3.9.2.
Таблица 3.9.2
| W | f2(W) | x2 | W | f2(W) | x2 | |
| 0 . . . 21 | 48 . . . 65 | |||||
| 22 . . . 23 | 66 . . . 67 | |||||
| 24 . . . 43 | 68 . . . 69 | |||||
| 44 . . . 45 | 70 . . . 71 | |||||
| 46 . . . 47 | 72 . . . 87 |
Из таблицы 3.9.2 следует, что при грузоподъемности транспортного средства до 21 ед. ничего в него погрузить нельзя, при грузоподъемности 22...23 ед. можно погрузить только один предмет второго типа, при грузоподъемности 24...43 ед. – либо один предмет первого типа, либо один предмет второго типа. Максимальная эффективность будет при загрузке предметами первого типа. При грузоподъемности 44...45 ед. можно погрузить либо один предмет первого типа, либо два предмета второго вида. Эффективность будет больше в последнем случае и f2(W) = 170. При грузоподъемности 46...47 ед. можно погрузить один предмет первого типа, до двух предметов второго вида, или же по одному предмету первого и второго видов. Эффективность загрузки в последнем варианте максимальна.
Приступим к оптимизации на шаге 3. Будем загружать транспортное средство предметами первых трех видов. Требуется максимизировать по x3
f123 = x3V3 + f2(W – x3P3); f3(W) = 
f123;
(3.53)
0 £ x3 £ [W/P3]
Задаемся значением W и для каждого такого значения получаем максимум f123 по x3. Значения f2(W) берем из таблицы 3.9.2. Например, пусть W = 38 ед. Возможное значение x3 = 0, 1, 2 ед., и соответствующая эффективность предметов третьего вида – 0, 50, 100 ед. На предметы первого и второго видов остается, соответственно, грузоподъемность 38, 22, 6 ед. По данным таблицы 3.9.2 находим f2(W) = 96, 85, 0 ед. Суммарная эффективность 96, 135, 100 ед. Максимальное значение эффективности при W = 38 ед. равно 135 ед. для x3 = 1. Результаты расчетов помещены в табл. 3.9.3.
| W | f3(W) | x3 | W | f3(W) | x3 | |
| 0 . . . 15 | 44. . . 45 | |||||
| 16 . . . 21 | 46 . . . 47 | |||||
| 22 . . . 23 | 48 . . . 63 | |||||
| 24 . . . 31 | 64 . . . 69 | |||||
| 32 . . . 37 | 70 . . . 71 | |||||
| 38 . . . 39 | 72 . . . 87 | |||||
| 40. . . 43 |
Таблица 3.9.3
Проводим оптимизацию на последнем (четвертом) шаге. Получим оптимальную загрузку самолета W*.
Зададимся значением W, которое может быть занято грузом четырех видов, и вычислим x4, f4(W). Строго говоря, здесь нам достаточно было бы вычислить одну строку табл.3.9.4 для W = 83.
Второй этап. Нахождение оптимального решения поставленной задачи. Максимальное значение f4(W) – это и есть W*, а соответствующее значение аргумента x4 – количество груза четвертого вида, которое берет самолет (x4*):
W* = max f4(W) = 308; x4* = 1
Масса предметов четвертого вида будет x4*P4 = 10 ед. На остальные три вида груза остается W – 10 = 73 ед. При значении W = 73 ед. по табл.3.9.3 получаем x3* = 0; аналогично получаем x2* = 0; x1* = 3.
Таблица 3.9.4
| W | f4(W) | x4 | W | f4(W) | x4 | |
| 0 . . . 9 | 46 . . . 47 | |||||
| 10 . . . 15 | 48 . . . 57 | |||||
| 16 . . . 21 | 58 . . . 63 | |||||
| 22 . . . 23 | 64 . . . 69 | |||||
| 24 . . . 33 | 70 . . . 71 | |||||
| 34 . . . 37 | 72 . . . 81 | |||||
| 38 . . . 39 | 82 . . . 87 | |||||
| 40. . . 45 |
Если еще раз вернуться к табл. 3.9.1 – 3.9.4, то увидим, что они содержат "заготовки" для оптимальной загрузки самолета любой грузоподъемности (до W= 87 ед.) указанными предметами. Таким образом, мы решили не только поставленную задачу, а большой набор родственных задач. С одной стороны, это хорошо, но, с другой стороны, в памяти компьютера необходимо хранить табл.3.9.1 – 3.9.4: столбцы f1(W) – f4(W) до выполнения следующего (n+1)-го шага, а столбцы x1, x2, x3, x4 и соответствующие им значения W – на протяжении всего процесса решения. Для сложных задач последнее обстоятельство имеет существенное значение и ограничивает возможности рассмотренного метода.
Подчеркнем, что полученное оптимальное решение x1* = 3, x2* = 0, x3* = 0, x4* = 1 и W* = 308 легко может быть получено как решение задачи целочисленного программирования в виде (3.49) – (3.50) с использованием программы Microsoft Excel.
2.9.3. ЗАДАЧА О ВКЛАДЕ СРЕДСТВ В ПРОИЗВОДСТВО
Методы динамического программирования лучше всего "подходят" к задачам с дискретными переменными, чем с непрерывными, так как невозможно запомнить все промежуточные значения при непрерывных переменных. Вместе с тем основное рекуррентное соотношение имеет один и тот же вид и для дискретных, и для непрерывных переменных, что принципиально позволяет применять динамическое программирование к задачам с непрерывными переменными. При этом иногда удается сократить объем расчетов применением дифференциального исчисления, но все же чаще задачу сводят к дискретным переменным.
Рассмотрим задачу с непрерывными переменными, связанную с планированием вклада средств в производство. Эта задача методически может быть отнесена к динамическому программированию, так как вложение средств планируется в определенные отрезки времени, чаще всего по годам.
Пусть планируется деятельность цехов (например, швейного и по ремонту обуви) сроком на 5 лет (m = 5). Функции вклада в производство средств j(x) = 0,75x, f(y) = 0,3y, то есть, если средства z вкладывать только в продукцию первого цеха, то по годам будет вкладываться средств 0,75z; 0,752z; 0,753z, . . . . Соответственно, если средства z вкладывать только в выпуск продукции второго цеха, то получим 0,3z; 0,32z; 0,33z, . . ..
Функции дохода как функции от объема вкладываемых средств x и y имеют вид
f(x) = 1 – e-x ;
g(y) = 1 – e-2y(3.54)
Требуется распределить имеющиеся ресурсы z = 2 между цехами по годам так, чтобы получить максимальный доход. То есть, необходимо определить по годам объемы вложений x в первый цех, и y – во второй цех.
При решении этой задачи можно применить метод динамического программирования, используя изложенный ранее алгоритм. Однако это приводит к необходимости вычислений значений целевой функции с определенным шагом. Для достижения высокой точности это шаг должен быть достаточно малым. Кроме того, для наглядности придется прибегнуть к графическим построениям решений.
Этих сложностей можно избежать, если прибегнуть к более общему подходу при решении, сформулировав эту задачу как общую задачу нелинейного математического программирования, используя из подхода динамического программирования лишь введение на каждом этапе своих переменных и "стыковок" решений на границах этапов.
Итак, примем в качестве управляющих переменных x1, x2, x3, x4, x5 – объемы средств, вкладываемых по годам в продукцию первого цеха, y1, y2, y3, y4, y5 –
объемы средств, вкладываемых по годам в продукцию второго цеха.
В соответствии с выражениями (3.54) целевую функцию, максимизирующую суммарный доход, запишем в виде
F(x, y) = 
® max (3.55)
Ограничения выражаются в распределении имеющихся ресурсов по годам в соответствии с приведенными выше функциями вклада средств в производство
zi = 0,75xi + 0,3(zi-1 – xi) при условии xi + yi = zi-1 (3.56)
для i = 1, 2, 3, 4, 5.
Именно условия (3.56) отражают динамический характер задачи, обеспечивая "стыковку" вложений ресурсов по годам.
Математическая модель (3.55) – (3.56) описывает задачу нелинейного программирования и успешно может быть решена с использованием табличного процессора интегрированной системы Microsoft Office. Результат такого решения представлен в виде таблицы Microsoft Excel (табл.3.9.5).
Таблица 3.9.5. Решение задачи о вкладе средств в производство
| Вложения в 1-й цех | Доход 1-го цеха | Вложения во 2-й цех | Доход 2-го цеха | |||||||
| X1 = | 1,619 | f1 = | 0,802 | Y1 = | 0,381 | g1 = | 0,533 | |||
| X2 = | 1,040 | f2 = | 0,646 | Y2 = | 0,289 | g2 = | 0,439 | |||
| X3 = | 0,627 | f3 = | 0,466 | Y3 = | 0,239 | g3 = | 0,381 | |||
| X4 = | 0,301 | f4 = | 0,260 | Y4 = | 0,241 | g4 = | 0,382 | |||
| X5 = | 0,000 | f5 = | 0,000 | Y5 = | 0,298 | g5 = | 0,449 | |||
| Суммарные ресурсы по годам | ||||||||||
| Z0 | Z1 | Z2 | Z3 | Z4 | Z5 | |||||
| 1,329 | 0,867 | 0,542 | 0,298 | 0,089 | ||||||
| Суммарный доход от двух цехов за 5 лет | 4,358 | |||||||||
В таблице приведены оптимальные значения управляющих переменных x1 – x5 и y1 – y5, значение целевой функции (суммарного дохода) в оптимальном решении, а также распределение по годам суммарных ресурсов (здесь z5 = 0,089 – остаток средств на конец планируемого периода – на конец 5-го года).
2.9.4. МОДЕЛЬ УПРАВЛЕНИЯ ЗАПАСАМИ
В настоящем разделе рассмотрена простейшая модель управления запасами, что позволяет сосредоточить внимание на небольшом числе важнейших особенностей динамических процессов управления запасами. Модель, к изучению которой мы приступаем, играет такую же – или почти такую же – роль в исследовании операций, как законы Ньютона в физике. Хотя рассматриваемая модель и является идеализированной, в ней все же учитывается множество важных факторов, влияющих на выбор правил управления запасами. Важно отметить, что внедрение модификаций рассматриваемой модели рядом фирм дало заметный экономический эффект. Само собой разумеется, что эффективная реализация таких моделей возможна лишь в среде информационных технологий.
Представим, что фирма "Партнер" должна разработать календарную программу выпуска некоторого вида изделий на плановый период, состоящий из N отрезков времени. Предполагается, что для каждого из этих отрезков имеется точный прогноз спроса на выпускаемую продукцию.
Время изготовления партии изделий будем считать пренебрежимо малым по сравнению с величиной соответствующего отрезка времени планового периода; соответственно продукция, изготавливаемая в течение отрезка t, может быть использована для полного или частичного покрытия спроса в течение этого отрезка времени. Для разных отрезков времени спрос неодинаков; кроме того, на экономические показатели производства влияют размеры изготавливаемых партий. Поэтому фирме нередко бывает выгодно изготавливать в течение некоторого отрезка времени (например, месяца) продукцию в объеме, превышающем спрос в пределах этого отрезка, и хранить излишки, используя их для удовлетворения последующего спроса. Вместе с тем, хранение возникающих при этом запасов связано с определенными затратами. В зависимости от обстоятельств эти затраты обусловлены такими факторами, как проценты на капитал, взятый взаймы для создания запасов, арендная плата за складские помещения, страховые взносы и расходы по содержанию запасов. Эти затраты необходимо учитывать при установлении программы выпуска.
Цель фирмы "Партнер" – разработать такую программу, при которой общая сумма затрат на производство и содержание запасов минимизируется при условии полного и своевременного удовлетворения спроса на продукцию.
Качественное описание изложенной задачи преобразуем в математическую модель.
Построение модели
Введем управляющие переменные:
xt – объем выпуска продукции в течение отрезка времени t;
it – уровень запасов на конец отрезка t.
Спрос на продукцию для отрезка t обозначим Dt; предполагается, что величины Dt для всех t отображаются неотрицательными целыми числами и что к началу планового периода все Dt известны.
Предположим также, что для каждого отрезка t затраты зависят от объема выпуска продукции xt, уровня запасов it на конец отрезка t и, кроме того, возможно от значения t. Обозначим затраты на отрезке t через Ct(xt, it). Тогда целевую функцию можно записать в следующем виде
® min (3.57)
На значения управляющих переменных xt и it наложено несколько ограничений. Во-первых, предполагается целочисленность объемов выпуска
xt = 0, 1, 2, 3, . . . (t = 1, 2, . . ., N) (3.58)
Во-вторых, предполагается, что для администрации фирмы желателен нулевой уровень запасов на конец отрезка N
iN = 0 (конечный запас равен нулю) (3.59)
Наконец, в-третьих, ставится условие полного и своевременного удовлетворения спроса в пределах каждого отрезка времени. Выполнение этого условия можно обеспечить, введя два ограничения. Первое из них назовем "балансо-вым", поскольку в нем утверждается, что
Уровень запасов на конец отрезка t = (Уровень запасов на начало отрезка t) +
+ (выпуск продукции на отрезке t) – (спрос на отрезке t).
Используя принятые условные обозначения, запишем это ограничение в виде
it = it-1 + xt – Dt (3.60)
или в более удобной форме
it-1 + xt – it =Dt (t = 1, 2, . . . , N) (3.61)
(заметим, что i0 – заданный уровень запасов на начало планового периода).
Согласно второму вводимому ограничению, обеспечивающему своевременное выполнение фирмой "Партнер" своих обязательств, уровень запасов на начало каждого отрезка и объемы выпуска продукции должны быть достаточными для того, чтобы уровень запасов на конец отрезка был бы неотрицателным. На самом же деле требуется не только неотрицательность, но и целочисленность уровней запасов (следует заметить, что, если предположить целочисленность объемов спроса и выпуска продукции, то предположение о целочисленности уровней запасов не создает дополнительных трудностей). Таким образом, требуется, чтобы
it = 0, 1, 2, 3, . . . (t = 1, 2, . . ., N) (3.62)
С другой стороны, как отмечалось ранее, требование целочисленности не является обязательным – в целом вид всех зависимостей сохраняется и при непрерывных переменных, существенно возрастает лишь объем вычислений при использовании метода динамического программирования.
Отметим, что ограничение (3.61) является линейным. Если бы все величины затрат Ct(xt, it) линейно зависели от значений переменных, то полученная модель была бы эквивалентна описанной ранее сетевой модели. Однако в большинстве практических случаев применения производственных моделей функция затрат нелинейна. Так, для выпуска партии изделий могут потребоваться дорогостоящие подготовительные операции (переналадка), из-за которых затраты на производство первой единицы партии изделий превышает дополнительные затраты на производство остальных единиц. В тех же случаях, когда объем производства в течение некоторого периода превышает нормальную мощность производственного участка, дополнительные затраты на единицу изделия могут возрастать из-за использования сверхурочных работ.
Решим указанную задачу, сформулировав ее в терминах динамического программирования. Пусть для определенности N = 4. Составим балансовые уравнения (3.61) для t = 1, 2, 3, 4. Матрица этой системы ограничений представлена на рис.3.11.
| x1 | i1 | x2 | i2 | x3 | i3 | x4 | ||||
| – 1 | = D1 – i0 | ||||||||
| – 1 | = D2 | |||||||||
| – 1 | = D3 | |||||||||
| = D4 |
Рис.3.11. Матрица ограничений задачи управления запасами
Построим пятое уравнение, просуммировав четыре уравнения, а затем составим систему из пяти уравнений, содержащую, наряду с пятым, четыре исходных уравнения, умноженных на – 1. Легко убедиться, что построенная система адекватна сети, изображенной на рис.3.12.
Вспомним, что в динамическом программировании вычислительный процесс строится от конечного состояния (сделаны все шаги многошагового процесса) к исходному. Применим такой же подход и к нашей задаче. Здесь конечным состоянием будет начало последнего отрезка планового периода, а исходным – начальный момент первого отрезка (впереди еще N отрезков).
При составлении математической модели удобно использовать систему индексов, при которой подстрочный индекс "1" соответствует конечному, а "N" – начальному состоянию. Примем следующие обозначения:
dn – спрос на продукцию на отрезке n, отстоящем от конца планового периода на n отрезков (включая рассматриваемый);
c(x, j) – затраты на отрезке n, связанные с выпуском x единиц продукции и с содержанием запасов, уровень которых к концу отрезка равен j единиц.
В этой системе обозначений d1 º Dn и dn º D1, а c1(x, j) º CN(x, j).
Пусть N = 4, а плановый период начинается с января. Тогда D1 есть январский спрос, D4 – апрельский. В модели же используется "обратная система индексов": январский спрос обозначен d4, апрельский – d1. Следовательно, d2 – мартовский спрос (до конца планового периода – два отрезка, включая март).
Что же определяет состояние системы в начале любого отрезка? Можно считать, что уровень запасов на начало отрезка. Для принятия текущего решения об объеме выпуска не нужно знать, каким образом достигнут начальный уровень. Учитывая это обстоятельство, введем следующие обозначения:
fn(i) – стоимость, отвечающая стратегии минимальных затрат на n оставшихся отрезков при начальном уровне запасов i;
xn(i) – выпуск (стратегия), обеспечивающий достижение fn(i).
Согласно условию (3.59), уровень запасов на конец планового периода равен нулю, поэтому можно записать
f0(0) = 0 (n = 0) (3.63)
Затем перейдем к n = 1. Начальный уровень запасов i может определяться любым неотрицательным целым числом, не большим, чем d1; вне зависимости от значения i для полного удовлетворения потребности в пределах последнего отрезка объем выпуска должен быть равен (d1 – i). Следовательно,
f1(i) = c1(d1 – i, 0), i = 0, 1, . . ., d1 (3.64)
Перейдем к n = 2. Заметим, что если начальный уровень запасов равен i, а объем выпуска – x, то общие затраты для двух месяцев составляют
c2(x, i+x–d2) + f1(i+x–d2),
причем предполагается, что выбранная стратегия для n = 1 была оптимальной. Заметим, что величина (i+x–d2) есть попросту уровень запасов на конец планового отрезка 2. Величина i может принимать любые неотрицательные целочисленные значения, не превышающие (d1 + d2) (вопрос к читателю: объясните, почему?). При заданном i целочисленное значение x должно быть не меньше, чем (d2 – i), что обеспечивает полное удовлетворение потребности на отрезке 2, но не больше, чем (d1 + d2 – i), так как конечный запас равен нулю. Оптимальному объему выпуска соответствует такое значение x, при котором минимизируется указанная выше сумма. Выполненный нами анализ ситуации для n = 2 можно выразить следующим общим выражением:
f2(i) = 
[c2(x, i +x–d2) + f1(i +x–d2)],
где i = 0, 1, 2, . . . , d1+d2, причем для отыскания минимума перебираются все неотрицательные целые значения x, заключенные в пределах d2 –i £ x £ d1+d2–i.
Как мы уже знаем, значения f3(i) можно вычислить, если известны значения f2(i), и т.д. В конце концов, в данной задаче можно вычислить fn(i0), где i0 – уровень запасов на начало планового периода. Общее рекуррентное соотношение динамического программирования для задачи управления запасами записывается в виде
fn(i) = [cn(x, i+x–dn) + fn-1(i+x–dn)], n = 1, 2, . . ., N, (3.65)
где i = 0, 1, . . ., d1 + . . . + dn, причем для отыскания минимума перебираются все неотрицательные целые значения x, заключенные в пределах
dn – i £ x £ d1 + d2 + . . . + dn – i.
Заметим, что, поскольку начальный уровень запасов i рассматривается как переменная величина, полностью характеризующая состояние системы, единственной независимой управляющей переменной в рекуррентном соотношении (3.65) является x, так как уровень запасов на конец отрезка равен (i+x–dn). Заметим также, что, поскольку f0(0) и f1(i) без труда вычисляются по формулам (3.63) и (3.64), можно непосредственно и поочередно вычислить значения f2(0), f2(1), . . . , f2(d1), а затем f3(0), f3(1), . . ., f3(d1+d2). Последовательно переходя к все большим значениям n, мы дойдем до вычисления fN-1(0), fN-1(1), . . . ,
fN-1(d1+d2+. . .+dN-1) и, наконец, до fN(i0).
Для отыскания оптимальной производственной программы определим, какой объем выпуска xN(i0) позволяет достичь полученного значения fN(i0). Соответствующее решение о выпуске является оптимальным решением для начального отрезка планового периода. Уровень запасов на начало следующего отрезка равен i0+xN(i0) –dN. Найдем объем выпуска, позволяющий достичь полученного нами значения fN-1[i0+xN(i0) – dN] и т.д.
Итак, процесс принятия решений рассматривается как многошаговый; n – число шагов (в данной задаче – число отрезков времени планового периода) до конца процесса. В иллюстративных целях снова примем N = 4, причем эти отрезки соответствуют январю, февралю, марту и апрелю; n = 1 относится к апрелю, а n = 4 – к январю. В рекуррентном соотношении (3.65) динамического программирования январский спрос обозначен d4; аналогичные индексы использованы и для целевой функции.
Начальный уровень запасов считается характеристикой состояния системы за n шагов до конца планового периода. Продолжая рассмотрение примера, построенного для четырех месяцев, заметим, что если известен уровень запасов на начало апреля и апрельский спрос, то необходимый объем производства в точности должен быть равен разности между двумя этими величинами. Такая зависимость отображается уравнением (3.64). Таким образом, если уровень запасов на начало апреля известен, нахождение оптимального выпуска для этого месяца чрезвычайно просто.
Аналогично этому, при известном уровне запасов на начало марта и мартовском спросе, необходимый объем выпуска должен быть не меньше, чем разность между этими двумя величинами.
В свою очередь, принимаемое решение об объеме производства в марте влияет на уровень запасов на начало апреля – этот уровень равен (i + x – d2). Если последняя величина известна, то можно действовать в апреле оптимальным образом. Однако апрельский выпуск уже был оптимизирован на предыдущем шаге. Поэтому при определении оптимального мартовского объема производства необходимо рассматривать только сумму затрат в марте и соответствующих оптимальных затрат после марта. Вся совокупность этих соображений представлена правой частью соотношения (3.65) динамического программирования. Те же рассуждения можно повторить для февраля и, наконец, для января.
Числовой пример
После того, как модель управления запасами сформирована, можем решить конкретную задачу, стоящую перед фирмой "Партнер".
Для упрощения анализа будем считать, что спрос и функция затрат одинаковы для всех отрезков планового периода. Для конкретности примем
Dt = 3 единицам (спрос постоянен во времени)
Предположим также, что затраты равны сумме двух элементов. Первый из них относится к производству, а второй определяется стоимостью содержания запасов, которая является линейной функцией объема запасов. Таким образом, для всех отрезков
Ct(xt, it) = C(xt) + hit, (3.66)
где C(0) = 0, C(1) = 15, C(2) = 17, C(3) = 19, C(4) = 21, C(5) = 23; h = 1.
В свою очередь, производственные затраты можно рассматривать как сумму условно-постоянных затрат на операции по переналадке (эти затраты равны 13 условным единицам) и пропорциональных затрат (они равны 2 условным единицам на каждую единицу продукции). Поскольку h = 1, затраты на содержание запасов численно равны уровню запасов на конец отрезка времени.
Производственные мощности и складские площади фирмы "Партнер" ограничены; это вводит в задачу дополнительное усложнение. Примем, что выпуск продукции в течение одного отрезка не может превысить 5 единиц, а уровень запасов на конец отрезка – 4 единицы. Таким образом, для всех отрезков
xt = 0, 1, 2, 3, 4, 5 и it = 0, 1, 2, 3, 4.
Заметим, что затраты на переналадку относительно высоки по сравнению с другими элементами; поэтому в оптимальной программе должна появиться тенденция к укрупнению партий. Однако объем выпуска xt не может превысить 5 единиц, тогда как спрос равен 3. Следовательно, в течение одного отрезка уровень запасов не может возрасти более чем на 2 единицы. Таким образом, в течение двух первых отрезков не удается избежать двух переналадок, если исходный запас равен нулю. Вовсе неочевидно, какая программа выпуска окажется оптимальной в случае более длительного планового периода.
При наличии приведенных данных об условиях деятельности фирмы "Партнер" можно составить динамическое рекуррентное соотношение, отображающее специфику задачи. Напомним, что используются следующие обозначения:
fn(i) – минимальные затраты в течение n последних отрезков планового периода
при начальном уровне запасов i;
xn(i) – выпуск, позволяющий достичь fn(i).
Для n = 1
f1(i) = C(3 – i), x1(i) = 3 – i , i = 0, 1, 2, 3, (3.67)
поскольку уровень запасов на конец планового периода равен нулю. В общем виде рекуррентное соотношение можно записать следующим образом
fn(i) = [C(x) + 1(i + x – 3) + fn-1(i + x – 3)], n = 2, 3, ..., (3.68)
где i = 0, 1, 2, 3, 4, и для отыскания минимума перебираются все неотрицательные целые значения x, заключенные в пределах 3 – i £ x £ min(5, 7– i). Ограниченность производственных мощностей не позволяет x превысить 5, а ограниченность уровня запасов на конец отрезка не позволяет x превысить (7 – i).
|
Для того чтобы анализ был содержательным, необходимо располагать всеми значениями функций fn(i). В связи с этим проведенные вычисления помещены в таблицы. Для каждого шага n построена одна таблица; в ней предусмотрено по одной строке для каждого возможного значения начального уровня запасов i и по одному столбцу – для каждого возможного значения выпуска x. Поскольку спрос на продукцию в пределах каждого отрезка должен быть полностью удовлетворен, а уровень запасов на конец отрезка не может превысить 4 единицы, некоторые клетки в таблицах "запрещены" – они соответствуют недопустимым сочетаниям i и x. Каждое из проставленных в таблице чисел представляет собой сумму затрат для рассматриваемого отрезка n и оптимальных затрат для всех (n -1) последующих отрезков. В двух правых столбцах таблицы проставлены: минимальная по строке сумма [в столбце fn(i)] и соответствующий ей оптимальный выпуск [в столбце xn(i)].
|
Значения f1(i), вычисленные по формуле (3.67), приведены в таблице рис.3.13, а значения функции f2(i) – в таблице рис.3.14. Рассмотрим структуру последней таблицы более подробно, В ней имеется 5 строк, по одной для каждого допустимого значения i. Клетки, соответствующие некоторым сочетаниям i и x, "запрещены" (на рисунке заштрихованы). Так, если i = 1, то спрос удается удовлетворить только при условии x³ 2. Если i=4, то x £2, иначе нарушается условие нулевого уровня запасов на конец планового периода. Первое из слагаемых в каждой клетке – значение C(x), вычисленное по формуле (3.66). Второе слагаемое – затраты на содержание запасов, равные уровню запасов на конец отрезка, умноженному на h = 1. Так, например, при i = 3 и x = 0 уровень запасов на конец отрезка равен нулю; поэтому равно нулю и второе слагаемое в соответствующей
клетке. При i = 3 и x =1 уровень запасов на конец месяца равен 1; в соответствующей клетке второе слагаемое также равно нулю. Аналогичным образом значения вторых слагаемых вычисляются и для других клеток третьей строки (i =3). Наконец, третье слагаемое – это значение f1(i+x-3), ранее вычисленное и приведенное в таблице рис.3.13.
|
Для каждого фиксированного i значение функции f2(i) представляет собой минимальную из всех сумм в "клетках" данной строки, а x2(i) – соответствующий выпуск. Так, при i = 1 и n = 2 оптимальный выпуск равен 5 единицам; он позволяет за два месяца достичь затрат, равных 26. Любое другое значение x обусловливает более высокие затраты.
|
Расчет значений f3(i) приведен в таблице рис.3.15. Здесь первое слагаемое равно [C(x)+1(i+x-3)], а второе слагаемое есть значение f2(i+x-3), взятое из таблицы рис.3.14. Остальные значения fn(i) для n = 4, 5, 6 представлены в
сводной таблице рис.3.16. Читателю следует проверить, насколько им освоены рекуррентные вычислительные операции метода динамического программирования, построив целиком расчетную таблицу для f4(i), аналогичную таблице рис.3.15, и сравнив полученные результаты с теми данными, которые представлены в сводной таблице рис.3.16. Отметим, что для n = 4 оптимальными являются два значения выпуска – 3 единицы и 4 единицы.