Методы многокритериальной целочисленной оптимизации, основанные на аппроксимации границы Парето

• Автор: Поспелов, Алексей Игоревич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 150 с. : ил.

Содержание
Введение .

Глава 1. Монотонные многокритериальные задачи целочисленной оптимизации.

1.1. Задача о наименьшем покрытии множествами .

1.2. Многокритериальная задача о рюкзаке

1.3. Задача локального уменьшения загрязнения в реке.

Глава 2. Методы решения задач многокритериальной целочисленной оптимизации с монотонными критериями.

2.1. Метод квазиразумиых целей.

2.2. Модификация метода уточнения оценок для полиэдральной аппроксимации выпуклых многогранников.
2.3. Метод разумных целей, основанный на аппроксимации выпуклой оболочки ЭджвортаПарето

Глава 3. Теоретический анализ скорости сходимости метода аппроксимации ВОЭП

3.1. Общие хаусдорфовы схемы, адаптивные методы и последовательности наполнения .
3.2. Скорость сходимости метода аппроксимации ВОЭП
Глава 4. Решения прикладных задач с помощью метода разумных целей .
4.1. Программный комплекс МРЦ для монотонных целочисленных
задач многокритериальной оптимизации
4.2. Использование программного комплекса в системе поиска эффективных технологий очистки воды в бассейнах крупных рек
4.3. Использование комплекса для поиска эффективных технологий
очистки воды в малых реках .
Заключение .
Литература


Для нахождения всех оптимальных решений в задачах типа (2)-(4) может быть использована схема ветвей и границ (см. Но, как показывает опыт, такой подход обладает очень высокой трудоемкостью в связи с тем, что число решений может оказаться очень велико даже для задач сравнительно малой размерности. Особенностью подходов, предлагаемых в настоящей диссертационной работе, является то. Парето с гарантированной точностью. Диссертация состоит из введения, четырех глав и заключения. В первой главе описаны некоторые классические задачи целочисленной многокритериальной оптимизации, такие как задача о многокритериальном рюкзаке, задача о покрытии, сводящиеся к рассматриваемым в работе монотонным многокритериальным задачам целочисленной оптимизации. Там же описаны некоторые задачи экологического и экономического содержания, моделирование которых приводит к задаче (2)-(4). Таким образом, показывается практическая значимость работы. Во второй главе описаны два метода решения задачи (2)-(4). В исходном МРЦ предполагается, что есть некоторая заданная в явном виде совокупность альтернатив — множество точек У = {у1,. Ят. Кт| /'е Ус : у'^3/}. ВОЭП может быть также определена как У с = Ус + М+, где М™ — неотрицательный конус пространства Мт (здесь и далее под суммой множеств А Л- В понимается множество, составленное из сумм всевозможных пар элементов из А и В, т. А + В = {(а + 6) | а е А, Ь € В}). Несложно показать, что У? Парето критериальных точек, что и Ус, но при этом имеет более простую границу. На рисунке 1 для двумерного случая приведен пример множества всех достижимых критериальных точек У, их выпуклой оболочки Ус и выпуклой оболочки Эджворта-Парето У с- В дискретном случае множество У нстелесно, тогда как множество У^ является телесным многогранным множеством, что позволяет строить сечения для последующей визуализации. Несмотря на то, что У? Далее, построенная аппроксимация У^ визуализируется с помощью диалогового наборов двумерных сечений У? Границы этих сечений являются кривыми объективного замещения для пары критериев при фиксированных остальных. Рис. Множество всех достижимых критериальных точек(У), их выпуклая оболочка(УЬ) и выпуклая оболочка Эджворта-Парото(У? У?. Сечения берутся при разных значениях третьего критерия и фиксированных значениях остальных критериев. После анализа границы Парето ЛПР указывает наиболее предпочтительную точку у, называемую разумной целью. Поскольку предварительный анализ границы Парето на основе визуализации позволяет ЛПР определить возможности рассматриваемой системы и подробно изучить взаимосвязь между критериями, выбор цели оказывается осознанным. В то же время, выбранная ЛПР точка у в силу дискретности множества У может, в отличие от метода достижимых целей [, ), оказаться недостижимой (см. Термин разумная цель был введен С. Рис. У. В МРЦ близость понимается как принадлежность у выпуклой оболочке У. Из совокупности X, содержащей малое число альтернатив, ЛПР выбирает окончательное решение самостоятельно или используя специальные методы поддержки принятия решений для работы с малым числом альтернатив (см. Для построения множества X можно использовать различные подходы. Опишем алгоритм, предложенный в [) и получивший теоретическое обоснование. Множество точек У формируется из точек У, для которых образы при отображении $*(•) оптимальны по Парето среди всех #(У) (см. Затем среди них отбираются точки, недоминируемые по Парето для исходной задачи. Р<х>Ы>у") = . Аг-, г — 1,2,. А;. По множеству У строится соответствующее множество альтернатив X. Цель второй главы — перенести идеи МРЦ на задачи многокритериальной оптимизации (2)-(4), характеризуемые значительно большим числом альтернатив, когда подход, используемый в исходном МРЦ, не может быть реализован непосредственно, поскольку расчет всех точек У и их последующее сравнение являются крайне трудоемкими процедурами. В разделе 2. МКРЦ). Метод предполагает, что имеется возможность вычислять значения критериев и ограничений не только на множестве но и на более широком множестве Xq = [О, К]п.