URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Юдин Д.Б. Задачи и методы стохастического программирования
Id: 111821
 
373 руб.

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

URSS. 2010. 392 с. Мягкая обложка. ISBN 978-5-396-00162-6.

 Аннотация

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

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


 Оглавление

Предисловие
Глава 1. ЗАДАЧА СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
 1.Прикладные аспекты стохастического программирования
 2.Стохастические задачи в сельском хозяйстве
 3.Стохастические задачи в медицине и здравоохранении
 4.Стохастические задачи транспортного типа
 5.Вариантные модели планирования
 6.Проектирование метода решения задач фиксированного класса
Глава 2. ВСПОМОГАТЕЛЬНЫЙ МАТЕМАТИЧЕСКИЙ АППАРАТ
 1.Теорема Вейерштрасса и смежные вопросы
 2.Основы теории вероятностей и теории меры
 3.Элементы выпуклого анализа
 4.Измеримый выбор
 5.Обобщенная теорема Кастена
 6.Условия полунепрерывности и непрерывности функционалов, определяющих одноэтапные М-модели и Р-модели
Глава 3. ОДНОЭТАПНЫЕ ЗАДАЧИ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ АПРИОРНЫЕ РЕШАЮЩИЕ МЕХАНИЗМЫ
 1.Детерминированный эквивалент задач с вероятностными ограничениями
 2.Приближенное построение детерминированных эквивалентов стохастических задач
 3.Стохастические модели, порожденные линейно-упорядоченными семействами множеств
 4.Условия выпуклости детерминированного эквивалент
 5.Решающие распределения нулевого порядка
Глава 4. ОДНОЭТАПНЫЕ СТОХАСТИЧЕСКИЕ ЗАДАЧИ С ДЕТЕРМИНИРОВАННЫМИ ПЛАНАМИ МЕТОДЫ 2-ГО РОДА
 1.Постановка задачи
 2.Метод усреднения для стохастических задач при локально-полном информационном отображении
 3.Решение стохастических задач при локально-точечном информационном отображении
 4.Итеративные методы решения стохастических задач (стохастическая аппроксимация в задачах стохастического программирования)
Глава 5. ОДНОЭТАПНЫЕ ЗАДАЧИ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ РЕШАЮЩИЕ ПРАВИЛА И РЕШАЮЩИЕ РАСПРЕДЕЛЕНИЯ
 1.Квадратичные стохастические задачи
 2.Примеры
 3.Одноэтапная задача с почти жесткими ограничениями
 4.Некоторые общие приемы построения решающих правил
 5.Решающие правила задач целочисленного стохастического программирования
 6.Достаточные условия существования решающих правил
 7.Решающие распределения
Глава 6. ДВУХЭТАПНАЯ ЗАДАЧА СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ -- КАЧЕСТВЕННЫЙ АНАЛИЗ
 1.Постановка линейной двухэтапной задачи
 2.Свойства Q (omega, х) и Q (х)
 3.Условия сильной регулярности и сильной стохастичности двухэтапной задачи
 4.Качественный анализ двухэтапной задачи
 5.Условия разрешимости задачи 2-го этапа
 6.Частные двухэтапные стохастические задачи
 7.Нелинейная двухэтапная задача. I
 8.Нелинейная двухэтапная задача. II
 9.Двухэтапная задача стохастическго программирования в минимаксной постановке
Глава 7. ДВУХЭТАПНАЯ ЗАДАЧА СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ. МЕТОДЫ РЕШЕНИЯ
 1.Методы 2-го рода решения двухэтапных стохастических задач
 2.Метод секущих плоскостей
 3.Метод возможных направлений
 4.Оценки
 5.Целочисленная двухэтапная задача
Глава 8 МНОГОЭТАПНЫЕ ЗАДАЧИ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
 1.Введение
 2.Теорема существования решения многоэтапных стохастических задач (формулировка и идея доказательства)
 3.Вспомогательные утверждения
 4.Доказательство теоремы существования решения многоэтапной стохастической задачи
 5.Содержательные аспекты информационных структур
 6.Марковское программирование
 7.Выпуклые стохастические задачи произвольной информационной структуры
 8.Решающие распределения и решающие правила многоэтапных задач стохастического программирования
 9.Априорные решающие правила многоэтапных задач с жесткими ограничениями
Глава 9. СТОХАСТИЧЕСКОЕ ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
 1.Постановка задач стохастического оптимального управления
 2.Теоремы существования решения задач стохастического оптимального управления
 3.Аппроксимация одноэтапных задач стохастического оптимального управления
 4.Аппроксимация многоэтапных задач стохастического оптимального управления
 5.Общая схема численного решения одноэтапных задач стохастического оптимального управления
 6.Схема численного решения двухэтапных задач стохастического оптимального управления
 7.Схемы решения двухэтапных задач с фазовыми ограничениями на 2-м этапе
 8.Схема численного решения линейных по фазовым переменным многоэтапных задач стохастического оптимального управления
Вместо послесловия
Список литературы
Предметный указатель

 Предисловие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 Об авторе

Давид Беркович ЮДИН (1919--2006)

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

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

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

 
© URSS 2016.

Информация о Продавце