---
# System prepended metadata

title: '2022年度 交通社会システム論<br>第2回：線形計画問題(1) 標準形<br>Mangament of Transpotation Networks in Social Systems - Linear Programming(1): Standard Form'
tags: [' lecture', ' linear programming', MTNS-2022]

---

---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第2回：線形計画問題(1) 標準形<br>Mangament of Transpotation Networks in Social Systems - Linear Programming(1): Standard Form
[ポータルへ戻る | Back to Portal](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：
You can access to this page via the following QR code or URL:
![](https://i.imgur.com/syx5ohA.png =200x)

<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch01</code>

</div>

# リア充問題 | How Mr. Adam can be happy?

- Aくんは彼女ができたばかり． ==**1日8時間**== ある自由な時間を, **バイト** と **デート** に振り分ける. 
- バイトすると ==**1時間あたり800円**== の**収入**に,デートすると ==**1時間あたり400円**== の **支出** になる. 
- Aくんの仕送りから家賃・食費などの生活費を除くと**リア充資金** として ==**1 日あたり 800 円**== を充当できる. 
- バイトもデートも**体力**を消耗する.Aくんの体力はバイトだけなら ==**1日9時間分**==, デートだけなら ==**1日6時間分**== ある. 
- Aくんはバイトからもデートからも充実感が得られるが，で きたばかりの彼女と過ごす時間の方が，バイトの時間よりも 充実感を味わえる. そこで, 1 時間あたりの充実感の比率を ==**バイト:デート = 1:2**== とする. 
- リア充資金とバイト給料でデート代を賄いつつ, ==**最も充実した生活**== を送るには 1日あたりバイトとデートを何時間づつすればよいだろう?

---
- Mr. Adam just got a new girflriend and wants to make his life rich and happy by assigning his free ==**8 hours**== per day to **part-time work** and **dating**.
- Working part-time yields **800 JPY** per hour, while datng costs **400 JPY** per hour.
- He has an endowment fund for his activity as **800 JPY** per day.
- Both of part-time job and dating are physically demanding. Mr. Adam's physical strength is equivalent to **9 hours part-time job** or **6 hours dating.**
- Although Mr. Adam can feel fulfilled from either part-time job or dating, he feels more fulfilled by spending time with his girlfriend. We assume that the hapiness of spending one hour on the date is ==**twice**== as much as that of spending one our on a part-time job.
## 定式化 | Formulation
最適化問題の構成要素:
Components of optimization problems:
1. 未知変数 | (unknown) variables 
2. 制約条件 | constraints
3. 目的関数 | objective function

### 未知変数(variables)と非負制約(non-negativity constraint)
求めたいのは最適なバイトとデートの時間．それぞれ, $x_{1}, x_{2}$とする．これらは，いずれも非負でなければならない．

Let $x_{1}$ be the time for part-time job per day, as well as $x_{2}$ be the time for date per day. Each should be non-negative.
  $$
  x_{1}, x_{2} \geq 0
  $$
### 制約条件(constraints)
バイト時間とデート時間の組$(x_{1}, x_{2})$は，**時間**，**予算**，**体力**の制約を満たす中でしか選べない．
The pair of variables $(x_{1}, x_{2})$ should satisfy the following three constraints:

#### 時間制約 (time constraint)
バイト時間とデート時間の合計は8時間を超えてはいけない:
The sum of times for part-time working and dating must not exceed 8 hours per day:
$$
x_{1} + x_{2} \leq 8
$$
  
#### 予算制約 (budget constraint)
「バイトの収入とリア充資金の合計」が「デートへの支出」以上でなければいけない:
The sum of part-time income and the endowment fund must be equal to or greater than the expenditure for dating:
$$
800 x_{1} + 800 \geq 400 x_{2}
$$
両辺を 400 で割って整理すれば，
A straightforward mathematic yields:
$$
-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)$ を結ぶ直線を超えてはいけない:
The time allocation $(x_{1}, x_{2})$ must not exceed the line between $(x_{1}, x_{2}) = (9,0)$ and $(x_{1}, x_{2}) = (0,6)$:
$$
2x_{1} + 3 x_{2} \leq 18
$$
  
### 目的関数 (objectives)
バイト時間とデート時間のそれぞれに充実感の比率を乗じた和(=充実度)を最大化したい：
Mr. Adam wants to maximize his happiness, which is a weighted-sum of spending times for his activities:
$$
Z(x_{1}, x_{2}) := x_{1} + 2 x_{2}
$$

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

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

A mathematical programming with linear objective and liner constraints.
:::

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

The feasible set of the variable $(x_{1}, x_{2})$ is represented by the green area. This is the intersection of five areas, each of which corresponds to a linear inequality (3 constraints and 2 non-negativity constraints).
![](https://i.imgur.com/YqkjRbf.png )

下図において，青い点線は，目的関数$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$である．

The blue dotted lines in the following picture contour lines of the objective function, $Z(x_{1}, x_{2})=x_{1}+2x_{2}$. These lines are orthogonal to the vector $\begin{bmatrix}1 \\2\end{bmatrix}$. The objective value is smaller toward the origin (lower left) and larger toward the opposite direction (upper right).

The ==**optimal solution**== (i.e. the farthest point from the origin in the green area) is $(x_{1}^{\ast}, x_{2}^{\ast}) = (\frac{3}{2}, 5)$ and the ==**optimal value**== is $Z(x_{1}^{\ast}, x_{2}^{\ast}) = 11.5$.

![](https://i.imgur.com/61UmshR.png)




# 線形計画問題の例 | Some Examples of LP.
## 1. 食生活問題 | A Diet Problem
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}$で表される．

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

- 未知変数: $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}
$$

---

Suppose that you want to obtain four nutrients, $N_{1}, N_{2}, N_{3}$ and $N_{4}$ from three different foods, $F_{1}, F_{2}$ and $F_{3}$. It is also assumed that
- The required intake of nutrient $N_j$ is denoted by a given constant $c_j$ ($j=1,2,3,4$).
- The price per unit of food $F_i$ is denoted by a given constant $b_i$ ($i=1,2,3$).
- The amount of nutrient Nj that can be obtained from one unit of food $F_{i}$ is denoted by a given constant $a_{ij}$ ($i=1,2,3$ and $j=1,2,3,4$).

::: warning
**Diet Problem**: How many of each food should you buy to get the required amount of all nutrients at the lowest cost? 
:::

- **Variables**: Let $y_{1}, y_{2}$ and $y_{3}$ be the amount of foods $F_{1}, F_{2}$ and $F_{3}$, respectively.
- **Objective**: The total expenditure to be minimized is:
$$Z(y_{1}, y_{2}, y_{3}) = y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3}
$$
- **Constraints**: Since the amount of nutrient $N_{j}$ from $y_{i}$ food $F_{i}$ is $y_{i} a_{ij}$, the required intake of nutrient $N_{j}$ is denoted by
$$
  y_{1} a_{1j} + y_{2} a_{2j} + y_{3} a_{3j} \geq c_{j} \qquad \forall j = 1, 2, 3, 4.
$$
The amount of each food can not be negative:
$$
y_{1}, y_{2}, y_{3} \geq 0.
$$

Accordingly, the diet problem can be formulated as the following LP:
$$
\begin{alignat}{3}
\min_{y_{1}, y_{2}, y_{3}} \quad & y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3} &&&&\text{(total expenditure)}\\
\text{s.t.} \quad 
& y_{1} a_{11} + y_{2} a_{21} + y_{3} a_{31} &&\geq c_{1} \quad &&\text{(required intake of nutrient $N_{1}$)}\\
& y_{1} a_{12} + y_{2} a_{22} + y_{3} a_{32} &&\geq c_{2} &&\text{(required intake of nutrient $N_{2}$)}\\
& y_{1} a_{13} + y_{2} a_{23} + y_{3} a_{33} &&\geq c_{3} &&\text{(required intake of nutrient $N_{3}$)}\\
& y_{1} a_{14} + y_{2} a_{24} + y_{3} a_{34} &&\geq c_{4} &&\text{(required intake of nutrient $N_{4}$)}\\
&y_{1}, y_{2}, y_{3} &&\geq 0&&\text{(non-negativity constraints)}
\end{alignat}
$$

## 2. 輸送問題 | Hitchcock's Transportation Problem
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}$で表される．

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

- 未知変数: $y_{ij}$を生産地$P_{i}$から消費地$M_{j}$までの輸送量とする．$\boldsymbol{y} = (y_{ij}: i = 1, 2, 3, j = 1, 2, 3, 4)$ とする．
- 目的関数: 最小化すべき総輸送費用は，以下の式で表される：
$$
Z(\boldsymbol{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_{\boldsymbol{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}
$$

---
Suppose that you want to transport gasoline from three production sites $P_1, P_2$ and $P_3$ to four consumption sites $M_1, M_2, M_3$ and $M_4$. It is also assumed that
- The gasoline supply from $P_{i}$ is denoted by a given constant $s_{i}$ ($i=1,2,3$).
- The gasoline demand at $M_{j}$ is denoted by a given constant $r_{j}$ ($j=1,2,3,4$).
- The transportation cost per unit of gasoline from $P_i$ to $M_j$ is denoted by a given constant $b_{ij}$ ($i=1,2,3$ and $j=1,2,3,4$).

:::warning 
**Hitchcock's Transportation Problem**: How much gasoline should be transportated from each production site to each demand site at the lowest cost?
:::

- **Variables**: Let $y_{ij}$ be the amount of gasoline transported from $P_{i}$ to $M_{j}$ ($i=1,2,3$ and $j=1,2,3,4$).
- **Objective**: The total transportation cost to minimize is
$$
Z(\boldsymbol{y}) = \sum_{i=1}^{3}\sum_{j=1}^{4} y_{ij} b_{ij}
$$
- **Constraints (supply side)**:
The total amount of gasoline transported *from* $P_{i}$ is $y_{i1} + y_{i2} + y_{i3} + y_{i4}$ and it should not exceed the supply $s_{i}$:
$$
\sum_{j=1}^{4} y_{ij} \leq s_{i} \qquad \forall i = 1, 2, 3
$$
- **Constraints (demand side)**:
The total amount of gasoline transported *to* $M_{j}$ is $y_{1j} + y_{2j} + y_{3j}$ and it should not smaller than the demand $r_{j}$:
$$
\sum_{i=1}^{3} y_{ij} \geq r_{j} \qquad \forall j = 1, 2, 3, 4
$$
- **Non-negativity constraints**:
The amount of gasoline should not be negative:
$$
y_{ij} \geq 0, \qquad \forall i=1, 2, 3\,  \forall j=1,2,3,4.
$$

The transportation problem thus can be formulated as 
$$
\begin{alignat}{3}
\min_{\boldsymbol{y}} \quad &\sum_{i=1}^{3} \sum_{j=1}^{4} y_{ij} b_{ij} &&&&\text{(total cost)}\\
\text{s.t.} \quad 
& \sum_{j=1}^{4} y_{ij} \leq s_{i} && \forall i = 1, 2, 3 \quad && \text{(supply const. at $P_{i}$)} \\
& \sum_{i=1}^{3} y_{ij} \geq r_{j} && \forall j = 1, 2, 3, 4 \quad && \text{(demand const. at $M_{j}$)}
\\
& y_{ij} \geq 0 && \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4 \quad && \text{(non-negativity)}
\end{alignat}
$$

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

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

- 未知変数: $x_{ij}$を，研究テーマ$j$の学生$i$への「割り当て」とする． 本来なら$x_{ij}$ は0か1のいずれかを離散的に取る変数(二値変数)であるが， ここでは$[0,1]$の範囲内の任意の実数値を取り得る連続変数として取り扱う．
- 目的関数： 最大化すべき総生産量は，
$$
Z(\boldsymbol{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_{\boldsymbol{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}
$$

---
Suppose that you want assign $M$ tasks to $N$ workers. It is assumed that
- Each worker is assigned at most 1 task.
- Each task is assigned to at most 1 worker.
- The performance of worker $i$ assigned to task $j$ is denoted by a given constant $c_{ij}$ ($i=1,\cdots,N, j=1, \cdots, M$).

:::warning
**Assignment Problem**: To maximize the total performance by assigning the workers to the tasks.
:::

- **Variables**: Let $x_{ij}$ be the assignment of worker $i$ to task $j$. If worker $i$ is assigned to task $j$, $x_{ij}=1$, while if worker $i$ is not assigned to task $j$, $x_{ij}=0$.
- **Constraint (worker side)**: Worker $i$ should not be assigned more than one tasks:
$$
\sum_{j=1}^{M} x_{ij} \leq 1 \quad \forall i = 1, 2, \cdots, N.
$$
- **Constraint (task side)**: No more than one workers are assigned to task $j$:
$$
\sum_{i=1}^{N} x_{ij} \leq 1 \quad \forall j = 1, 2, \cdots, M.
$$
- **Non-negativity constraints**:
The assignment should not be negative:
$$
x_{ij} \geq 0, \qquad \forall i=1, \cdots, N, \,  \forall j=1,\cdots, M.
$$

Thus the assignment problem is formulated as the following LP.
$$
\begin{alignat}{3}
\max_{\boldsymbol{x}} \quad &\sum_{i=1}^{N} \sum_{j=1}^{M} c_{ij} x_{ij} &&&&\text{(total performance)}\\
\text{s.t.} \quad 
& \sum_{j=1}^{N} x_{ij} \leq 1 && \forall i = 1, 2, \cdots, N \quad && \text{(const. for worker $i$)} \\
& \sum_{i=1}^{N} x_{ij} \leq 1 && \forall j = 1, 2, \cdots, M \quad && \text{(const. for task $j$)}
\\
& x_{ij} \geq 0 && \forall i = 1, 2, \cdots, N\, \forall j = 1, 2, \cdots, M\quad && \text{(non-negativity)}
\end{alignat}
$$

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

It is well known that the optimal solution to the assignment problem, $x_{ij}^{\ast}$, always takes either $1$ or $0$.
:::


# 標準形とベクトル・行列表現 | Standard Form and Vector/Matrix Representation
## 線形計画問題の分類 | Variations of LPs
- 目的関数(objective): 最大化(maximize) or 最小化 (minimize)
- 未知変数(variables): 非負制約あり(with non-negativity) or 非負制約なし(without non-negativity)
- 制約条件(constraints): 線形式 $\leq$ 定数 or 線形式 $=$ 定数 or 線形式 $\geq$ 定数

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

**Standard form** enables us to formulate and analyze any LPs in a uniform manner.


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

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

---
There are two standard forms:
- **Inequality standard form** (**Standard maximization** Standard minimization):
  Useful for obtaining dual problems.
- **Equiality standard form** 
  Useful for numerical solution method (simplex method).


# 標準最大化問題 | Standard Maximization
$N$ 個の未知変数$x_{1}, x_{2}, \cdots, x_{N}$ を用いて，$M$本の不等式制約条件を満足しながら，目的関数を最大化する．
To maximize the objective function by choosing $N$ variables $x_{1}, x_{2}, \cdots, x_{N}$ with $M$ inequality conditions.
$$
\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}
$$

## 標準最大化問題のベクトル・行列表現 | Vector/Matrix Representation
### 目的関数 | Objecive Function
標準最大化問題の目的関数は，2つのN次元列ベクトル
$$
    \boldsymbol{x} =
    \begin{bmatrix}
        x_{1} \\ x_{2} \\ \vdots \\ x_{N}
      \end{bmatrix}
    , \quad
    \boldsymbol{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} = \boldsymbol{c}^{\top} \boldsymbol{x}
$$
と表せる． ただし，${}^{\top}$は行列・ベクトルの転置を表す記号．

---

The objective function of a standard maximization problem can be represented as $$
c_{1} x_{1} + c_{2} x_{2} +\cdots +c_{N} x_{N} = \sum_{i=1}^{N} c_{i} x_{i} = \boldsymbol{c}^{\top} \boldsymbol{x},$$
where $\boldsymbol{x}$ and $\boldsymbol{c}$ are $N$-dimensional column vectors,
$$
\boldsymbol{x} =
\begin{bmatrix}
 x_{1} \\ x_{2} \\ \vdots \\ x_{N}
\end{bmatrix}
, \quad
\boldsymbol{c} =
\begin{bmatrix}
    c_{1} \\ c_{2} \\ \vdots \\ c_{N}
\end{bmatrix}$$ 
and ${}^{\top}$ is a tranpose operator.

### $j$ 番目不等式制約 | $j$ th Inequality Constraint
$j (= 1, \cdots, M)$ 本目の不等式制約は, $N$次元 行ベクトル$\boldsymbol{a}_{j}$:
$$
\boldsymbol{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} = \boldsymbol{a}_{j} \boldsymbol{x} \leq b_{j}
$$
と表せる． 

さらに，$M\times{N}$行列$\boldsymbol{A}$ および$M$次元列ベクトル:
$$
\boldsymbol{A} = \begin{bmatrix}
\boldsymbol{a}_{1} \\ \vdots \\ \boldsymbol{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}
, \boldsymbol{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}
\boldsymbol{a}_{1} \boldsymbol{x} \\
\vdots\\
\boldsymbol{a}_{M} \boldsymbol{x} 
\end{bmatrix} = \boldsymbol{A} \boldsymbol{x} \leq  \boldsymbol{b}
$$

---
$j$ th inequality constraint can be represented as
$$
a_{j1} x_{1} + a_{j2} x_{2} + \cdots + a_{jN} x_{N} = \sum_{i=1}^{N} a_{ji} x_{i} = \boldsymbol{a}_{j} \boldsymbol{x} \leq b_{j},
$$
where $\boldsymbol{a}_{j}$ is $N$-dimensional row vector:
$$
\boldsymbol{a}_{j} = \begin{bmatrix}
a_{j1} & a_{j2} & \cdots &a_{jN}
\end{bmatrix}
$$

The whole inequality constraints can be represented as
$$
\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}
\boldsymbol{a}_{1} \boldsymbol{x} \\
\vdots\\
\boldsymbol{a}_{M} \boldsymbol{x} 
\end{bmatrix} = \boldsymbol{A} \boldsymbol{x} \leq  \boldsymbol{b},
$$
where $\boldsymbol{A}$ and $\boldsymbol{b}$ are the following $M \times N$ matrix and $M$-dimensional column:
$$
\boldsymbol{A} = \begin{bmatrix}
\boldsymbol{a}_{1} \\ \vdots \\ \boldsymbol{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}
, \boldsymbol{b} = \begin{bmatrix}
b_{1} \\ \vdots \\ b_{M}
\end{bmatrix}
$$

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

Non-negativity constraints can be denoted by
$$
\boldsymbol{x} \geq \boldsymbol{0},
$$ 
where $\boldsymbol{0}$ is $N$-dimensional column with all elements $0$.


## 標準最大化問題のベクトル・行列表現 | Vector/Matrix Representation of Standard Maximization
結局，標準最大化問題は，
- $M\times{}N$行列 $\boldsymbol{A}$
- $M$次元列ベクトル $\boldsymbol{b}$
- $N$次元列ベクトル $\boldsymbol{c}$

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

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

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

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

---
A standard maximization problem can be denoted as
$$
\begin{align*}
\max_{\boldsymbol{x}} \quad &\boldsymbol{c}^{\top}\boldsymbol{x} \\
\text{s.t.} \quad &
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b} \\
&\boldsymbol{x} \geq \boldsymbol{0}
\end{align*}.
$$
or, more simply
$$
\max_{\boldsymbol{x}} \left\{\left.
\boldsymbol{c}^{\top} \boldsymbol{x} \right|
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{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$次元列ベクトル$\boldsymbol{y} = \begin{bmatrix}y_{1}\\\vdots\\y_{M}\end{bmatrix}$とすれば，標準最小化問題の不等式制約は，
$$
\boldsymbol{a}_{1}^{\top} y_{1} + \boldsymbol{a}_{2}^{\top} y_{2} + \cdots + \boldsymbol{a}_{M}^{\top} y_{M} = \boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}
$$
と書ける． 従って，標準最小化問題は，ベクトル・行列を用いて
$$
\begin{align*}
\min_{\boldsymbol{y}} \quad &\boldsymbol{y}^{\top}\boldsymbol{b} \\
\text{s.t.} \quad &
\boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c} \\
&\boldsymbol{y} \geq \boldsymbol{0}
\end{align*}
$$
と表せる． より簡潔に
$$
\min_{\boldsymbol{y}} \left\{\left.
\boldsymbol{y}^{\top} \boldsymbol{b} \right|
\boldsymbol{A}^{\top} \boldsymbol{y} \geq \boldsymbol{c}, \boldsymbol{y} \geq \boldsymbol{0}
\right\}
$$
と表すこともある. 
-->

# 標準最大化問題への変換 | Reduction to Standard Maximization Problem
任意の問題は不等式標準形に変換できる．たとえば，次の問題:
$$
\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*}
$$
は，以下の手順で標準最大化問題に変換できる．

Any linear programming problem can be reduced to standard form. Suppose the following LP as an example:
$$
\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 (either positive, negative or 0)}
\end{align*}
$$

1) 最小化問題は，目的関数の全ての係数に$-1$を乗じることで最大化問題に置き換える：
   Minimization is converted to maximization by multiplying objective function by $-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つの不等式に置き換える：
   Each equality constraint is replaced by two inequalities:
$$
x_{1} + x_{2} = 2 \Rightarrow \begin{cases}
x_{1} + x_{2} \leq 2 \\
x_{1} + x_{2} \geq 2
\end{cases}
$$
  
3) 不等式制約は ==**線形式$\leq$定数**== の形に揃える：
   Each inequality constraint is alined to the form of linear expression $\leq$ constant.  $$
  \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}^{-}$で置き換える．
     Each free variable is replaced by the difference between two (artificial) non-negative variables. Here two non-negative variables $x_{3}^{+}$ and $x_{3}^{-}$ are introduced and $x_{3}$ is replaced by the their difference.
  $$
  \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}
  $$

# 練習(提出の必要はありません) | Exercise (no submission required)
輸送問題を標準最大化問題に変換しなさい．
Convert the transportation problem to a standard maximization problem.
