線規(guī)劃模式LinearProgrammingModel.ppt

1,線性規(guī)劃模式 Linear Programming Models,Chapter 3,2,線性規(guī)劃模型(Linear Programming model)是在一組線性的限制式(a set of linear constraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標(biāo)函數(shù)(objective function) 線性規(guī)劃模型由下列三個部分組成: 一組決策變數(shù) (A set of decision variables) 一個特定的目標(biāo)函數(shù)(An objective function) 一組線性的限制式 (A set of constraints),線性規(guī)劃簡介 Introduction to Linear Programming,3,線性規(guī)劃簡介 Introduction to Linear Programming,線性規(guī)劃重要性 許多現(xiàn)實問題本身就適用線性規(guī)劃模型 已存在許多有效的求解技巧 已存在許多著名的成功應(yīng)用實例 Manufacturing Marketing Finance (investment) Advertising Agriculture,4,線性規(guī)劃重要性 線性規(guī)劃套裝軟體之所產(chǎn)生的結(jié)果提供有用的如果則 “what if” 的分析資訊,線性規(guī)劃簡介 Introduction to Linear Programming,5,線性規(guī)劃模型之假設(shè) Assumptions for Linear Programming,參數(shù)具有確定性(certainty) 目標(biāo)函數(shù)與限制式符合固定規(guī)模報酬之假設(shè)(constant returns to scale) 疊加性之假設(shè)：決策變數(shù)間沒有互動性 ，即某函數(shù)之總價值只能藉由線性加總求得 連續(xù)性 (Continuity) 之假設(shè)變數(shù)值必須再某一個可行範(fàn)圍內(nèi),1 單位產(chǎn)品$4， 3Hrs生產(chǎn),500單位產(chǎn)品$4*500=$2000，3*500=1,500Hrs生產(chǎn),6,典型範(fàn)例 The Galaxy Industries Production Problem,Galaxy 生產(chǎn)兩種玩具模型: 宇宙光Space Ray. 射擊手Zapper. 資源限制(Resources) 1000 磅特殊塑膠化合物 (special plastic) 每週40 小時生產(chǎn)時間(40 hrs of production time per week),7,市場需求(Marketing requirement) 每週總產(chǎn)量至多 700 打 Space Rays週產(chǎn)量不能過Zappers 350打以上,技術(shù)係數(shù) (Technological inputs) (Table 2.2) Space Rays 每打需要 2 pounds 塑膠與 3分鐘生產(chǎn)時間 Zappers每打需要 1pound 塑膠與 4分鐘生產(chǎn)時間,典型範(fàn)例 The Galaxy Industries Production Problem,8,生產(chǎn)需求: Space Ray每打利潤(profit) $8，Zappers每打利潤(profit) $5 盡量多生產(chǎn)Space Ray，剩餘資源再生產(chǎn)Zapper,目前生產(chǎn)計畫: Space Rays = 450 dozen Zapper = 100 dozen Profit = $4100 per week,典型範(fàn)例 The Galaxy Industries Production Problem,9,管理是尋求一個生產(chǎn)排程為了是能增加公司的利潤 Management is seeking a production schedule that will increase the companys profit.,10,線性規(guī)劃模式可以提供一種深 入與聰明之方法來解決此問題 A linear programming model can provide an insight and an intelligent solution to this problem.,11,決策變數(shù)(Decisions variables): X1 = 每週生產(chǎn)的 Space Rays 打數(shù) X2 =每週生產(chǎn)的 Zappers 打數(shù) 目標(biāo)函數(shù)(Objective Function): 極大化每週總利潤,典型範(fàn)例線性規(guī)劃模式 The Galaxy Linear Programming Model,12,Max 8X1 + 5X2 (每週總利潤) subject to 2X1 + 1X2 1000 (塑膠原料,Plastic) 3X1 + 4X2 2400 (生產(chǎn)時間,Production Time) X1 + X2 700 (最大產(chǎn)量,Total production) X1 - X2 350 (組合) Xj = 0, j = 1,2 (非負(fù)值,Nonnegativity),典型範(fàn)例線性規(guī)劃模式 The Galaxy Linear Programming Model,13,線性規(guī)劃模式圖形分析 Graphical Analysis of Linear Programming,滿足模型全部限制式的所有點集合稱為 The set of all points that satisfy all the constraints of the model is called a,可行區(qū)域 FEASIBLE REGION,14,圖形表示法(graphical presentation) 所有限制式(all the constraints) 目標(biāo)函數(shù)(objective function) 可行點(three types of feasible points),15,The non-negativity constraints (非負(fù)限制式),X2,X1,圖形分析 可行區(qū)域 Graphical Analysis the Feasible Region,16,1000,500,Feasible,X2,Infeasible,Production Time 限制式 3X1+4X2 2400,Total production 限制式 X1+X2 700 (多餘),500,700,X1,700,圖形分析 可行區(qū)域 Graphical Analysis the Feasible Region,17,1000,500,Feasible,X2,Infeasible,Production Time 限制式 3X1+4X2 2400,Total production 限制式 X1+X2 700 (多餘),500,700,Mix限制式 X1-X2 350,Plastic限制式 2X1+X2 1000,X1,700,圖形分析 可行區(qū)域 (p. 6768) Graphical Analysis the Feasible Region,可行點(feasible points)有三種,內(nèi)部點Interior points.,邊界點 Boundary points.,端點Extreme points.,18,以圖形求解是為了尋求最佳解Solving Graphically for an Optimal Solution,19,尋求最佳解圖解程序 (p.71) The search for an optimal solution,由任一個 profit開始, say profit = $1,250.,往利潤增加方向移動 increase the profit, if possible.,持續(xù)平行移動到無法增加為止 continue until it becomes infeasible,Optimal Profit =$4360,500,700,1000,500,X2,X1,紅色線段 Profit =$1250,20,最佳解 (p.69) Summary of the optimal solution,Space Rays X1 * = 320 dozen Zappers X2 * = 360 dozen Profit Z * = $4360 此最佳解使用了所有的塑膠原料(plastic)與生產(chǎn)時間 (production hours). 2X1 + 1X2 = 1000 (塑膠原料,Plastic) 3X1 + 4X2 = 2400 (生產(chǎn)時間,Production Time),Excel試算表,束縛方程式(Binding Constraints):等式被滿足之限制式,21,最佳解 (p.7071) Summary of the optimal solution,總產(chǎn)量(Total production) 680 打 (not 700打) Space Rays 產(chǎn)量只超過 Zappers 40打,非束縛方程式(Non-Binding Constraints)：最佳點不在其等式之限制式 寬鬆(Slack)：限制式右邊與左邊的差額，代表資源的剩餘數(shù)量,X1 + X2 = 680 700 (總產(chǎn)量) X1 - X2 = -40 350 (產(chǎn)品組合),總產(chǎn)量有700-680=20的寬鬆 產(chǎn)品組合有350-(-40) = 390的寬鬆,22,若一個線性規(guī)劃問題有一組最佳解，此最佳解一定發(fā)生在”端點”上 (端點最佳解之候選人,True/False) 兩個束縛方程式的交點形成一個”端點”或”角點”,端點與最佳解 (p.72) Extreme points and optimal solutions,端點：可行區(qū)域的角點,2X1+ X2 = 1000 X1-X2 = 350 之解,(450,100),(320,360),2X1+ X2 = 1000 3X1+4X2 = 2400 之解,(0,600),3X1+4X2 = 2400 X1 = 0 之解,23,若多重最佳解存在，則目標(biāo)函數(shù)必定平行其中一個限制式,多重最佳解 Multiple optimal solutions,多重最佳解之任何加權(quán)平均值亦為一組最佳解,X1=(350,0) 最佳解1,X2=(0,600) 最佳解2,X=X1+(1-)X2 , 0,1 亦為最佳解,目標(biāo)函數(shù) Z,24,最佳解敏感性分析之角色 The Role of Sensitivity Analysis of the Optimal Solution (p.75),輸入?yún)?shù)之變動對於最佳解之敏感度為何? 從事敏感性分析之原因： 輸入?yún)?shù)可能只是估計值或最佳估計值 模型建立在一個動態(tài)環(huán)境，因此有些參數(shù)可能變動 “如果會”(“What-if”)分析可以提供經(jīng)濟地與作業(yè)地資訊.,25,最佳範(fàn)圍(Range of Optimality) (p.76) 當(dāng)其他因素保持不變時，在不改變最佳解之情況下，目標(biāo)函數(shù)某係數(shù)可以變動多少? (p.77)最佳解將不會改變，若 目標(biāo)函數(shù)係數(shù)仍在最佳範(fàn)圍內(nèi) 不改變其他輸入?yún)?shù) 目標(biāo)函數(shù)某係數(shù)乘上一個非零正數(shù)，則目標(biāo)函數(shù)會改變.,(1) 目標(biāo)函數(shù)係數(shù)之敏感性分析Sensitivity Analysis of Objective Function Coefficients.,26,600,1000,500,800,X2,X1,Max 8X1 + 5X2,Max 4X1 + 5X2,Max 3.75X1 + 5X2,Max 2X1 + 5X2,目標(biāo)函數(shù)係數(shù)之敏感性分析Sensitivity Analysis of Objective Function Coefficients.,最佳解仍為(320,360),(320,360),C1係數(shù)=2，最佳解為(0,600) 而(320,360)不再是最佳解,(0,600),減少C1係數(shù)由83.75,27,600,1000,400,600,800,X2,X1,Max8X1 + 5X2,Max 3.75X1 + 5X2,Max 10 X1 + 5X2,C1係數(shù)的最佳範(fàn)圍: 3.75, 10,目標(biāo)函數(shù)係數(shù)之敏感性分析Sensitivity Analysis of Objective Function Coefficients.,增加C1係數(shù)，由810 最佳解仍包含(320,360),(320,360),同理，C2係數(shù)的最佳範(fàn)圍: 4, 10.67 (Can you find it ?),28,一個變數(shù)Xj =0的縮減成本RCj為目標(biāo)函數(shù)係數(shù)需要增加量的負(fù)值(-DZj) ，使得最佳解中該變數(shù)為正數(shù)(Xj 0) 縮減成本RCj為此變數(shù)Xj每增加一單位(DXj=1) ，目標(biāo)函數(shù)會改變的值,C1=2 X*=(0,600) X1=0 C1=3.75 X*=(320,360) X1=3200 RC1 =-Z1=-(3.75-2)=-1.75,縮減成本 Reduced cost (p.78),29,600,1000,500,800,X2,X1,Max 3.75X1 + 5X2,Max 2X1 + 5X2,目標(biāo)函數(shù)係數(shù)之敏感性分析 縮減成本 (p.79),(1,599.25) Z=2998.25,(0,600) Z=3000,X1 1,X1=1 (由X1=0X1=1) Z=2998.25-3000 = -1.75 RC1 =-1.75,30,問題： 若其他參數(shù)不變之前提下，若右手值變動一個單位，對於目標(biāo)函數(shù)之最佳解有何影響? 多少變動單位(增加或減少)，可以保持目前最佳解,(2) 右手邊數(shù)值 之敏感性分析 (p.78) Sensitivity Analysis of Right-Hand Side Values,31,發(fā)現(xiàn)： 任意變動束縛函數(shù)(Binding Constraints)之右手值，都會改變目前最佳解 非束縛函數(shù)(Non-Binding Constraints)之右手值，當(dāng)變動數(shù)量少於寬鬆(slack)或剩餘(surplus)量時，都不會改變目前最佳解 此結(jié)果可以由影子價格(Shadow Price)來解釋,右手邊數(shù)值 之敏感性分析 Sensitivity Analysis of Right-Hand Side Values,32,影子價格 Shadow Prices (p.80),若其他輸入?yún)?shù)不變之前提下，限制式的影子價格 是當(dāng)其對應(yīng)的右手值增加一個單位時，對最佳目標(biāo)函數(shù)值的變動量,33,1000,500,X2,X1,500,2X1 + 1x2 =1000,最佳解由(320,360)(320.8,359.4),2X1 + 1x2 =1001,當(dāng)右手值增加(例如由10001001)則可行區(qū)域擴大,影子價格Shadow Price 圖形表示 graphical demonstration,Shadow price = 4363.40 4360.00 = 3.40,34,可行性範(fàn)圍 Range of Feasibility (p.81),若其他輸入?yún)?shù)不變之前提下 右手值的可行性範(fàn)圍是影子價格依然不變的 右手值可以變動的範(fàn)圍. 在可行性範(fàn)圍內(nèi)，,目標(biāo)函數(shù)之改變量Change in objective value = 影價Shadow price*右手值變量Change in the right hand side value,35,塑膠的可行性範(fàn)圍 Range of Feasibility (p.81),1000,500,X2,X1,500,2X1 + 1x2 =1000,塑膠原料的數(shù)量可以增加到一個新限制式成為Binding為止,此處為不可行解,Production time 限制式,Total Production限制式 X1 + X2 700,36,塑膠的可行性範(fàn)圍 Range of Feasibility,1000,500,X2,X1,600,Production time 限制式 3X1+4X2 2400,請注意看： 當(dāng)塑膠數(shù)量增加時最佳解的變化,Total Production 限制式 X1+X2 700,塑膠的可行性範(fàn)圍 上限 = 2X1 + 1X2 =2*(400)+300=1100,X1+ X2 = 700 3X1+4X2 = 2400 之解 X*=(400,300)為最佳解,2X1 + 1x2 1000,37,塑膠的可行性範(fàn)圍 Range of Feasibility,1000,500,X2,X1,600,Plastic 限制式 2X1 + 1X2 1000,請注意看： 當(dāng)塑膠數(shù)量減少時最佳解的變化,3X1+ 4X2 = 2400 X1 = 0 之解 X*=(0,600)為最佳解,塑膠的可行性範(fàn)圍 下限 =2X1 + 1X2 = 2*(0)+1*600=600,Production time 限制式 3X1+4X2 2400,38,已投入成本(Sunk costs): 未被包括在目標(biāo)函數(shù)係數(shù)之計算當(dāng)中的資源成本- Shadow Price為該資源額外一單位的價值 淨(jìng)利潤可以將已投入成本$3800由目標(biāo)函數(shù)值中扣除,影子價格的正確解釋 The correct interpretation of shadow prices (p.83),1000磅塑膠每磅$3 Total Cost = $3000 Production Time $20/hr Total Cost =$20*40=$800 不管一週實際使用多少塑膠與Production Time，$3000+$800=$3800都必須支付，故為已投入成本,39,已包括成本(Included costs):被包括在目標(biāo)函數(shù)係數(shù)之計算當(dāng)中的資源成本Shadow Price為高於該資源之現(xiàn)有單位價值之額外的價值 見p.84表格2.5說明,影子價格的正確解釋 The correct interpretation of shadow prices (p.83),塑膠每磅$3 塑膠影價每磅=$3.4 管理者願意為額外塑膠磅數(shù)多支付$6.8(已包括成本),Production Time $0.33/min (or $20/hr) ， Production Time影價每分鐘=$0.4 管理者願意為額外Production Time多支付 $0.73,40,(3) 其他後最佳性變動 (p.84) Other Post - Optimality Changes,加入一個新限制式(Addition of a constraint) 刪除一個限制式(Deletion of a constraint),決定最佳解是否滿足此限制式 Yes, the solution is still optimal No, re-solve the problem (the new objective function is worse than the original one),決定刪除的限制式是否為束縛限制式 Yes, re-solve the problem (the new objective function is better than the original one) No, the solution is still optimal,41,其他後最佳性變動 (p.84) Other Post - Optimality Changes,刪除變數(shù) (Deletion of a variable) 增加變數(shù) (Addition of a variable)考慮淨(jìng)邊際利潤(Net Marginal Profit),決定被刪除變數(shù)在最佳解中是否為0 Yes, the solution is still optimal No, re-solve the problem (the new objective function is worse than the original one),42,其他後最佳性變動 (p.85) Other Post - Optimality Changes,【範(fàn)例】 X3=新產(chǎn)品大水槍產(chǎn)量 每一個大水槍需3lb塑膠與5min 生產(chǎn)時間 每打利潤$10,Max 8X1 + 5X2+ 10X3 (每週總利潤) subject to 2X1 + 1X2 + 3X3 1000 (塑膠原料,Plastic ,Shadow Price = $3.4) 3X1 + 4X2 + 5X3 2400 (生產(chǎn)時間,Production Time, SP = $0.4) X1 + X2 +X3 700 (最大產(chǎn)量,Total production, SP = $0) X1 - X2 350 (組合, SP = $0) Xj = 0, j = 1,2,3 (非負(fù)值,Nonnegativity),淨(jìng)邊際利潤=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0) = -$2.2 0 大水槍不具生產(chǎn)價值 X*=(320,360,0) 仍為最佳解,43,其他後最佳性變動 (p.85) Other Post - Optimality Changes,左手係數(shù)的變動(Changes in the left - hand side coefficients.),44,使用Excel Solver 尋找最佳解與分析結(jié)果,點選Galaxy.xls，可見輸入試算表 點選工具規(guī)劃求解(Solver)，可見下列對話視窗.,45,使用 Excel Solver,點選Galaxy.xls，可見輸入試算表 .,$D$7:$D$10=$F$7:$F$10,46,點選Galaxy.xls，可見輸入試算表,$D$7:$D$10=$F$7:$F$10,By Changing cells,$B$4:$C$4,Set Target cell,$D$6,使用 Excel Solver,按Solve以求最佳解,47,使用Excel Solver 最佳解,48,使用Excel Solver 最佳解,Solver 能提供分析報告與最佳解,49,使用Excel