2.1. задача о распределении инвестиций
2.1. задача о распределении инвестиций
"Условие задачи. В производственное объединение входят три предприятия Пі, ТІ2, Щ. Руководство объединения решило инвестировать в свои предприятия 5 условных денежных единиц (усл. ден. ед.) в общей сумме. Проведенные маркетинговые исследования прогнозируют величину ожидаемой прибыли каждого из предприятий в зависимости от объема инвестированных средств. Эти данные представлены в приведенной ниже таблице. Считается, что при нулевых инвестициях ожидается нулевая прибыль.
Требуется найти такое распределение инвестиций между предприятиями, которое обеспечило бы максимум суммарной ожидаемой прибыли.
Решение. В данной задаче управляемой системой является рассматриваемое производственное объединение, многошаговым процессом — процесс выделения средств предприятиям. Отметим, что структура многошагового процесса в данной задаче определяется не течением времени, а порядком планирования распределения инвестиций. Экономический эффект представляет суммарная величина ожидаемой прибыли, и при этом задача решается на поиск максимума.
Для решения поставленной задачи построим прежде всего ее экономико-математическую модель в соответствии с пп. 1-5 разд. 1.7 гл. 1.
Число шагов ./V в данной задаче следует принять равным 3, соответствующим числу входящих в производственное объединение предприятий: на первом шаге планируется выделение средств предприятию П, на втором шаге — предприятию Я2, на третьем шаге — предприятию Щ.
В качестве фазовой переменной х, определяющей состояние системы в ходе процесса распределения инвестиций, примем суммарный объем средств, выделенных предприятиям после каждого шага процесса. Именно, переменная х представляет объем средств, выделенных предприятиям после первого шага процесса (т. е. только предприятию П), Х2 — объем средств, выделенных после второго шага (предприятиям П и Д2), х3 —объем средств, выделенных после третьего шага процесса (всем предприятиям П, Я2 и Яз). Поскольку в начальный момент общая сумма выделенных средств равна 0, то начальное состояние системы характеризуется значением xq = 0. По условию задачи общая сумма инвестируемых средств равна 5 усл. ден. ед., т. е. обязательно выполняется условие хз = 5. Поскольку по смыслу задачи на каждом шаге процесса значения фазовой переменной не убывают, то выполняется ограничение Zj ^ 5. Отметим, что проведенный выбор фазовой переменной с указанным экономическим смыслом не является единственно возможным. Например, в рассматриваемой задаче можно было выбрать в качестве переменной х остаток нераспределенных средств.
В качестве управляющей переменной и примем объем средств, выделяемых предприятиям на каждом из шагов процесса. Именно, переменная щ представляет объем средств, выделяемых предприятию Щ (на 1-м шаге процесса), и2 — объем средств, выделяемых предприятию П2 (на 2-м шаге), из — объем средств, выделяемых предприятию 773 (на 3-м шаге). Будем считать, что средства предприятиям выделяются суммами но целому числу усл. ден. ед.; соответственно все управления принимают только целочисленные значения 0, 1, 2,... .
Функция процесса хі = /і(хі-і,щ), определяющая закон изменения состояния системы, для данной задачи представляется формулой
Хі = Хі-і + Щ
и имеет следующий простой смысл: суммарный объем средств хі, выделенных предприятиям нарастающим итогом после текущего шага с номером г, равен суммарному объему средств выделенных предприятиям после предшествующего шага с номером і — 1 (или, что то же самое, до текущего шага), плюс объем средств щ, выделенных предприятию Щ на текущем шаге.
Функция Zi, определяющая частный экономический эффект на шаге с номером г процесса, зависит только от объема щ инвестированных средств в предприятие Щ, т. е. Zi = Zi(m), и определяется по таблице данных задачи по столбцу, отвечающему этому предприятию. Например, z(2) = 4 (из столбца, отвечающего предприятию Пі), z2(3) = 6, 23 (4) = 9.
На этом действия, предписываемые пп. 1-5 разд. 1.7 гл. 1 выполнены, что означает завершение математической формализации поставленной задачи, т. е. построение соответствующей экономико-математической модели. Заметим, что после проведенной указанным образом формализации основные допущения метода ДП выполняются: отсутствие последействия следует из явных формул для вычисления Хі и Zi, а аддитивность целевой функции
Z = Zi(ui) + Z2 (и2) + 23(м3)
обусловлена самой постановкой задачи.
Тем самым можно непосредственно приступить к расчетам в соответствии с методом ДП. Эти расчеты, как указывалось выше в разд. 1.6 гл. 1, проводятся в три этапа: предварительный этап, этап условной оптимизации и этап безусловной оптимизации. На предварительном этапе и на этапе условной оптимизации результаты расчетов заносятся во вспомогательную и основную таблицы той структуры, которая приведена в разд. 1.7 гл. 1. На этапе безусловной оптимизации строится оптимальное решение задачи с использованием информации, содержащейся в основных таблицах.
Предварительный этап. Данный этап решения задачи проводится в естественном порядке для і = 1, 2,3 и не связан непосредственно с вычислением функций Беллмана Ві(хі). Заполняются только первая строка вспомогательной таблицы и четыре левых столбца основной таблицы.
і = 1.
Вспомогательная таблица заполняется соответственно начальному условию xq = 0 и имеет вид
х0 | 0 |
В0(х0) |
Заполнение основной таблицы проводится следующим образом. Для заданного единственного допустимого значения xq = 0 выбираем все возможные значения управления щ (оно может принимать все целочисленные значения от 0 до 5 включительно) и заносим их во второй столбец таблицы. По формуле xi — xq + щ (следующей из общей формулы хг = Xi-i + щ при і = 1) проводим расчет соответствующих значений переменной хх и заносим их в третий столбец. Для заполнения четвертого столбца значения ожидаемой прибыли zx берем из столбца таблицы исходных данных задачи, отвечающего предприятию Пі. для щ — 1 по этой таблице zj = 2, для и = 2 по таблице zi — 4 и т. д. Для щ = 0 по условию задачи zi = 0. Получаем следующую основную таблицу:
х0 | щ | хх • | z | Bi(xi) | Zi + Ві | Bq(x0) |
0 | 0 | 0 | 0 | |||
1 | 1 | 2 | ||||
2 | 2 | 4 | ||||
3 | 3 | 6 | ||||
4 | 4 | 8 | ||||
5 | 5 | 10 |
На этом заполнение левой части основной таблицы завершено, причем таблица имеет только один строчный фрагмент. Переходим к следующему шагу.
На втором шаге в первую строку вспомогательной таблицы внесем все значения переменной х, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Получаем следующую вспомогательную таблицу:
Хх | 0 | 1 | 2 | 3 | 4 | 5 |
Для заполнения основной таблицы на данном шаге будем, аналогично предшествующему шагу, последовательно выбирать все допустимые значения х, внесенные во вспомогательную таблицу, и проводить соответствующие расчеты. Каждому значению х будет соответствовать свой строчный фрагмент основной таблицы; разделяются соседние строчные фрагменты горизонтальной линией.
Для значения х = 0 выбираем все возможные значения управления U2 (оно может принимать все целочисленные значения от О до 5 включительно) и заносим их во второй столбец таблицы. По
формуле Х2 = Х + U2 (следующей ИЗ общей формулы Xi = Xi-l + щ
при г = 2) проводим расчет соответствующих значений переменной х2 и заносим их в третий столбец. Для заполнения четвертого столбца значения ожидаемой прибыли z2 берем из столбца таблицы исходных данных задачи, отвечающего предприятию П^'. для и2 = 1 по этой таблице Z2 = 1, для U2 — 2 по таблице z2 = 2 и т. д. На этом завершается заполнение первого строчного фрагмента основной таблицы, соответствующего х = 0; этот фрагмент имеет следующий вид:
хх | U2 | х2 | Z2 | В2{х2) | z2 + B2 | Вх(хх) |
0 | 0 | 0 | 0 | |||
1 | 1 | 1 | ||||
2 | 2 | 2 | ||||
3 | 3 | 6 | ||||
4 | 4 | 10 | ||||
5 | 5 | 12 |
Для следующего допустимого значения xi = 1 строим следующий строчный фрагмент. При этом управление и2 может принимать все целочисленные значения от 0 до 4 включительно (поскольку после выделения предприятию П средств в объеме Х = 1
Аналогично формируются строчные фрагменты таблицы и для х = 2,3,4,5. Ясно, что с увеличением значения Х множество допустимых значений управления U2 сужается, и для Х = 5 допустимым является только одно значение и2 = 0. В результате получаем следующую основную таблицу:
Хх | "2 | х2 | z2 | В2(х2) | z2 + B2 | Bi(xx) |
0 | 0 | 0 | 0 | |||
1 | 1 | 1 | ||||
2 | 2 | 2 | ||||
3 | 3 | 6 | ||||
4 | 4 | 10 | ||||
5 | 5 | 12 | ||||
1 | 0 | 1 | 0 | |||
1 | 2 | 1 | ||||
2 | 3 | 2 | ||||
3 | 4 | 6 | ||||
4 | 5 | 10 | ||||
2 | 0 | 2 | 0 | |||
1 | 3 | 1 | ||||
2 | 4 | 2 | ||||
3 | 5- | 6 | ||||
3 | 0 | 3 | 0 | |||
1 | 4 | 1 | ||||
2 | 5 | 2 | ||||
4 | 0 | 4 | 0 | |||
1 | 5 | 1 | ||||
5 | 0 | 5 ... | 0 |
Построенная таблица разделена на 6 строчных фрагментов-столько же, сколько различных значений может принимать переменная xi. Переходим к следующему (последнему) шагу. .
і = 3.
На третьем шаге в первую строку вспомогательной таблицы внесем все значения переменной х2, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Эти значения многократно повто
Обсуждение Динамическое программирование в экономических задачах
Комментарии, рецензии и отзывы