Содержание к диссертации
Введение
Глава 1. Многокритериальные "непрерывные" динамические задачи при неопределенности 14
1. Постановка задачи. Формализация решения 14
2. Векторные гарантии 18
3. Гарантированные решения 25
4. Необходимые условия 30
5. К оптимизации распределения капитальных вложений между отраслями 39
6. Линейно-квадратичная двухкритериальная задача 50
Глава 2. Многошаговые многокритериальные задачи при неопределенности 60
7. Постановка задачи. Формализация решения 60
8. Необходимые и достаточные условия 63
9. Линейно-квадратичная задача 73
10. Существование SS -седловой точки 77
11. Применение динамического программирования 79
12. Задача управления добычей некоторого биологического вида 88
Глава 3. Существование гарантированных решений 94
13. Постановка задачи 94
14. Сведение к антагонистической игре 103
15. Существование G-решения гарантированного по G 116
Заключение 124
Литература 125
- К оптимизации распределения капитальных вложений между отраслями
- Линейно-квадратичная двухкритериальная задача
- Применение динамического программирования
- Существование G-решения гарантированного по G
Введение к работе
Разумная человеческая деятельность в большинстве случаев состоит в том, что человеку для достижения тех или иных целей приходится принимать решения. При этом представляется вполне естественным стремление принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. Проблемы, связанные с выбором оптимальных решений, встречаются в экологии, военном деле, экономике, технике и т.д. По мере развития и математизации этих сфер человеческой деятельности соответствующие процессы принятия решений формализуются и приобретают характер математических моделей. Математическая модель отражает проблему принятия решений в абстрактной форме и позволяет учесть большое число разнообразных характеристик, от которых зависит функционирование конкретного объекта управления. Анализ и расчет математической модели позволяют выбрать оптимальные решения поставленной задачи и обосновать этот выбор.
Теория математических моделей принятия оптимальных решений составляет содержание исследования операций. Задачи исследования операций можно классифицировать по уровню информации о ситуации, которой располагает лицо, принимающее решения (ЛПР) [52, с.7]:
детерминированные - в этих задачах условия, в которых принимаются решения, известны полностью;
стохастические, в которых известно множество возможных вариантов условий и их вероятностное распределение;
неопределенные, когда известно множество возможных вариантов, но без какой-либо информации об их вероятностях. Такой уровень информации о ситуации является наиболее сложным, так как могут быть не ясны сами принципы оптимального поведения.
Методы решения задач первых двух типов изучаются в курсах математического программирования. При этом на первый план выходит изучение динамических систем. Исследованием таких задач занимается математическая теория оптимального управления. Основы этой теории были заложены в конце 50-х годов академиком Л.С. Понтрягиным
и его учениками [54], центральным, стержневым результатом здесь является принцип максимума. Большая значимость и популярность этого подхода привели к тому, что и в теории дискретных задач оптимизации (широкий интерес к которым возник несколько позже) были в первую очередь предприняты попытки найти дискретный аналог принципа максимума.
Одновременно был создан новый подход к решению задач оптимального управления - метод динамического программирования, - предложен американским математиком Р. Беллманом [3].
Математический аппарат теории дискретных оптимальных процессов развит в трудах В.Г. Болтянского [5], Л.И. Розоноэра [58], Ф.М. Кирилловой и Р. Габасова [12, 13], А.И. Пропоя [55], Р. Ариса [2] и др.
Эволюция теории оптимального управления происходит преимущественно в направлении изучения все более сложных систем. Одним из таких усложнений является увеличение числа оптимизируемых параметров, поскольку целенаправленное функционирование многих систем по своей природе многокритериально. Такие задачи возникают, например, в экономике, когда в процессе функционирования предприятия одновременно ставятся разные цели: добиться максимально возможных прибыли и выпуска продукции в натуральном или стоимостном выражении, одновременно с этим выдержать установленные показатели по номенклатуре или ассортименту, снизить себестоимость, добиться определенного уровня качества и рентабельности производимой продукции и т.д. Некоторые из этих показателей по тенденциям их реализации могут быть противоречивыми. В этом случае необходимо искать разумный компромисс, когда для принятого плана производства не достигаются потенциально возможные оптимальные значения отдельных целевых критериев, но каждый из них для этого плана принимает в той или иной мере близкое к оптимальному значение. Наличие нескольких критериев во многих прикладных задачах послужило причиной для возникновения нового направления - теории многокритериальных задач.
Основы теории многокритериальной оптимизации - в работах итальянского экономиста В. Парето (1848 - 1923). Одним из основных понятий этой теории является понятие оптимального по Парето или эффективного решения. Оно представляет собой обобщение понятия максимума числовой функции на случай нескольких функций: решение Парето-оптимально, если значение любого из критериев можно улучшить лишь за счет ухудшения значений хотя бы одного из остальных критериев.
На первых порах изучались статические задачи [53],[72],[79]. Однако запросы практики вскоре потребовали исследования и динамических многокритериальных систем управления [28].
Математические модели "классической" теории многокритериальных задач охватывают обычно идеальные системы, в которых каждому решению отвечает единственное значение каждого критерия. Однако в реальных системах данное условие часто не выполняется. Типичной является ситуация, когда относительно некоторых параметров системы или внешних воздействий известны лишь границы их изменения, внутри которых эти параметры могут принимать любое, заранее непредсказуемое значение. Так, например, при планировании выпуска продукции не всегда можно учесть сбои в обеспечении сырьем, брак, поломки оборудования и т.д. Поэтому решения приходится принимать, считаясь с воздействиями неконтролируемых факторов - неопределенностей. Многокритериальные задачи при неопределенности — новое активно развивающееся направление теории принятия решений.
Для однокритериальных (скалярных) задач при неопределенности в 50-х годах прошлого века были созданы несколько принципов, на основе которых могут быть построены оптимальные решения [40]. К ним относятся - принцип гарантированного результата (максиминной полезности или принцип Вальда), принцип минимаксного сожаления (принцип Сэвиджа), принцип пессимизма-оптимизма (принцип Гурвица) и др. До сих пор основные исследования многокритериальных задач при неопределенности ведутся в рамках подходящей модификации принципа гарантированного результата. Динамический вариант таких задач в позиционных стратегиях активно исследуется в России профессором В.И. Жуковским [26],[28],[29], [91] и его учениками B.C. Молоствовым [27], Г.И. Житомирским [23], В.А. Матвеевым [41], В.В. Мухиным [45], И.В. Чернявским [69]. Параллельно за рубежом ведутся работы по исследованию статического варианта: работы F. Ferro [76],[77], О. Blackwell [71], Т. Tanaka [87],[88],[89] W.L. Chan и W.T. Lau [73], G.Y. Chen [74], J.G. Lin [80]. Однако в вопросах прогнозирования и планирования актуальным является исследование динамических многокритериальных задач с программными управлениями и неопределенностями, а также соответствующих многошаговых задач. Именно таким задачам и посвящена диссертация.
Неопределенность занимает особое место среди условий, в которых приходится принимать решения. Это особое положение определяется,
в первую очередь, практической необходимостью принимать решения в условиях, когда не удается полностью учесть влияние каких-либо факторов. Такая ситуация встречается в подавляющем большинстве областей техники, экономики, экологии и социальных науках. При этом наличие неопределенности приводит к тому, что нельзя однозначно определить понятие решения многокритериальной задачи, а можно лишь указать "разумные, или хорошие в разных отношениях" решения. Поэтому необходимо стремиться к оптимальному использованию имеющейся информации относительно поставленной задачи, чтобы, взвесив все возможные варианты решений, постараться найти среди них наилучший.
Отметим, что задачи принятия решений при неопределенности (в том числе и многокритериальные) связаны с теорией игр. Следуя определению Н.Н. Воробьева, теория игр - это теория математических моделей принятия оптимальных решений в условиях неопределенности, когда принимающий решение субъект ("игрок") располагает информацией лишь о множестве возможных ситуаций, в одной из которых он в действительности находится, о множестве решений (стратегий), которым он может следовать, и о количественной мере того "выигрыша", который он мог бы получить, выбрав данную стратегию (Воробьев Н.Н. Философская энциклопедия- Т.5. - М., 1970, - С.208 - 210). Задачу принятия решений в условиях неопределенности зачастую можно трактовать как конфликтную ситуацию для двух игроков, одним из которых является ЛПР, а в качестве второго игрока рассматривается гипотетический индивид, формирующий неопределенность. При этом, если придерживаться принципа гарантированного результата (или его модификаций для многокритериальных задач), то следует считать, что второй игрок стремится всячески навредить первому, препятствуя достижению его целей.
Теория игр возникла вначале XX века и первые ее результаты систематически изложены в известной монографии Джона фон Неймана и Оскара Моргенштерна (на русском языке - [68]), опубликованной в 1944 году. Первые этапы развития теории игр были посвящены изучению "статических" игр , в них не учитывалась динамка объекта управления, но уже во второй половине XX века начинает активно развиваться теория динамических игр - дифференциальных ([1],[17], [36],[43],[47],[48],[20] - [22], [24],[31], др.)? многошаговых ([19],[70],[75] и др.). Результаты и подходы теории игр широко используются в исследовании многокритериальных задач при неопределенности.
Теперь перейдем к непосредственному рассмотрению динамической многокритериальной задачи при неопределенности (ДМЗН). Под ДМЗН обычно понимают упорядоченный набор
(s,w, я, W(tf,s)}*N>- (0.1)
В (0.1) символом Е обозначается управляемая динамическая система (объект). В экономике это могут быть промышленные предприятия, разного рода объединения, супермаркеты и так далее, в экологии - те же предприятия, очистные сооружения или среда обитания определенных биологических видов, в механике - группа кораблей, самолетов. Предполагают обычно, что функционирование объекта происходит на заданном временном интервале - от фиксированного момента начала to > 0 до фиксированного момента окончания процесса & > о При этом, если информация о состоянии объекта Е и управление процессом осуществляются "непрерывно" в каждый момент t Є [()>$)> то такую ДМЗН будем, следуя [5], называть "непрерывной". Если же информация о состоянии процесса и управление процессом осуществляются в дискретные моменты времени о,о + 1,о + 2,...,$ — 1, т.е. по шагам, то соответствующая ДМЗН называется многошаговой или дискретной. Множество указанных выше моментов времени, в которые возможно влиять на состояние системы, обозначим через 0, тогда для "непрерывных" задач 0 = [to, її) , а для дискретных ДМЗН будет 0 = {о> to + 1,...,^ — 1}.
Параметры (состояние) объекта Е в каждый момент времени t Є 0 описываются фазовым п -вектором x(t). Под влиянием управляющих воздействий ЛПР и неопределенностей фазовый вектор х Є Rn изменяется во времени. Это изменение описывается дифференциальным (в случае "непрерывной" ДМЗН) или конечно-разностным (в случае многошаговой ДМЗН) уравнением.
В каждый момент времени t Є 0 ЛПР выбирает и реализует решения на основе некоторой информации о текущем и / или предыдущих значениях фазового вектора. Подобной информацией может обладать и неопределенность. Ту информацию, которой владеет ЛПР на момент времени t обозначим через rf\ ? а ТУ> которая присуща неопределенности — через п\ Тогда множества
Фі = {*?!,* 0},
ф2 = Н.*єе}
определяют информационную структуру конкретной ДМЗН. При этом, если
*i = Ы ri) = {х(к),к< t},t e},j = 1,2, (0.2)
то соответствующая ДМЗН называется позиционной. Если же
ф> = Н : ^ = *(*о),* Є 0} ,i = 1,2, (0.3)
то ДМЗН называется задачей с программными управлениями и неопределенностями.
Через U в (0.1) обозначено множество управлений, выбором которых
распоряжается Л ПР. Конкретный элемент множества U обозначим че
рез U. В экономических и экологических задачах управлениями могут
быть штрафы, премии, объем инвестиций или производства, внедрение
новых технологий и т.д., в механических - угол поворота руля. ЛПР,
обладая той или иной информацией о состоянии системы Е, выбирает
конкретное управление U eU. При этом, если информационная струк
тура задачи имеет вид (0.2), то управление формируется как функция
времени и состояния, то есть »
и + ч(г,х), tee,
если же информационная структура имеет вид (0.3), то управление является функцией только времени, а именно
U -f 7(0» teQ. ,
Множество Z состоит из неопределенностей Z, о которых ЛПР в каждый момент і G 0 известна лишь область возможных значений. В экономических системах появление неопределенностей может быть вызвано как внешними факторами (недопоставки сырья, появление новых технологий, появление конкурентов), так и внутренними (срыв планируемых сроков пуска технологической линии, поломка оборудования, брак), в механических системах причиной возмущений могут быть температурные, погодные условия. Отметим, что неопределенности отождествляются с функциями, зависящими от времени t и состояния системы X , то есть
Z + X{t,x>), tee
("позиционные неопределенности") или с функциями, зависящими только от времени t:
z + x(t), tee
("программные неопределенности").
В результате воздействия управления U Є Ы и неопределенности Z Z на Е, система Е "вырабатывает" величины Ji(U,Z), і N = = {1,2,..., JV}, - критерии, характеризующие эффективность процесса управления "с точки зрения" ЛПР. Примем, что в интересах ЛПР выбрать такое управление U Є U, чтобы добиться одновременно возможно больших значений каждого из JV критериев. При этом ЛПР должен каким-то образом учесть возможность реализации любой, заранее непредсказуемой неопределенности Z Є 2.
Под решением ДМЗН будем понимать конкретное управление U* Є Є U, которое следует выбрать лицу, принимающему решение (ЛПР) и векторную гарантию J* = (Jj,..., Jjy) Є R^, которую ЛПР "обеспечивает себе", следуя управлению U*. Каждая компонента J*,i Є N, вектора J* определяет то гарантированное значение соответствующего критерия Ji(U, Z), і Є N, на которое ЛПР может рассчитывать при реализации любой неопределенности Z Є Z.
Одним из возможных подходов к формализации такого решения является применение принципа гарантированного результата к каждому критерию Jj(i7,Z),i Є N, в отдельности, а именно:
Определение. Вектор J9 = («/f,...,^j\r) называется минимальной векторной гарантией в задаче (0.1) при фиксированном управлении U* Є U, если
Jf = min Ji{U\Z)y »N. (0.4)
Недостатком данного определения является то, что, как правило, минимум в каждом из N равенств (0.4) достигается на разных неопределенностях Z^ Є Z:
min Ji(U*, Z) = Ji(U\ ZW), і Є N.
Однако в задаче (0.1) реализуется лишь одна из неопределенностей. Поэтому в диссертации рассматриваются только те векторные гарантии, которые реализуются на одной и той же неопределенности. Такой подход был предложен профессором В.И. Жуковским [91] и связан с применением понятий векторных минимумов (по Слейтеру, Парето, Борвей-ну, Джоффриону и А-минимума) из теории многокритериальных задач. Именно данный подход и применяется в диссертации.
Целью работы является исследование гарантированных решений в динамических многокритериальных задачах с программными управлениями и неопределенностями, причем предполагается, что о неопределенностях известна лишь область возможных значений.
Объектом исследования являются динамические многокритериальные задачи принятия решений в условиях неопределенности.
Предмет исследования - векторные седловые точки, реализующие гарантированные решения в "непрерывных" и многошаговых ДМЗН.
Проблема заключается в способе формализации гарантированных решений ДМЗН с программными управлениями и неопределенностями и в поиске методов построения векторных седловых точек, реализующих такие решения.
В основу исследования положена следующая гипотеза: на основе модификации принципа гарантированного результата и понятий опти-мумов по Слейтеру, Парето, Борвейну, Джоффриону и А-оптимума из теории многокритериальных задач можно, следуя [91], определить возможные решения ДМЗН и соответствующие векторные седловые точки, реализующие эти решения; основываясь на результатах из теории многокритериальных задач, теории игр и оптимального управления можно установить существование указанных седловых точек (а, следовательно, и гарантированных решений ДМЗН) и предложить способ их нахождения.
Для реализации поставленной цели и проверки сформулированной гипотезы потребовалось решить следующие задачи:
формализовать понятия гарантированных решений для ДМЗН с программными управлениями и неопределенностями и векторных седловых точек, реализующих такие решения;
установить связь гарантированных решений ДМЗН с равновесным решением специально построенной бескоалиционной игры двух лиц;
выявить условия существования таких решений для "непрерывных" и дискретных ДМЗН с программными управлениями и неопределенностями;
найти методы построения гарантированных решений, используя аппарат принципа максимума Л.С. Понтрягина;
построить управление и неопределенность, реализующие гарантированное решение для линейно-квадратичных "непрерывной" и многошаговой задач;
рассмотреть возможные приложения к конкретным экономическим задачам.
Методологическую основу работы составляют методы и подходы теории многокритериальных задач, теории игр, выпуклого анализа, теории матриц и квадратичных форм, дифференциальных и конечно-разностных уравнений, теории оптимального управления.
Научная новизна. До сих пор исследования ДМЗН велись в рамках "непрерывных" позиционных задач. Динамические "непрерывные" многокритериальные задачи при неопределенности с программными управлениями и неопределенностями, а также соответствующих многошаговые ДМЗН не рассматривались. Как раз этим вопросам посвящена диссертация. Поэтому результаты работы являются новыми.
Практическая значимость работы. Рассмотренный подход к определению решения для ДМЗН и предложенные способы построения гарантированных решений могут быть применены к различным прикладным задачам прогнозирования и планирования в экономике, экологии, механике управляемых систем. В качестве приложения в диссертации рассматривается математическая модель задачи оптимизации размещения капитальных вложений и задача добычи некоторого биологического вида.
Основные положения, выносимые на защиту:
формализовано понятие гарантированного решения для "непрерывных" и многошаговых ДМЗН с программными управлениями и неопределенностями;
выделен класс "непрерывных" ДМЗН, в которых существует гарантированное по Джоффриону решение;
найдены условия существования гарантированного по Слейтеру решения для многошаговых ДМЗН;
сформулированы необходимые условия существования седловых точек по Слейтеру в форме принципа максимума;
найден явный вид седловой точки по Слейтеру в "непрерывной и многошаговой линейно-квадратичных ДМЗН, при этом были использованы необходимые условия и (для одной многошаговой задачи) метод динамического программирования;
полученные результаты применены к построению гарантированных решений в двух конкретных экономических задачах.
Апробация. Результаты диссертации докладывались на научных семинарах кафедры математики и механики РосЗИТЛП, на научно-методическом семинаре кафедры информатики и дискретной математики МПГУ, на Международной школе по динамическим и управляемым системам (Суздаль, 2001), на Международной конференции по проблемам управления "Автоматика - 2001" (Одесса, 2001), на XII Крымской осенней математической школе-симпозиуме (Крым, Севастополь, 2001).
Перейдем к краткому изложению содержания диссертации. Диссертация состоит из трех глав, разбитых на пятнадцать параграфов.
В первой главе (1 — 6) вводятся гарантированные решения в "непрерывной" ДМЗН с программными управлениями и неопределенностями, исследуются седловые точки, реализующие эти решения. Именно, в 1 определяются основные составляющие элементы "непрерывной" ДМЗН, описывается процесс принятия решения, определяются цели, на достижение которых направлен процесс управления, приводится определение векторной гарантии. В 2 рассматриваются различные виды векторных гарантий, определенных на основе понятий минимумов по Слейтеру, Парето, Борвейну, Джоффриону, А-минимума из теории многокритериальных задач. В третьем параграфе, следуя [91], формализуются возможные решения ДМЗН и векторные седловые точки, реализующие эти решения, устанавливается связь между приведенными решениями и седловыми точками. Необходимым и достаточным условиям существования SS -седловых точек, реализующих гарантированное по Слейтеру решение ДМЗН, посвящен 4. Здесь же предложен способ нахождения SS -седловых точек, основанный на применении аппарата принципа максимума Понтрягина, приведены условия, при выполнении которых принцип максимума является не только необходимым, но и достаточным условием существования указанных седловых точек. Утверждения и алгоритмы из 4 применены в следующих двух параграфах для на-
хождения седловых точек в конкретных задачах. Именно, в 5 рассмотрена задача оптимизации распределения капитальных вложений между отраслями и для нее найдена SS -седловая точка, а в 6 найден явный вид АчА\ -седловой точки в линейно-квадратичной двухкритериальной задаче.
Содержание второй главы ( 7-12) составляет формализация гарантированных решений и исследование векторных седловых точек, реализующих эти решения в многошаговых ДМЗН. В 7 - постановка задачи, описание процесса управления, формализация предлагаемого решения. В 8 устанавливаются необходимые и достаточные условия существования SS -седловых точек, реализующих 5-решение гарантированное по S (по Слейтеру), в форме принципа максимума. В 9 выделен класс задач, в которых существует SS -седловая точка. Далее необходимые и достаточные условия из 8 применяются в 10 для нахождения явного вида SS -седловой точки в одной линейно-квадратичной двухкритериальной задаче. В 11 для другой линейно-квадратичной N -критериальной задачи седловая точка найдена с помощью метода динамического программирования. В заключении второй главы в 12 рассмотрена задача "разумной" добычи некоторого биологического вида (например, рыбы из водоема), для которой найден явный вид SS-седловой точки, реализующей предложенное гарантированное решение.
В третьей главе выделен класс "непрерывных" ДМЗН, в которых существует G -решение гарантированное по G (по Джоффриону). В 13 рассматриваются ограничения на управляемую систему, управления, неопределенности и критерии, и исходной задаче ставится в соответствие специальная вспомогательная бескоалиционная игра двух лиц (без неопределенности). В следующем 14 для указанной бескоалиционной игры строится специальная антагонистическая игра. Приводятся условия существования седловой точки антагонистической дифференциальной игры в двух случаях: когда заданы ограничения на множества стратегий игроков, и когда такие ограничения отсутствуют. Устанавливается связь равновесной ситуации бескоалиционной игры с седловой точкой построенной антагонистической игры. Основываясь на результатах предыдущих параграфов в 15 установлены условия существования G -решения гарантированного по G (по Джоффриону) в исходной задаче.
Основные результаты исследований опубликованы в работах
[60] - [65], [84] - [86], [90].
К оптимизации распределения капитальных вложений между отраслями
Методы решения задач первых двух типов изучаются в курсах математического программирования. При этом на первый план выходит изучение динамических систем. Исследованием таких задач занимается математическая теория оптимального управления. Основы этой теории были заложены в конце 50-х годов академиком Л.С. Понтрягиным и его учениками [54], центральным, стержневым результатом здесь является принцип максимума. Большая значимость и популярность этого подхода привели к тому, что и в теории дискретных задач оптимизации (широкий интерес к которым возник несколько позже) были в первую очередь предприняты попытки найти дискретный аналог принципа максимума.
Одновременно был создан новый подход к решению задач оптимального управления - метод динамического программирования, - предложен американским математиком Р. Беллманом [3].
Математический аппарат теории дискретных оптимальных процессов развит в трудах В.Г. Болтянского [5], Л.И. Розоноэра [58], Ф.М. Кирилловой и Р. Габасова [12, 13], А.И. Пропоя [55], Р. Ариса [2] и др.
Эволюция теории оптимального управления происходит преимущественно в направлении изучения все более сложных систем. Одним из таких усложнений является увеличение числа оптимизируемых параметров, поскольку целенаправленное функционирование многих систем по своей природе многокритериально. Такие задачи возникают, например, в экономике, когда в процессе функционирования предприятия одновременно ставятся разные цели: добиться максимально возможных прибыли и выпуска продукции в натуральном или стоимостном выражении, одновременно с этим выдержать установленные показатели по номенклатуре или ассортименту, снизить себестоимость, добиться определенного уровня качества и рентабельности производимой продукции и т.д. Некоторые из этих показателей по тенденциям их реализации могут быть противоречивыми. В этом случае необходимо искать разумный компромисс, когда для принятого плана производства не достигаются потенциально возможные оптимальные значения отдельных целевых критериев, но каждый из них для этого плана принимает в той или иной мере близкое к оптимальному значение. Наличие нескольких критериев во многих прикладных задачах послужило причиной для возникновения нового направления - теории многокритериальных задач.
Основы теории многокритериальной оптимизации - в работах итальянского экономиста В. Парето (1848 - 1923). Одним из основных понятий этой теории является понятие оптимального по Парето или эффективного решения. Оно представляет собой обобщение понятия максимума числовой функции на случай нескольких функций: решение Парето-оптимально, если значение любого из критериев можно улучшить лишь за счет ухудшения значений хотя бы одного из остальных критериев. На первых порах изучались статические задачи [53],[72],[79]. Однако запросы практики вскоре потребовали исследования и динамических многокритериальных систем управления [28].
Математические модели "классической" теории многокритериальных задач охватывают обычно идеальные системы, в которых каждому решению отвечает единственное значение каждого критерия. Однако в реальных системах данное условие часто не выполняется. Типичной является ситуация, когда относительно некоторых параметров системы или внешних воздействий известны лишь границы их изменения, внутри которых эти параметры могут принимать любое, заранее непредсказуемое значение. Так, например, при планировании выпуска продукции не всегда можно учесть сбои в обеспечении сырьем, брак, поломки оборудования и т.д. Поэтому решения приходится принимать, считаясь с воздействиями неконтролируемых факторов - неопределенностей. Многокритериальные задачи при неопределенности — новое активно развивающееся направление теории принятия решений.
Для однокритериальных (скалярных) задач при неопределенности в 50-х годах прошлого века были созданы несколько принципов, на основе которых могут быть построены оптимальные решения [40]. К ним относятся - принцип гарантированного результата (максиминной полезности или принцип Вальда), принцип минимаксного сожаления (принцип Сэвиджа), принцип пессимизма-оптимизма (принцип Гурвица) и др. До сих пор основные исследования многокритериальных задач при неопределенности ведутся в рамках подходящей модификации принципа гарантированного результата. Динамический вариант таких задач в позиционных стратегиях активно исследуется в России профессором В.И. Жуковским [26],[28],[29], [91] и его учениками B.C. Молоствовым [27], Г.И. Житомирским [23], В.А. Матвеевым [41], В.В. Мухиным [45], И.В. Чернявским [69]. Параллельно за рубежом ведутся работы по исследованию статического варианта: работы F. Ferro [76],[77], О. Blackwell [71], Т. Tanaka [87],[88],[89] W.L. Chan и W.T. Lau [73], G.Y. Chen [74], J.G. Lin [80]. Однако в вопросах прогнозирования и планирования актуальным является исследование динамических многокритериальных задач с программными управлениями и неопределенностями, а также соответствующих многошаговых задач. Именно таким задачам и посвящена диссертация.
Линейно-квадратичная двухкритериальная задача
Неопределенность занимает особое место среди условий, в которых приходится принимать решения. Это особое положение определяется, в первую очередь, практической необходимостью принимать решения в условиях, когда не удается полностью учесть влияние каких-либо факторов. Такая ситуация встречается в подавляющем большинстве областей техники, экономики, экологии и социальных науках. При этом наличие неопределенности приводит к тому, что нельзя однозначно определить понятие решения многокритериальной задачи, а можно лишь указать "разумные, или хорошие в разных отношениях" решения. Поэтому необходимо стремиться к оптимальному использованию имеющейся информации относительно поставленной задачи, чтобы, взвесив все возможные варианты решений, постараться найти среди них наилучший.
Отметим, что задачи принятия решений при неопределенности (в том числе и многокритериальные) связаны с теорией игр. Следуя определению Н.Н. Воробьева, теория игр - это теория математических моделей принятия оптимальных решений в условиях неопределенности, когда принимающий решение субъект ("игрок") располагает информацией лишь о множестве возможных ситуаций, в одной из которых он в действительности находится, о множестве решений (стратегий), которым он может следовать, и о количественной мере того "выигрыша", который он мог бы получить, выбрав данную стратегию (Воробьев Н.Н. Философская энциклопедия- Т.5. - М., 1970, - С.208 - 210). Задачу принятия решений в условиях неопределенности зачастую можно трактовать как конфликтную ситуацию для двух игроков, одним из которых является ЛПР, а в качестве второго игрока рассматривается гипотетический индивид, формирующий неопределенность. При этом, если придерживаться принципа гарантированного результата (или его модификаций для многокритериальных задач), то следует считать, что второй игрок стремится всячески навредить первому, препятствуя достижению его целей.
Теория игр возникла вначале XX века и первые ее результаты систематически изложены в известной монографии Джона фон Неймана и Оскара Моргенштерна (на русском языке - [68]), опубликованной в 1944 году. Первые этапы развития теории игр были посвящены изучению "статических" игр , в них не учитывалась динамка объекта управления, но уже во второй половине XX века начинает активно развиваться теория динамических игр - дифференциальных ([1],[17], [36],[43],[47],[48],[20] - [22], [24],[31], др.)? многошаговых ([19],[70],[75] и др.). Результаты и подходы теории игр широко используются в исследовании многокритериальных задач при неопределенности. Теперь перейдем к непосредственному рассмотрению динамической многокритериальной задачи при неопределенности (ДМЗН). Под ДМЗН обычно понимают упорядоченный набор
В (0.1) символом Е обозначается управляемая динамическая система (объект). В экономике это могут быть промышленные предприятия, разного рода объединения, супермаркеты и так далее, в экологии - те же предприятия, очистные сооружения или среда обитания определенных биологических видов, в механике - группа кораблей, самолетов. Предполагают обычно, что функционирование объекта происходит на заданном временном интервале - от фиксированного момента начала to 0 до фиксированного момента окончания процесса & о При этом, если информация о состоянии объекта Е и управление процессом осуществляются "непрерывно" в каждый момент t Є [() $) то такую ДМЗН будем, следуя [5], называть "непрерывной". Если же информация о состоянии процесса и управление процессом осуществляются в дискретные моменты времени о,о + 1,о + 2,...,$ — 1, т.е. по шагам, то соответствующая ДМЗН называется многошаговой или дискретной. Множество указанных выше моментов времени, в которые возможно влиять на состояние системы, обозначим через 0, тогда для "непрерывных" задач 0 = [to, її) , а для дискретных ДМЗН будет 0 = {о to + 1,..., — 1}.
Параметры (состояние) объекта Е в каждый момент времени t Є 0 описываются фазовым п -вектором x(t). Под влиянием управляющих воздействий ЛПР и неопределенностей фазовый вектор х Є Rn изменяется во времени. Это изменение описывается дифференциальным (в случае "непрерывной" ДМЗН) или конечно-разностным (в случае многошаговой ДМЗН) уравнением. В каждый момент времени t Є 0 ЛПР выбирает и реализует решения на основе некоторой информации о текущем и / или предыдущих значениях фазового вектора. Подобной информацией может обладать и неопределенность. Ту информацию, которой владеет ЛПР на момент времени t обозначим через rf\ а ТУ которая присуща неопределенности — через п\ Тогда множества определяют информационную структуру конкретной ДМЗН. При этом, если то соответствующая ДМЗН называется позиционной. Если же то ДМЗН называется задачей с программными управлениями и неопределенностями. Через U в (0.1) обозначено множество управлений, выбором которых распоряжается Л ПР. Конкретный элемент множества U обозначим че рез U. В экономических и экологических задачах управлениями могут быть штрафы, премии, объем инвестиций или производства, внедрение новых технологий и т.д., в механических - угол поворота руля. ЛПР, обладая той или иной информацией о состоянии системы Е, выбирает конкретное управление U eU.
Применение динамического программирования
Проблема заключается в способе формализации гарантированных решений ДМЗН с программными управлениями и неопределенностями и в поиске методов построения векторных седловых точек, реализующих такие решения.
В основу исследования положена следующая гипотеза: на основе модификации принципа гарантированного результата и понятий опти-мумов по Слейтеру, Парето, Борвейну, Джоффриону и А-оптимума из теории многокритериальных задач можно, следуя [91], определить возможные решения ДМЗН и соответствующие векторные седловые точки, реализующие эти решения; основываясь на результатах из теории многокритериальных задач, теории игр и оптимального управления можно установить существование указанных седловых точек (а, следовательно, и гарантированных решений ДМЗН) и предложить способ их нахождения.
Для реализации поставленной цели и проверки сформулированной гипотезы потребовалось решить следующие задачи: - формализовать понятия гарантированных решений для ДМЗН с программными управлениями и неопределенностями и векторных седловых точек, реализующих такие решения; - установить связь гарантированных решений ДМЗН с равновесным решением специально построенной бескоалиционной игры двух лиц; - выявить условия существования таких решений для "непрерывных" и дискретных ДМЗН с программными управлениями и неопределенностями; - найти методы построения гарантированных решений, используя аппарат принципа максимума Л.С. Понтрягина; - построить управление и неопределенность, реализующие гарантированное решение для линейно-квадратичных "непрерывной" и многошаговой задач; - рассмотреть возможные приложения к конкретным экономическим задачам. Методологическую основу работы составляют методы и подходы теории многокритериальных задач, теории игр, выпуклого анализа, теории матриц и квадратичных форм, дифференциальных и конечно-разностных уравнений, теории оптимального управления. Научная новизна. До сих пор исследования ДМЗН велись в рамках "непрерывных" позиционных задач. Динамические "непрерывные" многокритериальные задачи при неопределенности с программными управлениями и неопределенностями, а также соответствующих многошаговые ДМЗН не рассматривались. Как раз этим вопросам посвящена диссертация. Поэтому результаты работы являются новыми. Практическая значимость работы. Рассмотренный подход к определению решения для ДМЗН и предложенные способы построения гарантированных решений могут быть применены к различным прикладным задачам прогнозирования и планирования в экономике, экологии, механике управляемых систем. В качестве приложения в диссертации рассматривается математическая модель задачи оптимизации размещения капитальных вложений и задача добычи некоторого биологического вида. Основные положения, выносимые на защиту: формализовано понятие гарантированного решения для "непрерывных" и многошаговых ДМЗН с программными управлениями и неопределенностями; выделен класс "непрерывных" ДМЗН, в которых существует гарантированное по Джоффриону решение; найдены условия существования гарантированного по Слейтеру решения для многошаговых ДМЗН; сформулированы необходимые условия существования седловых точек по Слейтеру в форме принципа максимума; найден явный вид седловой точки по Слейтеру в "непрерывной и многошаговой линейно-квадратичных ДМЗН, при этом были использованы необходимые условия и (для одной многошаговой задачи) метод динамического программирования; полученные результаты применены к построению гарантированных решений в двух конкретных экономических задачах. Апробация. Результаты диссертации докладывались на научных семинарах кафедры математики и механики РосЗИТЛП, на научно-методическом семинаре кафедры информатики и дискретной математики МПГУ, на Международной школе по динамическим и управляемым системам (Суздаль, 2001), на Международной конференции по проблемам управления "Автоматика - 2001" (Одесса, 2001), на XII Крымской осенней математической школе-симпозиуме (Крым, Севастополь, 2001). Перейдем к краткому изложению содержания диссертации. Диссертация состоит из трех глав, разбитых на пятнадцать параграфов.
В первой главе (1 — 6) вводятся гарантированные решения в "непрерывной" ДМЗН с программными управлениями и неопределенностями, исследуются седловые точки, реализующие эти решения. Именно, в 1 определяются основные составляющие элементы "непрерывной" ДМЗН, описывается процесс принятия решения, определяются цели, на достижение которых направлен процесс управления, приводится определение векторной гарантии. В 2 рассматриваются различные виды векторных гарантий, определенных на основе понятий минимумов по Слейтеру, Парето, Борвейну, Джоффриону, А-минимума из теории многокритериальных задач. В третьем параграфе, следуя [91], формализуются возможные решения ДМЗН и векторные седловые точки, реализующие эти решения, устанавливается связь между приведенными решениями и седловыми точками. Необходимым и достаточным условиям существования SS -седловых точек, реализующих гарантированное по Слейтеру решение ДМЗН, посвящен 4. Здесь же предложен способ нахождения SS -седловых точек, основанный на применении аппарата принципа максимума Понтрягина, приведены условия, при выполнении которых принцип максимума является не только необходимым, но и достаточным условием существования указанных седловых точек. Утверждения и алгоритмы из 4 применены в следующих двух параграфах для на хождения седловых точек в конкретных задачах. Именно, в 5 рассмотрена задача оптимизации распределения капитальных вложений между отраслями и для нее найдена SS -седловая точка, а в 6 найден явный вид АчА\ -седловой точки в линейно-квадратичной двухкритериальной задаче.
Содержание второй главы ( 7-12) составляет формализация гарантированных решений и исследование векторных седловых точек, реализующих эти решения в многошаговых ДМЗН. В 7 - постановка задачи, описание процесса управления, формализация предлагаемого решения. В 8 устанавливаются необходимые и достаточные условия существования SS -седловых точек, реализующих 5-решение гарантированное по S (по Слейтеру), в форме принципа максимума. В 9 выделен класс задач, в которых существует SS -седловая точка. Далее необходимые и достаточные условия из 8 применяются в 10 для нахождения явного вида SS -седловой точки в одной линейно-квадратичной двухкритериальной задаче. В 11 для другой линейно-квадратичной N -критериальной задачи седловая точка найдена с помощью метода динамического программирования. В заключении второй главы в 12 рассмотрена задача "разумной" добычи некоторого биологического вида (например, рыбы из водоема), для которой найден явный вид SS-седловой точки, реализующей предложенное гарантированное решение.
Существование G-решения гарантированного по G
Содержание второй главы ( 7-12) составляет формализация гарантированных решений и исследование векторных седловых точек, реализующих эти решения в многошаговых ДМЗН. В 7 - постановка задачи, описание процесса управления, формализация предлагаемого решения. В 8 устанавливаются необходимые и достаточные условия существования SS -седловых точек, реализующих 5-решение гарантированное по S (по Слейтеру), в форме принципа максимума. В 9 выделен класс задач, в которых существует SS -седловая точка. Далее необходимые и достаточные условия из 8 применяются в 10 для нахождения явного вида SS -седловой точки в одной линейно-квадратичной двухкритериальной задаче. В 11 для другой линейно-квадратичной N -критериальной задачи седловая точка найдена с помощью метода динамического программирования. В заключении второй главы в 12 рассмотрена задача "разумной" добычи некоторого биологического вида (например, рыбы из водоема), для которой найден явный вид SS-седловой точки, реализующей предложенное гарантированное решение.
В третьей главе выделен класс "непрерывных" ДМЗН, в которых существует G -решение гарантированное по G (по Джоффриону). В 13 рассматриваются ограничения на управляемую систему, управления, неопределенности и критерии, и исходной задаче ставится в соответствие специальная вспомогательная бескоалиционная игра двух лиц (без неопределенности). В следующем 14 для указанной бескоалиционной игры строится специальная антагонистическая игра. Приводятся условия существования седловой точки антагонистической дифференциальной игры в двух случаях: когда заданы ограничения на множества стратегий игроков, и когда такие ограничения отсутствуют. Устанавливается связь равновесной ситуации бескоалиционной игры с седловой точкой построенной антагонистической игры. Основываясь на результатах предыдущих параграфов в 15 установлены условия существования G -решения гарантированного по G (по Джоффриону) в исходной задаче.
Основные результаты исследований опубликованы в работах [60] - [65], [84] - [86], [90]. В первой главе рассматривается формализация многокритериальной "непрерывной" динамической задачи при неопределенности (ДМЗН) с программными управлениями и неопределенностями, формализуется гарантированное решение этой задачи. Установлены необходимые условия существования предложенного решения в форме принципа максимума Понтрягина. Полученные необходимые условия применены для нахождения решения одной линейно-квадратичной ДМЗН и для решения задачи оптимального размещения капитальных вложений на заданном интервале планирования. 1. Постановка задачи. Формализация решения Под многокритериальной "непрерывной" динамической задачей при неопределенности понимается упорядоченная система Здесь функционирование управляемой динамической системы S рассматривается на отрезке времени [ ь$Ь гДе 0 о $ фиксированные моменты начала и окончания процесса. Текущее состояние системы Е в каждый момент времени t характеризуется фазовым вектором х = (жі,... ,хп) Є Rn. Задано начальное состояние системы X x(to) = XQ . Изменение фазового вектора с течением времени описывается векторным дифференциальным уравнением с начальными условиями В (1.1) п-вектор-функция (p(t,x,u,z) определена для любых значений векторных переменных #6Rn, uEQ С Rr, zP С R , множества Q и Р заданы априори. Для каждого конкретного момента времени t Є [(ь$) ЛПР выбирает некоторое управляющее воздействие и(ї) - точку из множества Q, которое называется областью управленил. Одновременно реализуется (независимо от действий ЛПР) неопределенный фактор z(t) - точка из множества Р - области значений неопределенности. Управление U, которым распоряжается ЛПР, отождествляется с функцией и — u(t) (U -і- и(-)), определенной на интервале [Ц,&) времени t и принимающей значение при всех t Є [to, $) в множестве QCRr. Множество всех управлений U обозначим через Ы. Аналогично вводится неопределенность Z: Z — z=z(-), tE[to,&), z(t) Є Р С R/ при всех t Є [to, ) , тогда Z Є Z - множеству неопределенностей. Здесь и далее через и( ) (соответственно, z(-)) обозначается вектор-функция и(-) = {u(t),t0 t #} ( () = {z(t),t0 t &}). Если ЛПР выбрал конкретное управление U -f- и(-) и реализовалась некоторая неопределенность Z Ч- z(-), то уравнение (1.1) примет вид Непрерывную функцию х(-), to t $, удовлетворяющую равенству называют решением уравнения (1.3) или траекторией движения системы Е, соответствующей начальному условию x(to) = XQ, управлению U-r-u(-) и неопределенности Z-гz(). При этом функции (p(t,x,u,z), и(-) к z{ ) і to t fi, должны удовлетворять определенным требованиям, при выполнении которых для заданного начального состояния x(to) = хо уравнение (1.3) имеет единственное непрерывное решение x(t) , продол-жимое на [to, 0]. Далее ограничимся случаем, когда система (1.1) линейна, то есть имеет вид где A(t),B(t),R(t) - матрицы соответствующих размерностей с кусочно-непрерывными (по t Є [to, і?]) элементами; напомним, что скалярная функция a(t) называется кусочно-непрерывной на отрезке [to, ії], если a(t) непрерывна во всех точках [to, 0], за исключением, быть может, лишь конечного числа точек t\,...tp Є ((ь$], в которых функция a(t) может терпеть разрывы типа скачка, то есть существуют конечные пределы но, вообще говоря a(U — 0)ф a(U + 0), г = 1,...,р. В качестве допустимых управлений и неопределенностей бз дем рассматривать кусочно-непрерывные функции (что "подходит" для большинства практических задач). Из этого, в частности, следует, что всякое управление и(-) и неопределенность z(-) являются ограниченными (даже если области Q и Р не являются ограниченными). Значение кусочно-непрерывного управления u(t) (и неопределенности z(t)) в точках разрыва не играет существенной роли, однако для определенности удобно предполагать, что в каждой точке разрыва т\ (тг) значение управления u(i) (неопределенности z(t)) равно пределу справа:
Похожие диссертации на Гарантированные решения в многокритериальных динамических задачах
