Зонирование территории по степени риска цунами

курсовая работа

2.1 Численные методы построения множества Парето

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

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

(2.1)

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

(2.2)

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

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

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

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

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

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

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

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

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

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

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

Делись добром ;)