2.2. задача о распределении инвестиций по максимуму нормы прибыли
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 строчных фрагментов включает только одну строку, а основная таблица имеет вид:
![]() |
і = 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 |
Обсуждение Динамическое программирование в экономических задачахКомментарии, рецензии и отзывы 2.2. задача о распределении инвестиций по максимуму нормы прибыли: Динамическое программирование в экономических задачах, Лежнёв А. В., 2010 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Изложен принцип оптимальности и базирующийся иа нем метод динамического программирования решения задач управления многошаговыми процессами, разобран ряд примеров решения типовых задач экономического содержания....
|