不等式の表す領域と線形計画法

方針：$b\ne0$ なら $y$ について、$b=0$ なら $x$ について不等式を解く。負の数で割ると不等号の向きが変わることに注意する。
段 1（$b>0$）。$ax+by+c\ge0$ の両辺から $ax+c$ を引いて $by\ge-ax-c$ である。$b>0$ で割ると向きは変わらず、$y\ge-\dfrac abx-\dfrac cb$ となる。右辺は境界の直線の $y$ 座標なので、点 $(x,y)$ は直線上か、直線の真上にある。
段 2（$b<0$）。同じく $by\ge-ax-c$ である。$b<0$ で割ると向きが変わり、$y\le-\dfrac abx-\dfrac cb$ となる。点は直線上か、直線の真下にある。
段 3（$b=0$）。$(a,b)\ne(0,0)$ なので $a\ne0$ で、不等式は $ax\ge-c$ である。$a>0$ なら $x\ge-\dfrac ca$、$a<0$ なら $x\le-\dfrac ca$ となる。$\square$

方針：1 次式の値は、線分の上で端の値の重み付き平均になることを使う。
段 1（重み付き平均）。$f(x,y)=ax+by+c$、$P=(x_1,y_1)$、$Q=(x_2,y_2)$ とする。$c=(1-t)c+tc$ と書けるので
$$ f\bigl((1-t)P+tQ\bigr)=a\bigl((1-t)x_1+tx_2\bigr)+b\bigl((1-t)y_1+ty_2\bigr)+(1-t)c+tc=(1-t)f(P)+tf(Q) $$
である。
段 2（どの不等式も保たれる）。$P$、$Q$ が $K$ の点なら、各 $i$ について $f_i(P)\ge0$、$f_i(Q)\ge0$ である。$0\le t\le1$ なら $1-t\ge0$、$t\ge0$ なので、段 1 により $f_i\bigl((1-t)P+tQ\bigr)=(1-t)f_i(P)+tf_i(Q)\ge0$ である。これがすべての $i$ で成り立つので、$(1-t)P+tQ$ は $K$ に含まれる。$\square$

方針：$u$ を具体的に作り、直線 $P+tu$ の上で各 $f_i$ の値が $t$ の 1 次関数になることを使う。進めなくなる $t$ を最小値で決める。
段 1（$u$ を作る）。$P$ で等号が成り立つ不等式がなければ、$u=(1,0)$ とすれば条件は何も課されない。等号が成り立つ不等式があるとき、その 1 つの法線ベクトルを $n=(a,b)$ とし、$u:=(-b,a)$ とおく。$u\ne0$ で $n\cdot u=-ab+ab=0$ である。$P$ は頂点でないので、等号が成り立つほかの不等式の法線ベクトル $n_i$ はどれも $n$ に平行で、$n_i=\lambda_in$ と書ける。よって $n_i\cdot u=\lambda_i(n\cdot u)=0$ である。
段 2（直線の上での値）。$f_i(P)=a_ix_0+b_iy_0+c_i$（$P=(x_0,y_0)$）、$u=(u_1,u_2)$ とすると
$$ f_i(P+tu)=a_i(x_0+tu_1)+b_i(y_0+tu_2)+c_i=f_i(P)+t\,(n_i\cdot u) $$
である。
段 3（値が減る不等式がある）。$J:=\{i: n_i\cdot u<0\}$ とおく。もし $J$ が空なら、すべての $i$ と $t\ge0$ について段 2 から $f_i(P+tu)\ge f_i(P)\ge0$ となり、半直線 $\{P+tu: t\ge0\}$ 全体が $K$ に含まれる。しかし三角不等式により $|P+tu|\ge t|u|-|P|$ であり、右辺は $t$ を大きくするといくらでも大きくなるので、$K$ が円の内部に含まれることに反する。よって $J$ は空でない。$i\in J$ なら $n_i\cdot u\ne0$ なので、$P$ で等号が成り立つ不等式ではなく（段 1）、$f_i(P)>0$ である。
段 4（$T$ を決める）。
$$ T:=\min_{i\in J}\frac{f_i(P)}{-\,n_i\cdot u} $$
とおく。分子・分母とも正なので $T>0$ である。最小値をとる番号の 1 つを $j$ とする。$0\le t\le T$ とする。$i\notin J$ なら $n_i\cdot u\ge0$ なので $f_i(P+tu)\ge f_i(P)\ge0$ である。$i\in J$ なら、$T$ の決め方から $t\,(-n_i\cdot u)\le T\,(-n_i\cdot u)\le f_i(P)$ なので $f_i(P+tu)=f_i(P)-t\,(-n_i\cdot u)\ge0$ である。よって $P+tu\in K$ で、1 が成り立つ。また $f_j(P+Tu)=f_j(P)-T(-n_j\cdot u)=0$、$n_j\cdot u<0$ で、2 が成り立つ。
段 5（$-u$）。$n_i\cdot(-u)=-(n_i\cdot u)=0$ なので、$-u$ も段 1 の条件を満たし、段 2〜4 がそのまま使える。$\square$

方針：頂点でない点 $P$ から lem-rlp-move で両向きに進み、$P$ を 2 つの到着点を結ぶ線分の内分点として表す。到着点は $P$ より頂点に近いので、これを繰り返す。
段 1（1 回の分解）。$P\in K$ が頂点でないとし、lem-rlp-move の $u$ をとる。$u$ の向きに進んだ到着点を $P_+:=P+T_1u$、$-u$ の向きに進んだ到着点を $P_-:=P-T_2u$ とする（$T_1,T_2>0$）。
$$ T_2P_++T_1P_-=T_2P+T_1T_2u+T_1P-T_1T_2u=(T_1+T_2)P $$
なので、
$$ P=\frac{T_2}{T_1+T_2}\,P_++\frac{T_1}{T_1+T_2}\,P_- $$
である。2 つの係数は正で、和は $1$ である。
段 2（到着点は頂点に近づく）。lem-rlp-move の後で述べたとおり、$P_\pm$ では $P$ より「等号が成り立つ不等式の法線の向き」が少なくとも 1 種類多い。$P$ で等号が成り立つ不等式がなければ、$P_\pm$ は辺の点か頂点である。$P$ が辺の点（向きが 1 種類）なら、$P_\pm$ は頂点である。
段 3（まとめる）。$P$ が頂点なら $P=1\cdot P$ でよい。$P$ が辺の点なら、段 1・2 により $P$ は 2 つの頂点の凸結合である。$P$ が内部の点なら、段 1 で $P=\alpha A+(1-\alpha)B$（$0<\alpha<1$）と書け、$A$、$B$ は頂点か辺の点なので、それぞれ 2 つ以下の頂点の凸結合である。$A=\beta V_1+(1-\beta)V_2$、$B=\gamma V_3+(1-\gamma)V_4$（$0\le\beta,\gamma\le1$。$A$ が頂点なら $\beta=1$、$V_2=V_1$ とする。$B$ も同様）とすると
$$ P=\alpha\beta V_1+\alpha(1-\beta)V_2+(1-\alpha)\gamma V_3+(1-\alpha)(1-\gamma)V_4 $$
で、4 つの係数は $0$ 以上、和は $\alpha\bigl(\beta+(1-\beta)\bigr)+(1-\alpha)\bigl(\gamma+(1-\gamma)\bigr)=1$ である。$\square$

方針：$K$ のどの点 $P$ についても、$g(V)\ge g(P)$ となる頂点 $V$ があることを示す。lem-rlp-move の向き $u$ を、$g$ が減らない側に選んで進む。これは、$g=k$ の直線を $k$ が増える向きに動かす高校の方法を、1 歩ずつ確かめられる形にしたものである。
段 1（1 歩で $g$ は減らない）。$P\in K$ が頂点でないとし、lem-rlp-move の $u$ をとる。$w:=(p,q)$ とする。$w\cdot u<0$ なら $u$ を $-u$ に取り替えて、$w\cdot u\ge0$ とする（lem-rlp-move は $-u$ でも成り立つ）。到着点 $P':=P+Tu$ では
$$ g(P')=p(x_0+Tu_1)+q(y_0+Tu_2)+r=g(P)+T\,(w\cdot u)\ge g(P) $$
である（$P=(x_0,y_0)$、$u=(u_1,u_2)$）。
段 2（2 歩以内で頂点）。lem-rlp-move の後で述べたとおり、1 歩ごとに等号の成り立つ不等式の法線の向きが少なくとも 1 種類増える。$P$ が内部の点なら 1 歩で辺の点か頂点に、辺の点なら 1 歩で頂点に着く。よって段 1 を多くても 2 回くり返すと、$g(V)\ge g(P)$ を満たす頂点 $V$ に着く。
段 3（1 の証明）。$K$ は空でないので点 $P$ があり、段 2 により頂点がある。頂点は平行でない 2 本の境界線の交点で、交点は 2 本の組ごとに 1 つなので、頂点は $\frac{m(m-1)}2$ 個以下である。
段 4（最大値）。頂点は有限個なので、頂点での $g$ の値の最大値 $M$ があり、ある頂点 $V_0$ で $g(V_0)=M$ となる。$K$ のどの点 $P$ についても、段 2 の頂点 $V$ をとると $g(P)\le g(V)\le M$ である。$V_0\in K$ なので、$M$ が $K$ での最大値である。
段 5（最小値）。$-g=(-p)x+(-q)y+(-r)$ も 1 次式なので、段 4 を $-g$ に使うと、$-g$ の最大値は頂点での $-g$ の値の最大値 $-m'$ である（$m'$ は頂点での $g$ の値の最小値）。つまり $K$ のすべての点で $-g(P)\le-m'$、すなわち $g(P)\ge m'$ で、等号はある頂点で成り立つ。$m'$ が $K$ での最小値である。$\square$

方針：lem-rlp-convex-comb で点を頂点の凸結合に書き、1 次式の値が係数と同じ重みの平均になることを使う。
段 1（頂点）。$K$ は空でないので点 $P$ があり、lem-rlp-convex-comb により $P$ は頂点の凸結合なので、頂点は少なくとも 1 つある。個数が有限であることは prf-rlp-vertex-move の段 3 と同じである。
段 2（1 次式は凸結合を保つ）。$P=\sum_k\lambda_kV_k$（$\lambda_k\ge0$、$\sum_k\lambda_k=1$、$V_k=(x_k,y_k)$）とすると、$r=\sum_k\lambda_kr$ と書けるので
$$ g(P)=p\sum_k\lambda_kx_k+q\sum_k\lambda_ky_k+\sum_k\lambda_kr=\sum_k\lambda_k\,g(V_k) $$
である。
段 3（平均は最大を超えない）。$M$ を頂点での $g$ の値の最大値とすると、各 $k$ で $g(V_k)\le M$、$\lambda_k\ge0$ なので
$$ g(P)=\sum_k\lambda_kg(V_k)\le\sum_k\lambda_kM=M $$
である。$M$ はある頂点での値なので、$K$ での最大値である。最小値も、不等号の向きを逆にした同じ計算で示せる。$\square$

方針：頂点なら、中点に表す 2 点は頂点を通る 2 本の境界線の両方に乗るので、頂点と一致する。頂点でなければ、lem-rlp-move で両向きに同じ距離だけ進んだ 2 点の中点になる。
段 1（頂点なら中点に表せない）。$V$ を頂点とし、$V=\frac12(A+B)$、$A,B\in K$ とする。$V$ で等号が成り立つ不等式 $f_i$ について、prf-rlp-convex の段 1 で $t=\frac12$ とすると
$$ 0=f_i(V)=\frac12f_i(A)+\frac12f_i(B) $$
である。$f_i(A)\ge0$、$f_i(B)\ge0$ なので、$f_i(A)=f_i(B)=0$ である。頂点の定義から、法線ベクトルが平行でない 2 つの $f_i$、$f_{i'}$ が $V$ で等号になるので、$A$ も $B$ も 2 本の平行でない直線 $f_i=0$、$f_{i'}=0$ の交点である。交点はただ 1 つなので $A=B=V$ となり、「異なる 2 点」の中点ではない。
段 2（頂点でなければ中点に表せる）。$V$ が頂点でないとき、lem-rlp-move により $u\ne0$ と $T_1,T_2>0$ があって、$0\le t\le T_1$ で $V+tu\in K$、$0\le t\le T_2$ で $V-tu\in K$ である。$T:=\min(T_1,T_2)>0$ とすると、$V+Tu$ と $V-Tu$ は $K$ の異なる 2 点で、中点は $V$ である。$\square$

方針：ex-rlp-certificate と同じ計算を文字で行う。不等号を 2 回使い、それぞれでどの条件を使うかを確かめる。
段 1（係数の比較）。$x\ge0$ と $p\le\sum_ia_iu_i$ から $px\le\left(\sum_ia_iu_i\right)x$ である。同じく $y\ge0$ と $q\le\sum_ib_iu_i$ から $qy\le\left(\sum_ib_iu_i\right)y$ である。足して並べ替えると
$$ px+qy\le\sum_i(a_ix+b_iy)\,u_i $$
である。
段 2（条件の比較）。各 $i$ で $a_ix+b_iy\le c_i$、$u_i\ge0$ なので $(a_ix+b_iy)u_i\le c_iu_i$ である。足して $\sum_i(a_ix+b_iy)u_i\le\sum_ic_iu_i$ で、段 1 と合わせて主張の不等式を得る。
段 3（等号の場合）。主問題の条件を満たすどの $(x',y')$ についても、段 1・2 から $px'+qy'\le\sum_ic_iu_i=px+qy$ なので、$px+qy$ は主問題の最大値である。同様に、双対問題の条件を満たすどの $(u_i')$ についても $\sum_ic_iu_i'\ge px+qy=\sum_ic_iu_i$ なので、$\sum_ic_iu_i$ は双対問題の最小値である。$\square$