---
lang: ja
tags: lecture, linear programming
---
# 線形計画問題(1): 標準形<br>練習問題回答例
[線形計画問題ポータルへ戻る | Back to LP Portal](https://hackmd.io/@nagae/LP)

# 練習問題
:::success
下記の輸送問題を標準最大化問題にしなさい
:::
$$
\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}
$$