第1回授業説明用パワーポイント

「シミュレーション」
森戸担当分第１回
線形計画モデル（１）
12/02/2005
森戸晋
生産計画問題（２製品、３リソース）
• 早稲田工場では、鉄鋼、電力、労働力という３種類の
リソースを使って、２種類の製品を生産している
• 来週の生産計画を立案したい
• 限られたリソースの範囲内で、利益最大の製品の生
産単位数（非負実数ならよいものと仮定）を決めたい
製品１製品２来週使えるリソース許容上限
鉄鋼
１
２
１４
電力
１
１
８
労働力
３
１
１８
利益
２
３
生産計画問題の定式化
線形計画問題
• 変数（決めること）
– 製品１の生産量
– 製品２の生産量
ｘ１
ｘ２
• 最大化ｚ＝２ｘ１＋３ｘ２（目的関数：利益）
• 制約（条件）ｘ１＋２ｘ２ ≦ １４（鉄鋼）
ｘ１＋ｘ２ ≦ ８（電力）
３ｘ１＋ｘ２ ≦ １８（労働力）
ｘ１，
ｘ２ ≧０
生産計画問題の幾何学的表現
ｘ2
ｚ＝一定
０
ｘ１
線形計画問題による定式化
• 定数与えられた問題のデータ
• 変数(variables)の定義
なにが制御可能か。なにを動かして最適化を達
成しようとするのか。
• 目的関数(objective function)の定義
計画をどう評価するのか。評価値を大きくしたい
のか、小さくしたいのか。
• 制約条件(constraints)の定義
どのような制約条件があるのか。
線形計画問題（ＬＰ）
(Linear Programming)
• 目的関数、制約条件がすべて線形（１次）関数
からなる
• 変数は（原則として非負の）実数（連続変数）
• 最大化ｚ＝ Σj=1,...,nｃｊｘｊ
制約条件
Σj=1,...,nａｉｊｘｊ＝ｂｉ , i=1,...,m
ｘｊ ≧０ , j=1,...,n
• 最小化問題や、制約条件が不等式（≦、≧）の問
題、変数の非負条件がない問題などあり
• 効率のよい解法が存在（単体法、内点法）
線形関数とは
• 変数ｘ（たとえば、生産量）の値が倍になれば、
必要となる資源も倍になる
– 世の中は必ずしも線形でないが、多くの実際問題が
線形モデルで表現、あるいは、近似できる
目的関数あれこれ
•
•
•
•
•
•
•
•
•
利益の最大化
費用の最小化
効用の最大化
リスクの最小化（分散の
最小化）
売上高の最大化
純現在価値の最大化
余剰従業員数の最小化
従業員数の最小化
顧客満足の最大化
• 納期遅れの最小化
• 最大完了時刻の最小化
• 移動距離（移動費用）の
最小化
• 配送費用の最小化
• 段取り回数（段取り費用）
の最小化
• 流量の最大化
• 渋滞（滞留時間）の最小
化
• ．．．
制約条件あれこれ
• 個別の変数に上下限制約がついている
Astro_sales ≦ 50
• 流量（水、エネルギー、交通量等）に制限がある
Supply1 + Supply2 + Supply3 ≦ 100
• 資源が限られている
6・Product1 + 9・Product2 ≦ 300 （原料供給制約）
• 一定品質を守らなければならない
6・Iron1 + 9・Iron2 ≧ 7 （原料品質制約）
• 流量がバランスしなければならない
Stockt＝ Stockt-1 + Productiont － Salest（期末在庫
量）
数理計画法の有効性
• 大規模な線形計画問題（ＬＰ）を高速に解く解法とパッ
ケージが存在
どれぐらいの問題が解ける？
• かなりの規模の整数計画問題（ＩＰ）／組合せ最適化問
題も解ける
• 単に最適解を得るだけでなく、問題の入力データ（具体
的には、制約条件や目的関数の係数）が変化した場合
の「感度分析」が容易
• 線形計画問題や整数計画問題として定式化可能な問
題が多く存在（線形計画は石油業界、鉄鋼業界等、整
数計画や組合せ最適化の応用領域は極めて広範）
（３製品版）生産計画問題
• 早稲田工場では、３つの製品、製品１、製品２、
製品３を生産）
• 原料として、鉄鋼、電力、労働力を使用
• １個当たり製品１製品２製品３保有量
利益
２万円３万円４万円
鉄鋼
１
２
３
１４
電力
１
１
２
８
労働力
３
１
２
１８
生産計画問題のEXCELによる求解
• 変数（決めること） → 変化させるセル
– 製品１、２、３の生産量
ｘ１，ｘ２，ｘ３
• 最大化ｚ＝２ｘ１＋３ｘ２＋４ｘ３（目的関数：利
益）
→ 目的セル
• 制約条件
ｘ１＋２ｘ２＋３ｘ３ ≦ １４（鉄鋼）
ｘ１＋ｘ２＋２ｘ３ ≦ ８（電力）
３ｘ１＋ｘ２＋２ｘ３ ≦ １８（労働力）
ｘ１，ｘ２，ｘ３≧０
ソルバーオプション設定
ソルバー使用上の留意点
• 「変化させるセル」（変数セル）はなるべく一箇
所にまとめる
– 複数の部分に分かれている場合はコンマ区切り
• 式をコピーする場合は、セルの相対参照と絶対
参照を使いわける（セルの絶対参照切替はF4）
• 「オプション」で、「線形モデルで計算」と「非負
数を仮定する」にチェックを忘れずに
• 整数条件や０－１条件が必要なときは、制約条
件の指定の中で、変化させるセルを「区間」（＝
整数）または「デー」（０－１）に
Microsoft Excel 8.0d 解答ﾚﾎﾟｰﾄ
ﾜｰｸｼｰﾄ名: [鉄鋼電力労働力.xls]３製品（鉄鋼電力労働力）
ﾚﾎﾟｰﾄ作成日: 01/10/08 15:59:40
目的ｾﾙ (最大値)
ｾﾙ
名前
$G$3 利益
変化させるｾﾙ
ｾﾙ
名前
$B$3 製品１生産量
$C$3 製品２生産量
$D$3 製品３生産量
制約条件
ｾﾙ
名前
$E$5 鉄鋼資源使用量
$E$6 電力資源使用量
$E$7 労働力資源使用量
計算前の値
ｾﾙの値
0
計算前の値
ｾﾙの値
0
0
0
ｾﾙの値
22
2
6
0
制約条件
ｽﾃｰﾀｽ
条件との差
14 $E$5<=$G$5 満たす
0
8 $E$6<=$G$6 満たす
0
12 $E$7<=$G$7 部分的に満たす
6
Microsoft Excel 8.0d 感度ﾚﾎﾟｰﾄ
ﾜｰｸｼｰﾄ名: [鉄鋼電力労働力.xls]３製品（鉄鋼電力労働力）
ﾚﾎﾟｰﾄ作成日: 01/10/08 15:59:40
変化させるｾﾙ
ｾﾙ
名前
$B$3 製品１生産量
$C$3 製品２生産量
$D$3 製品３生産量
計算限界目的ｾﾙ
許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
2
0
2
1
0.5
6
0
3
1
1
0
-1
4
1
1E+30
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$E$5 鉄鋼資源使用量
14
1
14
2
3
$E$6 電力資源使用量
8
1
8
1.2
1
$E$7 労働力資源使用量
12
0
18
1E+30
6
限界コスト、被約費用(reduced cost)
• 変数（列）に対応
• 二つの解釈が可能
①ｘｊ＝０である変数を無理に正にしようとしたと
きの、ｘｊ単位当たりの目的関数値の増加の度合
い
②ｘｊ＝０である変数を正にする可能性が生じる
（つまり、最適解が最適でなくなる）目的関数の
係数ｃｊの変化量
潜在価格(shadow price)，双対価格(dual price)
• 制約条件式（行）に対応（別名：単体乗数
(simplex multiplier), 双対変数(dual variable)）
• 当該制約条件の右辺定数以外のすべての係数
を元の問題のままにした上で、当該制約条件の
右辺定数を微小量増加させたときの、増加単位
量当たりの最適目的関数値の改善／改悪の度
合い
「最適（目的関数）値」関数
生産計画問題の鉄鋼リソースを例に
（問題の）他の条件が変わらないとしたときに、○○（例：鉄鋼）リ
ソースが変化したときの最適（目的関数）値の変化を示したグラフ
最
適
値 24
22
19
0
1
赤字は傾き
1.4
12
2
6
11
14 16
鉄鋼リソース許容量
家具の生産計画：問題の提示
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
7
5
2
B
160
8
4
8
C
40
3
8
4
D 生産能力（時間）
100
5
1000
5
720
2
640
a)切断時間の能力の余裕はいくらあるか。
b)製品Aを生産するようになるためには、製品Aの利益がいくらに
なる必要があるか。
c)製品B、１台当たりの利益が＄１００に落ちたときの最大総利益
はいくらになるか。
d)外部から研磨機が１時間当たり＄２０で借りられるとしたとき、
研磨機を借りるのがよいか。
e)無理に製品Cを作ろうとした場合、どんなことが言えるか。
f)仕上げ工程の生産能力を１００時間追加したときに、最大利益
はどうなるといえるか。
家具の生産計画：ソルバー結果
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
0
7
5
2
B
160
55
8
4
8
C
40
0
3
8
4
D 実際の生産時間
総利益
100
18800
100
生産能力（時間）
5
940
≦
1000
5
720
≦
720
2
640
≦
640
変化させるｾﾙ
ｾﾙ
$B$14
$C$14
$D$14
$E$14
名前
A
B
C
D
計算限界目的ｾﾙ許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
0 -10
90
10
1E+30
55
0
160
240
80
0 -130
40
130
1E+30
100
0
100
100
10
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$F$15 家具1台当たりの切断時間（時間）実際の生産時間
940
0
1000
1E+30
60
$F$16 家具1台当たりの研磨時間（時間）実際の生産時間
720
15
720
80
400
$F$17 家具1台当たりの仕上げ時間（時間）実際の生産時間
640 12.5
640
96
352
家具の生産計画：質問ａ）
a)切断時間の能力の余裕はいくらか。
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
0
7
5
2
B
160
55
8
4
8
C
40
0
3
8
4
D 実際の生産時間
総利益
100
18800
100
生産能力（時間）
5
940
≦
1000
5
720
≦
720
2
640
≦
640
変化させるｾﾙ
ｾﾙ
$B$14
$C$14
$D$14
$E$14
名前
A
B
C
D
計算限界目的ｾﾙ許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
0 -10
90
10
1E+30
55
0
160
240
80
0 -130
40
130
1E+30
100
0
100
100
10
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$F$15 家具1台当たりの切断時間（時間）実際の生産時間
940
0
1000
1E+30
60
$F$16 家具1台当たりの研磨時間（時間）実際の生産時間
720
15
720
80
400
$F$17 家具1台当たりの仕上げ時間（時間）実際の生産時間
640 12.5
640
96
352
家具の生産計画：質問ｂ）
b)製品Aを生産するようになるためには、製品Aの利益がいくらに
なる必要があるか。
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
0
7
5
2
B
160
55
8
4
8
C
40
0
3
8
4
D 実際の生産時間
総利益
100
18800
100
生産能力（時間）
5
940
≦
1000
5
720
≦
720
2
640
≦
640
変化させるｾﾙ
ｾﾙ
$B$14
$C$14
$D$14
$E$14
名前
A
B
C
D
計算限界目的ｾﾙ許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
0 -10
90
10
1E+30
55
0
160
240
80
0 -130
40
130
1E+30
100
0
100
100
10
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$F$15 家具1台当たりの切断時間（時間）実際の生産時間
940
0
1000
1E+30
60
$F$16 家具1台当たりの研磨時間（時間）実際の生産時間
720
15
720
80
400
$F$17 家具1台当たりの仕上げ時間（時間）実際の生産時間
640 12.5
640
96
352
家具の生産計画：質問ｃ）
c)製品B、１台当たりの利益が＄１００に落ちたときの最大総利益
はいくらになるか。
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
0
7
5
2
B
160
55
8
4
8
C
40
0
3
8
4
D 実際の生産時間
総利益
100
18800
100
生産能力（時間）
5
940
≦
1000
5
720
≦
720
2
640
≦
640
変化させるｾﾙ
ｾﾙ
$B$14
$C$14
$D$14
$E$14
名前
A
B
C
D
計算限界目的ｾﾙ許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
0 -10
90
10
1E+30
55
0
160
240
80
0 -130
40
130
1E+30
100
0
100
100
10
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$F$15 家具1台当たりの切断時間（時間）実際の生産時間
940
0
1000
1E+30
60
$F$16 家具1台当たりの研磨時間（時間）実際の生産時間
720
15
720
80
400
$F$17 家具1台当たりの仕上げ時間（時間）実際の生産時間
640 12.5
640
96
352
家具の生産計画：質問ｄ）
d)外部から研磨機が１時間当たり＄２０で借りられるとしたとき、
研磨機を借りるのがよいか。
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
0
7
5
2
B
160
55
8
4
8
C
40
0
3
8
4
D 実際の生産時間
総利益
100
18800
100
生産能力（時間）
5
940
≦
1000
5
720
≦
720
2
640
≦
640
変化させるｾﾙ
ｾﾙ
$B$14
$C$14
$D$14
$E$14
名前
A
B
C
D
計算限界目的ｾﾙ許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
0 -10
90
10
1E+30
55
0
160
240
80
0 -130
40
130
1E+30
100
0
100
100
10
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$F$15 家具1台当たりの切断時間（時間）実際の生産時間
940
0
1000
1E+30
60
$F$16 家具1台当たりの研磨時間（時間）実際の生産時間
720
15
720
80
400
$F$17 家具1台当たりの仕上げ時間（時間）実際の生産時間
640 12.5
640
96
352
家具の生産計画：質問ｅ）
e)無理に製品Cを作ろうとした場合、どんなことが言えるか。
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
0
7
5
2
B
160
55
8
4
8
C
40
0
3
8
4
D 実際の生産時間
総利益
100
18800
100
生産能力（時間）
5
940
≦
1000
5
720
≦
720
2
640
≦
640
変化させるｾﾙ
ｾﾙ
$B$14
$C$14
$D$14
$E$14
名前
A
B
C
D
計算限界目的ｾﾙ許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
0 -10
90
10
1E+30
55
0
160
240
80
0 -130
40
130
1E+30
100
0
100
100
10
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$F$15 家具1台当たりの切断時間（時間）実際の生産時間
940
0
1000
1E+30
60
$F$16 家具1台当たりの研磨時間（時間）実際の生産時間
720
15
720
80
400
$F$17 家具1台当たりの仕上げ時間（時間）実際の生産時間
640 12.5
640
96
352
家具の生産計画：質問ｆ）
f)仕上げ工程の生産能力を１００時間追加したときに、最大利益
はどうなるといえるか。
家具の種類
家具1台当たりの利益（ドル）
家具1台当たりの切断時間（時間）
家具1台当たりの研磨時間（時間）
家具1台当たりの仕上げ時間（時間）
A
90
0
7
5
2
B
160
55
8
4
8
C
40
0
3
8
4
D 実際の生産時間
総利益
100
18800
100
生産能力（時間）
5
940
≦
1000
5
720
≦
720
2
640
≦
640
変化させるｾﾙ
ｾﾙ
$B$14
$C$14
$D$14
$E$14
名前
A
B
C
D
計算限界目的ｾﾙ許容範囲内許容範囲内
値
ｺｽﾄ
係数
増加
減少
0 -10
90
10
1E+30
55
0
160
240
80
0 -130
40
130
1E+30
100
0
100
100
10
制約条件
計算潜在制約条件許容範囲内許容範囲内
ｾﾙ
名前
値価格
右辺
増加
減少
$F$15 家具1台当たりの切断時間（時間）実際の生産時間
940
0
1000
1E+30
60
$F$16 家具1台当たりの研磨時間（時間）実際の生産時間
720
15
720
80
400
$F$17 家具1台当たりの仕上げ時間（時間）実際の生産時間
640 12.5
640
96
352
鉄鉱石配合問題（Blending Problem)
• ４鉱山から鉄鉱石を購入し、配合して使用
• 配合されたものは、一定の品質基準を満たす必
要あり（ここでは、元素A,B,C）
• 最小費用の配合割合を決めたい（具体的に「何
ton必要」という情報はなし）
• この種の配合問題は、いろいろなシナリオで
しょっちゅう発生する（dog foodの配合、農薬の
配合、金属の配合、．．．）
鉄鉱石配合問題データ
元素
１
A
10
B
90
C
45
コスト 800
(＄／ton)
鉱山
２
３
3
8
150
75
25
20
400 600
４
2
175
37
500
必要
最小量
5
100
30
鉄鉱石配合問題のLP定式化
• 変数：Ｔｉ＝鉱山ｉの配合比率（≧0）
• 目的関数：最小化 ton当たりの費用
• 制約条件：各元素(A-C)の品質基準満足
配合比率の合計は1
• Min ｚ＝800T1＋400T2＋600T3＋500T4 (費用)
• s.t. 10T1＋ 3T2 ＋ 8T3＋ 2T4≧ 5 (元素A)
90T1＋150T2＋75T3＋175T4≧100 (元素B)
45T1＋ 25T2＋20T3＋ 37T4≧ 30 (元素C)
T1，
T2， T3，
T4 ≧ 0(非負条件)
この解答は間違い!!!
鉄鉱石配合問題のLP定式化
• 変数：Ｔｉ＝鉱山ｉの配合比率（≧0）
• 目的関数：最小化 ton当たりの費用
• 制約条件：各元素(A-C)の品質基準満足
配合比率の合計は1
• Min ｚ＝800T1＋400T2＋600T3＋500T4 (費用)
• s.t. 10T1＋ 3T2 ＋ 8T3＋ 2T4≧ 5 (元素A)
90T1＋150T2＋75T3＋175T4≧100 (元素B)
45T1＋ 25T2＋20T3＋ 37T4≧ 30 (元素C)
T1＋
T2＋ T3＋
T4＝ 1 (合計1)
T1，
T2， T3，
T4 ≧ 0(非負条件)
農場経営（Buster Ｓｏｄ）問題
•
•
•
•
灌漑設備付1,200acresの農場の年間計画
wheat, alfalfa, beefの生産
2,000 acre feet（水量の単位）の用水割当
beef($600/t)
wheat($1.60/bushel; 50 bushel/acre)
alfalfa(sell $34/t, buy $36/t; 3t/acre)
• 「技術的」条件（問題文中の表）
• 最大利益（または、最小費用）の計画立案
農場経営問題「技術的」データ
農場経営（Buster Sod）問題の技術的条件
労働・機械水
土地 alfalfa
Activity 等コスト($) (acre ft)(acres)(tons)
1 acre wheat
8
1.5
1
1 acre alfalfa 30
2.5
1
1 ton of beef 40
0.1 0.05
4
農場経営問題のLP定式化
• ①変数(variables)
②目的関数(objective function)
③制約条件(constraints)
• （決定）変数：wheat､alfalfa､beefの生産量
alfalfaの販売・購入量
• 目的関数：「収益ー費用」最大
• 制約条件：土地の許容上限
用水の許容上限
alfalfaのバランス
第1回のキーワード
• 数理計画法（数理計画問題）、変数、制約条件、
目的関数（評価関数）
• 線形関数とはなにか
• 定式化
• 線形計画問題の定式化
• EXCELソルバーによる求解
• 最適解、最適（目的関数）値、限界コスト、潜在
コスト

Download Report