Динамическое программирование в экономических задачах

А. В. Лежнёв

Динамическое
программирование
в экономических
задачах

Рекомендовано

объединением по образованию 
Учебнометодическим

в области прикладной информатики
в качестве учебного пособия для студентов 
высших учебных заведений

Москва
Лаборатория знаний
2020

4е издание, электронное

УДК 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

2

ПРЕДИСЛОВИЕ

Настоящее учебное пособие предназначено для студентов широкого круга экономических специальностей, обучающихся по дисциплине «Математика». Тема
и содержание учебного пособия и уровень сложности излагаемого материала соответствуют требованиям государственных образовательных стандартов. Актуальность разработки пособия обусловлена высокой востребованностью экономического образования в современных условиях, важностью повышения уровня математической подготовки студентов-экономистов и недостатком доступных учебных пособий, сочетающих систематизированное изложение теоретических основ метода динамического программирования с последовательным обучением решению данным методом типовых экономических
задач. При разработке пособия учтен опыт преподавания дисциплины «Математика» в Краснодарском филиале Российского государственного торговоэкономического университета.
В предлагаемом учебном пособии изложен необходимый теоретический
материал и детально разобран ряд примеров решения задач экономического
содержания, способствующих лучшему уяснению рассматриваемых понятий
и методов и усвоению пройденного материала. Наличие контрольных вопросов и задач для самостоятельного решения позволит студентам закрепить полученные теоретические знания и обрести навык решения задач, а преподавателям даст возможность использовать пособие на практических занятиях. Для
понимания излагаемого в пособии материала достаточно знаний, получаемых
студентами при изучении дисциплины «Математика» на первом курсе вузов
в объеме, установленном типовыми рабочими программами.
При оформлении настоящего учебного пособия приняты следующие соглашения. Вновь вводимые понятия и термины выделяются в тексте полужирным курсивом. Наиболее важные и принципиальные фрагменты текста, на которые следует обратить особое внимание при изучении материала,
выделяются в тексте светлым курсивом.
Автор
приносит
благодарность
рецензентам
проф.
Г. Т. Вартумяну
и доц. О. Б. Пантелеевой за ценные замечания, проф. Г. Л. Авагян за внимание к работе, а также студентам А. Волкоморовой и Д. Шведу, принявшим
активное участие в обсуждении данного учебного пособия.

ВВЕДЕНИЕ

Динамическое программирование — математический метод поиска
оптимальных решений по управлению многошаговыми процессами, в которых состояние исследуемых систем изменяется во времени или поэтапно. Подобные системы и процессы имеют широкое распространение в реальном мире, а необходимость эффективного управления ими
объективно определяет важность и актуальность использования математических методов решения соответствующих управленческих задач.
Теоретической основой метода динамического программирования (ДП)
является принцип оптимальности, имеющий широкую сферу приложений в экономике, технике, естествознании, военном деле.
Регулярное изучение многошаговых процессов восходит к работам
русского математика А. А. Маркова начала XX века. Его исследования
были продолжены в 40-х годах американским математиком А. Вальдом
(A. Wald), что привело к возникновению так называемого последовательного анализа. Впервые основные принципы оптимального управления многошаговыми процессами наиболее полно и систематизированно
были сформулированы в 50-х годах XX века американским математиком
Р. Беллманом (R. Bellman).
В первых задачах, решенных методом ДП, рассматривались процессы, развивающиеся во времени, что и объясняет наличие термина
«динамическое» в названии метода. Термин «программирование» означает, что метод ДП может быть представлен в виде четкой последовательности арифметических и логических операций, т. е. в виде алгоритма, по которому можно составить программу решения соответствующих задач на электронно-вычислительных машинах (ЭВМ). Иначе метод ДП называется «динамическим планированием»; это название, учитывая многообразие значений термина «программирование», в большей
степени раскрывает существо и назначение рассматриваемого метода.
Разработка и изучение математических методов решения тех или
иных задач может, безусловно, представлять самостоятельный теоретический интерес. В то же время весьма важным и актуальным является вопрос о практической роли и значимости математических методов для решения различных экономических задач. Подобные вопросы, обостряемые господствующей в настоящее время прагматично

Введение
5

стью и утилитарностью мышления, закономерно возникают у студентов,
изучающих соответствующий материал. Ответ на поставленный вопрос
является актуальным и для различного ранга руководителей и специалистов, находящихся в условиях постоянного поиска путей повышения эффективности функционирования руководимых ими экономических структур. Остановимся кратко на данной проблеме, поскольку ее
сложность и многоплановость приводят к существованию различных
точек зрения.
Прежде всего подчеркнем, что удивительно высокая эффективность
математики в естественных и технических науках постоянно подтверждается всей практической деятельностью человека; подчас даже выдающиеся ученые нашего времени пишут эмоциональные статьи о «непостижимой эффективности математики в естественных науках». Наиболее грандиозные технические проекты XX века — развитие авиации,
освоение атомной энергии, выход в космос — без использования мощного
математического инструментария не могли бы быть осуществлены в современном виде и качестве при минимальном количестве катастрофических ошибок. Для экономических наук и экономики вообще дело обстоит
сложнее, однако даже самый общий взгляд на проблему приводит к осознанию того, что тезис о возможной высокой эффективности математики в экономике является вполне естественным и логичным. Действительно, вся математика изначально и многие ее разделы впоследствии —
в том числе и ДП — своим происхождением и развитием обязаны именно
практической, хозяйственной, экономической жизни общества. Выйдя
из самих ее основ и неоднократно пройдя классический цикл «от живого
созерцания к абстрактному мышлению и от него к практике», развив
в себе мощные количественные методы анализа, математика не может
не найти эффективные приложения в самых различных сферах человеческой деятельности. Данное обстоятельство подчеркивает, в частности,
неправомерность острого противопоставления математики и реального
мира, равно как теории и практики вообще.
В то же время, справедливость общих положений еще не означает
их безусловного приоритета в каждом конкретном случае, а любой метод в любой области знания имеет свою сферу применения, подчас
весьма ограниченную. По этим причинам не следует преувеличивать
и тем более абсолютизировать роль и возможности математических методов и математики вообще — возникающие «натяжки» легко выявляются и вызывают у обучающихся негативное отношение к предмету. Как
показывает практика, существует широкий класс экономических структур, управление которыми осуществляется на интуитивном уровне без
какого-либо использования математических моделей и методов и дает

Введение

вполне приемлемые результаты. К таким структурам относятся, как
правило, организации, работа которых трудно поддается формализации и не может быть описана четкими количественными показателями
и критериями, либо отдельные предприятия мелкого масштаба. Применение математики в организациях и на предприятиях такого типа сводится к элементарным арифметическим расчетам в рамках задач бухгалтерского учета. Данные обстоятельства создают и укрепляют иллюзию возможности успешного управления любыми экономическими системами без использования какой-либо серьезной математики вообще.
Однако такая точка зрения является излишне упрощенной: имеющиеся примеры не умаляют прикладных возможностей математики,
а лишь свидетельствуют о возможности функционирования некоторых
экономических структур без должного математического обеспечения,
оставляя при этом открытым вопрос об эффективности самого функционирования. Ситуация кардинально меняется при управлении экономическими и техническими системами, характеризующимися сложной
организационной структурой, высоким уровнем технической оснащенности, широким диапазоном возможных производственных ситуаций,
быстрым изменением условий функционирования. В таких условиях интуиция, догадка, «чутье» как основа принятия управленческих решений — несмотря на отдельные достоинства интуитивного подхода — зачастую оказываются малопродуктивными. Действительно, интуиция формируется лишь на основе ранее приобретенного опыта и накопленных
знаний в той или иной сфере деятельности, что требует значительных
временных затрат, сопряжено с неизбежными ошибками в управлении
и сопровождается устойчивым снижением экономической эффективности. В жестких экономических условиях данный путь может «слишком
дорого стоить» и оказаться непозволительной роскошью. Более того,
для целесообразного управления сложными экономическими системами
недостаточно ведущихся на каждом предприятии бухгалтерских расчетов, которые лишь отражают сложившееся положение вещей и не ориентированы на поиск оптимальных управленческих решений (хотя исходные данные и результаты таких расчетов могут служить материалом
для реализации оптимизационных задач управления).
Ошибки в управлении сложными дорогостоящими или даже уникальными экономическими системами имеют чрезвычайно высокую
цену. Для исключения или, по меньшей мере, снижения риска возникновения таких ошибок неизбежно приходится прибегать к использованию
математических моделей, учитывающих и выражающих в математической форме весь спектр существенных соотношений между различными количественными характеристиками и параметрами управля

Введение
7

емых систем и окружающего их реального мира. Иными словами, математическая модель представляет собой математическое описание исследуемых систем, процессов или явлений (конечно, не абсолютно точное, а приближенное). Задачи управления, опирающиеся на грамотно
построенные математические модели, приводят к достоверным, приемлемым для практического применения результатам, однако являются
весьма сложными, и для их решения, как правило, не существует простых рецептов и явных формул. Тем самым объективно возникает потребность в разработке специальных математических методов решения
поставленных задач.
Как показывает история науки последнего времени, рациональное
применение математических методов может дать исключительно весомый дополнительный экономический эффект, многократно окупающий
затраты на постановку и исследование задачи управления, разработку
или адаптацию метода ее решения и реализацию его на ЭВМ. Не случайно современный развитый мир является свидетелем нарастающего
процесса математизации широкого спектра наук: экономических, социальных и даже чисто гуманитарных, не говоря уже о естественных и технических. При этом проявляется следующая общая закономерность: чем
крупнее масштаб управляемых систем, тем более весомый экономический эффект дает применение математических методов не только в абсолютном, но и в относительном исчислении.
Ускоренному проникновению математики в различные сферы деятельности человека в значительной степени способствует бурное развитие компьютерных технологий. Само появление ЭВМ с их большой
вычислительной мощностью позволило ставить и решать столь сложные задачи, подступиться к которым без помощи ЭВМ было совершенно
немыслимо. Обрела практический смысл разработка сложных математических методов и алгоритмов управления, значительная часть которых без привязки к ЭВМ превращается в отвлеченное формализованное
построение. Как признают многие ведущие ученые мира, целенаправленное использование вычислительной мощности ЭВМ является принципиально новым методом познания реального мира: огромный количественный рост производительности вычислений привел к качественным сдвигам в науке в целом и в математике в частности. В современных условиях математические методы реализуются, как правило,
в виде специального программного обеспечения для ЭВМ и их наиболее
широкого класса — персональных компьютеров. Важно заметить, что
при этом многие сложности и специфика реализуемых математических
методов скрываются за фасадом простого и удобного пользовательского
программного интерфейса; часто складывается обманчивое впечатле

Введение

ние, что математика не играет здесь никакой существенной роли, хотя
дело обстоит совершенно наоборот!
Математическим методам свойственно различаться глубиной логического анализа. В связи с этим подчеркнем, что любую задачу управления — в том числе и рассматриваемые в настоящем учебном пособии задачи управления многошаговыми процессами — с достаточной для практических целей точностью можно решить путем последовательного рассмотрения всех допустимых вариантов управления, или методом перебора (если множество допустимых вариантов бесконечно, то перебор
проводится с некоторым малым приращением значений управляющих
параметров). Логика метода перебора является наиболее простой и,
тем самым, весьма привлекательной для реализации. Однако за внешней простотой данного метода скрывается следующая серьезная проблема: объем вычислительных работ, связанных с простым перебором,
для сложных реальных задач может оказаться столь велик, что с его
проведением в разумные приемлемые сроки не смогут справиться даже
самые мощные ЭВМ. В то же время практическую значимость представляет не столько потенциальная, сколько актуальная разрешимость задачи: решение задачи управления, являясь оптимальным или близким
к таковому, должно быть получено оперативно, в режиме «реального
времени», иначе оно устареет и потеряет свою значимость еще до окончания поиска решения. В соответствии с данным обстоятельством возникает объективная необходимость в разработке иных более эффективных методов решения, пусть логически более сложных, но позволяющих
снизить трудоемкость вычислений.
Для задач управления многошаговыми процессами таким методом
является метод ДП, рассматриваемый в настоящем учебном пособии.
Излагаемый в пособии материал разделен на три главы. В первой
главе приводится общая постановка задачи управления многошаговыми
процессами, устанавливаются основные допущения классического метода ДП, обсуждаются проблемы, возникающие при решении соответствующих задач, формулируется принцип оптимальности Р. Беллмана,
рассматриваются замечания по практическому применению метода ДП.
Особенностью изложения данного материала, в отличие от традиционного, является выделение предварительного этапа метода ДП, что во
многих случаях позволяет снизить объем вычислений и упростить их.
Излагаемый в данной главе теоретический материал не имеет жесткой
привязки к экономическим задачам и может быть полезен читателям
широкого круга специальностей. Во второй главе приводятся примеры
решения ряда типовых экономических задач методом ДП. Данной главе
отведена значительная часть пособия, поскольку затруднения у студен

Введение
9

тов вызывает именно проведение математической формализации экономической задачи и практическое применение общего принципа оптимальности. Рассматриваемые в главе задачи выбраны достаточно простыми, чтобы продемонстрировать существо метода ДП и довести решение до конкретного числового результата, не осложняя изложение громоздкими вычислениями и второстепенными деталями. В третьей главе
рассматриваются важные и естественные обобщения классического
принципа оптимальности и метода ДП для задач, формулируемых в терминах теории графов. Приведенные в пособии контрольные вопросы
и задачи для самостоятельного решения позволяют закрепить знания
теоретического материала и приобрести навыки практического решения задач. Наличие ряда вариантов исходных данных позволит использовать предложенные задачи на практических и семинарских занятиях,
для домашних заданий и при проведении контрольных работ и тестов.
Отметим, что методологическая проблема выбора наиболее адекватной формы изложения сложных математических дисциплин для студентов экономических специальностей не является окончательно решенной.
Ограниченность часов на изучение темы, сильно варьирующийся уровень математической подготовки студентов, да и сами цели обучения
студентов-экономистов требуют специального подхода к преподаванию.
В этих условиях особую важность приобретают вопросы соблюдения
баланса между строгостью и доступностью изложения, а неизбежный
отказ от излишней формализации и строгих доказательств не должен
сопровождаться потерей логики и стройности изложения. При разработке настоящего учебного пособия автор предпринял попытку найти
и реализовать соответствующий стиль изложения, считая вслед за основоположником метода ДП, что ценность пособия определяется «в
конечном счете по его внутреннему содержанию, а не по удельному
весу высокопарных псевдоабстракций, которыми так легко пересолить
любой текст» [1].

Условные обозначения

В гл. 1 и 2 настоящего учебного пособия используются следующие
основные обозначения:

N — число шагов в многошаговом процессе, N ⩾ 1;

i — номер шага процесса, i = 1, 2, . . . , N, или индекс переменной

или функции, указывающий их отношение к номеру шага

процесса;

x, xi — фазовая переменная, или переменная состояния;

Введение

N — число шагов в многошаговом процессе, N ⩾ 1;

i — номер шага процесса, i = 1, 2, . . . , N, или индекс переменной

или функции, указывающий их отношение к номеру шага

процесса;

x, xi — фазовая переменная, или переменная состояния;

X — множество допустимых значений фазовой переменной;

u, ui — управляющая переменная, или управление;

U — множество допустимых значений управляющей переменной;

fi — функция процесса для шага с номером i;

zi — частная целевая функция на шаге с номером i;

Z — целевая функция, или критерий оптимальности для всего

многошагового процесса;

Bi(xi) — функция Беллмана;

˜ui(xi−1) — условно-оптимальное управление.

В гл. 3, посвященной приложениям метода динамического программирования в теории графов, данные обозначения используются в существенно меньшей степени.