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

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

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

Итак, как и выше, исходная задача ( 11.1 .0 ) заменяется задачей ( 11.2 .0 ), поэтому возникает справедливый вопрос: как соотносятся решения этих задач ?

У постановщика задачи здесь могут быть два принципиально различных подхода:

1. переход от постановки ( 11.1 .0 ) к ( 11.2 .0 ) производится путем тщательного анализа, в результате которого постановка ( 11.2 .0 ) полностью заменяет исходную постановку, получением решения задачи ( 11.2 .0 ) завершается работа;

2. признается, что постановка ( 11.2 .0 ) не полностью заменяет постановку ( 11.1 .0 ), поэтому решение задачи ( 11.2 .0 ) анализируется в первую очередь на эффективность.

Для этой цели применяется критерий эффективности, о наиболее употребляемом критерии упоминается в разделе 11.2.2.1

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

Наиболее распространенными свертками являются :

1)

при имеем наиболее употребительную из всех линейную свертку:

2)

3)

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

11.2.1.2Линейная свертка и ее свойства.

Популярность линейной свертки обусловлена тем, что с одной стороны часто нормализованные критерии обладают свойством аддитивности, с другой стороны коэффициенты можно рассматривать как "удельные веса" критериев, отражающие их важность. И, наконец, для выпуклых задач / все и выпуклы / конструктивный характер носит теорема Карлина:

В выпуклой задаче ( 11.1 .0 ) оптимальна по Парето, если существует вектор ,

такой, что

( 11.2.0 )

и обратно, если оптимальная по Парето, то найдется вектор , удовлетворяющий ( 11.2 .0 ).

Конструктивность этой теоремы можно рассматривать с двух позиций:

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

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

Замечание.

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

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

Поучительным будет рассмотрение с этих позиций нашего примера ( 11.1 .0 ) :

Применим свертку: .

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

Здесь удается применить классический метод, приводящий к простой системе уравнений:

Мы знаем из первой главы, что точка является эффективной. Кроме того, в первой главе мы выяснили, что множеством эффективных точек является отрезок . Применим линейную свертку, фиксировав . Получаем однокритериальную задачу:

Решением будет , откуда видим, что взяв любое , получаем .

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

Эффективным решением будет :

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

Эффективным решением будет :

Получили , как и следовало бы ожидать, существенно ближе к точке минимума , чем , во втором случае наоборот: существенно ближе к точке минимума , чем .

Существует несколько приемов , позволяющих по постановке задачи определять значения или как часто их называют - весовых коэффициентов.

11.2.1.3 Методы определения весовых коэффициентов.

Прием 1.

Для каждого частного критерия вычисляется коэффициент относительного разброса:

( 11.2.0 )

где

, иначе прием 1 применять нельзя.

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

( 11.2.0 )

При таком подходе в обобщенном критерии "большой вес" имеют те критерии, у которых минимальное значение частного критерия сильно разнится от максимального. Действительно, если - близки, то при любом полученное решение будет близко к . И, наоборот, чем больший разброс имеет некоторый критерий , тем с большим весом его необходимо взять в линейной свертке. В предельном случае, когда

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

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

Выше для этого примера мы получили общий вид решения:

в зависимости от .

Наконец получаем: .

Получили одну из эффективных точек для задачи ( 11.1 .0 ).

Замечание 1.

Следует обратить внимание на то, что при таком подходе "важность" критерия полностью определяется поведением функции на области .

Прием 2.

Может применяться при условии . Вводятся в рассмотрение вспомогательные функции:

которые можно рассматривать как относительное отклонение частного критерия от его наименьшего значения.

Важность - го критерия определяется через неравенство:

, где задает постановщик задачи:

чем важнее критерий, тем меньше . Затем для каждого критерия вычисляется радиус шара , имеющего

центром , являющуюся решением задачи:

,

внутри которого выполняются условия: .

Далее вычисляются по формуле:

.

При таком подходе важность критерия определяется двумя факторами:

• выбор величины ;

• видом функции .

Это является бесспорным достоинством метода. Проиллюстрируем на нашем примере ( 11.1 .0 ):

Назначим .

На этом этапе мы не даем ни одному из двух критериев никакого предпочтения.

.

В результате получили, что 1-й критерий оказался важнее 2-го.

Замечание.

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

Прием 3. Использование попарных приоритетов.

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

Наиболее приемлемым подходом является попарное сравнение критериев по важности в количественном выражении.

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

По имеющейся информации о степени предпочтения, по важности каждой пары частных критериев составляется матрица размерности , где

равно числителю

равно знаменателю

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

Зададимся конкретными данными:

.

.

Вопреки ожиданиям, наибольшим получили .

Дело в том, что здесь сыграли роль именно количественные показатели:

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

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

Прием 4. Использование интервальной информации.

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

С постановочной точки зрения этот подход предпочтительнее предыдущих.

Математически он приводит к решению следующей однокритериальной задачи с переменными:

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

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

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