Динамическое программирование (ДП) - метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Начало развития ДП относится к 50-м годам XX в. Оно связано с именем Р.Беллмана.
Если модели линейного программирования можно использовать в экономике для принятия крупномасштабных плановых решений в сложных ситуациях, то модели ДП применяются при решении задач значительно меньшего масштаба, например, при разработке правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа; при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; при распределении дефицитных капитальных вложений между возможными новыми направлениями их использования; при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены; при разработке долгосрочных правил замены выбывающих из эксплуатации основных фондов и т. п.
В реально функционирующих больших экономических системах еженедельно требуется принимать микроэкономические решения. Модели ДП ценны тем, что позволяют на основе стандартного подхода с использованием при минимальном вмешательстве человека принимать такие решения. И если каждое взятое в отдельности такое решение малосущественно, то в совокупности эти решения могут оказать большое влияние на прибыль.
Рассматривается управляемый процесс, например, экономический процесс распределения средств между предприятиями, использования ресурсов в течение ряда лет, замены оборудования, пополнения запасов и т. п.
В результате управления система (объект управления) S переводится из начального состояния (So), в конечное состояние (Sn). Предположим, что управление можно разбить на n-шагов, т.е. решение принимается последовательно на каждом шаге, а управление, переводящее систему S из начального состояния в конечное, представляет собой n-шаговый процесс управления.
На каждом шаге применяется некоторое управленческое решение x k , при этом множество х-{х1,х2,...,хn) называется управлением. Метод динамического программирования опирается на условие отсутствия последействия и условие аддитивности целевой функции.
Условие отсутствия последействия . Состояние S k , в которое перешла система за один K- ый шаг, зависит только от состояния S k -1 и выбранного управления x k , и не зависит от того, каким образом система пришла в состояние Sk 1:
S k (Sk 1, xk )
Также учитывается, что выбор управления на k-ом шаге зависит только от состояния системы к этому шагу:
x k (S k -1 )
На каждом шаге управления x k зависит от конечного числа управляющих переменных. Состояние системы на каждом шаге зависит от конечного числа параметров.
Принцип оптимальности. Каково бы ни было состояние s системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Основное требование, при котором принцип верен - процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Таким образом, решение на каждом шаге оказывается наилучшим с точки зрения управления в целом.
Рекуррентные соотношения Беллмана.
Нахождение оптимального решения управляемого процесса можно произвести на основе рекуррентных соотношений Беллмана. Пусть f k (S k -1 ,x k) - показатель эффективности k – ого шага при всевозможных управлениях . Выделяют обратную и прямую схемы Беллмана.
Таблица 6 . Значения прибыли предприятий
|
Объем выделенных ресурсов |
Прибыль от проектов |
||||
В данной таблице 6. представлены значения прибыли (F;(Q)),которые были получены путем решения производственно-экономической задачи каждого инвестируемого предприятия. Эти значения изменяются в зависимости от объемов вложенных инвестиции.
Таблица 7. Данные о дополнительном доходе предприятий
|
Выделяемые ресурсы | |||||
В данной таблице 7. представлены данные о дополнительном доходе, которое предприятие-инвестор получит от каждого инвестируемого предприятия в зависимости от объема вложенных инвестиций.
В таблице 8. рассчитаны показатели эффективности (Zi(Q)) инвестируемых предприятий, которые были получены с помощью прямой схемы Беллмана.
Таблица 8.Показатели эффективности
|
Выделяемые ресурсы |
Дополнительный доход от проектов |
||||
Рассмотрим нахождение каждого из показателей эффективности:
Для показателей эффективности одного предприятия Zi(0) = pi(0)=0
Z1(200’000)= p1(200"000)=7068135,2
Z1(400"000)= p1(400"000)=2567391,9
Z1(600"000)=p1(600"000)=2216151,6
Z1(800"000)=p1(800"000)=1222330,8
Z1(l"OOO"OOO)= p1(l"000"000)=122233,09 Для показателей эффективности двух предприятий .
Z 2 (0)=p 2 (0)=0
Z 2 (200"000)= max{0 + 70 68135,2; 94 07519,6 + 0 )=9407519,6
Z 2 (400"000)= max{0 + 25 67391,9; 94 07519,6 + 70 68135,2 ; 80 92519,9 + 0}=16475654,8
Z 2 (600"000)=max{0 + 22 16151,6; 94 07519,6 +25 67391,9 ; 80 92519,9 +70 68135,2 ; 80 92353,6 + 0)=15160655,1
Z 2 (800"000)= max{0 + 12 2233,08; 94 07519,6 + 22 16151,6; 80 92519,9 + 25 67391,9; 80 92353,6 + 70 68135,2 : 80 92353,6 + 0}=15160488,8
Z 2 (l"000"000)=max{0 + 12 22330,9; 94 07519,6 + 12 22330,8; 80 92519,9 +22 16151,6; 80 92353,6 + 25 67391,9; 80 92353,6 + 70 68135,2 ; 67 38741,6 + 0}=15160488,8
Для показателей эффективности трех предприятий .
Z 3 (0)= p 3 (0)=0
Z 3 (200"000)= max (0 + 94 07519,6; 507 43194,2 + 0 )=50743194,2
Z 3 (400"000)= max {0 + 8092519,9; 507 43194,2 + 94 07519,6 ; 272 10300,4 + 0}=60150713,8
Z 3 (600"000)= max {0 + 8092353,6; 507 43194,2 + 8092519,9 ; 272 10300,4+94 07519,6; 272 10300,4 + 0}=58835714,1
Z 3 (800"000)= max {0 + 8092353,6:507 43194,2 + 8092353,6 ; 272 10300,4 +9407519,6; 272 10300,4 + 8092519,9; 272 10300,5 + 0}= 58835547,8
Z 3 (l "000"000)= max {0+6738741,6; 507 43194,2 + 8092353,6 ; 272 10300,4 + 8092353,6; 272 10300,4 + 8092519,9; 272 10300,5 + 94 07519,6; 27210300,4+0}=58835547,8
Для показателей эффективности четырех предприятий .
Z 4 (0)=p 4 (0)=0
Z 4 (200"000)= max (0 + 507 43194,2 ; 118 73132,7 + 0}= 507 43194,2
Z 4 (400"000)= max {0 + 27210300,4; 118 73132,7 + 507 43194,2 ; 84 75336,3+0}=62616326,9
Z 4 (600"000)= max {0 + 27210300,4; 118 73132,7 + 27210300,4; 84 75336,3 + 507 43194,2 ; 84 75336,3 + 0}= 59218530,5
Z 4 (800"000)= max {0 + 27 210 300,5; 11 873 132,7 + 27 210 300,4; 8 475 336,3+27 210 300,4; 8 475 336,3 + 50 743 194,2 ; 71 37734,9 + 0}=59218530,5
Z 4 (l "000"000)= max {0 + 27210300,4; 118 73132,7 + 27210300,5; 84 75336,3+ 27210300,4; 84 75336,3 + 27210300,4; 71 37734,9 + 507 43194,2 ; 62 83185,8+0}=57880929,1
Для показателей эффективности пяти предприятий .
Z 5 (0)=p 5 (0)=0
Z 5 (200"000)= max (0 + 11873132,7 ; 103 07000,5 + 0}= 11873132,7
Z 5 (400"000)= max (0 + 8475336,3; 103 07000,5 + 11873132 ,7; 77 36093,1+ 0}=22180133,2
Z 5 (600"000)= max (0 + 8 475 336,3; 10 307 000,5 + 8 475 336,3; 7 736 093,1+11 873 132,7 ; 7 736 093,2 + 0}=19609225,8
Z 5 (800"000)= max {0 + 7137734,9; 10 307000,5 + 8 475336,3; 77 36093,1 + 8475336,3; 77 36093,2 + 11873132,7 ; 72 41299,8 + 0}= 19609225,9
Z 5 (l "000000)= max {0 + 6283185,8; 103 07000,5 + 7137734,9; 77 36093,1 + 8475336,3;7736093,2+ 8475336,3; 72 41299,8+11873132,7 ; 71 67372,4+, 0}=19714432,5
После получения последнего показателя эффективности можно получить решение задачи:
Z 5 (1"000"000)= 103 07000,5 + 59218530,5 = 69525531,00 Q 1 = 20 000 000p.
Z 4 (800"000)= 118 73132,7 + 58835714,1 = 70708846,80 Q 2 = 20 000 000p.
Z 3 (600"000)= 507 43194,2 + 16475654,8 = 67218849,00 Q 3 = 20 000 000 p.
Z 2 (400"000)= 94 07519,6 + 7068135,2 = 164756548 Q 4 = 20 000 000p.
Z1(200000) = p!(200"000)= 70 68135,2 Q 5 = 20 000 000р.
Для получения максимальной прибыли предприятием- инвестором выделенные ресурсы (денежные средства в размере 100 000 000 рублей) должны быть распределены следующим образом - каждому инвестируемому предприятию следует выделить по 20 000 000 рублей. При этом максимальный объединенный показатель эффективности будет равен 70 708 846,80 рублей.
Назначение сервиса . Данный сервис предназначен для решения задачи оптимального распределения инвестиций в онлайн режиме. Результаты вычислений оформляются в отчете формата Word (см. пример оформления).Такого рода задачи основаны на функции Беллмана и при решении используется метод обратной прогонки (см. Типовые задания). Также можно воспользоваться сервисом Процедура прямой прогонки .
Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций f(x) и g(x) , задача решается через этот калькулятор .
Пример №1 . Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.
| f1 | f2 | f3 | x i |
| 40 | 30 | 35 | 0 |
| 90 | 110 | 95 | 1 |
| 395 | 385 | 270 | 2 |
| 440 | 470 | 630 | 3 |
| 620 | 740 | 700 | 4 |
I этап. Условная оптимизация
.
1-ый шаг. k = 3.
| e 2 | u 3 | e 3 = e 2 - u 3 | f 3 (u 3) | F* 3 (e 3) | u 3 (e 3) |
| 1 | 0 | 1 | 35 | ||
| 1 | 0 | 95 | 95 | 1 | |
| 2 | 0 | 2 | 35 | ||
| 1 | 1 | 95 | |||
| 2 | 0 | 270 | 270 | 2 | |
| 3 | 0 | 3 | 35 | ||
| 1 | 2 | 95 | |||
| 2 | 1 | 270 | |||
| 3 | 0 | 630 | 630 | 3 | |
| 4 | 0 | 4 | 35 | ||
| 1 | 3 | 95 | |||
| 2 | 2 | 270 | |||
| 3 | 1 | 630 | |||
| 4 | 0 | 700 | 700 | 4 |
2-ый шаг. k = 2.
| e 1 | u 2 | e 2 = e 1 - u 2 | f 2 (u 2) | F* 2 (e 1) | F 1 (u 2 ,e 1) | F* 2 (e 2) | u 2 (e 2) |
| 1 | 0 | 1 | 30 | 95 | 125 | 125 | 0 |
| 1 | 0 | 110 | 0 | 110 | |||
| 2 | 0 | 2 | 30 | 270 | 300 | ||
| 1 | 1 | 110 | 95 | 205 | |||
| 2 | 0 | 385 | 0 | 385 | 385 | 2 | |
| 3 | 0 | 3 | 30 | 630 | 660 | 660 | 0 |
| 1 | 2 | 110 | 270 | 380 | |||
| 2 | 1 | 385 | 95 | 480 | |||
| 3 | 0 | 470 | 0 | 470 | |||
| 4 | 0 | 4 | 30 | 700 | 730 | ||
| 1 | 3 | 110 | 630 | 740 | 740 | 1 | |
| 2 | 2 | 385 | 270 | 655 | |||
| 3 | 1 | 470 | 95 | 565 | |||
| 4 | 0 | 740 | 0 | 740 |
3-ый шаг. k = 1.
| e 0 | u 1 | e 1 = e 0 - u 1 | f 1 (u 1) | F* 1 (e 0) | F 0 (u 1 ,e 0) | F* 1 (e 1) | u 1 (e 1) |
| 1 | 0 | 1 | 40 | 125 | 165 | 165 | 0 |
| 1 | 0 | 90 | 0 | 90 | |||
| 2 | 0 | 2 | 40 | 385 | 425 | 425 | 0 |
| 1 | 1 | 90 | 125 | 215 | |||
| 2 | 0 | 395 | 0 | 395 | |||
| 3 | 0 | 3 | 40 | 660 | 700 | 700 | 0 |
| 1 | 2 | 90 | 385 | 475 | |||
| 2 | 1 | 395 | 125 | 520 | |||
| 3 | 0 | 440 | 0 | 440 | |||
| 4 | 0 | 4 | 40 | 740 | 780 | 780 | 0 |
| 1 | 3 | 90 | 660 | 750 | |||
| 2 | 2 | 395 | 385 | 780 | |||
| 3 | 1 | 440 | 125 | 565 | |||
| 4 | 0 | 620 | 0 | 620 |
Примечание : Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация .
Из таблицы 3-го шага имеем F* 1 (e 0 = 4 млн.руб.) = 780 тыс.руб., то есть максимальная прибыль от инвестирования e 0 = 4 млн.руб. равна 780 тыс.руб.
Из этой же таблицы получаем, что первому предприятию следует выделить u* 1 (e 0 = 4 млн.руб.) = 0 млн.руб.
При этом остаток средств составит: e 1 = e 0 - u 1 , e 1 = 4 - 0 = 4 млн.руб.
Из таблицы 2-го шага имеем F* 2 (e 1 = 4 млн.руб.) = 740 тыс.руб., т.е. максимальная прибыль при e 1 = 4 млн.руб. равна 740 тыс.руб.
Из этой же таблицы получаем, что второму предприятию следует выделить u* 2 (e 1 = 4 млн.руб.) = 1 млн.руб.
При этом остаток средств составит: e 2 = e 1 - u 2 , e 2 = 4 - 1 = 3 млн.руб.
Последнему предприятию достается 3 млн.руб. Итак, инвестиции в размере 4 млн.руб. необходимо распределить следующим образом: первому предприятию ничего не выделять, второму предприятию выделить 1 млн.руб., третьему предприятию выделить 3 млн.руб., что обеспечит максимальную прибыль, равную 780 тыс.руб.
Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.
Динамическое программирование (ДП) представляет собой математический аппарат, разработанный с целью повышения эффективности вычислений при решении некоторого класса задач математического программирования путем их разложения (декомпозиции) на относительно небольшие и, следовательно, менее сложные подзадачи. Характерным для динамического программирования является подход к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа.
Фундаментальным принципом, положенным в основу теории ДП, является принцип оптимальности. По существу, он определяет порядок поэтапного решения допускающей декомпозицию задачи (это более приемлемый путь, чем непосредственное решение задачи в исходной постановке) с помощью рекуррентных вычислительных процедур.
Основные положения динамического программирования вместе с непривычными математическими обозначениями часто порождают трудности при изучении этого раздела математического программирования. В особенности это относится к тем, кто впервые знакомится с предметом. Однако опыт показывает, что систематическое обращение к задачам и методам ДП, требующее определенной настойчивости, в конечном счете, приводит начинающего к полному пониманию вначале неясных положений. Когда это происходит, динамическое программирование начинает казаться удивительно простой и стройной теорией.
Применим метод динамического программирования для распределения капиталовложений между четырьмя мероприятиями. Общая сумма средств инвестируемых в развитие составляет не более десяти миллионов гривен. На основе технико-экономических расчетов установлено, что в результате реконструкции в зависимости от количества затраченных средств, мероприятия будут иметь производительность, приведенную в таблице 2.5. Необходимо определить оптимальное распределение средств между мероприятиями, обеспечивающее максимальное увеличение производительности предприятия. Таким образом, в этой оптимизационной задаче используется критерий - суммарная производительность мероприятий.
Таблица 2.5 - Данные для решения задачи
|
№ мероприятия |
Средства, вкладываемые в развитие |
||||
|
Производительность в результате развития (тн) |
|||||
Прямой и, по-видимому, чрезмерно упрощенный способ решения сформулированной задачи заключается в использовании процедуры полного перебора. Задача имеет 4 х 5 = 20 возможных решения, причем некоторые из них не являются допустимыми, так как предполагают ассигнование свыше 10 млн. грн. В процессе полного перебора вычисляются суммарные затраты, ассоциированные с каждым из 20 возможных решений. Если величина затрат не превышает объема авансированных средств, следует вычислить соответствующий суммарный доход. Оптимальным будет допустимое решение, обеспечивающее максимум суммарного дохода.
Отметим следующие недостатки процедуры полного перебора.
- 1. Каждая комбинация проектов определяет некоторое решение задачи в целом, откуда следует, что перебор всех возможных комбинаций в задачах средней и большой размерности может быть связан с чрезмерно большим объемом вычислений.
- 2. Отсутствует априорная информация о решениях, которые не являются допустимыми, что снижает эффективность вычислительной схемы полного перебора.
- 3. Информация, полученная в результате анализа некоторых комбинаций проектов, в дальнейшем не используется для выявления и исключения неоптимальных комбинаций.
Применение методов ДП позволяет устранить все перечисленные недостатки.
Пусть х 1 , х 2 , х 3 , х 4 - капиталовложения в развитие соответственно первого, второго, третьего, четвертого мероприятия, 0 x i 10000000, i = . Обозначим f 1 (x), f 2 (x), f 3 (x), f 4 (x) - функции изменения производительности первого, второго, третьего, четвертого мероприятия при вложении в их развитие х млн. грн. Этим функциям соответствуют строки 1, 2, 3, 4 в таблице 2.5.
Определим максимум функции цели
F (x 1 , х 2 , х 3 , х 4) = f 1 (x) + f 2 (x) + f 3 (x) + f 4 (x).
При этом на капиталовложения х1, х2, х3, х4 наложены ограничения
х 1 + х 2 + х 3 + х 4 = А,
В основе метода динамического программирования, используемого для решения поставленной задачи, лежит принцип оптимальности.
Согласно этому принципу, выбрав некоторое начальное распределение ресурсов, выполняем многошаговую оптимизацию, причем на ближайшем шаге выбираем такое распределение ресурсов, чтобы оно в совокупности с оптимальным распределением на всех последующих шагах приводило к максимальному выигрышу на всех оставшихся шагах, включая данный.
Выделим в нашей задаче 3 шага:
- -- А млн. грн. вкладываются в первое, второе мероприятия одновременно;
- -- А млн. грн. вкладываются в первое, второе, третье мероприятия вместе;
А млн. грн. вкладываются в четыре мероприятия одновременно;
Обозначим: F 1,2 (A), F 1,2,3 (A), F 1,2,3,4 (A) -- соответственно оптимальные распределения средств для первого, второго, третьего шагов.
Алгоритм метода динамического программирования состоит из двух этапов. На первом этапе выполняется условная оптимизация, заключающаяся в том, что для каждого из трех шагов находят условный оптимальный выигрыш F 1,2 (A), F 1,2,3 (A), F 1,2,3,4 (A) для. На втором этапе выполняется безусловная оптимизация. Используя результаты первого этапа, находят величины капиталовложений в развитие мероприятий х 1 , х 2 , х 3 , х 4 обеспечивающие максимальную производительность группы мероприятий.
Первый этап включает следующие шаги:
1) Вычисление максимума критерия оптимизации для различных значений капиталовложений х = 0, 2500000, 5000000, 7500000, 10000000, которые используются только для мероприятий 1 и 2. Расчет ведется по формуле (2.4).
Результаты расчета представлены в таблице 2.6.
Таблица 2.6 - Результаты расчетов на первом этапе
Например, для того, чтобы определить F 1,2 (5000000), надо вычислить
f 1 (5000000) + f 2 (0) = 700 + 5000 = 5700;
f 1 (2500000) + f 2 (2500000) = 600 + 6000 = 6600;
f 1 (0) + f 2 (5000000) = 500 + 7000 = 7500.
Остальные F l,2 (х) получаются как наибольшее значение каждой диагонали в таблице (эти значения в таблице подчеркнуты):
F 2 (0) = 5500; F 2 (2500000) = max (5600, 6500) = 6500;
F 2 (5000000) = max (5700, 6600, 7500) = 7500;
F 2 (7500000) = max (5800, 6700, 7600, 9000) = 9000;
F 2 (10000000) = max (5900, 6800, 7700, 9100, 1500) = 9100;
2) Вычисление максимума критерия оптимизации для различных значений капиталовложений х =0, 2500000, 5000000, 7500000, 10000000, которые используются только для мероприятий 1,2 и 3.
Расчет ведется по формуле (2.5).
Результаты расчетов занесем в таблице 2.7, которая аналогична таблице 2.6, только вместо f 1 (х) в ней указаны значения F 2 (А), a f 2 (А - х) заменена на f 3 (А - х).
Таблица 2.7 - Результаты расчетов на втором этапе
Значения F 1,2,3 (А) будут следующими:
F 1,2,3 (0) = 8600; F 1,2,3 (2500000) = 9600; F 1,2,3 (5000000) = 10600;
F 1,2,3 (7500000) = 12100; F 1,2,3 (10000000) = 12200.
3) Вычисление максимума критерия оптимизации для различных значений капиталовложений х =0, 2500000, 5000000, 7500000, 10000000, которые используются для мероприятий 1,2, 3, 4.
Расчет ведется по формуле (2.6).
Результаты расчетов занесем в таблице 2.8.
Таблица 2.8 - Результаты расчетов на третьем этапе
Значения F 1,2,3,4 (А) будут следующими:
F 1,2,3,4 (0) = 9300; F 1,2,3,4 (2500000) = 10300; F 1,2,3,4 (5000000) = 11300;
F 1,2,3,4 (7500000) = 12800; F 1,2,3,4 (10000000) = 12900.
На этом первый этап решения задачи динамического программирования заканчивается.
Перейдем ко второму этапу решения задачи динамического программирования - безусловной оптимизации. На этом этапе используются таблицы 2.6, 2.7, 2.8. Определим оптимальные капиталовложения в развитие предприятий для А = 0, 2500000, 5000000, 7500000, 10000000. Для этого выполним следующие расчеты:
1) Пусть объем капиталовложений, выделенный на развитие предприятий, составляет А = 10000000 грн.
Определим объем капиталовложений на развитие четвертого мероприятия. Для этого используем таблицу 2.8. Выберем на ней диагональ, соответствующую А = 10000000 - это значения 12900, 12900, 11500, 10550, 9600. Из этих чисел возьмем максимальное F 1,2,3,4 (10000000) = 12900 т. Отмечаем столбец, в котором стоит эта величина. Далее определяем в отмеченном столбце объем капиталовложений в четвертое мероприятие х 4 = 2500000.
На развитие первого, второго и третьего мероприятий остается
А = 10000000 - х 4 = 2500000 грн.
2) Определим объем капиталовложений, выделенный на развитие третьего мероприятия.
Для этого используем таблицу 2.7. Выберем в этой таблице диагональ, соответствующую А = 7500000 - это значения12100, 10700, 9800, 8900. Отмечаем столбец, в котором стоит максимальная (подчеркнутая) величина производительности F 1,2,3 (7500000) = 12100 т. Определяем значение х 3 = 0 грн. в отмеченном столбце.
Третье мероприятие мы не будем финансировать.
3) Определим объем капиталовложений на развитие второго мероприятия. Для этого используем таблицу 2.6. Выберем на ней диагональ, соответствующую А = 75000000 - это 5800, 6700, 7600, 9000. Из этих чисел возьмем максимальное F 1,2 (75000000) = 9000 т. Отмечаем столбец, в котором стоит эта величина. Далее определяем в отмеченном столбце объем капиталовложений во второе мероприятие х 2 = 7500000.
Таким образом, для капиталовложений объемом А = 10000000 грн. оптимальным является вложение в развитие четвертого мероприятия 2500000 грн, второго - 7500000 грн., в развитие первого и третьего мероприятия средства не выделяются. При этом суммарная производительность четырех предприятий составит 12900 т.
Повторив расчеты второго этапа решения для А = 3, 2, 1, 0, определим оптимальные капиталовложения в развитие мероприятий. Результаты будут следующими:
F 1,2,3,4 (7500000) = 12800; x 1 = 0; х 2 = 7500000; х 3 = 0; х 4 = 0
F 1,2,3,4 (5000000) = 11300; x 1 = 0; х 2 = 5000000; х 3 = 0; х 4 = 0
F 1,2,3,4 (2500000) = 10300; x 1 = 0; х 2 = 250000; х 3 = 0; х 4 = 0
F 1,2,3,4 (0) = 9300; x 1 = 0; х 2 = 0; х 3 = 0; х 4 = 0
2.1. задача о распределении инвестиций
"Условие задачи. В производственное объединение входят три предприятия Пі, ТІ2, Щ. Руководство объединения решило инвестировать в свои предприятия 5 условных денежных единиц (усл. ден. ед.) в общей сумме. Проведенные маркетинговые исследования прогнозируют величину ожидаемой прибыли каждого из предприятий в зависимости от объема инвестированных средств. Эти данные представлены в приведенной ниже таблице. Считается, что при нулевых инвестициях ожидается нулевая прибыль.
Требуется найти такое распределение инвестиций между предприятиями, которое обеспечило бы максимум суммарной ожидаемой прибыли.
Решение. В данной задаче управляемой системой является рассматриваемое производственное объединение, многошаговым процессом - процесс выделения средств предприятиям. Отметим, что структура многошагового процесса в данной задаче определяется не течением времени, а порядком планирования распределения инвестиций. Экономический эффект представляет суммарная величина ожидаемой прибыли, и при этом задача решается на поиск максимума.
Для решения поставленной задачи построим прежде всего ее экономико-математическую модель в соответствии с пп. 1-5 разд. 1.7 гл. 1.
Число шагов./V в данной задаче следует принять равным 3, соответствующим числу входящих в производственное объединение предприятий: на первом шаге планируется выделение средств предприятию П, на втором шаге - предприятию Я2, на третьем шаге - предприятию Щ.
В качестве фазовой переменной х, определяющей состояние системы в ходе процесса распределения инвестиций, примем суммарный объем средств, выделенных предприятиям после каждого шага процесса. Именно, переменная х представляет объем средств, выделенных предприятиям после первого шага процесса (т. е. только предприятию П), Х2 - объем средств, выделенных после второго шага (предприятиям П и Д2), х3 -объем средств, выделенных после третьего шага процесса (всем предприятиям П, Я2 и Яз). Поскольку в начальный момент общая сумма выделенных средств равна 0, то начальное состояние системы характеризуется значением xq = 0. По условию задачи общая сумма инвестируемых средств равна 5 усл. ден. ед., т. е. обязательно выполняется условие хз = 5. Поскольку по смыслу задачи на каждом шаге процесса значения фазовой переменной не убывают, то выполняется ограничение Zj ^ 5. Отметим, что проведенный выбор фазовой переменной с указанным экономическим смыслом не является единственно возможным. Например, в рассматриваемой задаче можно было выбрать в качестве переменной х остаток нераспределенных средств.
В качестве управляющей переменной и примем объем средств, выделяемых предприятиям на каждом из шагов процесса. Именно, переменная щ представляет объем средств, выделяемых предприятию Щ (на 1-м шаге процесса), и2 - объем средств, выделяемых предприятию П2 (на 2-м шаге), из - объем средств, выделяемых предприятию 773 (на 3-м шаге). Будем считать, что средства предприятиям выделяются суммами но целому числу усл. ден. ед.; соответственно все управления принимают только целочисленные значения 0, 1, 2,... .
Функция процесса хі = /і(хі-і,щ), определяющая закон изменения состояния системы, для данной задачи представляется формулой
Хі = Хі-і + Щ
и имеет следующий простой смысл: суммарный объем средств хі, выделенных предприятиям нарастающим итогом после текущего шага с номером г, равен суммарному объему средств выделенных предприятиям после предшествующего шага с номером і - 1 (или, что то же самое, до текущего шага), плюс объем средств щ, выделенных предприятию Щ на текущем шаге.
Функция Zi, определяющая частный экономический эффект на шаге с номером г процесса, зависит только от объема щ инвестированных средств в предприятие Щ, т. е. Zi = Zi(m), и определяется по таблице данных задачи по столбцу, отвечающему этому предприятию. Например, z(2) = 4 (из столбца, отвечающего предприятию Пі), z2(3) = 6, 23 (4) = 9.
На этом действия, предписываемые пп. 1-5 разд. 1.7 гл. 1 выполнены, что означает завершение математической формализации поставленной задачи, т. е. построение соответствующей экономико-математической модели. Заметим, что после проведенной указанным образом формализации основные допущения метода ДП выполняются: отсутствие последействия следует из явных формул для вычисления Хі и Zi, а аддитивность целевой функции
Z = Zi(ui) + Z2 (и2) + 23(м3)
обусловлена самой постановкой задачи.
Тем самым можно непосредственно приступить к расчетам в соответствии с методом ДП. Эти расчеты, как указывалось выше в разд. 1.6 гл. 1, проводятся в три этапа: предварительный этап, этап условной оптимизации и этап безусловной оптимизации. На предварительном этапе и на этапе условной оптимизации результаты расчетов заносятся во вспомогательную и основную таблицы той структуры, которая приведена в разд. 1.7 гл. 1. На этапе безусловной оптимизации строится оптимальное решение задачи с использованием информации, содержащейся в основных таблицах.
Предварительный этап. Данный этап решения задачи проводится в естественном порядке для і = 1, 2,3 и не связан непосредственно с вычислением функций Беллмана Ві(хі). Заполняются только первая строка вспомогательной таблицы и четыре левых столбца основной таблицы.
Вспомогательная таблица заполняется соответственно начальному условию xq = 0 и имеет вид
Заполнение основной таблицы проводится следующим образом. Для заданного единственного допустимого значения xq = 0 выбираем все возможные значения управления щ (оно может принимать все целочисленные значения от 0 до 5 включительно) и заносим их во второй столбец таблицы. По формуле xi - xq + щ (следующей из общей формулы хг = Xi-i + щ при і = 1) проводим расчет соответствующих значений переменной хх и заносим их в третий столбец. Для заполнения четвертого столбца значения ожидаемой прибыли zx берем из столбца таблицы исходных данных задачи, отвечающего предприятию Пі. для щ - 1 по этой таблице zj = 2, для и = 2 по таблице zi - 4 и т. д. Для щ = 0 по условию задачи zi = 0. Получаем следующую основную таблицу:
На этом заполнение левой части основной таблицы завершено, причем таблица имеет только один строчный фрагмент. Переходим к следующему шагу.
На втором шаге в первую строку вспомогательной таблицы внесем все значения переменной х, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Получаем следующую вспомогательную таблицу:
Для заполнения основной таблицы на данном шаге будем, аналогично предшествующему шагу, последовательно выбирать все допустимые значения х, внесенные во вспомогательную таблицу, и проводить соответствующие расчеты. Каждому значению х будет соответствовать свой строчный фрагмент основной таблицы; разделяются соседние строчные фрагменты горизонтальной линией.
Для значения х = 0 выбираем все возможные значения управления U2 (оно может принимать все целочисленные значения от О до 5 включительно) и заносим их во второй столбец таблицы. По
формуле Х2 = Х + U2 (следующей ИЗ общей формулы Xi = Xi-l + щ
при г = 2) проводим расчет соответствующих значений переменной х2 и заносим их в третий столбец. Для заполнения четвертого столбца значения ожидаемой прибыли z2 берем из столбца таблицы исходных данных задачи, отвечающего предприятию П^". для и2 = 1 по этой таблице Z2 = 1, для U2 - 2 по таблице z2 = 2 и т. д. На этом завершается заполнение первого строчного фрагмента основной таблицы, соответствующего х = 0; этот фрагмент имеет следующий вид:
Для следующего допустимого значения xi = 1 строим следующий строчный фрагмент. При этом управление и2 может принимать все целочисленные значения от 0 до 4 включительно (поскольку после выделения предприятию П средств в объеме Х = 1
Аналогично формируются строчные фрагменты таблицы и для х = 2,3,4,5. Ясно, что с увеличением значения Х множество допустимых значений управления U2 сужается, и для Х = 5 допустимым является только одно значение и2 = 0. В результате получаем следующую основную таблицу:
Построенная таблица разделена на 6 строчных фрагментов-столько же, сколько различных значений может принимать переменная xi. Переходим к следующему (последнему) шагу. .
На третьем шаге в первую строку вспомогательной таблицы внесем все значения переменной х2, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Эти значения многократно повто
Онлайн калькуляторы
