Многокритериальные задачи

29.09.09 Многокритериальные задачи Если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколько-нибудь развязности, какая у Балтазара Балтазарыча, да, пожалуй, прибавить к этому еще дородности Ивана Павловича – я бы тогда тотчас же решилась. Н. В. Гоголь Причины появления многокритериальности Как отмечалось выше, всякая модель операции должна иметь единственный критерий. К сожалению, выбор такого критерия часто представляет значительную трудность. Поэтому приходится работать с не до конца формализованными моделями, в которых фигурируют несколько показателей, уменьшение или увеличение которых желательно для оперирующей стороны. В таких случаях говорят об исследовании многокритериальных задач. Определение. Многокритериальной задачей называется набор , где U – множество, а (i=1,…,m) – функции. Множество U интерпретируется как множество стратегий оперирующей стороны, а функции gi – как ее критерии. Пример такого рода дает известный лозунг советских времен: «Получить максимум продукции при минимуме затрат». Если подходить к этой ситуации формально, легко придти к бессмысленности: свести затраты к нулю нетрудно, но при этом и выпуск продукции будет нулевым. Тем не менее, оба показателя, и выпуск продукции, и размер затрат верно отражают стремления оперирующей стороны. • Фон Нейман–Моргенштерн, стр. 37 При формализации многокритериальных задач в теории исследования операций выделены некоторые часто использующиеся приемы. О них и пойдет речь ниже. Но подчеркнем, что выбор такого приема каждый раз должен определяться из содержательного анализа моделируемой операции, тем более, что приведенные ниже примеры далеко не исчерпывают всех возможностей. Причины появления многокритериальности могут быть различными. Например, оперирующая сторона может представлять собой группу лиц, каждое из которых имеет, вообще говоря, свои цели. Часто многокритериальность появляется при рассмотрении динамических процессов. Например, если коммерческая фирма стремится к увеличению прибыли, и ее функционирование рассматривается на достаточно длинном временном интервале, то возникает целый ряд показателей, характеризующих прибыль в каждый из моментов времени. Иногда удобно чисто формально рассматривать как многокритериальную задачу обычную модель операции, в которой имеется неопределенный фактор, рассматривая в качестве частных критериев значения общего критерия операции при конкретных значениях неопределенных факторов. В ряде случаев задачу с неопределенными факторами преобразуют в двухкритериальную модель, формулируя задачу минимум и задачу максимум. Очень часто приходится сталкиваться с ситуацией, когда оперирующая сторона просто не может сформулировать свои предпочтения на вербальном уровне, как в приведенном выше примере. ▪ Пример: диверсификация заявки на аукцион Иногда происходит путаница, и в качестве критерия задаются ограничения, которые должны соблюдаться в данной задаче. Так, например, формулируя задачу на создание межпланетного космического корабля, С.П. Королев писал, что Марс должен быть достигнут а) за минимальное время и б) с минимальной затратой средств. Понятно, что если речь идет о пилотируемом полете, то его длительность должна быть не слишком большой (ограничение!). Но вряд ли кто то станет стремиться к сокращению этого времени на несколько минут, или даже часов, за счет ухудшения других характеристик полета. Отметим, что критерий в любой модели операции должен выражаться через управления оперирующей стороны и, быть может неопределенные факторы. Например, стремление выйти замуж за миллионера может быть лишь благим пожеланием, а не целью, если у оперирующей стороны нет реальных возможностей встретить хотя бы одного миллионера. Точно так же лозунг «Наша цель – коммунизм» нельзя рассматривать как формулировку цели операции, поскольку совершенно не ясно, например, ведет ли к достижению этой цели выращивание кукурузы в приполярных районах, или нет. Данные соображения приводят к следующим определениям. Определение. Многокритериальной задачей называется набор , где U – множество, а gi – функции, отображающие U в множество действительных чисел . Целью данной лекции будет рассмотрение способов построения на основе многокритериальной задачи модели операции вида . Часто такую операцию строят, задавая функцию , и полагая, что . Функцию F в таком случае называют функцией свертки (или просто сверткой) критериев. Примеры сверток Три звезды мне даны, сердцу сказаны, И без каждой на небе изъян, А в судьбе моей звезды те названы: Дело жизни, любовь и друзья. Ю. Визбор По техническим причинам удобно разделить цели операций на два класса: количественные и качественные. К первым относятся те, которые могут быть либо достигнуты, либо нет. Ко вторым – те, степень достижения которых может быть выражена числом. Разумеется, качественная цель может быть описана количественным критерием, который, например, принимает значение 1, если цель достигнута, и значение 0 в противном случае. Экономический способ свертки. Свертка частных критериев g1,…,gm представляет собой взвешенную сумму . В экономических моделях данный способ свертки часто используется при агрегировании абсолютно взаимозаменяемых продуктов. • «Слон больше серый, чем ушастый, потому, что ушастый он только местами, а серый – везде» Пример. Предприятие выпускает m видов продукции. Критерии g1,…,gm выражают количества продукции каждого из видов, выпущенных предприятием. Доходы предприятия от реализации продукции выражаются сверткой . Коэффициенты свертки в этом случае имеют смысл цен. Пример. Рассмотрим деятельность фирмы за m лет. Критерии g1,…,gm выражают прибыль фирмы в соответствующие годы. Свертка оценивает суммарную прибыль за весь период. Числа 1,…m в этом случае имеют смысл коэффициентов дисконтирования. Пример. В классической биатлонной гонке имеется два критерия: количество промахов g1 и время прохождения дистанции g2. Результат спортсмена оценивается по линейной свертке (если время измерять в секундах). Разбиение на удовлетворительные и неудовлетворительные. Пусть имеется количественный критерий g и число . Свертка задает качественный критерий Пример. Знания студента на экзамене оценивается количественным критерием g, принимающим значения от двух до пяти. Качественная цель сдать экзамен описывается критерием Пример. При выборе работы люди часто ориентируются на два критерия: размер заработной платы и удовлетворение от работы. Во многих случаях нет стремления к максимизации заработной платы, гораздо важнее, чтобы она обеспечивала некоторый приемлемый уровень жизни. Например, не секрет, что в предперестроечные годы уровень реальных доходов работников торговли заметно превышал аналогичный показатель у врачей, учителей и инженеров, однако, заметного перетока кадров в торговлю не наблюдалось. Когда в годы реформ уровень жизни бюджетников заметно упал, многие из них занялись розничной торговлей, чтобы обеспечить себе тот самый приемлемый уровень жизни. Пример. В одной из телевизионных программ 28.11.07 был сформулирован следующий тезис: «Женщина должна стремиться к тому, чтобы объем талии не превышал объема бедер». Здесь налицо замена двух количественных критериев (объем талии и объем бедер) одним качественным. Лексикографическая свертка. Пусть даны критерии g1,…,gm, ранжированные в порядке возрастания номеров. Сначала находятся все точки максимума критерия g1, из них выбираются те, которые доставляют максимум критерию g2 и так далее. Наконец, из уже отобранных, выбираются те, которые доставляют максимум критерию gm. Выбранные на последнем этапе стратегии называются точками лексикографического максимума. • С. Г. Слободяник.. Дискретные положительные гармонические функции. Математическое просвещение, сер.3. Вып.11. С. 145–148. Пример. При формировании структуры государственных расходов самыми важными являются расходы на государственных служащих, затем идут затраты на оборону, на содержание силовых структур, и так далее. В конце списка обычно оказываются сельское хозяйство и культура. Примерно так на практике формируется расходная часть государственного бюджета. Дизъюнкция. Пусть есть m качественных критериев g1,…,gm. Цель, состоящая в достижении, по крайней мере, одной из частных целей описывается критерием . Пример. Каждый правоверный мусульманин должен хотя бы раз в жизни совершить хадж. Если годы его жизни пронумерованы числами от 1 до m и критерии g1,…,gm описывают совершение хаджа в конкретном году, то их свертка описывает выполнения этого обязательства перед Богом. Конъюнкция. Пусть есть m качественных критериев g1,…,gm. Цель, состоящая в достижении, сразу всех частных целей описывается критерием . Пример. Если за сессию студенту предстоит сдать m экзаменов и каждый из критериев g1,…,gm описывает сдачу одного из них, то цель, состоящая в успешной сдаче сессии, описывается критерием . Отрицание. Пусть имеется качественный критерий g. Критерий 1–g описывает цель, состоящую в не достижении исходной. Пример. Если исходная цель g состоит в том, чтобы избежать скандала, то цель, состоящая в попадании в скандальную хронику, описывается критерием 1–g. Обобщенная дизъюнкция. Часто используется следующий способ свертки. Пусть есть m количественных критериев g1,…,gm. Результирующий критерий образуется по правилу . Пример. Пусть в шоссейной велогонке принимают участие m спортсменов из одной команды и критерии g1,…,gm задают места, занятые ее членами. Очень часто все члены команды работают на одного лидера, то есть критерий команды есть . Обобщенная конъюнкция. Это свертка, при которой количественные критерии g1,…,gm заменяются общим критерием . В экономических моделях такой способ свертки применяется при агрегировании абсолютно не взаимозаменяемых продуктов. Пример. Пусть для производства изделия требуются комплектующие m видов и количества произведенных деталей описываются числами g1,…,gm. Критерий описывает количество готовых изделий, которое из них можно собрать. Числа имеют при этом смысл количества деталей i-го вида, необходимых для сборки одного готового изделия. Пример. По понятным физическим причинам, скорость каравана судов определяется скоростью самого тихоходного судна. Это обстоятельство нашло свое отражение даже в морском уставе. Случайная свертка. В литературе встречается и такой способ свертки критериев. На множестве критериев задается вероятностная мера, и критерий операции выбирается случайным образом в соответствии с этой мерой. Понятно, что если при этом оперирующая сторона ориентируется на математическое ожидание, то получается способ свертки, формально совпадающий с экономическим. Приведенные выше примеры являются наиболее простыми, и потому наиболее часто встречающимися. Но, разумеется, бывают и более экзотические способы. Принцип наименьшего сожаления. Это свертка, при которой количественные критерии g1,…,gm заменяются общим критерием , который нужно минимизировать. Принцип принятия решений в ЕЭС. По новым законам решение принимается по правилу двойного большинства: решение считается принятым, если за него проголосовало 55% стран население которых составляет 65%. В этом случае можно считать, что имеется столько качественных критериев, сколько стран принимает участие в голосовании. Из них делается два количественных критерия, которые в свою очередь сворачиваются в один качественный. Старый способ судейства в фигурном катании. Каждый из девяти судей выставлял две оценки от 0 до 6.0 (с шагом 0.1). Затем все участники ранжировались в соответствии с суммой этих оценок (в случае равенства сумм выше ставился участник, у которого выше оценка за артистизм). Затем вычислялась сумма мест за выполнение данной программы (короткой или произвольной). Потом участники ранжировались в соответствии с взвешенной суммой показателей за короткую и произвольную программу, что и давало результирующее место участника. Способ судейства в прыжках в длину. Сравнение результатов двух участников производится по самому дальнему прыжку каждого из них. Если эти прыжки одинаковы, то во внимание принимается следующий по дальности и так далее. Лексимин. Во многих социальных моделях и в теоретической математике полезен следующий способ свертки. При сравнении двух решений многокритериальной задачи прежде всего сравниваются самые маленькие значения критериев (возможно, свои у каждого варианта). Если они одинаковы, то во внимание принимаются следующие по величине и так далее. Разумеется, не существует и не может существовать идеального способа свертки, пригодного на все случаи жизни. Если уж правилами предусмотрен такой способ подведения итогов, как в предыдущем примере, то в соответствующей модели надо пользоваться именно им. Но совсем глупо было бы использовать его в задаче о караване судов. Теорема о свертке Теорема. Пусть каждый из критериев g1,…,gm принимает лишь два значения 0 и 1, а F:{0,1}m{0,1} – произвольная функция. Тогда критерий g, определенный условием g(u)=F(g1(u),…,gm(u)), может быть выражен через следующие элементарные операции: 1. конъюнкция: g1,…,gm  ; 2. дизъюнкция: g1,…,gm  ; 3. отрицание: gi  1–gi. Доказательство. Пусть y=(y1,…,ym) – произвольный булев вектор размерности m (здесь yi равны 0 или 1 при любом i=1,…,m). Рассмотрим функцию Fy :{0,1}m{0,1}, определенную условием , где zi=xi, если yi=1, и zi=1–xi, если yi=0. Непосредственно проверяется, что Fy(y)=1, и Fy(x)=0 для любого xy. Пример. На референдуме о сохранении Союза советских социалистических республик гражданам предлагалось ответить на четыре вопроса. Власти предлагали своим сторонникам ответить «да,да,нет,да». Таким образом, есть, четыре вспомогательных качественных критерия gi (ответ на i-ый вопрос). Если общая цель g состоит в лояльности власти, то она выражается через частные с помощью свертки g=g1g2(1–g3)g4. Для заданной нам функции F, обозначим Y={y: F(y)=1}. Покажем, что интересующий нас критерий g представляется в виде . (*) В самом деле, если g(u)=1, то по определению вектор t=(g1(u),…,gm(u)) принадлежит множеству Y. Значит, произведение в формуле (*) содержит множитель (1–FY(g1(u),…,gm(u))), равный нулю. Следовательно, и все произведение равно нулю, а вся правая часть формулы (*) равна 1. Если же g(u)=0, то вектор t=(g1(u),…,gm(u)) не принадлежит множеству Y, и для всех yY имеем Fy(g1(u),…,gm(u))=0. Значит, для этого u все сомножители в формуле (*) равны 1, а тогда и произведение в правой части равенства (*) равно 1, а сама правая часть равна нулю. Для завершения доказательства остается заметить, что при построении функций Fy мы пользовались лишь операциями отрицания и конъюнкции, а в формуле (*) использовалась еще и дизъюнкция. Замечание. Легко видеть, что сама операция дизъюнкции может быть выражена через конъюнкцию и отрицание, то есть список «элементарных» операций может быть сокращен. Теорема. Пусть каждый из критериев g1,…,gm принимает лишь конечное число значений, а F: m – произвольная функция. Тогда критерий g, определенный условием g(u)=F(g1(u),…,gm(u)), может быть выражен через следующие элементарные операции: 1. экономическая свертка: g1,…,gm ; 2. разбиение на удовлетворительные и неудовлетворительные: gi  3. конъюнкция: g1,…,gm  ; 4. дизъюнкция: g1,…,gm  ; 5. отрицание: gi  1–gi. Доказательство. Значения, которые может принимать критерий gi, обозначим в порядке возрастания символами . При сформулированных условиях критерий g может тоже принимать лишь конечное число значений. Обозначим их в порядке возрастания символами . Дальнейшие рассуждения разобьем на шесть шагов. 1. Для каждого i=1,…,m и каждого с помощью элементарной операции второго типа образуем вспомогательный критерий . Разумеется, критерий может быть выражен как функция критерия gi. 2. Верно и обратное: критерий gi может быть представлен как функция критериев . Чтобы убедиться в этом, заметим, что (**) где положено =0. В самом деле, если , то для всех j>l справедливо равенство , а для всех j≤l будем иметь . Поэтому для такого u правая часть равенства (**) может быть переписана в виде . Эта сумма, очевидно, равна , то есть равенство (**) справедливо. 3. Рассмотрим вспомогательные критерии g(u), определенные условиями (здесь ). Каждый из этих критериев является функцией критерия g. 4. Тогда по условию теоремы, тогда критерий может быть представлен, как функция критериев g1,…,gm. Значит, в силу утверждения п. 2 он может быть представлен и как функция вспомогательных критериев . 5. Но каждый из критериев g и принимает лишь значения 0 и 1, поэтому в силу предыдущей теоремы, каждый из критериев g может быть выражен через критерии с использованием лишь элементарных операций конъюнкции, дизъюнкции и отрицания. 6. Аналогично формуле (**) доказывается равенство где 0=0. Для завершения доказательства остается заметить, что критерии мы получили, пользуясь только сверткой типа 2, на шаге 4 для получения критериев g использовались свертки типов 3,4,5, и, наконец, на шаге 6 использовалась свертка типа 1. Теорема доказана. ◦ Теорема 6.2.1 на стр. 155 у Партхасаратхи и Рагхавана – теорема о свертке – модели голосования. Теорема 9.4 у толстого Мулена на стр.326. ◦ Теорема о свертке – гомоморфизм булевых алгебр? ◦ При доказательстве теоремы о свертке перенести геометрию в пространство основного критерия. Примеры Пример. Пусть каждый из критериев g1,…,gm принимает лишь конечное число значений. Значения, которые может принимать критерий gi, обозначим в порядке возрастания символами . Опишем, как с помощью элементарных операций получить свертку . Очевидно, что результирующий критерий может принимать лишь конечное число значений вида . Обозначим их в порядке возрастания . Образуем вспомогательные критерии используя разбиение на удовлетворительные и неудовлетворительные. Тогда . Пример. Пусть каждый из критериев g1,…,gm принимает лишь конечное число значений. Значения, которые может принимать критерий gi, обозначим в порядке возрастания символами . Опишем, как с помощью элементарных операций получить свертку . Очевидно, что результирующий критерий может принимать лишь конечное число значений вида . Обозначим их в порядке возрастания . Образуем вспомогательные критерии используя разбиение на удовлетворительные и неудовлетворительные. Тогда .. Пример. Пусть каждый из критериев g1,…,gm принимает лишь конечное число значений. Значения, которые может принимать критерий gi, обозначим в порядке возрастания символами . Опишем, как с помощью элементарных операций получить свертку, описывающую нахождение лексикографического максимума. Пусть и . Обозначим и положим . Нужный нам критерий задается экономической сверткой . Оптимальность по Парето Вильфредо Парето (1848–1923) – итальянский экономист. Определение. Будем говорить, что стратегия uU доминирует (по Парето) стратегию vU, а соответствующий вектор выигрышей (g1(u),…,gm(u)) доминирует вектор (g1(v),…,gm(v)), если для всех i=1,…,m выполняются неравенства gi(u)gi(v), а для некоторого k выполняется строгое неравенство gk(u)>gk(v). Определение. Стратегия uU, и соответствующий вектор выигрышей (g1(u),…,gm(u)) называются эффективными (оптимальными по Парето), если не существует стратегии vU, которая доминировала бы стратегию u. Полезно иметь в виду следующую геометрическую интерпретацию данного определения. Вектор выигрышей (g1(v),…,gm(v)) является эффективным, если пересечение множества всех возможных векторов выигрышей и конуса состоит из одной точки (g1(v),…,gm(v)). Множество эффективных векторов выигрышей, вообще говоря, не выпукло. Пример. Пусть, g1(u)=u1, g2(u)=u2. Множество эффективных векторов в этой задаче представляет собой четверть окружности и, следовательно, не выпукло. Множество эффективных векторов может быть и не замкнутым. Пример. Пусть, g1(u)=u1, g2(u)=u2. Эффективное множество в этой задаче состоит из двух дуг и одной точки . Это множество не замкнуто, поскольку точки (3,1/3) и (1/3,3) являются предельными для него, но не доминируются точкой (3,3). Отсюда, следует, что не существует такой непрерывной функции , что множество точек максимума функции совпадает с множеством эффективных точек в многокритериальной задаче . В частности, функция , что множество точек максимума функции совпадает с множеством эффективных точек в многокритериальной задаче не может быть задана как композиция элементарных способов свертки, рассмотренных выше. Приведенные примеры показывают, что нетривиальной становится даже постановка задачи о поиске эффективных точек, коль скоро речь идет о задаче полного выбора, что часто бывает нужно на практике. В самом деле, в общем не ясно даже в каких терминах должен быть сформулирован ответ в этой задаче. По этой и некоторым другим причинам технически удобнее бывает работать со слабо эффективными точками, хотя они менее интересны в прикладном плане. Определение. Стратегия uU, и соответствующий вектор выигрышей (g1(u),…,gm(u)) называются слабо эффективными, если не существует стратегии vU, которая сильно доминировала бы стратегию u. Лемма. Пусть множество U компактно, а функции gi:U непрерывны. Тогда множество слабо эффективных стратегий компактно. Доказательство. Пусть точка v не является слабо эффективной. Тогда найдется такая точка u, что выполняются неравенства gi(v)0 для всех i=1,…,m. Тогда существуют положительные числа 1,…m такие, что и x0 является точкой максимума функции . Доказательство. Положим Тогда Пусть u – любая точка. Так как точка u0 – эффективна, найдется номер i, для которого gi(u)gi(u0), или, что то же самое, igi(u)1. Значит, а это означает, что u0 – одна из точек максимума функции . Остается положить и заметить, что тогда u0 – одна из точек максимума функции F(u). Теорема доказана. К сожалению, нельзя утверждать, что всякая точка максимума функции будет эффективной точкой многокритериальной задачи. Пример. Пусть U={(u1,u2): 0u11, 0u21}, g1(u)=u1, g2(u)=u2. При точки максимума функции образуют отрезок {(u1,u2): u1=1, 0.5u21}, но только одна его точка (1,1) является эффективной. Теорема. Пусть существуют такие положительные числа 1,…m , что и x0 является точкой максимума функции . Тогда точка x0 является слабо эффективной. Доказательство. Допустим противное. Тогда найдется такая точка u1, что gi(u1)>gi(u0) для всех i=1,…,m. Но тогда F(u1)>F(u0), что противоречит условию. Пусть теперь множество U выпукло, а функции g1,…,gm вогнуты. Теорема (Карлин). Пусть x0 – эффективная точка. Тогда существуют неотрицательные числа p1,…,p m такие, что и x0 является точкой максимума функции . Доказательство. Не ограничивая общности, можем считать, что gi(u)>0 для всех i=1,…,m. В силу теоремы Гермейера существуют положительные числа 1,…m для которых u0 реализует максимум функции . Тогда (u0,F(u0)) является решением задачи математического программирования , uU, w. В силу теоремы Куна–Такера найдутся такие неотрицательные числа i , i=1,…,m, для которых (u0,F(u0)) будет точкой максимума функции на множестве U. Но это возможно, только если , (*) а тогда u0 является точкой максимума функции . Остается заметить, что в силу равенства (*), по крайней мере, одно i не равно нулю. А тогда мы можем положить . Теорема. Пусть существуют положительные числа p1,…,p m такие, что и u0 является точкой максимума функции . Тогда точка u0 является эффективной. Доказательство. Допустим противное. Тогда найдется такая точка u1, что gi(u1)gi(u0) для всех i=1,…,m, причем, по крайней мере, одно из этих неравенств не обращается в равенство. Умножая эти неравенства на pi и суммируя, получим неравенство (u1)>(u0), что противоречит условию. Нельзя утверждать, что всякая эффективная точка может быть найдена в результате максимизации функции с положительными коэффициентами p1,…,p m. Пример. Пусть , g1(u)=u1, g2(u)=u2.Максимум функции достигается в точке . В то же время, точка (1,0) является эффективной. С другой стороны, при неотрицательных коэффициентах p1,…,pm, точка максимума функции может быть неэффективной в многокритериальной задаче. Пример. Пусть U={(u1,u2): 0u11, 0u21}, g1(u)=u1, g2(u)=u2. Точки максимума функции (u)=1g1(u)+0g2(u) образуют отрезок {(u1,u2): u1=1, 0u21}, а эффективной является только одна точка (1,1) этого отрезка. Теорема. Пусть существуют неотрицательные числа p1,…,p m такие, что и u0 является точкой максимума функции . Тогда точка u0 является слабо эффективной. Доказательство. Допустим противное. Тогда найдется такая точка u1, что gi(u1)>gi(u0) для всех i=1,…,m. Умножая эти неравенства на pi и суммируя, получим неравенство (u1)>(u0), что противоречит условию. 2. Другие варианты ▪ Двойственность ▪ Идеальная точка ▪ Парето и лексикография: задача 9.3 стр. 339 у толстого Мулена. Примеры Пример. Пусть множество U представляет собой стандартный симплекс U={(u1,u2,u3): u10, u20, u30, u1+u2+u3=1} и имеется два критерия g1(u)=2u1+7u2+u3 и g2(u)=3u1+u2+4u3. Найдем точки максимума функции (u)=pg1(u)+(1–p)g2(u). Так как критерии в данной задаче линейны, а максимум линейной функции непременно достигается в одной из вершин, то . Нарисовав графики, нетрудно понять, что при 0p1/3 максимум достигается в вершине (0,1,0), а при 1/3p1 он достигается в вершине (0,0,1). При p=1/3 точки максимума заполняют все ребро, соединяющие эти вершины. Таким образом, все точки этого ребра являются эффективными. Пример. Пусть множество U представляет собой стандартный симплекс U={(u1,u2,u3): u10, u20, u30, u1+u2+u3=1} и имеется два критерия g1(u)=3u1+7u2+u3 и g2(u)=4u1+u2+4u3. Анализ, аналогичный проведенному выше, показывает, что в данном случае эффективными являются все точки, лежащие на двух ребрах: соединяющем вершину (1,0,0) с вершиной (0,1,0) и соединяющем вершины (1,0,0) и (0,0,1). В этом случае множество эффективных точек не выпукло. В двух предыдущих примерах полезно нарисовать образ множества U в пространстве критериев. Пример: дуополия Курно. Две фирмы выпускают однородный товар и продают его на рынке. Цена, складывающаяся на рынке, линейно убывает с ростом суммарного предложения: p(u)=a–b(u1+u2), где u1 и u2 объемы выпуска продукции первой и второй фирмой соответственно (по своему смыслу величины u1 и u2 неотрицательны). Пусть затраты первой и второй фирм на выпуск единицы продукции равны c1 и c2, а их цели состоят в максимизации прибылей g1(u1,u2)= p(u)u1–c1u1 и g2(u1,u2)= p(u)u2–c2u2. Найдем эффективные точки в этой двухкритериальной задаче. Для этого найдем максимум функции (u1,u2)=tg1(u1,u2)+(1–t)g2(u1,u2). Имеем . При фиксированном управлении одной фирмы эта функция представляет собой квадратный трехчлен относительно управления другой фирмы с отрицательным старшим коэффициентом. Поэтому, максимум этой функции достигается в критической точке тогда и только тогда, когда последняя лежит внутри области u10, u20. В противном случае максимум находится на границе этой области. Критическая точка есть решение системы уравнений Решая эту систему относительно u1 и u2, получим параметрическое представление множества эффективных точек.1 Исключив же из этой системы параметр p, получим уравнение 2(u1+u2)2–(d1+2d2)u1–(d2+2d1)u2–d1d2=0 множества эффективных точек. Нетрудно видеть, что это уравнение параболы с осью, параллельной биссектрисе координатных углов. Пересечение этой параболы с неотрицательным квадрантом и дает множество эффективных точек2. Поскольку это множество пересекается с любым лучом, выходящим из начала координат и лежащим в неотрицательном квадранте, других эффективных точек нет. • Олигополия Курно (больше двух игроков) • При каких способах свертки будут получаться эффективные решения? • Какие способы свертки критериев согласуются с аксиомами из главы 13 книги: Льюс Р.Д., Райфа Х. Игры и решения. М.: ИЛ. 1961. • Многоугольник Ньютона – оптимальность по Парето • Задача 1.4 стр. 49 у толстого Мулена • Современное состояние, гл. 5 Задачи 1. Мнение ученого совета по любому вопросу складывается из мнений каждого из m его членов по правилу большинства голосов. Выразите соответствующую свертку через элементарные операции, если число членов совета нечетно. 2. Мнение ученого совета по любому вопросу складывается из мнений каждого из m его членов по правилу большинства голосов. Выразите соответствующую свертку через элементарные операции, если число членов совета четно и в случае равенства голосов решающим является мнение председателя совета. 3. Студенту за сессию предстоит сдать пять экзаменов, на каждом из которых он может получить оценку от 2 до 5. Для получения стипендии необходима сдать все экзамена как минимум на удовлетворительно, и при этом получить не более одной тройки. Выразите соответствующую свертку критериев через элементарные операции. 4. В биатлонной гонке принимают участие 7 спортсменов от каждой страны. По ее итогам каждый из них получает целое число очков от 0 до 30. В командный зачет идет сумма результатов трех лучших гонщиков. Выразите соответствующую свертку критериев через элементарные операции. 5. В каждой гонке, входящей в зачет кубка мира спортсмен получает целое число очков от 0 до 50. В общий зачет идет сумма очков, набранных в 30 гонках, за исключением трех худших. Выразите соответствующую свертку критериев через элементарные операции. 6. В командной гонке конькобежцев принимают участие три спортсмена. Результат команды равен времени третьего из финишировавших. Выразите соответствующую свертку критериев через элементарные операции (время измеряется с точностью до сотых долей секунды). 7. Качество прыжка в соревнованиях по прыжкам с трамплина оценивают пять арбитров. Каждый из них выставляет оценку от 0 до 20 баллов с шагом 0.5 балла. Самая высокая и самая низкая оценка отбрасываются, а сумма трех оставшихся идет в зачет соревнования. Выразите соответствующую свертку критериев через элементарные операции. *** 8. Пусть U – компактное множество, а g1,…,gm – непрерывные функции, gi:U. Докажите, что для любой неэффективной точки u0 найдется доминирующая ее эффективная точка u1. 9. Докажите, что множество всех эффективных векторов из выпуклого компакта в является компактом. 10. Постройте пример выпуклого компакта в 3, для которого множество эффективных векторов не замкнуто. 11. Докажите, что множество слабо эффективных стратегий совпадает с множеством решений уравнения 12. Докажите, что множество эффективных стратегий совпадает с множеством решений системы неравенств , где 13. Докажите, что если множество U компактно, а функции gi непрерывны, то найдется такой вектор b, что множество слабо эффективных стратегий равно , где , а объединение берется по всем векторам r с положительными компонентами. 14. Докажите, что если множество U компактно, а функции gi непрерывны, то найдется такой вектор b, что множество эффективных стратегий равно , где , множество D(r,b) определено так же, как в предыдущей задаче, а объединение берется по всем векторам r с положительными компонентами. *** 15. Пусть множество U представляет собой стандартный симплекс U={(u1,u2,u3): u10, u20, u30, u1+u2+u3=1} и имеется два критерия и . Найдите множество эффективных точек. 16. Пусть в игре n лиц Ui=[0,), , где a,b,ci – положительные числа. Найдите ситуации, оптимальные по Парето. 17. Пусть в игре n лиц Ui=[0,), (считаем, что 0/0=0), где ai,bi – положительные константы. Найдите ситуации, оптимальные по Парето. 18. Пусть U={(u1,…,um): ui0, u1+…+un=A}, V={(v1,…,vm): vi0, v1+…+vn=B}, , . Найдите ситуации, оптимальные по Парето (pi,qi,i,i – неотрицательные, A,B – положительные числа). 19. Пусть U={(u1,…,um): ui0, u1+…+un=A}, V={(v1,…,vm): vi0, v1+…+vn=B}, (i,i – неотрицательные, pi,qi A,B – положительные числа). Найдите ситуации, оптимальные по Парето. 20. Пусть Ui=[0,ai], , где ci – положительные константы. Существуют ли в этой игре ситуации, оптимальные по Парето? 21. Пусть Ui=[0,), , где ci – положительные константы. Существуют ли в этой игре ситуации, оптимальные по Парето. 22. Пусть a,b,c – положительные константы, U=V=(0,), g1(u,v)=u(a–bu+cv), g2(u,v)=v(a–bv+cu). Найдите ситуации, оптимальные по Парето. 23. Пусть в игре n лиц Ui={0,1}, где ai,bi – положительные константы. Найдите ситуации, оптимальные по Парето. Литература 1. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971. 2. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 3. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.