---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第2回：線形計画問題(1) 標準形
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：
<code style="font-size:20pt">https://hackmd.io/@nagae/OptMech_2021-Ch01</code>

</div>

# リア充問題
- Aくんは彼女ができたばかり． ==**1日8時間**== ある自由な時間を, **バイト** と **デート** に振り分ける.
- バイトすると ==**1時間あたり800円**== の**収入**に,デートすると ==**1時間あたり400円**== の **支出** になる.
- Aくんの仕送りから家賃・食費などの生活費を除くと**リア充資金** として ==**1 日あたり 800 円**== を充当できる.
- バイトもデートも**体力**を消耗する.Aくんの体力はバイトだけなら ==**1日9時間分**==, デートだけなら ==**1日6時間分**== ある.
- Aくんはバイトからもデートからも充実感が得られるが，で きたばかりの彼女と過ごす時間の方が，バイトの時間よりも 充実感を味わえる. そこで, 1 時間あたりの充実感の比率を ==**バイト:デート = 1:2**== とする.
- リア充資金とバイト給料でデート代を賄いつつ, ==**最も充実した生活**== を送るには 1日あたりバイトとデートを何時間づつすればよいだろう?
## 定式化
最適化問題の構成要素
### 未知変数(variables)と非負制約(non-negativity constraint)
求めたいのは最適なバイトとデートの時間．それぞれ, $x_{1}, x_{2}$とする．これらは，いずれも非負でなければならない．
$$
x_{1}, x_{2} \geq 0
$$
### 制約条件(constraints)
バイト時間とデート時間の組$(x_{1}, x_{2})$は，**時間**，**予算**，**体力**の制約を満たす中でしか選べない．

#### 時間制約(time constraint)
バイト時間とデート時間の合計は8時間を超えてはいけない
$$
x_{1} + x_{2} \leq 8
$$

#### 予算制約(budget constraint)
「バイトの収入とリア充資金の合計」が「デートへの支出」以上でなければいけない:
$$
800 x_{1} + 800 \geq 400 x_{2}
$$
両辺を 400 で割って整理すれば，
$$
-2 x_{1} + x_{2} \leq 2
$$

#### 体力制約(physical constraint)
1日の体力が「バイト9時間分」もしくは「デート6時間分」なので, バイトとデートの時間の組 $(x_1, x_2)$ は $(x_1, x_2) = (9, 0)$ と$(x_1, x_2) = (0, 6)$ を結ぶ直線を超えてはいけない:
$$
2x_{1} + 3 x_{2} \leq 18
$$

### 目的関数 (objectives)
バイト時間とデート時間のそれぞれに充実感の比率を乗じた和(=充実度)を最大化したい：
$$
Z(x_{1}, x_{2}) := x_{1} + 2 x_{2}
$$

## 線形計画問題として定式化されたリア充問題
$$
\begin{alignat}{3}
\max_{x_{1}, x_{2}} \quad & x_{1} + 2x_{2} &&\quad& \text{(目的関数)}\\
\text{s.t.} \quad
& x_{1} + x_{2} &\leq 8 && \text{(時間制約)}\\
& - 2x_{1} + x_{2} &\leq 2 && \text{(予算制約)}\\
& 2x_{1} + 3x_{2} &\leq 18 && \text{(体力制約)}\\
& x_{1}, x_{2} &\geq 0 && \text{(非負制約)}
\end{alignat}
$$
s.t. は *subject to* の略．

:::info
**線形計画問題** (LP: *linear programming*):
目的関数が未知変数に対して **線形** で，制約条件が未知変数の **線形不等式** で表される.
:::

## 幾何学的イメージ
### 許容領域
下図において，緑色で塗り潰された領域は，3つの制約条件と非負制約の全てを満たす ==**許容領域(feasible set)**== を表す．

下図において，青い点線は，目的関数$Z(x_{1},x_{2})=x_{1}+2x_{2}$の ==**等高線**== を表す．目的関数の等高線は，ベクトル $\begin{bmatrix}1 \\2\end{bmatrix}$ を法線とする直線で， *原点方向(左下)に向かうほど目的関数は小さく，逆方向(右上)に向かうほど目的関数は大きくなる*．

==**最適解**==(i.e. 緑色の領域内で最も原点から遠い等高線が通る点)は，$(x_{1}^{\ast}, x_{2}^{\ast}) = (\frac{3}{2}, 5)$であり，その時の目的関数値(==**最適値**==)は，$Z(x_{1}^{\ast}, x_{2}^{\ast}) = 11.5$である．

# 線形計画問題の例
## 1. 食生活問題
4種類の栄養素$N_{1}, N_{2}, N_{3}, N_{4}$を，3種類の食材$F_{1}, F_{2}, F_{3}$ から摂取したい．
- 栄養素 $N_{j}$の1日あたりの ==**必要摂取量**== は定数$c_{j}$ で表される($j=1,2,3,4$)
- 食材 $F_{i}$ 1単位あたりの ==**価格**== は定数$b_{i}$ で表される($i=1,2,3$)
- 食材 $F_{i}$ 1単位から摂取できる栄養素$N_{j}$の量は定数$a_{ij}$で表される．

| 問題： ==**最も安価**== に全ての栄養素を ==**必要な量だけ摂取**== するには，==**どの食材を何単位づつ**== 購入すればよいか? |
|---|

- 未知変数: $y_{1}, y_{2}, y_{3}$ を， それぞれ， 食材$F_{1}, F_{2}, F_{3}$の購入量とする
- 目的関数: 最小化すべき食材購入費は以下の式で表される：
$$Z(y_{1}, y_{2}, y_{3}) = y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3}
$$
- 制約条件：$y_{i}$単位の食材$F_{i}$からできる栄養素$N_{j}$の量は$y_{i} a_{ij}$であるから，必要摂取量$c_{j}$を満たすための条件は， 以下の式で表される:
$$
y_{1} a_{1j} + y_{2} a_{2j} + y_{3} a_{3j} \geq c_{j} \qquad \forall j = 1, 2, 3, 4.
$$
- 非負制約：食材の購入量は非負なので，
$$
y_{1}, y_{2}, y_{3} \geq 0
$$

これより，食生活問題は，以下の線形計画問題として定式化できる：
$$
\begin{alignat}{3}
\min_{y_{1}, y_{2}, y_{3}} \quad & y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3} &&&&\text{(目的関数)}\\
\text{s.t.} \quad
& y_{1} a_{11} + y_{2} a_{21} + y_{3} a_{31} &&\geq c_{1} \quad &&\text{(栄養素$N_{1}$の摂取量制約)}\\
& y_{1} a_{12} + y_{2} a_{22} + y_{3} a_{32} &&\geq c_{2} &&\text{(栄養素$N_{2}$の摂取量制約)}\\
& y_{1} a_{13} + y_{2} a_{23} + y_{3} a_{33} &&\geq c_{3} &&\text{(栄養素$N_{3}$の摂取量制約)}\\
& y_{1} a_{14} + y_{2} a_{24} + y_{3} a_{34} &&\geq c_{4} &&\text{(栄養素$N_{4}$の摂取量制約)}\\
&y_{1}, y_{2}, y_{3} &&\geq 0&&\text{(非負制約)}
\end{alignat}
$$

## 2. 輸送問題
3箇所の生産地$P_{1}, P_{2}, P_{3}$から4箇所の消費地$M_{1}, M_{2}, M_{3}, M_{4}$ までガソリンを輸送したい．
- 生産地$P_{i}$から供給できるガソリンの量は定数$s_{i}$で表される$(i=1,2,3)$
- 消費地$M_{j}$で必要とされるガソリンの量は定数$r_{j}$で表される$(j=1,2,3,4)$
- 生産地$P_{i}$から消費地$M_{j}$までのガソリン1単位あたりの輸送費用は定数$b_{ij}$で表される．

| 問題： ==**最も安価**== に，各生産地の ==**供給能力内**== で ==**全ての消費地で必要とされる量を賄う**== には， ==**どの生産地からどの消費地に何単位**== のガソリンを運べばよいか?
|---|

- 未知変数: $y_{ij}$を生産地$P_{i}$から消費地$M_{j}$までの輸送量とする．$\mathbf{y} = (y_{ij}: i = 1, 2, 3, j = 1, 2, 3, 4)$ とする．
- 目的関数: 最小化すべき総輸送費用は，以下の式で表される：
$$
Z(\mathbf{y}) = \sum_{i=1}^{3}\sum_{j=1}^{4} y_{ij} b_{ij}
$$
- 制約条件(1)： 生産地$P_{i}$から運び出されるガソリンの量は $y_{i1} + y_{i2} + y_{i3} + y_{i4} = \sum_{j=1}^{4} y_{ij}$ であり，これが生産地$P_{i}$からの供給量$s_{i}$を上回ってはいけないから，
$$
\sum_{j=1}^{4} y_{ij} \leq s_{i} \qquad \forall i = 1, 2, 3
$$
- 制約条件(2): 消費地$M_{j}$に運び込まれるガソリンの量は
$y_{1j} + y_{2j} + y_{3j} = \sum_{i=1}^{3} y_{ij}$ であり，これが消費地$M_{j}$での需要量$r_{j}$を下回ってはいけないから，
$$
\sum_{i=1}^{3} y_{ij} \geq r_{j} \qquad \forall j = 1, 2, 3, 4
$$
- 非負制約：輸送量は非負なので，
$$
y_{ij} \geq 0 \quad \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4
$$

これより，輸送問題は，以下の線形計画問題として定式化できる：
$$
\begin{alignat}{3}
\min_{\mathbf{y}} \quad &\sum_{i=1}^{3} \sum_{j=1}^{4} y_{ij} b_{ij} &&&&\text{(目的関数)}\\
\text{s.t.} \quad
& \sum_{j=1}^{4} y_{ij} \leq s_{i} && \forall i = 1, 2, 3 \quad && \text{(生産地$P_{i}$の供給制約)} \\
& \sum_{i=1}^{3} y_{ij} \geq r_{j} && \forall j = 1, 2, 3, 4 \quad && \text{(消費地$M_{j}$の需要制約)}
\\
& y_{ij} \geq 0 && \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4 \quad && \text{(非負制約)}
\end{alignat}
$$

## 3. 割当問題
$N$人の学生に$M$個の研究テーマを割り当てたい．
- それぞれの学生 $i=1, 2, \cdots, N$ には，たかだか1つのテーマしか割り当てられない．
- それぞれのテーマ $j=1, 2, \cdots, M$ には，たかだか1人の学生しか割り当てられない．
- 学生$i$が研究テーマ $j$ に従事した時の生産量(論文の本数)は定数$c_{ij}$ で表される．

| 問題： ==**総生産量を最大化**== するには， ==**どの学生にどの研究テーマを**== 割り当てればよいか?
|---|

- 未知変数: $x_{ij}$を，研究テーマ$j$の学生$i$への「割り当て」とする． 本来なら$x_{ij}$ は0か1のいずれかを離散的に取る変数(二値変数)であるが， ここでは$[0,1]$の範囲内の任意の実数値を取り得る連続変数として取り扱う．
- 目的関数： 最大化すべき総生産量は，
$$
Z(\mathbf{x}) = \sum_{i=1}^{N} \sum_{j=1}^{M} c_{ij} x_{ij}
$$
- 制約条件(1): 学生$i$に割り当てられる研究テーマの総数は $x_{i1} + x_{i2} + \cdots + x_{iM} = \sum_{j=1}^{M} x_{ij}$ であり，各学生にはたかだか1つの研究テーマしか割り当てられないから，
$$
\sum_{j=1}^{M} x_{ij} \leq 1 \quad \forall i = 1, 2, \cdots, N.
$$
- 制約条件(2): 研究テーマ$j$ に割り当てられる学生の総数は
$x_{1j} + x_{2j} + \cdots + x_{Nj} = \sum_{i=1}^{N} x_{ij}$ であり，各研究テーマにはたかだか1人の学生しか割り当てられないから，
$$
\sum_{i=1}^{N} x_{ij} \leq 1 \quad \forall j = 1, 2, \cdots, M.
$$
- 非負制約： 割当は非負なので，
$$
x_{ij} \geq 0 \qquad \forall i = 1, 2, \cdots, N, \, \forall j = 1, 2, \cdots, M.
$$

これより，割当問題は，以下の線形計画問題として定式化できる：
$$
\begin{alignat}{3}
\max_{\mathbf{x}} \quad &\sum_{i=1}^{N} \sum_{j=1}^{M} c_{ij} x_{ij} &&&&\text{(目的関数)}\\
\text{s.t.} \quad
& \sum_{j=1}^{N} x_{ij} \leq 1 && \forall i = 1, 2, \cdots, N \quad && \text{(学生$i$への割当上限)} \\
& \sum_{i=1}^{N} x_{ij} \leq 1 && \forall j = 1, 2, \cdots, M \quad && \text{(研究テーマ$j$への割当上限)}
\\
& x_{ij} \geq 0 && \forall i = 1, 2, \cdots, N\, \forall j = 1, 2, \cdots, M\quad && \text{(非負制約)}
\end{alignat}
$$

:::success
割当問題は，その最適解 $x_{ij}^{\ast}$ が **0か1のいずれかになる** (常に離散解が得られる)ことが保証されている．
:::

# 標準形とベクトル・行列表現
## 線形計画問題の分類
- 目的関数: 最大化 or 最小化
- 未知変数: 非負制約あり or 非負制約なし
- 制約条件: 線形式 $\leq$ 定数 or 線形式 $=$ 定数 or 線形式 $\geq$ 定数

特定の組み合わせに限定されない**システマティック**な分析・解法が欲しい → 標準形

## 標準形
任意の線形計画問題を ==**同一の形式**== で記述でき，問題の性質(解の存在や双対性)の分析や解法の開発をシステマティックに行える：

- ==**不等式標準形**==(標準最大化/標準最小化)
→ 双対問題の導出に便利
- ==**等式標準形**==
→ 単体法(数値解法)の開発に便利

# 標準最大化問題
$N$ 個の未知変数$x_{1}, x_{2}, \cdots, x_{N}$ を用いて，$M$本の不等式制約条件を満足しながら，目的関数を最大化する．
$$
\begin{array}{rcccccccccc}
\displaystyle\max_{x_{1}, x_{2}, \cdots, x_{N}} &c_{1} x_{1}& + &c_{2} x_{2}& +&\cdots& +&c_{N} x_{N}\\
\text{s.t.}
& a_{11} x_{1} &+& a_{12} x_{2} &+& \cdots &+& a_{1N} x_{N} &\leq& b_{1}\\
& a_{21} x_{1} &+& a_{22} x_{2} &+& \cdots &+& a_{2N} x_{N} &\leq& b_{2}\\
& \vdots & & \vdots & & \ddots & & \vdots & & \vdots\\
& a_{{M}1} x_{1} &+& a_{{M}2} x_{2} &+& \cdots &+& a_{{M}N} x_{N} &\leq& b_{M}\\
& x_{1}, & & x_{2}, & & \cdots & & x_{N} & \geq & 0
\end{array}
$$

## 標準最大化問題のベクトル・行列表現
### 目的関数
標準最大化問題の目的関数は，2つのN次元列ベクトル
$$
\mathbf{x} =
\begin{bmatrix}
x_{1} \\ x_{2} \\ \vdots \\ x_{N}
\end{bmatrix}
, \quad
\mathbf{c} =
\begin{bmatrix}
c_{1} \\ c_{2} \\ \vdots \\ c_{N}
\end{bmatrix}
$$
を用いて，
$$
c_{1} x_{1} + c_{2} x_{2} +\cdots +c_{N} x_{N} = \sum_{i=1}^{N} c_{i} x_{i} = \mathbf{c}^{\top} \mathbf{x}
$$
と表せる． ただし，${}^{\top}$は行列・ベクトルの転置を表す記号．

### $j$ 番目不等式制約
$j (=1, \cdots, M)$本目の不等式制約は, $N$次元 行ベクトル$\mathbf{a}_{j}$:
$$
\mathbf{a}_{j} = \begin{bmatrix}
a_{j1} & a_{j2} & \cdots &a_{jN}
\end{bmatrix}
$$
を用いて
$$
a_{j1} x_{1} + a_{j2} x_{2} + \cdots + a_{jN} x_{N} = \sum_{i=1}^{N} a_{ji} x_{i} = \mathbf{a}_{j} \mathbf{x} \leq b_{j}
$$
と表せれる．

さらに，$M\times{N}$行列$\mathbf{A}$ および$M$次元列ベクトル:
$$
\mathbf{A} = \begin{bmatrix}
\mathbf{a}_{1} \\ \vdots \\ \mathbf{a}_{M}
\end{bmatrix}
= \begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1N} \\
\vdots & \vdots & \ddots & \vdots \\
a_{M1} & a_{M2} & \cdots & a_{MN}
\end{bmatrix}
, \mathbf{b} = \begin{bmatrix}
b_{1} \\ \vdots \\ b_{M}
\end{bmatrix}
$$
を用いれば，不等式制約全体を以下のようにベクトル・行列表現できる：
$$
\begin{bmatrix}
a_{11}x_{1} + a_{12} x_{2} + \cdots + a_{1N} x_{N}\\
\vdots \\
a_{M1}x_{1} + a_{M2} x_{2} + \cdots + a_{MN} x_{N}
\end{bmatrix}
= \begin{bmatrix}
\mathbf{a}_{1} \mathbf{x} \\
\vdots\\
\mathbf{a}_{M} \mathbf{x}
\end{bmatrix} = \mathbf{A} \mathbf{x} \leq \mathbf{b}
$$

### 非負制約
非負制約は，全ての要素が0の$N$次元列ベクトル$\mathbf{0}$ を用いて，
$$
\mathbf{x} \geq \mathbf{0}
$$
と表せる．

## 標準最大化問題のベクトル・行列表現
結局，標準最大化問題は，
- $M\times{}N$行列 $\mathbf{A}$
- $M$次元列ベクトル $\mathbf{b}$
- $N$次元列ベクトル $\mathbf{c}$

を与件(定数)とし，未知変数を
- $N$次元列ベクトル $\mathbf{x}$

とする以下の問題として表現できる．

$$
\begin{align*}
\max_{\mathbf{x}} \quad &\mathbf{c}^{\top}\mathbf{x} \\
\text{s.t.} \quad &
\mathbf{A} \mathbf{x} \leq \mathbf{b} \\
&\mathbf{x} \geq \mathbf{0}
\end{align*}
$$

より簡潔に
$$
\max_{\mathbf{x}} \left\{\left.
\mathbf{c}^{\top} \mathbf{x} \right|
\mathbf{A} \mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}
\right\}
$$
と表すこともある.

# 標準最小化問題
$M$ 個の未知変数$y_{1}, y_{2}, \cdots, y_{M}$ を用いて，$N$本の不等式制約条件を満足しながら，目的関数を最小化する．
$$
\begin{array}{rcccccccccc}
\displaystyle\min_{y_{1}, y_{2}, \cdots, y_{M}} &y_{1} b_{1}& + &y_{2} b_{2}& +&\cdots& +&y_{M} b_{M}\\
\text{s.t.}
& y_{1} a_{11} &+& y_{2} a_{21} &+& \cdots &+& y_{M} a_{{M}1} &\geq& c_{1}\\
& y_{1} a_{12} &+& y_{2} a_{22} &+& \cdots &+& y_{M} a_{{M}2} &\geq& c_{2}\\
& \vdots & & \vdots & & \ddots & & \vdots & & \vdots\\
& y_{1} a_{1{N}} &+& y_{2} a_{2{N}} &+& \cdots &+& y_{M} a_{{M}{N}} &\geq& c_{N}\\
& y_{1}, & & y_{2}, & & \cdots & & y_{M} & \geq & 0
\end{array}
$$

## 標準最小化問題のベクトル・行列表現
未知変数を$M$次元列ベクトル$\mathbf{y} = \begin{bmatrix}y_{1}\\\vdots\\y_{M}\end{bmatrix}$とすれば，標準最小化問題の不等式制約は，
$$
\mathbf{a}_{1}^{\top} y_{1} + \mathbf{a}_{2}^{\top} y_{2} + \cdots + \mathbf{a}_{M}^{\top} y_{M} = \mathbf{A}^{\top} \mathbf{y} \geq \mathbf{c}
$$
と書ける． 従って，標準最小化問題は，ベクトル・行列を用いて
$$
\begin{align*}
\min_{\mathbf{y}} \quad &\mathbf{y}^{\top}\mathbf{b} \\
\text{s.t.} \quad &
\mathbf{A}^{\top} \mathbf{y} \geq \mathbf{c} \\
&\mathbf{y} \geq \mathbf{0}
\end{align*}
$$
と表せる． より簡潔に
$$
\min_{\mathbf{y}} \left\{\left.
\mathbf{y}^{\top} \mathbf{b} \right|
\mathbf{A}^{\top} \mathbf{y} \geq \mathbf{c}, \mathbf{y} \geq \mathbf{0}
\right\}
$$
と表すこともある.

# 不等式標準形(標準最大化問題)への変換
任意の問題は不等式標準形に変換できる．たとえば，次の問題:
$$
\begin{align*}
\min_{x_{1}, x_{2}, x_{3}} & x_{1} + 3 x_{2} + 2x_{3}\\
\text{s.t.} & x_{1} + x_{2} = 2\\
& 2 x_{1} + x_{3} \geq x_{2} + 3 \\
& x_{1}, x_{2} \geq 0 \\
& x_{3} \text{ is free (正でも負でもよい)}
\end{align*}
$$
は，以下の手順で標準最大化問題に変換できる．

1) 最小化問題は，目的関数の全ての係数に$-1$を乗じることで最大化問題に置き換える：

$$
\min_{x_{1}, x_{2}, x_{3}} x_{1} + 3 x_{2} + 2 x_{3} \Rightarrow
\max_{x_{1}, x_{2}, x_{3}} - x_{1} - 3 x_{2} - 2 x_{3}
$$

2) 等式制約は，==**線形式=定数**== の形に揃えた後， ==**線形式$\leq$定数**== と ==**線形式$\geq$定数**== なる2つの不等式に置き換える：

$$
x_{1} + x_{2} = 2 \Rightarrow \begin{cases}
x_{1} + x_{2} \leq 2 \\
x_{1} + x_{2} \geq 2
\end{cases}
$$

3) 不等式制約は ==**線形式$\leq$定数**== の形に揃える：

$$
\begin{align*}
2 x_{1} + x_{3} \geq x_{2} + 3 &\Rightarrow -2x_{1} + x_{2} - x_{3} \leq -3\\
x_{1} + x_{2} \geq 2 &\Rightarrow -x_{1} - x_{2} \leq -2
\end{align*}
$$

4) 非負制約のない未知変数は，非負なる2つの未知変数を導入し，その差で置き換える． ここでは， 非負なる2つの未知変数$x_{3}^{+}, x_{3}^{-} \geq 0$を新たに導入し，正負どちらでもよい未知変数$x_{3}$を,$x_{3}^{+}-x_{3}^{-}$で置き換える．

$$
\begin{array}{rl}
\displaystyle \max_{x_{1}, x_{2}, x_{3}} &-x_{1}-3x_{2}-2x_{3}\\
\text{s.t.} & x_{1} + x_{2} \leq 2 \\
&-x_{1}-x_{2} \leq -2 \\
&-2x_{1}+x_{2}-x_{3} \leq -3 \\
&x_{1}, x_{2} \geq 0 \\
&x_{3} \text{ is free}
\end{array}
\Rightarrow
\begin{array}{rl}
\displaystyle \max_{x_{1}, x_{2}, \color{red}{x_{3}^{+}, x_{3}^{-}}} &-x_{1}-3x_{2}-
2\color{red}{\left(x_{3}^{+}-x_{3}^{-} \right)}\\
\text{s.t.} & x_{1} + x_{2} \leq 2 \\
&-x_{1}-x_{2} \leq -2 \\
&-2x_{1}+x_{2}-\color{red}{\left(x_{3}^{+}-x_{3}^{-}\right)} \leq -3 \\
&x_{1}, x_{2}, \color{red}{x_{3}^{+}, x_{3}^{-}} \geq 0
\end{array}
$$

# 練習(提出の必要はありません)
輸送問題を標準最大化問題に変換しなさい．