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

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

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

(2)

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

(3)

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

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

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

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

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

1)

2)

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

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

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

3)

4)

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

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

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

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

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

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

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

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

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

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