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

Размещено на http://www.allbest.ru/

Саратовский Государственный университет

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

Д. С. Смирнова

Саратов, Россия

Описание модели.

Будем рассматривать модель многокритериальной оптимизации по качественным критериям в виде

, (1)

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

Иногда на накладывают дополнительное условие:

. (2)

Обозначим через класс моделей многокритериальной оптимизации вида (1) с дополнительным условием (2). Будем полагать, что на множестве задан частичный строгий порядок < . Для моделей на множестве альтернатив определим бинарное отношение предпочтения по формуле:

. (3)

В настоящем для класса моделей решается ряд задач, связанных со свойствами отношения предпочтения.

1. Необходимое и достаточное условие при котором отношение предпочтения является отношением порядка.

Теорема 1. Для того, чтобы для любой модели отношение предпочтения было отношением порядка, необходимо и достаточно, чтобы упорядоченное множество удовлетворяло условию обрыва убывающих цепей (условию ОУЦ).

Замечание. В общем случае не является отношением порядка. Действительно, если не удовлетворяет условию ОУЦ, то существует бесконечная цепь вида:

,

Будем предполагать, что каждая цепь имеет не менее двух элементов. Зафиксируем в цепи элементы .

Рассмотрим задачу вида (1) для которой и функции заданы таблицей 1 (для всех остальных положим

.

Таблица 1

Покажем соотношение , используя (3). Из анализа таблицы получаем, что при нечетных s имеем . Если s нечетно, то мы переходим к более важному критерию с номером s+1 и получаем . Таким образом соотношение проверено.

Аналогично, выполнено . Однако, условие здесь не имеет места, так как для всех s=1, 2, …. Таким образом отношение предпочтения для построенной задачи не является антисимметричным, а значит не является отношением порядка.

2. Условие внешней устойчивости множества Парето оптимальных альтернатив.

С каждой моделью многокритериальной оптимизации вида (1) можно связать структуру Парето предпочтения , где отношение предпочтения определяется по следующей формуле:

. (4)

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

. (5)

Теорема 2. Пусть - модель многокритериальной оптимизации вида (1). Если все удовлетворяют условию максимальности и множество конечно, то для модели выполнено условие внешней устойчивости.

Доказательство.

Лемма 1. Если все удовлетворяют условию максимальности и множество конечно, то удовлетворяет условию обрыва возрастающих цепей (условию ОВЦ).

Доказательство леммы. Положим . Предположим, что

не удовлетворяет условию ОВЦ. Тогда существует бесконечная последовательность элементов из вида:

(6)

Из первого неравенства в (7) получаем, что существуют элементы ;

из второго неравенства получаем, что существуют элементы ;

из k-го неравенства получаем, что существуют элементы ;

и т. д.

Среди номеров хотя бы один из них будет повторяться бесконечное число раз, так как последовательность (6) бесконечная. Пусть повторяется бесконечное число раз, тогда получаем в бесконечную возрастающую последовательность, что противоречит условию ОВЦ для упорядоченного множества . Учитывая, что условие ОВЦ равносильно условию максимальности, получаем доказательство леммы 1.

Перейдем к доказательству теоремы 2.

В силу формулы (4) и инъективности отображения получаем, что упорядоченные множества и изоморфны. Упорядоченное множество удовлетворяет условию ОВЦ по лемме 1, следовательно упорядоченное множество также удовлетворяет условию ОВЦ.

Покажем условие внешней устойчивости (5) для модели . Зафиксируем . Возможны два случая: 1) , 2) . В первом случае имеет место и (5) выполнено тривиальным образом. Во втором случае из определения максимального элемента получаем, что для некоторого . Если максимальный элемент, то (5) выполнено, если , то из определения максимального элемента получаем, что для некоторого и т.д.

В результате получаем последовательность

,

а так как удовлетворяет условию ОВЦ, то эта последовательность оборвется на конечном номере k , причем и , то есть для модели выполнено условие внешней устойчивости. Теорема 2 доказана.

3. Рассмотрим теперь модель многокритериальной оптимизации по качественным критериям в виде , где -топологическое пространство, - линейно упорядоченное топологическое пространство и отображение является непрерывным при каждом . На множестве задано отношение предпочтения , определяемое формулой (4).

Теорема 3. Пусть дана модель многокритериальной оптимизации виде , где - компактное топологическое пространство, - упорядоченное топологическое пространство и отображение является непрерывным при каждом . Тогда для модели выполнено условие внешней устойчивости.

Доказательство разбивается на ряд лемм.

Лемма 2. Cрез является замкнутым множеством.

Доказательство. При любом фиксированном срез является замкнутым множеством, как прообраз замкнутого множества при непрерывном отображении. Тогда срез

,

является замкнутым множеством как пересечение замкнутых множеств.

Лемма доказана.

Лемма Цорна. Пусть упорядоченное множество удовлетворяет условию индуктивности: каждая цепь имеет мажоранту. Тогда любой элемент этого упорядоченного множества мажорируется некоторым максимальным элементом. многокритериальный парето качественный

Перейдем к доказательству теоремы. Проверим для упорядоченного множечтва условие индуктивности. Пусть - цепь в . Справедлива следующая эквивалентность:

(7)

Так как - цепь, то согласно формуле (7) семейство срезов

образует цепь относительно включения. Покажем, что она центрирована, то есть, что каждое конечное подсемейство этого семейства имеет непустое пересечение. В самом деле, зафиксируем произвольно конечное подмножество , тогда оно имеет наибольший элемент , то есть . Согласно (7) . Отсюда ; учитывая, что получаем, что , то есть . В силу компактности топологического пространства и учитывая, что все срезы замкнуты по Лемме 2, получаем, что семейство срезов имеет непустое пересечение. Пусть , тогда , то есть мажоранта цепи . Мы показали, что упорядоченное множество удовлетворяет условию индуктивности. Применим лемму Цорна к индуктивно упорядоченному множеству . Получаем, что для дюбого имеет место соотношение , где - максимальный элемент. Учитывая, что максимальные элементы относительно - это, в точности, альтернативы, оптимальные по Парето, получаем, что Теорема 3 доказана.

Список литературы

1. Скорняков Л. А. Элементы теории структур. М: Наука, 1970

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

Размещено на Allbest.ru