線形計画問題

概要

目的関数および制約条件が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} 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} $$

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} \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) 『最適化法』, 共立出版株式会社．

このページでは, 数式の表現に MathJax を利用しています.

このページでは, シンタックスハイライト(プログラムのコードに色を付ける機能)に Google Code Prettify を利用しています.

更新日: 2020/08/14

線形計画問題

概要

目次

定義

定式化

不等式標準形

等式標準形

解法

関連項目

参考文献