47
第
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.
ネットワークの表現49
員が，製造場所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.
ネットワークの表現51
図表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 = { e
1, e
2, . . . , e
m}
端点集合
V
と枝集合E
の組G = (V, E)
をあわせて，グラフ(graph)
といいます．グラフ上の枝 に向きがある場合(枝 ij
と枝ji
を区別する場合)を有向グラフ，向きがない場合を無向グラフと呼 びます．グラフの端点や枝に重みの情報を付け加えて，ネットワークの表現とする場合もあります．重 みについては輸送問題の節で説明しましょう．
図表
2.7
ネットワークの例1 2
3
4
5
6
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.2
輸送問題の定式化この問題を線形計画法の枠組で定式化してみることにします．
端点
i
と端点j
が枝ij
を介して繋がっているとき，端点i
から端点j
に製品を送ることができ ると考えます(枝 ji
が存在しない場合は，枝ij
が存在しても端点j
から端点i
にモノを送ることは2.3.
輸送問題53
図表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]
できないことに注意)．枝
ij
を通るモノの量を変数x
ijを用いて表します．xijの値が0
であれば，その枝を使ってはモノを流さないことを意味します．
このネットワークにおける総輸送費用は，各枝に通すモノの量に
1
単位当たりの輸送費用をか けて，それをすべての枝について合計すれば得られます．枝の集合E
をE = { 12, 14, 24, 25, 31, 36, 37, 43, 47, 56, 58, 63, 64, 78, 86 }
とします．また，枝
ij
の1
単位当たりの輸送費用をc
ijで表します．この問題では，例えば，c
12= 8，
c
58= 9
などとなります．以上の表記を用いると総輸送費用z
は，z = ∑
ij∈E
c
ijx
ij= 8x
12+ 18x
14+ 15x
24+ 4x
25+ 6x
31+ 5x
36+ 5x
37+ 3x
43+ 10x
47+ 25x
56+ 9x
58+ 4x
63+ 11x
64+ 3x
78+ 8x
86と表せます．
次に，この問題の制約条件を考えることにしましょう．この問題において満たすべき条件は，流 量均衡条件と呼ばれるものです．これは，モノが流れる際に，消費されない限り途中で消えてなく なったりしない，という条件です．具体的には，各端点において，流入量の合計と流出量の合計が 一致する，という表現になります．例えば，端点
2
に流入する量は端点1
からの来るx
12です．流 出する量は，端点4
へ流すx
24と端点5
へ流すx
25です．端点2
は中継点なのでこれ以外の流入出 量はありません．したがって，x
12= x
24+ x
25でなくてはなりません．
では，入口である工場の端点ではどうなるでしょうか．端点
1
での流入量はx
31で，流出量はx
12とx
14です．これに加えて12
単位の生産量が存在します．したがって，端点1
では，x
31+ 12 = x
12+ x
14が成り立っていなくてはなりません．この式を書き直すと，
x
31− x
12− x
14= −12
となります．同様に出口である直営店(端点 8)
は，x
58+ x
78= x
86+ 13
です．以上の条件をすべての端点について書くと
x
31− x
12− x
14= −12 x
12− x
24− x
25= 0
−x
31− x
36− x
37+ x
43+ x
63= 15 x
14+ x
24− x
43− x
47+ x
64= −7
x
25− x
56− x
58= −9 x
36+ x
56− x
63− x
64+ x
86= 0
x
37+ x
47− x
78= 0 x
58+ x
78− x
86= 13
(2.1)
となります．
演習問題
2.1
1.
方程式系(2.1)
においては端点の数だけ制約式が存在する．すべての制約式の右辺と左辺を足しあわせるとどうなるか確かめなさい．
2.
方程式系(2.1)
を行列で表現する際の係数行列を書きなさい．輸送問題を線形計画問題として定式化すると，
min 8x
12+ 18x
14+ 15x
24+ 4x
25+ 6x
31+ 5x
36+ 5x
37+ 3x
43+10x
47+ 25x
56+ 9x
58+ 4x
63+ 11x
64+ 3x
78+ 8x
86s.t. x
31− x
12− x
14= −12 x
12− x
24− x
25= 0
−x
31− x
36− x
37+ x
43+ x
63= 15 x
14+ x
24− x
43− x
47+ x
64= −7 x
25− x
56− x
58= −9
x
36+ x
56− x
63− x
64+ x
86= 0 x
37+ x
47− x
78= 0
x
58+ x
78− x
86= 13 x
ij≥ 0, ij ∈ E
(2.2)
となります．
(2.2)
を解くと，最適解は以下の通りです．x
12= 4 x
14= 8 x
24= 0 x
25= 4 x
31= 0
x
36= 0 x
37= 0 x
43= 15 x
47= 0 x
56= 0
x
58= 13 x
63= 0 x
64= 0 x
78= 0 x
86= 0
演習問題2.2
宮城県に拠点をおくメーカーが，県内の工場と配送センターを結ぶ配送計画の見直しをすること になった．工場は，利府，名取，古川にあり，配送センターは，仙台北部，仙台南部，石巻，古 川にある．各工場の生産可能量，および配送センターの需要が以下のように与えられている．
2.3.
輸送問題55
工場 生産可能量 配送センター 需要 利府
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
としています．これは，この在庫が仮想的なもので，実際の製品の移動はないことに対応してい ます．この問題の最適解は，以下の通り．
x
12= 0 x
14= 8 x
19= 4 x
24= 0 x
25= 0 x
31= 0
x
36= 0 x
37= 0 x
43= 15 x
47= 0 x
49= 0 x
56= 0 x
58= 3
x
59= 6 x
63= 0 x
64= 0 x
78= 0 x
86= 0
演習問題
2.3
端点の集合
V
と枝の集合E
がつぎのように与えられているとする．V = f 1; 2; 3; 4 g
E = f 12; 13; 21; 23; 24; 34; 43 g
図表
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]
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
ガソリンの購入計画ガソリンの卸売りをしている会社があります．ガソリンの値段と需要は毎期変動するので，月 毎に販売計画を調整しなければ，在庫が過剰になったり製品が供給できなくなったりします．この 会社は，ガソリンの貯蔵施設を保有しているので，在庫をうまく使って価格や需要の変動に対処し ています．
今，4期先まで，値段と需要についてある程度信頼のおける推計値が得られました．
2.4.
生産／在庫計画57
期 単位当たりの値段 需要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
を 得ます．図表
2.11
ガソリンの販売・在庫を表すネットワーク0
1 2 3 4 5
6 7 8 9
140 120 150 120
-550
20
[90] [85] [92] [90]
端点
6，7，8，9
が需要を表しており，端点0
がガソリンの仕入先を表します．端点0(仕入先)
から端点1
，2
，3
，4
にガソリンが移動することが，購入に相当します．したがって，枝01
，02
，03
，04
の費用をガソリンの単位当たりの仕入れ価格に設定しています．枝12
，23
，34
，45
を流れ る量が在庫量になります．このネットワークは輸送問題と全く同じ形式なので，同じようにＬＰに定式化してみます．
min 90x
01+ 85x
02+ 92x
03+ 90x
04s.t. −x
01− x
02− x
03− x
04= −550 x
01− x
12− x
16= 0
x
12+ x
02− x
23− x
27= 0 x
23+ x
03− x
34− x
38= 0 x
34+ x
04− x
45− x
49= 0
x
45= 20, x
16= 140, x
27= 120, x
38= 150, x
49= 120 x
ij≥ 0, ∀ ij
(2.4)
(2.4)
の最適解は，x
01= 140, x
02= 410, x
03= 0, x
04= 0,
x
12= 0, x
16= 140, x
23= 290, x
27= 120,
x
34= 140, x
38= 150, x
45= 20, x
49= 120,
となり，(2.3)と同じ結果を得ました．
今の問題は，あえてネットワークを書いてわざわざ
LP
に定式化しなくても解くことができま した．では，もう少し複雑な設定をしてみましょう．在庫として保有するガソリンに保管費用がか かるとします．1
単位当たり3
とします．この場合はモデル化のステップが必要でしょう．ネットワークができていれば簡単に対応でき ます．在庫を表す枝に費用をつけるだけです．結果は，図
2.12
のようになりました．図表
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.4.
生産／在庫計画59
LP
の定式化は省略して計算結果だけを示します．x
01= 140, x
02= 270, x
03= 0, x
04= 140,
x
12= 0, x
16= 140, x
23= 150, x
27= 120,
x
34= 0, x
38= 150, x
45= 20, x
49= 120
演習問題
2.4
1.
上記の問題では，在庫の容量は考えていなかった．貯蔵するガソリンは最大100
単位まで という制約がある場合の問題を線形計画問題として定式化せよ．2.
上の問題をさらに発展させて．在庫の容量制約に，次の条件を付け加える．まず，各期の 販売価格を仕入れ価格の1.1
倍とする．また需要は必ずしも満たさなくてもいいが，満た せない分に関しては，仕入れ値の1.2
倍のペナルティがかかるとする．[
総売り上げ]
−[
総仕入れ価格]
−[
在庫費用]
─[
ペナルティの合計]
を最大にするためには どのように定式化すべきか．2.4.2
生産シフトの決定ある工場で製品を生産しています．生産量や在庫量を調整することで，製品需要の変動に対応 しています．生産量の調整は
2
段階で行います．通常シフトでは1
単位当たり500
円で生産が可能 です．ただし通常シフトでは，最大80
単位までしか生産できません．通常シフトで生産が追い付 かないときは，臨時シフトをとって増産体制に入ります．臨時シフトではさらに20
単位まで増産 可能ですが，生産費用は高くなり，1単位当たり650
円です．在庫には上限はありませんが，1期 間毎に1
単位当たり100
円の保管費用がかかります．4
期先までの需要が表2.13
のように与えられている場合，費用を最小にするような各期の生産 量と在庫の量をネットワークとして表してみると，図2.14
のようになります．図表
2.13
各期の需要量期
1 2 3 4
需要量85 60 90 105
図表
2.14
生産量と在庫量のネットワーク1 2
3
4 5
6
7 8
9
10
11 12 13
[0]
[0] [0] [0] [0] [0] [0] [0]
[500]
[650]
[650]
[650]
[650]
[100] [100] [100]
[500] [500] [500]
-80
-20
-20 -80 -80 -20 -80 -20
60 90
85 105
60
演習問題
2.5
図
2.14
で表現されたネットワークを用いて，費用を最小にする生産在庫計画を求める問題をLP
として定式化せよ．演習問題
2.6
あるレンタカーショップの
1
週間(
営業日は6
日間)
の運用問題を考えるこのレンタカーショッ プでは，全部で30
台の車をレンタルしている．レンタルした車は必ずメンテナンスに出すので，常に
30
台が営業可能というわけではない．もし店頭にある車の台数が十分でないならば，姉妹 店からお金を払って借りてくる必要がある．姉妹店との取り決めで，借りる期間は１週間となっ ている．メンテナンスには，通常では
3
日かかり，その費用は1
台当たりp
円である．しかし，q(> p)
円支払うことで，1
日でメンテナンスを終えることができる．他の姉妹店から借りてくる場合は，１日あたり
r
円かかる．今から
1
週間について第j
日目の需要がd
jであるとわかっているとき(7
日目は休業日なのでd
7= 0
とします)
，このレンタカーショップの営業費用を最小にする計画を作るものとする．ただし，週始めにおいてはメンテナンスに出してある車はないものする．そのためには，
5
，6
日 目にレンタルした車は，1
日でメンテナンスを終えるようにしなければならない．また，このレ ンタカーショップの車種は1
つだけで，しかも貸し出した当日に返却されるとする．上記の設定を車の在庫管理の問題としてとらえ，ネットワークの図をつくれ．［ヒント：車がネッ トワークを流れると考えましょう．各営業日において車は，ショップにあるか，レンタルされて いるか，メンテナンスに出ているか，のいずれかです．］
2.5
整数性図表
2.15
輸送のネットワーク7 4 1
3 2
5 6
図
2.15
のネットワークを例に使って，輸送問題の解の性質をみることにします．端点1
に10
単位の供給があり，端点5
と7
に，それぞれ6
単位と4
単位の需要があるとします．枝の費用を2.5.
整数性61
c
ijとおいて，輸送問題を定式化すると，min +c
12x
12+ c
13x
13+ c
14x
14+ c
23x
23+ c
25x
25+ c
26x
26+c
34x
34+ c
35x
35+ c
36x
36+ c
37x
37+ c
46x
46+ c
47x
47+ c
65x
65+ c
76x
76s.t. −x
12− x
13− x
14= −10
+x
12− x
23− x
25− x
26= 0
+x
13+ x
23− x
34− x
35− x
36− x
37= 0 +x
14+ x
34− x
46− x
47= 0
+x
25+ x
35+ x
65= 6
+x
26+ x
36+ x
46− x
65+ x
76= 0 +x
47− x
76= 4
x
ij≥ 0, for all ij
(2.5)
となります．問題
(2.5)
の輸送費用をかえて，いくつか問題を解いてみました．その結果を表にし たのが，表2.16
です．図表
2.16
輸送費用の変化と輸送量枝
ij 12 13 14 23 25 26 34 35 36 37 46 47 65 76 (1) c
ij9.0 9.5 3.4 4.4 4.8 1.5 1.4 5.4 7.3 4.0 3.6 2.9 8.7 6.3
x
ij6 0 4 0 6 0 0 0 0 0 0 4 0 0
(2) c
ij2.5 9.8 6.5 2.3 6.9 6.7 1.4 0.3 2.7 1.2 0.7 8.6 1.9 0.4
x
ij10 0 0 10 0 0 0 6 0 4 0 0 0 0
(3) c
ij7.4 5.4 2.8 3.7 0.2 8.9 8.7 2.6 5.7 1.6 6.0 3.4 6.6 8.7
x
ij6 0 4 0 6 0 0 0 0 0 0 4 0 0
(4) c
ij9.0 3.3 7.4 4.2 4.0 5.1 1.7 5.3 6.5 0.2 8.4 8.1 7.0 4.7
x
ij0 10 0 0 0 0 0 6 0 4 0 0 0 0
(5) c
ij0.2 5.7 4.6 9.1 2.9 0.7 4.8 9.9 9.3 5.7 6.6 7.8 1.1 0.1
x
ij6 4 0 0 0 6 0 0 0 4 0 0 6 0
(6) c
ij5.5 0.1 4.6 2.0 7.9 6.2 0.2 9.0 7.7 9.1 7.6 3.9 3.4 5.1
x
ij0 10 0 0 0 0 4 6 0 0 0 4 0 0
(7) c
ij9.6 6.8 0.6 6.0 4.0 2.2 1.9 0.8 0.1 7.9 0.2 8.8 3.6 7.3
x
ij0 0 10 0 0 0 0 0 0 0 6 4 6 0
(8) c
ij6.0 1.6 3.2 2.4 0.1 4.0 6.5 0.9 7.7 9.7 7.2 7.9 2.4 2.0
x
ij0 6 4 0 0 0 0 6 0 0 0 4 0 0
演習問題
2.7
表
2.16
を参照して，最適解においてどのようなルートを通って配送しているか，図に記入せよ．この結果から以下のことがわかりました．
•
最適解はすべて整数である．•
最適な配送ルートはつながっている•
最適は配送ルート上では，ある端点へいたる道はひとつしかない(
並行する道がない)
以上は，ただ一つの問題についてパラメータをかえて数値実験を行っただけなので，もしかしたら 別のネットワークでは異なる結果になるかもしれないと思う人がいるかも知れません．実は，上記の結果はネットワーク特有の構造から導かれています．一定の条件を満たす輸送問題すべてに当て はまるのです．
説明のために，新しい言葉を導入しておきます．
•
端点u
と端点v
の経路とは，ネットワークの一部分をいい，端点u
から枝によって結ばれた 端点をたどって端点v
へ至ることができる(枝の向きはかんがえなくてもよい)．
•
閉路(cycle)
とはある端点から出発して同じ端点に戻ってくる経路である．•
ネットワークが連結であるとは，ネットワーク上の任意の2
つの端点間に必ず経路が存在す ることである．•
木(tree)
とは，連結でかつ閉路の存在しないネットワークのことである．•
全域木(spanning tree)
とは，もとのネットワークのすべての端点を含む木のことである．輸送問題における実行可能基底解は，
“
木”
に対応していることが知られています．直感的には 以下のように説明できます．1.
まず適当に実行可能な輸送案をつくってみてください．その案では当然，需要点と供給点の 間に経路があるはずです．2.
次に，その案に閉路があるかどうか探してください．もし閉路があったなら，二つの可能性 があります．一つはその閉路が一方通行で元に戻ってくる場合，もう一つはある端点へ流す 経路が2
種類ある場合です．前者であれば，同じところに戻すような流し方は不合理なので，その閉路のどこかの枝を輸送案からはずしましょう．後者であれば，2種類の経路のうち輸 送費用が安い方があれば十分なので，高い方をはずします．この段階で，輸送案から閉路は なくなりました．
3.
最後に，輸送案では通らない端点を探します．その端点と輸送案が通る端点とを結ぶ枝をみ つけて，(
輸送量0
として)
輸送案に付け加えましょう．4.
最終的に，ネットワークのすべての端点が連結されて，かつ閉路の存在しない輸送案になっ たはずです．すなわち全域木が構成されました．輸送問題の基底形式表現と全域木の対応関係は数学的に示すこともできますが，ここでは割愛しま す．興味がある人は適当な専門書を参照してください．
さて，実行可能解は木であることから最適解も木になっています．ここで，需要量と供給量が すべて整数である場合を考えましょう．木は，その名前の通り末端
(
葉，leaf
とよばれます)
から，だんだんと枝が合流していきます
(大本は根，root
とよばれます)．需要が整数であるなら，末端 の需要点に流れる量も(0
もふくめて)
整数のはずです．それが合流して，上流の枝に流れる量と なっても整数です．つまり木の構造と需要(と供給)
が整数であることから，実行可能解は必ず整 数になります．¶ ³
定理
2.1 (輸送問題の整数性)
輸送問題
min c
⊤x
s.t. Ax = b, x ≥ 0
において右辺
b
の要素がすべて整数だとする．この時，輸送問題に最適解が存在すれば，最 適解は整数である．µ ´
2.6.
割当や組合わせを決める問題63
上記の定理は，輸送問題の“よい”
性質を保証するものです．この性質を利用して，組合わせや 割り当てを決める問題に応用することができます．2.6
割当や組合わせを決める問題2.6.1
クッキーの作成場所2.1
節の続きです．今考えているのは，部員の製造場所への割り当てです．部員が製造場所に移動していくので，
輸送の最適化問題として考えることもできそうです．部員の部屋から，部員が
1
単位(=1
人)供 給されて，需要点である製造場所へ運ばれるイメージです．各需要点の需要を定員に設定してみ ましょう．さて，運ぶものは部員自身なので分割は不可能ですが，今は定式化の都合を優先させ て，部員の部屋から需要点へ運ばれる物(=部員)
の量を連続変数を使って表してみましょう．部員i (i = 1, . . . , 12)
の部屋から，それぞれの需要点j (j = A, B, C)
へ物が運ばれる可能性があるので，その量を
x
ij(i = 1, . . . , 12; j = A, B, C)
と表しましょう．つまり，36個の変数を用意することに なります．必要な制約は，供給点と需要点それぞれに存在します．供給点においては，部員は
1
単位まで しか供給できないので，x
iA+ x
iB+ x
iC= 1, i = 1, . . . , 12
となっていなくてはなりません．また，需要点では定員があるので，x
1A+ x
2A+ · · · + x
12A= 6 x
1B+ x
2B+ · · · + x
12B= 3 x
1C+ x
2C+ · · · + x
12C= 3
を満たしていなくてはなりません．非負制約も忘れてはいけません．
x
ij≥ 0, i = 1, . . . , 12; j = A, B, C
平均移動距離を最小化したいので，目的関数を総移動距離とおいても同じことです．
c
1Ax
1A+ c
2Ax
2A+ · · · + c
12Ax
12A+c
1Bx
1B+ c
2Bx
2B+ · · · + c
12Bx
12B+c
1Cx
1C+ c
2Cx
2C+ · · · + c
12Cx
12C(2.6)
c
ijは，供給点i
から需要点j
への距離を表します．たとえば，c1A= 3.1
です．以上をまとめると，
min c
1Ax
1A+ c
2Ax
2A+ · · · + c
12Ax
12A+c
1Bx
1B+ c
2Bx
2B+ · · · + c
12Bx
12B+c
1Cx
1C+ c
2Cx
2C+ · · · + c
12Cx
12Cs.t. x
iA+ x
iB+ x
iC= 1, i = 1, . . . , 12
x
1A+ x
2A+ · · · + x
12A= 6 x
1B+ x
2B+ · · · + x
12B= 3 x
1C+ x
2C+ · · · + x
12C= 3 x
ij≥ 0, i = 1, . . . , 12; j = A, B, C
(2.7)
となり，輸送問題が定式化されました．最適解は，
x
1A= 1 x
2B= 1 x
3A= 1
x
4A= 1 x
5C= 1 x
6B= 1
x
7C= 1 x
8C= 1 x
9B= 1
x
10A= 1 x
11A= 1 x
12A= 1
となりました．残りの変数の値は
0
です．最適解が1
または0
であることは，輸送問題の整数性に よって保証されます．物の輸送と便宜的に考えて定式化してきたのを，再度人の移動に置き換えて 解釈しなおすと，製造場所
A
へ行く部員1,3,4,10,11,12
製造場所B
へ行く部員2,6,9
製造場所
C
へ行く部員5,7,8
となります．この場合の最適値は，42.1(km)です．こうしてみると，最初の素朴な方法も値とし ては悪くない気がします．しかし，図
2.4
と図2.17
を比較すると，製造場所C
への割り当てのバ ランスが改善していることがわかります．また，図2.6
では，製造場所A
に極端に遠い人が割り当 てられていたのが，図2.17
では，比較的集合場所に近いところに割り当てられています．図表
2.17
最適化問題を解いた結果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.8
問題
(2.7)
は，平均移動距離最小化に対応している．では，もっとも移動距離が長い部員の移動距離を最小化にするような割り当て（最長移動距離最小化基準）を得るためには，どのような定 式化を行えばよいか．
2.6.
割当や組合わせを決める問題65
2.6.2 2
部グラフ部室の掃除
クッキーの袋づめを部室で行うと決めたものの，現在の汚れ具合いではとても食べ物を扱う作 業が許されるとは思えません．責任者であるあなたが音頭をとって部室の大掃除を行うことにしま した．毎度のことですが，わがままな部員が多くて，掃除の役割分担ではいつももめることになり ます．以前責任者が分担を一方的に決めたときはいやな仕事に割り振られた部員が怒り出したこと もありました．じゃんけんで決めたときは，最後に負けた部員が逃亡してしまい，結局責任者が泣 く泣くその仕事をする羽目になりました．
今年度大掃除の分担を決めるに当たって，あなたが部員の話を聞いてみたところ，みな仕事に たいして好き嫌いがあり，しかもそれは必ずしも全員一様でないことに気づきました．うまく皆の 意見を調整すれば，なんとか全員が不満を抱かずに済ませることができるかもしれません．
当日集まれる
8
人の部員にアンケートを取ったところ，表2.18
のような結果を得ました．各部 員が仕事についてどれが好ましいか順位をつけてもらったものです．あなたは，部員の割り当てに 応じて決まる数値の合計が小さいほど部員の不満は少ないだろうと考えました．図表
2.18
部員の仕事に対する好き嫌いの順序部員
1 2 3 4 5 6 7 8
a
窓ガラス6 8 5 1 1 1 4 7
b
照明1 5 3 2 3 4 1 6
c
棚1 2 7 8 7 6 2 7 8
d
棚2 3 3 4 8 2 5 8 4
e
机1 7 1 6 4 8 8 2 2
f
机2 4 4 1 3 7 6 6 5
g
ごみ8 6 7 6 5 3 5 3
h
床5 2 2 5 4 7 3 1
この割り当て問題を，ネットワークを使って解いてみることにします． 図
2.19
のようなネット ワークを描きました．図2.19
のように，端点の集合を2
つに分けたときに，すべての枝の始点が 一方の集合に属する端点となり，終点が他方の集合に属する端点となるネットワーク(グラフ)
を2
部グラフと呼びます．部員の端点に供給が
1
存在し，仕事の端点に需要が1
あるというように考えると，これは輸送 問題となります．枝の費用を選好順序して，最小費用輸送問題をとくことで，不満の少ない割り当 てを決めることができそうです．2.5
節で示したように，輸送問題型の定式化では解は必ず整数になるので，部員の端点からで る8
本の枝のうち，かならず1
本だけに1
単位の流量があります．そして，そこが部員に割り当 てる仕事になります．図表
2.19
部員と仕事のネットワーク1 2 3 4 5 6 7 8
a
b
d
e
f
g
h
6 1 2 3 7 1 4
5
定式化は，次の通りです．
min
∑
ni=1
∑
j∈J
c
ijx
ijs.t. ∑
j∈J
x
ij= 1, i = 1, . . . , n
∑
ni=1
x
ij= 1, j ∈ J
x
ij≥ 0, i = 1, . . . , n; j ∈ J
ただし，cijは部員
i
を仕事j
に割り当てたときの選好順序を表し，J= { a, b, , . . . , h }
とおいてい ます．結果は，図
2.21
の通りです．最悪でも3
番目までに割り当てられているので，おそらく部員に 不満はないことでしょう．ためしに，ジャンケンで勝った人からわりあてを決めた場合を見てみま しょう．部員8
が一番で，以下，部員5
，部員6
，部員3
，部員7
，部員4
，部員2
，部員1
の順序 で仕事を選ぶことになりました．部員は残っている仕事の中から一番自分の選好順序が高いものを 選びます．結果は表2.20
の通りです．じゃんけんで負けてしまった人は，あまりいい仕事につけ なかったようです．図表
2.20
ジャンケンで決めた場合の分担部員
(選んだ順序) 8 5 6 3 7 4 2 1
選んだ仕事
h a c f b e d g
選んだ仕事の順位1 1 2 1 1 4 3 8
演習問題
2.9
ある会社の従業員にたいする仕事の割り振りを考える．従業員
5
人に対して，割り振る仕事も5
つある．従業員はそれぞれの仕事に対して，得手不得手があり，各々の仕事をこなす時間はそれ ぞれ以下の表のようになっている．従業員B
は仕事1
を，従業員D
とE
は仕事4
と5
を行う ことはできない．全体の仕事にかかる時間が最小になる仕事の割り振りを決める問題を定式化せよ．
演習問題
2.10
1.
１０人の学生を，３つのゼミのいずれかに所属させることを考える．各ゼミは定員4
人を 越えて学生を所属させることはできないが，少ない分には構わない．また，各学生j
がゼ2.6.
割当や組合わせを決める問題67
図表
2.21
仕事の分担1 2 3 4 5 6 7 8
a
b
d
e
f
g
h 2
1
1
1
2 3
1 1
図表
2.22
従業員が仕事を終えるのに要する時間(
単位：時間)
仕事
1
仕事2
仕事3
仕事4
仕事5
従業員A 5 4 8 7 3
従業員B — 4 9 11 5
従業員C 6 5 8 5 4
従業員D 7 9 11 — —
従業員
E 6 8 10 — —
ミ
i
に所属したときの満足度u
ijは事前の調査でわかっているものとする．学生の満足度 の総計を最大にするようなゼミの所属を決める問題をあらわすネットワーク（2
部グラフ）をつくれ．
2.
最低定員(
最低でも所属しなければいけない人数)
が2
人と設定されているとする．上と同 様にネットワークであらわせ．(
注)
この場合は，2
部グラフになりません．2.6.3
参考：最大マッチング問題2.6.2
節では，あらかじめ組み合わせの数は与えられていました(掃除の分担でいえば，8
人を8
種類の仕事にわりあてました)
．今度は視点を変えて，可能な組合わせの中でなるべくたくさん の組をつくることを考えてみます．インコのペアリング1
インコのブリーダーが，自分の飼っているインコをつがいにしてインコを増やそうとしていま す．現在，ブリーダーが所有しているのは，オスが
11
羽，メスが10
羽です．インコにも相性の良 し悪しがあって，相性の悪いもの同士では雛は生まれません．相性が良いものだけでペアを組む必 要があります．ブリーダーは，できるならばたくさんのペアをつくって，インコをたくさん繁殖さ せたいと思っています．相性から考えて，可能な組合わせが表2.23
のように与えられたとき，最 もペアの数を多くするにはどうすればよいでしょうか．なお，このインコは共同で子育をするの で，オスまたはメスを共有するペアはつくれません．この問題は最大マッチング問題と呼ばれるものです．マッチングとはグラフに属する枝の集合 で，マッチングに属する枝は互いに始点も終点も共有しません．オスとメスのインコを端点と見な
1説明のためにインコを例として用いていますが，インコについて実際のことよく知りません．
![図表 2.10 仮想的な在庫の導入例 1 2 34 5 6 78[8][10][18][15][25][6] [3][5][8][4][9][5][4][11]-12 -9 -7 15 3[3]910[0][0][0] 1](https://thumb-ap.123doks.com/thumbv2/123deta/7072139.2311062/10.892.165.785.178.505/図表21仮想的な在庫の導入例1234567881181525.webp)
![1桁の引き算の文章題(ふりがなつき) | [問題]-028/180](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)