apx.253a.　凸集合，端点，最適値  目次（第5章）へ

　凸集合　ｎ次元空間における点集合Ｓがあるとき，このＳに属する任意の２点ｘ₁ ，ｘ₂ に対し，0≦α ≦1 なる任意のαに対し

　　　ｘ＝αx ₁ ＋(１−α) ｘ₂　　　　　　　　　　　　　　　 (1)

が再びＳに属するとき，この集合Ｓが凸( convex )であるとよぶ．

　端　点　　凸集合Ｓに属し，かつその点ｘが，Ｓに属する互いに異なる２点ｘ₁ ，ｘ₂によって上式のごとく表されないとき，その点ｘを端点とよんでいる．

　端点で最適値　　線形計画問題において，目的関数は制約領域の端点において最小 (または最大)となる．また二つの端点ｘ^{t 1}，ｘ^{t 2} において同じ最小値 (最大値) をもつならば， ｘ^{t 1} ，ｘ^{t 2} を結ぶ線上のすべての点において同じ値をとる．

　いま，目的関数

　　　ｆ(x)＝ｃ₁ｘ₁＋ｃ₂ｘ₂＋…＋ｃ_nｘ_n　　　　　　　　　　 (2)

が端点以外の点x ⁰ において最小値 ( 最大値 ) をとるならば，この点は制約領域の (有限値の)端点 ｘ^{t 1}，ｘ^{t 2} … ｘ^{t k} により，

　　　ｘ⁰＝α₁ｘ^{t 1}＋α₂ｘ^{t 2}＋…＋α_kｘ^{t k}　　　　　　　　　(3)

ただし，

　　　α₁＋α₂＋…＋α _k＝１，α i ≧0，ｉ＝1，2，…，k

と表すことができるから，個の点における目的関数の値は

　　　ｆ(ｘ⁰ )＝ｃｘ⁰

　　　　　　 ＝ｃ(α₁ｘ^{t 1}＋α₂ｘ^{t 2}＋…＋α_kｘ^{t k} )

　　　　　　 ＝α₁ｃｘ^{t 1}＋α₂ｃｘ^{t 2}＋…＋α _kｃｘ^{t k}

　　　　　　 ＝α₁ｆ(ｘ^{t 1} )＋α₂ｆ(ｘ^{t 2} )＋…＋α _kｆ(ｘ^{t k} )　　 (4)

したがって，いま

　　　ｆ(ｘ^{t 1} )≧ ｆ(ｘ^{t 2} )≧…≧ｆ(ｘ^{t k} )

とすれば

　　　ｆ(ｘ^{t 1} )≧ ｆ(ｘ⁰ )≧ｆ(ｘ^{t k} )　　　　　　　　　　　　　(5)

となり，等号はすべてのｆ(ｘ ^{t i} )が等しいとき成り立つ．(5)はｆ(x)が x ⁰において最小 (最大) になるという仮定に反しており，結局,目的関数ｆ(x)は端点において最適値をとることが証明されたわけである．また二つの端点 x ^{t 1}，x ^{t 2} において同じ値を取るならば，この線分上の任意の点

　　　ｘ＝αｘ^{t 1}＋(１−α )ｘ ^{t 2}　　　　　　　　　　　　　　 (6)

において目的関数が等しい値をもつことも(4)から明らかである．