— つながりを見る 第 2 章ネットワーク構造

49

第2_{章 ネットワーク構造}

— _{つながりを見る}

網目状に何かが互いに繋がっているものを，ネットワークといいます．道路網，

通信網などはが代表的なネットワークです．要素をつなぐものが目に見えなくて も，ネットワークを用いてその構造を記述できる場合があります．たとえば，工 程の前後関係とか，人やモノの組み合わせなどが挙げられます．ネットワークの 性質をうまく使うことで，問題を効率的に解いたり，モデルをわかりやすく表現 することが可能になります．

2.1 _{再びクッキー屋}

2.1.1 だれがどこでつくるか

模擬店で販売するクッキーをつくるのに，サークルの部員の部屋を使う予定です．部屋を提供 してくれる部員だけにつくらせるのは不公平なので，ほかの部員も手伝いに行くことになっていま す．あなたは責任者として，だれがどこへ手伝いに行くのか決めなくてはいけません．

まず，クッキー作りに使える部屋は3つあります．1つは自宅住まいの学生のものなので広さ に余裕があり，6人が同時に作業できます．ほかの二つは下宿生の部屋なので手伝いは3人までが 限度です．

部員が全部で15人いて，そのうち部屋の提供者3名を除く12名を割り振るにあたっては次の ことを考慮しなければなりません．

• 各製作場所に，必要な人数がいなければならない．

• できるだけ，距離的に近い場所に割り振るようにしなければならない．

距離については，どのような基準をとるかが悩ましいところです．たとえば，もっとも移動距離が 長い人を評価の目安にするか，あるいは全員の平均的な距離を考えるかで，結果は変わってくるこ とでしょう．とりあえず，もっとも簡単でかつ部員に説明のしやすい「平均距離最小化」の基準で 割り振りを考えることにしました．

対象の部員に番号をつけて，3つの製造場所A，B，Cまでの距離を計算したところ，表2.1の ようになりました(部員の部屋と製造場所の位置関係は図表2.2参照)．さて，だれをどこに割り振 るべきでしょうか?

2.1.2 素朴な方法

最初は素朴な方法で考えてみます．Aの定員が多いので，まずここから埋めていくことにしま す．Aから距離の近い部員を6人選びます．残った6人から，今度はBから近い部員を3名選び，

残りをCに回すことにしました．その結果が，表2.3です．製造場所Aには，1・2・4・10・11・12

図表2.1製造場所までの距離(km)

部員 製造場所A 製造場所B 製造場所C

1 3.1 1.9 7.3

2 4.5 2.9 6.1

3 5.3 7.5 6.0

4 2.1 3.4 7.2

5 6.5 5.0 4.3

6 4.6 1.1 8.3

7 8.8 9.8 3.1

8 5.6 5.7 3.7

9 6.4 4.6 4.7

10 4.1 7.2 8.0

11 4.3 3.2 5.8

12 3.4 6.8 8.5

定員 6名 3名 3名

図表2.2製造場所と部員の位置関係

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8

A B

C

1 2

3 4

5

6

7 8

9

10 11

12

2.2. ネットワークの表現 51 の部員が，製造場所Bには，5・6・9の部員が，製造場所Cには，3・7・8の部員が出かけること になります．この場合の総移動距離は，45.1km となりました．12人の平均移動距離は，3.76km です．Aへの割り当てられた人の移動距離は少ないものの，B，Cに割り当てられた6人中5人が 平均を超えています．不公平であると，文句が出るかもしれません．

図表2.3 Aから距離の近い順に割り当てる．次に，B，Cに割り当て

部員 製造場所A 製造場所B 製造場所C

4 2.1 3.4 7.2

1 3.1 1.9 7.3

12 3.4 6.8 8.5

10 4.1 7.2 8.0

11 4.3 3.2 5.8

2 4.5 2.9 6.1

A:小計 21.5

6 4.6 1.1 8.3

9 6.4 4.6 4.7

5 6.5 5.0 4.3

B:小計 10.8

8 5.6 5.7 3.7

3 5.3 7.5 6.0

7 8.8 9.8 3.1

C:小計 12.8

別の方法も考えてみましょう．今度は，近いところを最優先するという方法です．表を見ると，

部員6から製造場所Bへの距離が1.1kmで，ほかのすべての距離よりも小さいので，部員6を製 造場所Bへわりあてます．次に近いのは，1–B 間の距離1.9kmなおで，部員1も製造場所Bへ わりあてます．次いで，4–A，2–Bと近いところから順に割り当てをしていきます．この結果，表 2.5，図2.6を得ました．総距離は，42.7km(平均3.56km)です．

2つの図2.4と2.6を見比べてみると，前者の方が集合場所Aへの割り当てが優先されている 分，Cにしわ寄せが来ており，後者については人数の多いAに移動距離が長い人がいます．ほか に異なる割り振り方はたくさんありそうですが，部員に納得してもらうためにも「平均距離」の規 準で見たとき，これ以上は改善できないという案を示さないといけません．ここでは，ネットワー クという概念を用い，線形計画法を援用した手法によって最適解を導くことにします．いくつか準 備をしてから，2.6.1節で再度この問題を取り上げることにしましょう．

2.2 ネットワークの表現

ネットワークは何かのつながりを表すものです．現実の様々なネットワークも結局は，何が何 とつながっているか，という関係に還元することができます．したがって，その構造を表現するに は，ネットワークの結び目と結び目同士のつながりについての情報が必要です．

結び目に相当する部分を，端点(vertex)あるいは頂点と呼びます．そのつながりを示すのに，

端点同士を結ぶ線を引き，これを枝(edge)あるいは辺(arc)と呼ぶことにします．

例えば図表2.7は6個の端点と9本の枝からなるネットワークです．

ネットワークをモデル化するにあたって，いつも図に頼ることができるとは限らないので，記 号を使って表してみるにしましょう．

図表2.4 Aから距離の近い順に割り当てた結果

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8

A B

C

1 2

3 4

5

6

7 8

9

10 11

12

図表2.5距離の近い順に割り当て

部員 製造場所 距離

6 B 1.1

1 B 1.9

4 A 2.1

2 B 2.9

7 C 3.1

12 A 3.4

8 C 3.7

10 A 4.1

5 C 4.3

11 A 4.3

3 A 5.3

9 A 6.4

総距離 42.7

2.2. ネットワークの表現 53 図表2.6距離の近い順に割り当てた結果

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8

A B

C

1 2

3 4

5

6

7 8

9

10 11

12 A

B

C

1 2

3 4

5

6

7 8

9

10 11

12 A

B

C

1 2

3 4

5

6

7 8

9

10 11

12

まず，端点には名前をつけます．ここではすべての端点に番号をふって区別しました．場合に よっては，数字ではなく，a, b, c, . . .などを使ったりします．

枝は，どの端点から始まって，どの端点を至っているかに着目します．端点iから出て，端点 jへいたる枝をijとします．この流儀にしたがって，図表2.7の例の9本の枝に名前をつけると，

13, 15, 16, 21, 23, 34, 36, 42, 65 となります．

枝が出発する端点を始点，枝が至る端点を終点と呼びます．端点iから端点jへ至る枝ijの始 点はi，終点はjです．枝ijと枝jiを区別して考えます．

n個の端点とm本の枝からなるネットワークを考えます．

端点の集合：V={1, 2, . . . , n} 枝の集合：E={e1, e2, . . . , em}

端点集合Vと枝集合Eの組G= (V, E)をあわせて，グラフ(graph)といいます．グラフ上の枝 に向きがある場合(枝ijと枝jiを区別する場合)を有向グラフ，向きがない場合を無向グラフと呼 びます．

グラフの端点や枝に重みの情報を付け加えて，ネットワークの表現とする場合もあります．重 みについては輸送問題の節で説明しましょう．

図表2.7ネットワークの例

1 2

3

4

5

6

演習問題2.1

次のような端点の集合Vと枝の集合Eがあたえられたとき，そのネットワークを図示せよ．

端点の集合：V=f1; 2; 3; 4; 5; 6g

枝の集合：E=f12; 24; 26; 36; 41; 45; 52g

2.3 輸送問題

輸送問題(transshipment problem)とは，ネットワーク上で入口(source)から出口(sink)に向 かって，モノを流す際に，最適な経路とその経路上の流量を求める問題と考えることができます．

2.3.1 輸送問題の例

ある会社が製品を3つの工場で生産しています．ここで作られた製品は2ヶ所にある直営店で 販売されています．工場の生産量の合計と直営店の需要量の合計は一致しており，各工場の生産量 と各直営店の需要量はそれぞれ表2.8のようになっています．

図表2.8工場と直営店

工場A 工場B 工場C 直営店P 直営店Q 生産・需要量 12 7 9 15 13

対応する端点 1 4 5 3 8

この工場と直営店は図表2.9ような道路網で結ばれています．図の端点は，工場，直営店，中 継点のいずれかを表しています．枝(道路)の横の[ ]の中の数値は，その道路を利用して，製品 を1単位輸送する際にかかる費用(消費する燃料の費用，通行料，渋滞による機会費用の損失額な ど)です．需要量は，直営店に対応する端点の横に□で囲って示しました．生産量は負の需要とし て解釈し，マイナス記号をつけて記入してあります．

基本的にこの道路網では，ほとんどの道が一方通行ですが，端点3,6間では両方向に通行でき ます．

以上の条件のもとで，各工場から直営店に製品を輸送する際の費用を最小にするには，どのよ うな経路でどれくらいの量を送ればよいでしょうか．

2.3. 輸送問題 55

図表2.9工場・直営店間の道路網

1

2

3

4

5

6

7

8 [8] [10]

[18]

[15]

[25]

[6]

[3]

[5]

[8]

[4]

[9]

[5]

[4]

[11]

-12

-9 -7

15

13 [3]

2.3.2 輸送問題の定式化

この問題を線形計画問題として定式化してみることにします．

端点iと端点jが枝ijを介して繋がっているとき，端点iから端点jに製品を送ることができ ると考えます(枝jiが存在しない場合は，枝ijが存在しても端点jから端点iにモノを送ることは できないことに注意)．枝ijを通るモノの量を変数xijを用いて表します．xijの値が0であれば，

その枝を使ってはモノを流さないことを意味します．

このネットワークにおける総輸送費用は，各枝に通すモノの量に1単位当たりの輸送費用をか けて，それをすべての枝について合計すれば得られます．枝の集合Eを

E={12, 14, 24, 25, 31, 36, 37, 43, 47, 56, 58, 63, 64, 78, 86}

とします．また，枝ijの1単位当たりの輸送費用をcijで表します．この問題では，例えば，c12=8， c58=9などとなります．以上の表記を用いると総輸送費用zは，

z= ∑

ij∈E

cijxij

=8x12+18x14+15x24+4x25+6x31+5x36+5x37+3x43

+10x47+25x56+9x58+4x63+11x64+3x78+8x86

と表せます．

次に，この問題の制約条件を考えることにしましょう．この問題において満たすべき条件は，流 量均衡条件と呼ばれるものです．これは，モノが流れる際に，消費されない限り途中で消えてなく なったりしない，という条件です．具体的には，各端点において，流入量の合計と流出量の合計が 一致する，という表現になります．例えば，端点2に流入する量は端点1からの来るx12です．流 出する量は，端点4へ流すx₂₄と端点5へ流すx₂₅です．端点2は中継点なのでこれ以外の流入出 量はありません．したがって，

x12=x24+x25

でなくてはなりません．

では，入口である工場の端点ではどうなるでしょうか．端点1での流入量はx31で，流出量は x12とx14です．これに加えて12単位の生産量が存在します．したがって，端点1では，

x₃₁+12=x₁₂+x₁₄ が成り立っていなくてはなりません．この式を書き直すと，

x₃₁−x₁₂−x₁₄= −12 となります．同様に出口である直営店(端点8)は，

x58+x78=x86+13 です．

以上の条件をすべての端点について書くと

x31−x12−x14 = −12 x₁₂−x₂₄−x₂₅ = 0

−x31−x36−x37+x43+x63 = 15 x14+x24−x43−x47+x64 = −7

x25−x56−x58 = −9 x36+x56−x63−x64+x86 = 0

x₃₇+x₄₇−x₇₈ = 0 x58+x78−x86 = 13

(2.1)

となります．

輸送問題を線形計画問題として定式化すると，

min 8x₁₂+18x₁₄+15x₂₄+4x₂₅+6x₃₁+5x₃₆+5x₃₇+3x₄₃ +10x47+25x56+9x58+4x63+11x64+3x78+8x86

s.t. x₃₁−x₁₂−x₁₄= −12 x12−x24−x25=0

−x31−x36−x37+x43+x63=15 x₁₄+x₂₄−x₄₃−x₄₇+x₆₄= −7 x25−x56−x58= −9

x₃₆+x₅₆−x₆₃−x₆₄+x₈₆=0 x37+x47−x78=0

x58+x78−x86=13 xij ≥0, ij∈E

(2.2)

となります．(2.2)を解くと，最適解は以下の通りです．

x12=4 x₁₄=8 x24=0 x25=4 x31=0

x36=0 x₃₇=0 x43=15 x47=0 x56=0

x58=13 x₆₃=0 x64=0 x78=0 x86=0 演習問題2.2

1. 方程式系(2.1)においては端点の数だけ制約式が存在する．すべての制約式の右辺と左辺

を足しあわせるとどうなるか確かめなさい．

2.3. 輸送問題 57

2. 方程式系(2.1)を行列で表現する際の係数行列を書きなさい．

演習問題2.3

宮城県に拠点をおくメーカーが，県内の工場と配送センターを結ぶ配送計画の見直しをすること になった．工場は，利府，名取，古川にあり，配送センターは，仙台北部，仙台南部，石巻，古 川にある．各工場の生産可能量，および配送センターの需要が以下のように与えられている．

工場 生産可能量 配送センター 需要 利府 200 仙台北部 400 名取 400 仙台南部 300 古川 500 石巻 200 古川 200

また，各工場と配送センター間の製品1単位の輸送にかかる費用は以下のように与えられている．

配送センター

仙台北部 仙台南部 石巻 古川 工

場

利府 3 4 5 4

名取 3 2 4 3

古川 3 4 4 2

輸送費用を最小にするにはどうすればよいか．

1. ネットワークを図示せよ．

2. 輸送問題として定式化せよ．

2.3.3 参考：需給が一致しない場合

前節の問題では，工場の生産量の合計と直営店の需要量の合計が一致していました．供給量と 需要量を常に一致させるのは困難なため，一般には，需給のギャップを想定した方が自然です．し かし，流量均衡条件が成り立つためには，ネットワーク上の総供給量と総需要量が一致していなく てはなりません．生産量の合計が，需要を上回っているような場合は，どのように問題を表現すれ ばよいでしょうか．

現実に需給のギャップがある場合，たとえば供給量が過剰な場合，モノは在庫となります．輸 送問題に置いても同様です．仮想的な在庫を表す端点をもとのネットワークに導入すればよいので す．すなわち，図2.10のように，倉庫を表す端点9をつくり，そこと各工場を表す端点間に枝を 張ります．

図2.10では，端点8における直営店の需要量が13から3に減少したことをうけて，仮想的な 在庫の量を10と設定しました．また，各工場と仮想的な在庫を結ぶ枝19，49，59の輸送費用は 0としています．これは，この在庫が仮想的なもので，実際の製品の移動はないことに対応してい ます．

この問題の最適解は，以下の通り．

x12=0 x14=8 x₁₉=4 x24=0 x₂₅=0 x31=0

x36=0 x₃₇=0 x43=15 x47=0 x49=0 x56=0 x₅₈=3

x₅₉=6 x63=0 x64=0 x78=0 x86=0

図表2.10仮想的な在庫の導入例

1

2

3

4

5

6

7

8 [8] [10]

[18]

[15]

[25]

[6]

[3]

[5]

[8]

[4]

[9]

[5]

[4]

[11]

-12

-9 -7

15

3 [3]

9 10

[0]

[0]

[0]

演習問題2.4

端点の集合Vと枝の集合Eがつぎのように与えられているとする．

V=f1; 2; 3; 4g

E=f12; 13; 21; 23; 24; 34; 43g 1. グラフ(V; E)によって表されているネットワークを図示せよ．

2. このネットワークが生産拠点と販売拠点との間の配送網を表しているとする．端点1に生 産拠点があり毎日a単位の製造を行っている．一方，端点3と4に販売拠点があり，それ ぞれb単位，c単位の需要がある．また，各枝には以下のように単位あたりの輸送に掛る 費用が存在している． 枝 12 13 21 23 24 34 43

費用 2 5 4 1 4 2 7

生産量と販売量の間に以下の関係がある場合について，費用を最小にするような配送計画 を求める問題を定式化せよ．

(1)a=b+cの場合 (2)a > b+cの場合 (3)a < b+cの場合

必要であれば，与えられたネットワークに端点と枝をつけ加えても構わない．

2.4 生産／在庫計画

前節の輸送問題は，空間上の位置関係（工場と直送店の場所）がネットワークを用いて表され ていました．ネットワークは必ずしも物理的な場所に関係するとは限りません．時間軸上のつなが りをネットワーク構造を用いて表すことができます．

2.4.1 ガソリンの購入計画

ガソリンの卸売りをしている会社があります．ガソリンの値段と需要は毎期変動するので，月 毎に販売計画を調整しなければ，在庫が過剰になったり製品が供給できなくなったりします．この

2.4. 生産／在庫計画 59 会社は，ガソリンの貯蔵施設を保有しているので，在庫をうまく使って価格や需要の変動に対処し ています．

今，4期先まで，値段と需要についてある程度信頼のおける推計値が得られました．

期 単位当たりの値段 需要

1期 90 140 単位

2期 85 120 単位

3期 92 150 単位

4期 90 120 単位

販売と貯蔵については次のような条件があります．

• ガソリンは期首に購入

• 第4期の終りに，在庫として少なくとも20単位のガソリンが必要

• 販売価格は，4期間にわたり一定

• 貯蔵施設のキャパシティーは十分大きい

需要を満たし，かつ収益を最大にするためには，各期にどれくらいガソリンを購入すればよいで しょうか．

この問題は，実はとても単純な問題です．モデル化するまでもなく解けます．なぜなら，販売 価格が一定で，しかも在庫の容量に制限がないので，仕入れ価格が一番安いときにたくさん買えば いいからです．したがって，1期目の期首に，その期に必要な分(140単位)だけを購入し，もっと も安い2期目に以後必要な量をすべて(120+150+120+20=410単位)購入することが最適です．

結局，購入量と仕入れ価格の合計は

1期目：140 2期目：410 3期目：0 4期目：0 (2.3)

総仕入価格： 90∗140+85∗410=47540 となります．

次に，あえてこの問題をネットワークを用いて表してみましょう．各期間ごとの購入量，販売 量，在庫量を，あたかもガソリンがネットワークを流れるものとして表現してみると，図2.11を 得ます．

端点6，7，8，9が需要を表しており，端点0がガソリンの仕入先を表します．端点0(仕入先)

から端点1，2，3，4にガソリンが移動することが，購入に相当します．したがって，枝01，02，

03，04の費用をガソリンの単位当たりの仕入れ価格に設定しています．枝12，23，34，45を流れ る量が在庫量になります．

このネットワークは輸送問題と全く同じ形式なので，同じようにＬＰに定式化してみます．

min 90x01+85x02+92x03+90x04

s.t. −x01−x02−x03−x04= −550 x01−x12−x16=0

x₁₂+x₀₂−x₂₃−x₂₇=0 x23+x03−x34−x38=0 x₃₄+x₀₄−x₄₅−x₄₉=0

x45=20, x16=140, x27=120, x38=150, x49=120 xij ≥0, すべてのij

(2.4)

図表2.11ガソリンの販売・在庫を表すネットワーク

0

1 2 3 4 5

6 7 8 9

140 120 150 120

-550

20 [90] [85] [92] [90]

(2.4)の最適解は，

x01=140, x02=410, x03=0, x04=0,

x12=0, x16=140, x23=290, x27=120,

x34=140, x38=150, x45=20, x49=120,

となり，(2.3)と同じ結果を得ました．

今の問題は，あえてネットワークを書いてわざわざLPに定式化しなくても解くことができま した．では，もう少し複雑な設定をしてみましょう．在庫として保有するガソリンに保管費用がか かるとします．1単位当たり3とします．

この場合はモデル化のステップが必要でしょう．ネットワークができていれば簡単に対応でき ます．在庫を表す枝に費用をつけるだけです．結果は，図2.12のようになりました．

定式化するとつぎのようになります．

min 90x01+85x02+92x03+90x04+3x12+3x23+3x34+3x45

s.t. −x₀₁−x₀₂−x₀₃−x₀₄= −550 x01−x12−x16=0

x₁₂+x₀₂−x₂₃−x₂₇=0 x23+x03−x34−x38=0 x34+x04−x45−x49=0

x45=20, x16=140, x27=120, x38=150, x49=120 xij≥0, すべてのij

(2.5)

計算結果は次の通りです．

x₀₁=140, x₀₂=270, x₀₃=0, x₀₄=140,

x₁₂=0, x₁₆=140, x₂₃=150, x₂₇=120,

x34=0, x38=150, x45=20, x49=120

2.4. 生産／在庫計画 61 図表2.12ガソリンの販売・在庫を表すネットワーク：保管費用あり

0

1 2 3 4 5

6 7 8 9

140 120 150 120

-550

20 [90] [85] [92] [90]

[3] [3] [3] [3]

演習問題2.5

1. 上記の問題では，在庫の容量は考えていなかった．貯蔵するガソリンは最大100単位まで という制約がある場合の問題を線形計画問題として定式化せよ．

2. 上の問題をさらに発展させて．在庫の容量制約に，次の条件を付け加える．まず，各期の 販売価格をその期の仕入れ価格の1.1倍とする．また需要は必ずしも満たさなくてもいい が，満たせない分に関しては，仕入れ値の1.2倍のペナルティがかかるとする．

[総売り上げ]−[総仕入れ価格]−[在庫費用]─[ペナルティの合計]を最大にするためには どのように定式化すべきか．

2.4.2 生産シフトの決定

ある工場では，生産量や在庫量を調整することで，製品需要の変動に対応しています．生産量 の調整は2段階で行います．通常シフトでは1単位当たり500円で生産が可能です．ただし通常シ フトでは，最大80単位までしか生産できません．通常シフトで生産が追い付かないときは，臨時 シフトをとって増産体制に入ります．臨時シフトではさらに20単位まで増産可能ですが，生産費 用は高くなり，1単位当たり650円です．在庫には上限はありませんが，1期間毎に1単位当たり 100円の保管費用がかかります．

4期先までの需要が

期 1 2 3 4 需要量 85 60 90 105

と与えられている場合，費用を最小にするような各期の生産量と在庫の量をネットワークとして表 してみると，図2.13のようになります．

枝ijを流れる量をxijとして最適解を求めると，次のようになります．

x13=80 x20=15 x23=5 x40=5

x₄₆=75 x₅₀=20 x₆₉=15 x₇₉=80

x₈₀=20 x_9,12=5 x_10,12=80 x_11,12=20

図表2.13生産量と在庫量のネットワーク

1 2

3

4 5

6

7 8

9

10

12 11 13

[0]

[0] [0] [0] [0] [0] [0] [0]

[500]

[650]

[650]

[650]

[650]

[100] [100] [100]

[500] [500] [500]

-80

-20

-20 -20 -20

-80 -80 -80

60 90

85 105

60

非負の流量を持つ枝のみ示しました．この結果を見ると，通常シフトは第2期以外では最大限生産 を行う一方，臨時シフトの生産は第1期に5単位，第4期に20単位のみとなっています．在庫は 第2期末，第3期末にそれぞれ15単位，5単位生じています．

演習問題2.6

図2.13で表現されたネットワークを用いて，費用を最小にする生産在庫計画を求める問題をLP として定式化せよ．

演習問題2.7

あるレンタカーショップの1週間(営業日は6日間)の運用問題を考えるこのレンタカーショッ プでは，全部で30台の車をレンタルしている．レンタルした車は必ずメンテナンスに出すので，

常に30台が営業可能というわけではない．もし店頭にある車の台数が十分でないならば，姉妹 店からお金を払って借りてくる必要がある．姉妹店との取り決めで，借りる期間は１週間となっ ている．

メンテナンスには，通常では3日かかり，その費用は1台当たりp円である．しかし，q(> p) 円支払うことで，1日でメンテナンスを終えることができる．他の姉妹店から借りてくる場合は，

１日あたりr円かかる．

今から1週間について第j日目の需要がdjであるとわかっているとき(7日目は休業日なので d7=0とする)，このレンタカーショップの営業費用を最小にする計画を作るものとする．

ただし，週始めにおいてはメンテナンスに出してある車はないものする．そのためには，5，6日 目にレンタルした車は，1日でメンテナンスを終えるようにしなければならない．また，このレ ンタカーショップの車種は1つだけで，しかも貸し出した当日に返却されるとする．

上記の設定を車の在庫管理の問題としてとらえ，ネットワークの図をつくれ．［ヒント：車がネッ トワークを流れると考えましょう．各営業日において車は，ショップにあるか，レンタルされて いるか，メンテナンスに出ているか，のいずれかです．］

2.5 _整数性

図2.14のネットワークを例に使って，輸送問題の解の性質をみることにします．端点1に10 単位の供給があり，端点5と7に，それぞれ6単位と4 単位の需要があるとします．枝の費用を

2.5. 整数性 63 図表2.14輸送のネットワーク

7 4 1

3 2

5 6

-10

6 4

cijとおいて，輸送問題を定式化すると，

min +c12x12+c13x13+c14x14+c23x23+c25x25+c26x26

+c₃₄x₃₄+c₃₅x₃₅+c₃₆x₃₆+c₃₇x₃₇+c₄₆x₄₆+c₄₇x₄₇+c₆₅x₆₅+c₇₆x₇₆ s.t. −x12−x13−x14= −10

+x12−x23−x25−x26=0

+x13+x23−x34−x35−x36−x37=0 +x14+x34−x46−x47=0

+x₂₅+x₃₅+x₆₅=6

+x26+x36+x46−x65+x76=0 +x₃₇+x₄₇−x₇₆=4

xij≥0,すべてのij

(2.6)

となります．問題(2.6)の輸送費用をかえて，いくつか問題を解いてみました．その結果を表にし たのが，表2.15です．

演習問題2.8

表2.15を参照して，最適解においてどのようなルートを通って配送しているか，図に記入せよ．

この結果から以下のことがわかりました．

• 最適解はすべて整数である．

• 最適な配送ルートはつながっている

• 最適は配送ルート上では，ある端点へいたる道はひとつしかない(並行する道がない) 以上は，ただ一つの問題についてパラメータをかえて数値実験を行っただけなので，もしかしたら 別のネットワークでは異なる結果になるだろうと思う人がいるかもしれません．実は，上記の結果 はネットワーク特有の構造から導かれています．一定の条件を満たす輸送問題すべてに当てはまる のです．

説明のために，新しい言葉を導入しておきます．

• 端点uと端点vの経路とは，端点uと端点vを結ぶ枝と端点からなるネットワークの一部を いう．経路をたどると，端点uから端点vへ至ることができる(枝の向きはかんがえなくて もよい)．

• 閉路(cycle)とはある端点から出発して同じ端点に戻ってくる経路である．