Динамическое программирование (ДП) - метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Начало развития ДП относится к 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
Динамическое программирование представляет собой математический аппарат, разработанный для эффективного решения некоторого класса задач математического программирования. Этот класс характеризуется возможностью естественного (а иногда и искусственного) разбиения всей операции на ряд взаимосвязанных этапов. Термин "динамическое" в названии метода возник, видимо, потому что этапы предполагаются разделенными во времени. Однако этапами могут быть элементы операции, никак не связанные друг с другом показателем времени. Тем не менее, метод решения подобных многоэтапных задач применяется один и тот же, и его название стало общепринятым, хотя в некоторых источниках его называют многоэтапным программированием.
Модели динамического программирования могут применяться, например, при разработке правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа; при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; при распределении дефицитных капиталовложений между возможными новыми направлениями их использования; при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены; при разработке долгосрочных правил замены выбывающих из эксплуатации основных фондов и т.д.
Для определения сущности динамического программирования рассмотрим задачу:
Представим себе некоторую операцию О, состоящую из ряда последовательных "шагов" или этапов, например, деятельность отрасли промышленности в течение ряда хозяйственных лет. Пусть число шагов равно m. Выигрыш (эффективность операции) Z за всю операцию складывается из выигрышей на отдельных шагах:
где zi- выигрыш на i-м шаге.
Если Z обладает таким свойством, то его называют аддитивным критерием.
Операция О является управляемым процессом, то есть мы можем выбирать какие-то параметры, которые влияют на его ход и исход, причем на каждом шаге выбирается решение, от которого зависит выигрыш и на данном шаге, и выигрыш за операцию в целом. Эти решения называются шаговыми.
Совокупность всех шаговых управлений является управлением операцией в целом. Обозначим его буквой х, а шаговые управления- буквами х1, х2, ... , хm: х=х(х1, х2, ... , хm). Требуется найти такое управление х, при котором выигрыш Z обращается в максимум:
То управление х*, при котором этот максимум достигается, называется оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений: х*=х*(х1*, х2*, ... , хm*).
Максимальный выигрыш, который достигается при этом управлении, обозначим следующим образом: 
,
где Х- множество допустимых (возможных) управлений.
Самый простой способ решения задачи- полный перебор всех вариантов. Когда количество вариантов невелико, этот способ вполне приемлем. Однако на практике задачи с небольшим числом вариантов встречаются весьма редко, поэтому полный перебор, как правило, неприемлем из-за чрезмерных затрат вычислительных ресурсов. Поэтому в таких случаях на помощь приходит динамическое программирование.
Динамическое программирование часто помогает решить задачу, переборный алгоритм для которой потребовал бы очень много времени. Этот метод использует идею пошаговой оптимизации. В этой идее есть принципиальная тонкость: каждый шаг оптимизируется не сам по себе, а с "оглядкой на будущее", на последствия принимаемого "шагового" решения. Оно должно обеспечить максимальный выигрыш не на данном конкретном шаге, а на всей совокупности шагов, входящих в операцию.
Метод динамического програмирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:
- Задача оптимизации интерпретируется как n-шаговый процесс управления.
- Целевая функция равна сумме целевых функций каждого шага.
- Выбор управления на k-м шаге зависит только о состояния системы к этому шаге, не влияет на предшествующие шаги (нет обратной связи).
- Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1и управления xk (отсутствие последействия).
- На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk- от конечного числа параметров.
Каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Этот принцип впервые был сформулирован Р. Беллманом в 1953 г. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование- процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Принцип оптимальности утверждает, что для любого процесса без обратной связи оптимальное управление таково, что оно является оптимальным для любого подпроцесса по отношению к исходному состоянию этого подпроцесса. Поэтому решение на каждом шаге оказывается наилучшим с точки зрения управления в целом.
