1、1Chapter 32 線性規劃模型(Linear Programming model)是在一組線性的限制式(a set of linear constraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標函數(objective function)線性規劃模型由下列三個部分組成:一組決策變數(A set of decision variables)一個特定的目標函數(An objective function)一組線性的限制式(A set of constraints)3 線性規劃重要性許多現實問題本身就適用線性規劃模型 已存在許多有效的求解技巧已存在許
2、多著名的成功應用實例 Manufacturing Marketing Finance(investment)Advertising Agriculture4 線性規劃重要性 線性規劃套裝軟體之所產生的結果提供有用的如果則“what if”的分析資訊5 參數具有確定性確定性(certainty)目標函數與限制式符合固定規模報酬固定規模報酬之假設(constant returns to scale)疊加性疊加性之假設：決策變數間沒有互動性，即某函數之總價值只能藉由線性加總求得 連續性連續性(Continuity)之假設變數值必須再某一個可行範圍內6 Galaxy 生產兩種玩具模型:宇宙光Space
3、 Ray.射擊手Zapper.資源限制(Resources)1000 磅特殊塑膠化合物(special plastic)每週40 小時生產時間(40 hrs of production time per week)7 市場需求(Marketing requirement)每週總產量至多 700 打 Space Rays週產量不能過Zappers 350打以上 技術係數(Technological inputs)(Table 2.2)Space Rays 每打需要 2 pounds 塑膠與 3分鐘生產時間 Zappers每打需要 1pound 塑膠與 4分鐘生產時間8 生產需求:Space Ra
4、y每打利潤(profit)$8，Zappers每打利潤(profit)$5 盡量多生產Space Ray，剩餘資源再生產Zapper 目前生產計畫:Space Rays =450 dozenZapper =100 dozenProfit =$4100 per week8(450)+5(100)9管理是尋求一個生產排程為了是能增加公司的利潤 Management is seeking a production schedule that will increase the companys profit.10線性規劃模式可以提供一種深線性規劃模式可以提供一種深入與聰明之方法來解決此問題入與聰明之
5、方法來解決此問題A linear programming model can provide an insight and an intelligent solution to this problem.11Decisions variables)X1=每週生產的 Space Rays 打數 X2=每週生產的 Zappers 打數Objective Function):極大化每週總利潤 12Max 8X1+5X2 (每週總利潤)subject to2X1+1X2 1000 (塑膠原料,Plastic)3X1+4X2 2400 (生產時間,Production Time)X1+X2 700 (最
6、大產量,Total production)X1 -X2 350 (組合)Xj=0,j=1,2 (非負值,Nonnegativity)13 滿足模型全部限制式的所有點集合稱為滿足模型全部限制式的所有點集合稱為 The set of all points that satisfy all the constraints of the model is called a14 圖形表示法圖形表示法(graphical presentation)15The non-negativity constraints(非負限制式非負限制式)X2X1161000500FeasibleX2InfeasiblePro
7、duction Time 限制式限制式3X1+4X2 2400 Total production 限制式限制式 X1+X2 700(多餘多餘)500700Plastic限制式限制式2X1+X2 1000X1700171000500FeasibleX2InfeasibleProduction Time 限制式限制式3X1+4X2 2400 Total production 限制式限制式 X1+X2 700(多餘多餘)500700Mix限制式限制式X1-X2 350Plastic限制式限制式2X1+X2 1000X1700 可行點可行點(feasible points)有三種有三種內部點Inter
8、ior points.邊界點 Boundary points.端點Extreme points.1819由任一個 profit開始,say profit=$1,250.往利潤增加方向移動 increase the profit,if possible.持續平行移動到無法增加為止 continue until it becomes infeasibleOptimal Profit=$43605007001000500X2X1紅色線段紅色線段 Profit=$125020 Space Rays X1*=320 dozen Zappers X2*=360 dozen Profit Z*=$4360
9、此最佳解使用了所有的塑膠原料(plastic)與生產時間(production hours).2X1+1X2=1000 (塑膠原料,Plastic)3X1+4X2=2400 (生產時間,Production Time)Excel試算表束縛方程式束縛方程式(Binding Constraints):等式被滿足之限制式等式被滿足之限制式21 總產量(Total production)680 打(not 700打)Space Rays 產量只超過 Zappers 40打非束縛方程式非束縛方程式(Non-Binding Constraints)：最佳點不在其等式之限制式：最佳點不在其等式之限制式寬鬆寬
10、鬆(Slack)：限制式右邊與左邊的差額，代表資源的剩餘數量：限制式右邊與左邊的差額，代表資源的剩餘數量X1+X2 =680 700(總產量)X1 -X2 =-40 0)縮減成本RCj為此變數Xj每增加一單位(DXj=1)，目標函數會改變的值C1=2 X*=(0,600)X1=0C1=3.75 X*=(320,360)X1=3200 RC1=-Z1=-(3.75-2)=-1.75296001000500800X2X1Max 3.75X1+5X2Max 2X1+5X2(1,599.25)Z=2998.25(0,600)Z=3000X1 1X1=1 (由由X1=0X1=1)Z=2998.25-30
11、00=-1.75 RC1=-1.7530 問題：問題：若其他參數不變之前提下，若右手值變動一個單位，對於目標函數之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解31 發現：發現：任意變動束縛函數(Binding Constraints)之右手值，都會改變目前最佳解非束縛函數(Non-Binding Constraints)之右手值，當變動數量少於寬鬆(slack)或剩餘(surplus)量時，都不會改變目前最佳解此結果可以由影子價格(Shadow Price)來解釋32若其他輸入參數不變之前提下，限制式的影子價格 是當其對應的右手值增加一個單位時，對最佳目標函數值的變動量331
12、000500X2X15002X1+1x2=1000最佳解由(320,360)(320.8,359.4)Production time限制式限制式 X*=(320,360)Z*=$43602X1+1x2=1001 X*=(320.8,359.4)Z*=$4363.4當右手值增加(例如由10001001)則可行區域擴大Plastic限制式限制式Shadow price=4363.40 4360.00=3.40 34若其他輸入參數不變之前提下右手值的可行性範圍是影子價格依然不變的 右手值可以變動的範圍.在可行性範圍內，目標函數之改變量Change in objective value=影價Shado
13、w price*右手值變量Change in the right hand side value351000500X2X15002X1+1x2 =0,j=1,2,3 (非負值,Nonnegativity)淨邊際利潤淨邊際利潤=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0)=-$2.2 0大水槍不具生產價值大水槍不具生產價值 X*=(320,360,0)仍為最佳解仍為最佳解43 左手係數的變動(Changes in the left-hand side coefficients.)目目前前解解仍仍為為最最佳佳 No Yes 最最佳佳解解與與影影子子價價格格都都會會變變動
14、動 模模型型需需重重解解 束束縛縛限限制制式式 Yes 目目前前解解是是否否為為最最佳佳 No 44點選Galaxy.xls，可見輸入試算表點選工具規劃求解(Solver)，可見下列對話視窗.Equal To:By Changing cells這些儲存格包含 決策變數$B$4:$C$4加入限制式按此鍵 Set Target cell$D$6此儲存格包含 目標函數值$D$7:$D$10$F$7:$F$10所有具有相同方向之限制式必須包含在一個”Excel限制式”.45點選Galaxy.xls，可見輸入試算表.Equal To:$D$7:$D$10=$F$7:$F$10By Changing ce
15、lls這些儲存格包含 決策變數$B$4:$C$4Set Target cell$D$6此儲存格包含 目標函數值點選“選項/Option”並勾選”線性規劃”與“非負”.46點選Galaxy.xls，可見輸入試算表Equal To:$D$7:$D$10=$F$7:$F$10By Changing cells$B$4:$C$4Set Target cell$D$6按Solve以求最佳解 47Space RaysZappersDozens320360TotalLimitProfit854360Plastic211000=1000Prod.Time342400=2400Total11680=700Mix
16、1-1-40=350GALAXY INDUSTRIES48Space RaysZappersDozens320360TotalLimitProfit854360Plastic211000=1000Prod.Time342400=2400Total11680=700Mix1-1-40=350GALAXY INDUSTRIESSolver 能提供分析報告與最佳解49Microsoft Excel 9.0 Answer ReportWorksheet:Galaxy.xlsGalaxyReport Created:11/12/2001 8:02:06 PMTarget Cell(Max)CellNam
17、eOriginal ValueFinal Value$D$6Profit Total43604360Adjustable CellsCellNameOriginal ValueFinal Value$B$4Dozens Space Rays320320$C$4Dozens Zappers360360ConstraintsCellNameCell ValueFormulaStatusSlack$D$7Plastic Total1000$D$7=$F$7Binding0$D$8Prod.Time Total2400$D$8=$F$8Binding0$D$9Total Total680$D$9=$F
18、$9Not Binding20$D$10 Mix Total-40$D$10=$F$10 Not Binding39050Microsoft Excel Sensitivity ReportWorksheet:Galaxy.xlsSheet1Report Created:Adjustable CellsFinal ReducedObjectiveAllowableAllowableCellNameValueCostCoefficientIncreaseDecrease$B$4Dozens Space Rays3200824.25$C$4Dozens Zappers36005 5.6666666
19、671ConstraintsFinalShadowConstraintAllowableAllowableCellNameValuePriceR.H.SideIncreaseDecrease$D$7Plastic Total10003.41000100400$D$8Prod.Time Total24000.42400100650$D$9Total Total68007001E+3020$D$10 Mix Total-4003501E+3039051 不可行性不可行性(Infeasibility):一模型中無可行點 (p.96)無窮性無窮性(Unboundness):一模型中可行解存在，但目標函
20、數沒有限制。目標函數值為無限大(在極大化問題)或無限小(在極小化問題)(p.98)多重解多重解(Alternate solution):一模型中有一個以上的可行點使目標函數為最佳(p.98)52 1No point,simultaneously,lies both above line and below lines and.1232353Solver呈現無法找呈現無法找到可行解之結果到可行解之結果54無窮性無窮性 可行區域可行區域Maximize目標函數目標函數 55Solver呈現呈現Set Cell值無法收斂值無法收斂之結果之結果56 Solver 沒有提醒沒有提醒”多重最佳解多重最佳解
21、”存在的情形存在的情形 有有”多重最佳解多重最佳解”的的LP模型，則某個變數模型，則某個變數Xj 的目的目標函數的標函數的allowable increase or allowable decrease為為0.以以Solver尋找多重最佳解的程序如下：尋找多重最佳解的程序如下：(p.99)觀察到某個變數觀察到某個變數Xj中中 Allowable increase =0,或Allowable decrease=0.57 加入一個限制式加入一個限制式:Objective function=Current optimal value.If Allowable increase=0,change the objective to Maximize Xj If Allowable decrease=0,change the objective to Minimize Xj Excel試算表58 線性規劃軟體可以求解大型線性模型 大多數線性規劃軟體使用的技巧 單形法(Simplex Method)(原理部分見補充CD3)內點法(Interior Point Method)整數線性規劃軟體使用的技巧 如切面法(Cutting Plane Method)分支界限法(Branch and Bound Point Method)(原理部分見補充CD3)
