Упражнения к § 7
№ 1. Решить задачу векторной оптимизации методом последовательных уступок:
1)
если
и
2)
если
и
№ 2.
Пользуясь результатами теоремы 3, для
эффективной точки
найти такие величины уступок
,
что
является решением ЗВМ методом
последовательных уступок:
1)
если = (1/2; 1/2);
2)
если = (1/3; 2/3);
3)
если = (2; 1);
4)
если = (3, 5; 0, 5);
5)
если = (2; 3);
6)
если = (2; 2).
§ 8. Целевое программирование
Рассмотрим
допустимое множество
–
критерии оценки векторов множества
.
Будем предполагать, что в критериальном
пространстве
задано непустое, выпуклое множество
такое, что любые векторы
из множества
,
где
,
являются “хорошими” для лица, принимающего
решения.
Множество задается посредством введения ограничений на принимаемые критериями значения, которые можно разделить на следующие группы:
1)
2)
3)
4)
Если
пересечение множеств
достижимого множества
в пространстве критериев
не является пустым (
),
то решением задачи выбора являются
точки
.
Однако, как правило,
).
Тогда множество
называется утопическим
множеством в пространстве критериев,
а
– утопическим
множеством в пространстве решений.
В этом случае ставится задача отыскания
таких точек
допустимого множества
,
критериальные векторы
которых наиболее близки в смысле
введенной меры близости к утопическому
множеству. Такая задача носит название
задачи целевого
программирования (ЦП).
В качестве методов целевого программирования
решения задачи векторной максимизации
рассмотрим метод
идеальной точки и метод сведения к
архимедовой задаче.
Метод идеальной точки
Рассмотрим
ЗВМ (2) и точку
где
– оптимальное значение функции цели
в k-й
частной задаче:
Как
правило, точка
,
называемая идеальной точкой, не
принадлежит достижимому множеству в
пространстве критериев и тем самым
образует утопическое множество. Тогда
ставится задача отыскания таких векторов
,
критериальные векторы которых наиболее
близки в смысле введенного расстояния
,то
есть решается задача:
(28)
В
качестве функции
может быть выбрана одна из следующих
метрик в пространстве
:
1)
;
2)
где
В силу свойств функции расстояния, получаемые в ходе решения задачи (28) точки являются Парето–оптимальными.
Метод сведения к архимедовой задаче
Рассмотрим задачу целевого программирования, в которой задаваемые экспертом ограничения на критерии разделены на следующие группы:
(X) ≥
,
;(X) =
,
3)
≤
(X)
≤
,
.
Введем
в рассмотрение переменные величины
,
,
называемые переменными
нежелательных отклонений
критериев. Архимедова задача заключается
в отыскании таких векторов
,
для которых взвешенная сумма нежелательных
отклонений принимает наименьшее
значение:
ΩA
(29)
где
,
- задаваемые экспертом веса, характеризующие
важность нежелательных отклонений.
Архимедова задача (29) может быть решена методами линейного программирования. При этом отметим, что целевые ограничения в задаче (29) являются нежесткими в том смысле, что они не ограничивают допустимую область Ω в пространстве решений. В действительности они пополняют область допустимых решений, переводя Ω в пространство большей размерности и создавая таким образом расширенную (или архимедову) область допустимых решений для задачи ЦП.
Для задач целевого программирования вводится следующее определение эффективной точки.
Определение
1.
Пусть
–
вектор нежелательных отклонений,
соответствующий точке
.
Будем говорить, что точка
ЦП-эффективна
(в смысле минимизации отклонений), если
не существует другой точки
,
которой соответствует вектор
,
удовлетворяющий условиям:
,
.
Так как целевая функция в задаче (29) представляет собой взвешенную сумму нежелательных отклонений, то решением архимедовой задачи является ЦП-эффективная точка.
Для определения ЦП-эффективного множества можно использовать аппарат векторной оптимизации, образуя минимизируемые критерии из переменных нежелательных отклонений:
(
.
В
случае, если критерии в задаче ЦП
упорядочены по важности (
возможно использование методов
лексикографической оптимизации. В этом
случае задача целевого программирования
решается методом лексикографического
ЦП:
,
,
.
Если при этом критерии ЗВМ упорядочены нестрого, и некоторый уровень приоритета включает отклонение нескольких критериев (целей), то один из возможных способов постановки задачи – минимизация максимального отклонения для критериев одного уровня. В этом случае вводится минимаксная переменная λ и критерий на рассматриваемом уровне приобретает вид:
.
Составляя -задачу на рассматриваемом уровне приоритета, необходимо выписать столько дополнительных ограничений, сколько имеется переменных отклонения на данном уровне (см. пример 2).
Рассмотрим некоторые примеры.
Пример 1. Построить архимедову задачу и найти ее решения, если
=
,
=
,
,
,
где
=
8,
=
7.
Решение. Допустимое множество исходной задачи изображено на рисунке 16 и представляет собой многоугольник OABC, где O = (0,0), A = (0,4), B = (4,6), C = (10,0).
Утопическим
множеством в пространстве критериев
является точка
=
.
Достижимое множество
,
а также утопическое множество
представлены на рисунке 17. Архимедова
задача имеет вид:
+
+
+
→ min,
При
,
целевая функция архимедовой задачи
имеет вид:
.
Рассмотрим
линии уровня архимедовой целевой функции
в координатах (
,
для чего координатную плоскость разобьем
на следующие области:
Рассмотрим область, определяемую условием 1). В этой области
Линии уровня функции цели:
При
этом
Тогда
то есть:
Тогда:
Соответствующий
участок линии уровня изображен на
рисунке 18 при
и на рисунке 19 при
.
Аналогично в области, определяемой условиями 2), получаем
Линии уровня в этом случае задаются следующим уравнением:
Рассматривая
оставшиеся два случая, получаем, что
при
линии уровня архимедовой целевой
функции – это горизонтально сжатые
ромбы с центром в точке
(рис.19). Следовательно, критериальный
вектор
– это решение архимедовой задачи ЦП,
так как
– это общая точка; точка наименьшего
ромба с центром в точке
и достижимого множества
в пространстве критериев, как показано
на рисунке 18. Соответственная точка в
пространстве решений имеет вид:
При
ромбы сжаты по вертикали (рис.19), а точка
– решение архимедовой задачи ЦП в
критериальном пространстве, которой
соответствует точка
в пространстве решений.
Пример
2.
Сформулировать ЦП-задачу минимизации
максимальных отклонений, если
для задачи:
;
;
;
;
;
Решение. Лексикографическая формулировка задачи ЦП имеет вид:
,