Задача оптимального распределения инвестиций беллман

Задача оптимального распределения инвестиций беллман

Экономические науки/8 математи ческие методы в экономике

Дмитренко Ирина Сергеевна

к.ф-м.н. Колесников Сергей Алексеевич

Донбасская государственная машиностроительная академия

Кафедра высшей математики

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

Среди экономически важных задач большой интерес представляет проблема распределения капитальных вложений между отраслями или предприятиями отрасли. Постановка таких задач, а значит и подбор соответствующего метода решения, зависит от способа задания функции дохода предприятия. В данной работе рассмотрены два способа задания функции доходности и предложены следующие методы решения : 1) метод классической оптимизации, предусматривающий исследование непрерывной функции многих переменных на экстремум с помощью построения функции Лагранжа, 2) метод обратной прогонки динамического программирования для дискретной функции дохода, предусматривающий составление функциональных уравнений Беллмана.

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

Источник

ПРИНЦИП ОПТИМАЛЬНОСТИ БЕЛЛМАНА В ЗАДАЧЕ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СРЕДСТВ МЕЖДУ ПРЕДПРИЯТИЯМИ НА РАСШИРЕНИЕ ПРОИЗВОДСТВА

Полный текст:

Аннотация

Ключевые слова

Об авторах

Список литературы

1. Афанасьев, М. Ю. Суворов, Б. П. Исследование операций в экономике: модели, задачи, решения. – М.: ИНФРА-М, 2003. – 444 с.

2. Беллман, Р. Динамическое программирование. – М.: Изд-во иностранной литературы, 1960. – 401 с.

3. Кремер, Н. Ш., Путко, Б. А., Тришин, И. М., Фридман, М. Н. Исследование операций в экономике: Учеб. пособие для вузов. – М.: ЮНИТИ, 2002. – 407 с.

4. Лежнев, А. В. Динамическое программирование в экономических задачах: учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2010. – 176 с.

5. Токарев, В. В. Модели и решения: Исследование операций для экономистов, политологов и менеджеров – М.: Физматлит, 2014. – 408 c.

Для цитирования:

Тарасенко А.В., Егорова И.П. ПРИНЦИП ОПТИМАЛЬНОСТИ БЕЛЛМАНА В ЗАДАЧЕ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ СРЕДСТВ МЕЖДУ ПРЕДПРИЯТИЯМИ НА РАСШИРЕНИЕ ПРОИЗВОДСТВА. Вестник университета. 2019;(10):132-138. https://doi.org/10.26425/1816-4277-2019-10-132-138

For citation:

Tarasenko A., Egorova I. THE OPTIMAL PRINCIPLE OF BELLMAN IN THE PROBLEM OF OPTIMAL MEANS DISTRIBUTION BETWEEN ENTERPRISES FOR THE EXPANSION OF PRODUCTION. Vestnik Universiteta. 2019;(10):132-138. (In Russ.) https://doi.org/10.26425/1816-4277-2019-10-132-138

Контент доступен под лицензией Creative Commons Attribution 4.0 License.

Источник

Применение методов классической оптимизации и функциональных уравнений Беллмана при решении задач о распределении инвестиций

Среди экономически важных задач большой интерес представляет проблема распределения капитальных вложений между отраслями или предприятиями отрасли. Постановка таких задач, а значит и подбор соответствующего метода решения, зависит от способа задания функции дохода предприятия. В данной работе рассмотрены два способа задания функции доходности и предложены следующие методы решения : 1) метод классической оптимизации, предусматривающий исследование непрерывной функции многих переменных на экстремум с помощью построения функции Лагранжа, 2) метод обратной прогонки динамического программирования для дискретной функции дохода, предусматривающий составление функциональных уравнений Беллмана.

усл.ден.ед.

Прирост выпуска продукции, усл.ден.ед.

Запишем уравнение Беллмана для метода обратной прогонки и разобьем решение задачи на 4 этапа.

Этап 4. F5(C5)=0

F4(C4)=g4(x4)

F3(C3)=g3(x3)+ F4(C3-x3)

F2(C2)=g2(x2)+ F3(C2-x2)

F1(C1)=g1(x1)+ F2(C1-x1)

Из таблицы этапа 1 находим оптимальное значение целевой функции при распределении между предприятиями всей суммы С1=250: F1(250)=55. При этом первому предприятию должно быть выделено x1*=0 ден.ед. Тогда остальным трем предприятиям остается распределить С2=С1-x1*=250-0=250 ден.ед. Из таблицы этапа 2 выделению суммы С2=250 соответствует значение x2*=100, тогда С3=С2- x2*=250-100=150 ден.ед. Из таблицы этапа 3 выделению суммы С3=150 соответствует значение x3*=50, тогда С4=С3- x3*=150-50=100 ден.ед. На последнем этапе 4 определяем x4*=100.

Таким образом, оптимальный план инвестирования предприятий:

X*= (0,100,50,100), который обеспечит максимальный доход, равный

Вторая задача имеет похожую постановку, но функции дохода являются нелинейными. Для модернизации трех предприятий совет директоров инвестирует средства в объеме 150 денежных единиц. Пусть приросты выпуска продукции, а значит и общего дохода, зависят от выделенной суммы для i-го предприятия и выражаются соответствующими квадратичными зависимостями:

Найдем методом множителей Лагранжа распределение инвестиций между предприятиями, которое обеспечит фирме максимальный прирост продукции.

Перед тем, как составить функцию Лагранжа, запишем функцию суммарного дохода предприятий:

Тогда функция Лагранжа имеет вид:

Точку условного экстремума определим из необходимого условия экстремума функции многих переменных:

Таким образом, координаты искомой точки экстремума имеют вид: .

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

1. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Киев, «Высшая школа», 1975. 350-351с.

2. Таха, Хэмди А. Введение в исследование операций. -М.:Изд.дом «Вильямс», 2001.-447-452с.

Источник

Принцип оптимальности Беллмана

Принцип оптимальности Беллмана позволяет решать или осмыслить многие интересные задачи, возникающие в реальной жизни, например, задачу о рациональной эксплуатации генерирующего предприятия (ТЭЦ, ГЭС), выбора экономичного состава агрегатов и др.

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

Если на станциях имеется n агрегатов и каждый из них может быть либо включен, либо отключен, то все множество всех вариантов для работы с любой мощностью составит 2 в степени n.

Даже для n = 50 число вариантов становится очень большим!

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

В частном случае методы динамического программирования позволяют решать подобные задачи при числе агрегатов порядка 20-30.

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

Задача о графике эксплуатации электростанция. Станция имеет L агрегатов, известна производительность одного агрегата и цена единицы произведенной электроэнергии.

Задан график оплаченной электроэнергии, избыточно произведенная электроэнергия не оплачивается.

Известны затраты на поддержание в рабочем агрегатов, затраты на консервацию и затраты на пуск. Требуется определить оптимальный режим эксплуатации.

Интересны задачи о распределении инвестиций и ресурсов.

Задача о распределении инвестиций: имеется несколько предприятий, между которыми требуется распределить данную сумму инвестиций. Известна эффективность вложения данной суммы средств в каждое предприятие.

Задача о распределении ресурса: имеется N предприятий, каждое из которых приносит доход, зависящий от доли выделенного ресурса. Требуется наилучшим способом распределить между ними ограниченный ресурс a на доли x1, . , xN (x1 ≥ 0, . , xN ≥ 0, x1 +. + xN ≤ a).

Задача о наилучшей загрузке транспорта: транспорт, имеющее грузоподъемность a , загружается грузами N типов. Каждый тип груза имеет стоимость yi и вес zi .

Требуется найти оптимальный вариант загрузки, при котором стоимость взятых на борт предметов максимальна.

Задача о замене автомобиля: автотранспортное предприятие планирует приобрести автомобиль и эксплуатировать его в течение N лет.

Можно либо купить новый автомобиль возраста x0 = 0 лет и стоимости p, либо бывший в эксплуатации возраста x0 > 0 лет по стоимости, зависящей от времени эксплуатации.

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

В процессе эксплуатации автомобиль можно продавать по ликвидной стоимости и купить новый. В конце срока эксплуатации автомобиль также продается по ликвидной стоимости. Определить оптимальный возраст автомобиля при покупке и оптимальный график его замены.

Все эти и многие другие задачи могут быть решены с помощью принципа оптимальности Беллмана.

Опишем формально принцип Беллмана и объясним его смысл.

Ключевым является понятие управляемого объекта, к которому применяется принцип Беллмана.

Пусть имеется изменяющийся во времени объект, на который осуществляется внешнее воздействие u(t) или управление, а x(t) – описание этого объекта в момент времени t.

Если при известном управлении до момента t1, зная описание x(t) в момент времени t , можно однозначно определить его значение x(t) для любого t > t1 , то такое описание называют полным.

Полное описание называют состоянием, множество возможных состояний – пространством состояний.

Сам объект, допускающий возможность полного описания, называют динамической системой.

Будем рассматривать только дискретные моменты времени и в эти моменты управлять системой.

Каждому переходу из состояния xk в следующее состояние ставится в соответствие функция затрат, зависящая от состояния xk , момента времени и применяемого управления.

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

Итак, на каждом шаге мы вносим плату за выбранное управление, далее плата, внесенная на каждом шаге, суммируется и подводится итог.

Мы желаем таким образом управлять объектом, чтобы общая сумма затрат была минимальной.

Это и есть общая постановка задачи динамического программирования или управления динамической системой.

Иными словами, нам нужна программа действий на каждом шаге, позволяющий минимизировать затраты.

Общий принцип формулируется так: вне зависимости от того, каким образом управляемый процесс на шаге k попал в состояние xk , далее надо применять управление, оптимальное для этого состояния в завершающем (N − k)-шаговом процессе с учетом оптимального продолжения.

Это одна из возможных формулировок принципа Беллмана в форме достаточного условия.

Пусть Yk – множество состояний, из которых (при использовании допустимых управлений) можно ровно за k шагов попасть в одно из состояний финального множества X N.

Можно считать, что Y0 = X N.

Возьмем произвольное xN −k ∈Yk и обозначим через Sk (xN −k ) функцию, описывающую зависимость оптимальных затрат от состояния xN −k за k последних шагов, переводящих систему из xN −k в X N.

Такие функции называют функциями Беллмана.

Поскольку для состояний xN −1 из множества Y1 переход в XN происходит за один шаг, то функция оптимальных затрат S1(xN −1) может быть записана следующим образом:

Второе ограничение необходимо для того, чтобы гарантировать достижение заданного финального множества X N.

Значение uN , при котором достигается минимум в этом соотношении, обозначим через u*N( xN-1).

Несложно понять (сделайте это!), что функция оптимальных затрат Sk +1(xN −k −1) каждой следующей задачи рекуррентно выражается через предыдущую Sk (xN −k )

u*N −k (xN −k – 1) – управление, при котором достигается минимум затрат в (2).

Выражение u*k (xk-1) − определяет для каждого момента времени оптимальные правила управления в виде функций от текущего состояния динамического процесса, задают закон оптимального управления в форме оптимального регулятора по состоянию.

Оптимальное начальное состояние x*0 можно получить из решения следующей задачи:

Систему (1)-(3) называют рекуррентными уравнениями Беллмана.

Значения оптимального управления в явном виде можно последовательно определить следующим образом:

Стартуем из начального состояния x0.

Источник