線形計画問題から双対ベクトルを考える

　以下のような問題を考える。問題自体は[ORでわかる線形代数](http://www.orsj.or.jp/archive2/or60-12/or60_12_693.pdf)からお借りしたが、簡略化のため一部数値・文字を変更している。

- 2種類の商品を売ることによって利益を最大化したい
- 商品Xは材料Aを2、材料Bを3必要とする
- 商品Yは材料Aを1、材料Bを4必要とする
- 材料Aは40、材料Bは100しかない
- 商品Xは1個3円、商品Yは1個3円で売れる
- **この時の最大利益はいくらか？**

　このような問題は[線形計画問題](https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E8%A8%88%E7%94%BB%E5%95%8F%E9%A1%8C)と呼ばれる。

# まず解く

　これを求めるためには、XとYの量をそれぞれxとyと置いて、

```math
2x + y \leq 40 \\
3x + 4y \leq 100
```
　から、xyが存在しうる領域を求める。

　この中で、$3x+3y=k$という直線が接する中で$k$が取りうる最大値を求めればよい。図示すると以下のようになる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/ff221747-188a-33a8-c2c5-37698b41fb76.png)

　よって答えは84。これまでは高校数学の領域だ。

# コーナーケース

　今回は

```math
2x + y = 40\\
3x + 4y = 100
```

　を満たすようなxy（つまり両直線の交点）が求めるものであった。必ずしもそうだろうか？

　例えば、xを10円で売ってyを1円で売る、というような状況では、よほど材料に偏りがない限りxだけを作る方が合理的になる。以下のような状況である。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/ae6c7652-d112-9cdc-8168-a25f013eec22.png)

　また、yを作るのに大量の材料が必要である場合も、xだけを作る方が合理的になる。以下のような状況である。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/bef2c200-1869-8636-2509-5b6cbd46c395.png)

　しかしこれらは、日本語にすれば明白なように**そもそも悩む必要がない**。今後は、最初に示した問題のように、xとyをうまいバランスで組み合わせなければならない事例だけを考える。

# 行列で表現

　以上の問題を行列で表現する。

```math
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
\leq
\begin{pmatrix}
40 \\
100
\end{pmatrix}
\\
の条件下で、
\\
\begin{pmatrix}
3 & 3
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
を最大化せよ
```

　今回の問題では運よく

```math
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
=
\begin{pmatrix}
40 \\
100
\end{pmatrix}
\\
\begin{pmatrix}
x \\
y
\end{pmatrix}
=
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}^{-1}
\begin{pmatrix}
40 \\
100
\end{pmatrix}
```

　のときが最大値だったので、答えは、

```math
\begin{pmatrix}
3 & 3
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
\\
=
\begin{pmatrix}
3 & 3
\end{pmatrix}
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}^{-1}
\begin{pmatrix}
40 \\
100
\end{pmatrix}
\\
=
\begin{pmatrix}
3 & 3
\end{pmatrix}
\frac{1}{2\cdot 4-1\cdot 3}
\begin{pmatrix}
4 & -1 \\
-3 & 2
\end{pmatrix}
\begin{pmatrix}
40 \\
100
\end{pmatrix}
\\
=
\begin{pmatrix}
3 & 3
\end{pmatrix}
\frac{1}{5}
\begin{pmatrix}
4 & -1 \\
-3 & 2
\end{pmatrix}
\begin{pmatrix}
40 \\
100
\end{pmatrix}
\\
=3
\begin{pmatrix}
1 & 1
\end{pmatrix}
\frac{1}{5}
\begin{pmatrix}
4 & -1 \\
-3 & 2
\end{pmatrix}
20
\begin{pmatrix}
2 \\
5
\end{pmatrix}
\\
=12
\begin{pmatrix}
1 & 1
\end{pmatrix}
\begin{pmatrix}
4 & -1 \\
-3 & 2
\end{pmatrix}
\begin{pmatrix}
2 \\
5
\end{pmatrix}
\\
=12
\begin{pmatrix}
1 & 1
\end{pmatrix}
\begin{pmatrix}
3 \\
4
\end{pmatrix}
\\
=12\cdot7
\\
=84
```

　という行列計算により求められる。

# 基底の変換

　xy平面で考えるのはわかりやすいが、各直線が示すものの意味がわかりづらい。


```math
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
\leq
\begin{pmatrix}
40 \\
100
\end{pmatrix}
```

　これをそのままグラフで表現できないだろうか。

　つまり、

```math
\begin{pmatrix}
2  \\
3
\end{pmatrix}
と
\begin{pmatrix}
1 \\
4
\end{pmatrix}
```

　という2つのベクトルからなるグリッドを考える。このようなグリッドの単位を**基底**という。いくら伸ばされても斜めになろうとも、グリッドが同じ間隔で伸びていく限り、位置関係などは変わらない。順番なども自由に変えていいので、線形代数の世界ではわりと頻繁に行われる。

　さて、基底変換後のグラフは以下のようになる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/8cc60c27-04dc-e240-69b5-0c33e9dd7b17.png)

（x=0とy=0の線をわかりやすくするために太さを変えている）

　ここでの横軸、縦軸は商品の個数ではなく、材料aとbの使用量である。

　青い線は最大利益を表すが、意味合いとしては**商品単価×商品数**から、**商品単価×商品と材料の変換式×材料数**という変換を経ていることに注意である。

　つまり、当初のグラフではベクトル$\begin{pmatrix}3&3\end{pmatrix}$との内積は販売数を利益に変換する関数であり、それが最大となる$(x,y)=(12,16)$に作用させることにより総利益84を計算したが、基底変換後（むしろ順序としては変換前というべきだが）ではベクトル

```math
\begin{pmatrix}3&3\end{pmatrix}
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}^{-1}
=
\frac{3}{5}
\begin{pmatrix}
1 & 1 \\
\end{pmatrix}
```

　との内積は**材料を利益に変換する**関数である。それが最大となる$(a,b)=(40,100)$に作用させて総利益84を得る。こちらの図の方が、材料の限界と利益の関係を俯瞰しやすい。

# 視点を変える

　今までは**商品の利益を最大化する**という観点で問題を考えていた。ここで仕入コストについて考えてみる。当然、仕入値は小さければ小さい程良い。しかし材料を売る問屋はなるべく仕入れ値を高くしたいと考えている。問屋は自由に材料の単価を変えられるが、単価を上げすぎれば取引が成り立たなくなる。

　ここで問屋がスパイにより「この会社はXを3円、Yを3円で販売する計画であり、**それを超えるような仕入は行わない**」と知っていたらどうするか。XとYの商品価格はAとBの材料単価によって決まるので、これが成り立つギリギリまでAとBの価格を調整すればよい。このとき会社の利益＝売上－仕入値はゼロになり、この会社は何のために商売をしているのかという疑問は残るが、細かいことは気にしてはいけない。

- 商品Xは材料Aを2、材料Bを3必要とする
- 商品Yは材料Aを1、材料Bを4必要とする

　であったので、

```math
商品Xの仕入値 = 2a+3b\\
商品Yの仕入値 = a+4b
``` 

　となるので、この範囲を満たす$a,b$において$40a+100b$を最小化せよ、ということになる。

# 行列で表現

　さて、今度はこのように表現される。

```math
\begin{pmatrix}
2 & 3 \\
1 & 4
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
\geq
\begin{pmatrix}
3 \\
3
\end{pmatrix}
\\
の条件下で、
\\
\begin{pmatrix}
100 & 40
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
を最小化せよ
```

　最初の問題と比較してみよう。

　まず行列が

```math
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}
から
\begin{pmatrix}
2 & 3 \\
1 & 4
\end{pmatrix}
```

　になって、縦と横がひっくり返っている（転置）されていることに注意である。

　これをグラフ化すると以下のようになる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/a1ec9196-89f7-a12b-0e24-2042126c95b2.png)

　横軸は材料aの単価、縦軸は材料bの単価を示す。売値としてありえる範囲は水色（問屋としては、高ければ高いほどもうかるので、この領域であれば何円でも構わない）だが、会社としてはできるだけ安く買いたいので、価格は上図の赤丸になる。

　基底を変えてこのようにも表現できる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/338d5edb-1ed0-ff60-d0af-0dc5d67353c5.png)

　このとき、最小買値は

```math
\begin{pmatrix}
40 & 100 
\end{pmatrix}
\begin{pmatrix}
2 & 3 \\
1 & 4
\end{pmatrix}^{-1}
\begin{pmatrix}
3 \\
3
\end{pmatrix}
\\
=12
\begin{pmatrix}
2 & 5 
\end{pmatrix}
\begin{pmatrix}
4 & -3 \\
-1 & 2
\end{pmatrix}
\begin{pmatrix}
1 \\
1
\end{pmatrix}
\\
=84
```

　であり、当初の問題と全く同じ値が導かれる。というか、計算してみるとわかるが、**全く同じ計算**を行うことになる。

# 双対定理

　このように、会社が最大利益を得たい場合、そして問屋が（取引が成り立つ限りにおいて）売値をなるべく大きくしたい場合、両者が存在しえる領域は1点で交わり、最大売上＝最小買値となる。両者を[双対問題](https://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AF%BE%E5%95%8F%E9%A1%8C)といい、線形計画問題においては、主問題と最大値と補問題の最小値は一致することが知られている（双対定理）。

　改めて両者の値を比較してみる。

```math
主問題　84=
\begin{pmatrix}
3 & 3
\end{pmatrix}
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}^{-1}
\begin{pmatrix}
40 \\
100
\end{pmatrix}
\\
補問題　84 =
\begin{pmatrix}
40 & 100 
\end{pmatrix}
\begin{pmatrix}
2 & 3 \\
1 & 4
\end{pmatrix}^{-1}
\begin{pmatrix}
3 \\
3
\end{pmatrix}
```

　両者は完全な転置であることがわかる。

```math
\Bigl\{
\begin{pmatrix}
3 & 3
\end{pmatrix}
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}^{-1}
\begin{pmatrix}
40 \\
100
\end{pmatrix}
\Bigl\}^{T}
\\=
\begin{pmatrix}
40 & 100 
\end{pmatrix}
\begin{pmatrix}
2 & 3 \\
1 & 4
\end{pmatrix}^{-1}
\begin{pmatrix}
3 \\
3
\end{pmatrix}
```

　数学的に何の意味もない操作だが、以下のようにも書ける。

```math
84^{T} = 84
```

　もちろん**スカラー値の転置**という操作には何の意味もない（自分自身であることは自明である）。しかし、この記事の問題の例でいえば、売上を転置したら買値になる、と考えることもできる。（これは、算数においてみかんの個数をイメージするのと同じで、人間が勝手に数字に都合よく意味を与えているだけである）

　主問題では、$\begin{pmatrix}3&3\end{pmatrix}$との内積を$\begin{pmatrix}12&16\end{pmatrix}$なる座標に作用させて84を得た。また別の解き方では、$\frac{3}{5}\begin{pmatrix}1&1\end{pmatrix}$との内積を$\begin{pmatrix}40&100\end{pmatrix}$なる座標に作用させて84を得た。これは「真ん中」に位置する

```math
\begin{pmatrix}
2 & 1 \\
3 & 4
\end{pmatrix}^{-1}
```

　を左右どちらのベクトルに作用させるかという違いだけであり、本質的には何の違いもない。

　また、補問題では$\begin{pmatrix}40&100\end{pmatrix}$との内積を$\frac{3}{5}\begin{pmatrix}1&1\end{pmatrix}$という座標に計算させている。内積化関数（内積を作るようなベクトルを便宜上こう称する）と座標の関係が反対になっているが、行う計算は全く同じである。問題における意味では単価や材料数といった役割を与えられることがあるが、両者はどちらも内積化関数にもなりえるし、座標にもなりえる。あえて内積化関数とベクトルを区別する意味はあまりないことがわかる。

# 参考になったページ

[ORでわかる線形代数](http://www.orsj.or.jp/archive2/or60-12/or60_12_693.pdf)
[見積りで考える内積](https://qiita.com/7shi/items/03e9eb2c78360a5c1374)

# ソースコード

　使用言語はPython。

```python
import matplotlib.pyplot as plt
import numpy as np

delta = 0.025
lim = 40
xrange = np.arange(-lim*2, lim*2, delta)
yrange = np.arange(-lim*2, lim*2, delta)
X, Y = np.meshgrid(xrange,yrange)

#軸の設定
plt.axis([-0, lim, -0, lim])
plt.gca().set_aspect('equal', adjustable='box')

#描画
Z=2*X+Y-40
plt.contour(X, Y, Z, [0],colors='b')
Z=3*X+4*Y-100
plt.contour(X, Y, Z, [0],colors='b')
Z=X+Y-28
plt.contour(X, Y, Z, [0],colors='r')
plt.grid(which='major',color='black',linestyle='-')
plt.show()
```