多面体
変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する連立1次不等式\begin{equation}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。
連立1次不等式\(\left( 1\right) \)の係数行列\(A\)と変数ベクトル\(\boldsymbol{x}\)および定数ベクトル\(\boldsymbol{b}\)を、\begin{eqnarray*}A &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\in M_{m,n}\left( \mathbb{R} \right) \\
\boldsymbol{x} &=&\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\in M_{n,1}\left( \mathbb{R} \right) \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m}\end{pmatrix}\in M_{m,1}\left( \mathbb{R} \right)
\end{eqnarray*}と定めれば、\begin{eqnarray*}
A\boldsymbol{x} &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\quad \because A,\boldsymbol{x}\text{の定義} \\
&=&\begin{pmatrix}
a_{11}x_{1}+\cdots +a_{1n}x_{n} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}\quad \because \text{行列積の定義}
\end{eqnarray*}という変形が可能であるため、連立1次不等式\(\left( 1\right) \)を行列不等式\begin{equation}A\boldsymbol{x}\leq \boldsymbol{b} \quad \cdots (2)
\end{equation}として表現できます。ただし、ここでの\(\leq \)はユークリッド空間\(\mathbb{R} ^{n}\)における標準的順序です。
連立1次不等式\(\left( 1\right) \)と行列不等式\(\left( 2\right) \)は解集合を共有するため両者を同一視できます。したがって、連立1次不等式\(\left( 1\right) \)の解集合を、\begin{equation*}P=\left\{ \boldsymbol{x}\in M_{n,1}\left( \mathbb{R} \right) \ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}と表現できますが、これを多面体（polyhedron）と呼びます。後ほど示すように多面体は凸集合であるため、多面体を凸多面体（convex polyhedron）と呼ぶ場合もあります。
\end{equation*}を下半空間（lower halfspace）と呼び、\begin{equation*}
H^{+}\left( \boldsymbol{a},b\right) =\left\{ \boldsymbol{x}\in M_{n,1}\left( \mathbb{R} \right) \ |\ \boldsymbol{a}^{t}\boldsymbol{x}\geq b\right\}
\end{equation*}を上半空間（upper halfspace）と呼びます。下半空間と上半空間を総称して半空間（half space）と呼びます。下半空間\(H^{-}\left( \boldsymbol{a},b\right) \)は1次不等式\begin{equation*}a_{1}x_{1}+\cdots +a_{n}x_{n}\leq b
\end{equation*}の解集合であり、上半空間\(H^{+}\left( \boldsymbol{a},b\right) \)は1次不等式\begin{equation*}a_{1}x_{1}+\cdots +a_{n}x_{n}\geq b
\end{equation*}すなわち、\begin{equation*}
-a_{1}x_{1}-\cdots -a_{n}x_{n}\leq -b
\end{equation*}の解集合ですが、1次不等式は1つの不等式からなる連立不等式であるため、半空間\(H^{-}\left( \boldsymbol{a},b\right) ,H^{+}\left( \boldsymbol{a},b\right) \)はともに多面体です。
M_{n,1}\left( \mathbb{R} \right) \ |\ \boldsymbol{a}_{1}^{t}\boldsymbol{x}\leq b_{1}\right\} \\
\vdots \\
H^{-}\left( \boldsymbol{a}_{m},b_{m}\right) =\left\{ \boldsymbol{x}\in
M_{n,1}\left( \mathbb{R} \right) \ |\ \boldsymbol{a}_{1}^{t}\boldsymbol{x}\leq b_{m}\right\}
\end{gather*}を定義します。これらの共通部分\begin{equation*}
H^{-}\left( \boldsymbol{a}_{1},b_{1}\right) \cap \cdots \cap H^{-}\left(
\boldsymbol{a}_{m},b_{m}\right)
\end{equation*}は連立1次不等式\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m}\end{array}\right.
\end{equation*}の解集合であるため、下半空間どうしの共通部分\(H^{-}\left( \boldsymbol{a}_{1},b\right)\cap \cdots \cap H^{-}\left( \boldsymbol{a}_{m},b\right) \)は多面体です。同様の理由により、上半空間どうしの共通部分\begin{equation*}H^{+}\left( \boldsymbol{a}_{1},b\right) \cap \cdots \cap H^{+}\left(
\boldsymbol{a}_{m},b\right)
\end{equation*}もまた多面体です。また、同様の理由により、下半空間と上半空間どうしの共通部分もまた多面体です。
連立1次方程式の解集合は多面体
変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する連立1次方程式\begin{equation}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。
連立1次方程式\(\left( 1\right) \)は以下の連立1次不等式\begin{equation*}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m} \\
a_{11}x_{1}+\cdots +a_{1n}x_{n}\geq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\geq b_{m}\end{array}\right.
\end{equation*}すなわち、\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq b_{m} \\
-a_{11}x_{1}+\cdots -a_{1n}x_{n}\leq -b_{1} \\
\vdots \\
-a_{m1}x_{1}+\cdots -a_{mn}x_{n}\leq -b_{m}\end{array}\right.
\end{equation*}と必要十分であるため、連立1次不等式\(\left(1\right) \)の係数行列\(A\)と変数ベクトル\(\boldsymbol{x}\)および定数ベクトル\(\boldsymbol{b}\)を、\begin{eqnarray*}A &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn} \\
-a_{11} & \cdots & -a_{1n} \\
\vdots & \ddots & \vdots \\
-a_{m1} & \cdots & -a_{mn}\end{pmatrix}\in M_{2m,n}\left( \mathbb{R} \right) \\
\boldsymbol{x} &=&\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\in M_{n,1}\left( \mathbb{R} \right) \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m} \\
-b_{1} \\
\vdots \\
-b_{m}\end{pmatrix}\in M_{2m,1}\left( \mathbb{R} \right)
\end{eqnarray*}と定めれば、\begin{eqnarray*}
A\boldsymbol{x} &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn} \\
-a_{11} & \cdots & -a_{1n} \\
\vdots & \ddots & \vdots \\
-a_{m1} & \cdots & -a_{mn}\end{pmatrix}\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\quad \because A,\boldsymbol{x}\text{の定義} \\
&=&\begin{pmatrix}
a_{11}x_{1}+\cdots +a_{1n}x_{n} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n} \\
-a_{11}x_{1}+\cdots -a_{1n}x_{n} \\
\vdots \\
-a_{m1}x_{1}-\cdots -a_{mn}x_{n}\end{pmatrix}\quad \because \text{行列積の定義}
\end{eqnarray*}という変形が可能であるため、連立1次方程式\(\left( 1\right) \)を行列不等式\begin{equation}A\boldsymbol{x}\leq \boldsymbol{b} \quad \cdots (2)
\end{equation}として表現できます。したがって、連立1次方程式\(\left( 1\right) \)の解集合もまた多面体\begin{equation*}P=\left\{ \boldsymbol{x}\in M_{n,1}\left( \mathbb{R} \right) \ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}として表現できます。
\end{equation*}を超平面（hyperplane）と呼びます。超平面\(H\left( \boldsymbol{a},b\right) \)は1次方程式\begin{equation*}a_{1}x_{1}+\cdots +a_{n}x_{n}=b
\end{equation*}の解集合ですが、1次方程式は1つの方程式からなる連立方程式であるため、超平面\(H\left( \boldsymbol{a},b\right) \)は多面体です。
\vdots \\
H\left( \boldsymbol{a}_{m},b\right) =\left\{ \boldsymbol{x}\in M_{n,1}\left( \mathbb{R} \right) \ |\ \boldsymbol{a}_{1}^{t}\boldsymbol{x}\leq b\right\}
\end{gather*}を定義します。これらの共通部分\begin{equation*}
H\left( \boldsymbol{a}_{1},b\right) \cap \cdots \cap H\left( \boldsymbol{a}_{m},b\right)
\end{equation*}は連立1次方程式\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right.
\end{equation*}の解集合であるため、超平面どうしの共通部分\(H\left( \boldsymbol{a}_{1},b\right) \cap \cdots\cap H\left( \boldsymbol{a}_{m},b\right) \)は多面体です。
1次方程式と1次不等式が混在する連立式の解集合は多面体
変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する1次方程式と1次不等式からなる連立式\begin{equation}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1} \\
\vdots \\
a_{p1}x_{1}+\cdots +a_{pn}x_{n}=b_{p} \\
c_{11}x_{1}+\cdots +c_{1n}x_{n}\leq d_{1} \\
\vdots \\
c_{q1}x_{1}+\cdots +c_{qn}x_{n}\leq d_{q}\end{array}\right. \quad \cdots (1)
\end{equation}が与えられているものとします。ただし、\(a_{ij},c_{ij}\in \mathbb{R} \)は係数、\(b_{i},d_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。
連立式\(\left( 1\right) \)は以下の連立1次不等式\begin{equation*}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{p1}x_{1}+\cdots +a_{pn}x_{n}\leq b_{p} \\
a_{11}x_{1}+\cdots +a_{1n}x_{n}\geq b_{1} \\
\vdots \\
a_{p1}x_{1}+\cdots +a_{pn}x_{n}\geq b_{p} \\
c_{11}x_{1}+\cdots +c_{1n}x_{n}\leq d_{1} \\
\vdots \\
c_{q1}x_{1}+\cdots +c_{qn}x_{n}\leq d_{q}\end{array}\right.
\end{equation*}すなわち、\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq b_{1} \\
\vdots \\
a_{p1}x_{1}+\cdots +a_{pn}x_{n}\leq b_{p} \\
-a_{11}x_{1}+\cdots -a_{1n}x_{n}\leq -b_{1} \\
\vdots \\
-a_{p1}x_{1}+\cdots -a_{pn}x_{n}\leq -b_{p} \\
c_{11}x_{1}+\cdots +c_{1n}x_{n}\leq d_{1} \\
\vdots \\
c_{q1}x_{1}+\cdots +c_{qn}x_{n}\leq d_{q}\end{array}\right.
\end{equation*}と必要十分であるため、連立式\(\left( 1\right) \)の係数行列\(A\)と変数ベクトル\(\boldsymbol{x}\)および定数ベクトル\(\boldsymbol{b}\)を、\begin{eqnarray*}A &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{p1} & \cdots & a_{pn} \\
-a_{11} & \cdots & -a_{1n} \\
\vdots & \ddots & \vdots \\
-a_{p1} & \cdots & -a_{pn} \\
c_{11} & \cdots & c_{1n} \\
\vdots & \ddots & \vdots \\
c_{q1} & \cdots & c_{qn}\end{pmatrix}\in M_{2p+q,n}\left( \mathbb{R} \right) \\
\boldsymbol{x} &=&\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\in M_{n,1}\left( \mathbb{R} \right) \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{p} \\
-b_{1} \\
\vdots \\
-b_{p} \\
d_{1} \\
\vdots \\
d_{q}\end{pmatrix}\in M_{2p+q,1}\left( \mathbb{R} \right)
\end{eqnarray*}と定めれば、\begin{eqnarray*}
A\boldsymbol{x} &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{p1} & \cdots & a_{pn} \\
-a_{11} & \cdots & -a_{1n} \\
\vdots & \ddots & \vdots \\
-a_{p1} & \cdots & -a_{pn} \\
c_{11} & \cdots & c_{1n} \\
\vdots & \ddots & \vdots \\
c_{q1} & \cdots & c_{qn}\end{pmatrix}\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\quad \because A,\boldsymbol{x}\text{の定義} \\
&=&\begin{pmatrix}
a_{11}x_{1}+\cdots +a_{1n}x_{n} \\
\vdots \\
a_{p1}x_{1}+\cdots +a_{pn}x_{n} \\
-a_{11}x_{1}+\cdots -a_{1n}x_{n} \\
\vdots \\
-a_{p1}x_{1}+\cdots -a_{pn}x_{n} \\
c_{11}x_{1}+\cdots +c_{1n}x_{n} \\
\vdots \\
c_{q1}x_{1}+\cdots +c_{qn}x_{n}\end{pmatrix}\quad \because \text{行列積の定義}
\end{eqnarray*}という変形が可能であるため、連立式\(\left(1\right) \)を行列不等式\begin{equation}A\boldsymbol{x}\leq \boldsymbol{b} \quad \cdots (2)
\end{equation}として表現できます。したがって、連立式\(\left( 1\right) \)の解集合もまた多面体\begin{equation*}P=\left\{ \boldsymbol{x}\in M_{n,1}\left( \mathbb{R} \right) \ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}として表現できます。
多面体は凸集合
多面体は凸集合です。つまり、多面体\(P\subset \mathbb{R} ^{n}\)が与えられたとき、\begin{equation*}\forall \boldsymbol{x}_{1}\in A,\ \forall \boldsymbol{x}_{2}\in A,\ \forall
\lambda \in \left[ 0,1\right] :\lambda \boldsymbol{x}_{1}+\left( 1-\lambda
\right) \boldsymbol{x}_{2}\in A
\end{equation*}が成り立ちます。
ユークリッド空間上の多面体\(P\subset \mathbb{R} ^{n}\)は凸集合である。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】