g11 (542474), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Для этого необходимо решить такую задачу:

Такую задачу пришлось решать численно и получено:

Замечание.

Как и в предыдущих приемах , в общем случае, гарантий того, что получено эффективное решение, нет .

Прием 5. Теоретико-игровая модель выбора весовых коэффициентов.

В этом способе выбора весовых коэффициентов используют элементы матрицы :

где

- точка оптимума - того частного критерия.

Значения характеризуют влияние решения на частный критерий .

Очевидно, что

, а

поскольку мы берем по абсолютной величине.

Строится матрица , она будет квадратной:

Эту матрицу рассматривают как матрицу платежей в игре двух лиц с нулевой суммой.

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

Партию игры можно представить следующим образом:

первый игрок может выбрать одну из чистых стратегий , а второй игрок выбирает одну из чистых стратегий .

В этой игре «maxmin» равен 0, а «minmax» равен

то есть игра не имеет седловой точки.

Это означает, что оптимальное решение игры следует искать в форме смешанных стратегий, то есть:

для первого игрока каждая стратегия

выбирается с вероятностью ,

выбирается с вероятностью ,

...........................................................

выбирается с вероятностью

.

Для второго игрока с вероятностями

выбирается с вероятностью ,

выбирается с вероятностью ,

...........................................................

выбирается с вероятностью

.

Смешанная стратегия второго игрока может быть найдена из решения задачи линейного программирования, представленной в виде:

Решая эту задачу и получив значения находят значения :

.

В качестве примера снова рассмотрим задачу ( 11.1 .0 ):

Матрица принимает вид:

Решаем задачу вида:

Графически решая ее получаем:

,

Следовательно:

Прием 6. Определение весовых коэффициентов по разности максимального и минимального элемента матрицы .

- это матрица предпочтений.

Используется матрица , построенная по алгоритму, изложенному в приеме 5.

где

Вычисляются:

Далее вычисляются:

Значения таким образом вычисляют по формуле:

.

Вернемся к примеру ( 11.1 .0 ) и применим к нему прием 6 :

Матрица принимает вид:

Далее:

Следовательно:

Прием 7. Определение весовых коэффициентов при одинаковом приоритете частных критериев.

В этом способе выбора весовых коэффициентов определяется по формуле:

критерии равноправны.

11.2.2Решение задач векторной оптимизации при наличии дополнительной информации о важности частных критериев оптимальности.

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

11.2.2.1Метод выделения главного критерия.

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

( 11.2.0 )

где - некоторые пороговые значения соответствующих критериев.

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

но в этом случае ограничения на будут слабыми и решение задачи ( 11.2 .0 ) будет близко к решению задачи:

то есть критерии слабо влияют на результат.

Довольно распространенным является следующий подход . Выбирается некоторый относительный порог

/ часто он бывает одинаков для различных критериев, так как является безразмерной величиной / отклонения критерия от своего минимума:

где

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

Вернемся к примеру из раздела 11.1:

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

Пусть главным критерием будет , а величину порога будем задавать различной: .

.

Решаем геометрически однокритериальную задачу:

Получаем .

Теперь решим задачу при :

Получаем .

И, наконец, положим

Получаем .

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

В нашем примере, при получили решение, которое совпало с решением однокритериальной задачи / ограничение на не сыграло роли /.

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

Метод выделения главного критерия, как и все последующие методы этой главы, состоит в замене постановки исходной задачи ( 11.1 .0 ) некоторой другой, например ( 11.2 .0 ) , и в решении этой задачи. При этом возможны два подхода:

1. замена постановки производится затем, чтобы работать с этой новой постановкой , не возвращаясь к старой;

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

В первую очередь полученное решение исследуется на эффективность. Наиболее распространенным условием проверки на эффективность служит следующая теорема:

Теорема. Решение является эффективной точкой тогда и только тогда, когда оно минимизирует на множестве .

Вернемся к нашему примеру и проверим, например, решение, соответствующее .

Для этого необходимо решить задачу:

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

Пусть каким-то образом мы получили решение / заведомо мы знаем, что это неэффективное решение, так как оно не принадлежит области Парето /.

Итак, снова решаем задачу однокритериальной оптимизации:

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

В заключение этого раздела необходимо сделать замечание.

Замечание.

Метод выделения главного критерия позволяет в лучшем случае получить одно из нескольких эффективных решений.

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

11.2.2.2Метод последовательной оптимизации с учетом жесткого приоритета.

Этот метод применяется в случае , если для всех частных критериев оптимальности задано предпочтение по важности:

то есть считается, что критерий более важен , чем критерий и все последующие критерии , критерий более важен, чем критерий и так далее.

В этом случае решение доминирует над , если:

или ,

или , ..., ,

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

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

1-ый шаг.

Решается задача:

( 11.2.0 )

Пусть - множество решений задачи ( 11.2 .0 ).

Если - пусто, то принимается, что исходная многокритериальная задача решения не имеет. Если - состоит из одного элемента , то этот элемент признается решением задачи ( 11.1 .0 ) . Если - содержит более одного элемента , то осуществляется переход к шагу 2.

2-й шаг.

Решается задача:

( 11.2.0 )

- множество решений задачи ( 11.2 .0 ).

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

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

Таким образом, этот метод не позволяет справедливо учесть интересы менее важных критериев, так как не допускает уменьшение менее важных критериев , если это вызывает хотя бы незначительное увеличение важных по уровню приоритета частных критериев оптимальности. Этот недостаток в какой-то мере удаётся устранить в методе последовательных уступок.

Характеристики

Список файлов книги