Методы решения некоторых многокритериальных задач оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ

ГЛАВА I. МИНИМИЗАЦИЯ ВЫПУКЛОГО ОБОБЩЕННОГО КРИТЕРИЯ В ЛИНЕЙНЫХ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧАХ.

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

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

ГЛАВА П. ОТЫСКАНИЕ ОПТИМАЛЬНЫХ ПО ПАРЕТО РЕШЕНИЙ (ОЦЕНОК) МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1. Нахождение множества оптимальных по Парето решений при произвольном конечном числе критериев

2.2. Нахождение множества оптимальных по Парето решений (оценок) в двукритериальном случае

2.3. Об уменьшений размерности исходной задачи

2.4. Числовой пример.

ГЛАВА Ш. ПАРАМЕТРИЗАЦИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ И КУСОЧНО-ЛИНЕЙНАЯ АППРОКСИМАЦИЯ ПАРЕТОВОЙ ГРАНИЦЫ.

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

3.2. Кусочно-линейная аппроксимация паретовой границы двукритериальных задач

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

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

Систематическое исследование проблемы многокритериальной оптимизации было начато в 60-х годах. Здесь отметим работу [I], в которой на конкретных примерах впервые подчеркивалась важность оптимизации нескольких критериев одновременно. Показан противоречивый характер индивидуальных критериев и высказана идея о выборе окончательного решения из множества так называемых эффективных решений на основе дополнительных рассуждений.

Понятие эффективного, или оптимального по Парето решения является одним из основных, фундаментальных понятий современной теории принятия решения. Последнее название связано с именем итальянского экономиста и социолога В.Парето (1848-1923),который одним из первых начал рассматривать проблему многокритериальной оптимизации в своих исследованиях. Пусть G С Е" - заданное множество, и пусть на этом множестве определено отношение Р С G * G (называемое отношением Парето [2 ] ) u до оо i 1 и пусть р = (3 х G\ Р • Тогда любая точка р ос e & = { ОС € G I (LJ, X) е Р; V у € G } называется точкой Парето. С помощью этого отношения оптимальное по Парето решение для многокритериальных задач определяется следующим образом: пусть ^ - множество допустимых решений и f : X Е

- векторный критерий, по которому оценивается выбранное допустимое решение. Пусть У - { f(x)j ОС G X } * ^ешение °С £ называется оптимальным по Парето, если ^ (X) € . Многокритериальная задача с принципом оптимальности, задаваемым отношением Р , состоит в нахождении множества Парето

ХР= {осе X) f(x)6yP}.

Свойствам и методам отыскания оптимальных по Парето решений посвящено большое количество работ как советских [3 - 211 , так и зарубежных [22 -38] ученых. Изложение современного состояния теории оптимумов по Парето для конечномерных многокритериальных задач, т.е. задач, в которых X - подмножество пространства Е , дано в монографии . В ней приводится более подробный обзор по этой проблеме. Обзор работ, посвященных оптимальным по Парето решениям многокритериальной оптимизации процессов, приведен в . При наличии риска и неопределенности оптимальные по Парето решения исследуются в работах 1 5].

В многокритериальной задаче оптимизации любое оптимальное по выбранному принцицу оптимальности решение, естественно,должно быть из множества Х^ • Этим объясняется та важная роль, которую играет множество Парето в теории принятия решения.

Обычно хр состоит из множества частных оптимальных по Парето решений, и определение множества Х^ » как правило, связано с огромными вычислительными трудностями. Однако в конкретных задачах не всегда требуется полностью определить это множество, достаточно бывает найти хотя бы один элемент Х€ Х^ или часть ХР » обладающие некоторыми свойствами. Выделение частного решения, т.е. выбор окончательного решения во множестве » является наиболее ответственным моментом в процессе принятия решения, и это требует дополнительной информации для обоснованного проведения такого выбора. Большинство известных методов, предложенных для этой цели, основываются на использовании в той или иной форме информации о важности критериев. Одним из наиболее известных такого рода методов является метод, основанный на "свертывании" векторного критерия ^ в одну функцию - обобщенный критерий f (o<t,., 7 f - * ^) * Учитывая при этом относительную важность ^ при помощи соответствующего специального положительного числа , называемого коэффициентом важности [Ч, Ь}ЧВ-ЧЬ'] . в результате исходная многокритериальная задача сводится к обычной задаче оптимизации по одному критерию f в пространстве векторных оценок У Применяется и следующий вид обобщенного критерия: определяется идеальная (утопическая) точка в пространстве функционалов, вводится мера приближения к ней посредством евклидовой нормы и эта мера принимается за функцию if . Определяемое таким образом решение называется "среднеквадратичным" . Указанный метод называется методом идеальной точки £21 и был предложен М.Е. Салуквадзе £^9] .

В работах [50,51] рассмотрен подход к решению векторной задачи линейного программирования в случае, когда область ее допустимых решений может изменяться. В основе его лежит идея системной оптимизации, предложенная академиком В.М. Глушковым ["521 . Этот подход позволяет определить окончательное решение с желаемыми для лица, принимающего решения значениями критериев.

Использование того или иного подхода решения (это зависит от конкретной рассматриваемой задачи) существенно может повлиять на трудоемкость численной реализации поставленной многокритериальной задачи. Это относится особенно к специальным классам задач, для которых при скалярном критерии качества разработаны эффективные алгоритмы, использующие специфику ограничений и специфику критериальной функции [53] . Например, если решать специальные многокритериальные линейные задачи (задача транспортного типа, задача с блочными диагональными матрицами и т. п.) с нелинейными обобщенными критериями, то нарушается линейность задачи, о-сли же применить метод ограничений £4 J , то может нарушиться специфика ограничений задачи, и тем самым существующие в од-нокритериальном случае эффективные алгоритмы становятся неприменимыми для их решения. Поэтому представляется актуальным ставить следующую задачу: разработать эффективные алгоритмы для решения отдельных важных классов многокритериальных задач с достаточно общими принципами оптимальности. Одной из таких задач, рассматриваемой в главе I настоящей диссертации, является минимизация выпуклого обобщенного критерия для следующей многокритериальной задачи линейного программирования

С х -ч>тах , осе X = [ ^ Е" j ЭС-Ах£ & , х>0 J ^ (0.1) где А - Пхп - матрица с неотрицательными элементами; Q - {хп -матрица; & е и >0,i = Cn.

Выбор многокритериальной задачи с указанным видом ограничений обоснован тем, что к ней приводятся важные планово-экономические задачи и в частности, задача оптимизации нефтедобычи при жестком (стационарном) режиме [54] •

Рассматриваемую нами задачу можно записать в виде: п, у = & (0.2)

Она является задачей выпуклого программирования в пространсти ве f . Задачу (0.2) будем решать при дополнительном предположении на ^ : ^) 00 > WW ^ •

Для решения этой задачи построен релаксационный процесс вида хС1с+= xcvo+ j5Ck> . Здесь за начальное приближение принимается любая точка х°е X • Суть метода заключается в выборе cto направления спуска р , вычисление которого сводится к решению l+i • систем линейных алгебраических уравнений, отлич&ю щихся лишь правыми частями, и одной задачи выпуклого программирования с простыми ограничениями. Матрица этих уравнений является диагональной подматрицей матрицы I-A (I - единичная и -мерная матрица). Длина шага рСЮ= max [ р \ X}

Обосновывается сходимость алгоритма по функционалу.Получена r\ / <-К> rs оценка скорости сходимости порядка (J ^ z ); о < г <i. Она является следствием приводимой в работе более сильной оценки, оценивающей отклонение приближенного значения ^ Cvj<4'<)) ( 'Jjc>r = QoctK>) от оптимального Ч** разностью ¥ С у 0<>) -- Ч С, ^ . Наряду с полученной оценкой, к достоинствам метода 'могут быть отнесены конечность числа используемых во всех итерациях направлений рс?хк,(т.е. конечность множества { рс+ог'к = о I, } ) и конечность числа итераций требуемых ir * / для вычислений: I) минимального значения т ,2) оптимальной векторной оценки У = { = С х | ос <= при строгой выпуклости f ; 3) оптимального решения хЧ X при условии его единственности. Условие строгой выпуклости функции всегда выполняется,ерш за обобщенный критерий при^-нимается функция вида » где монотонно возрастающие, строго выпуклые функции; о*. > О L ос = 1 ^ tj* ,nax (С°с). , X • в частности, V может быть евклидовой мерой в пространстве критериев,введенной в [49] . Следовательно, оптимальная векторная оценка у* соответствующая средне-квадратичному решению х*€ X , с помощью предлагаемого нами алгоритма всегда находится за конечное число шагов. Отметим, что при наличии оптимальной векторной оценки нахождение оптимального решения X задачи (0.2) сводится к определению хотя бы одного частного решения системы

Сх = у", х - А* > х •

Далее, в главе I разрабатывается алгоритм для минимизации выпуклого обобщенного критерия для следующей динамической линейной многокритериальной задачи в пространстве х)-*тах^= i,t , X ijx-Fx^^X^o] (0.3)

Здесь - линейный ограниченный оператор; L" [ои ( ; ) - скалярное произведение в L foi],

Дополнительно предполагается, что § >0 и f - неотрицательный оператор, т.е. если х^о , то рх £0 .

При 1= 1 задача (0.3) является задачей динамического линейного программирования в В работе [55] приведен ряд задач экономического планирования, математическая постановка которых сводится к этой задаче, и предложены алгоритмы для ее решения. Многокритериальная трактовка рассмотренных в [55] практических задач сводится к постановке (0.3). Задача (0.3) является обобщением задачи (0.1) на бесконечномерГ ное пространство Lt .

Рассматриваемую нами задачу можно записать в виде ard'^^^'^^^'CMh-N^*^]. (0.4)

Задачу (0.4) будем решать при условии, что оператор |-р (I - единичный оператор) имеет неотрицательный обратный и ^ у = con** -> о

Задача (0.4) является задачей выпуклого программирования с п линейными ограничениями в пространстве и 2 • Отметим, что удобного и применимого для всех случаев метода решения таких задач при общей постановке не существует. Это объясняется отсутствием такого рода метода для решения задач динамического линейного программирования. Обзор по поводу последней проблемы приведен в [5f J . Поэтому имеет смысл выделить специальные классы задач выпуклого программирования в функциональном пространстве, с линейными ограничениями^имеющие практическое значение> и разработать эффективные алгоритмы их решения. Одним из таких классов задач и являются задачи вида (0.4).

При разработке алгоритма решения за'дачи (0.4) (как и в конечномерном случае ) используется ее специфика. Она состоит в том, что минимизируемая функция интерпретируется как функция f определенная на множестве векторных оценок У = {% & Е | у гДе (f, х) = ((f, х),. . a)), F" - неотрицательный оператор и (з > 0 . Схема этого алгоритма аналогична той, которую мы используем в конечномерном случае.

Приводится достаточное условие слабой сходимости алгоритма. При условии (I-F) & £ Lao скорость его сходимости имеет такой же порядок, как и в конечномерном случае. Физический и экономический смысл этого условия и условияо, te[о,tj разъяснены на конкретных примерах. В частности, если в (0.4) предполагать, что • £ ин> [Г* £ 9 то алгоритм решения задачи(0.4) будет и алгоритмом решения задачи (0.2). Таким образом, получаем два алгоритма для решения задачи (0.2). В отличие от второго алгоритма, в первом - кроме условия выпуклости, на функцию f налагается дополнительное ограничение, обеспечивающее существование минимизирующего решения на любом замкнутом подмножестве пространства Е . Однако, во втором алгоритме на множество допустимых решений налагается дополнительное условие неотрицательности матрицы ( J - Д) , являющееся необходимым и достаточным для ограниченности этого множества.

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

Методы приближенного построения множества Парето в двукритериальных задачах предложены в [56,5?]

Для многокритериальных задач линейного программирования удается построить в точности множества Парето, и этому вопросу посвящена довольно обширная литература [58-6*0

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

С X ™ах 7 А эс = & э х ^ 0 > (0.5) где А — h х п - матрица с положительными диагональными элементами и неположительными недиагональными; . & в Е и

- матрица. Очевидно, что если в (0.1)

А)ц < ■ i » L ~ и условие §> 0 заменить условием (> Z 0 , то (0.5) становится эквивалентной формой записи задачи (0.1). Такую форму записи мы используем для удобства изложения материала.

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

Предлагаемый метод решения задачи (0.5) существенным образом использует специфику условий задачи. Дается сравнение его с многокритериальным симплекс-методом [64] и показывается эффективность первого. Далее, отметим работы [65-6?! ,в этом направлении, в которых для отдельных важных классов линейных многокритериальных задач разработаны частные методы их решения. Эти методы представляют собой развитие методов решения соответствующих задач линейного программирования.

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

Для множества М = \ 1,.,и} множество его подмножеств обозначим через аМ и пусть = {(lU^e ЛгМ| ГП Г= Ф ) . Для каждой пары множеств (] \ J2) £ определим множество. z , ' .

FaUVlxeXKAxV^I^^jel ]

Очевидно, что \г)тф » т-е* Г(ИГ)является гранью многогранника X и множество xF = {Fu:f)|(iT)e/.(m} v состоит из множества всех граней многогранника д . При | =M\l грань ^ (I ,1 ) является 0 - мерной гранью, т.е. вершиной многогранника X > и множество состоит из множества всех вершин многогранника X •

Для каждого подмножества J О f4^ составим подматрицу Д^ состоящую из строк Д ,t в J матрицы А • Соответственно разбиению множества М = I UCMXl*) разобьем матрицу С-[С, С), At=0\i>AJ и рассм°трим матрщу

AdV-CC^.-C^CKAJ.

Пару (J }] называем допустимой парой, если система идтъо, ^Гиг, с >

ТД (Г)).=о , сеМ\СГиГ)

0 , леЕг совместна, и называем максимальной допустимой, если она допустима и не существует другой допустимой пары (Д J)такой, что 1с] ,

ГсГ Пусть Z.(M),i: множества всех допустимых и максимальных допустимых пар, соответственно» Показывается, что xP=u{Fu:r)Kr.i,)€/1.jM)] со.6) и справедливо следующее выражение для множества всех эффективных вершин XI многогранника X xf^U[F(Il,r)l(I'lVZ(M),r=!i\r}. f

Предлагаемый нами алгоритм нахождения множества Парето X задачи (0.5) состоит из двух этапов. На первом этапе определяем множество Хе* • ВТ°Р°М этапе с помощью множества Хех определяется множество. У\ в виде разложения (0.6). Показано, что множество Lm]j$\ не зависит от величин компонентов вектора . Данное свойство позволяет сразу выделить область устойчивости множества при изменении вектора правых частей ограничений. Это - область £>2 0 . Отметим, что выделение области устойчивости при изменении вектора S требуется во многих прикладных задачах оптимизации.

Следующие перечисленные моменты показывают основные преимущества предлагаемого нами алгоритма по сравнению с многокритериальным симплекс-методом [б^] , применяемым к решению задачи (0.5): I. не требуется вычисления разрешающих элементов при переходе от одного базиса к другому соседнему базису (эти элементы все время находятся на диагонали матрицы условий); Z. практически не увеличивая объем вычислений, требуемых в [6-7] для определения новой эффективной вершины, находим эффективную грань, которая может содержать более чем одну эффективную вершину, не определенную на ранних этапах алгоритма; 3. для запоминания раннее найденного эффективного или неэффективного базиса в нашем случае требуется в два раза меньше объема памяти ЭВМ; 4. максимальные эффективные грани выбираются лишь среди тех, которые содержат только аффективные вершины, и это обстоятельство существенно уменьшает число решаемых дополнительных задач линейного программирования, возникающих при применении алгоритма из [64].

Отдельно в главе II рассматриваем случай, когда в задаче (0.5) -£= 2 . Используя хорошо известную методику (см.например [£ЛЗ ) решение задачи сводим к нахождению множества всех оптимальных решений однопараметрической задачи линейного программирования

С1 сс. + А ( С2 - С* ) ^ Аэе эс£0;О<А<1 (0.7) для всего диапазона изменения параметра Л , где Q I - строка матрицы С • Затем предлагается алгоритм, с помощью которого составляется это множество. Весь процесс решения задачи укладывается в конечное число итераций. На каждой итерации алгоритма находится конкретный оптимальный базис. Вычисляются оценки векторов условий относительно этого базиса.Используя их, составляется множество, состоящее из оптимальных решений параметрической задачи, когда параметр изменяется во множестве оптимальности данного базиса. Множество этих решений образует некоторую эффективную грань многогранника X • Объединение этих граней, определяемых во всех итерациях алгоритма, дает искомое решение - множество Парето по вектор-функции Сгос) относительно множества X Совокупность всех найденных оптимальных базисов является решением параметрической задачи (0.7) и основной объем вычислений в алгоритме связан с их определением. Эти базисы можно найти и с помощью алгоритма параметрического линейного программирования [68] . В отличие от последнего, применяемого к задаче (0.7), для предложенного нами алгоритма характерны следующие свойства:

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

2. как и в общем случае, здесь не требуется нахождения разрешающих элементов при переходе от одного базиса к другому; 3. используется групповой ввод (вывод) векторов условий в базис;4. не требуются решения вспомогательных задач линейного программирования при движении по базисам.

Поскольку в многокритериальных задачах качество допустимого решения оценивается по значению векторного критерия, то кроме р знания множества X требуется определить и множество эф-фектвных оценок у'3 . Для задачи (0.5), после того как опреде

Р Р лено множество X » множество У определяется из равенства У^ — I Сое I осе XPi. Для случая , основываясь на предлокенном нами алгоритме нахождения множества X дается более простой способ определения множества У^ . Этот алгоритм представляет интерес не только в рамках многокритериальной оптимизации. Его можно использовать и при решении ряда однокритериальных задач оптимизации на множестве X . Для иллюстрации этого мы рассматриваем задачу максимизации числовой функции: найти ( С х, С?х ) j Д х < Ь , х * о } где h (• > •) - непрерывная числовая функция двух переменных, являющаяся неубывающей на своей области задания У по каждой переменной.

Пусть Г, ГсМ^1'-"'"] и Гл • Задаче (0.5) сопоставим задачу

С х , X е Xft* = { X € XI (Аф ^ I* I*! (0'8)

Структура ограничений задачи (0.5) позволяет записать задачу (0.8) в эквивалентном виде А «О; < , , i бМ\(141/Г)/

О X —^ max. д 2

6. , jel , xR=o, .

Исключив из последней задачи все переменные ос. , l I Uj ее

ЕИ-k. где

-г 1 2 к - число элементов множества [ U £ . Непосредственной проверкой легко можно убедиться, что полученная задача имеет такую же структуру, как (0.5). Обозначим У^г, = ^ Сэс \ ос б £ Xj4j?]и предположим, что

Р Р

У = У^г (0.9)

Тогда очевидно, что с X и хеХ^

Сое.= Сх- »т.е. ос. их находится в отношении безразличия^ во множестве решений. Отсюда^из того, что является отношением эквивалентности, множество Х^г содержит хотя бы один элемент из каждого класса, получающегося разбиением множества Х^ отношением ^^ . Таким образом, задача (08) совпадает с задачей (0.5) с точностью . Назовем ее редуцированной задачей для задачи (0.5). Однако, не всегда может существовать пара множеств (I^I1) » удовлетворяющая условию (0.9). Если такая пара существует, то назовем ее - парой. R - пару сг.п назовем максимальной,если не существует другая R - пара д ) j 1 'т! r2 tZ такая, что i С 1 } 1 с 1

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

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

Пусть X ~ некоторое топологическое пространство и fi>• - • i - непрерывные вещественные функции на X • Рассмотрим задачу максимизации t L - Г^к. на X • Пусть X - множество Парето этой задачи. Пусть П - некоторое топологическое пространство и Ц ~ непрерывная вещественная функция, заданная на произведении Е^хД

Будем говорить, что функция Н является параметризирующей функцией рассматриваемой задачи, если выполнены следующие условия: а) При каждом о<. £ .Q. » точка X » минимизирую щая функцию х И 0^><*)= Н (I (X),. I (эсш) на множестве X р 1 * 1 принадлежит множеству VI б) Если сс и ос2 минимизируют Н при одном и том же значении otefi > то f- С ос1) - I • (ос*;, I -С* •

I L о Р в) Для всякой точки Х°е X существует ^гакие последовательности и С X .что fj (е0?^, (^ fi С*°"> fj С «•), I = О г) Если последовательности С Q , 1хСи)}сХ обладан~ , <.vv? см . г| / (и> w в

X , СХ, ) и 0< > сх , то последовательности £■■ (ссс,л)) сходятся к f при всех

• L ь

I - .

Для С X} пусть X минимизирует И . В силу свойства б) f зависит только от (X . Положим cj. (pi) = (ос0). Согласно свойству г) функции непрерывны. Исходной многокритериальной задаче сопоставим следующую многокритериальную задачу

СоО полх , <) = , ы € J2 .

Показаны следующие свойства

D J2P =

Свойства 1),2) утверждают, что в новой многокритериальной задаче на множестве J2 сохранены практически все возможности старой задачи и никаких новых возможностей не появилось.

Будем говорить, что многокритериальная задача удовлетворяет условию выпуклости, если для любых точек оа^ос^еХ и всякого л [ 0, i ] существует такая точка х £ ^ , что a f. + (ocS , ; =

Рассмотрим также более сильное условие строгой выпуклости: если сеД ос* 6 X 7 Л 6 (о,О и ^(сс4) # 4» то существует такая точка х3£ X » что выполняется (0.10) и Л \ (X4) + ( .

В качестве Q. возьмем открытый ( х-1 ) - мерный симплекс к

Л { Ы;>0 Гя г

1 t=t

Рассмотрим функцию

Доказана следующая теорема

Теорема. Пусть пространство X компактно. Для того, чтобы построенная выше функция ]~( была параметриаирующей функцией рассматриваемой задачи,достаточно» чтобы выполнялось условие строгой выпуклости. Если к-2 , то для этого достаточно и условие выпуклости.

Если^О)- -предкомпактное ^множество , то выбирая конечную, достаточно плотную сеть Сг С\/ можно сколь угодно точно пок

1 iP Р рыть множество У с помощью точек J ((;) С У • В работе Г, для векторных задач математического программирования указанный вопрос разбирается с помощью построения равномерной сетки во множестве Q , когда оно является правильным симплексом.

Построение множества Х^" или является первым важным этапом решениямногокритериальных задач [ 3 1 . Для получения точки из X приходится оптимизировать некоторую свертку векторного критерия на множестве X • В непрерывном случае, как правило, множество Х"^ состоит из бесконечного числа точек. Поэтому, максимальное, что можно здесь сделать - это как можно более точно представить множество Х^ с помощью конечных оптимальных по Парето решений. Эффективность алгоритма построения конечного точечного покрытия множества Х^ с заданной плотностью зависит от числа обращений к "скаляризованной"экстремальной задаче и от используемого метода параметрической "скаля-ризации" многокритериальной задачи. Используя метод ограничений

Ч 1 и метод ассортиментной скаляризации О ] для выпуклых двукритериальных задач в работе [5?] были предложены два алгоритма кусочно-линейной аппроксимации множества У . Необходимое число узлов интерполирования при этом может быть значительно меньше, чем это требуется для построения крнечного точечнор го покрытия множества У заданной плотности.

Далее в главе Ш предлагается новый алгоритм для кусочно- линейной аппроксимации множества У двукритериальных задач максимизации. В нем используется линейная свертка для параметрической "скаляризации" рассматриваемой многокритериальной задачи. Получена априорная оценка числа обращений к "скаляризованной" экстремальной задаче для достижения предписанной точности аппроксимации. Она совпадает с аналогичной оценкой из [5?] . В процессе работы алгоритма производится целенаправленный выбор узлов интерполирования, и "скаляризованная" экстремальная задача решается лишь в том случае, если это необходимо для гарантии достижения требуемой точности.

Для конечномерной двукритериальной задачи линейного программирования наш алгоритм позволяет построить в точности множество I Р

У . Число решаемых экстремальных задач в этом случае не больше, чем число точек излома У .

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

- 22

Диссертация включает приложение. Оно содержит программу алгоритма § 1.2 для конечномерного случая и акт внедрения. Программа составлена на языке ФОРТРАН.

Основные результаты диссертации опубликованы в работах [71-76].

1. Za-c/e/n L. A. Dpi imfriiti^ <Xnol non^caCccz -2ra,iud pez^ozmctnce CZibcLiOu. —• IEEE 3 rtcwb . Adorned. . СопЬъ. 1963, v. AC. - % , p- se -co.

2. Макаров И. M., Виноградская Т. М., Рубчинский А. А., Соколов В. Б, Теория выбора и принятия решений. М.: Наука, 1982,328 с.О.»

3. Барисов В. И. Проблемы векторной оптимизации. В кн.: Исследование операций. Методологические аспекты. - М., 1972, с.v 72-91.

4. Вентцель Е. С. Исследование операций. М.: Сов. радио, 1972, 550 с.

5. Вилкас Э. Й. Существование эффективно-равновесных точек в задаче векторной оптимизаций. Литовский матем. сб. 1968, т.8, & I, с. 41-44.

6. Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1971, 384 с.

7. Гороховик В. В. К проблеме векторной оптимизации, Изв. АН СССР, сер. Техн. кибернетика, 1972, № 6, с. 63-70.

8. Гороховик В. В. Условия слабой эффективности в конечномерных задачах векторной оптимизации. Минск: Ин-т матем. АН БССР, 1976. - Препринт.

9. Ляшко И. И., Китель В. Р. 0 некоторых свойствах эффективных планов многокритериальной задачи. В кн.: Вычислит, матем. в совр. научно-техн. прогресс. Конев, 1974, с. 407-418.

10. Метревели Д. Г. Необходимые и достаточные условия эффективности в задачах векторной оптимизации. Сообщ. АН Груз. ССР, 1976, т. 83, с. 585 - 588.

11. Молдавский М. А. 0 выделении множества недоминируемых решений в непрерывных задачах векторной оптимизации. Автоматика, 1981, № 5, с. 48 - 55.

12. Молодцов Д. А. Регуляризация множества точек Парето. SBM и МФ, 1978, * 3, с. 597 - 602.

13. Морозов В. В. 0 свойствах множества не доминируемых векторов. Вестник МГУ, сер. Вычисл. матем. и киберн., 1977, й 4, с. 47 - 51.

14. Ногин В. Д. Об условиях оптимальности в многоцелевой оптимизации. В кн.: Численные методы нелинейного программирования. Харков, 1979,с.139 - 140.

15. Озерной В. М., Буянов Б. Б., Васышна Л. М. Алгоритм выделения множества неподчиненных решений в многокритериальных задачах. В кн.: Проблемы принятия решений. М.: Ин-т проблем управления, 1974, вып. 5, с. 61 - 67.

16. Подиновский В. В. Методы многокритериальной оптимизации. Вып. I. Эффективные планы. М., 1971.

17. Подиновский В. В., Гаврилов В. М. Оптимизация по последовательно применяемым критериям. М.: Сов. радио, 1975, - 192с.

18. Хоменш В. В., Чемерис М. Б. Об улучшаемости в многокритериальных задачах. В кн.: Прикладные методы теории оптимизации.Владивасток, 1977, с. 28 33.

19. Карлин С. Математические методы в теории игр, программирования и экономике. М.: Мир, 1964, - 838с.

20. Эрроу К.Дж., Баранкин Е. В., Блекуэлл Д. Допустимые точки выпуклых множеств. В кн.: Матричные игры. М.: Физматгиз, 1961, с. 274 280.

21. Б сп-Ллг&сС Д., Ben -Jal А Chawe s А . /l4cessaz^ and efficient aynoLition-b joz Ol $CLZe,to optimum in convex pzoOtamуп^ . — Lcoytomzibica. , 197 7 , i/ .45 Ц, pJH- S20.

22. Xin J. Q. Muftipfc o^j'etilbe. ргоЫетъ : pazeto - optima*?solutions method o| ргорег -e^LLixiit^ conbi^o-ivd.^.—

23. EE Automat . CO^-l 197-6 , i/. AC-21 ,p. 641-650.

24. J. Is. Muihp-ie ofycctibe optimizo-iton iy Ou fflutii-piiez method oj- ръорех. ^uO-iUi^ ао^^ъсиСпЫ . —1.EEutomU . Coniz. , i 9 , 1/. AC 24, fi/S 4 , p. 66? - 5 73.

25. Phi tip f\l^btLlkmb Цьг. the Irtoioz ггглит1га££оп jozoi-tem.-MM . Рьо^ъбст mj i67-2 t v. 27 fl/Z2 , p. 201-22$ .

26. У а P./,. Я solution* jjt>z Cjzo+ojо dztibion рго£йт s.Man.Sc137S ,p. 93 6 -W.

27. Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач М.: Наука, 1982, - 256с.

28. Тынянский Н. Т., Жуковский В. И. Дифференциальные игры с ненулевой суммой (кооперативной вариант). В кн.: Итоги науки и техники, сер. Матем. анализ. М.: ВИНИТИ, 1979, т. 17, с. 3 - 112.

29. Бурштейн Ф. В., Корелов Э. С. Многокритериальные задачи принятия решений при неопределенности и риске. В кн.: Теоретическая кибернетика. Тбилиси: Мецниереба, 1980, с. 143 - 148.

30. Гурин Л. Г. О понятии точек равновесия и точек Парето в задачах со случайными факторами. IBM и МФ, 1981, № 6, с. I4II 1422.

31. Жуковин В. Е. Модели и процедуры принятия решений. Тбилиси: Мецниереба, 1981, - П5с.

32. Подиновский В. В. Эффективные планы в многокритериальных задачах принятия решений в условиях неопределенности. В кн.: Модели процессов принятия решений. Владивосток, 1978,с. 102 ИЗ.

33. Подиновский В. В. Принцип гарантированного результата для частичных отношений предпочтения. SBM и МФ, 1979, й 6, с. 1436 - 1450.

34. Гермейер Ю. Б. Образование целей в задачах с векторным критерием (тезисы). Известия АН СССР. Техническая кибернетика, 1976, № 4, с. 3-13.

35. Зак Ю. А. Модели и методы построения компромиссных планов в задачах математического программирования с несколькими целевыми функциями. Кибернетика, 1972, Л 4, с. 102 - 107.

36. Волкович В. Л., Даргейко Л. Ф. Об одном алгоритме выбора ком-промисного решения для линейных критериев. Кибернетика, 1972, № 5, с. 133 - 136.

37. Салуквадзе М. Е. Задача векторной оптимизации в теории управления. Тбилиси: Мецниереба, 1975, - 202 с.

38. Глушков В. М., Михалевич В. С., Волкович В. Л., Даленко Г. А. К вопросу системной оптимизации в многокритериальных задачах линейного программирования. Кибернетика, 1982, № 3, с. 4-8.

39. Глушков В. М., Михалевич В. С., Волкович В. Л., Даленко Г. А. Системная оптимизация в многокритериальных задачах линейного программирования при интервальном задании предпочтений. -Кибернетика, 1983, № 3, с. I 8.

40. Глушков В. М. О системной оптимизации. Кибернетика, 1980, № 5, с. 89 - 90.

41. Лэсдон Л. С. Оптимизация больших систем. М.: Наука, 1975, 432 с.

42. Мееров М. В., Литвак Б. Л. Оптимизация систем многосвязного управления. М.: Наука, 1972, - 344 с.

43. Мееров М. В., Берщанский Я. М. Решение динамических задач оптимизации для линейных многосвязных систем (Препринт). М.: Ин - т проблем управления, 1975, - 68 с.

44. R^ Е. 0* Йе appzoximcUCon solutions -to rnuHipia cztftzicL dtcibion rnaktyitj pzoi'tem s .—Jn. \ M uiicple czctexio. oltci^Lon rnalancj. Kyoto , 1в}5, Зргс'пуег Ikzicw^ ,p.2?/&2.

45. Полищук Л. И. Кусочно-линейная аппроксимация паретовой границы выпуклых двукритериальных задач. В кн.: Модели и методы исследования эконом, систем. Новосибирск: Наука, 1979, с. 108 - 116.

46. Дымков М. П. Метод решения общей многокритериальной задачи линейного программирования. В кн.: Проблемы управления и оптимизации. Минск, 1976, с. 147 - 157.

47. Iv&rib J.P} S'teuezR.E. A zebised simplex yneiUod foz tineazmutbipie o&jeciiire. . — MM. pzu^tam. f i 9 73 , v. 5, i}p.

48. Gat T■ A qenezat method joz ddezminin^ the set -cUrvt bohdlowb to a. timox yeoio^mcodmuLYYi pzoHem. — ^uzop 3- Орег . Res. 19?? , v. i , Vs 5", p. 30?-$22.

49. Aetmann H. е^тега^с^ £/ге ъе-i oj M г • ^icLeni Sotuioons Ol line.az muliCp-lt oijecdibe.угю^ъ&м . — Ojo&z. Res. Qua-z-t. , , i/. ZZJ/Ji*>\))p. fii

50. У и PL.,M. *t of alt л on dominated solutions in lineal c&see and ol muliicbiie,zioL simjofex m eihod.-lMM.Amt. rnd Appl, 19?5, v. 49 р-ЧЪ0-Ц(>1.

51. Казакова M. Ф. Нахождение оптимумов Парето в полиматричной задаче коммивояжере. В кн.: Матем. методы решения эконом, задач. М.: Наука, 1974, с. 55 - 61.

52. Гольштейн E. Г., Юдин'Д. Б. Новые направления в линейном программировании. М.: Советское радио, 1966, - 524 с.

53. Гермейер Ю. Б. 0 свертывании векторных критериев эффективности в единой критерий. В сб.: Кибернетику - на службу коммунизму. М.: Энергия, 1971, т. 6, с. 175 - 184.

54. Растригин Л. А. Системы экстремального управления. М.: Наука, 1974, - 630 с.

55. Гамидов Р. Г. Об одной двукритериальной задаче линейногопрограммирования. Изв. АН Азерб. ССР, сер. Физ.- техн. и матем. наук, 1980, № 4, с. 114 - 117.

56. Гамидов Р. Г. К векторной статической оптимизации линейных многосвязных систем. Изв. АН Азерб. ССР, сер. Физ.- техн. и матем. наук, 1983, ft I, с. Ill - 115.

57. Гамидов Р. Г. Об одной задаче выпуклого программирования с линейными ограничениями в конечномерном пространстве. М.: ВИНИТИ, 1983, # 2900. 16 с.

58. Гамидов Р. Г. Об одной задаче минимизации выпуклого функцио4нала при наличии линейных ограничений в пространстве ц . М.: ВИНИТИ, 1983, К 2862. 13 с.

59. Гамидов Р. Г. Кусочно-линейная аппроксимация множества эффективных оценок двукритериальных задач. М.: ВИНИТИ, 1983, № 6414. II с.

60. Гамидов Р. Г., Фарбер М. Ш. О принятии решения в задачах многокритериальной оптимизации. Изв. АН Азерб. ССР, сер. Физ.- техн. и матем. наук, 1978, 3, с. II - 16.

61. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1967, - 576 с.

62. Бахвалов Н. С. Численные методы. М.: Наука, 1975, - 632 с.

63. Демидович Б. П., Марон И. А. Основы вычислительной математики. М.: Наука, 1966, - 664 с.

64. Канторович Л. В., Акилов Г. П. Функциональный анализ. М.: Наука, 1977, - 744 с.

65. Беллман Р. Гликсберг И., Гросс 0. Некоторые вопросы математической теории процессов управления. М.: ИЛ, 1962,

66. Юдин Д. Б., Голыптейн Е. Г. Линейное программирование (теория, методы и приложения). М.: Наука, 1969, - 424 с.

67. Qto^ion Д-М. 5oil/in^ ticziie-zion matherrjaiicaf pzocj ~ ъсстъ . — Opez . Res. } 196? , v. 1 5 Ж i , p-39 5 У .

68. Пшеничный Б. Н. Необходимые условия экстремума. М.: Наука, 1969, - 152 с.

69. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1980, - 520 с.

70. Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике. М.: Наука, 1976, - 250 с.

71. Форсайт Дж., Малькольм М., Моулер М. Машинные методы математических вычислений. М.: Мир, 1980, - 279 с.