Имя материала: Динамическое программирование в экономических задачах

Автор: Лежнёв А. В.

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

 

 

 

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

i = 2.

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

 

Хх

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, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Эти значения многократно повто

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |