Содержание к диссертации
Введение
ГЛАВА I. Минимизация выпуклого обобщенного критерия в линейных многокритериальных задачах 23
1.1. Минимизация выпуклого обобщенного критерия в многокритериальных задачах линейного программирования . 23
1.2. Минимизация выпуклого обобщенного критерия в многокритериальных задачах динамического линейного программирования 35
ГЛАВА II. Отыскание оптимальных по парето'решений (оценок) многокритериальной задачи линейного программирования 46
2.1. Нахождение множества оптимальных по Парето решений при произвольном конечном числе критериев 46
2.2. Нахождение множества оптимальных по Парето решений (оценок) в двукритериальном случае 60
2.3. Об уменьшений размерности исходной задачи 67
2.4. Числовой пример 75
ГЛАВА III. Параметризация многокритериальных задач и кусочно-линейная аппроксимация паретовой границы 80
3.1. Параметризиругощая функция и построение ее для некоторого класса многокритериальных задач 80
3.2. Кусочно-линейная аппроксимация паретовой границы двукритериальных задач 89
Литература
- Минимизация выпуклого обобщенного критерия в многокритериальных задачах динамического линейного программирования
- Нахождение множества оптимальных по Парето решений (оценок) в двукритериальном случае
- Числовой пример
- Кусочно-линейная аппроксимация паретовой границы двукритериальных задач
Введение к работе
Во многих областях человеческой деятельности возникает необходимость принятия решения, оптимального не по одному критерию, а по нескольким критериям одновременно. Например, в ряде задач экономического планирования приходится максимизировать прибыль при минимальных затратах; в задаче о коммивояжере при выборе маршрута коммивояжер может руководствоваться не только расстояниями, но также издержками, общим временем переездов, и еще какими-нибудь подобными критериями. Эти и многие другие практические задачи часто математически могут быть сформулированы в виде максимизации одновременно нескольких числовых функций, определенных на заданном множестве (альтернативных) решений с определенным принципом оптимальности. Такая задача называется многокритериальной задачей оптимального управления. Она занимает важное место среди задач, составляющих предмет исследования теории выбора и принятия решения.
Отсутствие единого принципа оптимальности отличает многокритериальные задачи от однокритериальных. Это повлекло за собой создание большого количества подходов для их решения. Каждый из этих принципов состоит в упорядочении (частичном или полном) множества векторных оценок и определении наилучших допустимых решений в смысле введенного упорядочения. Достаточно общим и хорошо разработанным является способ задания упорядочения на "языке" бинарных отношений. Для каждой конкретной многокритериальной задачи это отношение строится на основе необходимой информации о предпочтениях, которая может быть получена у лица, принимающего решения, экспертов, а также в результате исследования математической модели задачи.
Систематическое исследование проблемы многокритериальной оптимизации было начато в 60-х годах. Здесь отметим работу [I], в которой на конкретных примерах впервые подчеркивалась важность оптимизации нескольких критериев одновременно. Показан противоречивый характер индивидуальных критериев и высказана идея о выборе окончательного решения из множества так называемых эффективных решений на основе дополнительных рассуждений.
Свойствам и методам отыскания оптимальных по Парето решений посвящено большое количество работ как советских [3 - 211 , так и зарубежных [22 -38] ученых. Изложение современного состояния теории оптимумов по Парето для конечномерных многокритериальных задач, т.е. задач, в которых X. - подмножество пространства Е , дано в монографии Сзд] . В ней приводится более подробный обзор по этой проблеме. Обзор работ, посвященных оптимальным по Парето решениям многокритериальной оптимизации процессов, приведен в С °] . При наличии риска и неопределенности оптимальные по Парето решения исследуются в работах /i - 5].
В многокритериальной задаче оптимизации любое оптимальное по выбранному принципу оптимальности решение, естественно, должно быть из множества X • Этим объясняется та важная роль, которую играет множество Парето в теории принятия решения.
Обычно состоит из множества частных оптимальных по Парето решений, и определение множества X » как правило, связано с огромными вычислительными трудностями. Однако в конкретных задачах не всегда требуется полностью определить это множество, достаточно бывает найти хотя бы один элемент Х€ X или часть X » обладающие некоторыми свойствами. Выделение частного решения, т.е. выбор окончательного решения во множестве, является наиболее ответственным моментом в процессе принятия решения, и это требует дополнительной информации для обоснованного проведения такого выбора. Большинство известных методов, предложенных для этой цели, основываются на использовании в той или иной форме информации о важности критериев. Одним из наиболее известных такого рода методов является метод, основанный на "свертывании" векторного критерия ! в одну функцию - обобщенный критерий f (о ,..., Хл f I ..f) » учиты - 7 вая при этом относительную важность f • при помощи соответствующего специального положительного числа с - , называемого коэффициентом важности 4, 6; 6- S] . В результате исходная многокритериальная задача сводится к обычной задаче оптимизации по одному критерию в пространстве векторных оценок У Применяется и следующий вид обобщенного критерия: определяется идеальная (утопическая) точка в пространстве функционалов, вводится мера приближения к ней посредством евклидовой нормы и эта мера принимается за функцию if . Определяемое таким образом решение называется "среднеквадратичным"[HO j . Указанный ме- ( тод называется методом идеальной точки 21 и был предложен М.Е. Салуквадзе [ 9] .
В работах [50,51] рассмотрен подход к решению векторной задачи линейного программирования в случае, когда область ее допустимых решений может изменяться. В основе его лежит идея системной оптимизации, предложенная академиком В.М. Глушковым ["521 . Этот подход позволяет определить окончательное решение с желаемыми для лица, принимающего решения значениями критериев.
Использование того или иного подхода решения (это зависит от конкретной рассматриваемой задачи) существенно может повлиять на трудоемкость численной реализации поставленной многокритериальной задачи. Это относится особенно к специальным классам задач, для которых при скалярном критерии качества разработаны эффективные алгоритмы, использующие специфику ограничений и специфику критериальной функции [53] . Например, если решать специальные многокритериальные линейные задачи (задача транспортного типа, задача с блочными диагональными матрицами и т. п.) с нелинейными обобщенными критериями, то нарушается линейность задачи, ёлли же применить метод ограничений J , то может нарушиться специфика ограничений задачи, и тем самым существующие в однокритериальном случае эффективные алгоритмы становятся неприменимыми для их решения. Поэтому представляется актуальным ставить следующую задачу: разработать эффективные алгоритмы для решения отдельных важных классов многокритериальных задач с достаточно общими принципами оптимальности.
Следующие перечисленные моменты показывают основные преимущества предлагаемого нами алгоритма по сравнению с многокритериальным симплекс-методом [ЬН] , применяемым к решению задачи (0.5): I. не требуется вычисления разрешающих элементов при переходе от одного базиса к другому соседнему базису (эти элементы все время находятся на диагонали матрицы условий); 2. практически не увеличивая объем вычислений, требуемых в (6 /] для определения новой эффективной вершины, находим эффективную грань, которая может содержать более чем одну эффективную вершину, не определенную на ранних этапах алгоритма; 3. для запоминания раннее найденного эффективного или неэффективного базиса в нашем случае требуется в два раза меньше объема памяти ЭВМ; 4. максимальные эффективные грани выбираются лишь среди тех, которые содержат только аффективные вершины, и это обстоятельство существенно уменьшает число решаемых дополнительных задач линейного программирования, возникающих при применении алгоритма из [64].
Основные результаты диссертации опубликованы в работах [71-76].
Минимизация выпуклого обобщенного критерия в многокритериальных задачах динамического линейного программирования
Число решаемых во всех итерациях линейных алгебраических уравнений и задач выпуклого программирования с простыми ограничениями конечно . Это свойство следует из конечности числа решаемых во всех итерациях задач вида (1.5)-(1.7). Свойство 1.2. Для каждого числа 0 д у существует номер такой, что
Доказательство. В силу (1.20) и леммы 1.2 можно написать т.е. Из свойства I.I следует, что множество \ Ч С ) , І=О,І,... j состоит из конечного числа элементов. Отсюда и из сходимости следует свойство 1.2. Это свойство означает, что алгоритм определяет минимальное значение функции f в задаче (1.2) за конечное число шагов.
Свойство 1.3. Если f строго выпуклая на t- функция и о 5" J , то существует номер к (Я) такой, что а), где и - решение задачи mi)и Ч ( JJ) 3 4 Доказательство. Пусть ОС в X оптимальное решение задачи (1.2). Тогда, в силу единственности решения задачи тш f (и-) У получаем, что и = Сое . Пусть к.( ) - номер итерации, который выбирается из свойства 1.2, т.е. Так как X С X и Ч1 - строго выпукла, то ясно, что т.е. С - % при к к() . Свойство 1.3 доказано. Свойство 1.3 утверждает, что при строгой выпуклости функции Ч на t » решение и задачи (1.2),-на множестве У находится за конечное число шагов. Свойство 1.4. Если задача (1.2) имеет единственное решение х X и 0 5 у , то х находится за конечное число шагов.
Доказательство. Согласно (1.26), последовательность { Xе ) является ограниченной последовательностью. Тогда Хс —ъ ос . Рассмотрим множество Q - [ &С"К\ к- о, і,...) . Для доказательства свойства 1.4 достаточно рассмотреть случай, когда Сг П )\ 0 Из конечности множества Q имеем d = тім g - ос II О ; J Є (} , ос є X . Тогда справедливость свойства следует из неравенства Н сс і ccwll = jbCK,]o(.c xw bW)-J О. Вернемся к свойству 1.3. Пусть у - решение задачи (1.2) во множестве У . Рассмотрим систему С ое. = J , х- А = ; ос о , Любое решение этой системы является решением задачи (1.2), и его можно найти с помощью симплекс-метода. Таким образом, при строгой выпуклости функции f , дополнительно решая одну задачу линейного программирования, решение Осе X задачи (0.1) можно определить аа конечное число шагов. 5. Частный случай. Допустим, что ЧЧу) = 11У-Ч » гДе
Точка у называется идеальной (утопической) точкой для задачи (І.І). Задача (1.2) в данном случае определяет такое компромиссное решение ос еХ Для задачи (І.І), при котором отклонение значения векторного функционала Ох от М будет минимальным. Такой подход к решению многокритериальных задач был предложен М.Е.Салуквадзе [ч$ ] и широко применяется на практике. В этом случае трудоемкость вычислений, требуемых на отдельном шаге алгоритма, сильно уменьшается, благодаря простоте минимизируемой функции ч , и алгоритм определяет решение зс за конечное число шагов.
Рассмотрим следующую динамическую линейную многокритериаль-нуго задачу в пространстве Цг ( хЬ ,Ь = Л,осбХ={хеГ8[.У x-Fx g,xlo}. (1.27) Здесь F-/, [&1" /,г[ЛІ - линейный ограниченный оператор; ( ) , I- Г - линейные функционалы в Lz [о.У ; і е Lzl0 Дополнительно предполагается, что & о & \ - неотрицательный оператор (F 0) , т.е. если х о , то рх О .
Всюду неравенство между векторными функциями понимается как неравенство для каждой из компонент и должно выполняться почти для всех te[o,y. Пусть Ц» - выпуклый на Е обобщенный критерий для задачи (1.27), из минимизации которого определяется ее решение, т.е. рассмотрим задачу
Нахождение множества оптимальных по Парето решений (оценок) в двукритериальном случае
Обоснование алгоритма. Если решать задачу /л х симплекс-методом, начиная с опорного плана эс=о , то из свойств а)-в) следует, что в оптимальном базисе задачи все переменные ос- , LeLl =иемР- -1) являются базисными, и соответствующие пере-менным г-, ІАІ оценки строго положительны. Поскольку эти рассуждения справедливы для любого Л (о,І) и имеет место (2.18), то из второй теоремы двойственности следует, что
Для задачи / \. составим симплексную таблицу с базисом соот ветствующем характеристической матрице г , и вычеркним из Г) этой таблицы все столбцы и строки с индексами с XI Для основной части алгоритма в качестве вводных данных достаточно брать оставшуюся часть таблицы. Решение задачи (2.17), таким образом, в предварительной части алгоритма сводим к решению эквивалентной задачи, размерность которой на [ 1/ J единиц меньше размерности исходной задачи, где [ \L J - число индексов в В m - й итерации основной части алгоритма множество [ Л ,) ] находится из решения системы Из построения отдельной итерации алгоритма следует, что если то к. +-т при JX XYV,- Л. Следовательно итерации, т.е.
Таким образом, основная Далее, если х - оптимальное решение задачи /\ и послед-ней итерации, т.е. при и.= rn t сс G р ] , J ) . і). Таким образом, основная часть алгоритма приводит к разбиению 0 Лх - me і множества (0,1) на подмножест-. ва (0, 3,( , 3, Длгпі1; О , для которых имеет место следующее: а) соответствующий характеристической матрице г базис Ь является оптимальным базисом задачи (2.17) при л в б) г VI Л ) является множеством всех оптимальных реше ний задачи (2.17), когда параметр Л меняется во множестве
Совокупность всех найденных оптимальных базисов О t р: - 1, т является решением параметрической задачи линейного программирования Д се & , ос о э с х + АСС -( :Х1 ШОХ 0 1 (2.23) и основной объем вычислений в алгоритме связан с их определением. Эти базисы можно найти и с помощью алгоритма параметрического линейного программирования \j 8] .В отличие от этого алгоритма, применяемого к задаче (2.23), для вышепредлагаемого справедливы следующие свойства: I. среди найденных оптимальных базисов не существуют такие, для которых множество оптимальности состоит из единственной точки; 2. не требуется нахождение разрешающих элементов при переходе от одного базиса к другому. 3. используется групповой ввод (вывод) векторов условий в базис, 4. не требуется решение вспомогательных задач линейного программирования при движении по базисам.
На основании равенства (2.24) можно предложить следующий путь нахождения множества У . а) с помощью алгоритма п.1 находим точки х , - = 0 б) последовательно соединяя точки С осс , 1= і,0, находим множество
Предложенный способ определения множества У представляет интерес не только в рамках многокритериальной оптимизации. Его можно использовать и при решении однокритериальных задач оптимизации с теми же ограничениями как в (2.17) со специальными видами оптимизируемых функций (см.[ЯЗ] , стр.40).
В качестве примера рассмотрим следующую задачу максимизации числовой функции: Найти max ii (C x,C x) , ос X (2.26) где ті - непрерывная числовая функция двух переменных, являющаяся неубывающей на своей области задания СчА по каждой переменной. К задаче (2.26) сводится, в частности, задача нахождения среднеквадратичного решения двукритериальнои задачи (2.1).
Среди решений задачи (2.26) имеется, по крайней мере, одно оптимальное по Парето по вектор-функции (_,х относительно множества X Следовательно, имеет место равенство max. hCc x,c х") = max 4і(ч)
Числовой пример
Во многих областях человеческой деятельности возникает необходимость принятия решения, оптимального не по одному критерию, а по нескольким критериям одновременно. Например, в ряде задач экономического планирования приходится максимизировать прибыль при минимальных затратах; в задаче о коммивояжере при выборе маршрута коммивояжер может руководствоваться не только расстояниями, но также издержками, общим временем переездов,и еще какими-нибудь подобными критериями. Эти и многие другие практические задачи часто математически могут быть сформулированы в виде максимизации одновременно нескольких числовых функций, определенных на заданном множестве (альтернативных) решений с определенным принципом оптимальности. Такая задача называется многокритериальной задачей оптимального управления. Она занимает важное место среди задач, составляющих предмет исследования теории выбора и принятия решения.
Отсутствие единого принципа оптимальности отличает многокритериальные задачи от однокритериальных. Это повлекло за собой создание большого количества подходов для их решения. Каждый из этих принципов состоит в упорядочении (частичном или полном) множества векторных оценок и определении наилучших допустимых решений в смысле введенного упорядочения. Достаточно общим и хорошо разработанным является способ задания упорядочения на "языке" бинарных отношений. Для каждой конкретной многокритериальной задачи это отношение строится на основе необходимой информации о предпочтениях, которая может быть получена у лица, принимающего решения, экспертов, а также в результате исследования математической модели задачи.
Систематическое исследование проблемы многокритериальной оптимизации было начато в 60-х годах. Здесь отметим работу [I], в которой на конкретных примерах впервые подчеркивалась важность оптимизации нескольких критериев одновременно. Показан противоречивый характер индивидуальных критериев и высказана идея о выборе окончательного решения из множества так называемых эффективных решений на основе дополнительных рассуждений.
Понятие эффективного, или оптимального по Парето решения является одним из основных, фундаментальных понятий современной теории принятия решения. Последнее название связано с именем итальянского экономиста и социолога В.Парето (1848-1923),который оСвойствам и методам отыскания оптимальных по Парето решений посвящено большое количество работ как советских [3 - 211 , так и зарубежных [22 -38] ученых. Изложение современного состояния теории оптимумов по Парето для конечномерных многокритериальных задач, т.е. задач, в которых X. - подмножество пространства Е , дано в монографии Сзд] . В ней приводится более подробный обзор по этой проблеме. Обзор работ, посвященных оптимальным по Парето решениям многокритериальной оптимизации процессов, приведен в С ] . При наличии риска и неопределенности оптимальные по Парето решения исследуются в работах /i - 5].
В многокритериальной задаче оптимизации любое оптимальное по выбранному принципу оптимальности решение, естественно,должно быть из множества X Этим объясняется та важная роль, которую играет множество Парето в теории принятия решения.
Обычно состоит из множества частных оптимальных по Парето решений, и определение множества X » как правило, связано с огромными вычислительными трудностями. Однако в конкретных задачах не всегда требуется полностью определить это множество, достаточно бывает найти хотя бы один элемент Х X или часть X » обладающие некоторыми свойствами. Выделение частного решения, т.е. выбор окончательного решения во множестве Х , является наиболее ответственным моментом в процессе принятия решения, и это требует дополнительной информации для обоснованного проведения такого выбора. Большинство известных методов, предложенных для этой цели, основываются на использовании в той или иной форме информации о важности критериев. Одним дним из первых начал рассматривать проблему многокритериальной оптимизации в своих исследованиях.
Кусочно-линейная аппроксимация паретовой границы двукритериальных задач
Длина шага СЮ= max [ а \ эс+ .рск д j Обосновывается сходимость алгоритма по функционалу.Получена оценка скорости сходимости порядка (J \Л ) о г і. Она является следствием приводимой в работе более сильной оценки, оценивающей отклонение приближенного значения (ч ) ( СКг = ( ,octK ) от оптимального Н7 разностью Ч? С 0 ) -- Ч Q ц к+) . Наряду с полученной оценкой, к достоинствам метода могут быть отнесены конечность числа используемых во всех итерациях направлений рс?хк,(т.е. конечность множества Ірс+х:ї = 0 і, -». } ) и конечность числа итераций требуемых для вычислений: I) минимального значения т ; 2) оптимальной векторной оценки м У = {ц=Сзсосєлі при строгой выпуклости f ; 3) оптимального решения Х X при условии его единственности. Условие строгой выпуклости функции всегда выполняется,если за обобщенный критерий приї-нимается функция вида (4)= ,1,( 4.) , где К монотонно возрастающие, строго выпуклые функции; - 0 в частности, V мо жет быть евклидовой мерой в пространстве критериев,введенной в [49] . Следовательно, оптимальная векторная оценка у соответствующая средне-квадратичному решению х є X , с помощью предлагаемого нами алгоритма всегда находится за конечное число шагов. Отметим, что при наличии оптимальной векторной оценки нахождение оптимального решения х є /Ч задачи (0.2) сводится к определению хотя бы одного частного решения системы
Далее, в главе I разрабатывается алгоритм для минимизации выпуклого обобщенного критерия tf для следующей динамической линейной многокритериальной задачи в пространстве (,х)- тах =1, X eX j AlU-F o] (0.3)
Дополнительно предполагается, что - неотри цательный оператор, т.е. если х о , то рх. При = 1 задача (0.3) является задачей динамического линейного программирования в , В работе [55] приведен ряд задач экономического планирования, математическая постановка которых сводится к этой задаче, и предложены алгоритмы для ее решения. Многокритериальная трактовка рассмотренных в [55] практических задач сводится к постановке (0.3). Задача (0.3) является обобщением задачи (0.1) на бесконечномер Г ное пространство Lt .
Рассматриваемую нами задачу можно записать в виде ) Задачу (0.4) будем решать при условии, что оператор f-p (1 - единичный оператор) имеет неотрицательный обратный и
Задача (0.4) является задачей выпуклого программирования с линейными ограничениями в пространстве и2 . Отметим, что удобного и применимого для всех случаев метода решения таких задач при общей постановке не существует. Это объясняется от сутствием такого рода метода для решения задач динамического линейного программирования. Обзор по поводу последней проблемы приведен в [55 ] . Поэтому имеет смысл выделить специальные классы задач выпуклого программирования в функциональном пространстве, с линейными ограничениями имеющие практическое значение и разработать эффективные алгоритмы их решения. Одним из таких классов задач и являются задачи вида (0.4).
При разработке алгоритма решения за дачи (0.4) (как и в конечномерном случае ) используется ее специфика. Она состоит в том, что минимизируемая функция f интерпретируется как функция , определенная на множестве векторных оценок У = і & С I «a=U,x),tteX} . гДе (f,x) = №oc),..., ( , ос)), F - неот-рицательный оператор и о 0 . Схема этого алгоритма аналогична той, которую мы используем в конечномерном случае.
Приводится достаточное условие слабой сходимости алгоритма. При условии (I F) o-G Цс скорость его сходимости имеет такой же порядок, как и в конечномерном случае. Физический и экономический смысл этого условия и условия (р.#) У 0, 6- i h і є [о, tj разъяснены на конкретных примерах. В частности, если в (0.4) предполагать, что Р. Е — Е i, $L и » т0 алгоритм решения задачи(0.4) будет и алгоритмом решения задачи (0.2). Таким образом, получаем два алгоритма для решения задачи (0.2). В отличие от второго алгоритма, в первом - кроме условия выпуклости, на функцию f налагается дополнительное ограничение, обеспечивающее существование минимизирующего решения на любом замкнутом подмножестве пространства L .
