Такого рода задачи основаны на функции Беллмана и при решении используется метод обратной прогонки (см. Типовые задания). Также можно воспользоваться сервисом Процедура прямой прогонки .
Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций 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.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, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Эти значения многократно повто
Динамическое программирование (ДП) представляет собой математический аппарат, разработанный с целью повышения эффективности вычислений при решении некоторого класса задач математического программирования путем их разложения (декомпозиции) на относительно небольшие и, следовательно, менее сложные подзадачи. Характерным для динамического программирования является подход к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа.
Фундаментальным принципом, положенным в основу теории ДП, является принцип оптимальности. По существу, он определяет порядок поэтапного решения допускающей декомпозицию задачи (это более приемлемый путь, чем непосредственное решение задачи в исходной постановке) с помощью рекуррентных вычислительных процедур.
Основные положения динамического программирования вместе с непривычными математическими обозначениями часто порождают трудности при изучении этого раздела математического программирования. В особенности это относится к тем, кто впервые знакомится с предметом. Однако опыт показывает, что систематическое обращение к задачам и методам ДП, требующее определенной настойчивости, в конечном счете, приводит начинающего к полному пониманию вначале неясных положений. Когда это происходит, динамическое программирование начинает казаться удивительно простой и стройной теорией.
Применим метод динамического программирования для распределения капиталовложений между четырьмя мероприятиями. Общая сумма средств инвестируемых в развитие составляет не более десяти миллионов гривен. На основе технико-экономических расчетов установлено, что в результате реконструкции в зависимости от количества затраченных средств, мероприятия будут иметь производительность, приведенную в таблице 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
Глава 3. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Основные понятия и постановка задачи
В задачах линейного и нелинейного программирования рассматриваются статистические задачи экономики, которые не зависят от времени. Для них оптимальное решение находится за один шаг (этап). Такие задачи называются одноэтапными или одношаговыми. В отличие от них задачи динамического программирования являются многоэтапными или многошаговыми. Многошаговым называют процесс экономики, развивающийся во времени или распадающийся на ряд шагов или этапов.
Особенность метода динамического программирования состоит в том, что управленческое решение состоит из комплекса взаимосвязанных решений. Последовательность взаимосвязанных решений, принимаемых на каждом этапе развития процесса во времени, называют стратегией или управлением. В экономике управление сводится к распределению и перераспределению средств (ресурсов) на каждом этапе.
Рассмотрим некоторый развивающийся экономический процесс, разделяющийся по времени из нескольких этапов (шагов). На каждом шаге выбираются параметры, влияющие на ход и исход операции, и принимается решение, от которого зависит выигрыш и на данном шаге по времени, например, в текущем году, и в операции в целом, например, за пятилетку. Этот выигрыш называется шаговым управлением.
Управление процессом в целом распадается на совокупность шаговых управлений : 
. В общем случае – числа, векторы, функции. Нужно найти такое управление , при котором выигрыш (например, доход) является максимальным 
. Управление , при котором этот максимум достигается, называется оптимальным и состоит из шаговых управлений 
. Максимальный выигрыш обозначим .
Задачи математического программирования, которые можно представить как многошаговый (многоэтапный) процесс, составляют предмет динамического программирования. При решении задач оптимизации методом динамического программирования нужно на каждом шаге учитывать последствия, к которым приведет в будущем решение, принимаемое в данный момент. Такой способ выбора решения является определяющим в динамическом программировании. Он называется принципом оптимальности.
Метод динамического программирования рассмотрим на отдельных примерах.
1. Задача управления производством. Планируется работа промышленного объединения, состоящего из предприятий, , на период времени из лет, . В начальный период на развитие объединения выделяются средства в размере . Их нужно распределить между предприятиями. В процессе работы выделенные средства частично расходуются. Каждое предприятие за год дает прибыль, зависящую от вложенных в него средств. В начале каждого года средства можно перераспределять. Нужно так распределить средства между предприятиями, чтобы суммарная прибыль объединения за период T летбыла максимальной.
Принятие решения разбивается на шагов, . Управление заключается в начальном распределении и последующих перераспределениях средств. Управление на каждом шаге t
выражается вектором 
, где 
– объем средств, выделенных i
-му предприятию в начале года t
. Управление процессом в целом состоит из совокупности шаговых управлений 
.
Пусть – материальное и финансовое состояние системы на начало t
-го года, 
. Состояние каждого предприятия также является вектором. Его компонентами являются трудовые ресурсы, основные фонды, финансовое положение и т.д. То есть 
, где – число компонент вектора. Вектор управления – это функция состояния системы предприятий на начало соответствующего финансового года . Начальное состояние системы задается.
Целевая функция – суммарная прибыль объединения за лет. Пусть – прибыль объединения за год . Тогда целевая функция 
. На состояние системы и вектор управления в каждом году могут быть наложены ограничения. Пусть – множество этих ограничений, которое называется множеством допустимых управлений или множеством экономических возможностей. Возможные управления должны принадлежать ей . Таким образом, окончательно задача имеет вид 
.
2. Задача о ремонте и замене оборудования . Владелец автомашины эксплуатирует её в течение m лет. В начале каждого года он может принять одно из трёх решений: 1) продать машину и заменить её новой; 2) отремонтировать и продолжать эксплуатацию; 3) продолжить эксплуатацию без ремонта.
Пошаговое управление – выбор одного из трех решений. Его нельзя выразить числами, но можно приписать первому значение 1, второму – 2, третьему – 3. Как чередовать управления 1, 2, 3 по годам, чтобы суммарные расходы на ремонт, эксплуатацию, покупку новой машины были минимальными: 
.
Управление операций представляет собой какую-то комбинацию чисел, например: . Любое управление – это вектор такого вида, содержащий m компонент, каждый из которых принимает одно из трех значений 1, 2, 3.
Особенности задач динамического программирования.
1. В этих задачах вместо поиска оптимального решения сразу для всей сложной задачи переходят к нахождению оптимального решение для нескольких более простых задач аналогичного содержания, на которые распадается исходная задача.
2. Решение, принимаемое на конкретном шаге, не зависит от «предыстории»: от того, каким образом оптимизируемый процесс достиг настоящего состояния. Оптимальное решение выбирается с учетом факторов, характеризующих процесс в данный момент;
3. Выбор оптимального решения на каждом шаге по времени производится с учетом его последствий. Оптимизируя процесс на каждом отдельном шаге, нельзя забывать обо всех последующих шагах.
Общая постановка задачи динамического программирования.
Рассмотрим некоторую развивающуюся во времени систему управления, на которую можно влиять принимаемыми решениями. Пусть эта система распадается на T шагов (этапов). Ее состояние на начало каждого шага описывается вектором 
. Множество всех состояний, в которых может находиться система на начало t
-го шага, обозначим через . Начальное состояние системы считается известным, то есть при задан вектор .
Развитие системы состоит в последовательном переходе из одного состояния в другое. Если система находится в состоянии , то ее состояние на следующем шаге определяется не только вектором , но и управленческим решением , принятым на шаге t
. Запишем это следующим образом . Решение на каждом шаге нужно выбирать из некоторого множества возможных решений, оно не может быть произвольным. Развитие системы в течение всего рассматриваемого периода можно описать последовательностью состояний 
, где .
Любая последовательность допустимых решений, переводящая систему из начального состояния в конечное состояние , называют стратегией. Для полного описания процесса, состоящего из шагов, каждой стратегии надо дать оценку – значение целевой функции , которая представима в виде суммы оценочных функций , значения которых находятся на каждом шаге при переходе из состояния в состояние , т.е. 
.
Общую задачу динамического программирования можно сформулировать так. Найти стратегию , доставляющую экстремум функции при условиях, что задан вектор начального состояния системы , а вектор текущего состояния системы на момент времени является функцией состояния системы на момент времени и управленческого решения, принятого на этом шаге: , .
Функциональные уравнения динамического программирования называются функциональными уравнениями Беллмана .
Математическая формулировка принципа оптимальности с аддитивным критерием . Пусть заданы начальное и конечное состояние системы . Введем обозначения: – значение функции цели на первом этапе при начальном состоянии системы X 0 и при управлении , – значение функции цели на втором шаге при состоянии системы и при управлении . Соответственно далее – значение функции цели на -ом этапе, . Очевидно, что
Требуется найти оптимальное управление 
, такое что
при ограничениях
Поиск оптимального решения задачи (69)–(70) сводится к оптимальному решению нескольких более простых задач аналогичного содержания, которые входят составной частью в исходную задачу.
Пусть – соответственно области определения (допустимых решений) для задачи на последнем этапе, на последних двух этапах и т.д., – область определения исходной задачи. Пусть – условно оптимальное значение функции цели на последнем этапе, т.е.
, . (71)
Обозначим соответственно оптимальные значения функции цели на двух последних, трех последних этапах и т.д., на Т этапах. В силу этих обозначений имеем:
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
Выражения (71) – (75) называются функциональными уравнениями Беллмана. Эти уравнения имеют рекуррентный характер, так как для нахождения оптимального уравнения на T шагах нужно знать условно оптимальное управление на последующих T –1 шагах и т.д. Поэтому функциональные уравнения также называют рекуррентными соотношениями Беллмана.
Используя функциональные уравнения Беллмана, находим решение рассматриваемой задачи динамического программирования. Решение ищется в обратном порядке от до .
Запишем функциональное уравнение последнего этапа
.
Рассматривают набор фиксированных состояний и решений и отвечающих им значений . Среди решений выбирают такое , которое обеспечивает максимум (минимум) функции . Затем переходят к предшествующему этапу и рассматривают функциональное уравнение (72). Для каждого возможного состояния находят значение в зависимости от допустимого решения . Затем сравнивают суммы и определяют максимальную (минимальную) сумму для каждого состояния и соответствующее условное оптимальное решение , т.е. определяют решение, при котором функция принимает экстремальное значение.
Далее переходят к этапам ( и т.д.) до момента времени . Для первого этапа записывают функциональное уравнение (75). На этом шаге предположения о возможных состояниях процесса не делают, так как первоначальное состояние известно. Для этого состояния находится оптимальное решение с учетом всех условно оптимальных решений предыдущих этапов.
Весь процесс проходят в прямом направлении от до и определяют оптимальное решение для всего процесса (всей задачи). Оно придает целевой функции максимальное (минимальное) значение.
Задача выбора кратчайшего пути . Задана транспортная железнодорожная сеть (рис.11), на которой указан пункт отправления A и пункт назначения B. Между ними имеется много других пунктов. Некоторые соединены между собой железнодорожным полотном. Над каждым участком железнодорожной сети проставлены цифры, указывающие расстояние между двумя соседними пунктами. Требуется составить маршрут из пункта A в пункт B минимальной длины.
Разобьем все расстояние между A и B на этапы (рис.11). Оценим отрезки, на которые делят линии (2-2) и (3-3) участки сети.
Выбор кратчайшего пути начнем с конца. Найдем кратчайшие пути, соединяющие конечный пункт B с каждой точкой пересечения линии (2-2) с транспортной сетью. Таких точек пересечения три: D 1 , D 2 , D 3 . Для точки D 1 min(10;8+4;8+3+5)=10; для точки D 2 min(5+4;5+3+5)=9; для точки D 3 min(2.5+3+4; 2.5+5)=7.5.
На рисунке кратчайшие расстояния от точек D 1 ,D 2 и D 3 до конечного пункта B показаны в скобках. Далее рассматриваем точки пересечения линии (3-3) с участком сети. Эти точки C 1 , C 2 , C 3 . Находим кратчайшие расстояния от этих точек до пункта B. Они показаны в скобках у точек C 1 (19), C 2 (14), C 3 (12). Наконец находим минимальную длину пути, ведущего из A в B. Это расстояние равно 23. Затем находим этапы в обратном порядке. Находим кратчайший путь: 
.
Ключевые слова : динамическое программирование, многоэтапный процесс, управление, управляемый процесс, стратегия, оптимальная стратегия, принцип оптимальности, условно оптимальное управление, функциональные уравнения Беллмана.
Вопросы для самопроверки
1. Что является предметом динамического программирования?
2. В чем отличие динамического программирования от линейного программирования?
3. Каковы основные свойства динамического программирования?
4. В чем заключается принцип оптимальности динамического программирования?
5. Какова модель задачи планирования работы промышленного объединения?
6. Какова формулировка общей задачи динамического программирования?
7. Что выражают функциональные уравнения Беллмана?
8. В чем заключается идея решения задачи динамического программирования?
Задачи для самостоятельного решения
Пример 1. Сформулировать приведенные задачи в терминах динамического программирования.
А) Производственное объединение состоит из т предприятий. В начале каждого года между ними полностью распределяется централизованный фонд развития производства. Выделение i -му предприятию из этого фонда тыс.руб. обеспечивает получение дополнительной прибыли, равной тыс. руб. К началу планового периода из T лет централизованному фонду развития производства выделено тыс.руб. В каждый последующий год этот фонд формируется за счет отчислений от полученной прибыли. Эти отчисления для i -го предприятия составили тыс.руб. Найти такой вариант распределения централизованного фонда развития производства, чтобы получить за T лет максимальную общую прибыль.
Б) В состав производственного объединения входят два предприятия, связанные между собой кооперированными поставками. Вкладывая дополнительные средства в их развитие, можно улучшить технико-экономические показатели деятельности производственного объединения в целом, обеспечив получение дополнительной прибыли. Ее величина зависит от величины средств, выделяемых каждому предприятию, и использованию этих средств. Считая, что на развитие i -го предприятия в начале k -го года выделяется тыс.руб., найти такой вариант распределения средств между предприятиями в течении T лет, чтобы за данный период времени будет получить максимальную прибыль.
Пример 2. Требуется перевезти груз из пункта A в пункт B.
На рис.12 показана сеть дорог и стоимость перевозки единицы груза между отдельными пунктами сети (проставлены у соответствующих ребер). Определить маршрут доставки груза из пункта A в пункт B, которому соответствуют наименьшие затраты.
Пример 3. На данной сети дорог имеется несколько маршрутов по доставке груза из пункта A в пункт B (рис.13). Стоимость перевозки единицы груза между отдельными пунктами сети проставлена у соответствующих ребер. Определить оптимальный маршрут доставки груза из пункта A в пункт B, по которому общие затраты будут минимальными.
Задача распределения инвестиций между предприятиями
На реконструкцию и модернизацию основного производства объединению выделяются материальные ресурсы в объеме . Эти ресурсы нужно распределить между n предприятиями объединения.
Пусть – прибыль, получаемая, если i -му предприятию выделено единиц ресурса. Общая прибыль объединения складывается из прибылей отдельных предприятий
Математическая модель распределения инвестиций имеет вид
Требуется добиться максимума целевой функции (76) при условиях полного распределения инвестиций объема между предприятиями (77) и неотрицательности переменных (78).
Решение задачи представим в виде многоэтапного процесса. Вместо решения одной задачи с заданным объемом инвестиций и фиксированным числом предприятий n рассмотрим семейства задач, в которых объем выделяемого ресурса может меняться от 0 до , а число предприятий – от 1 до n . Например, предполагается, что на первом этапе инвестиция в объеме выделяется только одному предприятию, на втором этапе – двум предприятиями и т.д., на n -ом этапе – предприятиям.
Введем последовательность функций , где – максимальное значение прибыли, получаемой, когда ресурс x
распределен только одному предприятию; – максимальное значение прибыли, получаемой при условии, что объем ресурса распределен между двумя предприятиями и т.д.; – максимальное значение прибыли, получаемой при условии, что ресурс распределен между n
предприятиями. Очевидно, что 
.
В двух случаях элементы последовательности имеют простой вид: . Эти соотношения означают: если инвестиция не распределяется, то ожидаемая прибыль равна нулю, и если инвестиция распределяется одному предприятию, то прибыль объединения будет состоять из прибыли только одного предприятия.
Пусть инвестиция объема x , , распределяется между двумя предприятиями. Если – объем инвестиций, выделенный второму предприятию, то его прибыль составит
.
Допустим, что инвестиция объема x распределяется между k предприятиями. Если – объем инвестиций, выделенный k -му предприятию, то оставшееся количество ресурса распределяется между оставшимися k –1 предприятиями наилучшим образом. Так как известно, то
. (79)
Полученное рекуррентное соотношение (79) и есть функциональное уравнение Беллмана.
Решение исходной задачи получим при из соотношения (79):
Рассмотрим вычислительную схему решения задачи распределения инвестиций методом динамического программирования.
Промежуток разбивают, например, на N интервалов с шагом и считают, что функции определены для значений . При i =1 функция определяется равенством . Множество значений , записывают в таблицу. Зная значения , переходят к вычислению значений функции :
В ходе вычислений устанавливают не только значения 
, но и такие значения , при которых достигается максимум прибыли . Затем находят значения функции и т.д. Пройдя весь процесс вычисления функций , получают соотошение
с помощью которого находят значение . Таким образом, на последнем этапе находят максимальное значение функции цели , а также оптимальное значение выделяемого ресурса для n
-го предприятия.
Затем процесс вычислений просматривается в обратном порядке. Зная , находят – объем инвестиций, подлежащий распределению между оставшимися n– 1 предприятиями.
Прежде всего, используя соотношение
находят значения и и т.д. Продолжая таким образом, в конце процесса находится значение .
Пример 1. Между четырьмя предприятиями следует распределить 200 единиц ограниченного ресурса. Значения, получаемой предприятиями прибыли в зависимости от выделенной суммы , приведены в табл.57 , составленной с «шагом» единиц ресурса. Составить план распределения ресурса, дающий наибольшую суммарную прибыль.
Таблица 57
| Выделяемый объем инвестиций | Величина прибыли предприятия | |||
Решение. Представим поставленную задачу как четырехэтапную. На первом этапе, при , рассмотрим случай, когда инвестиция выделяется только одному предприятию. В этом случае . Для каждого значения из промежутка находим значения и заносим их в таблицу 58.
Таблица 58
При инвестиция распределяется между двумя предприятиями. В этом случае общая прибыль вычисляется с помощью следующего функционального уравнения
. (80)
· пусть , то :
· пусть , то 
:
· пусть то :
· пусть , то :
Результат вычисления запишем в табл.59.
Таблица 59
| 0+15 | 14+0 | |||||||
| 0+28 | 14+15 | 30+0 | ||||||
| 0+60 | 14+28 | 30+15 | 55+0 | |||||
| 0+75 | 14+60 | 30+28 | 55+15 | 73+0 | ||||
| 0+90 | 14+75 | 30+60 | 55+28 | 73+15 | 85+0 |
На 3-ем этапе инвестиция в объеме единиц распределяется между тремя предприятиями. В этом случае общая прибыль объединения определяется с помощью функционального уравнения
.
Результаты вычислений представим в табл.60.
Таблица 60
| 0+15 | 17+0 | |||||||
| 0+30 | 17+15 | 33+0 | ||||||
| 0+60 | 17+30 | 33+15 | 58+0 | |||||
| 0+75 | 17+60 | 33+30 | 58+15 | 73+0 | ||||
| 0+90 | 17+75 | 33+60 | 58+30 | 73+15 | 92+0 |
На 4-м этапе инвестиция распределяется между четырьмя предприятиями и общая прибыль при этом распределяется с помощью функционального уравнения
Динамическое программирование представляет собой математический аппарат, разработанный для эффективного решения некоторого класса задач математического программирования. Этот класс характеризуется возможностью естественного (а иногда и искусственного) разбиения всей операции на ряд взаимосвязанных этапов. Термин "динамическое" в названии метода возник, видимо, потому что этапы предполагаются разделенными во времени. Однако этапами могут быть элементы операции, никак не связанные друг с другом показателем времени. Тем не менее, метод решения подобных многоэтапных задач применяется один и тот же, и его название стало общепринятым, хотя в некоторых источниках его называют многоэтапным программированием.
Модели динамического программирования могут применяться, например, при разработке правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа; при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; при распределении дефицитных капиталовложений между возможными новыми направлениями их использования; при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены; при разработке долгосрочных правил замены выбывающих из эксплуатации основных фондов и т.д.
Самый простой способ решения задачи – полный перебор всех вариантов. Когда количество вариантов невелико, этот способ вполне приемлем. Однако на практике задачи с небольшим числом вариантов встречаются весьма редко, поэтому полный перебор, как правило, неприемлем из-за чрезмерных затрат вычислительных ресурсов. Поэтому в таких случаях на помощь приходит динамическое программирование.
Динамическое программирование часто помогает решить задачу, переборный алгоритм для которой потребовал бы очень много времени. Этот метод использует идею пошаговой оптимизации. В этой идее есть принципиальная тонкость: каждый шаг оптимизируется не сам по себе, а с "оглядкой на будущее", на последствия принимаемого "шагового" решения. Оно должно обеспечить максимальный выигрыш не на данном конкретном шаге, а на всей совокупности шагов, входящих в операцию.
Метод динамического программирования может применяться только для определенного класса задач. Эти задачи должны удовлетворять таким требованиям:
· задача оптимизации интерпретируется как n-шаговый процесс управления;
· целевая функция равна сумме целевых функций каждого шага;
· выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи);
· состояние s k после k-го шага управления зависит только от предшествующего состояния s k-1 и управления x k (отсутствие последействия);
· на каждом шаге управление X k зависит от конечного числа управляющих переменных, а состояние s k – от конечного числа параметров.
В основе решения всех задач динамического программирования лежит "принцип оптимальности" Беллмана, который выглядит следующим образом:
каково бы ни было состояние системы S в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Этот принцип впервые был сформулирован Р.Беллманом в 1953 г. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование – процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно оказывать влияния на предшествующие шаги.
Общая постановка классической задачи распределения инвестиций.
Рассмотрим общую постановку динамической задачи распределения инвестиций.
Для развития выделены капитальные вложения в размере S. Имеется n объектов вложений, по каждому из которых известна ожидаемая прибыль fi(x), получаемая от вложения определенной суммы средств. Необходимо распределить капитальные вложения между n объектами (предприятиями, проектами) таким образом, чтобы получить максимально возможную суммарную прибыль.
Для составления математической модели исходим из предположений:
· прибыль от каждого предприятия (проекта) не зависит от вложения средств в другие предприятия;
· прибыль от каждого предприятия (проекта) выражается в одних условных единицах;
· суммарная прибыль равна сумме прибылей, полученных от каждого предприятия (проекта).
Данная постановка является упрощенной моделью реального процесса распределения инвестиций, и в "чистом" виде не встречается, так как не учитывает некоторые факторы, а именно:
· наличие "неформальных" критериев, т.е. тех, которые невозможно измерить количественно (например, согласованность проекта с общей стратегией предприятия, его социальный, либо экологический характер и т.д.), в связи с чем проекты могут иметь различный приоритет;
· уровень риска проектов;
· другие факторы.
В связи с необходимостью учета уровня риска при формировании инвестиционного портфеля появилось стохастическое динамическое программирование, которое имеет дело с вероятностными величинами. Оно нашло применение в различных областях, среди которых одной из наиболее широко исследуемых является управление рисковыми финансовыми инвестициями.