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. Соответственно, вспомогательная таблица имеет вид:

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

= 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 и не связан непосредственно

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

і = 2.

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

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

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

і = 3.

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

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

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