Юдин Д.Б. Задачи и методы стохастического программирования Изд. стереотип.

Оглавление

Предисловие

1. Целенаправленная деятельность связана с решением экстремальных задач. Выбор решения в реальных ситуациях производится, как правило, в условиях неопределенности или риска при соблюдении разнообразных ограничений, определяемых конкретным содержанием задачи.

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

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

Стохастическое расширение моделей планирования, управления и проектирования связано с потерей некоторой, обычно непервостепенной важности, информации об условиях задачи. Переход к стохастическому аналогу требует, однако, получения дополнительной информации о месте изучаемой задачи в более широкой проблеме. Для построения рациональной стохастической модели процесса управления необходимо помимо статистических характеристик параметров условий располагать еще данными о порядке поступления, хранения и использования информации, о допустимой очередности выбора решения, о предпочтениях на множестве реализаций целевых функционалов и невязок в условиях задачи, о требованиях к качеству решения. Учет дополнительной информации, естественный в стохастических моделях, существенно усложняет постановку детерминированных задач. Рациональные стохастические модели управления, планирования и проектирования часто оказываются содержательнее и проще для исследования и реализации алгоритмов управления сложными системами, чем соответствующие детерминированные модели.

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

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

В одноэтапных задачах динамика поступления исходной информации не играет роли, а решение принимается один раз и не корректируется. Одноэтапные задачи различаются по показателям качества решения (по целевым функциям), по характеру ограничений и по виду решения.

Чаще других в качестве целевой функции используются вероятность попадания решения в некоторую, вообще говоря случайную, область (соответствующие модели называются Р-моделями) и математическое ожидание или дисперсия некоторых функций от решения (соответственно М-модели и V-модели).

Ограничения задачи, которые должны выполняться при всех (или при почти всех) реализациях параметров условий задачи, называются жесткими (или почти жесткими) ограничениями. В тех случаях, когда по содержательным соображениям можно допустить, чтобы невязки в условиях не превышали заданных с вероятностями, не большими alpha_i > 0, говорят о стохастических задачах с вероятностными ограничениями. Параметры alpha_i предполагаются заданными или являются решениями задачи более высокого уровня. Часто возникают ситуации, в которых постановка задачи позволяет заменить жесткие ограничения их усреднением по распределению случайных параметров. Такие ограничения называют статистическими.

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

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

Выбор вида целевой функции и ограничений и характера решения определяется, естественно, содержательным (физическим, экономическим или техническим) смыслом задачи.

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

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

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

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

3. Книга состоит из 9 глав. 1-я глава посвящена разнообразным практическим приложениям основных классов моделей стохастического программирования. В ней рассматриваются постановки стохастических задач в планировании сельскохозяйственного производства, в медицине и здравоохранении, в совершенствовании организации производства и перевозок и в других областях административной и научной деятельности, для которых характерны случайность и недостаток информации об условиях функционирования. В гл.2 излагается вспомогательный математический аппарат, используемый в других главах. Последующее содержание книги может быть разделено на четыре части, в которых исследуются одноэтапные (гл.3–5), двухэтапные (гл.6–7), многоэтапные (в том числе и бесконечноэтапные) задачи стохастического программирования (гл.8) и задачи стохастического оптимального управления (гл.9).

В гл.3 изучаются одноэтапные задачи, в которых оптимальный план не зависит от реализации случая и определяется в виде решающего правила нулевого порядка или решающего распределения нулевого порядка. Здесь рассматриваются методы построения детерминированного эквивалента стохастических задач и точные и приближенные методы анализа – методы 1-го рода, использующие информацию о статистических характеристиках случайных параметров условий задачи. Методы 1-го рода интерпретируются в содержательных терминах как методы управления в условиях риска. В гл.4 также исследуются методы решения одноэтапных стохастических задач с детерминированными планами, однако вероятностная мера, определяющая распределение условий задачи, здесь не предполагается заранее известной. В главе изучаются методы 2-го рода, использующие для решения задачи независимые одинаково распределенные наборы реализаций параметров условий. Методы 2-го рода интерпретируются в содержательных терминах как методы адаптации. Гл.5 посвящена одноэтапным задачам стохастического программирования, в которых оптимальный план определяется в виде решающего механизма – решающего правила или решающего распределения. Решающее правило представляет собой чистую стратегию принимающего решение – зависимость компонент оптимального плана от реализованных и наблюденных значений случайных параметров условий задачи. Решающее распределение представляет собой смешанную стратегию принимающего решение – распределение составляющих оптимального плана, зависящее от реализованных и наблюденных значений случайных параметров условий задачи. В гл.5 рассматриваются методы построения решающих механизмов для различных классов одноэтапных задач стохастического программирования.

В гл.6 приводятся постановка и качественный анализ одной из наиболее распространенных моделей управления в условиях неполной информации – двухэтапной задачи стохастического программирования и ее разнообразных модификаций. Гл.7 посвящена построению, обоснованию и качественной оценке методов решения линейных и нелинейных (в том числе и целочисленных) двухэтапных стохастических задач.

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

"наблюдение – решение – наблюдение-... – решение";

"решение – наблюдение – решение – ... – решение".

Решающие правила и решающие распределения, отвечающие этим цепочкам, называются соответственно апостериорными и априорными.

В гл.9 приводятся постановки и качественный анализ одноэтапных, двухэтапных и некоторых классов многоэтапных задач стохастического оптимального управления, связанных с обыкновенными дифференциальными уравнениями, и изучаются подходы к численному решению задач стохастического оптимального управления. Здесь рассматриваются разностные аппроксимации бесконечномерных задач стохастического оптимального управления и излагаются схемы и техника численного анализа этих задач.

К изучению задач стохастического программирования и его важного раздела – стохастического оптимального управления сводится решение различных проблем планирования производства и развития экономических систем, управления технологическими процессами и проектирования автоматических устройств. Современное состояние стохастического программирования позволяет считать его формальным аппаратом качественного и численного анализа сложных систем выбора решений и эффективным методом построения алгоритмов управления и адаптации. Автор приносит искреннюю благодарность Е.М.Берковичу, И.В.Евстигнееву, А.Д.Иоффе, А.С.Немировскому, Б.Т.Поляку, Э.В.Цою и А.Д.Юдину за обсуждение различных вопросов, затронутых в книге, и полезные советы.

Об авторе

Родился в Днепропетровске. Во время учебы в школе часто участвовал в городских, областных и республиканских математических олимпиадах и каждый раз попадал в число победителей. В 1936 г. по окончании 10 класса (за 9 лет) был без экзаменов зачислен на 1 курс механико-математического факультета Днепропетровского государственного университета.

С июля 1941 г. – участник Великой Отечественной войны. Демобилизовался в 1975 г. в звании инженер-полковника. В 1948 г. защитил в НИИ-5 ГАУ диссертацию на соискание ученой степени кандидата технических наук, а в 1957 г. в Академии им. Фрунзе – диссертацию на соискание ученой степени доктора технических наук. Ученое звание старшего научного сотрудника присвоено в 1951 г., профессора – в 1962 г. Награжден двумя орденами и 16 медалями. В течение ряда лет консультировал Госплан СССР. Более 35 лет являлся профессором экономического факультета МГУ, с 1994 г. – профессор Высшей школы экономики. В 1982 г. Международным обществом по математическому программированию и Американским математическим обществом присвоена премия имени Фалкерсона по дискретной математике. В 1993 г. Д. Б. Юдину присвоено звание "Заслуженный деятель науки и техники РСФСР". В 1994 г. он избран действительным членом Нью-Йоркской академии наук.

Д. Б. Юдиным опубликовано 18 монографий по различным разделам математического программирования, по теории и методам принятия решений, а также более 200 научных работ в различных периодических изданиях.