制約条件 - 経営システム工学科 実験・演習のページ

経営システム工学入門実験
ロジスティクス 第3回
2006/7/3
担当教員 森戸 晋
担当助手 後藤 允
協力: 森戸研究室修士学生
ビールゲーム表彰
総合評価(発表+総費用)
上位2チームを以下に表彰します

4班(ODAI)

6班(株式会社 白髭)
パレット回送問題
+250
出超局(都会)
+100
〒
郵便局Y
140
120
〒
郵便局X
270
-180
70
〒
郵便局A
40
20
90
〒
郵便局Z
100
60
50
250
130
160
90
〒
郵便局B
入超局(田舎)
-90
10
20
〒
郵便局C
-120
40
〒
郵便局D
70
10
10
30
+150
120
-110
パレット回送問題のデータ
X
X
Y
Z
A
B
C
D
受取量計
120
90
50
40
30
20
350
Y
140
270
120
90
70
50
740
実パレット
局間移動量
Z
A
B
C
100
70
50
30
250
180
130
160
100
70
80
40
10
50
30
10
10
50
70
20
30
50
20
120
500
480
300
450
D
60
150
40
30
30
90
400
送出量 受取量
合計 合計 送出-受取
450
350
100
990
740
250
650
500
150
300
480 -180
210
300
-90
330
450 -120
290
400 -110
3220 3220
0
生産計画問題(2製品、3リソース)

大久保工場では、鉄鋼、電力、労働力という3種類のリソー
スを使って、2種類の製品を生産しています。この工場では、
いま来週の生産計画を立てようとしています。手持ちのリ
ソースの範囲で、利益最大とする生産計画を求めてください。
製品1 製品2

鉄鋼
電力
労働力
利益
1
1
3
2
2
1
1
3
来週使えるリソース
許容上限
14
8
18
数理計画問題(最適化問題)の定式化



変数(variables)の定義
なにが制御可能か。なにを動かして最適
化を達成しようとするのか。
目的関数(objective function)の定義
計画をどう評価するのか。評価値を大きく
したいのか、小さくしたいのか。
制約条件(constraints)の定義
どのような制約条件があるのか。
線形計画問題

変数(決めること)




製品1の生産量
製品2の生産量
x1
x2
最大化 z=2 x1 + 3 x 2 (目的関数:利益)
制約条件
x1 + 2 x 2 ≦ 14 (鉄鋼)
x1 + x 2 ≦ 8 (電力)
3 x1 + x 2 ≦ 18 (労働力)
x1,x2≧0
(非負条件)
線形計画問題(LP)
(Linear Programming)



目的関数、制約条件がすべて線形関数から
なる
変数は、原則として非負の実数(連続変数)
最大化
z =Σ j=1,...,ncj xj
制約条件
Σ j=1,...,naij xj = bi , i=1,...,m
xj ≧0 , j=1,...,n
ソルバー使用上の留意点
• 「変化させるセル」(変数セル)はなるべく一箇
所にまとめる
– 複数の部分に分かれている場合はコンマ区切り
• 式をコピーする場合は、セルの相対参照と絶対
参照を使いわける(セルの絶対参照切替はF4)
• 「オプション」で、「線形モデルで計算」と「非負
数を仮定する」にチェックを忘れずに
• 整数条件や0-1条件が必要なときは、制約条
件の指定の中で、変化させるセルを「区間」(=
整数)または「デー」(0-1)に
輸送問題(Transportation Problem)
問題のシナリオ: 早稲田工業では、4ヵ所の原料処理場 A,B,C,D で処理された原料を使って、3 つ
の工場 X,Y,Z で生産を行っている。7 月の処理場、および工場の生産計画はすでに決まっている。こ
の原料の輸送は危険を伴うため、非常にコストがかさむ。輸送費は、輸送量*輸送単価で計算できる。
各処理場から工場に送ることのできる原料の供給量、各工場が生産に必要とする原料の必要量が下表
のように与えられ、さらに、各処理場から各工場までの輸送単価が既知であるとき、総輸送費が最小
となる輸送計画を求めたい。
工場X
輸送量
(xij)
必要量
工場Y
工場Z
処理場A
処理場B
処理場C
処理場D
10
25
15
供給量
18
9
12
11
輸送問題
供給量
18
処理場A
必要量
6
5 1
9
12
11
処理場B
処理場C
処理場D
4
工場X
10
工場Y
25
工場Z
15
5
6
3
6
8
7 2
10
枝上に輸送距離
輸送問題
(Transportation Problem)


変数(決めたいこと)
処理場iから工場jへの輸送量xij (≧0)
制約条件
1)処理場iからの輸送量は処理場iの供給量以
下
2)工場jへの輸送量は、工場jの必要量以上

目的関数(評価尺度;狙い)
延輸送距離を最小化
輸送問題の数式による表現



変数
xij =処理場iから工場jへの輸送量≧0
目的関数 最小化 6xAX+xAY+ 5xAZ+
4xBX+5xBY+…+2xDY+10xDZ
制約条件
xAX+xAY+ xAZ≦18(処理場Aの送出量≦処理場Aの供給量)
...
xAX+xBX+xCX +xDX≧15( 工場Xへの輸送量≧工場Xの必
要量)
...
輸送問題の数式による表現

データ
処理場iの供給量ai, 工場jの必要量bj
処理場iから工場jへの距離cij



変数
xij =処理場iから工場jへの輸送量≧0
目的関数 最小化 ΣiΣjcijxij
制約条件
Σjxij ≦ai (処理場iから送り出される量≦処理場iの供給量)
Σixij ≧bj ( 工場jへ輸送される量
≧工場jの必要量)
パレット回送問題の言葉による表
現



流れの特徴: 都会から地方へのもの
の流れが、地方から都会へのものの
流れより多い
特徴によって生じる問題: ほっておく
と、都市のパレットあるいはケース(以
下、パレット)がなくなる
対策: 余っているところから、足りな
いところに効率よく送る
コンピュータに問題を解かせる



コンピュータに輸送問題を解かせるために
は、解法が必要
解法については、「基礎OR」などで学習
数理計画を解くためのパッケージ
①EXCELのソルバー(小規模な問題)
②商用数理計画パッケージ
CPLEX、OPL、XpressーMP、...
今日の演習・宿題



「鉄鋼電力労働力の生産計画問題」、「輸送
問題」をソルバーで解く(すでに終了)
(実験後半)
さまざまな問題を(数理計画で定式化して)ソ
ルバーで解く
宿題は、レポートとして提出
締切7月10日(月)13時
提出箇所:51号館2階レポートボックス
宿題1-1 (問題16)
(問題16)乗捨てレンタカーの回送
R社は、北海道の函館、室蘭、千歳、小樽、札
幌、旭川、帯広に営業所を構え、50台の車
で観光客相手にレンタカー事業を営んでい
る。週末に車を借り出した客の多くが、最終
旅行地近くの営業所に車を乗り捨てていくた
め、週明けの車の配置が週末の需要と著し
く異なる。このため、毎週、週の半ばに週末
の需要に合わせて、社員が手分けして車を1
台ずつ回送している。R社の社長は、常々、
回送にかかる手間や時間、それに費用を
もっと節約できないものかと考えている。
右の表で、ある週の各営業所における週明け
の配置と週末の需要(台数)と、各地点間の
(最短)距離(km)が与えられている。どうした
ら適切な回送計画が立てられるだろうか?
レンタカーの週明けの配置
と週末の需要
函館 室蘭 千歳 小樽 札幌 旭川 帯広
週明け配置 10
1
25
2
6
2
4
週末の需要
4
4
13
3
15
8
2
各営業所間の(最短)距離
(km)
始点
終点 函館 室蘭 千歳 小樽 札幌 旭川 帯広
函館
室蘭
千歳
小樽
札幌
旭川
帯広
0
191
278
273
309
447
600
191
0
87
161
125
263
416
278
87
0
74
38
176
329
273
161
74
0
36
174
327
309
125
38
36
0
138
291
447
263
176
174
138
0
179
600
416
329
327
291
179
0
宿題1-2 (問題17)
(問題17)駅伝レースの出場順序
W大学の競走部では、今年も大学対
選手の区間別走行タイム(分)
抗の駅伝レースに参加することに
なった。この駅伝は、1チーム5人編
成の5区間レースである。起伏の激
区間
しさが区間ごとに異なり、選手に
1区 2区 3区 4区 5区
よって区間ごとの走行タイムがかな
A 22.2 33.2 16.6 39.3 50.3
り違うため、選手登用の優劣がチー
ムの成績に大きく影響する。A・B・ 選 B 21 32.8 16.7 40.2 51.2
C・D・Eの5人の選手を選抜し、各区 手 C 24.6 36.1 18.5 37.4 46.4
D 26.0 35.2 19.1 36.9 45.7
間ごとに選手の走行タイム (分)を
計ったところ、以下の表の結果を得
E 22.5 33.6 17.5 37.8 49.0
た。どの選手をどの区間に出場させ
るのが最適か。
宿題2
身近な問題、高尚な問題等、何でもよいで
すから、最適化問題として捉えられる(現実
的な)問題のシナリオを提示し、数理計画問
題として定式化して下さい。定式化では、変
数が何、目的関数が何で、制約条件が何か
を簡潔、かつ、正確に示して下さい。また、小
規模な問題でもよいので具体的なデータを与
えて、EXCELソルバーで解き、その結果をも
とに簡単なレポートをまとめてください。