资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,線性規劃與整數規劃模式,Linear and Integer Programming Models,Chapter 2,1,線性規劃模型,(Linear Programming model),是在一組線性的限制式,(a set of linear constraints),之下，尋找極大化,(maximize),或極小化,(minimize),一個特定的目標函數,(objective,function),線性規劃模型由下列三個部分組成,:,一組決策變數,(A set of decision variables),一個特定的目標函數,(An objective function),一組線性的限制式,(A set of constraints),2.1,線性規劃簡介,Introduction to Linear Programming,2,線性規劃簡介,Introduction to Linear Programming,線性規劃重要性,許多現實問題本身就適用線性規劃模型,已存在許多有效的求解技巧,已存在許多著名的成功應用實例,Manufacturing,Marketing,Finance (investment),Advertising,Agriculture,3,線性規劃重要性,線性規劃套裝軟體之所產生的結果提供有用的如果,則,“what,if”,的分析資訊,線性規劃簡介,Introduction to Linear Programming,4,線性規劃模型之假設,Assumptions for Linear Programming,參數具有,確定性,(,certainty),目標函數與限制式符合,固定規模報酬,之假設,(,constant returns to scale),疊加性,之假設：決策變數間沒有互動性,，即某函數之總價值只能藉由線性加總求得,連續性,(Continuity,),之假設變數值必須再某一個可行範圍內,1,單位產品,$4,，,3Hrs,生產,500,單位產品,$4*500=$2000,，,3*500=1,500Hrs,生產,5,典型範例,The Galaxy Industries Production Problem,Galaxy,生產兩種玩具模型,:,宇宙光,Space Ray.,射擊手,Zapper.,資源限制,(Resources),1000,磅特殊塑膠化合物,(special plastic),每週,40,小時生產時間,(40 hrs of production time per week),6,市場需求,(Marketing requirement),每週總產量至多,700,打,Space Rays,週產量不能過,Zappers 350,打以上,技術係數,(Technological inputs) (Table 2.2),Space Rays,每打需要,2 pounds,塑膠與,3,分鐘生產時間,Zappers,每打需要,1pound,塑膠與,4,分鐘生產時間,典型範例,The Galaxy Industries Production Problem,7,生產需求,:,Space Ray,每打利潤,(profit) $8,，,Zappers,每打利潤,(profit) $5,盡量多生產,Space Ray,，剩餘資源再生產,Zapper,目前生產計畫,:,Space Rays = 450 dozen,Zapper = 100 dozen,Profit = $4100 per week,典型範例,The Galaxy Industries Production Problem,8(450) + 5(100),8,管理是尋求一個生產排程為了是能增加公司的利潤,Management is seeking a production schedule that will increase the companys profit.,9,線性規劃模式可以提供一種深,入與聰明之方法來解決此問題,A linear programming model,can provide an insight and an,intelligent solution to this problem.,10,決策變數,(,Decisions variables),:,X,1,=,每週生產的,Space Rays,打數,X,2,=,每週生產的,Zappers,打數,目標函數,(,Objective Function):,極大化每週總利潤,典型範例線性規劃模式,The Galaxy Linear Programming Model,11,Max 8X,1,+ 5X,2,(,每週總利潤,),subject to,2X,1,+ 1X,2,1000 (,塑膠原料,Plastic),3X,1,+ 4X,2,2400 (,生產時間,Production Time),X,1,+ X,2,700 (,最大產量,Total production),X,1,- X,2,350 (,組合,),X,j, = 0, j = 1,2 (,非負值,Nonnegativity),典型範例線性規劃模式,The Galaxy Linear Programming Model,12,2.3,線性規劃模式圖形分析,Graphical Analysis of Linear Programming,滿足模型全部限制式的所有點集合稱為,The set of all points that satisfy all the constraints of the model is called a,可行區域,FEASIBLE REGION,13,圖形表示法,(graphical presentation),所有限制式,(all the constraints),目標函數,(objective function),可行點,(three types of feasible points),14,The non-negativity constraints,(,非負限制式,),X,2,X,1,圖形分析,可行區域,Graphical Analysis the Feasible Region,15,1000,500,Feasible,X,2,Infeasible,Production Time,限制式,3X,1,+4X,2,2400,Total production,限制式,X,1,+X,2,700 (,多餘,),500,700,Plastic,限制式,2X,1,+X,2,1000,X,1,700,圖形分析,可行區域,Graphical Analysis the Feasible Region,16,1000,500,Feasible,X,2,Infeasible,Production Time,限制式,3X,1,+4X,2,2400,Total production,限制式,X,1,+X,2,700 (,多餘,),500,700,Mix,限制式,X,1,-X2,350,Plastic,限制式,2X,1,+X,2,1000,X,1,700,圖形分析,可行區域,(p. 6768),Graphical Analysis the Feasible Region,可行點,(feasible points),有三種,內部點,Interior points.,邊界點,Boundary points,.,端點,Extreme points.,17,以圖形求解是為了尋求最佳解,Solving Graphically for an Optimal Solution,18,尋求最佳解圖解程序,(p.71),The search for an optimal solution,由任一個,profit,開始, say profit = $1,250.,往利潤增加方向移動,increase the profit, if possible.,持續平行移動到無法增加為止,continue until it becomes infeasible,Optimal Profit =$4360,500,700,1000,500,X,2,X,1,紅色線段,Profit,=$1250,19,最佳解,(p.69),Summary of the optimal solution,Space Rays X,1,*,= 320 dozen,Zappers X,2,*,= 360 dozen,Profit Z,*,= $4360,此最佳解使用了所有的塑膠原料,(plastic),與生產時間,(production hours).,2X,1,+ 1X,2,= 1000 (,塑膠原料,Plastic),3X,1,+ 4X,2,= 2400 (,生產時間,Production Time),Excel,試算表,束縛方程式,(Binding Constraints):,等式被滿足之限制式,20,最佳解,(p.7071),Summary of the optimal solution,總產量,(Total production) 680,打,(not 700,打,),Space Rays,產量只超過,Zappers 40,打,非束縛方程式,(Non-Binding Constraints),：最佳點不在其等式之限制式,寬鬆,(Slack),：限制式右邊與左邊的差額，代表資源的剩餘數量,X1 + X2,= 680 700 (,總產量,),X1 - X2 = -40 0),縮減成本,RC,j,為此變數,Xj,每增加一單位,(,D,Xj,=1),，目標函數會改變的值,C1=2 X*=(0,600),X1=0,C1=3.75 X*=(320,360),X1=3200, RC,1,=,-Z,1,=-(3.75-2)=-1.75,縮減成本,Reduced cost (p.78),28,600,1000,500,800,X,2,X,1,Max 3.75X,1,+ 5X,2,Max 2X,1,+ 5X,2,目標函數係數之敏感性分析,縮減成本,(p.79),(1,599.25),Z=2998.25,(0,600),Z=3000,X,1,1,X,1,=1 (,由,X1=,0,X1=,1),Z=2998.25-3000 = -1.75,RC,1,=-1.75,29,問題：,若其他參數不變之前提下，若右手值變動一個單位，對於目標函數之最佳解有何影響,?,多少變動單位,(,增加或減少,),，可以保持目前最佳解,(2),右手邊數值 之敏感性分析,(p.78) Sensitivity Analysis of Right-Hand Side Values,30,發現：,任意變動束縛函數,(Binding Constraints),之右手值，都會改變目前最佳解,非束縛函數,(Non-Binding Constraints),之右手值，當變動數量少於寬鬆,(slack),或剩餘,(surplus),量時，都不會改變目前最佳解,此結果可以由,影子價格,(Shadow Price),來解釋,右手邊數值 之敏感性分析,Sensitivity Analysis of Right-Hand Side Values,31,影子價格,Shadow Prices (p.80),若其他輸入參數不變之前提下，,限制式的影子價格,是當其對應的右手值增加一個單位時，對最佳目標函數值的變動量,32,1000,500,X,2,X,1,500,2X,1,+ 1x,2,=1000,最佳解由,(320,360)(320.8,359.4),Production time,限制式,X*=(320,360),Z*= $4360,2X,1,+ 1x,2,=1001,X* =(320.8,359.4),Z* = $4363.4,當右手值增加,(,例如,由,10001001),則可行區域擴大,影子價格,Shadow Price ,圖形表示,graphical demonstration,Plastic,限制式,Shadow price =,4363.40 4360.00 = 3.40,33,可行性範圍,Range of Feasibility (p.81),若其他輸入參數不變之前提下,右手值的可行性範圍,是影子價格依然不變的 右手值可以變動的範圍,.,在可行性範圍內，,目標函數之改變量,Change in objective value = ,影價,Shadow price,*,右手值變量,Change in the right hand side value,34,塑膠的可行性範圍,Range of Feasibility (p.81),1000,500,X,2,X,1,500,2X,1,+ 1x,2, = 0, j = 1,2,3 (,非負值,Nonnegativity),淨邊際利潤,=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0) = -$2.2 0,大水槍不具生產價值,X*=(320,360,0),仍為最佳解,42,其他後最佳性變動,(p.85),Other Post - Optimality Changes,左手係數的變動,(Changes in the left - hand side coefficients.),43,2.5,使用,Excel Solver,尋找最佳解與分析結果,點選,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,限制式,”.,44,使用,Excel Solver,點選,Galaxy.xls,，可見輸入試算表,.,Equal To:,$D$7:$D$10=$F$7:$F$10,By Changing cells,這些儲存格包含,決策變數,$B$4:$C$4,Set Target cell,$D$6,此儲存格包含,目標函數值,點選,“,選項,/Option”,並勾選,”,線性規劃,”,與,“,非負,”.,45,點選,Galaxy.xls,，可見輸入試算表,Equal To:,$D$7:$D$10=$F$7:$F$10,By Changing cells,$B$4:$C$4,Set Target cell,$D$6,使用,Excel Solver,按,Solve,以求最佳解,46,使用,Excel Solver ,最佳解,47,使用,Excel Solver ,最佳解,Solver,能提供分析報告與最佳解,48,使用,Excel Solver ,解答報表,Answer Report,49,使用,Excel Solver ,敏感性分析報表,Sensitivity Report,50,不可行性,(Infeasibility):,一模型中無可行點,(p.96),無窮性,(,Unboundness,):,一模型中可行解存在，但目標函數沒有限制。目標函數值為無限大,(,在極大化問題,),或無限小,(,在極小化問題,),(p.98),多重解,(Alternate solution):,一模型中有一個以上的可行點使目標函數為最佳,(p.98),無單一最佳解之模型,51,1,No point, simultaneously,lies both above line and below lines and,.,1,2,3,2,3,不可行模型,Infeasible Model,52,不可行模型,Solver,呈現之結果,Solver,呈現無法找到可行解之結果,53,無窮性,Unbounded solution,可行區域,Maximize,目標函數,54,無窮性模型,Solver,呈現之結果,Solver,呈現,Set Cell,值無法收斂之結果,55,Solver,沒有提醒,”,多重最佳解,”,存在的情形,有,”,多重最佳解,”,的,LP,模型，則某個變數,X,j,的目標函數的,allowable increase or allowable decrease,為,0,.,以,Solver,尋找多重最佳解的程序如下：,(p.99),觀察到某個變數,X,j,中,多重最佳解模型,Solver,呈現之結果,Allowable increase = 0,或,Allowable decrease = 0.,56,加入一個限制式,:,Objective function = Current optimal value.,If Allowable increase = 0, change the objective to Maximize X,j,If Allowable decrease = 0, change the objective to Minimize X,j,Excel,試算表,多重最佳解模型,Solver,呈現之結果,57,成本最小化問題,海軍海上糧食,:,Texfoods,Calration,.,最小化海上糧食總成本,維持維他命,A,，,D,與鐵之基本需求,58,決策變數,(Decision variables),X1 (X2) - The number of two-ounce portions of Texfoods (Calration) product used in a serving.,The Model,Minimize 0.60X1 + 0.50X2,Subject to,20X1 + 50X2,100Vitamin A,25X1 + 25X2,100 Vitamin D,50X1 + 10X2,100 Iron,X1, X2,0,Cost per 2 oz.,% Vitamin A,provided per 2 oz.,% required,成本最小飲食問題,59,10,2,4,5,Feasible Region,Vitamin “D” constraint,Vitamin “A” constraint,The Iron constraint,成本最小飲食問題,圖解法,60,Summary of the optimal solution,Texfood product = 1.5 portions (= 3 ounces),Calration product = 2.5 portions (= 5 ounces),Cost =$ 2.15 per serving.,The minimum requirement for Vitamin D and iron are met with no surplus.,The mixture provides 155% of the requirement for Vitamin A.,成本最小飲食問題,Excel,試算表,61,線性規劃軟體可以求解大型線性模型,大多數線性規劃軟體使用的技巧,單形法,(Simplex Method),(,原理部分見補充,CD3),內點法,(Interior Point Method),整數線性規劃軟體使用的技巧,如切面法,(Cutting Plane Method),分支界限法,(Branch and Bound Point Method),(,原理部分見補充,CD3),LP,程式的代數解法,62,
展开阅读全文