Упражнения к § 4

№ 1. Для задач векторной максимизации с заданной функцией полезности ЛПР найти решение в пространстве решений и критериальном пространстве:

1)

.

2)

.

3)

.

№ 2. Решить методом взвешенных сумм

1)

, ,

2)

, ,

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

1)

а) отрезок [A,B]; b) точка B; c) точка C; d) отрезок [B,C], где A=(0,0), В=(0,3), С=(3,3).

2)

а) отрезок [A,B]; b) точка B; c) точка C; d) отрезок [B,C], где A=(3,0), В=( ), С=( ).

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

1)

2)

№ 5. Пусть модель автомобиля оценивается по 2 характеристикам: надежность ( ), максимальная скорость передвижения ( ). Причем автомобиль может быть сконструирован с любой комбинацией данных характеристик, удовлетворяющих системе ограничений:

Критерии выбора , .

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

№ 6. В рамках эксперимента введены единые государственные экзамены по математике и английскому языку. Школьник имеет 100 дней для подготовки к тестам. Оценка, полученная на экзамене, измеряется в 100-балльной шкале и, по прогнозам, пропорциональна количеству дней, затраченных на подготовку к экзамену по данному предмету. Школьник желает получить максимальный балл по каждому предмету. Требуется распределить количество дней на подготовку к каждому экзамену.

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

1. математике; b) английскому; c) ни по математике, ни по английскому; d) по обоим предметам.

§ 5. Принцип максимальной эффективности в принцип гарантированного результата

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

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

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

Нормализация критериев ЗВМ

Под способом нормализации критериев ЗВМ будем понимать однозначное отображение такое, что:

1. Решение задач:

,

(11)

должны совпадать для каждого .

2. Нормализованные критерии должны быть измерены в одних и тех же единицах.

3. В оптимальных точках каждой частной задачи (11) величины всех критериев должны иметь одинаковую величину, т.е.

,

где ­– оптимальное значение функции цели k-й частной задачи.

Только при выполнении названных выше требований представляется возможным сравнить критерии по их численному значению. Для нормализиции критериев в ЗВМ в качестве отображения используется линейное преобразование:

не влияющее на результат решения каждой частной задачи.

Рассмотрим один из способов нормализации задач векторной максимизации.

Пусть для любого k конечны следующие величины:

Тогда:

1. критерии нормализованы, если каждый из них удовлетворяет соотношению:

2. критерии нормализованы, если каждый из них удовлетворяет соотношению:

Здесь называется относительной оценкой по k-му критерию точки и представляет собой степень достижения оптимума в точке по k-й компоненте векторного критерия; называется относительным отклонением достижения оптимума по k-му критерию.

Очевидно выполнение следующих свойств:

1. 

2. 

3. 

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

Замечание 1. Кроме естественной нормализации известны следующие типы нормализации:

1. нормализация сравнения:

2. нормализация Сэвиджа:

3. нормализация осреднения:

Итак, рассмотрим ЗВМ с нормализованными критериями

Обозначим через , где – заданная величина, .

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

Принцип гарантированного результата

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

(12)

Точка обладает свойством: (другими словами, ), т.е. оценка по k-му частному критерию в оптимальной точке не ниже величины .

Приведем алгоритмы решения ЗВО каждым из рассмотренных принципов.

Алгоритм 1. Алгоритм реализации принципа гарантированного результата

Шаг 0. Рассматривается задача векторной максимизации (2), - частные критерии задачи, , – допустимое множество.

Шаг 1. Решение частных задач вида:

- максимальное значение функции цели;

- минимальное значение функции цели.

Шаг 2. Нормализация частных критериев:

Шаг 3. Формирование функции

Шаг 4. Решение задачи:

(*)

– решение задачи (*) является решением ЗВМ с принципом гарантированного результата. Останов.

Отметим, что, если число переменных и критериев в ЗВМ равно 2, то возможное графическое решение ЗВМ принципом гарантированного результата с использованием множества достижимости (см. пример 1).

Принцип максимальной эффективности

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

где , т.е.

(13)

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

Алгоритм 2. Алгоритм решения ЗВМ принципом максимальной эффективности

Шаг 0. Рассматривается задача векторной максимизации (2), - частные критерии задачи, , – допустимое множество.

Шаг 1. Решение частных задач вида:

- максимальное значение функции цели;

- минимальное значение функции цели.

Шаг 2. Нормализация частных критериев:

Шаг 3. Решение -задачи

– решение -задачи является решением ЗВМ.

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

Свойства принципов максимальной эффективности

и гарантированного результата

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

Теорема 1. Принцип максимальной эффективности совпадает с принципом гарантированного результата, т.е. .

Доказательство

1. Покажем, что .

2. Покажем, что .

В силу определения множества и выполнения условия ; имеем:

Из доказанных п. 1 и 2 следует справедливость теоремы. Что и требовалось доказать.

Таким образом, задача (12) сводится к эквивалентной ей задаче (13), которая представляет собой задачу скалярной оптимизации.

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

. (14)

В дальнейшем для определенности будем рассматривать принцип гарантированного результата, подразумевая его эквивалентное представление в виде (14).

Взаимосвязь множества решений задач (12), (13) и множества эффективных точек ЗВМ нашла свое отражение в следующих теоремах.

Теорема 2. Решение –задачи есть слабоэффективный вектор.

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

Тогда , а следовательно,

что противоречит предположению о том, что есть решение задачи (13). Теорема доказана.

На основе ЗВМ (2) построим ЗВМ следующего вида:

где – константы.

Теорема 3. Решение не зависит от положительного линейного преобразования частных критериев.

Доказательство. Докажем, что решения ЗВМ (2) и задачи (15) совпадают.

Пусть - нормированные критерии задачи (2),

где

Аналогично: . Тогда

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

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

Лемма 1. В выпуклой ЗВМ, решенной на основе нормализации критериев и принципа гарантированного результата, в оптимальной точке всегда найдется 2 критерия с индексами q и p, для которых выполняется равенство: , а остальные критерии определяются неравенствами .

Доказательство. Первоначально докажем, что существует хотя бы один критерий q, для которого , а затем докажем, что таких критериев два.

1. Предположим противное: не существует ни одного критерия q, для которого , т.е. .

Рассмотрим

тогда , т.е. не является решением задачи максимизации (12), получили противоречие.

2. Предположим, что существует только один критерий, для которого . Рассмотрим величину .

Тогда .

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

,

и для которого остается строгое неравенство:

(**)

Такое увеличение критерия может идти до тех пор, пока относительная оценка одного из критериев p не будет равна относительной оценке критерия k, т.е. строгое неравенство (**) не станет равенством. В результате получили, что существует два критерия p, q, большие , что противоречит решению ВЗМ с принципом гарантированного результата, в котором –максимальная величина. Остается принять, что существуют критерии p,q, относительные оценки которых равны . А остальные критерии определяются как что и требовалось доказать.

Теорема 4. В выпуклой ЗВМ, решенной на основе нормализации критериев и принципа гарантированного результата, точка оптимума оптимальна по Парето, причем такая точка только одна.

Доказательство. Пусть - решение задачи (12).

Тогда в точке оптимума , или

(16)

Согласно лемме 1, система неравенств (16) выполняется как равенство хотя бы для двух критериев, т.е. существуют индексы p и q такие, что:

а для остальных индексов

Рассмотрим новую точку X’, которая получается из добавлением приращения такого, что критерий q увеличился:

Тогда

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

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

Следовательно, не существует другой точки , для которой бы выполнялось равенство , а остальные критерии удовлетворяли бы неравенствам

Таким образом, точка не оптимальна по Парето, что и требовалось доказать.