線形の目的関数の最大・最小は頂点で起こる

$f_j(X)=\boldsymbol n_j\cdot X+c_j$（$\boldsymbol n_j\ne\boldsymbol 0$、$j=1,\dots,k$）に対し $K=\{X\mid f_j(X)\ge0\ (j=1,\dots,k)\}$ は空でない有界集合とする。$K$ の点 $V$ で、2 つの制約 $f_j(V)=f_{j'}(V)=0$ で $\boldsymbol n_j,\boldsymbol n_{j'}$ が 1 次独立なものを頂点という。頂点は有限個で、1 次関数 $\varphi(X)=\boldsymbol\alpha\cdot X+\beta$ について、$K$ の各点 $X$ に対し、$\varphi(V)\ge\varphi(X)$ を満たす頂点 $V$ が存在する。したがって $K$ での $\varphi$ の最大値は頂点での値の最大値で、最小値も同様である。