Document

生産計画を立てる
・簡単なバージョン：輸送問題
定式化、最小費用流、バリエーション
・部品組立て計画
定式化、バリエーション
・生産計画
定式化、バリエーション
輸送問題：運送コストを最小化
・いくつかの工場がある
・いくつかの小売店がある
・どれも一種類の品目を扱っている
・毎日、朝、売れる分だけ工場から小売店に輸送
・工場での1日の生産数は固定
・輸送コストは、品物1つあたりいくら、で固定
どこからどこへ、どれだけ運ぶと、コストが最小？
輸送問題：絵で解説
500個
1000個
1800個
2000個
2500個
800個
1500個
どの工場からどの小売店にどれだけ運ぶと、コストが最小？
輸送問題：用語
・工場 1,2,…,n
・小売店 1,2,…,m
・工場の生産量
s1 , s2 ,…, sn
・小売店の需要量
t1 , t2 ,…, tm
・工場 i から小売店 j
への輸送コスト ciｊ
＠10円
500個
1000個
1800個
2000個
800個
1500個
コスト最小化問題として定式化しよう
1500個
輸送問題：定式化
・工場 i から小売店 j への輸送量を xiｊとする
・工場 i の生産数 ≧ 工場 i から各小売店への輸送量の合計
 si ≧ Σ j=1,…,m xiｊ for i = 1,…,n
・小売店 j の需要数 ≦ 各工場 i から小売店 j への輸送量の合計
 tｊ ≦ Σ i=1,…,n xiｊ
for j = 1,…,m
・工場 i から小売店 j への輸送コストは ciｊ × xiｊ
・目的関数は、各工場・小売店間の輸送コストの和
 Σ i=1,…,n Σ j=1,…,m ciｊ × xiｊ
輸送問題：定式化 (2)
最小化
Σ i=1,…,n Σ j=1,…,m
制約条件
si ≧ Σ j=1,…,m xiｊ
tｊ ≦ Σ i=1,…,n xiｊ
xiｊ ≧ 0
ciｊ × xiｊ
for i = 1,…,n
for j = 1,…,m
for j = 1,…,m, i = 1,…,n
線形計画で解ける
※ この問題は、「単体法（シンプレックス法）で解くと、必ず整数
解が出てくる」という良い性質がある
（ただし、問題の係数が全て整数のとき）
最小費用流問題
・輸送問題に、中継地点と、各ルートの輸送量の上限を付けた問題
≦30
≦20
100個
どのように品物を運ぶとコストが最小になるか？
70個
例題
230,70
500
200,90
180,90
330,90
120,70
250
200,40
90,30
80,40
50,50
100
200,30
70,60
80,50
80,30
300
40,20
200,90
80,30
150
150,30
300,50
190
180,50
180,50
70
170,50
80,30
170,30
80,30
150,10
120
50,50
300
150,50
180,30
230
200,30
180,30
130
例題２
230,70
500
200,90
180,90
330,90
120,70
250
200,40
90,30
80,40
50,50
100
200,30
70,60
80,50
80,30
300
40,20
200,90
180,30
150
150,30
300,50
190
180,50
180,50
70
170,50
80,30
170,30
80,30
150,10
120
50,50
300
150,50
180,30
230
200,30
180,30
130
例題２ (最適解)
10
10
500
0
260
50
250
50
200
70
110
0
50
190
180
70
200
230
0
120
100
20
20
300
80
0
40
40
100
180
150
300
150
180
150
120
150
130
150
130
130
最小費用流問題：変数と入力
・工場・中継点・小売店と、扱うものが増えたので、
輸送計画とは少々違う記法を使おう
・工場・小売店・中継点を頂点と呼ぶ v1 , v2 ,…, vn
・頂点から頂点へのルートは枝と呼ぶ
・各頂点 vi の需要／生産量 bi
（ bi がプラスなら、 bi 個のものを作る工場
bi がマイナスなら、 bi 個のものを必要とする小売店
bi = 0 なら、中継点）
・頂点 vi から頂点 vj への輸送コスト： ciｊ
・頂点 vi から頂点 vj への輸送量の上限： uiｊ
（頂点と枝でできているものをネットワーク／グラフと呼ぶ）
最小費用流問題：定式化
・頂点 vi から頂点 vj への輸送量を xiｊとする
 頂点 vi から出て行く品物の数 Σj=1,…,n xiｊ
 頂点 vi に入ってくる品物の数 Σj=1,…,n xji
・（頂点 vi から出て行く数）－（頂点 vi に入って来る数）
が、頂点 vi の生産数／需要数と一致している必要がある

（Σj=1,…,m xji ）－（Σj=1,…,m xiｊ） = bi
・頂点 vi から vj への輸送量は uiｊ以下  xiｊ ≦ uiｊ
・残りの制約・目的関数は輸送問題と同じ
最小費用流問題：定式化 (2)
最小化
制約条件
Σi=1,…,n Σj=1,…,n ciｊ × xiｊ
（Σj=1,…,m xji ）－（Σ j=1,…,m xiｊ） = bi
0 ≦ xiｊ ≦ uiｊ
・この問題も線形計画問題
・輸送問題は、最小費用流問題の特殊ケース
・実は、最小費用流問題も、輸送問題の特殊ケースになっている
最小費用流問題の変形
・最小費用流問題の各枝を、輸送問題の（１頂点＋２枝）に変
換
最小費用流
bi
vi
ciｊ, uiｊ
輸送問題
bｊ
vｊ
b'ij = uiｊ
b'i = bi - uiｊ
0
vi
ciｊ
vｊ
vij
b'j = bｊ
・ vi 、vj は、複数個作らない（共有する）
この変形を、全ての枝について行う
最小費用流問題の変形 (2)
・ vi から vj に y 流れる
 bi が bi - y に減り、 bj が bj + y に増える。コストは ciｊ y
・ vij から vi , vj に uij - y, y ずつ流れる
 bi が bi - y に減り、 bj が bj + y に増える。コストは ciｊ y
※ 0 ≦ y ≦ uij
bi-y
y
vi
bｊ+y
vｊ
b'ij = uiｊ
uiｊ-y
vij
y
b'i = bi - uiｊ
vi
vｊ
b'j = bｊ
両者は等価：
この変形を、全ての枝について行えばよい
最小費用流問題の解法
・輸送問題は、「単体法（シンプレックス法）で解くと、必ず整数解
が出てくる」
・最小費用流問題は輸送問題の特殊ケース
 最小費用流問題も「単体法（シンプレックス法）で解くと、必ず
整数解が出てくる」
シンプレックス法以外にも、いくつかのアルゴリズムがある
・最短路増加法
・負閉路除去法
・コストスケーリング法・容量スケーリング法
．．．
流量に下限がある場合
bi
vi
liｊ ≦xiｊ ≦ uiｊ
bｊ
bi - liｊ
vｊ
vi
bｊ+ liｊ
0≦xiｊ ≦ uiｊ - liｊ
・あらかじめ vij に liｊだけ流している、と考えればよい
vｊ
工場・小売店は１つでも良い
・工場がたくさん、小売店もたくさんある問題でも、
工場・小売店がひとつしかない問題に変換できる。
b1
b4
b5
b2
b3
b6
b7
工場・小売店は１つでも良い (2)
・スーパー工場、スーパー小売店を作り、そこですべて生産・販売
・スーパー工場⇒工場、小売店⇒スーパー小売店の枝の上限を、
もとの生産量にする

必ずその分だけ流れる
usi = lsi = bi
s
b1+b2+b3
uit = lit = bi
t
b4+b5+b6+b7
最低生産量・販売量
・ s から工場への枝の下限・上限をいじると、各工場の最
低･最高生産量が設定できる
・同じようにして、各小売店の最低販売量・最大販売量が
設定できる
lsi ≦xsi ≦ usi
s
lit ≦xit ≦ uit
t
最小費用流問題の特殊ケース
・最短路問題
ネットワークの各枝にコスト ciｊが与えられているとき、
頂点 s から頂点 t へのルートの中で、最小コストのものを見つ
ける問題
※ uiｊ = 1 、 bs = 1, bt = -1、他の頂点 vi に対しては bi = 0 とした
最小費用流問題と等価
・ダイクストラ法などのアルゴリズムを使えば、かなり高速に最
適解が見つかる
最小費用流問題の特殊ケース (2)
・最大流問題
ネットワークの各枝に輸送量の上限 uiｊが与えられているとき、
頂点 s から頂点 t へ流せる最大流量を求める
s
t
プリフロープッシュ法・極大流追加法でO(n4) 時間で最適解が求まる
最大流問題の変形
・すべての枝のコストを 0 、 b=0 として、
以下の新しい枝を１つ付け加えればよい
（なるべくたくさん流すのが、最適解になる。）
s
t
コスト -1, 容量無限大
部品組立てネットワーク (1)
・いくつかの工場でできているネットワークを考える
各工場では、何種類かの部品を使ってある1種類の製品を
作り、それを出荷しているとする
s
t
部品組立てネットワーク (2)
・各工場では、一種類の製品しか作らない
・各工場の生産量は、上限・下限がある
・枝には運送コストが設定されている
s
t
どの工場でどれだけ品物を作り、どの工場からどの工場へ
どれくらい製品を運べばコストが最小になるだろうか
組立て計画：変数と入力
・製品 1,…,n
・製品 p を作る工場 vp1 , vp2 ,…, vpn
・製品工場 vpi での生産コストfpi
・各工場 vpi の生産量の上限・下限 lpi,upi
・頂点 vpi から頂点 vqj への輸送コスト： cpiqｊ
・頂点 vpi から頂点 vqj への輸送量上下限： lpiqｊ,upiqｊ
・製品 p を作るために必要な部品 1,…,n の数 qp1 , qp2 ,…, qpn
以下変数：
・工場 vpi の生産量を ypi とする
・工場 vpi から工場 vrj への輸送量を xpirｊとする
部品組立て計画：制約条件
・生産量の上限・下限の制約：
lpi ≦ ypi ≦ upi
・輸送量上下限の制約： lpiqｊ ≦ xpiqｊ ≦ upiqｊ
・生産量と部品のつじつま： qpr ypi = Σj xrjpi
・生産量と出荷量のつじつま： ypi = Σr,j xpirj
目的関数：
・工場 vpi での生産コスト＝ fpi ypi
・工場 vpi から工場 vqj への輸送コスト＝
 Σ fpi ypi ＋ Σ cpiqｊ xpiqｊ
線形計画になる
cpiqｊ xpiqｊ
組立て計画：制約条件
・組立て計画は線形計画になる
しかし、輸送問題とは異なり、最適解に小数が含まれることもある
・通常、この手の問題は規模が大きい
・しょせん、製品ロスがある
などの理由から、実用上は、適当に丸めてしまっても
問題にならない
生産計画
・組立て計画で、ある期間の最適生産計画を作る問題．こ
んどは、それぞれの枝を使って運ぶのにどれくらい時間
がかかるか、という要素も考えに入れる
s
t
生産計画
・小売店、または t での、今後の需要予測が与えられている
とする。（どの週にどれくらい売れそうか）
・運送コスト、生産コスト、生産量上下限なども、時期によって
異なるとする（世界規模で工場を持つメーカーなどの問題）
s
t
各週、小売店に必要量の品物が届くような、
最小コストの輸送・生産プランを作りたい
生産計画：変数と入力
時刻 T での：
・製品工場 vpi での生産コスト： fTpi
・各工場 vpi の生産量の上限・下限： lTpi, uTpi
・頂点 vpi から頂点 vqj への輸送コスト： cTpiqｊ
・頂点 vpi から頂点 vqj への輸送時間： dTpiqｊ
・頂点 vpi から頂点 vqj への輸送量上下限： lTpiqｊ,uTpiqｊ
以下変数：
・工場 vpi の生産量を yTpi とする
・工場 vpi から工場 vqj への輸送量を xTpiqｊとする
※ あとは組立て計画と同じ
生産計画：制約条件
時刻 T での：
・生産量の上限・下限の制約：
lTpi ≦ yTpi ≦ uTpi
・輸送量上下限の制約： lTpiqｊ ≦ xTpiqｊ ≦ uTpiqｊ
・生産量と部品のつじつま： qpr yTpi = Σj xT-drjpirjpi
・生産量と出荷量のつじつま： yTpi = Σr,j xTpirj
目的関数：
・工場 vpi での生産コスト＝ fTpi yTpi
・工場 vpi から工場 vqj への輸送コスト＝ cTpiqｊ xTpiqｊ
 Σ fTpi yTpi ＋ Σ cTpiqｊ xTpiqｊ
線形計画になる
生産計画：バリエーション
・時刻 T での工場 vpi の生産に、時間 hTpi が必要なとき
 生産量と出荷量のつじつま： yTpi = Σr,j xTpirj
を yTpi = Σr,j xT+ hTpi pirj とする
・工場 i から工場 j への品物の運搬時間が変化する dTpirj 場合：
 生産量と部品のつじつま： qpr yTpi = Σr,j xT-drjpirjpi
を qpr yTpi = Σr,j xT- dtpirj rjpi とする
・製品を出荷まで倉庫に保持できる場合：
※ 時刻 T での工場 vpi の保管コストを gTpi とする
時刻Tの保管量＝（時刻Tまでの生産量）－（時刻T までの出荷量）
 保管コスト＝ gTpi × （Σ1≦w≦T ywpi － Σ1≦w≦TΣ1≦j≦n xwpirj ）
これも線形計画になる
生産計画：問題の大きさ
・生産計画はとても大きな問題になる
例）工場30、期間50週とすると、変数の数は
およそ 50×30×30 ＝ 45000
商用ソフトでも、ぎりぎり1時間で解けるくらい
※ 不要な変数を消去したり、不要な制約をなくしたりして、
問題を簡単にして解く
まとめ
・
・
・
・
・
・
輸送問題の紹介と線形計画での定式化
最小費用流問題の紹介、輸送問題と等価であること
最小費用流問題のバリエーション、変形
部品組立て計画の紹介と定式化
生産計画の紹介と定式化
商用ソフトでの生産計画求解時間

Download Report