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

Пусть 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)=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). В этом случае множество эффективных точек не выпукло.

В двух предыдущих примерах полезно нарисовать образ множества 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 – положительные числа). найдите ситуации, оптимальные по Парето.

20. Пусть uⁱ =[0, a_i ], , где c_i – положительные константы. Существуют ли в этой игре ситуации, оптимальные по Парето?

21. Пусть uⁱ =[0,¥), , где c_i – положительные константы. Существуют ли в этой игре ситуации, оптимальные по Парето.

22. Пусть a,b,c – положительные константы, u=v =(0,¥), g ¹(u,v)= u (a–bu+cv), g ²(u,v)= v (a–bv+cu). найдите ситуации, оптимальные по Парето.