Джоффрион
Cтраница 1
Джоффрион [1] формализовал эту идею следующим образом. [1]
 |
Аппроксимация касательны. [2] |
Джоффрион в [2] предложил альтернативный подход к решению координирующей программы. [3]
Общая схема метода в терминах задачи целочисленного программирования, недавно предложенная Джоффрионом и Марстеном [58], согласуется с нашим подходом, но является менее подробной. Мы покажем, каким образом девятка параметров может быть использована для описания класса обычных алгоритмов ветвей и границ для общей задачи о перестановках, включая общую задачу составления расписаний [25, 128], пространство допустимых решений которой является подмножеством множества всех перестановок п объектов. В рамках этой основной схемы мы опишем ряд теоретических результатов, ка сающихся поведения чисел порождаемых вершин и активных вершин как функций от выбора девятки параметров Как мы увидим, эти результаты подтверждают одни наши интуитивные представления и опровергают другие. [4]
Следует заметить, что отличие гибкой процедуры перебора от аддатив-ного алгоритма в форме Джоффриона заключается в том, что при замене выбранной переменной на фиксированную выбор этой переменной производится по правилу Балаша. В алгоритме Балаша для этой цели в списке выбиралась крайняя правая выбранная переменная. Число итераций при этом нововведении сокращается примерно на 40 % [181] при незначительном увеличении времени счета одной итерации. [5]
На основе подхода Куна-Таккера - Мукая [363] и с учетом известной теоремы Да Канхи-Поллака - Джоффриона [206] в [213, 230] сформулированы необходимые условия слабой оптимальности по конусу. [6]
Решения, которым соответствуют собственно эффективные оценки, также называются собственно эффективными, или оптимальными по Джоффриону. [7]
Формирование точной информации о взаимных локальных изменениях показателей, как это делается, например, в методе Джоффриона при вычислении вектора коэффициентов замещения, предъявляет высокие квалификационные требования к проектировщику. Это естественно повышает трудоемкость решения задачи многокритериальной оптимизации. Для преодоления этого недостатка в ряде работ предлагается диалоговая процедура с лингвистическим моделированием предпочтений. [8]
Касательной гиперплоскости с опорным показателем J - соответствует матрица А WT, где компоненты W / вектора W представляют собой коэффициенты замещения, вычисленные по алгоритму Джоффриона. [9]
Легко показать [32, 83, 206], что если компоненты У, показателя J, a также множество Q - выпуклые, то между множеством Jo ( 2) собственно эффективных ( оптимальных по Джоффриону) [206] решений задачи (3.7) и множеством Л вида (3.10) существует взаимнооднозначное соответствие. Таким образом, при заданной структуре функции O ( J, А) вектор А е Л полностью определяет решение на множестве Парето. На каждой диалоговой итерации проектировщик производит коррекцию вектора А, с тем, чтобы в конечном счете выйти на нужное решение. [10]
В § 4 было указано, что задача многокритериальной оптимизации является специальным случаем задачи оптимизации относительно конуса. Однако понятие собственной эффективности ( по Джоффриону) существенно использует координатный характер отношения и поэтому на более общий случай оптимизации относительно конуса прямо не переносится. В связи с этим Борвейном [124] было предложено общее определение собственной эффективности, которое мы сформулируем здесь применительно к многокритериальной задаче оптимизации. [11]
Переменные х далее разделяются на множества зависимых и независимых путем анализа базисных матриц. Это расчленение позволяет исключить зависимые переменные и блочные ограничения из задачи, что приводит к проблемам меньшей размерности. При исключении зависимых переменных теряется контроль за выполнением условий их неотрицательности. Таким образом, можно сказать, что эти ограничения ослабляются, релаксируются, и требуются дополнительные итерации, определяющие такое новое расчленение, чтобы в конечном счете условия неотрицательности оказались выполненными. Поскольку, как было указано Джоффрионом [1], концепция релаксации ограничений является объединяющей идеей, в рамках которой может быть понята работа всех этих методов, мы начнем с обсуждения этой концепции. [12]
Страницы: 1