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

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

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

Пример 1. Для выпуска двух видов продукции используются три вида ресурсов. Известна матрица норм расхода , цены на ресурсы, цены реализации продукции и запасы ресурсов.

, , , .

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

Можно пожелать добиться максимума выручки и прибыли одновременно. Тогда получим задачу с двумя целевыми функциями:

или в развернутой форме

,

,

,

,

,

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

Вершина | A(0,10) | B(10,5) | C(12,3) | D(13,0)
Функция | 120 | 230 | 240 | 221
Функция | 50 | 55 | 51 | 39

Из таблицы видно, что максимальное значение , а соответствующее ему оптимальное решение есть C(12,3); максимальное значение и соответствующее ему оптимальное решение есть B(10,5).

окончательный выбор наилучшего решения за ЛПР.

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

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

Если доминирует , то ни при каком разумном подходе не может быть признано наилучшим решением.

Решение называется недоминируемым, если нет решения , которое доминировало бы .

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

Определение: множество недоминируемых решений называется множеством Парето или множеством оптимальности по Парето.

Пример 2: Рассмотрим некоторое множество на плоскости . Оно называется игровым множеством. Два игрока играют в игру. Партия игры состоит в том, что они указывают совместно пару чисел . Если это точка попадает в множество то первый игрок получает сумму , а второй - сумму .Затем играется следующая партия и т.д. Каждый из игроков хочет выиграть как можно больше, но для этого они вынуждены взаимодействовать и играть совместно, обдумывая свои ходы.

Совершенно ясно, что точка доминирует точку , если и или . Следовательно, для множества , как видно из рисунка, множество недоминируемых точек, или множество Парето, есть ломанная

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

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

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

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

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

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

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

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

Ящик Эджворта позволяет ответить на вопрос: каково конечное распределение (т.е. после всевозможных обменов) для данного начального?

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

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

Как же узнать оптимальные по Парето точки в этом ящике Эджворта?

Рассмотрим произвольную точку . Пусть и , и .

Очевидно следующее.

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

Если функции полезности «хорошие», например дифференцируемые, то справедливо следующее.

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