- •Курсовая работа
- •Содержание
- •Введение. Общее описание задачи о ранце. Простейшая математическая модель.
- •Однокритериальная задача. Алгоритм решения
- •Постановка кзр
- •Алгоритм решения кзр методом динамического программирования
- •Алгоритм решения кзр методом ветвей и границ
- •Решение поставленной задачи с помощью метода ветвей и границ
- •Решение поставленной задачи с с помощью метода реккурентных соотношений
- •Решение задач многокритериальной оптимизации
- •Подход к решению многокритериальных задач, использующий схемы компромисса
- •Метод последовательных уступок по значению ведущего критерия (для 2х критериев)
- •Метод главного критерия
- •Принцип гарантированного результата
- •Метод идеальной точки
- •Принцип равенства
- •Принцип справедливой абсолютной уступки
- •Принцип относительной справедливой уступки
- •Подход к решению многокритериальных задач, основанный на концепции эффективной оценки и Парето-оптимального решения
- •Концепция Парета
- •Роль лпр в решении задач многокритериальной оптимизации
- •Многокритериальная многомерная задача о ранце
- •Постановка многокритериальной задачи
- •Заключение
- •Список литературы
Метод главного критерия
(К1(х), К2(х),…, Кl(х))
Его суть состоит в оптимизации значения наиболее важного для ЛПР критерия при том, что каждый последующий критерий в этой задаче принимает значение не ниже какого-то порога. ЛПР назначает значения порога P2,P3,…Pl
Получаем однокритериальную задачу
К1(х) , Ki(x)≥Pi , i=2,3,4,…,l
Решив эту задачу найдем оптимальное решение
Принцип гарантированного результата
(К1(х),К2(х),…, Кl(х))
Кi(х) =Вi – максимально возможное значение каждого критерия
i=1,2,3,4,…,l Х∈D – произвольное возможное значение Х
для 1го критерия - относительное отклонение (чем оно меньше, тем в большей степени мы учитываем критерии); , где ( ) – отклонение значения iго критерияот своего оптимального значения, вычисленное для решения х.
для всех критериев max (к примеру =0,03 – значит по каждому критерию отклоняется от своего оптимального решения не более, чем на 3%)
minmax - однокритериальная задача, дает оптимально ерешение по принципу гарантированного результата. (всего (l+1) однокритериальная задача)
Метод идеальной точки
(К1(х),К2(х),…, Кl(х)) Этот метод применяется в ситуации, когда в пространстве критериев введена некоторая метрика, а ЛПР в том же пространстве определена идеальная точка.
Б еря разные точки Х (допустимые решения) мы получаем разные точки ((К1(х),К2(х),…, Кl(х))
в l- мерном пространстве
получаем вектор – функцию (х)= К1(х),К2(х),…, Кl(х)
это множество значений обозначает область КD
область КD – это область оценок точка
X’: (х)= К1(х’),К2(х’),…, Кl(х’)
Надо найти решение Х, которое дает точку, ближайшую к идеальной. Решение Х дает точку К(х).
|К(х)-Y| - расстояние зависит от того, какую метрику мы введем
Метод идеальной точки к решению задач линейного программирования не сводится.
Пример : эвклидово пространство: , где k - координата α по номеру k.
Принцип равенства
Оптимальным компромиссным решением считается такое, которое обеспечивает равенство всех локальных критериев. Данный принцип является весьма "жестким" и может приводить к решению вне области D или совсем не иметь решения.
Математически этот принцип-оптимальности может быть записан следующим образом: opt ={ К1+К2+,…, +Кl}
Принцип справедливой абсолютной уступки
Справедливым считается такой компромисс, при котором суммарный абсолютный уровень снижения одного или нескольких критериев не превосходит суммарного абсолютного уровня повышения других критериев.
Оптимальным будет такое решение, которое обеспечивает δабс≥0 при переходе в любую соседнюю точку. Принципу справедливой абсолютной уступки соответствует принцип оптимальности, состоящий в максимизации суммы локальных критериев, т. е.
Величина суммарной абсолютной уступки при переходе от к равна δабс=( - )+( - ) Недостаток этого принципа состоит в том, что высокое значение суммарного критерия может быть достигнуто за счет высокого уровня одних локальных критериев, хотя значения других могут быть очень низкими.