Анотация

Изложен принцип оптимальности и базирующийся иа нем метод динамического программирования решения задач управления много­шаговыми процессами, разобран ряд примеров решения типовых за­дач экономического содержания, рассмотрены обобщения классического принципа оптимальности и метода динамического программирования на случай задач из теории графов. Контрольные вопросы и задачи позволят закрепить полученные знания теоретического материала и обрести на­вык самостоятельного решения задач, дадут возможность использовать пособие для работы на практических занятиях.

Для студентов экономических специальностей вузов, а также для студентов технических специальностей, изучающих соответствующий раздел математического программирования.

ПРЕДИСЛОВИЕ

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

В предлагаемом учебном пособии изложен необходимый теоретический материал и детально разобран ряд примеров решения задач экономического содержания, способствующих лучшему уяснению рассматриваемых понятий и методов и усвоению пройденного материала. Наличие контрольных вопро­сов и задач для самостоятельного решения позволит студентам закрепить по­лученные теоретические знания и обрести навык решения задач, а преподава­телям даст возможность использовать пособие на практических занятиях. Для понимания излагаемого в пособии материала достаточно знаний, получаемых студентами при изучении дисциплины «Математика» на первом курсе вузов в объеме, установленном типовыми рабочими программами.

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

Автор приносит благодарность рецензентам проф. Г. Т. Вартумяну и доц. О. Б. Пантелеевой за ценные замечания, проф. Г. Л. Авагян за вни­мание к работе, а также студентам А. Волкоморовой и Д. Шведу, принявшим активное участие в обсуждении данного учебного пособия.

ВВЕДЕНИЕ

Динамическое программирование — математический метод поиска оптимальных решений по управлению многошаговыми процессами, в ко­торых состояние исследуемых систем изменяется во времени или по­этапно. Подобные системы и процессы имеют широкое распростране­ние в реальном мире, а необходимость эффективного управления ими объективно определяет важность и актуальность использования мате­матических методов решения соответствующих управленческих задач. Теоретической основой метода динамического программирования (ДП) является принцип оптимальности, имеющий широкую сферу приложе­ний в экономике, технике, естествознании, военном деле.

Регулярное изучение многошаговых процессов восходит к работам русского математика А. А. Маркова начала XX века. Его исследования были продолжены в 40-х годах американским математиком А. Вальдом (А. Wald), что привело к возникновению так называемого последова­тельного анализа. Впервые основные принципы оптимального управле­ния многошаговыми процессами наиболее полно и систематизированно были сформулированы в 50-х годах XX века американским математиком Р. Беллманом (R. Bellman).

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

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

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

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

Ошибки в управлении сложными дорогостоящими или даже уни­кальными экономическими системами имеют чрезвычайно высокую цену. Для исключения или, по меньшей мере, снижения риска возникно­вения таких ошибок неизбежно приходится прибегать к использованию математических моделей, учитывающих и выражающих в мате­матической форме весь спектр существенных соотношений между раз­личными количественными характеристиками и параметрами управля­емых систем и окружающего их реального мира. Иными словами, ма­тематическая модель представляет собой математическое описание ис­следуемых систем, процессов или явлений (конечно, не абсолютно точ­ное, а приближенное). Задачи управления, опирающиеся на грамотно построенные математические модели, приводят к достоверным, прием­лемым для практического применения результатам, однако являются весьма сложными, и для их решения, как правило, не существует про­стых рецептов и явных формул. Тем самым объективно возникает по­требность в разработке специальных математических методов решения поставленных задач.

Как показывает история науки последнего времени, рациональное применение математических методов может дать исключительно весо­мый дополнительный экономический эффект, многократно окупающий затраты на постановку и исследование задачи управления, разработку или адаптацию метода ее решения и реализацию его на ЭВМ. Не слу­чайно современный развитый мир является свидетелем нарастающего процесса математизации широкого спектра наук: экономических, соци­альных и даже чисто гуманитарных, не говоря уже о естественных и тех­нических. При этом проявляется следующая общая закономерность: чем крупнее масштаб управляемых систем, тем более весомый экономиче­ский эффект дает применение математических методов не только в аб­солютном, но и в относительном исчислении.

Ускоренному проникновению математики в различные сферы дея­тельности человека в значительной степени способствует бурное раз­витие компьютерных технологий. Само появление ЭВМ с их большой вычислительной мощностью позволило ставить и решать столь слож­ные задачи, подступиться к которым без помощи ЭВМ было совершенно немыслимо. Обрела практический смысл разработка сложных матема­тических методов и алгоритмов управления, значительная часть кото­рых без привязки к ЭВМ превращается в отвлеченное формализованное построение. Как признают' многие ведущие ученые мира, целенаправ­ленное использование вычислительной мощности ЭВМ является прин­ципиально новым методом познания реального мира: огромный коли­чественный рост производительности вычислений привел к качествен­ным сдвигам в науке в целом и в математике в частности. В совре­менных условиях математические методы реализуются, как правило, в виде специального программного обеспечения для ЭВМ и их наиболее широкого класса — персональных компьютеров. Важно заметить, что при этом многие сложности и специфика реализуемых математических методов скрываются за фасадом простого и удобного пользовательского программного интерфейса; часто складывается обманчивое впечатле­ние, что математика не играет здесь никакой существенной роли, хотя дело обстоит совершенно наоборот!

Математическим методам свойственно различаться глубиной логи­ческого анализа. В связи с этим подчеркнем, что любую задачу управле­ния — в том числе и рассматриваемые в настоящем учебном пособии за­дачи управления многошаговыми процессами — с достаточной для прак­тических целей точностью можно решить путем последовательного рас­смотрения всех допустимых вариантов управления, или методом пе­ребора (если множество допустимых вариантов бесконечно, то перебор проводится с некоторым малым приращением значений управляющих параметров). Логика метода перебора является наиболее простой и, тем самым, весьма привлекательной для реализации. Однако за внеш­ней простотой данного метода скрывается следующая серьезная про­блема: объем вычислительных работ, связанных с простым перебором,

I

для сложных реальных задач может оказаться столь велик, что с его проведением б разумные приемлемые сроки не смогут справиться даже самые мощные ЭВМ. В то же время практическую значимость представ­ляет не столько потенциальная, сколько актуальная разрешимость за­дачи: решение задачи управления, являясь оптимальным или близким к таковому, должно быть получено оперативно, в режиме «реального времени», иначе оно устареет и потеряет свою значимость еще до окон­чания поиска решения. В соответствии с данным обстоятельством воз­никает объективная необходимость в разработке иных более эффектив­ных методов решения, пусть логически более сложных, но позволяющих снизить трудоемкость вычислений.

Для задач управления многошаговыми процессами таким методом является метод ДП, рассматриваемый в настоящем учебном пособии. Излагаемый в пособии материал разделен на три главы. В первой главе приводится общая постановка задачи управления многошаговыми процессами, устанавливаются основные допущения классического ме­тода ДП, обсуждаются проблемы, возникающие при решении соответ­ствующих задач, формулируется принцип оптимальности Р. Беллмана, рассматриваются замечания по практическому применению метода ДП. Особенностью изложения данного материала, в отличие от традицион­ного, является выделение предварительного этапа метода ДП, что во многих случаях позволяет снизить объем вычислений и упростить их. Излагаемый в данной главе теоретический материал не имеет жесткой привязки к экономическим задачам и может быть полезен читателям широкого круга специальностей. Во второй главе приводятся примеры решения ряда типовых экономических задач методом ДП. Данной главе отведена значительная часть пособия, поскольку затруднения у студен­тов вызывает именно проведение математической формализации эко­номической задачи и практическое применение общего принципа опти­мальности. Рассматриваемые в главе задачи выбраны достаточно про­стыми, чтобы продемонстрировать существо метода ДП и довести реше­ние до конкретного числового результата, не осложняя изложение гро­моздкими вычислениями и второстепенными деталями. В третьей главе рассматриваются важные и естественные обобщения классического принципа оптимальности и метода ДП для задач, формулируемых в тер­минах теории графов. Приведенные в пособии контрольные вопросы и задачи для самостоятельного решения позволяют закрепить знания теоретического материала и приобрести навыки практического реше­ния задач. Наличие ряда вариантов исходных данных позволит исполь­зовать предложенные задачи на практических и семинарских занятиях, для домашних заданий и при проведении контрольных работ и тестов.

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

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

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

N — число шагов в многошаговом процессе, N ^ 1; г —номер шага процесса, г = 1,2,..., N. или индекс переменной или функции, указывающий их отношение к номеру шага процесса;

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

N — число шагов в многошаговом процессе, N ^ 1; г — номер шага процесса, г = 1,2,..., АГ, или индекс переменной или функции, указывающий их отношение к номеру шага процесса;

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

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

и — множество допустимых значений управляющей переменной; /г ^— функция процесса для шага с номером г; гъ — частная целевая функция на шаге с номером ц 2 — целевая функция, или критерий оптимальности для всего многошагового процесса; В_г (х_г) — функция Беллмана; щ(х_г-1) — условно-оптимальное управление.

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