Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Алгоритм построения множества Парето






Задача выделения всех эффективных точек в общем виде еще не решена, но разработано довольно много различных методов отыскания эффективных точек для двухкритериальных и линейных многокритериальных задач.

Рассмотрим простейший случай (два критерия). Имеем задачу:

(2)

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

(3)

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

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

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

Фиксируем некоторые желательные значения критериев и :

Значения C1 и С2 следует выбрать так, чтобы они принадлежали множеству достижимости. Теперь решаем две оптимизационные задачи:

1)

2)

Решив эти задачи, определим точки а и b (рис.4).

 

Рис.4 Аппроксимация множества Парето.

 

Проведя через них прямую 1, получим простейшую аппроксимацию множества Парето. Для уточнения аппроксимации решаем следующие задачи:

3)

4)

Находим еще две точки - c и d, принадлежащие этому множеству. Значения С3 и С4 снова должны принадлежать множеству достижимости.

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

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

 

3. Метод уступок

Методы, использующие ограничения на критерии, включают метод ведущего критерия и метод последовательных уступок

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

где - исходная система функций-ограничений.

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

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

 

Алгоритм метода последовательных уступок:

1. Критерии нумеруются в порядке убывания важности

2. Определяется оптимальное значение наиболее важного критерия . Лицом, принимающим решение (ЛПР), устанавливается величина уступки по этому критерию.

3. Решается задача по критерию с дополнительным ограничением .

4. Пункты 2 и 3 повторяются последовательно для критериев .

 

Если ЛПР устраивают полученные значения всех критериев, то задача считается решенной. В противном случае изменяются величины уступок и задача решается заново.

К преимуществам данного метода относится то, что сразу видно, ценой какой уступки в одном показателе приобретается выигрыш в другом и какова величина этого выигрыша.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал