ISBN 978-5-9963-2564-1 Изложен принцип оптимальности и базирующийся на нем метод динамического программирования решения задач управления многошаговыми процессами, разобран ряд примеров решения типовых задач экономического содержания, рассмотрены обобщения классического принципа оптимальности и метода динамического программирования на случай задач из теории графов. <...> ВВЕДЕНИЕ Динамическое программирование —математический метод поиска оптимальных решений по управлению многошаговыми процессами,вкоторых состояние исследуемых систем изменяется во времени или поэтапно. <...> Теоретической основой метода динамического программирования (ДП) является принцип оптимальности, имеющий широкую сферу приложений в экономике, технике, естествознании, военном деле. <...> Термин «программирование» означает, что метод ДП может быть представлен в виде четкой последовательности арифметических и логических операций, т. е. в виде алгоритма, по которому можно составить программу решения соответствующих задач на электронно-вычислительных машинах (ЭВМ). <...> Иначе метод ДП называется «динамическим планированием»; это название, учитывая многообразие значений термина «программирование», в большей степени раскрывает существо и назначение рассматриваемого метода. <...> В первой главе приводится общая постановка задачи управления многошаговыми процессами, устанавливаются основные допущения классического метода ДП, обсуждаются проблемы, возникающие при решении соответствующих задач, формулируется принцип оптимальности Р. <...> Беллмана, рассматриваются замечания по практическому применению метода ДП. <...> 1 и 2 настоящего учебного пособия используются следующие основные обозначения: N —число шагов в многошаговом процессе, N 1; i—номер шага процесса, i =1, 2,. ,N, или индекс переменной или функции, указывающий их отношение к номеру шага процесса; x,xi —фазовая переменная, или переменная состояния; 10 Введение N —число шагов в многошаговом <...>
Динамическое_программирование_в экономических_задачах.pdf
А. В. Лежнёв
Динамическое
программирование
в экономических
задачах
4е издание, электронное
Рекомендовано
объединением по образованию
Учебнометодическим
в области прикладной информатики
в качестве учебного пособия для студентов
высших учебных заведений
Москва
Лаборатория знаний
2020
Стр.2
ББКУДК 519.8+330
22.19: 65.053
Л40
Лежнёв А. В.
Л40 Динамическое программирование в экономических задачах
: учебное пособие / А. В. Лежнёв. — 4-е изд., электрон. —
М. : Лаборатория знаний, 2020. — 179 с. — Систем. требования:
Adobe Reader XI ; экран 10".— Загл. с титул. экрана. —Текст :
электронный.
ISBN 978-5-00101-682-3
Изложен принцип оптимальности и базирующийся на нем метод
динамического программирования решения задач управления многошаговыми
процессами, разобран ряд примеров решения типовых
задач экономического содержания, рассмотрены обобщения классического
принципа оптимальности и метода динамического программирования
на случай задач из теории графов. Контрольные вопросы
и задачи позволят закрепить полученные знания теоретического
материала и обрести навык самостоятельного решения задач, дадут
возможность использовать пособие для работы на практических
занятиях.
Для студентов экономических специальностей вузов, а также для
студентов технических специальностей, изучающих соответствующий
раздел математического программирования.
ББКУДК 519.8+330
22.19: 65.053
Деривативное издание на основе печатного аналога:
Динамическое программирование в экономических задачах :
учебное пособие / А. В. Лежнёв.—М. : БИНОМ. Лаборатория
знаний, 2006. — 176 с. : ил. —ISBN 5-94774-344-2.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных техническими средствами защиты авторских прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации
ISBN 978-5-00101-682-3
○c Лаборатория знаний, 2015
Стр.3
Оглавление
Предисловие .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 3
Введение.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 4
Глава 1. Задачи управления многошаговыми процессами и метод
динамического программирования.. .. .. ... .. .. .. .. .. .. .. .. 11
1.1. Основные понятия и постановка задачи . .. .. ... .. .. .. .. .. .. .. .. 11
1.2. Допущения метода динамического программирования .. .. .. .. .. .. 16
1.3. Замечания по оптимизации многошаговых процессов .. .. .. .. .. .. 17
1.4. Методика вычисления оптимального значения задачи .. .. .. .. .. .. 20
1.5. Принцип оптимальности Беллмана . .. .. .. .. ... .. .. .. .. .. .. .. .. 24
1.6. Метод динамического программирования и его основные этапы .. . 26
1.7. Замечания по практическомуприменению метода динамического
программирования.. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 29
Контрольные вопросы.. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. . 32
Глава 2. Примеры решения типовых задач методом динамического
программирования .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. . 34
2.1. Задача о распределении инвестиций .. .. .. .. ... .. .. .. .. .. .. .. .. 34
2.2. Задача о распределении инвестиций по максимуму нормы
прибыли .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 49
2.3. Задача о загрузке транспортного средства. .. ... .. .. .. .. .. .. .. .. 58
2.4. Задача о замене оборудования . .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 70
2.5. Задача о распределении ресурсов. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 77
Задачи для самостоятельного решения .. .. .. ... .. .. .. .. .. .. .. .. 85
Глава 3. Динамическое программирование в теории графов .. .. .. .. 90
3.1. Основные понятия теории графов .. .. .. .. .. ... .. .. .. .. .. .. .. .. 90
3.2. Перечисление путей на графе.. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 96
3.3. Задача о кратчайшем пути .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 100
3.4. Решение задачи о кратчайшем пути методом динамического
программирования.. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 105
3.5. Задача о проектировании дороги . .. .. .. .. .. ... .. .. .. .. .. .. .. .. 114
3.6. Ориентированные графы и сети.. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 120
3.7. Задача о кратчайшем пути на ориентированных графах .. .. .. .. . 125
3.8. Динамическое программирование на ориентированных графах .. .. 132
3.9. Задача об управлении самолетом. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 137
3.10. Построение максимального пути.. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 145
3.11. Динамическое программирование в задачах сетевого
планирования .. .. .. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. 155
3.12. Пример расчета параметров сетевого графика .. .. .. .. .. .. .. .. .. 162
Контрольные вопросы.. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. . 167
Задачи для самостоятельного решения .. .. .. ... .. .. .. .. .. .. .. .. 169
Заключение .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .... .. . 173
Литература .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .... .. . 175
Стр.177