Парето-оптимальные решения многокритериальных задач

Подиновский В.В.
Ногин В.Д.






Парето-оптимальные решения многокритериальных задач








МОСКВА ФИЗМАТЛИТ ®

  УДК 519.8
  ББК 22.18
       П44

     Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. — 2-е изд., испр. и доп. — М.: ФИЗМАТЛИТ, 2007. — 256 с. — ISBN 978-5-9221-0812-6.
     Монография, ставшая классической, посвящена оптимумам по Парето, играющим базовую роль при анализе многокритериальных задач принятия решений. В ней разбирается содержательный смысл, теоретическое и практическое значения понятия оптимального по Парето решения, подробно рассматриваются различного рода условия оптимальности, исследуются структура и свойства множества Парето, излагается теория двойственности многокритериальных задач.
     Книга рассчитана на широкий круг читателей — математиков, специалистов, применяющих математические методы анализа решений в экономике и менеджменте, технике и энергетике, транспорте и строительстве, информатике и военном деле, при автоматизации управления и проектирования, а также студентов и аспирантов соответствующих специальностей.
     Она будет служить хорошим руководством для всех, кто уже использует теорию многокритериальной оптимизации в своей научной и педагогической работе или пока только еще готовится стать квалифицированным специалистом в области системного анализа, исследования операций и поддержки принятия решений.


















ISBN 978-5-9221-0812-6

                                 (е) ФИЗМАТЛИТ, 2007
                                 © В. В. Подиновский, В.Д. Ногин,

2007

            ОГЛАВЛЕНИЕ


  Предисловие ко второму изданию......................... 7
  Основные обозначения.................................. 12

  Глава 1. Основные понятия и определения............... 14
   § 1.1. Общие сведения о многокритериальных задачах оптимизации .................................................. 14
   §1.2.  Отношения предпочтения, функции ценности и выбора. . .  20
   § 1.3. Независимость критериев по предпочтению. Многокритериальные задачи максимизации.......................... 28
   § 1.4. Эффективные и слабо эффективные оценки и решения ...    32
   § 1.5. Теоретическое и практическое значения понятия эффективного решения.......................................... 40
   § 1.6. Собственно и подлинно эффективные решения..... 50
   § 1.7. Эффективные последовательности оценок и решений ....    58
   § 1.8. Эквивалентные векторные критерии.............. 60

  Глава 2. Условия оптимальности........................ 65
   § 2.1. Общие условия оптимальности................... 66
   § 2.2. Условия оптимальности для вогнутых и линейных задач . . 95
   § 2.3. Условия оптимальности для двухкритериальных задач . . . 113
   § 2.4. Условия оптимальности для дифференцируемых функций 119
   §2.5.  Условия оптимальности второго порядка........ 123
   § 2.6. Условия оптимальности для негладких задач.... 126
   § 2.7. Свойства эффективных последовательностей..... 131

  Глава 3. Структура и свойства множества эффективных решений.......................................... 136
   §3.1.  Топологические свойства множеств эффективных оценок и решений.............................................. 136
   § 3.2. Условия существования эффективных решений.... 149
   §3.3.  Структура множеств эффективных решений в линейных задачах.............................................. 156
   § 3.4. Оценка числа эффективных точек в дискретных задачах . 163
   § 3.5. О построении множества эффективных решений и проверке эффективности выделенного решения.................... 174

Оглавление

  Глава 4. Двойственные многокритериальные задачи. . . 180
   § 4.1. Седловые пары, максимины и минимаксы векторных функций ................................................. 181
   §4.2.  Общая конструкция двойственных задач.......... 188
   § 4.3. Вогнутый случай............................... 192
   § 4.4. Линейный случай............................... 202

  Послесловие........................................... 221
  Дополнительные библиографические ссылки............... 222
  Список литературы..................................... 224
  Добавление ко второму изданию книги. 77. С. Краснощеков, А. В. Лотов.........'................................. 242
  Предметный указатель.................................. 253

    Предисловие ко второму изданию

     Читателю предлагается второе издание книги В. В. Подинов-ского и В. Д. Ногина «Парето-оптимальные решения многокритериальных задач», впервые выпущенной издательством Физматлит в 1982 г. Книга посвящена теоретическим основам многокритериальной оптимизации, т. е. теории важного класса задач выбора решений (вариантов действий, стратегий, планов), характеризуемых наличием нескольких критериев выбора и большим или бесконечным числом возможных вариантов решений.
     В большинстве сложных и ответственных задач принятия решений приходится учитывать различные аспекты и последствия возможных вариантов действий: экономические, социальные, политические, технические, экологические и иные. Поэтому далеко не всегда возможно представить задачи поиска наиболее подходящего варианта действий в классической математической форме решения задачи оптимизации, т. е. максимизации или же минимизации целевой функции (единственного критерия выбора). В связи с этим возникли и получили широкое распространение многокритериальные постановки задачи выбора решения, основанные на явном признании наличия нескольких различных (как принято говорить, частных) критериев выбора. Анализ проблем выбора варианта действий в многокритериальной постановке не так прост, как в случае единственного критерия, когда достаточно решить математическую задачу поиска оптимального решения — необходимы специальные подходы, методы и процедуры.
     Сейчас это положение не вызывает вопросов и является общепринятым. Однако так было не всегда. В середине XX в., когда начало интенсивно развиваться научно-прикладное направление методов выбора стратегий, получившее наименование «Исследование операций», считалось, что математическая модель операции должна представляться именно в форме задачи оптимизации единственного критерия (одной целевой функции). Задачи, которые естественным образом оказывались многокритериальными, рассматривались как сформулированные не до конца. Поэтому первоначально, в пятидесятых-шестидесятых годах прошлого века, практически все подходы и методы, предлагавшиеся для ра

Предисловие ко второму изданию

  боты с такими задачами, основывались на одной и той же идее: свести исходную многокритериальную проблему к однокритериальной. Наиболее известным из них является метод «свертывания» всех критериев в один обобщенный, или агрегированный (чаще всего им служит линейная свертка, т. е. сумма произведений исходных критериев на их коэффициенты «важности»). Кроме того, большое распространение получили метод выделения среди исходных критериев главного и назначения требуемых уровней для всех остальных, а также метод целевого программирования (оптимальным считается такой вариант действий, для которого вектор значений всех критериев наиболее близок к целевому множеству). Эти методы, по своей сути, являются эвристическими, они не имеют строго научного обоснования и опираются на здравый смысл и накопленный опыт лица, принимающего решение (ДПР), на основе предпочтений которого и должны свертываться отдельные (частные) критерии или назначаться ограничения, целевые точки и т. д. Затем появились и математически обоснованные методы, в том числе методы построения функций полезности (ценности), описывающих предпочтения ДПР. Однако такие методы крайне сложны и трудоемки для ДПР *), а потому возможности их практического применения весьма ограничены.
     Постепенно стало ясно, что рассмотренный путь решения многокритериальных задач является далеко не универсальным. Начали появляться иные подходы, создаваться иные методы. Большие надежды возлагались на итеративные методы, которые предполагают не одноэтапный, а пошаговый поиск варианта действий в многокритериальной задаче. Они реализуются в виде интерактивных процедур, т. е. диалоговых процедур «человек-компьютер», в которых компьютер на каждом шаге решает некоторую задачу однокритериальной оптимизации и находит некоторый вариант действий, а ДПР реагирует на полученное решение этой задачи, меняя ее параметры с целью поиска более предпочтительного варианта. В процессе такого диалога ДПР начинает лучше понимать суть поставленной анализируемой задачи и ее особенности, свои предпочтения и возможности выбора. Как показала жизнь, такие методы также имеют ограниченные возможности практического применения, поскольку участие в длительных интерактивных процедурах, в которых требуется отвечать на

      *) См., например, О. И. Ларичев. Теория и методы принятия решений. — М.: Логос, 2002.

Предисловие ко второму изданию

9

  сложные вопросы о собственных предпочтениях, также затруднительно для ЛПР **).
     Альтернативный подход к поддержке ЛПР в процессе выбора предпочтительных решений состоит в построении совокупности всех «разумных» вариантов действий и информировании ЛПР об этих вариантах. Человек сам должен указать наиболее предпочтительное решение среди разумных вариантов. При этом возникает вопрос о том, что можно понимать под «разумным» вариантом действий, а также как найти совокупность «разумных» вариантов и проинформировать ЛПР об этой совокупности. Теория принятия решений при многих критериях рассматривает эти вопросы. Таким образом, она является основой методов аппроксимации совокупности «разумных» вариантов и ее представления ЛПР, которые получают все более широкое распространение в последние годы.
     Остановимся теперь на объекте исследования теории многокритериальной оптимизации — совокупности «разумных» вариантов действий. В этой теории для формулировки концепции «разумного» варианта действий используется понятие оптимальности по Парето, или, как стали говорить в последнее время, оптимальности по Эджворту-Парето, названной так в честь Ф. Эджворта и В. Парето (Francis Edgeworth, 1845-1926; Vilfredo Pareto, 1848-1923), которые ввели это понятие и использовали его в экономических и социологических исследованиях. Это понятие несложно: некоторый возможный (или, как принято говорить, допустимый) вариант действий является оптимальным по Парето, если при замене его любым другим допустимым вариантом нельзя добиться улучшения значения хотя бы одного из критериев, не ухудшив при этом значения какого-то другого. Только среди таких вариантов и надлежит выбирать наиболее предпочтительный.
     Совокупность таких вариантов действий принято называть множеством парето-оптимальных решений. Каждое из парето-оптимальных решений порождает вектор значений критериев, который обладает простым геометрическим свойством: он лежит на границе множества критериальных векторов, которые могут быть получены при использовании всех допустимых вариантов действия (множества достижимых критериальных векторов или, как принято говорить в книге, множества достижимых критери

      **) См. там же.

Предисловие ко второму изданию

  альных оценок). Таким образом, совокупность парето-оптималь-ных решений порождает часть границы множества достижимых критериальных векторов, которую принято называть паретовой границей. Ее анализ имеет и большое прикладное значение, поскольку аппроксимация паретовой границы является основой современных методов многокритериальной оптимизации. Паретова граница является основным объектом теоретического исследования в настоящей книге.
     В годы, предшествующие первому изданию этой книги, возник массовый интерес к анализу многокритериальных задач и начали публиковаться научные статьи, посвященные этой проблематике. В этих статьях нередко «переоткрывались» результаты, уже известные по работам в математической экономике и теории неантагонистических игр, а в прикладных работах встречались и явные ошибки. Поэтому появление монографии, написанной на высоком научном уровне и содержащей основные теоретические результаты в области многокритериальной оптимизации, явилось важной вехой в становлении и развитии теории принятия решений при многих критериях. Книга не только подвела итоги развития теории к началу 80-х годов, но и во многом явилась пионерской, так как содержала ряд новых и оригинальных идей и результатов, ранее не публиковавшихся. Она позволила научным работникам иметь, по существу, энциклопедию по теории многокритериальной оптимизации, а преподавателям — учебное пособие для преподавания в вузах этой теории и методов, использующих ее результаты.
     Хотя со времени первого выхода в свет книги В. В. Подинов-ского и В. Д. Ногина прошло почти четверть века и за этот период получен ряд новых результатов, книга по-прежнему вызывает большой интерес научных работников и преподавателей. Это связано, прежде всего, с отсутствием новой книги (как в России, так и за рубежом), которая превзошла бы книгу В. В. Подиновского и В. Д. Ногина своей полнотой и ясностью изложения. Авторы книг по методам многокритериальной оптимизации, изданных за последние четверть века, в учебниках обычно ограничиваются отдельными (зачастую не самыми важными) свойствами задач, а в монографиях рассматривают только те их аспекты, которые важны для самих авторов. Поэтому на книгу В. В. Подиновского и В. Д. Ногина имеются ссылки практически во всех русскоязычных работах, посвященных многокритериальным задачам; она хорошо известна специалистам и за рубежом, которые также часто

Предисловие ко второму изданию

11

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

  Заведующий кафедрой «Исследование операций» ф-та вычислительной математики и кибернетики МГУ им. М. В. Ломоносова, академик РАН
П. С. Краснощеков


  Заведующий сектором Вычислительного центра РАН д. ф.-м. и.


А. В. Лотов

            Основные обозначения


  {аг € А | тг(аг)} —совокупность элементов х множества А, для которых выполнено тг(аг).
  0 — пустое множество.
  |А| —число элементов конечного множества А.
  А х В — декартово произведение множеств А и В.
  п . А В — отображение h множества А во множество В.
  Е — множество вещественных чисел.
  Ent-[</] — целая часть числа q.
  Ет — евклидово m-мерпое пространство.
  0(щ) = (0, 0,..., 0) — нулевой вектор пространства Ет.
     Для векторов у, z из Ет:
          т
  {у, z) = ^2 yiZi — скалярное произведение у и з;
          i=l
  ||у|| = V<У> у) — норма у;
  у Д z -Н y-i Д Zi, i = 1, 2,..., m;
  у > z -Н- у Д z и Зг: у» > гд
  у > z -Н y-i > Zi, i = 1, 2,... , т;
  у > z -Н- у = z или у» > Zi хотя бы при одном i = 1, 2,... , т;
  Е™ = {у € Ет | у >      —положительный ортант пространства Ет;
  Е™ = {у € ^r" I У = 0(щ)} — неотрицательный ортант пространства Ет.

     Для множества А С Ет:
  А — замыкание множества А;
  int А —внутренность множества А;
  FrA —граница множества А;
  ri А — относительная внутренность выпуклого множества А;
  conv А — выпуклая оболочка множества А;
  convA — замыкание выпуклой оболочки А;
  А ° — поляра выпуклого конуса А;
  0⁺(А) —рецессивный конус выпуклого множества А;
  Т(А; у*) —касательный конус ко множеству А в точке у*;
  МахА (MinA) — множество максимальных (минимальных) элементов множества А, частично упорядоченного отношением >.