Методы оптимальных решений

 

Лекция 9

 

Тема лекции  9: «Задачи многокритериальной оптимизации в экономике»

Разделы лекции:

 

1. Постановка задачи многокритериальной оптимизации.

2. Оптимальность по Парето.

3. Метод идеальной точки.

 

РАЗДЕЛ 1.  ПОСТАНОВКА ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ.

 

В СВЯЗИ С ЧЕМ ВОЗНИКАЮТ ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ?

 

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

 

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

2. Задача со многими критериями оптимизации возникает, например, при выборе работы.  Выбирая работу, человек, как правило, руководствуется несколькими критериями. Например, кому-то хочется, чтобы одновременно выполнялись такие условия:

- заработная плата была как можно выше;

- условия работы были как можно комфортнее;

-  место работы было как можно ближе к дому.

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

 

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

 

5. Еще один пример – выбор инвестиционного решения, когда хочется получить максимальный доход (или доходность) при наименьшем риске.

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

 

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

Рассмотрим простой пример задачи, когда необходимо одновременное выполнение двух условий (критериев), противоречащих друг другу.

 

ПРИМЕР 1. Из железного листа, имеющего форму квадрата со стороной L, требуется скроить коробку максимально возможного объема V при минимальных отходах материала.

 

Вырезав из листа четыре квадрата с неизвестной пока стороной х (рисунок 1) и согнув по линиям, отмеченным пунктиром, мы получим коробку, объем V(x) которой равен
(напомним, что объем параллелепипеда равен произведению площади его основания, умноженной на высоту данного параллелепипеда):

 

V(x)= (L – 2x)²∙x.

При этом теряется железо общей площадью S(x)=4x² (площадь четырех  вырезанных квадратов).

 

Рисунок 1.

По условию задачи требуется одновременное выполнение двух условий (критериев):

(1) V(x)=x∙(L – 2x)²→max,

(2) S(x)=4x²→min,

 

где 0≤x≤L/2.

 

Неравенства 0≤x≤L/2 очевидны: если x=0, то лист железа вообще не режем; если x=L/2, то весь лист уходит в отходы. Таким образом, переменная задачи x принимает следующие значения: 0≤x≤L/2.

 

 

Графики функций y= x∙(L – 2x)² и y=4x² , заданных на отрезке [0, L/2] оси OX представлены на рисунке 2.

 

Рисунок  2. Графики функций y= x∙(L – 2x)² и y=4x² , заданных на отрезке [0, L/2].

 

 

Максимум функции V(x) достигается в точке x*=L/6.

 

Минимум функции S(x) достигается в точке x**=0.

 

Заметим, что нахождение экстремумов функции мы подробно рассмотрели на лекции 7 «Задачи нелинейной оптимизации».

 

Ясно, что одновременно удовлетворить обоим критериям невозможно: минимальные отходы S_min получаются при х=0 (не резать вообще), а максимального объема V_max коробка достигает при х=L/6.

КАКИЕ ЗАДАЧИ НАЗЫВАЮТСЯ ЗАДАЧАМИ ВЕКТОРНОЙ ОПТИМИЗАЦИИ?

 

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

 

КАК ФОРМУЛИРУЕТСЯ ЗАДАЧА МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ?

 

Обозначим через X вектор переменных модели, пусть X={x₁, x₂, …, x_n}. Обозначим i-й частный критерий оптимальности через Zi, i=1, …, m. Обозначим через Q множество допустимых значений переменных модели. Тогда для каждого вектора X, принадлежащего множеству Q, определено значение i-го частного критерия оптимальности  Z_i(Х), i=1, …, m.  

 

В многокритериальной задаче оптимизации  каждому допустимому значению вектора X (X принадлежит множеству Q) ставится в соответствие вектор критериев

 

 Z(X)={Z₁(X), Z₂(X), …, Z_m(X)}.

 

То есть на множестве допустимых решений Q определена вектор-функция  

 

Z: Q → Z(Q),

 

такая, что

 

Z(X)={Z₁(X), Z₂(X), …, Z_m(X)}, "XÎQ.

 

Таким образом, вектор критериев Z – это вектор-функция m переменных Zi, i=1, …, m;  при этом каждая компонента Zi, i=1, …,m,  ставит в соответствие каждому вектору X из множества Q значение i-го частного критерия оптимальности Zi(X).

 

 

Другими словами, на множестве Q задается упорядоченный набор Z={Z₁, Z₂, …, Z_m}, состоящий из  m  функций Zi, i=1, …,m,  каждая из которых ставит в соответствие вектору X значение определенного критерия Zi(X), где вектор X – произвольное допустимое решение (вектор переменных модели).   

 

 

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

 

Z(X)={Z₁(X); Z₂(X); …, Z_m(X)} → max,  (1)

 

при условии, что вектор X принадлежит множеству допустимых решений Q.  (2)

 

 

ПРИМЕР 1 (ПРОДОЛЖЕНИЕ). Сформулируем задачу многокритериальной оптимизации (1), (2) для примера 1.

Вектор X={x} переменных задачи имеет одну действительную компоненту x.

 

Множество допустимых решений Q=[0, L/2] – отрезок действительной прямой OX.

 

Первый частный критерий Z₁ – действительная функция V(x):

 

Z₁(x)=V(x)=(L – 2x)²∙x.

Второй частный критерий Z₂ – действительная функция (– 1)∙S(x):

 

Z₂(x)= (– 1)∙S(x)= – 4x².

Заметим, что при задании критерия Z₂ мы поменяли у функции S(x) знак на противоположный, так как в примере 1 функция S(x) минимизируется, а в задаче (1), (2) каждый критерий максимизируется. При этом условия

 

Z₂(x)→max,

 

и

 

S(x)→min

 

равносильны.

 

Вектор критериев имеет вид:

 

Z(X)={Z₁(X); Z₂(X)}={V(x); – S(x)}={(L – 2x)²∙x; – 4x²}.

 

Таким образом, мы получаем следующую задачу многокритериальной оптимизации:

 

Z(x)={(L – 2x)²∙x; – 4x²} →max, (1’)

 

при условии

 

xÎ[0; L/2].  (2’)

 

Многокритериальная задача выбора решения в общем виде состоит в выборе некоторого допустимого вектора X из множества Q на основе анализа вектора критериев Z(X). При этом предполагается, что вектор критериев Z(X) полностью описывает интересующие ЛПР аспекты принятия решения.

 

КАКОЕ КОЛИЧЕСТВО ЭЛЕМЕНТОВ МОЖЕТ СОДЕРЖАТЬ МНОЖЕСТВО ДОПУСТИМЫХ РЕШЕНИЙ Q?

 

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

 

Так, множество Q в примере 1 бесконечно:

 

Q=[0, L/2].  

 

Если множество допустимых решений Q конечно (скажем, Q состоит из k элементов), то элементы множества Q обычно нумеруют, т. е. множество Q представляют в виде:

 

Q={X₁, X₂,…, X_k}.

 

ЧТО ТАКОЕ МАТРИЦА РЕШЕНИЙ?

 

Если множество допустимых решений Q конечно: Q={X₁, X₂, …, X_k}, то задачу принятия решения в этом случае удобно сформулировать в виде матрицы решений

 

D=

Z1(X1)	…	Zm(X1)
…	…	…
Z1(Xk)	…	Zm(Xk)

 

 

Матрица D  предоставляет полную информацию о задаче принятия решения в случае конечного числа вариантов решения. В этой матрице i-я строка содержит вектор значений критериев  при выборе решения Xi, а j-й столбец  соответствует значениям  j-го критерия Zj при различных вариантах решения.

 

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

 

РАЗДЕЛ 2.   ОПТИМАЛЬНОСТЬ ПО ПАРЕТО.

 

КАКОЕ РЕШЕНИЕ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ ОПТИМИЗАЦИИ НАЗЫВАЕТСЯ ЭФФЕКТИВНЫМ (ОПТИМАЛЬНЫМ) ПО ПАРЕТО?

 

ОПРЕДЕЛЕНИЕ. Вектор X*, принадлежащий множеству допустимых решений Q, называется эффективным (оптимальным) по Парето решением задачи многокритериальной оптимизации (1), (2), если не существует такого вектора X из множества Q, что выполняются неравенства:

 

Z_i(X)≥Z_i(X*), i =1, …, m, (3)

 

причем хотя бы для одного значения j, где 1≤j≤ m, имеет место строгое неравенство:

 

Z_j(X)>Z_j(X*).

 

 

ОПРЕДЕЛЕНИЕ. Если для допустимых решений X₍₁₎ , X₍₂₎ задачи многокритериальной оптимизации (1), (2) выполнены условия:

 

Z_i(X₍₁₎) ≥Z_i(X₍₂₎) , i=1,2, ... , m;

и при этом существует такой критерий Z_j, где1≤j≤ m, что выполнено строгое неравенство:

 

Z_j(X₍₁₎)>Z_j(X₍₂₎),

 

то говорят, что допустимое решение X₍₁₎ доминирует допустимое решение X₍₂₎.

 

Другими словами, будем говорить, что решение X₍₁₎ из множества допустимых решений Q в задаче многокритериальной оптимизации (1), (2) доминирует решение X₍₂₎ из того же множества Q , если X₍₁₎ по каждому из критериев не хуже X₍₂₎,  и при этом хотя бы по одному из критериев – строго лучше.

 

В соответствии с введенным определением решения, оптимального по Парето, получим, что решение X* из множества допустимых решений Q задачи многокритериальной оптимизации (1), (2) будет оптимальным по Парето, если не существует допустимых решений, которые бы его доминировали.

 

ПРИМЕР 2 (ИНВЕСТИЦИОННЫЕ ОПЕРАЦИИ, ОПТИМАЛЬНЫЕ ПО ПАРЕТО).

 

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

Если E — случайная эффективность инвестиционной операции, и в качестве ожидаемой эффективности операции мы выбрали математическое ожидание ME случайной величины E, то в качестве меры риска операции естественно взять среднее квадратичное отклонение

σE = √DE

(здесь DE — дисперсия случайной величины E).

Знание только математических ожиданий и средних квадратичных отклонений случайных величин довольно-таки важно при анализе группы случайных величин; оно помогает выбрать из множества случайных величин оптимальные по Парето, отбросив заведомо «плохие».

КАКАЯ ИНВЕСТИЦИОННАЯ ОПЕРАЦИЯ НАЗЫВАЕТСЯ ОПТИМАЛЬНОЙ ПО ПАРЕТО?

 

Пусть на финансовом рынке существует возможность осуществить несколько инвестиционных операций, ожидаемые эффективности и риски которых известны и равны, соответственно,  ME₁, ME₂, ..., ME_n и σ₁, σ₂, ..., σ_n.

Говорят, что i-я инвестиционная операция E_i  доминирует j-ю инвестиционную операцию E_j, если выполняются следующие условия.

 

Или

 

(A): ME_i ≥ME_j, σ_i<σ_j ;

 

или

 

(Б): ME_i>ME_j,  σ_i ≤σ_j .

 

Инвестиционная операция E*_i называется оптимальной по Парето, если не существует инвестиционных операций, которые бы ее доминировали.

ЧТО ТАКОЕ МНОЖЕСТВО ПАРЕТО (ОБЛАСТЬ КОМПРОМИССОВ)?

 

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

так называемое «переговорное» множество эффективных решений (оптимальных по Парето).

 

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

 

ПРИМЕР 2 (ПРОДОЛЖЕНИЕ). Инвестор рассматривает четыре инвестиционные операции со случайными эффективностями, описываемыми случайными величинами E₁, E₂, E₃, E₄ со следующими  рядами распределений.

E1	2	5	8	4
p	1/6	1/2	1/6	1/6

 

E2	2	3	4	12
p	1/2	1/6	1/6	1/6

 

E3	3	5	8	10
p	1/6	1/6	1/2	1/6

 

E4	1	2	4	8
p	1/2	1/6	1/6	1/6

 

Требуется определить, какие из этих операций оптимальны по Парето.

РЕШЕНИЕ. Ожидаемые эффективности и риски равны, соответственно:

 

ME₁=4,81, σ₁=1,77; ME₂=4,16, σ₂=3,57; ME₃=7,00, σ₃=2,30; ME₄=2,81, σ₄=2,54.

 

Построим на плоскости OXY точки с координатами (x,y)=(MEi;σi), i=1,2,3,4 (рисунок 3). Тогда i-я операция E_i  доминирует j-ю операцию E_j, если точка, соответствующая i-й операции, находится на плоскости OXY правее и ниже точки, соответствующей j-й операции. Видно, что первая операция доминирует вторую и четвертую; третья операция также доминирует вторую и четвертую. При этом первая операция не доминирует третью, а третья не доминирует первую. Первая и третья операции, таким образом, оптимальны по Парето.

 

Рисунок 3. График «риск — доходность».

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

 

ПРИМЕР 3.

 

Например, если перед нами стоит выбор из двух операций:

- потерять 1 руб.;

- с вероятностью 0,5 получить один миллион рублей и с вероятностью 0,5 потерять 100000 руб.,

то обе эти операции окажутся оптимальными по Парето, так как ME₁=–1, σ₁=0, ME₂=450000, σ₂=550000). Но, скорее всего, мы склонимся к выбору первой операции, несмотря на то, что ожидаемый доход по ней составляет отрицательное число (–1 руб.), тогда как ожидаемый доход от исполнения второй операции составляет 450000 руб., но при этом слишком велик риск у второй операции, слишком велика вероятность больших потерь.

Рассмотренный подход может быть применен при анализе любых других задач многокритериальной оптимизации.

 

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

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

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

 

ЗАМЕЧАНИЕ.

 

Отметим, что, вообще говоря, переменные вектора решений X могут быть и функциями (скажем, времени), и более сложными объектами;  то же самое относится и к критериям.

 

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

 

Например, в некоторых случаях считают, что увеличение значения j-го частного критерия Zj (при неизменных других частных критериях) делает решение более предпочтительным для ЛПР. В этом случае соответствующую функцию

 

Zj=Zj(X), "XÎQ,

 

иногда называют целевой функцией.

 

Иногда в исследовании для целевой функции назначают некоторый уровень γ⁰_j, который должен достигаться на основе принимаемого решения. Этот уровень γ⁰_j часто называют целью, а ограничение  

 

Zj(X)≥γ⁰j, "XÎQ,

 

– критериальным  ограничением.

 

 

Отметим, что частные критерии Zj могут быть:

 

- количественными, т. е. функции Zi принимают числовые значения Zi(X);

 

- качественными, то есть функции Zi могут принимать  значения Zi(X) типа:  «да» и «нет»; «много» и «мало»; «отлично», «хорошо», «удовлетворительно» и «неудовлетворительно», и т. д.

 

 

Некоторые частные критерии Z_i, i=1, …, m, могут противоречить друг другу, другие действуют в одном направлении, третьи — индифферентны, безразличны друг к другу. Поэтому процесс решения многокритериальных задач неизбежно связан с экспертными оценками, как самих критериев, так и взаимоотношений между ними.

 

КАКИЕ СУЩЕСТВУЮТ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ?

 

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

 

1. СУБОПТИМИЗАЦИЯ. Выбор конкретного решения из переговорного множества (по-другому называемого множество допустимых решений, оптимальных по Парето) предоставляется человеку – лицу, принимающему решение (и несущему за него ответственность). В некоторых ситуациях пользуются специальными приемами, сужающими множество Парето (в идеале — до одного решения). Например, производят оптимизацию одного, признанного наиболее важным, критерия; остальные критерии при этом играют роль дополнительных ограничений.

 

Субоптимизация состоит в том, что выделяется один максимизируемый критерий (например, с номером k), а для остальных критериев (с номерами j≠k) задаются нижние границы γ_j.  Таким образом, получают следующую задачу оптимизации.

Z_k(X) → max,

Z_j(X)≥γ_j, j=1, …, k-1, k+1, …, m;

где X принадлежит множеству допустимых решений Q.

 

 

2. Упорядочение заданного множества критериев и последовательная оптимизация по каждому из них. Этот подход иллюстрируется применением метода последовательных уступок.

 

3. ЛЕКСИКОГРАФИЧЕСКАЯ ОПТИМИЗАЦИЯ. В ряде ситуаций при использовании методов  многокритериальной оптимизации исходят из относительной важности, или значимости, каждого критерия оптимальности, при этом наиболее часто пользуются введением весовых коэффициентов. Весовые коэффициенты определяют обычно с помощью методов экспертных оценок с непосредственным назначением коэффициентов веса. Таким образом, более важный критерий получает более высокий вес. Лексикографическая оптимизация предполагает, что частные критерии Zi, i=1, …, m, упорядочены по относительной важности. На первом шаге из множества Парето выделяются решения, имеющие максимальную оценку по важнейшему критерию, и если такое решение единственно, оно считается оптимальным. Если же таких решений не одно, то среди них отбирают те, которые имеют максимальную оценку по следующему критерию, и т. д.

 

4. МЕТОД ОБОБЩЕННОГО КРИТЕРИЯ. Можно провести поиск решения при многокритериальной оптимизации (между оптимизируемыми критериями и формированием специальной целевой функции) с отысканием компромиссной целевой функции по методу обобщенного критерия. Обычный подход заключается в стремлении «свернуть» частные критерии в один обобщенный скалярный критерий, оптимизация которого приводит к оптимальному решению задачи в целом. Формулировка подходящего обобщенного критерия в зависимости от конкретных условий как раз и является основным вопросом, который изучается в многокритериальной оптимизации.

 

ЧТО ТАКОЕ СВЕРТКА КРИТЕРИЕВ?

Метод обобщенного критерия предлагает перейти от m частных критериев Zi, i=1, …, m,  к так называемой свертке критериев:

             m

W(X) = ∑ α_i∙Z_i(X) → max,

             i=1

где X принадлежит множеству допустимых решений Q, а веса α_i определяют важность критериев.

 

ПРИМЕР 4. Пусть требуется из четырех вариантов системы,  характеризуемой параметрами: производительностью П (шт./мин) и  стоимостью С (тыс. руб.), приведенными в таблице 1, выбрать наилучший вариант (с наибольшей производительностью и наименьшей стоимостью) по обобщенному критерию, характеризующему обобщенные свойства каждого варианта системы.

 

Таблица 1.

Параметры системы	Варианты системы
	1	2	3	4
П (шт./мин.)	20	30	50	60
C (тыс. руб.)	100	400	200	500

 

 

РЕШЕНИЕ.  Выбранный обобщенный критерий W должен обеспечивать  операции с критериями различной размерности, включая нормирование по некоторому заданному значению и учет относительной важности каждого критерия с помощью коэффициентов веса. Улучшение  желательных параметров должно увеличивать значение критерия, а рост нежелательных параметров — снижать его значение. Тогда для данной задачи мы имеем два частных критерия оптимальности:

 

Z₁=П/П_N, Z₂=(-C/C_N),

 

Z₁(i)→ max, Z₂(i)→ max,

 

где П_N, С_N – нормирующие значения производительности П и стоимости С системы.

 

Построим свертку критериев:

 

W=α₁∙Z₁+ α₂∙Z₂,

 

где α₁, α₂ – коэффициенты веса.

 

Заметим, что в данной задаче множество допустимых решений конечно Q={1, 2, 3, 4} (Q состоит из 4-х возможных вариантов системы).  Тогда имеем:

 

W(i)= α₁∙[П(i)/П_N]+ α₂∙(-[C(i)/C_N]), i=1,2,3,4.         (*)

 

 

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

В формуле (*), используя данные таблицы 1, в качестве нормирующих значений принимаем:

 

П_N=П_max= 60; С_N=C_max = 500.

 

При этом формула для свертки критериев W приобретает вид:

 

W(i)= α₁∙[П(i)/60]+ α₂∙(-[C(i)/500]), i=1,2,3,4.        

 

Теперь оценим коэффициентами веса относительную важность  частных критериев Z₁ и Z₂. А, именно, определим значения критерия W, для трех основных ситуаций, при которых:

 

(а) важна лишь производительность системы: α₁=1, α₂=0;

 

(б) производительность и стоимость системы одинаково важны: α₁=0,5, α₂=0,5;

 

(в) важна лишь стоимость системы: α₁=0, α₂=1.

 

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

 

Таблица 2.

Ситуации	Весовые коэффициенты		Варианты системы
	α1	α2	1	2	3	4
(а)	1	0	0,33	0,5	0,83	1,0
(б)	0,5	0,5	0,67	-0,15	0,22	0
(в)	0	1	-0,2	-0,8	-0,4	-1,0

 

 

Для каждой из ситуаций можно выписать матрицы решений по обобщенному критерию W. Матрицы решений – векторы-столбцы D_(а), D_(б), D_(в), для каждой из ситуаций имеют следующий вид.

 

D_(а) =     

0,33

0,5

0,83

1,0

 

D_(б) =

0,67

-0,15

0,22

0

 

D_(в) =

-0,2

-0,8

-0,4

-1,0

 

 

Для ситуации (а) лучшим оказывается вариант 4, для ситуации (б) — вариант 1, для  ситуации (в) — вариант 1 (вариант 2 в каждой из трех рассмотренных  ситуаций будет худшим).

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

 

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

 

ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ С БЕСКОНЕЧНЫМ МНОЖЕСТВОМ ДОПУСТИМЫХ РЕШЕНИЙ.

КАК КЛАССИФИЦИРУЮТСЯ МЕТОДЫ АНАЛИЗА МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ С БЕСКОНЕЧНЫМ МНОЖЕСТВОМ ДОПУСТИМЫХ РЕШЕНИЙ?

 

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

 

- методы, направленные на построение единственного решения, и

 

- методы, направленные на  построение эффективного множества (множества Парето).

 

Таблица 3.

Методы анализа многокритериальных задач с бесконечным множеством допустимых решений
Методы построения единственного решения			Методы построения эффективного множества
Без участия ЛПР	Диалоговые процедуры выбора решения	Выявление предпочтений ЛПР до анализа задачи	Построение эффективных точек	Построение обобщенного множества достижимости

 

 

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

 

Таблица 4.

Диалоговые процедуры выбора решения
Методы взвешивания критериев	Методы критериальных ограничений	Методы целевой точки

 

 

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

 

На рисунке 4 представлена общая классификация методов анализа задачи (1), (2) с бесконечным множеством допустимых решений Q.

 

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

 

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

ОСНОВНЫЕ ПОНЯТИЯ. МНОЖЕСТВО (ГРАНИЦА) ПАРЕТО.

 

ЧТО ТАКОЕ ГРАНИЦА МНОЖЕСТВА?

 

Рассмотрим на координатной плоскости OUV множество Ω (рисунок 5). Каждая точка M, принадлежащая множеству Ω,  обладает одним из следующих свойств:

 

- либо все точки, ближайшие к точке M, принадлежат множеству Ω (то есть некоторая окрестность точки M принадлежит множеству Ω; такая точка M называется внутренней точкой множества Ω),

 

- либо сколь угодно близко от точки M  расположены как точки множества Ω, так и точки, множеству Ω не принадлежащие (то есть в любой окрестности точки M найдется точка, не принадлежащая множеству Ω, и найдется точка, принадлежащая множеству Ω; такая точка M называется граничной точкой множества Ω).

 

Граничная точка может, как принадлежать, так и не принадлежать множеству Ω. Множество всех граничных точек множества Ω обозначим через ∂Ω. Множество ∂Ω называется границей множества Ω. 

 

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

 

 

Рисунок 5. Граница множества Ω.

Пусть М — произвольная точка множества Ω, внутренняя или граничная, и (U, V) – ее координаты. Поставим следующий вопрос: можно ли, оставаясь во множестве Ω, переместиться из точки М в близкую точку так, чтобы при этом увеличились обе ее координаты? Если М – внутренняя точка, то это, бесспорно, возможно. Если же М – граничная точка, то такое возможно не всегда.  Поясним это на следующем примере (рисунок  6).

 

ПРИМЕР 5.  Рассмотрим множество Ω, изображенное на рисунке 6. Из точек M₁, M₂ и М₃, которые принадлежат множеству Ω (M₁ – внутренняя точка множества Ω, M₂, M₃ – граничные точки множества Ω), можно переместиться, оставаясь во множестве Ω, так, чтобы увеличились обе координаты точек. Но уже из точек вертикального отрезка АВ можно переместиться, увеличивая лишь координату V (координата U при этом остается неизменной). Перемещая точку горизонтального отрезка PQ вправо, мы увеличиваем координату U (при этом координата V сохраняет свое значение). Что же касается дуги BQ, то перемещение вдоль нее способно лишь увеличить одну из координат при одновременном уменьшении другой.

Рисунок 6. Классификация точек множества Ω.

 

Тем самым точки множества Ω  можно разбить на следующие три класса.

 

1. К первому классу относятся точки, которые можно сдвинуть так, чтобы одновременно увеличились обе координаты и при этом точки остались в множестве Ω  (в этот класс попадают все внутренние точки множества Ω и часть его граничных точек);

 

2. Второй класс образуют точки, перемещением которых по множеству Ω можно увеличить только одну из координат при сохранении значения второй (вертикальный отрезок АВ и горизонтальный отрезок PQ на границе множества Ω;

 

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

 

Рисунок 7.  Граница (множество) Парето множества Ω.

 

ЧТО ТАКОЕ ГРАНИЦА ПАРЕТО?

 

Множество точек третьего класса называется границей (множеством) Парето данного множества Ω (выделено на рисунке 7).

 

Говоря нестрого, граница (множество ) Парето множества Ω  – это множество всех таких точек, принадлежащих множеству Ω, из которых нельзя сдвинуться на «север», «восток» либо «северо-восток», оставаясь в том же множестве Ω. На рисунке 8 указаны границы Парето некоторых множеств.

Рисунок 8. Примеры границ (множеств) Парето.

 

ЗАДАЧА МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ С БЕСКОНЕЧНЫМ МНОЖЕСТВОМ ДОПУСТИМЫХ РЕШЕНИЙ.

 

Пусть на плоскости OXY задано множество ω (рисунок  9),  и в каждой точке этого множества определены две непрерывные функции:

 

U=Φ(x,y), V=Ψ(x,y).

 

Рисунок 9. Множество ω на плоскости OXY.

 

Рассмотрим следующую задачу.

На множестве ω найти точку (x⁰, y⁰), в которой одновременно выполняются следующие равенства:

 

Φ(x⁰, y⁰) = Φ_max, Ψ(x⁰, y⁰)= Ψ_max.

 

Обычно это записывается так:

Φ(x,y)→ max, Ψ(x,y) → max,  (x,y) Î ω.

 

Сразу же отметим, что в общем случае поставленная задача решения не имеет.

В самом деле, изобразим на плоскости (OUV) все точки, координаты которых вычисляются по формулам: U=Φ(x,y), V=Ψ(x,y).  Обозначим полученное множество через Ω (рисунок 10).

 

Рисунок 10. Множество Ω.

 

Из рисунка 10 видно, что наибольшее значение U (т.е. U_max) и наибольшее значение V (т.е. V_max) достигаются в разных точках, а точка с координатами (U_max, V_max) лежит вне множества Ω. Тем самым в исходной постановке задача, вообще говоря, неразрешима – удовлетворить обоим требованиями одновременно невозможно. И, следовательно, нужно искать какое-то компромиссное решение.

Среди известных методов решения данной задачи отметим следующие.

(1) МЕТОД  ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК;

 

(2) МЕТОД ИДЕАЛЬНОЙ ТОЧКИ.

 

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

В ЧЕМ ЗАКЛЮЧАЕТСЯ МЕТОД ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК?

 

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

РАЗДЕЛ 3. МЕТОД ИДЕАЛЬНОЙ ТОЧКИ.

В ЧЕМ СОСТОИТ МЕТОД  ИДЕАЛЬНОЙ  ТОЧКИ?

 

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

В этом разделе лекции мы подробно рассмотрим метод идеальной точки на следующем конкретном примере.

 

Пусть на множестве ω плоскости (OXY) определяемом системой неравенств:

 

0≤x≤4;

0≤y≤2;

 

x+2y≤6;

 

заданы две линейные функции:

U(x,y)=x+y+2;

 

V(x,y)=x–y+6.

 

Требуется найти решение задачи

U=Φ(x,y)→ max, V=Ψ(x,y) → max,  (x,y) Î ω.

 

 

Множество ω представляет собой пятиугольник (рисунок  11) ABCDE, вершины которого имеют следующие координаты: A(0,0), B(0,2), C(2,2), D(4,1), E(4,0).

 

Рисунок  11. Метод идеальной точки.

В силу линейности критериев U и V пятиугольник ABCDE на плоскости OXY переходит в пятиугольник A*B*C*D*E* (рисунок 12) на плоскости OUV, координаты вершин которого вычисляются по следующим формулам (3):

A*=(U(A),V(A))=(U(0,0), V(0,0))=(2,6);

 

B*=(U(B),V(B))=(U(0,2), V(0,2))=(4,4);

 

C*=(U(C),V(C))=(U(2,2), V(2,2))=(6,6);

 

D*=(U(D),V(D))=(U(4,1), V(4,1))=(7,9);

 

E*=(U(E),V(E))=(U(4,0), V(4,0))=(6,10).

 

Теперь находим границу Парето: это отрезок D*E*. Точка утопии М*(7,10) считается заданной (ее координаты равны, соответственно,  наибольшим значениям U и V). Из рисунка 12 ясно, что U_M*=U_D*=7,  V_M*=V_E*=10 в системе координат OUV.

 

Рисунок 12. Построение границы Парето множества Ω.

 

Требуется найти на множестве Парето точку, ближайшую к точке утопии М*. Из рисунка 12 видно, что искомая точка должна лежать на отрезке D*E*. Проведем через точки D* и Е* прямую (D* E*).  Найдем уравнение этой прямой (рисунок 13). Пусть  уравнение прямой (D* E*) в системе координат (OUV) имеет вид: 

 

α∙U+β∙V=γ.

 

Чтобы отыскать конкретные значения параметров α, β и γ, подставим в него координаты обеих точек – и D*, и Е*.

 

Рисунок 13. Прямая (D*E*).

 

Получим следующую систему уравнений.

 

(D*): α∙7+β∙9=γ,

 

(E*): α∙6+β∙10=γ.

 

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

α – β=0.

 

Отсюда, α=β.

Положим  α=β=1, тогда γ=16.

Следовательно,  искомое уравнение прямой (D*E*):

 

U+V=16.

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

Пусть M₁(U₁,V₁) и M₂(U₂,V₂) – две точки на плоскости (OUV). Для того чтобы найти расстояние между ними, достаточно вычислить длину гипотенузы построенного прямоугольного треугольника (рисунок 14).

Рисунок 14. Расстояние между двумя точками |M₁ M₂|.

 

Воспользовавшись теоремой Пифагора, получим для гипотенузы |M₁ M₂| построенного прямоугольного треугольника:

|M₁ M₂|² = (U₂ – U₁)²+(V₂ – V₁)².

 

По условию задачи нам нужно определить на прямой (D*E*), заданной уравнением

 

U + V= 16,

точку М⁰(U⁰, V⁰), расстояние которой от точки М*(7,10) минимально, то есть решить экстремальную задачу:

f(U,V)= (U – 7)²+(V– 10)²→min.

 

Так как U = 16 – V, то последнее соотношение можно переписать в виде:

f(U(V),V)≡F(V)=(9 –V)²+(V– 10)²→min.

 

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

 

F(V)=2V² – 38V+181  → min.

Это уравнение описывает параболу (рисунок 15) с вершиной (V⁰,F(V⁰)), где координата V⁰ находится из условия равенства нулю производной:  F`(V)= 4V – 38 =0. То есть V⁰=19/2, тогда F(V⁰)= 2(19/2)² – 38∙19/2+181=1/2.

 

 

Рисунок 15. Нахождение расстояния от точки утопии до идеальной точки.

 

Таким образом, идеальная точка М⁰(U⁰, V⁰) находится на расстоянии √F(V⁰)=1/√2 от точки утопии М*(7,10) (рисунок 16). Чтобы найти координату U⁰, рассмотрим уравнение прямой (D*E*), на которой лежит идеальная точка М⁰(U⁰, V⁰):

 

U+V=16.

 

Отсюда,  U⁰+V⁰=16.

 

Следовательно, U⁰+19/2=16, U⁰=16 – 19/2=13/2.

 

Таким образом, M⁰=(13/2; 19/2).

 

Рисунок 16. Нахождение идеальной точки.

 

Возвращаясь к системе координат OXY, заметим, что соответствующие значения x⁰ и y⁰ легко находятся из системы линейных уравнений:

 

 

U⁰=x⁰+y⁰ – 6,

 

V⁰=x⁰ – y⁰ +2. 

Здесь мы воспользовались равенствами:

 

U⁰=U(x⁰,y⁰),

 

V⁰=V(x⁰,y⁰).

 

Имеем:

 

13/2= x⁰+y⁰ + 6,

 

19/2= x⁰ – y⁰ +2.  

Складывая уравнения, получим:

 

16=2x⁰ + 8, то есть x⁰ =4.

 

Вычитая из первого уравнения второе уравнение, получим:

 

- 3=2y⁰ – 4, то есть y⁰=1/2.

 

Значит, идеальная точка на плоскости OXY имеет координаты: (4; 1/2).

 

 

ЗАМЕЧАНИЕ. Мы рассмотрели задачу, в которой

U=Φ(x,y)→ max, V=Ψ(x,y) → max,  (x,y) Î ω.

 

На практике часто встречаются случаи, когда требования выглядят по-иному:

так:

 

U=Φ(x,y)→ max, V=Ψ(x,y) → min,  (x,y) Î ω.

 

или даже так:

 

U=Φ(x,y)→ min, V=Ψ(x,y) → min,  (x,y) Î ω.

 

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

 

Θ= – Ψ 

 

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

Ψ(x,y) → min и Θ(x,y)→ max 

 

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

Φ(x,y)→ max, Ψ(x,y) → max. 

 

СПИСОК  РЕКОМЕНДУЕМОЙ  ЛИТЕРАТУРЫ.

[1] Таха Х.А. Введение в исследование операций. — 6-е изд. Пер. с англ. — М.: Издательский дом «Вильямс», 2001. — 912 с: ил.

 

[2] Фомин Г. П. Математические методы и модели в коммерческой деятельности: Учебник. — 2-е изд., перераб. и доп. — М.: Финансы и статистика, 2005. — 616 с: ил.

 [3] Шелобаев С. И. Математические методы и модели в экономике,  финансах, бизнесе: Учебное пособие для вузов. — М.: ЮНИТИ - ДАНА, 2001. - 367 с.

[4] Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учебное пособие. — 3-е изд. — М.: Дело, 2004. — 440 с. — (Серия «Классический университетский учебник»).

 

[5] Экономико-математические методы и прикладные модели: Учебное пособие для вузов/ В.В. Федосеев, А.Н. Гармаш,  Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. — М.:  ЮНИТИ, 1999. - 391 с.