Юдин Д.Б. Математические методы управления в условиях неполной информации:
Задачи и методы стохастического программирования. Изд. стереотип.

Оглавление

Предисловие

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

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

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

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

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

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

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

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

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

В приложениях стохастическое программирование используется для решения задач двух типов. В задачах первого типа прогнозируются статистические характеристики поведения множества идентичных в том или ином смысле экстремальных систем. Соответствующий раздел стохастического программирования будем называть пассивным стохастическим программированием. Модели второго типа предназначены для построения методов и алгоритмов планирования и управления в условиях неполной информации. Будем называть соответствующий раздел стохастического программирования активным стохастическим программированием, подчеркивая этим действенную целевую направленность моделей. (В некоторых работах, например в [266], термин "активное программирование" истолковывается значительно уже. Под активным стохастическим программированием иногда понимают раздел пассивного программирования, в котором рациональный выбор некоторых параметров позволяет желаемым образом воздействовать на статистические характеристики оптимального плана или оптимального значения целевой функции. Поскольку, однако, терминологию в стохастическом программировании до сих пор еще нельзя считать установившейся, представляется более естественным под активным стохастическим программированием понимать теорию и методы выбора решений в условиях неопределенности и риска).

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

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

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

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

Значительно большее разнообразие имеет место в информационной структуре динамических (многоэтапных) задач стохастического программирования. Будем рассматривать информационные структуры, порождаемые следующими двумя цепочками – процедурами последовательного анализа задачи [107]: "решение – наблюдение – решение...... – решение" и "наблюдение – решение – наблюдение-... – решение". Решающие правила и решающие распределения, отвечающие первой процедуре, 'будем называть априорными, а решающие правила и распределения, соответствующие второй цепочке, – апостериорными.

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

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

Настоящая монография содержит пятнадцать глав. В гл.1, носящей вводный характер, классифицируются постановки задач стохастического программирования, приводится краткая историческая справка и излагается вспомогательный математический аппарат. Глава 2 посвящена анализу постановок различных технических и экономических прикладных задач управления в условиях неполной информации. Содержание последующих девяти глав связано с активным подходом к стохастическому программированию-формальной основой для выбора решений в условиях неполной информации. В гл.3–5 исследуются одноэтапные 'стохастические задачи с вероятностными и статистическими ограничениями, решаемые в чистых и смешанных стратегиях, в априорных и апостериорных решающих правилах и решающих распределениях. Главы 6–8 посвящены теории и вычислительным схемам классической двухэтапной задачи стохастического программирования. В гл.9–11 описаны динамические модели управления "в условиях неполной информации-'многоэтапные задачи стохастического программирования с условными и безусловными статистическими и вероятностными ограничениями "с априорными и апостериорными решающими правилами.

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

В заключительной, 15-й главе стохастическая аппроксимация и ее обобщения рассматриваются как общие итеративные методы решения задач стохастического (программирования "по последовательным "предъявлениям наборов случайных параметров условий задачи.

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

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

При подготовке монографии предполагалось, что читатель знаком с элементами математического анализа, линейной алгебры и теории вероятностей и имеет представление об основных разделах математического программирования.

Об авторе

Юдин Давид Беркович

Доктор технических наук, профессор, заслуженный деятель науки и техники РСФСР. Участник Великой Отечественной войны. В течение ряда лет консультировал Госплан СССР. Более 35 лет являлся профессором экономического факультета МГУ имени М. В. Ломоносова; с 1994 г. — профессор Высшей школы экономики. Награжден двумя орденами и 16 медалями. В 1982 г. Международным обществом по математическому программированию и Американским математическим обществом Д. Б. Юдину присвоена премия имени Фалкерсона по дискретной математике. В 1994 г. избран действительным членом Нью-Йоркской академии наук. Автор 18 монографий по различным разделам математического программирования, по теории и методам принятия решений, а также более 200 научных работ в различных периодических изданиях.