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

Пусть 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 – компактное множество, а g ¹,…, g^m – непрерывные функции, gⁱ: U ® .

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

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

Остается положить и заметить, что тогда 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 ₀), что противоречит условию.