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

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

2.2.    задача о распределении инвестиций по максимуму нормы прибыли

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

Замечание 1. Конечно, поставленную задачу можно решить по образцу предыдущей, проведя отдельно расчеты для сумм в 3, 4 и 5 усл. ден. ед., но это привело бы к громоздким дублирующимся вычислениям. Гораздо более эффективным решением будет проведение одного общего расчета по следующей схеме, в которой проведен иной выбор фазовой переменной.

Решение. В данной задаче, как и в предыдущей, управляемой системой является рассматриваемое производственное объединение, многошаговым процессом — процесс выделения средств предприятиям. Экономический эффект представляет норма прибыли, и при этом задача решается на поиск максимума.

Проведем прежде всего математическую формализацию поставленной задачи, т. е. построим ее экономико-математическую модель в соответствии с пп. 1-5 из разд. 1.7 гл. 1.

Число шагов N в данной задаче, как и в предыдущей, следует принять равным 3: на первом шаге планируется выделение средств предприятию Пі, на втором шаге — предприятию П2, на третьем шаге — предприятию Щ.

Поскольку в отличие от предыдущей задачи сумма распределяемых средств не является известной заранее, то следует рассмотреть не одно, а несколько возможных начальных состояний системы. При этом в качестве фазовой переменной х, определяющей состояние системы в ходе процесса распределения инвестиций, удобно принять суммарный объем средств, оставшихся нераспределенными после каждого шага процесса. Начальное состояние системы представляет собой весь объем инвестируемых средств и характеризуется переменной xq, которая может принимать значения 3, 4, 5. Переменная xi представляет объем нераспределенных средств после первого шага процесса (т. е. после выделения средств предприятию Пі), х2 — объем нераспределенных средств после второго шага (после выделения средств предприятиям Пі и П2), 2:3 — объем нераспределенных средств после третьего шага процесса (после выделения средств всем предприятиям Пі, П2 и /7з). Поскольку все инвестируемые средства распределяются между предприятиями без остатка, то должно выполняться условие х\% = 0.

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

т + и2 + и3 = xq.

Функция процесса хі = /і(хі-і,щ), определяющая закон изменения состояния системы, для данного выбора фазовой и управляющей переменных представляется формулой

Х\% — Хі~ і Ui

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

5. Составим целевую функцию, определяющую экономический эффект в данной задаче. Чтобы в наибольшей степени сохранить сходство с предыдущей задачей и подчеркнуть отличия, обозначим частные целевые функции, итоговую целевую функцию и оптимальное значение данной задачи через yi, Y и Y* соответственно. Как и выше, будем обозначать через Zi — Zj(uj) ожидаемую прибыль предприятия И при инвестировании в него средств в объеме щ; эта функция задается таблицей исходных данных из условия предыдущей задачи. Суммарная прибыль производственного объединения равна

Zi + z2 + z3

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

у _ zl + z2 + Z3 ^

х0

при этом, очевидно, частные целевые функции у і следует принять равными Zi/xQ, что приведет к равенству Y = yi + у2 + уз.

Задание аддитивного критерия оптимальности позволяет непосредственно приступить к решению задачи, но мы проведем сначала некоторые преобразования, имея в виду следующие обстоятельства. В выражении для функции Y присутствует деление на переменную xq, имеющую общее значение для всех шагов; возникает желание «вынести» эту переменную «за "скобки». Более того, деление, как правило, приводит к возникновению дробных чисел на промежуточных этапах и загромождает решение.

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

Р(х0) —  max {zi + z2 + z3 | щ + u2 + щ = x0},

гіі,гі2,гіз

где максимум берется по всевозможным значениям управляющих переменных иі,и2,щ, удовлетворяющим условию щ + и2 + Щ = Xq.

Вычисление функции Р(хо) может быть проведено методом ДП, причем частными целевыми функциями здесь являются Zi, а промежуточные деления отсутствуют. Отношение

ры

х0

равно максимальной норме прибыли производственного объединения при общем объеме хо инвестиций, а оптимальное значение задачи Y* вычисляется по формуле

Y  = max< ——- >, хо   {   x0 J

Щ + U2 + Щ — x0 J = Щ +U2 +Щ = x0

где максимум берется по xq= 3, 4, 5. Проведенные рассуждения можно представить следующей цепочкой равенств:

Z + 22 + 23

X0,Ul,U2,U3 [ Хо

Z+ Z2 + 23

max< max

Хо     I U1,U2,U3 I Xo

Y = max

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

г = 1.

В данном случае начальное состояние системы не является определенным однозначно, а соответствующая переменная xq принимает несколько допустимых значений: 3, 4, 5. Соответственно, вспомогательная таблица имеет вид:

 

Хо

3

4

5

Во{хо)

8

10

13

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

= max

xo

Mr       I          1 1       f рЫ 1

< — max z + Z2 + z3u +U2 +Щ = xq > — max<         >,

[_ Xoui,u2,u3            )           x0    ^    Xo )

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

вычисление функции Р(хо) для каждого допустимого значения жо методом ДП;

вычисление оптимального значения задачи Y* и построение оптимального решения.

На этом математическая формализация поставленной задачи завершена. Как нетрудно проверить, основные допущения метода ДП — отсутствие последействия и аддитивность целевой функции —для нее выполняются. Тем самым можно непосредственно приступить к расчетам, включающим предварительный этап, этап условной оптимизации и этап безусловной оптимизации. Важно подчеркнуть, что вычисляемая функция Р(хо) равна функции Беллмана Во(хо) для решаемой задачи с целевой функцией 21+22 + 23:

РЫ = в0(х0).

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

Предварительный этап. Данный этап решения задачи проводится в естественном порядке для г = 1, 2, 3 и не связан непосредственно

 

Хо

Ml

Х

21

Bi(zi)

zi + Bi

Во{х0)

3

/0

3

0

8

8

8

 

/1

2

2

6

8

 

 

2

1

4

3

7

 

 

3

0

6

0

6

 

4

/0

4

0

10

10

10

 

/1

3

2

8

10

 

 

/2

2

4

6

10

 

 

3

1

6

3

9

 

 

4

0

8

0

8

 

5

/0

5

0

13

13

13

 

1

4

2

10

12

 

 

2

3

- 4

8

12

 

 

3

2

6

6

12

 

 

4

1

8

3

11

 

 

5

0

10

0

10

 

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

і = 2.

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

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

 

х2

0

1

2

3

4

5

В2(х2)

0

3

6

8

9

10

 

Xi

0

1

2

3

4

5

вг(хг)

0

3

6

8

10

13

Заполнение основной таблицы проводится обычным образом с учетом той особенности, что для выполнения условия хз = 0 необходимо в соответствии с полученной выше формулой хі = Xj_i — щ при і = 3 выбирать из = х2. Соответственно каждый из 6 строчных фрагментов включает только одну строку, а основная таблица имеет вид:

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

і = 3.

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

 

х2

и3

хз

23

Вз(х3)

z3 + B3

В2(х2)

0

0

0

0

0

0

0

1

1

0

3

0

3

3

2

2

0

6

0

6

6

3

3

0

8

0

8

8

4

4

0

9

0

9

9

5

5

0

10

0

10

10

На этом предварительный этап решения задачи завершен. Приступаем к этапу условной оптимизации.

Этап условной оптимизации. Данный этап непосредственно связан с вычислением функций Bi (xj ) и проводится в обратном порядке для г = 3,2,1. При этом заполняются остальные фрагменты таблиц: вторая строка вспомогательной таблицы и три правых столбца основной таблицы. На этом же этапе расставляются и знаки «/», указывающие те условно-оптимальные значения управления, на которых достигаются промежуточные условные максимумы. (Как было сказано выше, все получаемые таблицы приведены уже окончательно заполненными.)

і = 3.

Поскольку в силу принципа оптимальности Беллмана имеет место равенство Вз(хз) = 0, то в пятый столбец основной таблицы записываем нулевые значения. При этом в шестой столбец записываются суммы соответствующих чисел из двух предшествующих столбцов, а в последний столбец заносится максимум из всех чисел шестого столбца для каждого строчного фрагмента отдельно. Но поскольку в каждом строчном фрагменте последней основной таблицы имеется только одна строка, то соответствующий максимум В2{х2) равен сумме гз + В3. Полученные значения функции В2(х2) заносятся во вторую строку вспомогательной таблицы.

Аналогично завершается заполнение основных и вспомогательных таблиц для г — 2 и г = 1. Обратим внимание, что в основной таблице дЛЯ і = 1 в некоторых строчных фрагментах имеется более одного знака «/»• Это означает, что промежуточный максимум достигается на нескольких управлениях, что может привести к существованию нескольких различных оптимальных решений задачи. Приступаем к этапу безусловной оптимизации.

Этап безусловной оптимизации. На данном этапе находим оптимальное значение задачи Y* и оптимальное управление (и,и2,и^). Полученные значения функции В0(х0), как уже отмечалось выше, равны значениям функции Р(х0) (значение Во(5) = 13, конечно, совпадает с оптимальным значением предшествующей задачи при распределении 5 усл. ден. ед.). В соответствии с принятой схемой решения задачи необходимо вычислить норму прибыли как отношение

Р(х0) = В0(х0)

Хо Хо

и выбрать максимальное значение. Поскольку

3,(3) _ 8          Я„(4) _ Ю       Д>(5) _ 13 _

___-_2,66...,    —_т_2,5,    — ---2,0,

то максимум нормы прибыли Y* — 2,66... достигается при распределении 3 усл. ден. ед., т. е. оптимальное начальное состояние системы отвечает значению х^ = 3. Соответствующее оптимальное распределение инвестиций находим по основным таблицам, просматривая их еще раз в естественном порядке при г = 1,2,3 и используя отмеченные знаками «/» строки, содержащие условно-оптимальные значения управления. Получаем такую последовательность шагов.

і = 1.

На данном шаге соответствующая основная таблица имеет три строчных фрагмента. Из них выбираем тот строчный фрагмент, который соответствует уже найденному оптимальному начальному состоянию х^ = 3. Но в этом фрагменте условно-оптимальными являются два значения управления щ = 0 и щ = 1, отмеченные знаком «/». Это означает, что задача имеет не одно, а несколько оптимальных решений, по меньшей мере два. Построим сначала первое решение, соответствующее и = 0. Для этого определим по той же строке таблицы х* = 3.

і = 2.

На данном шаге из второй основной таблицы выбираем тот строчный фрагмент, который содержит уже найденное на предшествующем шаге оптимальное значение х = 3. В этом фрагменте оптимальным является единственное управление и = 0, отмеченное знаком «/»; соответственно в той же строке таблицы находим х = 3.

і = 3.

На данном шаге из третьей основной таблицы выбираем тот строчный фрагмент, который соответствует уже найденному оптимальному значению х = 3. Этот фрагмент содержит только одну строку и одно значение управления, которое и будет оптимальным: Ug = 3; в той же строке таблицы находим х\% = 0.

На этом завершено построение первого оптимального решения задачи, которое имеет вид (0,0,3). Проведем построение второго оптимального решения, соответствующего ul = 1, проходя все основные таблицы еще раз уже без детальных пояснений.

 

г

= 1:

 

= з,

 

= 1,

хх

= 2.

г

= 2:

*

хг

= 2,

*

= 0,

 

= 2.

г

= 3:

*

Х2

= 2,

*

= 2,

4

= 0.

Следовательно, второе оптимальное решение имеет вид (1,0,2). Других оптимальных решений задача не имеет. Этап безусловной оптимизации метода ДП завершен.

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

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

выделить все 3 усл. ден. ед. одному предприятию Яз;

выделить 1 усл. ден. ед. предприятию П и 2 усл. ден. ед. предприятию 77з-

Замечание 2. Отметим еще раз все те новые обстоятельства, которые встретились нам при решении данной задачи.

Начальное состояние xq системы не было определено однозначно заранее, а могло принимать ряд различных значений. Оптимальное начальное состояние х^ определялось в ходе решения задачи.

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

Наличие двух условно-оптимальных значений управления для хо = 3 привело к тому, что данная задача имеет несколько оптимальных решений (именно, два различных решения). В то же время подчеркнем, что наличие нескольких условно-оптимальных значений управления не обязательно приводит к существованию различных оптимальных решений задачи. Например, для х0 = 4 существуют 3 условно-оптимальных управления щ = 0,1,2, ни одно из которых не стало безусловно оптимальным по той причине, что значение х0 = 4 оказалось вне оптимальной траектории.

 

2.3.    Задача о загрузке транспортного средства

Условие задачи. Транспортное средство грузоподъемностью М = 50 усл. ед. массы загружается предметами трех типов Гі,Г2,Гз, масса т и стоимость р усл. ден. ед. каждого из которых известны и приведены в таблице.

 

 

Ті

т2

Т3

т

11

17

23

Р

20

Страница: | 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 |