Характеристика методов динамического программирования
Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же первое и второе одновременно, характеризуются нелинейными зависимостями. Примерами нелинейных зависимостей могут 233
быть: зависимость экономической эффективности деятельности предприятия от масштабов производства; зависимость затрат на производство партии деталей от количества изделий в партии и др. Использование в экономическом анализе методов динамического программирования рассмотрим на следующем примере. Задача. Инвестор планирует вложить 7 тыс. грн в акции трех предприятий. Стоимость акций предприятий: 1-го — 3 тыс. грн, 2-го — 2 тыс. грн, 3-го — 1 тыс. грн. Прибыль от акций предприятий: 1-го — 7 тыс. грн, 2-го — 5 тыс. грн, 3-го — 2 тыс. грн. Необходимо найти такой план вложения средств, при котором прибыль будет максимальной. Решение. Составим математическую модель задачи: Xj (j = 1,3) — количество акций j-го предприятия; F(X) = 7X1 + 5X2 + 2X3 → max — сумма прибыли. Система ограничений: 3X1 + 2X2 + X3 ⇐ 7; Xj ⇒ 0, j = 1,3; Xj∈ Z, j = 1,3. Решение задачи разбивается на три этапа, на каждом из которых соответственно определяется максимальная прибыль от вложения средств в акции 1-го предприятия; 1-го и 2-го, а затем 1-го, 2-го и 3-го предприятий. Для этого используем следующее рекуррентное соотношение: fn(Z) = max[XnCn + fn (Z) – f(Z – XnAn)], 0 ⇐ Xn ⇐ [Z/An], где fn(Z) — максимальная прибыль от вложения Z средств в акции 1-го, 2-го,…, n-го предприятий; Xn — количество акций n-го предприятия; Cn — прибыль от акций n-го предприятия; An — стоимость акций n-го предприятия; fn–1(Z – XnAn) — максимальная прибыль от вложения Z – XnAn средств в акции 1-го, 2-го,…, n–1-го предприятий. Первый этап. Рассчитаем значения функции f1(Z) для разных значений Z: f1(Z) = max 7X1, 0 ⇐ X1 ⇐ [Z/3]. Результаты расчетов приведены в табл. 39.
Второй этап. Рассчитаем значения функции f2(Z) для разных значений Z: f2(Z) = max[5X2 + f1(Z –2X2)], 0 ⇐ X2 ⇐ [Z/2]. Результаты расчетов приведены в табл. 40. Таблица 40 Результаты расчетов функции f2(Z) Z X2 f(Z) 0 0 0 1 0 0 2 1 5 3 0 7 4 2 10 5 1 12 6 3 15 7 2 17
Третий этап. Поскольку данный этап является завершающим, рассчитаем значения функции f3(Z) для значения Z = 7: f3(7) = max[2X3 + f2(7 – Х3)], 0 ⇐ X3 ⇐ [7/1]. В табл. 41 представлены значения функции f3(7) при разных значениях X3. Необходимо выбрать максимальное значение f3(7) и таким образом определить X3. Таблица 41 Выбор величины Х3 при известных значениях f3(7) X3 f3(7) 0 17 1 17 2 16 3 16 4 15 5 15 6 12 7 14
235
Максимальная прибыль от вложения 7 тыс. грн в акции 1–3-го предприятий будет равна 17 тыс. грн, при этом возможны два значения X3. Это значит, что существует два оптимальных плана вложения средств. Результаты расчетов каждого этапа приведены в обобщающей таблице (табл. 42). Таблица 42 Обобщающая таблица расчетов Z 0 1 2 3 4 5 6 7 f1(Z) 0 0 0 7 7 7 14 14 X1 0 0 0 1 1 1 2 2 f2(Z) 0 0 5 7 10 12 15 17 X2 0 0 1 0 2 1 3 2 17 0 или 1 f3(Z) X3
Найдем оптимальный план вложения средств при X3 = 0. При этом 7 – 0⋅3 = 7 тыс. грн вкладываются в акции 1-го и 2-го предприятий; f2(7) = 17 при X2 = 2, тогда 7 – 2⋅2 = 3 тыс. грн вкладываются в акции 1-го предприятия; f1(3) = 7 при X1 = 1. Таким образом, получаем следующий оптимальный план вложения средств: 1 акция 1-го предприятия; 2 акции 2-го предприятия; 3 акции 3-го предприятия. Найдем оптимальный план вложения средств при X3 = 1. При этом 7 – 1 = 6 тыс. грн вкладываются в акции 1-го и 2-го предприятий; f2(6) = = 15 при X2 = 3, тогда 6 – 3⋅2 = 0 тыс. грн вкладываются в акции 1-го предприятия; f1(0) = 0 при X1 = 0. Таким образом, получаем следующий оптимальный план вложения средств: 0 акций 1-го предприятия; 1 акция 2-го предприятия; 2 акции 3-го предприятия. Таким образом, методы динамического программирования позволяют выбрать из множества альтернативных решений оптимальное, которое обеспечивает максимальное достижение поставленной цели. 236
Методы динамического программирования более широко рассматриваются в курсе “Исследование операций и методы оптимизации”.
Ви переглядаєте статтю (реферат): «Характеристика методов динамического программирования» з дисципліни «Сучасний економічний аналіз і прогнозування (мікро-та макрорівні)»
