多面体（凸多面体）
有限\(n\)個の変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する有限\(m\)本の1次不等式から構成される連立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} \)は変数です。
係数行列\(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 \mathbb{R} ^{n} \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m}\end{pmatrix}\in \mathbb{R} ^{m}
\end{eqnarray*}と定めれば、\begin{eqnarray*}
&&\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. \\
&\Leftrightarrow &\begin{pmatrix}
a_{11}x_{1}+\cdots +a_{1n}x_{n} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}\leq \left(
\begin{array}{c}
b_{1} \\
\vdots \\
b_{m}\end{array}\right) \quad \because \text{標準的順序}\leq
\text{の定義} \\
&\Leftrightarrow &\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}\leq \left(
\begin{array}{c}
b_{1} \\
\vdots \\
b_{m}\end{array}\right) \quad \because \text{行列積の定義} \\
&\Leftrightarrow &A\boldsymbol{x}\leq b
\end{eqnarray*}が成り立つため、連立1次不等式\(\left( 1\right) \)を行列不等式\begin{equation}A\boldsymbol{x}\leq \boldsymbol{b} \quad \cdots (2)
\end{equation}として表現できます。ただし、ここでの\(\leq \)はユークリッド空間\(\mathbb{R} ^{n}\)における標準的順序であり、任意の\(\boldsymbol{x},\boldsymbol{y}\in \mathbb{R} ^{n}\)に対して、\begin{equation*}\boldsymbol{x}\leq \boldsymbol{y}\Leftrightarrow \forall i\in \left\{
1,\cdots ,n\right\} :x_{i}\leq y_{i}
\end{equation*}を満たすものとして定義されます。
連立1次不等式\(\left( 1\right) \)と行列不等式\(\left( 2\right) \)は解集合を共有するため両者を同一視できます。そこで、それらの解集合を、\begin{equation*}P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}で表記し、これを多面体（polyhedron）と呼びます。後ほど示すように多面体は凸集合であるため、多面体を凸多面体（convex polyhedron）と呼ぶ場合もあります。
\end{equation*}と定義されますが、\begin{equation*}
\boldsymbol{a}\cdot \boldsymbol{x}\leq c\Leftrightarrow a_{1}x_{1}+\cdots
+a_{n}x_{n}\leq c
\end{equation*}であるため、\(H^{-}\left( \boldsymbol{a},c\right) \)は1本の1次不等式からなる連立1次不等式\begin{equation*}a_{1}x_{1}+\cdots +a_{n}x_{n}\leq c
\end{equation*}の解集合であり、ゆえに多面体です。実際、\(\boldsymbol{a},\boldsymbol{x}\)を列ベクトルとみなす場合には、\begin{eqnarray*}\boldsymbol{a}\cdot \boldsymbol{x}\leq c &\Leftrightarrow &\left(
\begin{array}{c}
a_{1} \\
\vdots \\
a_{n}\end{array}\right) \cdot \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \leq c \\
&\Leftrightarrow &\left( a_{1},\cdots ,a_{n}\right) \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \leq c \\
&\Leftrightarrow &\boldsymbol{a}^{t}\boldsymbol{x}\leq c
\end{eqnarray*}となるため、係数行列を、\begin{equation*}
A=\boldsymbol{a}^{t}\in M_{1,n}\left( \mathbb{R} \right)
\end{equation*}と定義することにより、\begin{equation*}
\boldsymbol{a}\cdot \boldsymbol{x}\leq c\Leftrightarrow A\boldsymbol{x}\leq c
\end{equation*}となります。したがって、\begin{equation*}
H^{-}\left( \boldsymbol{a},c\right) =\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq c\right\}
\end{equation*}であるため\(H^{-}\left( \boldsymbol{a},c\right) \)は多面体です。
\end{equation*}と定義されますが、\begin{eqnarray*}
\boldsymbol{a}\cdot \boldsymbol{x}\geq c &\Leftrightarrow &-\left(
\boldsymbol{a}\cdot \boldsymbol{x}\right) \leq -c \\
&\Leftrightarrow &-a_{1}x_{1}-\cdots -a_{n}x_{n}\leq -c
\end{eqnarray*}であるため、\(H^{+}\left( \boldsymbol{a},c\right) \)は1本の1次不等式からなる連立1次不等式\begin{equation*}-a_{1}x_{1}-\cdots -a_{n}x_{n}\leq -c
\end{equation*}の解集合であり、ゆえに多面体です。実際、\(\boldsymbol{a},\boldsymbol{x}\)を列ベクトルとみなす場合には、\begin{eqnarray*}\boldsymbol{a}\cdot \boldsymbol{x}\geq c &\Leftrightarrow &-\left(
\boldsymbol{a}\cdot \boldsymbol{x}\right) \leq -c \\
&\Leftrightarrow &\left( -\boldsymbol{a}\right) \cdot \boldsymbol{x}\leq -c
\\
&\Leftrightarrow &\left(
\begin{array}{c}
-a_{1} \\
\vdots \\
-a_{n}\end{array}\right) \cdot \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \leq -c \\
&\Leftrightarrow &\left( -a_{1},\cdots ,-a_{n}\right) \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \leq -c \\
&\Leftrightarrow &\left( -\boldsymbol{a}\right) ^{t}\boldsymbol{x}\leq -c
\end{eqnarray*}となるため、係数行列を、\begin{equation*}
A=\left( -\boldsymbol{a}\right) ^{t}\in M_{1,n}\left( \mathbb{R} \right)
\end{equation*}と定義することにより、\begin{equation*}
\boldsymbol{a}\cdot \boldsymbol{x}\geq c\Leftrightarrow A\boldsymbol{x}\leq
-c
\end{equation*}となります。したがって、\begin{equation*}
H^{+}\left( \boldsymbol{a},c\right) =\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq -c\right\}
\end{equation*}であるため\(H^{+}\left( \boldsymbol{a},c\right) \)は多面体です。
\vdots \\
H^{-}\left( \boldsymbol{a}_{m},c_{m}\right) =\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ \boldsymbol{a}_{m}\cdot \boldsymbol{x}\leq c_{m}\right\}
\end{gather*}を定義します。これらの共通部分\begin{equation}
H^{-}\left( \boldsymbol{a}_{1},c_{1}\right) \cap \cdots \cap H^{-}\left(
\boldsymbol{a}_{m},c_{m}\right) \quad \cdots (1)
\end{equation}は連立1次不等式\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}\leq c_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\leq c_{m}\end{array}\right.
\end{equation*}の解集合であるため\(\left( 1\right) \)は多面体です。同様の理由により、上半空間どうしの共通部分\begin{equation*}H^{+}\left( \boldsymbol{a}_{1},c_{1}\right) \cap \cdots \cap H^{+}\left(
\boldsymbol{a}_{m},c_{m}\right)
\end{equation*}もまた多面体です。同様の理由により、下半空間と上半空間どうしの共通部分もまた多面体です。
多面体の幾何学的解釈
多面体の形式的定義は、\begin{equation*}
P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}ですが、これは有限個の1次不等式から構成される連立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*}の解集合と一致します。個々の不等式は空間\(\mathbb{R} ^{n}\)上に存在する平らな壁の内側の領域に相当するため、多面体は有限個の平らな壁で空間\(\mathbb{R} ^{n}\)を切り取り、その内側に残った領域とみなすことができます。
&=&\left\{ x\in \mathbb{R} \ |\ 0\leq x\leq 1\right\}
\end{eqnarray*}に注目します。以下の関係\begin{eqnarray*}
0\leq x\leq 1 &\Leftrightarrow &0\leq x\wedge x\leq 1 \\
&\Leftrightarrow &-x\leq 0\wedge x\leq 1
\end{eqnarray*}が成り立つため\(P\)は多面体であるとともに、\begin{equation*}P=\left\{ x\in \mathbb{R} \ |\ -x\leq 0\right\} \cap \left\{ x\in \mathbb{R} \ |\ x\leq 1\right\}
\end{equation*}と表現できます。つまり、\(P\)は空間\(\mathbb{R} \)上に存在する2個の壁\begin{eqnarray*}&&\left\{ x\in \mathbb{R} \ |\ x=0\right\} \\
&&\left\{ x\in \mathbb{R} \ |\ x=1\right\}
\end{eqnarray*}によって囲まれた領域です。
\end{equation*}に注目します。以下の関係\begin{equation*}
x\geq 0\wedge y\geq 0\wedge x+y\leq 1\Leftrightarrow -x\leq 0\wedge -y\leq
0\wedge x+y\leq 1
\end{equation*}が成り立つため\(P\)は多面体であるとともに、\begin{equation*}P=\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ -x\leq 0\right\} \cap \left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ -y\leq 0\right\} \cap \left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ x+y\leq 1\right\}
\end{equation*}と表現できます。つまり、\(P\)は空間\(\mathbb{R} ^{2}\)上に存在する3個の壁\begin{eqnarray*}&&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ x=0\right\} \\
&&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ y=0\right\} \\
&&\left\{ \left( x,y\right) \in \mathbb{R} ^{2}\ |\ x+y=1\right\}
\end{eqnarray*}によって囲まれた領域です。
\end{equation*}に注目します。以下の関係\begin{eqnarray*}
0 &\leq &x\leq 1\wedge 0\leq y\leq 1\wedge 0\leq z\leq 1 \\
&\Leftrightarrow &-x\leq 0\wedge x\leq 1\wedge -y\leq 0\wedge y\leq 1\wedge
-z\leq 0\wedge z\leq 1
\end{eqnarray*}が成り立つため\(P\)は多面体であるとともに、\begin{eqnarray*}P &=&\left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ -x\leq 0\right\} \cap \left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ x\leq 1\right\} \\
&&\cap \left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ -y\leq 0\right\} \cap \left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ y\leq 1\right\} \\
&&\cap \left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ -z\leq 0\right\} \cap \left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ z\leq 1\right\}
\end{eqnarray*}と表現できます。つまり、\(P\)は空間\(\mathbb{R} ^{3}\)上に存在する6個の壁\begin{eqnarray*}&&\left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ x=0\right\} \\
&&\left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ x=1\right\} \\
&&\left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ y=0\right\} \\
&&\left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ y=1\right\} \\
&&\left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ z=0\right\} \\
&&\left\{ \left( x,y,z\right) \in \mathbb{R} ^{2}\ |\ z=1\right\}
\end{eqnarray*}によって囲まれた領域です。
多面体は有限個の平らな壁の内側の領域であるため、多面体の境界は有限個の面であり、ゆえに境界は滑らかな曲面ではありません。多面体という名称の由来はここにあります。この意味において、多面体を規定する1次不等式の個数が有限であるという条件は重要です。無限個の1次不等式からなる連立1次不等式の解集合については、その境界が滑らかな曲面になり得るため、それを多面体とみなすことはできません。
\end{equation*}に注目します。\(\left\Vert \boldsymbol{a}\right\Vert =1\)を満たすベクトル\(\boldsymbol{a}\in \mathbb{R} ^{2}\)すなわち単位ベクトルは無数に存在するため、\(A\)は無限個の1次不等式からなる連立1次不等式の解集合であり、ゆえに多面体ではありません。実際、\begin{equation*}A=\left\{ \boldsymbol{x}\in \mathbb{R} ^{2}\ |\ \left\Vert \boldsymbol{x}\right\Vert \leq 1\right\}
\end{equation*}が成り立ちますが、\(A\)は単位円盤であるため境界が滑らかな曲面であり、これを多面体とみなすことはできません（演習問題）。
連立1次方程式の解集合は多面体
有限\(n\)個の変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する有限\(m\)本の1次方程式から構成される連立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次方程式は互いに反対向きの2つの1次不等式の組として表現できることを踏まえると、連立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*}と必要十分であるため、係数行列\(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 \mathbb{R} ^{n} \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m} \\
-b_{1} \\
\vdots \\
-b_{m}\end{pmatrix}\in \mathbb{R} ^{2m}
\end{eqnarray*}と定めれば、\begin{eqnarray*}
&&\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. \\
&\Leftrightarrow &\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. \\
&\Leftrightarrow &\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}\leq
\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m} \\
-b_{1} \\
\vdots \\
-b_{m}\end{pmatrix}
\\
&\Leftrightarrow &\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}\leq
\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m} \\
-b_{1} \\
\vdots \\
-b_{m}\end{pmatrix}
\\
&\Leftrightarrow &A\boldsymbol{x}\leq \boldsymbol{b}
\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) \)の解集合もまた多面体\begin{equation*}P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}として表現できます。
\end{equation*}と定義されますが、\begin{equation*}
\boldsymbol{a}\cdot \boldsymbol{x}=c\Leftrightarrow a_{1}x_{1}+\cdots
+a_{n}x_{n}=c
\end{equation*}であるため、\(H\left( \boldsymbol{a},c\right) \)は1本の1次方程式からなる連立1次方程式\begin{equation*}a_{1}x_{1}+\cdots +a_{n}x_{n}=c
\end{equation*}の解集合であり、ゆえに多面体です。
\vdots \\
H\left( \boldsymbol{a}_{m},c_{m}\right) =\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ \boldsymbol{a}_{1}\cdot \boldsymbol{x}=c_{m}\right\}
\end{gather*}を定義します。これらの共通部分\begin{equation}
H\left( \boldsymbol{a}_{1},c_{1}\right) \cap \cdots \cap H\left( \boldsymbol{a}_{m},c_{m}\right) \quad \cdots (1)
\end{equation}は連立1次方程式\begin{equation*}
\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}=c_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}=c_{m}\end{array}\right.
\end{equation*}の解集合であるため\(\left( 1\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 \mathbb{R} ^{n} \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{p} \\
-b_{1} \\
\vdots \\
-b_{p} \\
d_{1} \\
\vdots \\
d_{q}\end{pmatrix}\in \mathbb{R} ^{2p+q}
\end{eqnarray*}と定めれば、\begin{eqnarray*}
&&\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. \\
&\Leftrightarrow &\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. \\
&\Leftrightarrow &\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}\leq \left(
\begin{array}{c}
b_{1} \\
\vdots \\
b_{p} \\
-b_{1} \\
\vdots \\
-b_{p} \\
d_{1} \\
\vdots \\
d_{q}\end{array}\right) \\
&\Leftrightarrow &\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}\leq \left(
\begin{array}{c}
b_{1} \\
\vdots \\
b_{p} \\
-b_{1} \\
\vdots \\
-b_{p} \\
d_{1} \\
\vdots \\
d_{q}\end{array}\right) \\
&\Leftrightarrow &A\boldsymbol{x}\leq \boldsymbol{b}
\end{eqnarray*}が成り立つため、連立1式\(\left( 1\right) \)を行列不等式\begin{equation*}A\boldsymbol{x}\leq \boldsymbol{b}
\end{equation*}として表現できます。ただし、ここでの\(\leq \)はユークリッド空間\(\mathbb{R} ^{n}\)における標準的順序です。したがって、連立式\(\left( 1\right) \)の解集合もまた多面体\begin{equation*}P=\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ A\boldsymbol{x}\leq \boldsymbol{b}\right\}
\end{equation*}として表現できます。
多面体は凸集合
多面体は凸集合です。
ユークリッド空間上の集合\(P\subset \mathbb{R} ^{n}\)が多面体であるならば、\(P\)は凸集合である。
演習問題
\end{equation*}が多面体であることを証明してください。
\end{equation*}について、\begin{equation*}
A=\left\{ \boldsymbol{x}\in \mathbb{R} ^{2}\ |\ \left\Vert \boldsymbol{x}\right\Vert \leq 1\right\}
\end{equation*}が成り立つことを証明してください。
- 有界な多面体の具体例を挙げてください。
- 非有界な多面体の具体例を挙げてください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】