Методы построения множества Парето - раздел Информатика, РАЗДЕЛ 1.МЕСТО И РОЛЬ ПРОЦЕССОВ ПОДГОТОВКИ И ПРИНЯТИЯ РЕШЕНИЙ В ОБЩЕЙ ТЕХНОЛОГИИ УПРАВЛЕНИЯ СЛОЖНЫМИ ОРГАНИЗАЦИОННО-ТЕХНИЧЕСКИМИ СИСТЕМАМИ (СОТС
Приведенные В П.4.2.2 Свойства Множества Парето Могут Быть Ис...
Приведенные в п.4.2.2 свойства множества Парето могут быть использованы для построения (исследования) данного множества (либо его подмножеств) или определения его характеристик в конкретных прикладных задачах. При этом большинство методов определения указанного множества основано на сформулированных условиях оптимальности. Чаще всего используются необходимые условия оптимальности, состоящие в том, что если точка эффективна (в том или ином смысле), то она является решением задачи максимизации или минимизации (возможно, при некоторых дополнительных ограничениях) числовой функции специального вида при надлежащим образом назначенных величинах параметров, входящих в эту функцию и (или) ограничения.
В этом случае задача выделения всех эффективных решений сводится к соответствующей скалярной параметрической задаче математического программирования. Указанную замену исходной задачи векторной оптимизации параметрическим семейством обычных экстремальных задач часто называют скаляризацией исходной задачи. Однако в этом случае получаемое множество может содержать «лишние» точки, которые не являются эффективными и поэтому должны быть выявлены и отсеяны. Если при поиске множества используют достаточные условия оптимальности, то решения соответствующих скалярных параметрических задач, удовлетворяющие им, являются эффективными.
К настоящему времени наиболее конструктивные результаты, связанные с построением множества Парето, получены для случаев, когда компактно и выпукло, а непрерывные функции вогнуты. В этом случае оказываются справедливы свойства 4 и 5, которым должны удовлетворять все точки множества Парето. Алгоритм поиска указанных точек сводится к решению следующей совокупности экстремальных задач:
(4.12)
Последовательно перебирая значения , можно получать точки множества Парето. Геометрическая интерпретация данного процесса сводится к построению опорных гиперплоскостей к множеству допустимых значений критериальных функций . На рисунке 4.8 показан для случая двух критериальных функций пример построения двух линий уровня, которые касаются множества в точках, принадлежащих . Следует подчеркнуть, что требование выпуклости и вогнутости существенно, т.к. если данные требования не выполняются, то решение задач (4.12) не гарантирует получение всех точек множества Парето. Это иллюстрируется геометрическим примером, представленным на рисунке 4.9. На данном рисунке точки множества , выделенные штриховой линией, не могут быть выделены ни при каких коэффициентах в задаче (4.12).
Рис. 4.8.
Рис. 4.9.
Частным случаем постановки задачи (4.12) является задача многокритериального линейного программирования, в которой множество ограничено выпуклой оболочкой, натянутой на конечное множество точек (вершин), называемой выпуклым многогранником [15, 24]. При этом все линейны. Вершины рассматриваемого выпуклого многогранника, образующие конечное множество , и являются объектом первоначального исследования.
Цель этого исследования состоит в выявлении всех вершин, принадлежащих к множеству недоминируемых решений . Эти вершины образуют конечное множество . В частности, очевидно, что к множеству принадлежат все вершины, в которых достигаются экстремумы по каждой целевой функции в отдельности.
При поиске элементов используется ряд свойств этого множества. Среди них наиболее важным для практических приложений является свойство связности, т.е. возможности последовательного перехода между точками через такие соседние вершины, которые также принадлежат к . На основе данного свойства была разработана комбинаторная симплекс-процедура для отыскания всех точек множества . Эта процедура связана с запоминанием всех базисов выявленных точек и с определением на каждом шаге соответствующим образом модифицированным симплекс-методом новой точки при проведении перебора указанных базисов.
РАЗДЕЛ МЕСТО И РОЛЬ ПРОЦЕССОВ ПОДГОТОВКИ И ПРИНЯТИЯ РЕШЕНИЙ В ОБЩЕЙ ТЕХНОЛОГИИ УПРАВЛЕНИЯ СЛОЖНЫМИ ОРГАНИЗАЦИОННО ТЕХНИЧЕСКИМИ СИСТЕМАМИ... Gt...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Методы построения множества Парето
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Концептуальная модель принятия решений
Анализ многочисленных публикаций по различным аспектам проблемы выбора показывает, что в настоящее время наметилась прогрессивная тенденция к интеграции различных научных направлени
Постановка задачи линейного программирования
Значительная часть задач принятия решения – это задачи распределения ресурсовмежду объектами.
Пусть имеется т видов ресурсов, каждый i
Двойственные задачи линейного программирования
Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):
Прямая задача (ПЗ)
Обобщенный алгоритм решения задач НЛП
Эффективное решение различных задач нелинейного программирования может быть осуществлено на основе учета конкретных особенностей этих задач. При этом под эффективностью того или иного алгоритма, ка
Аналитические методы решения задач НЛП
В некоторых случаях задачи НЛП удается решить аналитически. Это, в частности, удается в том случае, если ЦФ и ОДА являются выпуклыми. Обобщенный алгоритм решения задачи НЛП включает в себя следующи
Численные методы решения задач НЛП
В качестве r(xk) используется направление, в котором наиболее сильно возрастает целевая функция. Это направление задается градиентом функции ÑF(xk). Суть метода состоит
Постоянный шаг.
Задается hk = h = const, при этом должно выполняться условие
F(xk+1) = F(xk + hkÑF(xk)) > F(xk).
Пусть
Наискорейший подъем.
Если подставить в выражение для F(x) значение x=xk+1 в соответствии с (1), то получим выражение F(xk+hkÑF(xk)), как функцию от величины шага. След
Функции Лагранжа
Исторически первым способом сведения задачи с ограничениями к задаче безусловной оптимизации явилось использование функции Лагранжа L(x,m)
L(x, m) = f(x) + mт(b - j(x)) = f(x) +
Штрафные функции
Исходная задача условной оптимизации сводится к последовательности задач безусловной оптимизации функций
Fk(x, m) = f(x) - Sk(x, mk), k = 1,2,3,....
Методы прямой условной оптимизации
Методы прямой условной оптимизации предназначены для непосредственного решения задачи выпуклого программирования в условиях ограничений, описывающих множество допустимых решений D.
Итак, п
Метод условного градиента
Существо метода условного градиента состоит в том, что, если известна некоторая точка xkÎD, то направление возрастания целевой функции может задаваться некоторой внутренней или кра
Постановка задачи целочисленного программирования
Первые упоминания о линейных уравнениях возникли ещё за несколько веков до нашей эры.
В Древней Греции Диофант (II-III в.) формулирует уравнения, в которых искомые переменн
Характерные особенности задач многокритериального выбора
Реальные задачи выбора, возникающие на практике, чрезвычайно разнообразны, но всех их объединяет общая схема поиска решения, суть которой состоит в формировании совокупности операци
Принцип В.Парето в задачах многокритериального выбора
В п. 4.1 было установлено, что для корректного решения задач многокритериального выбора необходимо в исходную постановку задачи (4.1)‑(4.2) привнести дополнительную информацию
Принятие решений в условиях стохастической среды
Постановка задач принятия решений в условиях стохастической среды имеет вид
(D(w), f(w)), wÎW,
где D(w) - множество допустимых альтернатив, f(w) - целевая функция.
Методы детерминизации.
При решении конкретных задач выбора на вероятностных структурах часто вводится предположение о том, что задание целевой функции f(w) и ограничивающих отношений ri(w), i=1,...,m, определя
Методы имитационной оптимизации.
В методах имитационной оптимизации (прямых методах стохастического выбора) не производится преобразование задачи к ее детерминированному эквиваленту. Суть данных методов заключается в том, что гене
Принятие решений в условиях целенаправленной среды
Принятие решений в условиях целенаправленной среды связано с тем, что известна цель среды, в соответствии с которой она выбирает свои состояния и которую преследует в своих действиях. Эти действия
Постановка задач игрового выбора.
Рассмотрим формализованное представление задачи принятия решений в условиях целенаправленной среды. Обобщенную задачу принятия решения в условиях неопределенности можно записать в виде
(D
Матричные игры. Чистые и смешанные стратегии.
Простейшим вариантом игры является антагонистическая игра, в которой противодействуют две оперирующих стороны (2 игрока), при этом множества различных альтернатив из которых они выбирают решения ко
Методы нахождения оптимальных смешанных стратегий.
Процедура нахождения оптимальных чистых или смешанных стратегий соответствует выявлению рациональной линии поведения противников в конфликтной ситуации, описываемой игровой моделью. Поэтому такую п
Принятие решений в условиях неизвестной среды
В случае неизвестной среды нет достаточных оснований для предположений о том, какие значения будут принимать параметры, характеризующие состояние среды на рассматриваемом временном интервале. При э
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов