線形計画問題
概要
- 目的関数および制約条件が1次式で書かれた最適化問題
定義
最適化問題のうち, 以下の条件を満たすものを 線形計画問題(linear programming problem) という.
LP問題 ともいう.
- 全体集合 が \(n\)次元ユークリッド空間
- 制約条件 有限本の1次等式または1次不等式
- 目的関数 が 1次関数
線形計画問題 は次のように表記できる.
\[ \begin{aligned} x_{j} , a_{ij} , b_{i} , c_{j} \in \mathbb{R} \end{aligned} \]
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad &&\sum_{j=1}^{n} c_{j} x_{j} \in \mathbb{R} \\ \\ &\textbf{s.t.} \quad &&\sum_{j=1}^{n} a_{ij} x_{j} \leq b_{i} \, (i = 1, \cdots , k) \\ &&&\sum_{j=1}^{n} a_{ij} x_{j} = b_{i} \, (i = k + 1, \cdots , k + l) \end{aligned} \right. \end{aligned} \]
定式化
以下,
\[ \begin{aligned} x_{j} , a_{ij} , b_{i} , c_{j} \in \mathbb{R} \end{aligned} \]
とする.
最適化問題(最小化) は
\[ \begin{aligned} f : X \supset S \rightarrow \mathbb{R} \end{aligned} \]
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad f(x) \\ &\textbf{s.t.} \quad x \in S \\ \end{aligned} \right. \end{aligned} \]
と書けるので, 線形計画問題 は条件を順に書けば,
\[ \begin{aligned} &X = \mathbb{R} ^n \\ &S = \begin{Bmatrix} \left. \boldsymbol{x} = \left( \begin{array}{c} x_1 \\ \vdots \\ x_j \\ \vdots \\ x_n \end{array} \right) \in X \, \right| \, \begin{aligned} &\sum_{j=1}^{n} a_{ij} x_j \leq b_i \, (i = 1, \cdots , k) \\ &\sum_{j=1}^{n} a_{ij} x_j = b_i \, (i = k + 1, \cdots , k + l) \end{aligned} \end{Bmatrix} \\ &f : X \supset S \ni \boldsymbol{x} \longmapsto f( \boldsymbol{x} ) = \sum_{j=1}^{n} c_j x_j \in \mathbb{R} \\ &\left \Vert \quad \begin{aligned} &\textbf{min.} \quad f( \boldsymbol{x} ) \\ &\textbf{s.t.} \quad \boldsymbol{x} \in S \\ \end{aligned} \right. \end{aligned} \]
となる.
まとめて書けば,
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad f( \boldsymbol{x} ) = \sum_{j=1}^{n} c_j x_j \in \mathbb{R} \\ &\textbf{s.t.} \quad \boldsymbol{x} \in \begin{Bmatrix} \left. \boldsymbol{x} = \left( \begin{array}{c} x_1 \\ \vdots \\ x_j \\ \vdots \\ x_n \end{array} \right) \in X \, \right| \, \begin{aligned} &\sum_{j=1}^{n} a_{ij} x_j \leq b_i \, (i = 1, \cdots , k) \\ &\sum_{j=1}^{n} a_{ij} x_j = b_i \, (i = k + 1, \cdots , k + l) \end{aligned} \end{Bmatrix} \end{aligned} \right. \end{aligned} \]
つまり, 線形計画問題 は以下で書ける.
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad &&\sum_{j=1}^{n} c_{j} x_{j} \in \mathbb{R} \\ \\ &\textbf{s.t.} \quad &&\sum_{j=1}^{n} a_{ij} x_{j} \leq b_{i} \, (i = 1, \cdots , k) \\ &&&\sum_{j=1}^{n} a_{ij} x_{j} = b_{i} \, (i = k + 1, \cdots , k + l) \end{aligned} \right. \end{aligned} \]
不等式標準形
以下の形の線形計画問題を不等式標準形という.
\[ \begin{aligned} x_{j} , a_{ij} , b_{i} , c_{j} \in \mathbb{R} \end{aligned} \]
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad &&\sum_{j=1}^{n} c_{j} x_{j} \in \mathbb{R} \\ \\ &\textbf{s.t.} \quad &&\sum_{j=1}^{n} a_{ij} x_{j} \geq b_{i} \, (i = 1, \cdots , m) \\ &&&x_{j} \geq 0 \, (j = 1, \cdots , n) \end{aligned} \right. \end{aligned} \]
\(\boldsymbol{x}\) , \(C\) , \(B\) , \(A\) を
\[ \begin{aligned} &\boldsymbol{x} = \left( \begin{array}{c} x_{1} \cdots x_{j} \cdots x_{n} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^n \\ &C = \left( \begin{array}{c} c_{1} \cdots c_{j} \cdots c_{n} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^n \\ &B = \left( \begin{array}{c} b_{1} \cdots b_{i} \cdots b_{m} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^m \\ &A = \left( \begin{array}{ccccc} a_{11} & \cdots & a_{1j} & \cdots & a_{1n} \\ \vdots && \vdots && \vdots \\ a_{i1} & \cdots & a_{ij} & \cdots & a_{in} \\ \vdots && \vdots && \vdots \\ a_{m1} & \cdots & a_{mj} & \cdots & a_{mn} \\ \end{array} \right) \in \mathbb{R} ^ {m \times n} \end{aligned} \]
とすると,
\[ \begin{aligned} C ^\mathrm{T} \boldsymbol{x} &= \left( \begin{array}{c} c_{1} \cdots c_{j} \cdots c_{n} \end{array} \right) \left( \begin{array}{c} x_{1} \\ \vdots \\ x_{j} \\ \vdots \\ x_{n} \end{array} \right) \\ \\ &= \sum_{j=1}^{n} c_{j} x_{j} \end{aligned} \]
であり,
\[ \begin{aligned} A \boldsymbol{x} &= \left( \begin{array}{ccccc} a_{11} & \cdots & a_{1j} & \cdots & a_{1n} \\ \vdots && \vdots && \vdots \\ a_{i1} & \cdots & a_{ij} & \cdots & a_{in} \\ \vdots && \vdots && \vdots \\ a_{m1} & \cdots & a_{mj} & \cdots & a_{mn} \\ \end{array} \right) \left( \begin{array}{c} x_{1} \\ \vdots \\ x_{j} \\ \vdots \\ x_{n} \end{array} \right) \\ \\ &= \left( \begin{array}{c} \sum_{j=1}^{n} a_{1j} x_{j} \\ \vdots \\ \sum_{j=1}^{n} a_{ij} x_{j} \\ \vdots \\ \sum_{j=1}^{n} a_{mj} x_{j} \end{array} \right) \end{aligned} \]
より,
不等式標準形は
\[ \begin{aligned} &\boldsymbol{x} = \left( \begin{array}{ccc} x_{1} & \cdots & x_{n} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^n \\ &C = \left( \begin{array}{ccc} c_{1} & \cdots & c_{n} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^n \\ &B = \left( \begin{array}{ccc} b_{1} & \cdots & b_{m} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^m \\ &A = \left( \begin{array}{c} a_{ij} \end{array} \right) \in \mathbb{R} ^ {m \times n} \end{aligned} \]
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad &&f(x) = C ^\mathrm{T} \boldsymbol{x} \\ &\textbf{s.t.} \quad &&A \boldsymbol{x} \geq B \\ &&&\boldsymbol{x} \geq \boldsymbol{0} \end{aligned} \right. \end{aligned} \]
と書ける.
ただし,
\[ \begin{aligned} &\boldsymbol{0} = \left(\begin{array}{c} 0 \cdots 0 \end{array}\right) : \text{zero vector} \\ &\boldsymbol{u} = (\cdots u_i \cdots)^\mathrm{T} \geq (\cdots v_i \cdots)^\mathrm{T} = \boldsymbol{v} \overset{\text{def.}}{\Longleftrightarrow} ^\forall i , u_i \geq v_i \end{aligned} \]
とする.
等式標準形
以下の形の線形計画問題を等式標準形という.
\[ \begin{aligned} x_{j} , a_{ij} , b_{i} , c_{j} \in \mathbb{R} \end{aligned} \]
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad &&\sum_{j=1}^{n} c_{j} x_{j} \in \mathbb{R} \\ \\ &\textbf{s.t.} \quad &&\sum_{j=1}^{n} a_{ij} x_{j} = b_{i} \, (i = 1, \cdots , m) \\ &&&x_{j} \geq 0 \, (j = 1, \cdots , n) \end{aligned} \right. \end{aligned} \]
不等式標準形と同様に,
\[ \begin{aligned} &\boldsymbol{x} = \left( \begin{array}{ccc} x_{1} & \cdots & x_{n} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^n \\ &C = \left( \begin{array}{ccc} c_{1} & \cdots & c_{n} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^n \\ &B = \left( \begin{array}{ccc} b_{1} & \cdots & b_{m} \end{array} \right) ^ \mathrm{T} \in \mathbb{R} ^m \\ &A = \left( \begin{array}{c} a_{ij} \end{array} \right) \in \mathbb{R} ^ {m \times n} \end{aligned} \]
\[ \begin{aligned} \left \Vert \quad \begin{aligned} &\textbf{min.} \quad &&f(x) = C ^\mathrm{T} \boldsymbol{x} \\ &\textbf{s.t.} \quad &&A \boldsymbol{x} = B \\ &&&\boldsymbol{x} \geq \boldsymbol{0} \end{aligned} \right. \end{aligned} \]
と書ける.
解法
線形計画問題は, 単体法や内点法を用いて解くことができる.
関連項目
- 最適化問題
- 単体法(シンプレックス法)
- 内点法
参考文献
- 田村明久・村松正和 (2018) 『最適化法』, 共立出版株式会社．