Логическое объединение качественных целей.

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

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

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

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

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

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

Пример. Цели уменьшить риск r операции и увеличить надежность g, связаны соотношением g = 1-r

5. Обобщенное логическое свертывание колич критериев

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

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

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

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

Заметим, что свертки (4.1), (4.2) прямо следуют из (5.1), (5.2), если все используемые функции принимают значения только 0 или 1.

5.3. Замена критерия на антагонистический. В этом случае, аналогичном случаю 4.3, максимизация критерия заменяется на минимизацию, то есть критерий g…, заменяется на M= -

Связь 5и4-ЮБ

Пример. Инвестор анализирует целесообразность вложения средств в проект. Он рассматривает две цели: увеличение доходности и надежности Рассмотрим различные варианты сверток.

Экономический. Пусть потеря 1% надежности для инвестора компенсируется 5% доходности. Тогда его критерий эффективности можно записать в виде

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

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

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

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

Покажем это на примере качественных целей

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

конъюнкция: g¹, …, g^m ®
дизъюнкция: g¹, …, g^m ®
отрицание: gⁱ ® 1–gⁱ.

Доказательство. Пусть v=(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.

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

. (*)

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

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

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

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

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

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

экономическая свертка;
разбиение на удовлетворительные и неудовлетворительные;
конъюнкция(обобщенная);
дизъюнкция (обобщенная);
отрицание (максимизация антагонистического критерия).

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

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

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

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

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

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

Пусть в пространстве критериев множество выигрышей задается ломаной OABCDO.

Тогда отрезок BC – определяет множество эффективных точек, отрезок AB – слабоэффективных точек.

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

Поиск эффективных точек

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

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

Доказательство. Положим Тогда

Пусть u – любая точка. Так как точка u₀ – эффективна, найдется номер i, для которого gⁱ(u)£ gⁱ(u₀), или, что то же самое, m_igⁱ(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) является эффективной.

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

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

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

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

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

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

uÎ U, wÎ .

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

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

, (*)

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

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

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

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

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

Пример. Пусть , g¹(u)=u₁, g²(u)=u₂.Максимум функции достигается в точке . В то же время, точка (1, 0) является эффективной.

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

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

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

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

Пример

Подставим крайние точки единичного треугольника трехмерного пространства

( (0, 0, 1) (0, 1, 0), (1, 0, 0) ) в систему уравнений , затем полученные значения подставим в М и получим 3 прямы

Max значение достигается при пересечении прямых 4-3Р и 6р+1, следовательно приравняв их найдет оптимальное значение р

4-3р=6р+1 → р = →

При (1, 0, 0) М =

При (0, 1, 0) М = 3

Значение М в точке (0, 1, 0) является максимальным и оптимальным по Парето

Примеры

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

Найдем точки максимума функции 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)=3u₁+7u₂+u₃ и g²(u)=4u₁+u₂+4u₃.

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

В двух предыдущих примерах полезно нарисовать образ множества U в пространстве критериев.

Пример: дуополия Курно. Две фирмы выпускают однородный товар и продают его на рынке. Цена, складывающаяся на рынке, линейно убывает с ростом суммарного предложения: p=a–b(u₁+u₂), где u₁ и u₂ объемы выпуска продукции первой и второй фирмой соответственно (по своему смыслу величины u₁ и u₂ неотрицательны). Пусть затраты первой и второй фирм на выпуск единицы продукции равны c₁ и c₂, а их цели состоят в максимизации прибылей g¹(u₁, u₂)=pu₁–c₁u₁ и g²(u₁, u₂)=pu₂–c₂u₂. Найдем эффективные точки в этой двухкритериальной задаче.

Для этого найдем максимум функции F(u₁, u₂)=p(u₁, u₂)+i(1–p) g²(u₁, u₂)=pu₂–c₂u₂. Имеем . При фиксированном управлении одной фирмы эта функция представляет собой квадратный трехчлен относительно управления другой фирмы с отрицательным старшим коэффициентом. Поэтому, максимум этой функции достигается в критической точке тогда и только тогда, когда последняя лежит внутри области u₁³ 0, u₂³ 0. В противном случае максимум находится на границе этой области.

Критическая точка есть решение системы уравнений

Решая эту систему относительно u₁ и u₂, получим параметрическое представление

множества эффективных точек.[1]

Исключив же из этой системы параметр p, получим уравнение

2(u₁+u₂)²–(d₁+2d₂)u₁–(d₂+2d₁)u₂–d₁d₂=0

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

Литература

Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.
Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982.
Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир, 1964.

Лекция 5

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒