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

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

Теорема (Гермейер). Пусть u₀ – эффективная точка, причем gⁱ(u₀)>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) является эффективной.

Теорема.Пусть существуют такие положительные числа что и 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)=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(u)=a–b(u₁+u₂), где u₁ и u₂ объемы выпуска продукции первой и второй фирмой соответственно (по своему смыслу величины u₁ и u₂ неотрицательны). Пусть затраты первой и второй фирм на выпуск единицы продукции равны c₁ и c₂, а их цели состоят в максимизации прибылей g¹(u₁,u₂)= p(u)u₁–c₁u₁ и g²(u₁,u₂)= p(u)u₂–c₂u₂. Найдем эффективные точки в этой двухкритериальной задаче.

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

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

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

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

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

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

ЗАДАЧИ

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

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

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

4. В биатлонной гонке принимают участие 7 спортсменов от каждой страны. По ее итогам каждый из них получает целое число очков от 0 до 30. в командный зачет идет сумма результатов трех лучших гонщиков. Выразите соответствующую свертку критериев через элементарные операции.

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

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

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

8. Пусть u – компактное множество, а g¹,…,g^m – непрерывные функции, gⁱ:u® . Докажите, что для любой неэффективной точки u₀ найдется доминирующая ее эффективная точка u₁.

9. Докажите, что множество всех эффективных векторов из выпуклого компакта в является компактом.

10. Постройте пример выпуклого компакта в ³, для которого множество эффективных векторов не замкнуто.

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

12. Докажите, что множество эффективных стратегий совпадает с множеством решений системы неравенств , где

13. Докажите, что если множество u компактно, а функции gⁱ непрерывны, то найдется такой вектор b, что множество слабо эффективных стратегий равно , где , а объединение берется по всем векторам r с положительными компонентами.

14. Докажите, что если множество u компактно, а функции gⁱ непрерывны, то найдется такой вектор b, что множество эффективных стратегий равно , где , множество d(r,b) определено так же, как в предыдущей задаче, а объединение берется по всем векторам r с положительными компонентами.

15. Пусть множество u представляет собой стандартный симплекс u={(u₁,u₂,u₃): u₁³0, u₂³0, u₃³0, u₁+u₂+u₃=1} и имеется два критерия и . Найдите множество эффективных точек.

16. Пусть в игре n лиц uⁱ=[0,¥), , где a,b,c_i – положительные числа. Найдите ситуации, оптимальные по Парето.

17. Пусть в игре n лиц uⁱ=[0,¥), (считаем, что 0/0=0), где a_i,b_i – положительные константы. Найдите ситуации, оптимальные по Парето.

18. Пусть u={(u₁,…,u_m): u_i³0, u₁+…+u_n=a}, v={(v₁,…,v_m): v_i³0, v₁+…+v_n=b}, , . Найдите ситуации, оптимальные по Парето (p_i,q_i,a_i,b_i – неотрицательные, a,b – положительные числа).

19. Пусть u={(u₁,…,u_m): u_i³0, u₁+…+u_n=a}, v={(v₁,…,v_m): v_i³0, v₁+…+v_n=b}, (a_i,b_i – неотрицательные, p_i,q_i a,b – положительные числа). найдите ситуации, оптимальные по Парето.