s t 1, 2,..., 10 s t a, b,..., k t s 1, 2,..., 10 1 a, b,..., k 1 s t ts 1 0 ( 2.25) ½ ¾ ½¼ x 1j = 1 x 2c = 1 x 3e = 1

この問題は最大マッチング問題と呼ばれるものです．マッチングとはグラフに属する枝の集合 で，マッチングに属する枝は互いに始点も終点も共有しません．従業員とプロジェクトを端点と見 なし，可能な組合わせを枝と見なして 2 部グラフをつくると．プロジェクトの担当問題は，このグ ラフのマッチングの数を最大にする問題と考えることができます1_． 可能な組合わせを表す 2 部グラフを作ってみましょう．これは，図表 2.24 となります．つぎに この 2 部グラフを埋め込んだネットワークを作ります．あらたに端点 s と t を導入します．端点 1, 2, . . . , 10へ s 枝を張り，端点 t から端点 a, b, . . . , k へ枝を張ります．最後に t から s へ枝を張り ます．端点 1, 2, . . . , 10 に供給が 1 単位あり，端点 a, b, . . . , k に需要が 1 単位あるとします．また 端点 s と t には，それぞれ 10 単位の需要と 11 単位の供給があるとします．枝にかかる輸送費用 は，枝 ts 間のみ 1 をつけ，ほかはすべて 0 としましょう．これで輸送問題として定式化すること ができます (図 2.25)． 図表 2.24 担当可能な組合わせを表す 2 部グラフ 1 2 3 4 5 6 7 8 9 10 a b d e f g h i j k 輸送問題として定式化し，解いた結果， x1j= 1 x2c= 1 x3e= 1 x4s= 1 x5g= 1 x6i = 1 x7d= 1 x8h= 1 x9f= 1 x10k= 1 xta= 1 xtb= 1 xts= 9 を得ました．これを図示したのが図 2.26 です．今，同時進行できるプロジェクトの最大数は 9 で あることがわかりました．当面，担当者のいないプロジェクト a と b を発注した企業には，納期 の延長交渉をしなくてはなりません． ツアーと添乗員 旅行会社が，7 月に 8 つのツアーを計画しています．各ツアーのスケジュールは，2.27 の通り です． 1_{参考までに，マッチングと被覆の関係を述べます．一般のグラフにおいて，被覆 (cover) とはグラフの端点の集合で，} グラフ上の任意の枝は，必ず被覆に属する端点が始点もしくは終点となっている， とう性質を持ちます．同じグラフ上で，マッチング M に属する枝の数 (jMj) と，被覆 C に属する端点の数 (jCj) のあい だにはjCj ≥ jMj が成り立ちます．2 部グラフにおいては，最大マッチング M∗と最小被覆 C∗にかんして，jC∗j = jM∗j が成り立ちます．

2.6. 割当や組合わせを決める問題 73 図表 2.25 担当可能な組合わせを表す 2 部グラフを埋め込んだグラフ t 1 2 3 4 5 6 7 8 9 10 a b d e f g h i j k s 図表 2.26 プロジェクトの担当者 t 1 2 3 4 5 6 7 8 9 10 a b d e f g h i j k s 図表 2.27 ツアーのスケジュール ツアー名 1 2 3 4 5 6 7 8 出発日 7/2 7/2 7/6 7/9 7/12 7/12 7/15 7/20 帰着日 7/13 7/9 7/13 7/11 7/19 7/14 7/19 7/23 期間 12 8 7 3 8 3 5 4

図表 2.28 ツアーの順序関係 (左) と 2 部グラフを埋め込んだネットワーク (右) 1 2 3 4 5 6 7 8 1’ 2’ 3’ 4’ 5’ 6’ 7’ 8’ 1 2 3 4 5 6 7 8 1’ 2’ 3’ 4’ 5’ 6’ 7’ 8’ 9 10 [-1] -1 1 8 _-8 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 各ツアーには添乗員が同行することになっています．ツアー i の帰着日がツアー j の出発日よ り前であれば，i と j に同じ添乗員を割り当てることができます．ただし，1 週間以上のツアーに 同行した場合，次のツアーまで少なくとも 2 日以上の間隔を空けるというルールがあります．この 旅行会社の７月のツアーのためには，少なくとも何名の添乗員が必要でしょうか． この問題も添乗員とツアーの最大マッチング問題と考えることができます．まず，各ツアー間 の前後関係を 2 部グラフで表してみましょう．端点 i から端点 j′に枝が存在しているのは，ツアー iに同行した添乗員がツアー j′に同行できることを意味しています． 2部グラフにもとづいて，ツアーの順序関係を輸送問題型のネットワークとして表してみます． 8の需要を持つダミーの端点 9，-8 の供給を持つダミーの端点 10 を導入します．端点 i(i= 1, . . . , 8) は供給 1 を持ち，端点 i’(i’= 1, . . . , 8) は需要 1 を持ちます．費用は，枝 109 のみに −1 かかるもの とします．これを輸送問題とみて，最小費用を求めると，添乗員の最小人数がわかります．

2.7. 参考：最大流問題 75 min −x109 s.t. x18′+ x19 = 1 x25′ + x26′ + x27′+ x28′+ x29 = 1 x38′+ x39 = 1 x45′ + x46′ + x47′+ x49′+ x49 = 1 x59 = 1 x67′+ x68′+ x69 = 1 x78′+ x79 = 1 x89 = 1 x101′ = 1 x102′ = 1 x103′ = 1 x104′ = 1 x25′ + x45′ + x105′ = 1 x26′ + x46′ + x106′ = 1 x47′ + x67′ + x107′ = 1 x18′+ x28′+ x38′+ x68_∑′ + x78′ + x108′ = 1 8 i=1xi9+ x109 = 8 ∑8′ j=1′x10j+ x109 = 8 xij≥ 0 すべての ij これを解くと， x18′ = 0 x19= 1 x25′ = 1 x26′ = 0 x27′ = 0 x28′ = 0 x29= 0 x38′ = 0 x39= 1 x45′ = 0 x46′ = 1 x47′ = 0 x49′ = 0 x49= 0 x59= 1 x67′ = 1 x68′ = 0 x69= 0 x78′ = 1 x79= 0 x89= 1 x101′ = 1 x102′ = 1 x103′ = 1 x104′ = 1 x105′ = 0 x106′ = 0 x107′ = 0 x108′ = 0 x109= 4 を得ました．xij′ = 1となるツアーの組をみると，2–5，4–6，6–7，7–8 です．これは，4 のツ アーに同行した添乗員は，6 のツアーにも同行できることを意味するので，一人の添乗員によって 4–6–7のツアーをカバーできることがわかりました．結局，掛け持ちができないツアー (1，3) の 数とあわせて 4 人の添乗員がいれば，7 月のツアーをすべてまかなうことができるのです． 一般的に，n 個のツアーがあり，2 部グラフのマッチング M の個数が|M| だったならば，必要 な添乗員の数は n −|M| です．添乗員の数を最小にするには，マッチングを最大にすればよいとい うのは，この関係から導かれます．

2.7

参考：最大流問題

輸送問題においては需要と供給があらかじめ与えられており，ネットワークを動く量は総量にお いて決まっています．この節で扱う最大流問題は，枝ごとに流量の上限が決まっている場合，ネッ トワークに流せる最大の流量を求めるものです．

図表 2.29 パイプライン

s

t

<12>

<10>

<3>

<2>

<5>

<8>

<4>

<9>

<11>

<7>

1

2

3

4

5

6

2.7.1

パイプラインの例

図 2.29 のようなパイプラインがあります．パイプラインを表す各枝には，そのパイプに単位時 間当たりに流せる最大の流量が決まっていて，⟨·⟩ にその値が示してあります． 端点 s から端点 t へオイルを流すとして，最大どれくらいの量を流すことができるでしょうか． この問題もやはり線形計画問題として定式化することができます．端点 t から端点 s へ仮想的 なパイプを導入して，ネットワークを修正します．この枝 ts の流量に上限はなく，流量 1 単位当 たりの費用を 1 とします (図表 2.30 参照)．このネットワークにおいて，目的関数を xtsとおいて， 最大化問題を解けば，最大流が得られる．通常の輸送問題と違って，需要と供給量がない変わりに， 枝に流量の上限が与えられています．定式化すると，枝の流量の上限は決定変数 (枝の流量) の上 限制約として制約式に現れます． 図表 2.30 パイプラインに仮想的なパイプを導入

s

t

<12>

<10>

<3>

<2>

<5>

<8>

<4>

<9>

<11>

<7>

[1]

1

2

3

4

5

6

2.7. 参考：最大流問題 77 max xts s.t. −xts+ xs1+ xs2= 0 −xs1+ x13+ x14= 0 −xs2+ x26= 0 −x13+ x35= 0 −x14+ x45+ x46= 0 −x35− x45+ x5t= 0 −x46− x26+ x6t= 0 −x5t− x6t+ xts= 0 xs1≤ 12, xs2≤ 8 x13≤ 5, x14≤ 2 x26≤ 7, x35≤ 3 x45≤ 4, x46≤ 11 x5t≤ 10, x6t≤ 9 xij ≥ 0, ij ∈ E (2.9) 最適解は xs1= 5 xs2= 7 x13= 3 x14= 2 x26= 7 x35= 3 x45= 2 x46= 0 x5t= 5 x6t= 7 xts= 12 となりました．

2.7.2

最小カット

問題 (2.9) は線形計画問題です．では，このその双対問題はどうなっているのでしょうか． 問題 (2.9) の双対問題： min 12ξs1+ 8ξs2+ 5ξ13+ 2ξ14+ 7ξ26+ 3ξ35 +4ξ45+ 11ξ46+ 10ξ56+ 10ξ5t+ 9ξ6t s.t. −λs+ λt≥ 1 λs− λ1+ ξs1≥ 0 λs− λ2+ ξs2≥ 0 λ1− λ3+ ξ13≥ 0 λ1− λ4+ ξ14≥ 0 λ2− λ6+ ξ26≥ 0 λ3− λ5+ ξ35≥ 0 λ4− λ5+ ξ45≥ 0 λ4− λ6+ ξ46≥ 0 λ5− λt+ ξ5t≥ 0 λ6− λt+ ξ6t≥ 0 ξij≥ 0, ij ∈ E (2.10)

双対問題 (2.10) において，λi (i = s, 1, 2, . . . , 6, t)は自由変数であす．ここで次の事実に注意し ましょう．今，最適解が λ∗i (i = s, 1, 2, . . . , 6, t) と ξ∗ij (ij∈ E) であったとして，任意の実数 δ に より新たに λ†_i= λ∗_i+ δ, i= s, 1, 2, . . . , 6, t をつくります．そうすると，λ†i (i = s, 1, 2, . . . , 6, t) と ξ∗ij (ij∈ E) も制約を満たし，かつ目的関 数値が同じなので最適解です．このままでは無数に最適解が存在してしまうので，λs= 0 と固定 します． (2.10)の制約式はすべて不等式です．したがって，最適解 (λ∗s, λ∗1, . . . , λt∗, ξ∗s1, . . . , ξ∗6t)が厳密 な不等式を満たす場合，例えば λ∗1− λ∗4+ ξ∗14> 0 となる可能性があります．しかし目的関数の性質 (ξijの値をなるべく小さくする) より，これが起 こり得ないことはすぐにわかります．したがって最適解を代入すると，制約式はすべて等号で成り 立つはずです．以上のことから，(2.10) は min 12ξs1+ 8ξs2+ 5ξ13+ 2ξ14+ 7ξ26+ 3ξ35 +4ξ45+ 11ξ46+ 10ξ56+ 10ξ5t+ 9ξ6t s.t. −λs+ λt= 1 λs− λ1+ ξs1= 0 λs− λ2+ ξs2= 0 λ1− λ3+ ξ13= 0 λ1− λ4+ ξ14= 0 λ2− λ6+ ξ26= 0 λ3− λ5+ ξ35= 0 λ4− λ5+ ξ45= 0 λ4− λ6+ ξ46= 0 λ5− λt+ ξ5t= 0 λ6− λt+ ξ6t= 0 λs= 0 ξij≥ 0, ij ∈ E (2.11) と等価です． 次に，s から t へのすべての経路を考えましょう．経路をすべて列挙すると， 1番目: s—1—3—5—t 2番目: s—1—4—5—t 3番目: s—1—4—6—t 4番目: s—2—6—t でとなります．各径路に含まれる枝の集合を以下のように定義します． P1={s1, 13, 35, 5t} P2={s1, 14, 45, 5t} P3={s1, 14, 46, 6t} P4={s2, 26, 6t}

2.8. 参考：最短経路問題 (Shortest Path Problem) 79 1番目の経路を例にとりましょう．双対変数の制約式は主問題の変数に対応していることから，1 番目の経路に含まれる枝に関係する双対問題の制約は， λs− λ1+ ξs1= 0 λ1− λ3+ ξ13= 0 λ3− λ5+ ξ35= 0 λ5− λt+ ξ5t= 0 となります．すべての式の両辺を足し合わせると， −λs+ ∑ ij∈P1 ξij− λt= 0 を得ました．λs= 0より λt= 1なので，結局 ∑ ij∈P1 ξij= 1 でなければなりません．この関係を使うと，双対問題は以下のように書き換えることができます． min 12ξs1+ 8ξs2+ 5ξ13+ 2ξ14+ 7ξ26+ 3ξ35 +4ξ45+ 11ξ46+ 10ξ56+ 10ξ5t+ 9ξ6t s.t. ∑ ij∈Pk ξij = 1, k= 1, 2, 3, 4 ξij≥ 0, ij ∈ E (2.12) この問題は，すべての経路上で最も流量が制約される場所 (ボトルネック) を探す問題と解釈でき ます．これは最小カット問題とよばれるものです． 双対問題 (2.10) の最適解: λs= 1 λ1= 1 λ2= 1 λ3= 1 λ4= 0 λ5= 0 λ6= 0 λt= 0 ξ13= 0 ξ14= 1 ξ26= 1 ξ35= 1 ξ45= 0 ξ46= 0 ξ56= 0 ξ5t= 0 ξ6t= 0 ξs1= 0 ξs2= 0 最適値は 12 です． 演習問題2.12 7種類のチョコレートをそれぞれ3個づつ作った．このチョコレートを5つの箱に詰めるとする． 箱に入れることのできるチョコレートの数はそれぞれ6，4，5，4，3個である(チョコレートの 大きさに差はない)．なるべくバラエティに富んでいた方がよいので，ひとつの箱に同じ種類の チョコレートは入れたくない．そのような詰め方が可能かどうか，最大流問題として定式化する ことで判定せよ．

2.8

参考：最短経路問題

(Shortest Path Problem)

仕事や遊びで旅行をするとき，目的地までどのようなルートをとるかを考えなくてはなりませ ん．鉄道を使うのか，自動車で行くか，あるいは飛行機か．交通手段が決まったとして，鉄道であ

れば路線と乗り換え駅を考えなくてはいけません．自動車であっても，高速道を使うかどうか，ど の道を通るか，などについて，様々な条件を考慮して選択することになります．実際の旅行などは， 予算や興味の対象を考慮してルートを選択することになるでしょう． この節では，ルート選択を “距離” が最短になるように選ぶ問題を考えます．すなわち，ネット ワークの枝に，何らかの意味で端点間の遠近の度合を表す “ 距離” が与えられているものとして， 2つの相異なる端点間の距離を最短で結ぶような経路を求めるということです．“距離” として考え られるものには，例えば，地理上の距離，交通費，移動時間などが挙げられます． A地点から B 地点まで移動することを考えます．両地点間の移動に利用できる交通網は図 2.31 のネットワークによって表現することができます．枝上に与えられた数字は，その枝で表される交 通を利用した際の時間を表すとします．最短時間の移動経路はどのような経路になるでしょうか? 図表 2.31 A 地点と B 地点間の交通網 2 4 1 6 3 5 1 7 3 6 10 2 8 2 5 2 最初に，輸送問題として定式化してみましょう． この問題を輸送問題の枠組で解くには，A 地点に供給量として 1 を，B 地点に需要量として 1 を与えます．そして，枝上の時間を，1 単位の輸送にかかる費用とみなして，最小費用輸送問題と して定式化すればよいのです．最適解において 1 単位の物流が存在する経路が最短時間で移動でき る経路です．2.5 節で示したように，この種の輸送問題は，最適解では輸送料がどの枝でも必ず整 数 (この場合は 1) になることを思い出してください． 最短経路を求める問題は最小費用を目的関数とする輸送問題として考えることができることを 示しました．あとは線形計画問題を適当なソルバで解けばよいことになります．しかし最短経路問 題の解法は，LP ばかりではありません．例えばダイクストラ (Dijkstra) 法などのより効率的な解 法が存在するのです． 端点の集合 V ={s, 1, 2, . . . , n} と枝の集合 E，および枝 ij ∈ E の距離 dij> 0が与えられたと とき，以下の手続きを用いて，端点 s から他の端点 j への最短経路を求めることができます． [ダイクストラ法のアルゴリズム：] ステップ 1 初期化:

2.8. 参考：最短経路問題 (Shortest Path Problem) 81 以下のように初期値を設定する． vs= 0 vj=∞, j ∈ V, j ̸= s M={s} N=∅ ステップ 2 端点の選択： Mの中から，最小のラベルを持つ端点 i を選び出す． vi= min j∈M{vj} ステップ 3 Mと N の更新： N← N ∪ {i} M← M/{i} ステップ 4 ラベル vjの更新： すべての j∈ V/M について，ij ∈ E が存在し，vi+ dij< vjならば， vj← vi+ dij M← M ∪ {j} とする． ステップ 5 終了判定： M=∅ なら終了する．そうでなければ，ステップ 2 へ． ダイクストラ法が終了したときのラベル dj が，s から j への最短距離を与えます．図 2.31 の ネットワークに対してダイクストラ法を適用した際の途中経過を表 2.32 にまとめました． 次に, 一般的な動的計画法 (dynamic programming, DP) による解法を見ることにします2_． 端点の集合を V = 1, 2, . . . , n, t とします．端点 t が目標とする端点です (図 2.31 では，端点 6)． 端点 i から t まで，n −k ステップで到達する場合の最短距離を Jk(i)で表します．k = 0, 1, . . . , n − 1 です．そうすると，Jk(i)は以下の関係を満たすものとして定義することができます3． { Jk(i) = minj=1,...,n[dij+ Jk+1(j)], k= 0, 1, . . . , n − 2; i = 1, . . . , n Jn−1(i) = ait, i= 1, . . . , n (2.13) ここで，dijは，枝 ij の距離を表します．また dii= 0とおきます． k= n − 1から 0 にむかって，(2.13) を後ろ向きに計算 (後退計算) することで，DP を解くこ とができます．実際に，図 2.31 に適用してみましょう． 2_{ダイクストラ法も DP の一種と考えることができます} 3_{(2.13)の 1 本目の式は再帰方程式と呼ばれます．}

図表 2.32 ダイクストラ法の適用例

初期化 step 1 v1= 0, vj=∞, j = 2, 3, 4, 5, 6

M={1}, N = {∅}

反復 1 step 2 minj_∈M{vj} = v1= 0 端点 1 を選択

step 3 M={∅}, N = {1}

step 4 端点 2: min{v0+ d12, v2} = min{0 + 1, ∞} = 1 ラベルを更新

端点 3: min{v0+ d13, v3} = min{0 + 7, ∞} = 7 ラベルを更新

M={2, 3}

step 5 M̸= ∅ なので step 2 へ

反復 2 step 2 minj∈M{vj} = min{v2, v3} = min{1, 7} = 1 端点 2 を選択

step 3 M={3}, N = {1, 2}

step 4 端点 3: min{v2+ d23, v3} = min{1 + 3, 7} = 4 ラベルを更新

端点 4: min{v2+ d24, v4} = min{1 + 6, ∞} = 7 ラベルを更新

端点 5: min{v2+ d25, v5} = min{1 + 10, ∞} = 11 ラベルを更新

M={3, 4, 5}

step 5 M̸= ∅ なので step 2 へ

反復 3 step 2 minj∈M{vj} = min{v3, v4, v5} = min{4, 7, 11}=4 端点 3 を選択

step 3 M={4, 5}, N = {1, 2, 3}

step 4 端点 4: min{v3+ d34, v4} = min{4 + 2, 7} = 6 ラベルを更新

端点 5: min{v3+ d35, v5} = min{4 + 8, 11} = 11 ラベルを更新しない

M={4, 5}

step 5 M̸= ∅ なので step 2 へ

反復 4 step 2 minj_∈M{vj} = min{v4, v5} = min{6, 11}=6 端点 4 を選択

step 3 M={5}, N = {1, 2, 3, 4}

step 4 端点 5: min{v4+ d45, v5} = min{6 + 2, 11} = 8 ラベルを更新

端点 6: min{v4+ d46, v6} = min{6 + 5, ∞} = 11 ラベルを更新

M={5}

step 5 M̸= ∅ なので step 2 へ

反復 5 step 2 minj∈M{vj} = min{v5, v6} = min{8, 11}=8 端点 5 を選択

step 3 M={6}, N = {1, 2, 3, 4, 5}

step 4 端点 6: min{v5+ d56, v6} = min{8 + 2, 11} = 10 ラベルを更新

M={6}

step 5 M̸= ∅ なので step 2 へ

反復 6 step 2 minj∈M{vj} = min{v6} = 10 端点 6 を選択

step 3 M={∅}, N = {1, 2, 3, 4, 5, 6} step 4 M={∅}

step 5 M=∅ なので終了

結果 v1= 0, v2= 1, v3= 4, v4= 6, v5= 8, v6= 10

2.8. 参考：最短経路問題 (Shortest Path Problem) 83 k= 4 (1ステップで t に到達する場合)： J4(4) = 5 J4(5) = 2 k= 3 (2ステップで t に到達する場合)： J3(5) = min j=1,...,n{d5j+ J4(j)} = d55+ J4(5) = 0 + 2 = 2 J3(4) = min{d44+ J4(4), d45+ J4(5)} = {0 + 5, 2 + 2} = 4 J3(3) = min{d34+ J4(4), d35+ J4(5)} = {2 + 5, 8 + 2} = 7 J3(2) = min{d24+ J4(4), d25+ J4(5)} = {6 + 5, 10 + 2} = 11 k= 2 (3ステップで t に到達する場合)： J2(5) = min{d55+ J3(5)} = 0 + 2 = 2 J2(4) = min{d44+ J3(4), d45+ J3(5)} = {0 + 4, 2 + 2} = 4 J2(3) = min{d33+ J3(3), d34+ J3(4), d35+ J3(5)} = {0 + 7, 2 + 4, 8 + 2} = 6 J2(2) = min{d22+ J3(2), d23+ J3(3), d24+ J3(4), d25+ J3(5)} ={0 + 11, 3 + 7, 6 + 4, 10 + 2} = 10 J2(1) = min{d12+ J3(2), d13+ J3(3)} = min{1 + 11, 7 + 7} = 12 k= 1 (4ステップで t に到達する場合)： J1(5) = min{d55+ J2(5)} = 0 + 2 = 2 J1(4) = min{d44+ J2(4), d45+ J2(5)} = {0 + 4, 2 + 2} = 4 J1(3) = min{d33+ J2(3), d34+ J2(4), d35+ J2(5)} = {0 + 6, 2 + 4, 8 + 2} = 6 J1(2) = min{d22+ J2(2), d23+ J2(3), d24+ J2(4), d25+ J2(5)} ={0 + 10, 3 + 6, 6 + 4, 10 + 2} = 9 J1(1) = min{d11+ J2(1), d12+ J2(2), d13+ J2(3)} = min{0 + 12, 1 + 10, 7 + 6} = 11 k= 0 (5ステップで t に到達する場合)： J0(5) = min{d55+ J1(5)} = 0 + 2 = 2 J0(4) = min{d44+ J1(4), d45+ J1(5)} = {0 + 4, 2 + 2} = 4 J0(3) = min{d33+ J1(3), d34+ J1(4), d35+ J1(5)} = {0 + 6, 2 + 4, 8 + 2} = 6 J0(2) = min{d22+ J1(2), d23+ J1(3), d24+ J1(4), d25+ J1(5)} ={0 + 9, 3 + 6, 6 + 4, 10 + 2} = 9 J0(1) = min{d11+ J1(1), d12+ J1(2), d13+ J1(3)} = min{0 + 11, 1 + 9, 7 + 6} = 10 計算結果をまとめると図 2.33 となります．横軸にステップ数，縦軸に端点を取りました．図の 黒い丸の上にある数字は Jk(i)の値です．端点 2 からの最短径路を知るには，k = 0 で i = 2 の場 所を見ます．この矢印をたどっていくと，2(—2)—3—4—5—6 が最短のルートであることがわか ります．端点 1 から 6 までの最短距離が，ダイクストラ法で求めた値 (10) と等しいことを確認し てください．

図表 2.33 DP によって解いた結果 k i 1 2 3 4 1 2 3 4 5 6 2 2 2 2 4 4 4 5 7 6 6 9 11 0 4 6 9 10 2 10 11 10 例題 2.13 図書館で蔵書を収容するために新しい棚を設置することになりました．この蔵書の内訳は，4 イン チの高さが 200 冊，8 インチが 100 冊，12 インチが 80 冊です．本棚は，棚の高さに応じた種類が あり，4 インチ，8 インチ，12 インチの 3 種類を選択できます．当然ながら 8 インチの棚には 4 イ ンチの本も収納できるし，12 インチであれば，全ての本を収納することが可能です．全ての本の 厚さは 0.5 インチで一定であると仮定します．本一冊あたりの保管費用はその本が占める面積 (棚 の高さ× 本の厚み) に比例し，単位面積当り 5 ドルかかります．また，本棚はどの種類も 1 つの価 格は同じで，2300 ドルです．設置費用と保管費用の合計が最小になるような棚の高さの組合わせ はどのようになるでしょうか． [解答例] 図 2.34 で表される最短経路問題を解くと最適な棚の高さの組合わせが得られます．ただし，枝 の距離を設置コストと保管費用の和としています．すなわち， 枝 0 4 のコスト = 2300 + 4× 0.5 ∗ 200 枝 0 8 のコスト = 2300 + 8× 0.5 ∗ (200 + 100) 枝 0 12 のコスト = 2300 + 12× 0.5 ∗ (200 + 100 + 80) 枝 4 8 のコスト = 2300 + 8× 0.5 ∗ 100 枝 4 12 のコスト = 2300 + 12× 0.5 ∗ (100 + 80) 枝 8 12 のコスト = 2300 + 12× 0.5 ∗ 80