Суть методов динамического программирования

1. Задача распределения инвестиций. Для реконструкции и модернизации производства на четырех предприятиях выделены денежные средства С = 80 ден. ед. По каждому предприятию известен возможный прирост f_i(х) (i = 1, 4) выпуска продукции в зависимости от выделенной суммы.
2. Метод прогонки.
3. Задача замены оборудования.
4. Задача Джонсона.
5. Задача о рюкзаке.

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

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

Рассмотрим общее описание задачи динамического программирования.
Пусть многошаговый процесс принятия решений разбивается на n шагов. Обозначим через ε⁰ – начальное состояние системы, через ε¹, ε², … εⁿ – состояния системы после первого, второго, n-го шага. В общем случае состояниеε^k – вектор (ε^k₁, …, ε^k_s).
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) u^k = (u^k₁, ..., u^k_r), принимаемых на каждом шаге k и переводящих систему из состояния ε^k-1 = (ε^k-1₁, …, ε^k-1_s) в состояние ε^k = (ε^k₁, …, ε^k_s).
В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе. Например, выпуск продукции любым предприятием – управляемый процесс, так как он определяется изменением состава оборудования, объемом поставок сырья, величиной финансирования и т. д. Совокупность решений, принимаемых в начале года, планируемого периода, по обеспечению предприятия сырьем, замене оборудования, размерам финансирования и т. д. является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции. Следовательно, выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов. Необходимо предусмотреть мероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т. е. по периодам времени. Последнее хотя и приводит к уменьшению первоначального объема выпускаемой продукции, но обеспечивает в дальнейшем возможность расширения производства. Таким образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов (шагов), на каждом из которых осуществляется влияние на его развитие.
Началом этапа (шага) управляемого процесса считается момент принятия решения (о величине капитальных вложений, о замене оборудования определенного вида и т. д.). Под этапом обычно понимают хозяйственный год.
Обычно на управление на каждом шаге u^k накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называются допустимыми.
Предполагая, что показатель эффективности k-го шага процесса зависит от начального состояния на этом шаге ^k-1и от управления на этом шаге u^k, получим целевую функцию всего многошагового процесса в виде:
.

Сформулируем теперь задачу динамического программирования: «Определить совокупность допустимых управлений (u¹, …, uⁿ), переводящих систему из начального состояния ε⁰ в конечное состояние εⁿ и максимизирующих или минимизирующих показатель эффективности F».
Управление, при котором достигается максимум (минимум) функции F называется оптимальным управлением u^* = (u^1*,…, u^n*).
Если переменные управления u^k принимают дискретные значения, то модель ДП называется дискретной. Если переменные u^k изменяются непрерывно, то модель ДП называется непрерывной.
В зависимости от числа параметров состояния s и числа управляющих переменных r различают одномерные и многомерные задачи ДП.
Число шагов в задаче может быть конечным или бесконечным.

Прикладные задачи динамического программирования

1. задача коммивояжера;
2. задача о планировании строительства объектов.

Модели динамического программирования

Динамическое программирования

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

• прибыль F k (Х) не зависит от вложения средств в другие предприятия;
• прибыль от каждого предприятия выражается в одних и тех же единицах;
• суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.

Решение находим с помощью сервиса распределение средств между предприятиями
Введём обозначения:
Х - количество средств, выделенных каждому предприятию.
Суммарная прибыль равна: Z =∑ F k (Х).
Переменные удовлетворяют ограничениям:
∑Х _k =5
Х _k ≥0
Требуется найти переменные Х1,Х2,Х3,Х4, удовлетворяющие системе уравнений и обращающие в максимум функцию.
Таблица

Используя уравнение Беллмана рассмотрим алгоритм решения задачи.
Если Х₁=0, то S ₁ =5, то прибыль, полученная от четырёх предприятий при этих условиях, будет равна: Z₁ = 0+19=19.
Если Х₁=1, то S 2=4, то прибыль при этих условиях равна: Z ₁ = 8+16=24.
Если Х₁=2, то S ₂ =3, то прибыль при этих условиях равна: Z ₃ = 10+13=23
Если Х₁=3, то S ₂ =2, то прибыль при этих условиях равна:
Z ₄ = 11+10=2110+13=23
Если Х₁=4, то S ₂ =1, то прибыль при этих условиях равна: Z ₅ = 12+16=28
Если Х₁=5, то S ₂ =0, то прибыль при этих условиях равна: Z ₅ =18+0=18
Сравнивая полученные числа, получим: Z ₁ = 24, при Х1=1.
Максимум суммарной прибыли Zmaх = 24 ус/ед. при условии, что:
- первому предприятию выделено 1 ус/ед.;
- второму предприятию 2 ус/ед.;
- третьему предприятию 1 ус/ед.;
- четвёртому предприятию 1 ус/ед.

I этап. Условная оптимизация.
1-ый шаг. k = 4.

Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 4-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 1-го шага имеем F*₄(e⁰ = 5) = 24. То есть максимальный доход всей системы при количестве средств e⁰ = 5 равен 24.
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*₁(e⁰ = 5) = 1
При этом остаток средств составит:
e¹ = e⁰ - u¹
e¹ = 5 - 1 = 4
Из таблицы 2-го шага имеем F*₃(e¹ = 4) = 16. То есть максимальный доход всей системы при количестве средств e¹ = 4 равен 16.
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*₂(e¹ = 4) = 2
При этом остаток средств составит:
e² = e¹ - u²
e² = 4 - 2 = 2
Из таблицы 3-го шага имеем F*₂(e² = 2) = 7. То есть максимальный доход всей системы при количестве средств e² = 2 равен 7.
Из этой же таблицы получаем, что 3-му предприятию следует выделить u*₃(e² = 2) = 1
При этом остаток средств составит:
e³ = e² - u³
e³ = 2 - 1 = 1
Последнему предприятию достается 1.
Итак, инвестиции в размере 5 необходимо распределить следующим образом:
1-му предприятию выделить 1,
2-му предприятию выделить 2,
3-му предприятию выделить 1,
4-му предприятию выделить 1.
Что обеспечит максимальный доход, равный 24.

Перейти к онлайн решению своей задачи

Типовые задачи по динамическому программированию

Задание №1. Планируется распределение начальной суммы средств e⁰ между n предприятиями П₁, П₂, ..., П_n. Выделение предприятию П_k средств u^k приносит доход f_k(u^k). Определить, какое количество средств нужно выделить каждому предприятию, чтобы обеспечить максимальный суммарный доход

Задание №2. Совет директоров фирмы рассматривает предложения по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырёх предприятиях, принадлежащих фирме. Для модернизации предприятия совет директоров инвестировал средства в объёме e⁰ млн. р. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причём на одно предприятие можно осуществить только одну инвестицию.

Задание №3. Найти оптимальный план распределения кредитов и прибыль.

Задание №4. Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.

Задание №5. В таблице приведены значения возможного прироста выпуска продукции на четырех фирмах, в зависимости от выделенной на модернизацию производства суммы x. Распределить между фирмами 1 млн. руб. чтобы общий прирост выпуска продукции был максимальным. Для упрощения вычислений значения х принимать кратными 200 тыс. руб.

Видеоинструкция