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

# 問題
[線形計画問題(1)標準形](https://hackmd.io/@nagae/LP-Ch01)で紹介した下記3つの問題のそれぞれについて，双対問題を導出せよ:
Derive dual problems of the following three LPs in [[LP(1) standard form]](https://hackmd.io/@nagae/LP-Ch01):

1. 食生活問題 | Diet problem
2. 輸送問題 | (Hitchcock's) Transportation problem
3. 割当問題 | Assignment problem

## 1. 食生活問題 | Diet Problem
もとの問題（主問題）:
The original problem (primal):
$$
\text{(P1)} \qquad
\begin{alignat}{3}
\min_{y_{1}, y_{2}, y_{3}} \quad & y_{1} b_{1} + y_{2} b_{2} + y_{3} b_{3} \\
\text{s.t.} \quad
& y_{1} a_{11} + y_{2} a_{21} + y_{3} a_{31} &&\geq c_{1} \\
& y_{1} a_{12} + y_{2} a_{22} + y_{3} a_{32} &&\geq c_{2} \\
& y_{1} a_{13} + y_{2} a_{23} + y_{3} a_{33} &&\geq c_{3} \\
& y_{1} a_{14} + y_{2} a_{24} + y_{3} a_{34} &&\geq c_{4} \\
&y_{1}, y_{2}, y_{3} &&\geq 0
\end{alignat}
$$

標準最大化問題へ変換：
Convert to a standard maximization problem:
$$
\text{(P1')} \qquad
\begin{alignat}{3}
\max_{y_{1}, y_{2}, y_{3}} \quad & -y_{1} b_{1} - y_{2} b_{2} - y_{3} b_{3} \\
\text{s.t.} \quad
& -y_{1} a_{11} - y_{2} a_{21} - y_{3} a_{31} &&\leq -c_{1} \\
& -y_{1} a_{12} - y_{2} a_{22} - y_{3} a_{32} &&\leq -c_{2} \\
& -y_{1} a_{13}- y_{2} a_{23} - y_{3} a_{33} &&\leq -c_{3} \\
& -y_{1} a_{14} - y_{2} a_{24} - y_{3} a_{34} &&\leq -c_{4} \\
&y_{1}, y_{2}, y_{3} &&\geq 0
\end{alignat}
$$

双対問題の導出：
Derive the dual problem:
$$
\text{(D1')} \qquad
\begin{alignat}{3}
\min_{x_{1}, x_{2}, x_{3}, x_{4}} \quad & -c_{1}x_{1} - c_{2}x_{2}-c_{3}x_{3}-c_{4}x_{4}\\
\text{s.t.} \quad
& - a_{11}x_{1} -a_{12}x_{2}-a_{13}x_{3}-a_{14}x_{4} &&\geq -b_{1} \\
& - a_{21}x_{1} -a_{22}x_{2}-a_{23}x_{3}-a_{24}x_{4} &&\geq -b_{2} \\
& - a_{31}x_{1} -a_{32}x_{2}-a_{33}x_{3}-a_{34}x_{4} &&\geq -b_{3} \\
&x_{1}, x_{2}, x_{3}, x_{4} &&\geq 0
\end{alignat}
$$

目的関数と制約条件に$-1$を乗じて整理：
Mutiplying $-1$ to the objective and the constraints, we obtain:
$$
\text{(D1)} \qquad
\begin{alignat}{3}
\max_{x_{1}, x_{2}, x_{3}, x_{4}} \quad & c_{1}x_{1} + c_{2}x_{2}+c_{3}x_{3}+c_{4}x_{4}\\
\text{s.t.} \quad
& a_{11}x_{1} +a_{12}x_{2}+a_{13}x_{3}+a_{14}x_{4} &&\leq b_{1} \\
& a_{21}x_{1} +a_{22}x_{2}+a_{23}x_{3}+a_{24}x_{4} &&\leq b_{2} \\
& a_{31}x_{1} +a_{32}x_{2}+a_{33}x_{3}+a_{34}x_{4} &&\leq b_{3} \\
&x_{1}, x_{2}, x_{3}, x_{4} &&\geq 0
\end{alignat}
$$

「双対問題の双対問題は主問題」と以下の関係から直接求めてもよい：
You can obtain the dual by using "The dual of dual problem is the primal problem":
$$
\text{(P)} \quad \max_{\boldsymbol{x}}
\left\{
\left.\boldsymbol{c}^{\top} \boldsymbol{x}\right|
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}
\right\}
\Leftrightarrow
\text{(D)} \quad \min_{\boldsymbol{y}}
\left\{
\left.\boldsymbol{y}^{\top}\boldsymbol{b}\right|
\boldsymbol{y}^{\top} \boldsymbol{A} \geq \boldsymbol{c}^{\top}, \mathbf{y} \geq \boldsymbol{0}
\right\}
$$

## 2. 輸送問題 | Hitchcock's Transportation Problem

もとの問題(主問題):
The original primal:
$$
\text{(P2)}\qquad
\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}
$$

上記$\text{(D)}$の形（標準最小化問題と呼ばれる）に変形：
Convert to the above $\text{(D)}$-type form (referred to as a standard minimization problem):
$$
\text{(P2')}\qquad
\begin{alignat}{3}
\min_{\boldsymbol{y}} \quad &\sum_{i=1}^{3} \sum_{j=1}^{4} y_{ij} b_{ij} \\
\text{s.t.} \quad
& - \sum_{j=1}^{4} y_{ij} \geq - s_{i} \quad && (p_{i}) \quad \forall i = 1, 2, 3 \\
& \sum_{i=1}^{3} y_{ij} \geq r_{j} \quad &&(q_{j}) \quad \forall j = 1, 2, 3, 4
\\
& y_{ij} \geq 0 && \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4 ,
\end{alignat}
$$
ただし，括弧内の変数は，それぞれの制約条件に対応した主変数．
where symbols in the parenthes are dual variables corresponding to each constraint.

$\text{(P2')}$の双対問題を導出：
Derive the dual of $\text{(P2')}$:
$$
\text{(P2')}\qquad
\begin{alignat}{3}
\max_{\boldsymbol{p}, \boldsymbol{q}} \quad &
\sum_{j=1}^{4} r_{j} q_{j}
-\sum_{i=1}^{3} s_{i} p_{i} \\
\text{s.t.} \quad
& q_{j} - p_{i} \leq b_{ij}&& \forall i = 1, 2, 3\, \forall j = 1, 2, 3, 4 \\
& p_{i} \geq 0 &&\forall i = 1, 2, 3\\
& q_{j} \geq 0 &&\forall j = 1, 2, 3, 4 \quad
\end{alignat}
$$

もちろん，食生活問題$\text{(P1)}$と同様に標準最大化問題に直してから双対問題を求めてもよい．
Of course you can derive the dual problem via the standard maximization form as $\text{(P1)}$.

## 3. 割当問題
もとの問題（主問題）:
The original primal problem:
$$
\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}
$$

各労働者 $i=1, \cdots, N$ についての双対変数を$p_{i}$， 各タスク $j=1, \cdots, M$ についての双対変数を$q_{j}$とおけば， 双対問題は以下のように求められる：
Let $p_{i}$ and $q_{j}$ be dual variables with respect to the worker $i$'s constraint and the task $j$'s constraint, respectively, the dual problem can be formulated as:
$$
\begin{alignat}{3}
\min_{\boldsymbol{p}, \boldsymbol{q}} \quad &
\sum_{i=1}^{N} p_{i} + \sum_{j=1}^{M} q_{j}\\
\text{s.t.} \quad
& p_{i} + q_{j} \geq c_{ij} && \forall i = 1, 2, \cdots, N, \forall j = 1, 2, \cdots, M \\
& p_{i} \geq 0 && \forall i = 1, 2, \cdots, N\\
& q_{j} \geq 0 && \forall j = 1, 2, \cdots, Mt
\end{alignat}
$$