III. Краткие теоретические сведения

⇐ ПредыдущаяСтр 4 из 9Следующая ⇒

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

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

(1)

Каждой точке соотношения

(2)

ставят в соответствие некоторую точку f в плоскости критериев (рис.1). Соотношения (2) определяют отображение множества на .

Множество носит название множества достижимости или множества предельных возможностей. Изучение структуры этого множества может оказаться весьма полезным при исследовании

Рис. 1.

различных задач проектирования и планирования. Поэтому в последние годы началось систематическое изучение возможностей построения множеств достижимости. Заметим, что множество Парето представляет собой лишь часть границы множества достижимости. На рис. 1 множеством Парето будет дуга АСD.

Приближенное построение множества Парето сводится к последовательному решению ряда задач математического программирования. Опишем одну из возможных схем расчета. Фиксируем некоторые желательные значения критериев и :

Значения и С₂ следует выбрать так, чтобы они принадлежали множеству достижимости.

Примечание. В общем случае проблема определения внутренней точки множества достижимости может оказаться совсем не простой.

Решаем теперь две оптимизационные задачи.

I: II:

Решив эти задачи, мы определим точки а и b (рис. 3.3), Проведя через них прямую 1, мы получим простейшую аппроксимацию множества Парето.

Для уточнения аппроксимации, решив нижеследующие задачи III и IV, мы находим еще две точки —c и d, - принадлежащие этому множеству:

III. IV.

Значения и снова должны принадлежать множеству достижимости. Через точки a, c, d, b мы проведем ломаную 2, которая и будет следующим приближением. Очень часто подобной информации о структуре множества Парето уже бывает достаточно для решения практических задач. Описанный способ можно распространить и на случай большинства критериев.

Рис. 2. Рис. 3.

Для аппроксимации множества Парето можно поступить и по – другому. Пусть и - строго положительные числа такие, что

(3)

Составим новый критерий

и решим следующую задачу математического программирования:

Оказывается, что решение этой задачи определяет такой вектор , что точка принадлежит множеству Парето.

Поэтому аппроксимацию множества Парето мы можем осуществить следующим образом (рис. 3.4). Решаем задачу

(4)

где и удовлетворяют условию (3). Задача (3), (4) определит некоторый вектор , который в плоскости f определит точку с координатами

Точно так же мы определим точку и через точки и проведем прямую 1. Она будет простейшей аппроксимацией множества Парето (см. рис. 3). Строя точки и , мы можем получить с их помощью ломаную 2, которая будет следующим приближением, и т. д.

Рис. 4

При использовании подобных построений возникает вопрос: можно ли таким способом построить любую точку множества Парето? Другими словами, каждой ли точке множества Парето мы можем поставить в соответствие такой вектор ( ), удовлетворяющий условиям , что решение задачи оптимизации

определяет совокупность чисел , являющихся координатами данной точки множества Парето? В общем случае ответ на этот вопрос остается открытым. Он решен, притом положительно, только для того случая, когда множество —многогранник, а критерии имеют вид

т. е. являются также линейными функциями

В заключение этого параграфа сделаем одно замечание о точности описанного способа аппроксимации множества Парето.

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

⇐ Предыдущая 1 2 345 6 7 8 9 Следующая ⇒