第４回 線形計画 2000年11月 第4回 線形計画.

Presentation on theme: "第４回 線形計画 2000年11月 第4回 線形計画."— Presentation transcript:

1 第４回 線形計画 2000年11月 第4回 線形計画

2 内容 線形計画と図式解法 辞書と単体法 番外編 Excelによる線形計画 2000年11月 第4回 線形計画

3 線形計画法の大まかな歴史 1947年 単体法 Dantzig 比較的単純な方法 1979年 楕円体法 Khachian
多項式時間解法，非実際的 1984年 内点法 Karmarkar 理論的には多項式時間解法，実際的に効率的 2000年11月 第4回 線形計画

4 丼チェーン店長の悩み トンコケ丼，コケトン丼，ミックス丼の3種類
トンコケ丼を1杯作るには，200グラムの豚肉と100グラムの鶏肉コケトン丼を1杯作るには，100グラムの豚肉と200グラムの鶏肉ミックス丼は，豚肉，鶏肉，牛肉を100グラムずつミックス 豚，鶏，牛の肉は，最大1日あたり6キログラム，6キログラム，3キログラム 販売価格は，トンコケ丼1杯1500円，コケトン丼1杯1800円，ミックス丼1杯3000円 お店の利益を最大にするためには，あなたは丼を何杯ずつ作るように指示を出せばよいのだろうか？ 2000年11月 第4回 線形計画

5 丼チェーン店長の悩み（図） 種類 トンコケ丼 コケトン丼 ミックス丼 使用可能量 （百グラム） 豚 2 1 60 鶏 牛 30 利益
30 利益 （百円） 15 18 2000年11月 第4回 線形計画

6 定式化 トンコケ丼の数：x1（杯） 変数 コケトン丼の数：x2 （杯） ミックス丼の数：x3 （杯）
目的関数 制約式 材料の使用可能量の上限 （百グラム） 丼の数は非負 2000年11月 第4回 線形計画

7 定式化 線形 変数の加減算より構成 すべての式が線形な問題 線形計画問題 解 変数の組 実行可能解 全ての制約式を満たす解 最適解
目的関数を最大にする実行可能解 最適目的関数値（最適値） 最適解における目的関数値 2000年11月 第4回 線形計画

8 定式化 豚肉の使用可能量を表す制約式 制約式を等号で満たすような集合 {(x1, x2, x3) | 2x1 + x2 + x3 = 60}
（3次元の場合）平面 （4次元以上の場合）→超平面 半空間 全ての制約式を満たす領域→半空間の共通部分 実行可能領域 2000年11月 第4回 線形計画

9 直感的理解 平面 2x1 + x2 + x3 = 60 2000年11月 第4回 線形計画

10 直感的理解 平面 x1 + 2x2 + x3 = 60 2000年11月 第4回 線形計画

11 直感的理解 平面 x3 = 30 2000年11月 第4回 線形計画

12 直感的理解 丼チェーン店の例題の 実行可能領域 多面集合 2000年11月 第4回 線形計画

13 多面集合 数式による表現 有界な多面集合→多面体 2000年11月 第4回 線形計画

14 多面集合 線形計画問題の目的 ↓ 実行可能領域の中で目的関数が最大の点を求めること 目的関数を等式に直す
z = 15x1 + 18x2 + 30x3 zを固定したとき，この制約は平面 実行可能領域との共通部分が なくならないように zを大きくする 端点 2000年11月 第4回 線形計画

15 定理1：多面集合の端点 端点でない 多面集合が有界である 必ず端点を持つ P 多面集合が直線を含まない
（直線と半直線・線分は異なることに注意） 端点 2000年11月 第4回 線形計画

16 端点を持たない多面集合の例 有界でない多面集合 2000年11月 第4回 線形計画

17 最適解が端点でない例 直線上は全て最適解 P 目的関数の方向ベクトル 直線上の両端は端点なので 端点の中に最適解が存在することは 保証される
2000年11月 第4回 線形計画

18 定理２ 線形計画問題に最適解が存在し，線形計画問題の制約からなる多面集合が少なくとも1つの端点を持つならば，多面集合の端点の中に最適解が存在する． 2000年11月 第4回 線形計画

19 ちょっと練習 丼チェーン店の例題の制約を表す多面体の全ての端点 （８つ）を求めてみよう． それぞれの平面の式は
2x1 + x2 + x3 = 60 x1 + 2x2 + x3 = 60 x3 = 30 x1 = x2 = x3 = 0 2000年11月 第4回 線形計画

20 さらに練習 丼チェーン店の例題の制約を表す多面体の全ての端点 （８つ）に対応する目的関数値を求めてみよう． 2000年11月
第4回 線形計画

21 最適解 最適解 目的関数値：1230（対応する端点は(10,10,30)）
丼チェーンの店長は，トンコケ丼を10杯，コケトン丼を10杯，ミックス丼を30杯作るよう指示すればよい． 1日あたり123000円の利益をあげることができる． 2000年11月 第4回 線形計画

22 実際には 実際には，全ての端点を数え上げてその目的関数を計算することは非効率的． 効率的に最適解を算出したほうがよい． 2000年11月
第4回 線形計画

23 単体法 適当な端点から出発して目的関数値を改良する端点に移動 ↓ 最小木問題で勉強した改善法の考え方 1947年
Dantzigが単体法を考案 太陽（目的関数）の暖かさに誘われた蟻さんが多面体の縁をたどって移動 2000年11月 第4回 線形計画

24 余裕変数 制約式を等式に直すために余裕（スラック）変数を導入 標準形 2000年11月 第4回 線形計画

25 余裕変数を含めた端点と目的関数値 x1 x2 x3 s1 s2 s3 目的関数値（百円） 60 30 450 540 20 660 900
60 30 450 540 20 660 900 15 1125 1170 10 1230 いずれもちょうど3つの変数が0になっている 2000年11月 第4回 線形計画

26 基底変数 0に固定した変数→非基底変数 それ以外の変数→基底変数 基底解 m本の等式制約，n個の変数 m個の変数が基底変数
2000年11月 第4回 線形計画

27 基底解 基底解 端点解 丸が基底解 黒丸は端点解 全ての変数が非負である基底解 →実行可能基底解 2000年11月 第4回 線形計画

28 単体法 実行可能基底解を次々と生成することによって 最適解を得る方法 基底解を表すには色々な流儀 今回は辞書による方法を採用 モダン
2000年11月 第4回 線形計画

29 初期辞書 非基底変数(=0) 初期辞書 z =0 +15x1 +18x2 +30x3 s1=60 －2x1 －x2 －x3
辞書表現 平たく言えば等式の集合 x1=x2=x3=0 s1=60, s2=60, s3=30 z=0 を表す これを改善する 2000年11月 第4回 線形計画

30 改善 改善＝zの値を増加 x3を1大きくすれば zは30増加 z =0 +15x1 +18x2 +30x3 x1を1大きくすれば
2000年11月 第4回 線形計画

31 改善 x1， x2を固定しx3をどこまで大きくできる？ s1=60 －x3 s1，s2，s3は非負より s2=60 －x3
2000年11月 第4回 線形計画

32 辞書の変形 初期辞書 z =0 +15x1 +18x2 +30x3 s1=60 －2x1 －x2 －x3
次の辞書 z =?? +??x1 +??x2 +??s3 s1=?? +??x1 +??x2 +??s3 s2=?? +??x1+??x2 +??s3 x3=?? ??s3 どうなる？ 等式変形を使う 2000年11月 第4回 線形計画

33 辞書の変形 次はここに注目 1反復後の辞書 z =900+15x1+18x2－30s3 s1=30 －2x1 －x2 +s3
2000年11月 第4回 線形計画

34 ちょっと練習 x2を基底変数としてみよう． どれを非基底変数とする？ 改善後の辞書は？ 2000年11月 第4回 線形計画

35 辞書を用いた単体法の法則 法則１：非基底変数のうち最も改善効果の大きい変数を選び， それを基底変数にするように辞書を変形する
法則２：最も改善効果の大きい変数が複数ある場合には， 添え字の最も小さいものを選ぼう（巡回対策） 法則３：辞書の変形の際に，基底変数から非基底変数にできるものが複数ある場合には，やっぱり添え字の最も小さいものを選ぼう（退化対策） わかりづらい場合には 非基底変数→＝の右側の変数 基底変数→＝左側の変数 と読み替えても可 2000年11月 第4回 線形計画

36 さらに練習 ３反復後の辞書を作ってみよう 2000年11月 第4回 線形計画

37 最終辞書 もう改善できそうにないので終了 2000年11月 第4回 線形計画

38 番外編 Excelによる線形計画 2000年11月 第4回 線形計画

39 Excelに書く 次は変数を導入 2000年11月 第4回 線形計画

40 変数を導入 トンコケ丼の生産量x1を表す コケトン丼の生産量x2を表す ミックス丼の生産量x3を表す 次は目的関数の設定 2000年11月
第4回 線形計画

41 目的関数の設定 次は制約条件の設定 2000年11月 第4回 線形計画

42 豚肉の使用量の制約 2000年11月 第4回 線形計画

43 鶏肉の使用量の制約 2000年11月 第4回 線形計画

44 牛肉の使用量の制約 これでシート上で必要な準備は整った，次はソルバーの使い方 2000年11月 第4回 線形計画

45 初めてのソルバー 2000年11月 第4回 線形計画

46 ソルバーとは OKを選択すれば 使えるようになる 2000年11月 第4回 線形計画

47 ソルバーの起動 2000年11月 第4回 線形計画

48 ソルバーの設定 2000年11月 第4回 線形計画

49 ソルバーの設定 2000年11月 第4回 線形計画

50 ソルバーの設定 2000年11月 第4回 線形計画

51 ソルバーの設定 2000年11月 第4回 線形計画

52 ソルバーの実行 準備が整ったら実行 2000年11月 第4回 線形計画

53 ソルバーの結果 これはどちらでも良い 2000年11月 第4回 線形計画

54 流通最適化工学 追加資料 Excel 2010でのソルバー起動法
ファイル/（下部の）オプション/アドイン （Excel2007ではOfficeボタン，Excel2003ではツール/アドイン） ソルバーアドインをクリックして，下部の管理でExcelアドインの設定ボタンを押す． 上部リボンのデータの右端にソルバーができているので，それをクリック 2000年11月 第4回 線形計画

55 GurobiソルバーとPythonで求解！Gurobi (1)
MIP solver Developed by: Zonghao Gu, Edward Rothberg，Robert Bixby Free academic license！計算機センターでGurobiを一度起動した後， Python IDLEで記述 “gurobipy” モジュールの読み込み from gurobipy import * モデルオブジェクト model をModelクラスから生成（引数はモデルの名前 model = Model(“Product Mix") 2000年11月 第4回 線形計画

56 Gurobi (2) 変数オブジェクトをmodelオブジェクトのaddVarメソッドを用いて生成（引数は名前；省略可） x1 = model.addVar(name="x1") x2 = model.addVar(name="x2") x3 = model.addVar(name="x3") モデルの更新（制約を追加する前に必ず呼ぶ） model.update() 2000年11月 第4回 線形計画

57 Gurobi (3) 目的関数の設定 model.setObjective(15*x1 + 18*x2 + 30*x3, GRB.MAXIMIZE) 制約の追加 model.addConstr(2*x1 + x2 + x3 <= 60) model.addConstr(x1 + 2*x2 + x3 <= 60) model.addConstr(x3 <= 30) 最適化 model.optimize() 2000年11月 第4回 線形計画

58 Pythonのリストを用いた記述 変数オブジェクトをリストxに追加 x=[] for i in range(3): var=model.addVar() x.append(var) 制約 “x1 + x2 + x3 <= 2”の記述 model.addConstr( sum(x) <= 2 ) 　もしくは model.addConstr( quicksum(x) <= 2 ) （高速版） 2000年11月 第4回 線形計画

59 Pythonの辞書を用いた記述 名前(“TonKoke”, “KokeTon”, “Mix”) を変数オブジェクトの写像する辞書 x={} x[“TonKoke”]= model.addVar() x[“KokeTon”]= model.addVar() x[“Mix”]= model.addVar() 制約“2x1 + x2 + x3 <= 30”の追加 model.addConstr( 2*x[“TonKoke”]+ x[“KokeTon”] x[“Mix”] <=30 ) 2000年11月 第4回 線形計画

60 辞書を用いたデータ入力 Bowels, Profit = multidict({“TonKoke”:15, “KokeTon”:18, “Mix”:30}) => Bowels=[“TonKoke”, “KokeTon“, “Mix“] キー（丼）のリスト Profit[“TonKoke”]=15, Profit[“KokeTon”]=18, ... 利益の辞書 Meats, Inventory = multidict({“Pork":60, “Chiken":60, “Beef":30}) 肉のリスト Meetsと使用可能量の辞書の同時生成 Use = { (“Pork”,“TonKoke”):2, (“Pork”,“KokeTon”):1, (“Pork”,”Mix“):1, (“Chicken”,“TonKoke”):1, } 肉と丼のタプル（組）をキー，使用量を値とした辞書 2000年11月 第4回 線形計画

61 辞書を用いた最適化 x = {} # 変数を保管する辞書 for j in Bowels: # 丼ごとに変数の生成
x[j] = model.addVar() model.update() #モデルの更新 model.setObjective(quicksum(Profit[j]*x[j] for j in Bowels), GRB.MAXIMIZE) #目的関数の最大化 for i in Meats: model.addConstr(quicksum(Use[i,j]*x[j] for j in Bowels) <= Inventory[i]) #制約の追加 model.optimize() print “Obj=”,model.ObjVal #最適値の表示 2000年11月 第4回 線形計画