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

このページへは以下のQRコードまたはURLからアクセスできます：
This page is available from the following QR code or URL:
<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch02</code>

</div>

# 双対問題 | Dual Problem
## A君ふたたび | Here comes Mr. Adam, again.

バイトとデートへの時間配分を直接考えるのではなく，以下の3つの制約だけから「どこまで高いリア充度が実現できるか」を考えてみる：
- 時間制約: $x_{1} + x_{2} \leq 8$
- 予算制約: $-2x_{1}+x_{2} \leq 2$
- 体力制約: $2x_{1} + 3x_{2} \leq 18$

なお，リア充度は$Z(x_{1}, x_{2}) = x_{1} + 2x_{2}$ である．

In the previous lecture, we consider a "happiness maximization problem," where the unknown variables are the allocation of time to the part-time work and dating. Let us consider how much Mr. Adam can increase his happiness, $Z(x_{1}, x_{2}) = x_{1} + 2x_{2}$, based only on the following three constraints:
1. Time constraint: $x_{1} + x_{2} \leq 8$
2. Budget constraint: $-2x_{1}+x_{2} \leq 2$
3. Physical constraint: $2x_{1} + 3x_{2} \leq 18$

## 制約条件からリア充度の上限を推定する | Estimate the Upper Bound (UB) of the Happiness
まず，時間制約$x_{1}+x_{2} \leq 8$ の両辺を2倍してみる：
$$
2x_{1} + 2 x_{2} \leq 16
$$
このとき，
- この不等式左辺の$x_{1}, x_{2}$の係数$(2,2)$は，リア充度$x_{1} + 2x_{2}$ の係数$(1,2)$以上
- $x_{1}, x_{2} \geq 0$

であることから，上記不等式の左辺は， ==**リア充度と同じかそれより大きい**==. 従って，
$$
\text{リア充度}=x_{1} + 2 x_{2} \leq 2x_{1} + 2x_{2} \leq 16
$$
が成り立つ．これは，==**時間制約**== を満たす限り，==**16より高いリア充度**== は実現できないことを意味する．

次に，体力制約$2x_{1} + 3x_{2} \leq 18$ の両辺を$2/3$倍してみる．
$$
\frac{4}{3} x_{1} + 2x_{2} \leq 12
$$
この不等式左辺の係数$(\frac{4}{3},2)$は，リア充度$x_{1} + 2x_{2}$ の係数$(1,2)$以上．従って，
$$
\text{リア充度}=x_{1} + 2 x_{2} \leq \frac{4}{3}x_{1} + 2x_{2} \leq 12
$$
が成り立つ．つまり，==**体力制約**== を満たす限り，==**12より高いリア充度**== は実現できない．

ここで得られたリア充度の上限($=12$)は，時間制約から得られた上限($=16$)より小さい(i.e. ==**より精度が高い**==)．

もっと精度の高い(小さい)上限はないだろうか?

予算制約と体力制約の両辺に，それぞれ，$1/8$および$5/8$を乗じる：
- 予算制約: $-2x_{1}+x_{2} \leq 2 \, (\times \frac{1}{8}) \rightarrow -\frac{1}{4} x_{1} + \frac{1}{8} x_{2} \leq \frac{1}{4}$
- 体力制約: $2x_{1}+3x_{2} \leq 18 \, (\times \frac{5}{8}) \rightarrow \frac{5}{4} x_{1} + \frac{15}{8} x_{2} \leq \frac{45}{4}$

得られた不等式を足し合わせれば，
$$
\text{リア充度} = x_{1} + 2x_{2} \leq \frac{23}{2} = 11.5
$$
となり，より小さい ==**リア充度の上限 11.5**== が得られる． 実は，これは最小の上限となっている(どのように制約条件を組み合わせても，これより小さい上限は実現できない)．

First, let us double both sides of the time constraint $x_{1}+x_{2} \leq 8$:
$$
2x_{1} + 2 x_{2} \leq 16
$$
Remark that the left hand side of this inequality must not be smaller than the happiness for any $(x_{1}, x_{2})$. That is, the following inequality always holds.
$$
\text{Happiness}=x_{1} + 2 x_{2} \leq 2x_{1} + 2x_{2} \leq 16.
$$
In other words, the happiness *can not be higher than $16$*, as long as the time constraint is met (i.e. $16$ is the **upper bound** of the happiness).

Second, let us multiply the both sides of the physical constraint by $2/3$:
$$
\frac{4}{3} x_{1} + 2x_{2} \leq 12
$$
Again, the left hand side of this inequality is equal to or greater than the happiness:
$$
\text{Happiness}=x_{1} + 2 x_{2} \leq \frac{4}{3}x_{1} + 2x_{2} \leq 12.
$$
It implies that the happiness *can not exceed* $12$ as long as the physical condition is met. Note that this new upper limit is finer, that is, it is smaller than that obtained from the time constraint. In other words, you can replace the upper limit by 12 rather than 16.

Is there a more finer (i.e. smaller) upper bound?

Let us multiply the budget and the physical constraints by $1/8$ and $5/8$, respectively:
- Budget const.: $-2x_{1}+x_{2} \leq 2 \, (\times \frac{1}{8}) \rightarrow -\frac{1}{4} x_{1} + \frac{1}{8} x_{2} \leq \frac{1}{4}$
- Physical const.: $2x_{1}+3x_{2} \leq 18 \, (\times \frac{5}{8}) \rightarrow \frac{5}{4} x_{1} + \frac{15}{8} x_{2} \leq \frac{45}{4}$

Adding together the these inequalities, we obtain:
$$
\text{Happiness} = x_{1} + 2x_{2} \leq \frac{23}{2} = 11.5.
$$
This is the **minimum** (the most accurate) upper bound of the Happiness.

## リア充度の上限推定問題 | Estimation of UB
ここまでで見てきた「制約条件からリア充度の上限を探る問題」を定式化してみよう．
Let us formulate this problem to obtain the upper bound (UB) of the happiness from constraints as a linear programming problem:

:::info
**問題の概要 | The Outline of the Problem**
- 「時間制約」「予算制約」「体力制約」を定数倍(重みづけ)したものを足し合わせて($x_{1}, x_{2}$についての) ==**線形式$\leq$ 定数**== 型の ==**不等式**== を構成する．
We need to form a inequality of the type "linear expression $\leq$ given constant", by multiplying and adding together the time, budget and physical constraints.
- ここで，
- 各不等式に乗ずる ==**重み**== が非負
- 不等式左辺の$x_{1}, x_{2}$についての係数が，いずれも，リア充度の係数$(1,2)$を下回らない
とすることで，不等式左辺が ==**リア充度以上**== となることが保証できる．
The followings are required to ensure that the left hand side of the inequality is equal to or greater than the happiness:
- The weight of each constraint is non-negative.
- The coefficient of the linear expression of the left hand side of the inequality should not be smaller than that of the happiness $(1,2)$.
- 不等式右辺の定数(リア充度)が ==**なるべく小さくなる**==(精度が高くなる)ように，各制約への ==**重み**== を決定．
We want to obtain the minimum (the most accurate) upper limit.
:::

### 未知変数と非負制約 | Unknown Variables and Non-negativity Constraints
- 求めたいのは，時間制約，予算制約および体力制約に対する ==**重み**==． それぞれ, $y_{1}, y_{2}, y_{3}$とする． これらの重みは，いずれも非負でなければならない．
Let $y_{1}, y_{2}$ and $y_{3}$ be the weight to the time constraint, budget constraint and physical constraint, respectively. These weights must be non-negative.
$$
y_{1}, y_{2}, y_{3} \geq 0
$$

### 各制約の加重線形和から得られる不等式 | Inequality obtained from the weighted sum of constraints
各制約に重み$y_{1}, y_{2}, y_{3}$ を乗じて足し合わせることで，以下の不等式が得られる:
The following inequality is obtained from the weighted sum of constraints:
$$
\begin{array}{rrcrcll}
y_{1} \times (& x_{1} &+& x_{2} &\leq& 8 &) \\
y_{2} \times (&-2 x_{1} &+& x_{2} &\leq& 2 &) \\
y_{3} \times (& 2 x_{1} &+& 3 x_{2} &\leq& 18 &) \\
\hline
&(y_{1} -2 y_{2} + 2 y_{3}) x_{1} &+& (y_{1} + y_{2} + 3 y_{3}) x_{2} &\leq& 8 y_{1} + 2 y_{2} + 18 y_{3}
\end{array}
$$

### 不等式の左辺がリア充度以上となるための制約 | The constraint to ensure that the LHS of the inequality is equal to or greater than the happiness
加重線形和として得られた不等式の左辺：
$$
(y_{1} -2 y_{2} + 2 y_{3}) x_{1} + (y_{1} + y_{2} + 3 y_{3}) x_{2}
$$
が，常にリア充度:
$$
x_{1} + 2 x_{2}
$$
以上となるためには，前者の$x_{1}, x_{2}$の係数が，いずれも後者のそれ以上となる必要がある：
- $x_{1}$の係数: $y_{1} - 2y_{2} + 2 y_{3} \geq 1$
- $x_{2}$の係数: $y_{1} + y_{2} + 3 y_{3} \geq 2$

By comparing the coefficients of the inequality obtained from the weighted sum of the constraints and happiness, the followings must be satisfied to ensure that the LHS of the inequality is equal to or greater than the happiness.
- The coefficient of $x_{1}$: $y_{1} - 2y_{2} + 2 y_{3} \geq 1$,
- The coefficient of $x_{2}$: $y_{1} + y_{2} + 3 y_{3} \geq 2$.

### 目的関数 | Objective
加重線形和として得られた不等式の右辺：
$$
8 y_{1} + 2 y_{2} + 18 y_{3}
$$
は ==**リア充度の上限**== を表しており，これをなるべく小さく(==**最小化**==)したい．

The RHS of the inequality:
$$8y_{1}+2y_{2}+18y_{3}$$
is the UB of the happiness to be minimized.

### 線形計画問題として定式化されたリア充度の上限推定問題 | LP Formulation of the UB Estimation
$$
\begin{alignat*}{3}
\min_{y_{1}, y_{2}, y_{3}} \quad & 8 y_{1} + 2 y_{2} + 18 y_{3} && \text{(目的関数=リア充度の上限)}\\
\text{s.t.} \quad
& y_{1} - 2 y_{2} + 2 y_{3} &\geq 1 \quad & \text{(バイト時間の係数が満たすべき条件)}\\
& y_{1} + y_{2} + 3 y_{3} &\geq 2 \quad & \text{(デート時間の係数が満たすべき条件)}\\
& y_{1}, y_{2}, y_{3} &\geq 0 \quad & \text{(非負制約)}
\end{alignat*}
$$
Accordingly, the estimation of the UB of the happiness can be formulated as the following LP:
$$
\begin{alignat*}{3}
\min_{y_{1}, y_{2}, y_{3}} \quad & 8 y_{1} + 2 y_{2} + 18 y_{3} && \text{(Obj.: the upper limit)}\\
\text{s.t.} \quad
& y_{1} - 2 y_{2} + 2 y_{3} &\geq 1 \quad & \text{(constr. to the coefficient of $x_{1}$)}\\
& y_{1} + y_{2} + 3 y_{3} &\geq 2 \quad & \text{(constr. to the coefficient of $x_{2}$)}\\
& y_{1}, y_{2}, y_{3} &\geq 0 \quad & \text{(non-negativity)}
\end{alignat*}
$$

# もとの問題と比べてみる | Comparing with the original problem
<table>
<tr><th style="text-align:center">もとの問題 | Original</th><th style="text-align:center">リア充度上限推定問題 | UB estimation</th>
</tr>
<tr><td style="vertical-align:top">

$$
\begin{array}{rl}
\displaystyle
\max_{x_{1}, x_{2}} & x_{1} + 2 x_{2}\\
\text{s.t.}
& x_{1} + x_{2} \leq 8 \\
& -2x_{1} + x_{2} \leq 2 \\
& 2x_{1} + 3 x_{2} \leq 18\\
& x_{1}, x_{2} \geq 0
\end{array}
$$

</td><td style="vertical-align:top">

$$
\begin{array}{rl}
\displaystyle
\min_{y_{1}, y_{2}, y_{3}} & 8 y_{1} + 2 y_{2} + 18 y_{3}\\
\text{s.t.}
& y_{1} - 2 y_{2} + 2 y_{3} \geq 1 \\
& y_{1} + y_{2} + 3 y_{3} \geq 2\\
& y_{1}, y_{2}, y_{3} \geq 0
\end{array}
$$

</td>
</tr>
</table>

係数と定数だけ並べてみると
Let us focus on the coefficients and constants:
<table>
<tr><th style="text-align:center">もとの問題 | Original </th><th style="text-align:center">リア充度上限推定問題 | UB estimation</th>
</tr>
<tr><td style="vertical-align:top">

$$
\begin{array}{lrr|l}
& (x_{1}) & (x_{2})\\
\max & \color{red}{1} & \color{red}{2} \\
\hline
\text{s.t.}
& 1 & 1 & \color{blue}{8}\\
& -2 & 1 & \color{blue}{2}\\
& 2 & 3 & \color{blue}{18}
\end{array}
$$

</td><td style="vertical-align:top">

$$
\begin{array}{lrrr|l}
& (y_{1}) & (y_{2}) & (y_{3})\\
\min & \color{blue}{8} & \color{blue}{2} &\color{blue}{18}\\
\hline
\text{s.t.}
& 1 & -2 & 2 & \color{red}{1}\\
& 1 & 1 & 3 & \color{red}{2}\\
\end{array}
$$

</td></tr>
</table>

以下の関係が見てとれる：
- もとの問題の制約条件の左辺係数の転置 = 推定問題の制約条件の左辺係数
- もとの問題の目的関数の係数(の転置) = 推定問題の制約条件の右辺定数
- もとの問題の制約条件の右辺定数(の転置) = 推定問題の目的関数の係数

You can observe:
- The transpose of the coefficients of orig. constraints = The coefficients of UB estimation constraints
- The transpose of the coefficients of orig. Obj. = The RHS constants of UB constraints.
- The tranpose of the RHS of orig. constraints = The coefficients of UB Obj.

# 双対問題 | Dual Problem
$N$次元列ベクトル$\boldsymbol{c}, \boldsymbol{x}$, $M$次元列ベクトル$\boldsymbol{b}, \boldsymbol{y}$および$M\times{N}$行列$\boldsymbol{A}$が与えられた時，標準最大化問題
$$
\text{(P)} \qquad \max_{\boldsymbol{x}}
\left\{
\left.\boldsymbol{c}^{\top} \boldsymbol{x}\right|
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}
\right\}
$$
に対して，最小化問題
$$
\text{(D)} \qquad \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\}
$$
を, ==**双対問題 (dual problem)**== と呼ぶ．双対問題 $\text{(D)}$ に対して，もとの問題 $\text{(P)}$ を ==**主問題 (primal problem)**== と呼ぶ．

「双対問題の双対問題」は主問題と等価である．

Given $N$-dimensional columns $\boldsymbol{c}, \boldsymbol{x}$, $M$-dimensional columns $\boldsymbol{b}, \boldsymbol{y}$ and a $M\times{}N$ matrix $\boldsymbol{A}$. Suppose a *standard maximization problem*:
$$
\text{(P)} \qquad \max_{\boldsymbol{x}}
\left\{
\left.\boldsymbol{c}^{\top} \boldsymbol{x}\right|
\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}
\right\}.
$$
Then the following minimization problem:
$$
\text{(D)} \qquad \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\}
$$
is referred to as the **dual problem** of $\text{(P)}$. For a dual problem $\text{(D)}$, the original problem $\text{(P)}$ is referred to as the **primal problem**. The dual of the dual problem is the primal problem.

# 双対問題の解釈 | An Economic Interpretation of Dual
双対問題は，それ自身が ==**何らかの意味を持った問題**== として解釈できることが多い．リア充問題の双対問題は，A君が持つ「時間」「資金」「体力」という3つの ==**資源**== のそれぞれの「(リア充度で測った)==**価値**==」を求める問題として解釈できる．

The dual itself can often be interpreted as a meaningful problem. For example, the dual of Mr. Adam's happiness maximization can be regarded as a problem to estimate the **value of the three resources** --time, budget and physical strength--- in terms of the happiness.

## 未知変数と非負制約 | Variables
$y_{1}, y_{2}, y_{3}$ は，それぞれ，時間，資金，体力の各資源の ==**価値**== とする． 非負制約$y_{1}, y_{2}, y_{3}\geq 0$は，価値が負の値にはならない自然な条件と解釈できる．

The variables of the dual, $y_{1}, y_{2}$ and $y_{3}$, can be interpreted as the **value** (in terms of the happiness) of each resource (i.e. time, budget and physical strength), respectively.

## 目的関数 | Objective
双対問題の目的関数
$$
8 y_{1} + 2y_{2} + 18 y_{3}
$$
は，(リア充度で測った) ==**総資産価値**== と見なせる．双対問題は ==**最小化問題**== であることから， ==**総資産価値の上限**== を推定する問題と解釈できる．

The objective function of the dual:
$$
8 y_{1} + 2y_{2} + 18 y_{3}
$$
can be interpreted as the **upper bound of the total value** of the resources (in terms of the happiness) to be minimized.

## $x_{1}$の係数に関する不等式制約 | Dual Constraint to the Coefficient of $x_{1}$
「1時間のバイト」は，

- ==**1単位**== の「時間」 と ==**2単位**== 「体力」 を**投入** して, ==**2単位**== の「資金」 と ==**1単位**== の「リア充度」 を **生産** する活動

と見なせる(「==**2単位**== の資金の**生産**」は，「==**-2単位**== の資金の**投入**」と読み替えてもよい．)
このとき，バイトに従事する時間$x_{1}$の係数に関する双対問題の不等式制約:
$$
y_{1} - 2 y_{2} + 2 y_{3} \geq 1
$$
は， ==**投入される資源の総価値**== (左辺)が，少なくともその対価として得られる ==**リア充度**== (右辺)を下回らなってはいけない条件と解釈できる．

"One hour part-time work" can be regarded as an economic activity that **produces** *2 unit of "budget"* and *1 unit of "happiness"* by **inputting** *1 unit of "time"* and *2 unit of "physical strength"* (or, "*2 unit production* of budget" can be replaced by "*-2 unit input* of budget"). Then the inequality constraint to the coefficient of $x_{1}$ of the dual:
$$
y_{1} - 2 y_{2} + 2 y_{3} \geq 1
$$
can be regarded as a constraint that the *total value of the input resources* (LHS) must not be less than the *produced happiness* (RHS).

## $x_{2}$の係数に関する不等式制約 | Dual Constraint to the Coefficient of $x_{2}$
バイトと同様，「1時間のデート」は，
- 「時間」「資金」および「体力」を，それぞれ ==**$(1,1,3)$ 単位**== づつ **投入** して ==**2単位**== の「リア充度」を **生産** する活動

と解釈できるから，デートに費す時間$x_{2}$ の係数に関する双対問題の不等式制約:
$$
y_{1} + y_{2} + 3 y_{3} \geq 2
$$
は，==**投入される資源の総価値**== (左辺)が，少なくともその対価として得られる ==**リア充度**== (右辺)を下回らなってはいけない条件と解釈できる．

Similarly, "one hour dating" can be regarded as an economic activity that **produces** *2 unit of "happiness"* by **inputting** *1 unit of "time"*, 1 unit of "budget" and *3 unit of "physical strength"*. Then the inequality constraint to the coefficient of $x_{2}$ of the dual:
$$
y_{1} + y_{2} + 3 y_{3} \geq 2
$$
can be regarded as a constraint that the *total value of the input resources* (LHS) must not be less than the *produced happiness* (RHS).

## 双対問題： 保有資源の総価値の上限を推定する問題
結局，リア充問題の双対問題は，

- A君が保有する 「時間」「資金」「体力」という ==**資源の総価値**== を，バイトとデートというそれぞれの ==**生産活動**== に おいて「投入資源の総価値が, 生産されるリア充度を下回らない」という条件の下で見積る問題

と解釈できる．

Accordingly, the dual of Mr. Adam's happiness maximization can be interpreted as the estimation of the upper bound of total value (in terms of the happiness) of the resources --- time, budget and physical strength --- subject to constrains that "the total value of input to each economic activity must not be less than that of production."

## リア充問題よりリアル(?)な問題 | Want More Reality?
ある地域に，以下の3種類の ==**再生可能資源**== を投入要素とする発電機とボイラーを導入する．
- 畜産由来の ==**8単位**== のバイオガス
- 地熱由来の ==**2単位**== の温水
- 間伐材由来の ==**18単位**== の木質バイオマス

Suppose an area with the following three different renewable resources to be input to a generator and boiler:
- 8 unit of biogas from livestock
- 2 unit of hot water
- 18 unit of woody biomass

発電機とボイラーの性能(稼働時間1単位に対する投入と生産):
<table>
<tr><th>発電機</th><th>ボイラー</th></tr>
<tr><td>

- ==**1単位**== のバイオガス
- ==**2単位**== の木質バイオマス

を**投入**すると
- ==**2単位**== の温水
- ==**1単位**== の電気

を**生産**する

</td><td>

- ==**1単位**== のバイオガス
- ==**1単位**== の温水
- ==**3単位**== の木質バイオマス

を**投入**すると
- ==**1単位**== の熱

を**生産**する．

</td>
</tr>
</table>
生産された ==**電気**== は1単位あたり1万円, ==**熱**== は1単位あたり2万円で売却できるとする．

The performance of the energy conversions (i.e. input and production per unit of operation) is summarized as
<table>
<tr><th>Generator</th><th>Boiler</th></tr>
<tr><td>
Input:
<ul>
<li>1 unit of biogas
<li>2 unit of woody biomass
</ul>
Output:
<ul>
<li> 2 unit of hot water
<ii> 1 unit of electricity
</ul>
</td><td>
Input:
<ul>
<li>1 unit of biogas
<li>1 unit of hot water
<li>3 unit of woody biomass
</ul>
Output:
<ul>
<li> 1 unit of heat
</ul>
</td>
</tr>
</table>
Suppose that the 1 unit of electricity can be sold at 10,000 JPY and 1 unit of heat can be sold at 20,000JPY.

<table>
<tr><th>主問題</th><th>双対問題</th></tr>
<tr><td>

発電機とボイラーの稼働時間$x_{1}, x_{2}$を ==**未知変数**== とし，各資源について
$$
\text{投入量}\leq\text{賦存量}
$$
なる制約を満たしながら，エネルギーの総売上を ==**最大化**==:
$$
\begin{align*}
\max_{x_{1},x_{2}} \quad & x_{1} + 2 x_{2}\\
\text{s.t.} \quad
& x_{1} + x_{2} \leq 8\\
& - 2 x_{1} + x_{2} \leq 2\\
& 2 x_{1} + 3 x_{2} \leq 18\\
& x_{1}, x_{2} \geq 0
\end{align*}
$$

</td>
<td>

各資源の価値$y_{1}, y_{2}, y_{3}$を ==**未知変数**== とし，各変換技術(発電機とボイラー)について ，
$$
\text{投入資源の価値}\geq\text{生産されるエネルギー価値}
$$
なる制約を満たしながら，資源の総価値の上限を ==**最小化**==:
$$
\begin{align*}
\min_{y_{1},y_{2},y_{3}} \quad & 8 y_{1} + 2y_{2} + 18 y_{3}\\
\text{s.t.} \quad
& y_{1} - 2y_{2} + 2 y_{3} \geq 1\\
& y_{1} + y_{2} + 3 y_{3} \geq 2 \\
& y_{1}, y_{2}, y_{3} \geq 0
\end{align*}
$$

</td></tr>
</table>
### Primal
- **Variables:** the operation time of generator and boiler, $x_{1}$ and $x_{2}$.
- **Constraints:** for each resources, the total input must not exceed the initial endowment.
- **Objective:** Maximize the total sales of energy
$$
\begin{align*}
\max_{x_{1},x_{2}} \quad & x_{1} + 2 x_{2}\\
\text{s.t.} \quad
& x_{1} + x_{2} \leq 8\\
& - 2 x_{1} + x_{2} \leq 2\\
& 2 x_{1} + 3 x_{2} \leq 18\\
& x_{1}, x_{2} \geq 0
\end{align*}
$$
### Dual
- **Variables:** the value of resources (biogas, hot water and woody biomass), $y_{1}, y_{2}$ and $y_{3}$
- **Constraints:** for each conversion technology, the total value of input must not be smaller than that of production.
- **Objective:** Minimize the upper bound of total value of resources
$$ \begin{align*} \min_{y_{1},y_{2},y_{3}} \quad & 8 y_{1} + 2y_{2} + 18 y_{3}\\ \text{s.t.} \quad & y_{1} - 2y_{2} + 2 y_{3} \geq 1\\ & y_{1} + y_{2} + 3 y_{3} \geq 2 \\ & y_{1}, y_{2}, y_{3} \geq 0 \end{align*} $$

# 等式制約を持つ / 非負制約を持たない問題に対する双対問題
# Dual of LP with Equality Constraints and Free Variables

## 主問題が等式制約を持つ場合 | Dual of LP with Equality Constraint

### 等式制約を持つ線形計画問題 | Primal
$$
\begin{align*}
\max_{x_{1}, x_{2}, x_{3}} \quad &
3 x_{1} + 4 x_{2} + x_{3} \\
\text{s.t.} \quad &
\color{red}{x_{1} + 3x_{2} + 2x_{3} = 4} \\&
x_{1} - 2 x_{2} + 3x_{3} \leq 5 \\&
x_{1}, x_{2}, x_{3} \geq 0
\end{align*}
$$
### 標準最大化問題 | Standard Maximization Problem
$$
\begin{alignat*}{3}
\max_{x_{1}, x_{2}, x_{3}} \quad &
3 x_{1} + 4 x_{2} + x_{3} \\
\text{s.t.} \quad &
\color{red}{x_{1} + 3x_{2} + 2x_{3} \leq 4} && (y_{1}^{+})\\&
\color{red}{- x_{1} - 3x_{2} - 2x_{3} \leq -4} \quad && (y_{1}^{-})\\&
x_{1} - 2 x_{2} + 3x_{3} \leq 5 && (y_{2})\\&
x_{1}, x_{2}, x_{3} \geq 0
\end{alignat*}
$$
ただし，各制約について，末尾の括弧内は，対応する双対問題の未知変数(双対変数)を表す．
Where symbols in the parentheses denote the corresponding dual variables.

### 双対問題 | Dual
$$
\begin{align*}
\min_{y_{1}^{+}, y_{1}^{-}, y_{2}} \quad &
4 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + 5 y_{2} \\
\text{s.t.} \quad &
\color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + y_{2} \geq 3 \\&
3 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} - 2 y_{2} \geq 4 \\&
2 \color{red}{\left(y_{1}^{+}-y_{1}^{-}\right)} + 3 y_{2} \geq 1 \\&
y_{1}^{+}, y_{1}^{-}, y_{2} \geq 0
\end{align*}
$$

### $y_{1} = y_{1}^{+} - y_{1}^{-}$ とおく
$$
\begin{align*}
\min_{\color{red}{ y_{1}}, y_{2}} \quad &
4 \color{red}{ y_{1}} + 5 y_{2} \\
\text{s.t.} \quad &
\color{red}{ y_{1}} + y_{2} \geq 3 \\&
3 \color{red}{ y_{1}} - 2 y_{2} \geq 4 \\&
2 \color{red}{ y_{1}} + 3 y_{2} \geq 1 \\&
\color{red}{ y_{1} \text{ is free}}, y_{2} \geq 0
\end{align*}
$$
==**等式制約**== に対応する ==**双対変数**== は _非負制約を持たない_
The dual variable corresponding to an equality condition is free.

## 主問題の未知変数が非負制約を持たない場合 | Dual of LP with Free Variables
### 非負制約を持たない未知変数を持つ線形計画問題 | LP with Free Variables
$$
\begin{align*}
\min_{\color{red}{x_{1}}, x_{2}} \quad &
4 \color{red}{ x_{1}} + 5 x_{2} \\
\text{s.t.} \quad &
\color{red}{ x_{1}} + x_{2} \geq 3 \\&
3 \color{red}{ x_{1}} - 2 x_{2} \geq 4 \\&
2 \color{red}{ x_{1}} + 3 x_{2} \geq 1 \\&
\color{red}{ x_{1} \text{ is free}}, x_{2} \geq 0
\end{align*}
$$

### 標準最小化問題 | Standard Maximization Problem
$$
\begin{alignat*}{3}
\max_{x_{1}^{+}, x_{1}^{-}, x_{2}} \quad &
-4 \color{red}{\left(x_{1}^{+}-x_{1}^{-}\right)} - 5 x_{2} \\
\text{s.t.} \quad &
-\color{red}{ \left(x_{1}^{+}-x_{1}^{-}\right)} - x_{2} \leq -3 &&(y_{1})\\&
-3 \color{red}{ \left(x_{1}^{+}-x_{1}^{-}\right)} + 2 x_{2} \leq -4 &&(y_{2})\\&
-2 \color{red}{ \left(x_{1}^{+}-x_{1}^{-}\right)} - 3 x_{2} \leq -1 &&(y_{3})\\&
x_{1}^{+}, x_{1}^{-}, x_{2} \geq 0
\end{alignat*}
$$

ただし，各制約について，末尾の括弧内は，対応する双対問題の未知変数(双対変数)を表す．
Where symbols in the parentheses denote the corresponding dual variables.

### 双対問題 | Dual
$$
\begin{align*}
\min_{y_{1}, y_{2}, y_{3}} \quad &
-3 y_{1} - 4 y_{2} - y_{3} \\
\text{s.t.} \quad &
\color{red}{-y_{1} - 3y_{2} - 2y_{3} \geq -4} \\&
\color{red}{ y_{1} + 3y_{2} + 2y_{3} \geq 4} \\&
-y_{1} + 2 y_{2} - 3y_{3} \geq -5 \\&
y_{1}, y_{2}, y_{3} \geq 0
\end{align*}
$$

### 線形式 $\lesseqgtr$ 定数→線形式$=$定数
The first two inequality can be replaced by an equality constraint.
$$
\begin{align*}
\min_{y_{1}, y_{2}, y_{3}} \quad &
-3 y_{1} - 4 y_{2} - y_{3} \\
\text{s.t.} \quad &
\color{red}{-y_{1} - 3y_{2} - 2y_{3} = -4} \\&
-y_{1} + 2 y_{2} - 3y_{3} \geq -5 \\&
y_{1}, y_{2}, y_{3} \geq 0
\end{align*}
$$

==**非負制約を持たない変数**== に対応した双対問題の ==**制約条件**== (双対制約)は _等式になる_.
The dual constraint corresponding to a free variable holds equality.

# 練習 (提出は不要) | Exercise (no submission required)
前回の講義で紹介した3つの問題：
1. 食生活問題
2. 輸送問題
3. 割当問題

のそれぞれについて，双対問題を導出せよ．

Derive dual problems of the following three LPs in the previous lecture:
1. Diet problem
2. Transportation problem
3. Assignment problem