Причины появления многокритериальности

↑

▷ Содержание

⇐ ПредыдущаяСтр 8 из 10Следующая ⇒

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

Определение. Многокритериальной задачей называется набор , где u – множество, а  (i =1,…, m) – функции.

Множество u интерпретируется как множество стратегий оперирующей стороны, а функции gⁱ – как ее критерии.

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

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

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

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

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

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

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

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

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

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

Определение. Многокритериальной задачей называется набор , где u – множество, а gⁱ – функции, отображающие u во множество действительных чисел .

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

Часто такую операцию строят, задавая функцию , и полагая, что . функцию f в таком случае называют функцией свертки (или просто сверткой) критериев.

Примеры сверток

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

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

Экономический способ свертки. свертка частных критериев g ¹,…, g^m представляет собой взвешенную сумму .

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

Пример. Предприятие выпускает m видов продукции. критерии g ¹,…, g^m выражают количества продукции каждого из видов, выпущенных предприятием. доходы предприятия от реализации продукции выражаются сверткой . коэффициенты свертки в этом случае имеют смысл цен.

Пример. Рассмотрим деятельность фирмы за m лет. критерии g ¹,…, g^m выражают прибыль фирмы в соответствующие годы. свертка  оценивает суммарную прибыль за весь период. числа l₁,…l _m в этом случае имеют смысл коэффициентов дисконтирования.

Пример. В классической биатлонной гонке имеется два критерия: количество промахов g ¹ и время прохождения дистанции g ². Результат спортсмена оценивается по линейной свертке  (если время измерять в секундах).

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

Пример. Знания студента на экзамене оценивается количественным критерием g, принимающим значения от двух до пяти. Качественная цель сдать экзамен описывается критерием

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

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

Лексикографическая свертка. Пусть даны критерии g ¹,…, g^m, ранжированные в порядке возрастания номеров. Сначала находятся все точки максимума критерия g ¹, из них выбираются те, которые доставляют максимум критерию g ² и так далее. Наконец, из уже отобранных, выбираются те, которые доставляют максимум критерию g^m. Выбранные на последнем этапе стратегии называются точками лексикографического максимума.

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

Дизъюнкция. Пусть есть m качественных критериев g ¹,…, g^m. цель, состоящая в достижении, по крайней мере, одной из частных целей описывается критерием .

Конъюнкция. Пусть есть m качественных критериев g ¹,…, g^m. Цель, состоящая в достижении, сразу всех частных целей описывается критерием .

Пример. Если за сессию студенту предстоит сдать m экзаменов и каждый из критериев g ¹,…, g^m описывает сдачу одного из них, то цель, состоящая в успешной сдаче сессии, описывается критерием .

Отрицание. Пусть имеется качественный критерий g. критерий 1– g описывает цель, состоящую в не достижении исходной.

Пример. Если исходная цель g состоит в том, чтобы избежать скандала, то цель, состоящая в попадании в скандальную хронику, описывается критерием 1– g.

Обобщенная дизъюнкция. Часто используется следующий способ свертки. Пусть есть m количественных критериев g ¹,…, g^m. результирующий критерий образуется по правилу .

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

Обобщенная конъюнкция. Это свертка, при которой количественные критерии g ¹,…, g^m заменяются общим критерием .

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

Пример. Пусть для производства изделия требуются комплектующие m видов и количества произведенных деталей описываются числами g ¹,…, g^m. критерий  описывает количество готовых изделий, которое из них можно собрать. Числа  имеют при этом смысл количества деталей i -го вида, необходимых для сборки одного готового изделия.

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

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

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

Принцип наименьшего сожаления. Это свертка, при которой количественные критерии g ¹,…, g^m заменяются общим критерием , который нужно минимизировать.

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

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

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

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

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

Теорема о свертке

Теорема. Пусть каждый из критериев g ¹,…, g^m принимает лишь два значения 0 и 1, а f:{0,1} ^m ®{0,1} – произвольная функция. тогда критерий g,определенный условием g (u) = f (g ¹(u),…, g^m (u)), может быть выражен через следующие элементарные операции:

1. конъюнкция: g ¹,…, g^m ® ;

2. дизъюнкция: g ¹,…, g^m ® ;

3. отрицание: gⁱ ® 1– gⁱ.

Доказательство. Пусть y =(y ₁,…, y_m) – произвольный булев вектор размерности m (здесь y_i равны 0 или 1 при любом i = 1,…, m). рассмотрим функцию f_y:{0,1} ^m ®{0,1}, определенную условием , где z_i = x_i, если y_i =1, и z_i =1– x_i, если y_i =0. непосредственно проверяется, что f_y (y)=1, и f_y (x)=0 для любого x ¹ y.

Пример. На референдуме о сохранении союза советских социалистических республик гражданам предлагалось ответить на четыре вопроса. Власти предлагали своим сторонникам ответить «да, да, нет, да». таким образом, есть, четыре вспомогательных качественных критерия gⁱ (ответ на i -ый вопрос). Если общая цель g состоит в лояльности власти, то она выражается через частные с помощью свертки g = g ¹ g ²(1– g ³) g ⁴.

Для заданной нам функции f, обозначим y ={ y: f (y)=1}. Покажем, что интересующий нас критерий g представляется в виде

.                                      (28)

В самом деле, если g (u)=1, то по определению вектор t =(g ¹(u),…, g^m (u)) принадлежит множеству y. значит, произведение в формуле (28) содержит множитель (1– f_y (g ¹(u),…, g^m (u))), равный нулю. следовательно, и все произведение равно нулю, а вся правая часть формулы (28) равна 1.

Если же g (u)=0, то вектор t =(g ¹(u),…, g^m (u)) не принадлежит множеству y, и для всех y Î y имеем f_y (g ¹(u),…, g^m (u))=0. значит, для этого u все сомножители в формуле (28) равны 1, а тогда и произведение в правой части равенства (28) равно 1, а сама правая часть равна нулю.

Для завершения доказательства остается заметить, что при построении функций f_y мы пользовались лишь операциями отрицания и конъюнкции, а в формуле (28) использовалась еще и дизъюнкция.

Замечание. Легко видеть, что сама операция дизъюнкции может быть выражена через конъюнкцию и отрицание, то есть список «элементарных» операций может быть сокращен.

Теорема. Пусть каждый из критериев g ¹,…, g^m принимает лишь конечное число значений, а  – произвольная функция. Тогда критерий g,определенный условием g (u) = f (g ¹(u),…, g^m (u)), может быть выражен через следующие элементарные операции:

1. экономическая свертка: g ¹,…, g^m ® ;

2. разбиение на удовлетворительные и неудовлетворительные: gⁱ ®

3. конъюнкция: g ¹,…, g^m ® ;

4. дизъюнкция: g ¹,…, g^m ® ;

5. отрицание: gⁱ ® 1– gⁱ.

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

1. для каждого i = 1,…, m и каждого  с помощью элементарной операции второго типа образуем вспомогательный критерий . разумеется, критерий  может быть выражен как функция критерия gⁱ.

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

                                          (29)

где положено =0.

в самом деле, если , то для всех j > l справедливо равенство , а для всех j ≤ l будем иметь . поэтому для такого u правая часть равенства (29) может быть переписана в виде . эта сумма, очевидно, равна , то есть равенство (29) справедливо.

3. рассмотрим вспомогательные критерии g _g(u), определенные условиями

(здесь ). Каждый из этих критериев является функцией критерия g.

4. тогда по условию теоремы, тогда критерий  может быть представлен, как функция критериев g ¹,…, g^m. значит, он может быть представлен и как функция вспомогательных критериев .

5. но каждый из критериев g _g и  принимает лишь значения 0 и 1, поэтому в силу предыдущей теоремы, каждый из критериев g _g может быть выражен через критерии  с использованием лишь элементарных операций конъюнкции, дизъюнкции и отрицания.

6. аналогично формуле (29) доказывается равенство

 где g₀=0.

Для завершения доказательства остается заметить, что критерии  мы получили, пользуясь только сверткой типа 2, на шаге 4 для получения критериев g _g использовались свертки типов 3,4,5, и, наконец, на шаге 6 использовалась свертка типа 1. теорема доказана.

Примеры

Пример. Пусть каждый из критериев g ¹,…, g^m принимает лишь конечное число значений. Значения, которые может принимать критерий gⁱ, обозначим в порядке возрастания символами . опишем, как с помощью элементарных операций получить свертку .

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

используя разбиение на удовлетворительные и неудовлетворительные. Тогда .

Пример. Пусть каждый из критериев g ¹,…, g^m принимает лишь конечное число значений. значения, которые может принимать критерий gⁱ, обозначим в порядке возрастания символами . опишем, как с помощью элементарных операций получить свертку .

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

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

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

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

ОПТИМАЛЬНОСТЬ ПО ПАРЕТО

Вильфредо Парето (1848–1923) – итальянский экономист.

Определение. Будем говорить, что стратегия u Î u доминирует (по Парето) стратегию v Î u, а соответствующий вектор выигрышей (g ¹(u),…, g^m (u)) доминирует вектор (g ¹(v),…, g^m (v)), если для всех i = 1,…, m выполняются неравенства gⁱ (u)³ gⁱ (v), а для некоторого k выполняется строгое неравенство g^k (u)> g^k (v).

Определение. Стратегия u Î u, и соответствующий вектор выигрышей (g ¹(u),…, g^m (u)) называются эффективными (оптимальными по Парето), если не существует стратегии v Î u, которая доминировала бы стратегию u.

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

Множество эффективных векторов выигрышей, вообще говоря, не выпукло.

Пример. Пусть , g ¹(u)= u ₁, g ²(u)= u ₂. Множество эффективных векторов в этой задаче представляет собой четверть окружности  и, следовательно, не выпукло.

Множество эффективных векторов может быть и не замкнутым.

Пример. Пусть ,  

Эффективное множество в этой задаче состоит из двух дуг и одной точки . это множество не замкнуто, поскольку точки (3,1/3) и (1/3,3) являются предельными для него, но не доминируются точкой (3,3).

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

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

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

Определение. Стратегия u Î u, и соответствующий вектор выигрышей (g ¹(u),…, g^m (u)) называются слабо эффективными, если не существует стратегии v Î u, которая сильно доминировала бы стратегию u.

Лемма. Пусть множество u компактно, а функции  непрерывны. Тогда множество слабо эффективных стратегий компактно.

Доказательство. Пусть точка v не является слабо эффективной. Тогда найдется такая точка u, что выполняются неравенства  в силу непрерывности функций gⁱ найдется настолько малая окрестность o точки v, что неравенства  будут выполняться для любой точки w из O, то есть множество точек, которые не являются слабо эффективными, является открытым.

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

Пусть множество u компактно, а функции  непрерывны. Определим по индукции множества . Положим

  .

Лемма. Всякая точка из множества u_m является эффективной.

Доказательство. Допустим противное. Пусть точка v Î u доминирует точку u. тогда найдется такой номер k, что  для i =1,…, k –1, и g^k (u)< g^k (v). Так как точка u Î u ₁, выполняется неравенство g ¹(u)³ g ¹(v), то есть на самом деле g ¹(u)= g ¹(v) и, следовательно, v Î u ₁. Но тогда в силу включения u Î u ₂, имеем g ²(u)³ g ²(v). Продолжая эти рассуждения, получим v Î u_k. но тогда справедливо неравенство g^k (u)³ g^k (v), которое противоречит условию g^k (u)< g^k (v). Полученное противоречие доказывает лемму.

Следствие. Пусть множество u компактно, а функции непрерывны. Тогда множество эффективных точек не пусто.

Доказательство. В силу теоремы Вейерштрасса, непрерывная функция g ¹ достигает своего максимума на компактном множестве u ₀, то есть множество u ₁ не пусто. Множество u ₁ замкнуто, так как является прообразом компактного множества (точки действительно прямой) при непрерывном отображении g ¹. Замкнутое множество u ₁ является подмножеством компактного множества u ₀. поэтому u ₁ компактно.

По аналогичным соображениям множество u ₂ не пусто и компактно. продолжая те же рассуждения, приходим к выводу, что множество u_m не пусто. Любая его точка эффективна, что и доказывает следствие.

ПОИСК ЭФФЕКТИВНЫХ ТОЧЕК

Пусть u – компактное множество, а g ¹,…, g^m – непрерывные функции, .

Теорема (Гермейер). Пусть u ₀ – эффективная точка, причем gⁱ (u ₀)>0 для всех i = 1,…, m. Тогда существуют положительные числа l₁,…l _m такие, что  и x ₀ является точкой максимума функции .

Доказательство. Положим  Тогда  Пусть u – любая точка. Так как точка u ₀ – эффективна, найдется номер i, для которого gⁱ (u)£ gⁱ (u ₀), или, что то же самое, m _i gⁱ (u)£1. значит,  а это означает, что u ₀ – одна из точек максимума функции .

Остается положить  и заметить, что тогда u ₀ – одна из точек максимума функции f (u). Теорема доказана.

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

Пример.Пусть u ={(u ₁, u ₂): 0£ u ₁£1, 0£ u ₂£1}, g ¹(u)= u ₁, g ²(u)= u ₂. при  точки максимума функции  образуют отрезок {(u ₁, u ₂): u ₁=1, 0.5£ u ₂£1}, но только одна его точка (1,1) является эффективной.

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

Доказательство. Допустим противное. Тогда найдется такая точка u ₁, что  для всех i =1,…, m. но тогда  что противоречит условию.

Пусть теперь множество u выпукло, а функции g ¹,…, g^m вогнуты.

Теорема (Карлин).Пусть x ₀ – эффективная точка. Тогда существуют неотрицательные числа p ₁,…, p _m такие, что  и x ₀ является точкой максимума функции .

Доказательство. Не ограничивая общности, можем считать, что gⁱ (u)>0 для всех i = 1,…, m. В силу теоремы Гермейера существуют положительные числа  для которых u ₀ реализует максимум функции .

Тогда (u ₀, f (u ₀)) является решением задачи математического программирования

,

В силу теоремы Куна–Такера найдутся такие неотрицательные числа a _i, i = 1,…, m, для которых (u ₀, f (u ₀)) будет точкой максимума функции

на множестве , но это возможно, только если

,                                                  (30)

а тогда u ₀ является точкой максимума функции .

Остается заметить, что в силу равенства (30), по крайней мере, одно a _i не равно нулю. Тогда мы можем положить .

Теорема. Пусть существуют положительные числа p ₁,…, p _m такие, что  и u ₀ является точкой максимума функции . тогда точка u ₀ является эффективной.

Доказательство. Допустим противное. Тогда найдется такая точка u ₁, что gⁱ (u ₁)³ gⁱ (u ₀) для всех i =1,…, m, причем, по крайней мере, одно из этих неравенств не обращается в равенство. Умножая эти неравенства на p_i и суммируя, получим неравенство F(u ₁)>F(u ₀), что противоречит условию.

Нельзя утверждать, что всякая эффективная точка может быть найдена в результате максимизации функции  с положительными коэффициентами p ₁,…, p _m.

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

С другой стороны, при неотрицательных коэффициентах p ₁,…, p_m, точка максимума функции  может быть неэффективной в многокритериальной задаче.

Пример. Пусть  Точки максимума функции F(u)=1× g ¹(u)+0× g ²(u) образуют отрезок {(u ₁, u ₂): u ₁=1, 0£ u ₂£1}, а эффективной является только одна точка (1,1) этого отрезка.

Теорема. Пусть существуют неотрицательные числа p ₁,…, p _m такие, что  и u ₀ является точкой максимума функции . тогда точка u ₀ является слабо эффективной.

Доказательство. Допустим противное. тогда найдется такая точка u ₁, что  для всех i =1,…, m. Умножая эти неравенства на p_i и суммируя, получим неравенство  что противоречит условию.

Примеры

Пример. Пусть множество u представляет собой стандартный симплекс u ={(u ₁, u ₂, u ₃): u ₁³0, u ₂³0, u ₃³0, u ₁+ u ₂+ u ₃=1} и имеется два критерия g ¹(u)=2 u ₁+7 u ₂+ u ₃ и g ²(u)=3 u ₁+ u ₂+4 u ₃.

Найдем точки максимума функции F(u)= pg ¹(u)+(1– p) g ²(u). Так как критерии в данной задаче линейны, а максимум линейной функции непременно достигается в одной из вершин, то . Нарисовав графики, нетрудно понять, что при 0£ p £1/3 максимум достигается в вершине (0,1,0), а при 1/3£ p £1 он достигается в вершине (0,0,1). При p =1/3 точки максимума заполняют все ребро, соединяющие эти вершины. Таким образом, все точки этого ребра являются эффективными.

Пример. Пусть множество u представляет собой стандартный симплекс u ={(u ₁, u ₂, u ₃): u ₁³0, u ₂³0, u ₃³0, u ₁+ u ₂+ u ₃=1} и имеется два критерия g ¹(u)=3 u ₁+7 u ₂+ u ₃ и g ²(u)=4 u ₁+ u ₂+4 u ₃.

Анализ показывает, что в данном случае эффективными являются все точки, лежащие на двух ребрах: соединяющем вершину (1,0,0) с вершиной (0,1,0) и соединяющем вершины (1,0,0) и (0,0,1). В этом случае множество эффективных точек не выпукло.

В двух предыдущих примерах полезно нарисова

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Познавательные статьи:



Техника нижней прямой подачи мяча

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

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов