Распределение капитальных вложений

Идеи метода динамического программирования

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

Поэтому процесс динамического программирования на 1-м этапе раз­ворачивается от конца к началу, то есть раньше всех планируется послед­ний,

N-й шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать все возможные предположе­ния о том, чем кончился предпоследний, (N — 1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на послед­нем шаге был бы максимален. Решив эту задачу, мы найдем условно оптимальное управление (УОУ) на N-м шаге, т.е. управление, которое надо применить, если (N — 1)-й шаг закончился определенным образом.

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

(N — 1)-го шага мы знаем УОУ на N-м шаге и соответствующий ему условно оптимальный выигрыш (УОВ). Теперь мы можем оптими­зировать управление на предпоследнем, (N — 1)-м шаге. Сделаем все возможные предположения о том, чем кончился предпредпоследпий, то есть (N — 2)-й шаг, и для каждого из этих предположений найдем такое управление на (N — 1)-м шаге, чтобы выигрыш за последние два ша­га (из которых последний уже оптимизирован) был максимален. Далее оптимизируется управление на (N — 2)-м шаге, и т.д.

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

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

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

Примем следующие обозначения:

	Номер предприятия (j=1,2,…,n)
	Общая сумма капитальных вложений
	Сумма капитальных вложений в j-ое предприятие
	Прирост мощности или прибыли j-го предприятия, если оно получит xj денежных единиц капитальных вложений

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

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

=0 или 1, или 2, или 3, …;

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

	Некоторое количество предприятий, для которых определяется параметр и функция состояния ()
	Сумма капитальных вложений, выделяемая нескольким предприятиям ()
	Максимальный прирост прибыли или мощности на первых предприятиях, если они вместе получат капитальных вложений

Тогда, если из денежных единиц k-ое предприятие получит денежных единиц, то остаток денежных средств необходимо распределить между предприятиями от первого до так, чтобы был получен максимальный прирост прибыли или мощности. Следовательно, прирост прибыли или мощности k предприятий будет равен и нужно выбрать такое значение между 0 и, чтобы увеличение прибыли или мощности k предприятий было бы максимальным, т.е.:

, где.

Если же k=1, то:

Допустим, что производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 денежных единиц (b=700), при этом суммы выделяемые предприятиям кратны 100 денежным единицам. Значения функций приведены в таблице 3:

Таблица 3.

Для заполнения таблицы 5 необходимо в таблице 4 сложить значения функции со значениями и на каждой северо-восточной диагонали выбрать наибольшее число (отмечено звездочкой), указав соответствующие значение:

Таблица 4.
0			42^*
100			72^*
			91^*	107^*
				121^*	134^*	143^*

Таблица 5.

Для заполнения таблицы 7 необходимо в таблице 6 сложить значения функции со значениями и на каждой северо-восточной диагонали выбрать наибольшее число (отмечено звездочкой), указав соответствующие значение:

Таблица 6.
0			42^*	72^*
100				94^*	113^*	129^*
						144^*	158^*

Таблица 7.

Теперь, в таблице 8, необходимо сложить значения функции со значениями, но только для значения, т.е. заполнить только одну диагональ:

Таблица 8.
100
							197^*

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

денежных единиц

причем четвертому предприятию должно быть выделено:

денежных единиц

Тогда третьему предприятию должно быть выделено (см. табл. 7.):

денежных единиц

второму предприятию должно быть выделено (см. табл. 5.):

денежных единиц

на долю первого предприятия остается:

денежных единиц

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

которое обеспечивает производственному объединению наибольший возможный прирост прибыли:

денежных единиц

Динамическая задача управления запасами

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

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

Примем следующие обозначения:

	Номер месяца (j=1,2,…,n)
	Число изделий, производимых в j-ом месяце
	Величина запаса к началу j-го месяца
	Число изделий, которые должны быть отгружены в j-ом месяце
	Затраты на хранение и производство изделий в j-ом месяце

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

, где

и минимизируют суммарные затраты за весь планируемый период:

причем по смыслу задачи,, при

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

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

	Наличный запас продукции в конце k-го месяца ()
	Минимальные затраты за первые месяцев:

Тогда, минимальные затраты за один первый месяц ():

Следовательно, минимальные затраты при:

, где

Если при этом функция затрат на хранение и производство изделий в j-ом месяце имеет вид:

, где

, при и, при
	Затраты на оформление заказа (переналадку оборудования) в j-ом месяце
	Затраты на хранение единицы продукции, переходящей из j‑го месяца в месяц j+1
	Затраты на производство (закупку) единиц продукции в j‑ом месяце

то минимальные затраты за один первый месяц ():

если ввести обозначение:

то следовательно, минимальные затраты при:

, где

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

Таблица 9.
Период k
Спрос ()
Затраты на оформление заказа ()
Затраты на хранение единицы запаса ()

Предполагается, что затраты на приобретение продукции составляют 5 руб. за каждую единицу для первых трех единиц и 7 руб. за каждую дополнительную единицу, т.е.

Положим, тогда:

Тогда, т.к. параметр состояния может принимать значения на отрезке:

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

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

т.е. каждому значению отвечает единственное значение, поэтому:

, тогда:

Значения функции состояния приведены в таблице 10.:

Таблица 10.

Положим, тогда:

, где:

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

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

т.е., при этом из балансового уравнения следует, что остаток товара на начало второго месяца связан с объемом производства и с параметром состояния соотношением:

Тогда:

()

^*   ^*

Наименьшие из полученных значений, есть, т.е.:

причем минимум достигается при и, т.е.:

и

эти значения указываем в результирующей таблице 11.

Аналогично:

()			^*
()			^*
()			^*

Таким образом:

Таблица 11.

Теперь положим, что, тогда:

, где:

Если оставлять продукцию к концу третьего периода не нужно, тогда параметр состояния принимает единственное значение, следовательно, переменная может изменяться в пределах:

а из балансового уравнения следует, что остаток товара на начало третьего месяца связан с объемом производства соотношением:

Тогда:

()

^*

Следовательно, получаем:

причем минимум достигается при, т.е.:

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

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

Тогда т.к., то, откуда, следовательно, из таблицы 11.:

или

Аналогично т.к., то или, откуда или, следовательно, из таблицы 10.:

или

Следовательно, получен оптимальный план производства, который имеет два варианта:

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

Элементы модели динамического программирования. Задача распределения капиталовложений

Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме 5 млн. долл. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами (в миллионах долларов) суммарных затрат (с) и доходов (R), связанных с реализацией каждого из проектов. Соответствующие данные приведены в табл.. 9.1, в которую включены также проекты с нулевыми затратами. Это позволяет учесть возможность отказа от расширения какого-либо предприятия. Цель фирмы состоит в получении максимального дохода от инвестиций в объеме 5 млн. долл

Таблица 9.1

Прямой и, по-видимому, чрезмерно упрощенный способ решения сформулированной задачи заключается в использовании процедуры полного перебора. Задача имеет 3x4x2=24 возможных решения, причем некоторые из них не являются допустимыми, так как пред­полагают ассигнование свыше 5 млн. долл. В процессе полного перебора вычисляются суммарные затраты, ассоциированные с каж­дым из 24 возможных решений. Если величина затрат не превышает объема авансированных средств, следует вычислить соответствующий суммарный доход. Оптимальным будет допустимое решение, _обеспечивающее максимум суммарного дохода. Например, затраты на реализацию проектов 2, 3 и 1 для предприятий 1, 2 и 3 составля­ют 4 млн. долл. (<5), а суммарный доход равен 14 млн. долл. С дру­гой стороны, набор проектов 3, 4 и 2 не является допустимым, так как объем затрат в этом случае равен 7 млн. долл.

Отметим следующие недостатки процедуры полного перебора.

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

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

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

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

Сетевая модель

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

х₁=объем капиталовложений, распределенных на этапе 1; х_а=объем капиталовложений, распределенных на этапах 1 и 2; х₃=объем капиталовложений, распределенных на этапах 1, 2, 3.

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

Заметим, что конкретные значения х_г и х_% заранее не известны, однако мы знаем, что эти значения лежат в интервале между 0 и 5. Так как затраты на реализацию каждого из проектов выражаются целыми числами, значения х_г и х₂ могут быть равны 0, 1, 2, 3, 4 и 5. С другой стороны, значение переменной х₃, которая выражает объем капиталовложений, распределенных на всех трех этапах, равно 5.

Рис. 9.1 служит иллюстрацией сетевой модели для рассматри­ваемой задачи. Каждому возможному значению х_ь х₂ и х₃ поставлен в соответствие узел, ассоциированный с одним из этапов /=1, /=2 и /=3. Начальный этап /=0 введен в рассмотрение для удобства вы­числений. Длины дуг, соединяющих узлы на некотором этапе с узлами на последующем этапе, численно равны доходам от реализации наилучшего допустимого проекта.Рассмотрим дуги, соединяющие узел U на этапе/=0 с узлами 0, 1, 2, 3, 4, 5 на этапе /= 1. Дуга (О, 0) (соединяющая узлы 0 на этапе /=0 и 0 на этапе /= 1) соответст­вует случаю, когда средства на этапе 1 не выделяются. Допустимым

здесь является проект 1 с Л?1=0, и дуге (0, 0) приписывается длина Ri (О, 0)=0. С другой стороны, для дуги (0, 1) допустимыми оказы­ваются проекты 1 и 2, что предопределяет выбор проекта 2 с более высоким уровнем дохода /=5; дуге (0, I) приписывается длина 5. По тем же самым причинам дуге (0, 2) приписывается длина 6, по­скольку здесь все три проекта являются допустимыми, а проекту 3 соответствует самый высокий уровень дохода /=6. Значения i=3, 4 и 5 соответствуют «избыточным» вариантам, для которых в лучшем случае =6.

Если внимательно изучить построенную сеть, то нетрудно" заметить, что некоторые дуги можно отбросить как заведомо неоптимальные. Например, можно исключить дугу (0, 1) между этапами /=1 и /=2, так как ассигнование =l млн. долл. на этапе 2 не приносит ни­какого дохода, поскольку эта сумма не является достаточной для реализации проекта 2. Исключение неоптимальных дуг значительно уменьшает объем необходимых вычислений. Однако чтобы сделать изложение материала более доходчивым, мы не будем рассматривать процедуры такого рода. Тем не менее, если у вас появился интерес к проблеме идентификации неоптимальных дуг, рекомендуем обра­титься к следующему упражнению.

Упражнение 9.1.1. Выявите все заведомо неоптимальные дуги сети, изобра­женной на рис. 9.1.

Ответ. Все перечисленные ниже дуги заведомо не являются оптимальными, так как соответствуют вариантам с элементами неокупаемых затрат. Дуги между этапами /—0 и /=1: (0, 3), (0, 4) и (0, 5). Дуги между этапами /—1 и /=2: (0, 1), (0, 5), (1, 2), (2, 3), (3, 4), (4, 5). Дуги между этапами /=2 и /=3: (0, 5), (1, 5), (2, 5) и (3, 5).

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

Обозначим через fj(Xj) величину самого длинного пути, ведущего в узел xj на этапе /. Поскольку /—О — исходный этап, /₀(0)=0. Далее вычисления производятся поэтапно.

Ниже приводятся результаты вычислений по данной формуле. (Со­ветуем обратиться к рис. 9.1 и проследить за ходом вычислений.)

f₂(1)=max{0+0; 5+0}=5,

f₂(2)=max{0+8; 5+0; 6+0}=8,

f₂(3)=max {0+9; 5+8; 6+0; 6+0} = 13,,

f_a(4)max (0+12; 5+9; 6+8; 6+0; 6+0} = 14,

f₂(5)=max J0+12; 5+12; 6+9; 6+8; 6+0; 6+0} = 17. Полученные результаты представлены на рис. 9.2, б, на котором показаны дуги, соответствующие вычисленным значениям f₂. Как и ранее, числа в круглых скобках обозначают номера проектов, ассоциированных с конкретными дугами.

В результате вычислений находим (см. рис. 9.1) f₃(5)=max {0+3;5+3;8+3;13+3;14+3;17+0}=17.

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

Отметим, что всем трем решениям соответствует один и тот же уро­вень дохода, а именно 17млн. долл.

РАЗДЕЛ 5. ТЕОРИЯ ИГР.

Дата добавления: 2014-01-15