解法

前節では線形計画法の典型的な問題を例示しました。それは制約条件

$$10x+10y\leq 400$$ (7)

$$20x+10y\leq 600$$ (8)

$$15x+40y\leq 1300$$ (9)

$$0\leq x$$ (10)

$$0\leq y$$ (11)

のもとで,関数

$$f(x,y)=2x+y$$

を最大化する問題でした。
条件 $(\ref{senkei7})\sim (\ref{senkei8})$を充たす点$P=(x,y)$は 下のような,凸多角形の境界線も含めた内部にあります。

(図1.1)
この凸多角形の頂点を

$$P_0=(x_0,y_0),P_1=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3),P_4=(x_4,y_4)$$

とすると, 内部の点$P=(x,y)$はこれらの頂点 $P_i=(x_i,y_i),i=0,1,2,3,4$によって

$$\begin{eqnarray*} &&(1)~~P=\lambda_0 P_0 + \lambda_1 P_1+\lambda_2 P_2+\lambda_3... ...\lambda_2 \le 1,~~ 0 \le \lambda_3 \le 1,~~0 \le \lambda_4 \le 1 \end{eqnarray*}$$

で表されます。これを $P_i=(x_i,y_i),i=0,1,2,3,4$の凸結合といいます。

$$f(x,y)=2x+y$$

には「線形性」という性質があります。 これは $P=(x,y),Q=(x',y')$

と$\alpha,\beta$について,

$$f(\alpha P+ \beta Q)=f(\alpha (x,y)+\beta (x',y')) =\alpha f(x,y)+\beta f(x',y')=\alpha f(P)+\beta f(Q)$$

という性質です。この線形性を使うと,以下の議論ができます。

まず各頂点での関数$f$

$$f(P_i)=f(x_i,y_i),i=0,1,2,3,4$$

のうち最大値を $f(P_*)=f(x_*,y_*)$とします。すると凸多角形の内の任意の 点$P=(x,y)$に対する$f(P)=f(x,y)$は $P$が $P_i=(x_i,y_i),i=0,1,2,3,4$の凸結合で表されることから

$$f(P)=f(\lambda_0 P_0 + \lambda_1 P_1+\lambda_2 P_2+\lambda_3 P_3+\lambda_4 P_4)$$

さらに$f$の線形性から

$$右辺=\lambda_0 f(x_0,y_0) + \lambda_1 f(x_1,y_1) +\lambda_2 ... ..._2)+\lambda_3 f(x_3,y_3)+\lambda_4f(x_4,y_4) （ｆの線形性） \\$$

$f(P_*)=f(x_*,y_*)$が最大で,(3)のように各$\lambda_i$は正の数( $1 \ge \lambda_i \ge 0$)でしたら,

$$右辺\le (\lambda_0 + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4)f(x_*,y_*)\\$$

さらに,(2)から

$$\lambda_0 + \lambda_1 +\lambda_2 +\lambda_3 +\lambda_4= 1$$

で

$$f(P)=f(x,y) \le f(x_*,y_*)=f(P_*)$$

となります。結局,関数$f$の制約条件を表す凸多角形の内部(境界を含む)の点全てを調べる必要がなく、頂点での関数$f$の値を調べれば良いことがが判ります。

(図1.2)

線形化計画法の代表的な解法であるシンプレクス法はは,制約条件を表す凸多角形の頂点での関数$f$の値を効率的に調べる方法です。適当な,頂点から始め,関数$f$の値が増大する頂点へ次々移動して,最大解を探します。

この他に,凸多角形の内部の点から,最大解を与える頂点を探索する内点法もあります。 これらの詳細は,後日述べます。