こんにちは！しゅんです！
この記事では具体例を使って線形計画問題として定式化した最短経路問題の双対問題を求めます。
前回の記事で最短経路問題を整数計画問題として定式化して、それを線形緩和しても整数の最適解が得られることを紹介しました。てことで双対問題を求めたくなったので紹介したいと思います。
前回の記事はこちらから！
それではやっていきましょう！
普段は組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
最短経路問題を線形計画問題として定式化する
パラメータ：
\(V\) : 頂点集合
\(E\) : 辺集合
\(w_{ij}\) : 辺\((i,j)\)の重み
\(s \in V\) : 始点
\(t \in V\) : 終点
変数：
\(x_{ij} \) : 連続変数に緩和
定式化：
\( \min \;\;\; \sum\limits_{(i,j) \in E}w_{ij}x_{ij}\)
\(\;\text{s.t.}\;\;\;\sum\limits_{j \in V,(s,j) \in E}x_{sj} = 1\)
\(\;\;\;\;\;\;\;\;\; \sum\limits_{j \in V,(j,t) \in E}x_{jt} = 1\)
\(\;\;\;\;\;\;\;\;\; \sum\limits_{i \in V,(i,j) \in E}x_{ij} – \sum\limits_{k \in V, (j,k) \in E}x_{jk} = 0 \;\;\; (\forall j \in V/\{s,t\})\)
\(\;\;\;\;\;\;\;\;\; x_{ij} \geq 0 \;\;\; (\forall (i,j) \in E)\)
まず最初に最短経路問題を線形計画問題として定式化します。定式化の方法は前回の記事で説明しているのでここでは飛ばします。
前回の記事はこちらから！
具体例を使って考えてみる
上のグラフを使って考えていきたいと思います。
線形計画問題として定式化
まず最初に線形計画問題として定式化しましょう。分かりやすくするために\(\sum\)を使わずに記述してみます。
\(w_{s1}x_{s1}+w_{s2}x_{s2}+w_{13}x_{13}+w_{1t}x_{1t}+w_{23}x_{23}+w_{3t}x_{3t}\)
\(-x_{s1}-x_{s2} = -1\)
\(x_{1t}+x_{3t} = 1\)
\(x_{s1}-x_{1t}-x_{13} = 0\)
\(x_{s2}-x_{23} = 0\)
\(x_{13}+x_{23}-x_{3t} = 0\)
\(x_{s1},x_{s2},x_{13},x_{1t},x_{23},x_{3t} \geq 0\)
この後説明しますが、とある理由で一番上の始点\(s\)に関する制約式は両辺を\((-1)\)倍しておきます。
行列・ベクトルを使って表記する
\(\min \;\;\; c^\top x\)
\(\;\text{s.t.}\;\;\;Ax=b \)
\(\;\;\;\;\;\;\;\;\; x \geq 0\)
\(\max \;\;\; b^\top y\)
\(\;\text{s.t.}\;\;\;A^\top y \leq c \)
標準形の線形計画問題とその双対問題は上のような関係です。行列、ベクトルを使って表されているので今回の目的関数、制約条件も行列、ベクトルを使って表しましょう。
まず目的関数は以下のように表せます。
\(\begin{pmatrix}w_{s1},w_{s2},w_{13},w_{1t},w_{23},w_{3t}\end{pmatrix} \begin{pmatrix}x_{s1}\\x_{s2}\\x_{13}\\x_{1t}\\x_{23}\\x_{3t}\end{pmatrix}\)
よって\(c,x\)を下のようにすれば標準形の線形計画問題の形と合わせられます。
\(c=\begin{pmatrix}w_{s1}\\w_{s2}\\w_{13}\\w_{1t}\\w_{23}\\w_{3t}\end{pmatrix}, x=\begin{pmatrix}x_{s1}\\x_{s2}\\x_{13}\\x_{1t}\\x_{23}\\x_{3t}\end{pmatrix}\)
次に制約条件を行列、ベクトルを使って表すと以下のようになります。
\(\begin{pmatrix}-1&-1&0&0&0&0\\0&0&0&1&0&1\\1&0&-1&-1&0&0\\0&1&0&0&-1&0\\0&0&1&0&1&-1\end{pmatrix} \begin{pmatrix}x_{s1}\\x_{s2}\\x_{13}\\x_{1t}\\x_{23}\\x_{3t}\end{pmatrix} = \begin{pmatrix}-1\\1\\0\\0\\0\end{pmatrix}\)
よって\(A,b\)を下のようにすれば標準形の線形計画問題の形と合わせられます。
\(A = \begin{pmatrix}-1&-1&0&0&0&0\\0&0&0&1&0&1\\1&0&-1&-1&0&0\\0&1&0&0&-1&0\\0&0&1&0&1&-1\end{pmatrix}, b= \begin{pmatrix}-1\\1\\0\\0\\0\end{pmatrix}\)
双対問題を作る
それでは公式に従って双対問題を作ってみましょう。
\(\min \;\;\; c^\top x\)
\(\;\text{s.t.}\;\;\;Ax=b \)
\(\;\;\;\;\;\;\;\;\; x \geq 0\)
\(\max \;\;\; b^\top y\)
\(\;\text{s.t.}\;\;\;A^\top y \leq c \)
\(c=\begin{pmatrix}w_{s1}\\w_{s2}\\w_{13}\\w_{1t}\\w_{23}\\w_{3t}\end{pmatrix}, x=\begin{pmatrix}x_{s1}\\x_{s2}\\x_{13}\\x_{1t}\\x_{23}\\x_{3t}\end{pmatrix}\)
\(A = \begin{pmatrix}-1&-1&0&0&0&0\\0&0&0&1&0&1\\1&0&-1&-1&0&0\\0&1&0&0&-1&0\\0&0&1&0&1&-1\end{pmatrix}, b= \begin{pmatrix}-1\\1\\0\\0\\0\end{pmatrix}\)
双対問題で使う変数\(y\)を以下のように定義します。
\(y = \begin{pmatrix}y_s\\y_t\\y_1\\y_2\\y_3\end{pmatrix}\)
まず目的関数は\(b^\top y\)なので以下のようになります。
\(b^\top y = \begin{pmatrix}-1&1&0&0&0\end{pmatrix}\begin{pmatrix}y_s\\y_t\\y_1\\y_2\\y_3\end{pmatrix}=y_t-y_s\)
制約条件は以下のように表せます。
\(\begin{pmatrix}-1&0&1&0&0\\-1&0&0&1&0\\0&0&-1&0&1\\0&1&-1&0&0\\0&0&0&-1&1\\0&1&0&0&-1\end{pmatrix}\begin{pmatrix}y_s\\y_t\\y_1\\y_2\\y_3\end{pmatrix}=\begin{pmatrix}y_1-y_s\\y_2-y_s\\y_3-y_1\\y_t-y_1\\y_3-y_2\\y_t-y_3\end{pmatrix} \leq \begin{pmatrix}w_{s1}\\w_{s2}\\w_{13}\\w_{1t}\\w_{23}\\w_{3t}\end{pmatrix}\)
まとめるとこの最短経路問題の双対問題は以下のようになります。
目的関数(最大化) :
\(y_t-y_s\)
制約条件 :
\(y_1-y_s \leq w_{s1}\)
\(y_2-y_s \leq w_{s2}\)
\(y_3-y_1 \leq w_{13}\)
\(y_t-y_1 \leq w_{1t}\)
\(y_3-y_2 \leq w_{23}\)
\(y_t-y_3 \leq w_{3t}\)
より一般的に考える
双対問題：
\(\max \;\;\; y_t-y_s\)
\(\;\;\; \text{s.t} \;\;\; y_j-y_i \leq w_{ij} \;\;\; (\forall (i,j) \in E)\)
但し\(E\)は辺集合
それでは最後により一般的な問題の双対問題をどう表せるか考えてみましょう。少し難しいので上の具体例を見ながら読むと理解しやすいと思います。まず\(b\)について考えてみます。
ベクトル\(b\)の要素数は主問題の制約条件の個数だけあります。主問題の制約条件はグラフの頂点数個だけあります。そして\(b\)の各要素は
・始点\(s\)の制約式に対応する要素は-1
・終点\(t\)の制約式に対応する要素は1
・それ以外の頂点の制約式に対応する要素は0
となります。したがって双対問題の目的関数は\(y_t-y_s\)となります。
（\(s,t\)以外の頂点\(i\)に対応する変数\(y_i\)の係数が0だから。）
次に\(A\)について考えてみましょう。実は\(A\)はグラフの接続行列の各要素を\((-1)\)倍したものになっています。
始点\(s\)に関する制約式を(-1)倍したのは係数行列を接続行列とするためです。
よって各行の要素は各頂点に関する情報を持っており、その頂点から出る辺だったら-1、向かってくる辺だったら1となっています。また各列の要素は各辺に関する情報を持っており、例えば辺\((i,j)\)の列のときは頂点\(i\)の行の要素が-1、頂点\(j\)の行の要素が1となっています。
接続行列についてはこちらの記事で解説しています！
したがって\(A\)を転置させると各行が辺に関する情報を表しており、辺\((i,j)\)の行の要素は頂点\(i\)の列が-1、頂点\(j\)の列が1となります。よって制約式の左辺は
\(y_j-y_i\)
となります。制約式の右辺は\(c\)の要素なので最後に\(c\)について考えます。\(c\)は主問題の目的関数の係数ベクトルですが、要素数はグラフの辺の数だけあります。そのため辺\((i,j)\)の要素\(w_{ij}\)なので先ほどの制約式の右辺は\(w_{ij}\)となります。
よって双対問題における辺\((i,j)\)に関する制約式は
\(y_j-y_i\leq w_{ij}\)
となります。この制約式がグラフ中の全ての辺に対して存在します。以上のことから最短経路問題を線形計画問題として定式化とき、その双対問題は以下のように表すことができます。
\(\max \;\;\; y_t-y_s\)
\(\;\;\; \text{s.t} \;\;\; y_j-y_i \leq w_{ij} \;\;\; (\forall (i,j) \in E)\)
但し\(E\)は辺集合
おわりに
いかがでしたか。
今回の記事では最短経路問題について解説していきました。
今後もこのような数理最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
