Методы многокритериальной оптимизации

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

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

Наиболее общая математическая формулировка многокритериальных задач принятия решений представлена выражениями (2.12), (2.13) к общей формулировке многокритериальной задачи принятия решения могут сводиться задачи различного происхождения, которые можно классифицировать на четыре типа:

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

2. Задачи оптимизации на множестве объектов. Рассматривается совокупность объектов, качество функционирования каждого из которых оценивается самостоятельным критерием; качество функционирования совокупности объектов оценивается векторным критерием, составленным из частных критериев, характеризующих каждый объект.

3. Задачи оптимизации на множестве условий функционирования – задан спектр условий, в которых предстоит работать объекту, и применительно к каждому условию качество функционирования оценивается некоторым частным критерием.

4. Задачи оптимизации на множестве этапов функционирования – рассматривается функционирование объекта на некотором интервале времени, разбитом на несколько этапов; качество управления на каждом этапе оценивается частным критерием, а на множестве этапов – общим векторным критерием.

В задачах 2, 3, 4-го типа частные критерии имеют обычно единую размерность.

Для случая, описываемого выражениями (2.12), (2.13), вид платежной матрицы (см таблицу 3.2) остается прежним. Длатежные матрицы соответствующие каждому частному критерию, будут образовывать макростолбцы общей платежной матрицы исследуемой ситуации. Для случая детерминированной задачи вся информация для принятия решения также будет соответствовать определенному критерию, а не набору значений неопределенных факторов.

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

для критериев, которые стремятся увеличивать, и

для критериев, которые стремятся уменьшить. При этом иозначают соответственно максимальное или минимальное значениеp-го критерия оптимальности.

Таким образом, после нормировки вместо матрицы , в который элементы столбцов имели различную размерность, получается матрица, размерность элементов которой от 0 до 1:.

К полученной матрице в принципе можно применять критерии, приведенные выше. Однако в ситуации принятия решений по многим критериям исследователь зачастую обладает дополнительной информацией о важности того или иного критерия оптимальности. Эта эвристическая информация с помощью методов экспертной оценки может формироваться в виде коэффициентов важности каждогоp-го критерия –.

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

критерий справедливости абсолютной уступки

;

критерий справедливой относительной уступки

,

где – нормированное значениеp-го критерия оптимальности;λ_p– коэффициент важности сверткиp-го критерия.

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

Именно поэтому в последнее время большое распространение среди методов многокритериальной оптимизации получили человеко-машинные процедуры. В отличие от других групп методов многокритериальной оптимизации, где мнение руководителя ( в дальнейшем лица, принимающего решение, или сокращенно ЛПР) о важности отдельных критериев в том или ином виде выявляется до решения конкретной задачи, человеко-машинные процедуры работают в диалоговом (интерактивном) режиме с ЛПР. Машинная программа, реализующая человеко-машинную процедуру, выводит информацию для ЛПР в виде распечаток или непосредственно на дисплей. ЛПР анализирует эту информацию и вырабатывает свои представления по поводу соотношения важности целей в конкурентной ситуации, в том числе и с учетом качественной, неформализуемой информации, затем эти новые предпочтения вводятся в ЭВМ и происходит их обработка. Далее для ЛПР вновь выводится информация, в которой учтено его предыдущее мнение, и цикл повторяется до тех пор, пока не будет получено решение, удовлетворяющее ЛПР. Различные человеко-машинные процедуры отличаются друг от друга видом информации, представляемой ЛПР на каждой итерации, а также формой, в которой ЛПР вырабатывает и вводит в ЭВМ предпочтения по важности целей. Выбор той или иной процедуры для решения конкретной задачи должен основываться на максимально полном удовлетворении следующих требований: обеспечение доверия ЛПРом; пригодность получаемой информации для принятия решения; высокая скорость сходимости решения.

Максимальное доверие к решению обеспечивают процедуры, в которых удается наиболее наглядно показать все альтернативные решения, обеспечить легкость использования и понимания метода работы человеко-машинной процедуры ЛПР, сходство действий ЛПР с методикой его работы без использования процедуры. Иллюстрацией работы человеко-машинной процедуры может быть пример использования модифицированной процедуры С. Зайонца и Ю. Валлениуса.

Укрупненный алгоритм модифицированной процедуры следующий.

1.Ввод исходной информации для расчета значений критериев и ограничений математической модели.

2. Присвоение начальных значений коэффициентам важности для свертки критериев оптимальности в единую целевую функцию вида (maxиminв зависимости от смысла решаемой задачи). При этом должно выполняться условие. Для первой итерации допустимо задавать равные значения коэффициентов.

3. Решение задачи отыскания оптимального решения (базового) решения модели на основе единой целевой функции

. (3.9)

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

Например, при наличии трех критериев оптимальности возможно формирование трех вариантов (), близких к базовому по критериям

,

если предполагается увеличение на величину епервого критерия;

,

если увеличивается второй критерий, и

при увеличении третьего критерия.

5. Решение задач отыскания оптимального решения для всех сгенерированных вариантов, близких к базовому, по вновь полученным в п. 4 целевым функциям и вывод на печать или дисплей базового или близки[ к енму вариантов решений.

6. Анализ базового или близких к нему вариантов решения ЛПР и ввод парных предпочтений для каждого из вариантов решений по отношению к базовому («+» – вариант более предпочтителен, чем базовое решения; «-» – вариант менее предпочтителен, чем базовое решение).

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

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

. (3.10)

При этом ограничения при максимизации единой целевой функции имеют вид:

а) для каждого k-го варианта, который признан ЛПР более предпочтительным, чем базовый,

, (3.11)

где ξ –некое достаточно малое число, например,ξ=0,001;– значениеp-го критерия дляk- го и базового вариантов соответственно;

б) для каждого k-го варианта, который признан ЛПР менее предпочтительным, чем базовый, записываются ограничения вида

; (3.12)

В) получивший набор значений должен соответствовать условию

. (3.13)

10. Получение новых значений коэффициентов свертки критериев () при решении математической модели (3.10) – (3.13) с помощью симплекс-метода и переход к блоку 3.

При минимизации единой целевой функции (3.9) ограничения (3.11) и (3.12) меняются местами.

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

1. Раскройте основные положения и содержание этапов аналитического исследования при поиске оптимальных решений для однокритериальных моделей.

2. Раскройте основные положения и содержание этапов исследования при помощи численных методов в процессе поиска оптимальных решений для однокритериальных моделей.

3. Раскройте основные положения и содержание этапов экспериментальной оптимизации на ЭВМ при поиске оптимальных решений для однокритериальных моделей.

4. Представьте основные особенности организации поиска решений при наличии в модели случайных факторов

5. В чем заключается суть сведения стохастической задачи к детерминированной?

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

7. Опишите основные методы и подходы при реализации процедур принятия решений при наличии в модели неопределенных факторов

8. Что такое платежная матрица? Опишите ее структуру и назначение.

9. Опишите порядок нахождения решений в конфликтной ситуации при использовании моделей с неопределенными факторами. Представьте основные критерии, используемые при этом

10. Что такое многокритериальная оптимизация? Приведите классификацию типов задач многокритериальной оптимизации. Опишите основную суть методов многокритериальной оптимизации.