生産計画を立てる • 簡単なバージョン：輸送問題 定式化、最小費用流、バリエーション • 部品組立て計画 定式化、バリエーション

Presentation on theme: "生産計画を立てる • 簡単なバージョン：輸送問題 定式化、最小費用流、バリエーション • 部品組立て計画 定式化、バリエーション"— Presentation transcript:

1 生産計画を立てる • 簡単なバージョン：輸送問題 定式化、最小費用流、バリエーション • 部品組立て計画 定式化、バリエーション
　　定式化、最小費用流、バリエーション • 部品組立て計画 　　定式化、バリエーション • 生産計画

2 どこからどこへ、どれだけ運ぶと、コストが最小？
輸送問題：運送コストを最小化 • いくつかの工場がある • いくつかの小売店がある • どれも一種類の品目を扱っている • 毎日、朝、売れる分だけ工場から小売店に輸送 • 工場での1日の生産数は固定 • 輸送コストは、品物1つあたりいくら、で固定 どこからどこへ、どれだけ運ぶと、コストが最小？

3 どの工場からどの小売店にどれだけ運ぶと、コストが最小？
輸送問題：絵で解説 500個 1000個 1800個 2000個 800個 2500個 1500個 どの工場からどの小売店にどれだけ運ぶと、コストが最小？

4 輸送問題：用語 • 工場 1,2,…,n • 小売店 1,2,…,m ＠10円 • 工場の生産量 500個 s1 , s2 ,…, sn
• 小売店の需要量 　　 t1 , t2 ,…, tm • 工場 i から小売店 j 　 への輸送コスト ciｊ ＠10円 500個 1000個 1800個 2000個 800個 1500個 1500個 コスト最小化問題として定式化しよう

5 輸送問題：定式化 • 工場 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ｊ

6 輸送問題：定式化 (2) 最小化 Σ i=1,…,n Σ j=1,…,m ciｊ × xiｊ 制約条件
　　si ≧ Σ j=1,…,m xiｊ for i = 1,…,n 　　tｊ ≦ Σ i=1,…,n xiｊ for j = 1,…,m 　　xiｊ ≧ for j = 1,…,m, i = 1,…,n 線形計画で解ける ※ この問題は、「単体法（シンプレックス法）で解くと、必ず整数解が出てくる」という良い性質がある 　　（ただし、問題の係数が全て整数のとき）

7 どのように品物を運ぶとコストが最小になるか？
最小費用流問題 • 輸送問題に、中継地点と、各ルートの輸送量の上限を付けた問題 ≦20 ≦30 70個 100個 どのように品物を運ぶとコストが最小になるか？

8 例題 230,70 200,90 190 500 180,90 330,90 180,50 180,50 120,70 70 250 90,30 170,50 200,40 80,40 230 50,50 200,30 80,30 170,30 100 70,60 80,30 80,50 120 80,30 40,20 50,50 300 200,90 300 150,50 80,30 300,50 200,30 180,30 150 130 150,10 180,30 150,30

9 例題２ 230,70 200,90 190 500 180,90 330,90 180,50 180,50 120,70 70 250 90,30 170,50 200,40 80,40 230 50,50 200,30 80,30 170,30 100 70,60 80,30 80,50 120 80,30 40,20 50,50 300 200,90 300 150,50 180,30 300,50 200,30 180,30 150 130 150,10 180,30 150,30

10 例題２ (最適解) 10 10 190 500 260 180 70 50 70 250 50 110 200 230 50 200 120 100 20 80 120 20 40 40 300 100 300 150 180 180 150 130 150 130 150 130 150

11 最小費用流問題：変数と入力 • 工場・中継点・小売店と、扱うものが増えたので、 輸送計画とは少々違う記法を使おう
• 工場・小売店・中継点を頂点と呼ぶ v1 , v2 ,…, vn • 頂点から頂点へのルートは枝と呼ぶ • 各頂点 vi の需要／生産量 bi 　　（ bi がプラスなら、 bi 個のものを作る工場 　　　 bi がマイナスなら、 bi 個のものを必要とする小売店 　　　 bi = 0 なら、中継点） • 頂点 vi から頂点 vj への輸送コスト： ciｊ • 頂点 vi から頂点 vj への輸送量の上限： uiｊ （頂点と枝でできているものをネットワーク／グラフと呼ぶ）

12 最小費用流問題：定式化 • 頂点 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ｊ • 残りの制約・目的関数は輸送問題と同じ

13 最小費用流問題：定式化 (2) 最小化 Σi=1,…,n Σj=1,…,n ciｊ × xiｊ
制約条件　　（Σj=1,…,m xji ）－（Σ j=1,…,m xiｊ） = bi 　　　　　　　　　　0 ≦ xiｊ ≦ uiｊ • この問題も線形計画問題 • 輸送問題は、最小費用流問題の特殊ケース • 実は、最小費用流問題も、輸送問題の特殊ケースになっている

14 最小費用流問題の変形 • 最小費用流問題の各枝を、輸送問題の（１頂点＋２枝）に変換 最小費用流 輸送問題 b'i = bi - uiｊ bi
　　最小費用流　　　　　　　　　　　　　輸送問題 b'i = bi - uiｊ bi bｊ ciｊ, uiｊ b'ij = uiｊ vi vi vｊ vij ciｊ vｊ b'j = bｊ • vi 、vj は、複数個作らない（共有する） この変形を、全ての枝について行う

15 両者は等価： この変形を、全ての枝について行えばよい
最小費用流問題の変形 (2) • vi から vj に y 流れる 　　　 bi が bi - y に減り、 bj が bj + y に増える。コストは ciｊ y • vij から vi , vj に uij - y, y ずつ流れる 　　 ※ 0 ≦ y ≦ uij b'i = bi - uiｊ bi-y bｊ+y y b'ij = uiｊ uiｊ-y vi vij vi vｊ vｊ y b'j = bｊ 両者は等価：　　この変形を、全ての枝について行えばよい

16 最小費用流問題の解法 • 輸送問題は、 「単体法（シンプレックス法）で解くと、必ず整数解が出てくる」
• 最小費用流問題　は　輸送問題の特殊ケース  最小費用流問題も 「単体法（シンプレックス法）で解くと、必ず整数解が出てくる」 シンプレックス法以外にも、いくつかのアルゴリズムがある • 最短路増加法 • 負閉路除去法 • コストスケーリング法・容量スケーリング法 　　．．．

17 流量に下限がある場合 bi bｊ bi - liｊ bｊ+ liｊ liｊ ≦xiｊ ≦ uiｊ 0≦xiｊ ≦ uiｊ - liｊ vi
• あらかじめ vij に liｊ だけ流している、と考えればよい

18 工場・小売店は１つでも良い • 工場がたくさん、小売店もたくさんある問題でも、 工場・小売店がひとつしかない問題に変換できる。 b4 b1

19 工場・小売店は１つでも良い (2) • スーパー工場、スーパー小売店を作り、そこですべて生産・販売
• スーパー工場⇒工場、小売店⇒スーパー小売店の枝の上限を、もとの生産量にする　　  　　必ずその分だけ流れる uit = lit = bi s t usi = lsi = bi b1+b2+b3 b4+b5+b6+b7

20 最低生産量・販売量 • s から工場への枝の下限・上限をいじると、各工場の最低･最高生産量が設定できる
• 同じようにして、各小売店の最低販売量・最大販売量が設定できる lit ≦xit ≦ uit lsi ≦xsi ≦ usi s t

21 最小費用流問題の特殊ケース • 最短路問題 ネットワークの各枝にコスト ciｊ が与えられているとき、
頂点 s から頂点 t へのルートの中で、最小コストのものを見つける問題 ※ uiｊ = 1 、 bs = 1, bt = -1、他の頂点 vi に対しては bi = 0 とした最小費用流問題と等価 • ダイクストラ法などのアルゴリズムを使えば、かなり高速に最適解が見つかる

22 最小費用流問題の特殊ケース (2) • 最大流問題 ネットワークの各枝に輸送量の上限 uiｊ が与えられているとき、
頂点 s から頂点 t へ流せる最大流量を求める s t プリフロープッシュ法・極大流追加法でO(n4) 時間で最適解が求まる

23 最大流問題の変形 • すべての枝のコストを 0 、 b=0 として、 以下の新しい枝を１つ付け加えればよい
（なるべくたくさん流すのが、最適解になる。） s t コスト　-1,　 容量無限大

24 部品組立てネットワーク (1) • いくつかの工場でできているネットワークを考える
各工場では、何種類かの部品を使ってある1種類の製品を作り、それを出荷しているとする s t

25 部品組立てネットワーク (2) • 各工場では、一種類の製品しか作らない • 各工場の生産量は、上限・下限がある
• 枝には運送コストが設定されている s t どの工場でどれだけ品物を作り、どの工場からどの工場へ どれくらい製品を運べばコストが最小になるだろうか

26 組立て計画：変数と入力 • 製品 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ｊ とする

27 部品組立て計画：制約条件 • 生産量の上限・下限の制約： lpi ≦ ypi ≦ upi
• 輸送量上下限の制約： lpiqｊ ≦ xpiqｊ ≦ upiqｊ • 生産量と部品のつじつま：　 qpr ypi = Σj xrjpi • 生産量と出荷量のつじつま：　 ypi = Σr,j xpirj 目的関数： • 工場 vpi での生産コスト　＝　 fpi ypi • 工場 vpi から工場 vqj への輸送コスト　 ＝ cpiqｊ xpiqｊ 　 　 Σ fpi ypi ＋ Σ cpiqｊ xpiqｊ 線形計画になる

28 組立て計画：制約条件 • 組立て計画は線形計画になる しかし、輸送問題とは異なり、最適解に小数が含まれることもある
• 通常、この手の問題は規模が大きい • しょせん、製品ロスがある などの理由から、実用上は、適当に丸めてしまっても 問題にならない

29 生産計画 • 組立て計画で、ある期間の最適生産計画を作る問題．こんどは、それぞれの枝を使って運ぶのにどれくらい時間がかかるか、という要素も考えに入れる s t

30 各週、小売店に必要量の品物が届くような、
生産計画 • 小売店、または t での、今後の需要予測が与えられているとする。（どの週にどれくらい売れそうか） • 運送コスト、生産コスト、生産量上下限なども、時期によって異なるとする（世界規模で工場を持つメーカーなどの問題） s t 各週、小売店に必要量の品物が届くような、 最小コストの輸送・生産プランを作りたい

31 生産計画：変数と入力 時刻 T での： • 製品工場 vpi での生産コスト： fTpi
• 各工場 vpi の生産量の上限・下限： lTpi, uTpi • 頂点 vpi から頂点 vqj への輸送コスト： cTpiqｊ • 頂点 vpi から頂点 vqj への輸送時間： dTpiqｊ • 頂点 vpi から頂点 vqj への輸送量上下限： lTpiqｊ,uTpiqｊ 以下変数： • 工場 vpi の生産量を yTpi とする • 工場 vpi から工場 vqj への輸送量を xTpiqｊ とする ※ あとは組立て計画と同じ

32 生産計画：制約条件 時刻 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ｊ 線形計画になる

33 生産計画：バリエーション これも線形計画になる • 時刻 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 ） これも線形計画になる

34 生産計画：問題の大きさ • 生産計画はとても大きな問題になる 例）工場30、期間50週とすると、変数の数は
およそ 50×30×30 ＝ 45000 商用ソフトでも、ぎりぎり1時間で解けるくらい ※　不要な変数を消去したり、不要な制約をなくしたりして、 　　　問題を簡単にして解く

35 まとめ • 輸送問題の紹介と線形計画での定式化 • 最小費用流問題の紹介、輸送問題と等価であること • 最小費用流問題のバリエーション、変形
• 部品組立て計画の紹介と定式化 • 生産計画の紹介と定式化 • 商用ソフトでの生産計画求解時間