---
lang: ja
tags: MTNS-2020, lecture, linear programming
---
# 2020年度 交通社会システム論<br>第2回 演習問題解答例
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2020)
<div style="text-align: center">

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

# 課題
輸送問題を標準最大化問題にしなさい

## 輸送問題
$$
\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}
$$

## 目的関数に$-1$を乗じて最大化問題にする．
$$
\min_{\mathbf{y}} \sum_{i=1}^{3} \sum_{j=1}^{4} y_{ij} b_{ij} \rightarrow
\max_{\mathbf{y}} \sum_{i=1}^{3} \sum_{j=1}^{4} - y_{ij} b_{ij}
$$

## 制約条件を ==**線形式 $\leq$ 定数**== のかたちに揃える
$$
\sum_{i=1}^{3} y_{ij} \geq r_{j} \rightarrow
\sum_{i=1}^{3} - y_{ij} \leq - r_{j} \qquad \forall j = 1, 2, 3, 4
$$

## 標準最大化問題に変換された輸送問題
$$
\begin{alignat}{3}
\max_{\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} \leq - r_{j} &\qquad & \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}
$$