线性规划与整数规划模式知识讲座(ppt 62页)

線性規劃與整數規劃模式 LinearandIntegerProgrammingModelsChapter2 線性規劃模型(LinearProgrammingmodel)是在一組「線性」的限制式(asetoflinearconstraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標函數(objectivefunction) 線性規劃模型由下列三個部分組成: 一組決策變數(Asetofdecisionvariables) 一個特定的目標函數(Anobjectivefunction) 一組「線性」的限制式(Asetofconstraints)2.1線性規劃簡介IntroductiontoLinearProgramming線性規劃簡介IntroductiontoLinearProgramming 線性規劃重要性 許多現實問題本身就適用線性規劃模型 已存在許多有效的求解技巧 已存在許多著名的成功應用實例 Manufacturing Marketing Finance(investment) Advertising Agriculture 線性規劃重要性 線性規劃套裝軟體之所產生的結果提供有用的「如果…則」“what…if”的分析資訊線性規劃簡介IntroductiontoLinearProgramming線性規劃模型之假設AssumptionsforLinearProgramming 參數具有「確定性」(certainty) 目標函數與限制式符合「固定規模報酬」之假設(constantreturnstoscale) 「疊加性」之假設：決策變數間沒有互動性，即某函數之總價值只能藉由線性加總求得 「連續性」(Continuity)之假設變數值必須再某一個可行範圍內1單位產品$4，3Hrs生產500單位產品$4*500=$2000，3*500=1,500Hrs生產典型範例TheGalaxyIndustriesProductionProblem Galaxy生產兩種玩具模型: 宇宙光SpaceRay. 射擊手Zapper. 資源限制(Resources) 1000磅特殊塑膠化合物(specialplastic) 每週40小時生產時間(40hrsofproductiontimeperweek) 市場需求(Marketingrequirement) 每週總產量至多700打 SpaceRays週產量不能過Zappers350打以上 技術係數(Technologicalinputs)(Table2.2) SpaceRays每打需要2pounds塑膠與3分鐘生產時間 Zappers每打需要1pound塑膠與4分鐘生產時間典型範例TheGalaxyIndustriesProductionProblem 生產需求: SpaceRay每打利潤(profit)$8，Zappers每打利潤(profit)$5 盡量多生產SpaceRay，剩餘資源再生產Zapper 目前生產計畫: SpaceRays=450dozen Zapper =100dozen Profit =$4100perweek典型範例TheGalaxyIndustriesProductionProblem 管理是尋求一個生產排程為了是能增加公司的利潤Managementisseekingaproductionschedulethatwillincreasethecompany’sprofit. 線性規劃模式可以提供一種深入與聰明之方法來解決此問題Alinearprogrammingmodel canprovideaninsightandan intelligentsolutiontothisproblem. 決策變數(Decisionsvariables): X1=每週生產的SpaceRays打數 X2=每週生產的Zappers打數 目標函數(ObjectiveFunction): 極大化每週總利潤 典型範例線性規劃模式TheGalaxyLinearProgrammingModel Max8X1+5X2 (每週總利潤) subjectto 2X1+1X2£1000(塑膠原料,Plastic) 3X1+4X2£2400(生產時間,ProductionTime) X1+X2£700(最大產量,Totalproduction) X1-X2£350(組合) Xj>=0,j=1,2(非負值,Nonnegativity)典型範例線性規劃模式TheGalaxyLinearProgrammingModel2.3 線性規劃模式圖形分析GraphicalAnalysisofLinearProgramming滿足模型全部限制式的所有點集合稱為Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda 可行區域FEASIBLEREGION圖形 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示法(graphicalpresentation)所有限制式(alltheconstraints)目標函數(objectivefunction)可行點(threetypesoffeasiblepoints)Thenon-negativityconstraints(非負限制式)X2X1圖形分析–可行區域GraphicalAnalysis–theFeasibleRegion1000500FeasibleX2InfeasibleProductionTime限制式3X1+4X2£2400Totalproduction限制式X1+X2£700(多餘)500700X1700圖形分析–可行區域GraphicalAnalysis–theFeasibleRegion1000500FeasibleX2InfeasibleProductionTime限制式3X1+4X2£2400Totalproduction限制式X1+X2£700(多餘)500700Mix限制式X1-X2£350Plastic限制式2X1+X2£1000X1700圖形分析–可行區域(p.67~68)GraphicalAnalysis–theFeasibleRegion 可行點(feasiblepoints)有三種內部點Interiorpoints.邊界點Boundarypoints.端點Extremepoints.以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution尋求最佳解圖解程序(p.71)Thesearchforanoptimalsolution由任一個profit開始,sayprofit=$1,250.往利潤增加方向移動increasetheprofit,ifpossible...持續平行移動到無法增加為止continueuntilitbecomesinfeasibleOptimalProfit=$43605007001000500X2X1紅色線段Profit=$1250最佳解(p.69)SummaryoftheoptimalsolutionSpaceRaysX1*=320dozenZappersX2*=360dozenProfit Z*=$4360 此最佳解使用了所有的塑膠原料(plastic)與生產時間(productionhours).2X1+1X2=1000(塑膠原料,Plastic) 3X1+4X2=2400(生產時間,ProductionTime)Excel試算表束縛方程式(BindingConstraints):等式被滿足之限制式最佳解(p.70~71)Summaryoftheoptimalsolution 總產量(Totalproduction)680打(not700打) SpaceRays產量只超過Zappers40打 非束縛方程式(Non-BindingConstraints)：最佳點不在其等式之限制式寬鬆(Slack)：限制式右邊與左邊的差額，代表資源的剩餘數量X1+X2=680<700(總產量)X1-X2=-40<350(產品組合)總產量有700-680=20的寬鬆產品組合有350-(-40)=390的寬鬆 若一個線性規劃問題有一組最佳解，此最佳解一定發生在”端點”上(端點最佳解之候選人,True/False) 兩個束縛方程式的交點形成一個”端點”或”角點”端點與最佳解(p.72)Extremepointsandoptimalsolutions端點：可行區域的角點2X1+X2=1000X1-X2=350之解(450,100)(320,360)2X1+X2=10003X1+4X2=2400之解(0,600)3X1+4X2=2400X1=0之解 若多重最佳解存在，則目標函數必定平行其中一個限制式多重最佳解Multipleoptimalsolutions 多重最佳解之任何加權平均值亦為一組最佳解X1=(350,0)最佳解1X2=(0,600)最佳解2X=αX1+(1-α)X2,α∈[0,1]亦為最佳解目標函數Z2.4最佳解敏感性分析之角色TheRoleofSensitivityAnalysis oftheOptimalSolution(p.75) 輸入參數之變動對於最佳解之敏感度為何? 從事敏感性分析之原因： 輸入參數可能只是估計值或最佳估計值 模型建立在一個動態環境，因此有些參數可能變動 “如果..會”(“What-if”)分析可以提供經濟地與作業地資訊. 最佳範圍(RangeofOptimality)(p.76) 當其他因素保持不變時，在不改變最佳解之情況下，目標函數某係數可以變動多少? (p.77)最佳解將不會改變，若 目標函數係數仍在最佳範圍內 不改變其他輸入參數 目標函數某係數乘上一個非零正數，則目標函數會改變.(1)目標函數係數之敏感性分析SensitivityAnalysisofObjectiveFunctionCoefficients.6001000500800X2X1Max8X1+5X2Max4X1+5X2Max3.75X1+5X2Max2X1+5X2目標函數係數之敏感性分析SensitivityAnalysisofObjectiveFunctionCoefficients.最佳解仍為(320,360)(320,360)C1係數=2，最佳解為(0,600)而(320,360)不再是最佳解(0,600)減少C1係數由8→3.756001000400600800X2X1Max8X1+5X2Max3.75X1+5X2Max10X1+5X2C1係數的最佳範圍:[3.75,10]目標函數係數之敏感性分析SensitivityAnalysisofObjectiveFunctionCoefficients.增加C1係數，由8→10最佳解仍包含(320,360)(320,360)同理，C2係數的最佳範圍:[4,10.67](Canyoufindit?) 一個變數Xj=0的縮減成本RCj為目標函數係數需要增加量的負值(-DZj)，使得最佳解中該變數為正數(Xj>0) 縮減成本RCj為此變數Xj每增加一單位(DXj=1)，目標函數會改變的值C1=2X*=(0,600)X1=0→C1=3.75X*=(320,360)X1=320>0RC1=-∆Z1=-(3.75-2)=-1.75縮減成本Reducedcost(p.78)6001000500800X2X1Max3.75X1+5X2Max2X1+5X2目標函數係數之敏感性分析縮減成本(p.79)(1,599.25)Z=2998.25(0,600)Z=3000X1≥1∆X1=1(由X1=0→X1=1)∆Z=2998.25-3000=-1.75RC1=-1.75 問題： 若其他參數不變之前提下，若右手值變動一個單位，對於目標函數之最佳解有何影響? 多少變動單位(增加或減少)，可以保持目前最佳解(2)右手邊數值之敏感性分析(p.78)SensitivityAnalysisofRight-HandSideValues 發現： 任意變動束縛函數(BindingConstraints)之右手值，都會改變目前最佳解 非束縛函數(Non-BindingConstraints)之右手值，當變動數量少於寬鬆(slack)或剩餘(surplus)量時，都不會改變目前最佳解 此結果可以由影子價格(ShadowPrice)來解釋右手邊數值之敏感性分析SensitivityAnalysisofRight-HandSideValues影子價格ShadowPrices(p.80) 若其他輸入參數不變之前提下，限制式的影子價格是當其對應的右手值增加一個單位時，對最佳目標函數值的變動量1000500X2X15002X1+1x2<=1000最佳解由(320,360)→(320.8,359.4)2X1+1x2<=1001當右手值增加(例如由1000→1001)則可行區域擴大影子價格ShadowPrice–圖形表示graphicaldemonstrationShadowprice=4363.40–4360.00=3.40可行性範圍RangeofFeasibility(p.81) 若其他輸入參數不變之前提下 右手值的可行性範圍是影子價格依然不變的右手值可以變動的範圍. 在可行性範圍內，目標函數之改變量Changeinobjectivevalue=[影價Shadowprice]*[右手值變量Changeintherighthandsidevalue]塑膠的可行性範圍RangeofFeasibility(p.81)1000500X2X15002X1+1x2<=1000塑膠原料的數量可以增加到一個新限制式成為Binding為止此處為不可行解Productiontime限制式TotalProduction限制式X1+X2£700塑膠的可行性範圍RangeofFeasibility1000500X2X1600Productiontime限制式3X1+4X2≤2400請注意看：當塑膠數量增加時最佳解的變化TotalProduction限制式X1+X2≤700塑膠的可行性範圍上限=2X1+1X2=2*(400)+300=1100X1+X2=7003X1+4X2=2400之解X*=(400,300)為最佳解2X1+1x2£1000塑膠的可行性範圍RangeofFeasibility1000500X2X1600Plastic限制式2X1+1X2£1000請注意看：當塑膠數量減少時最佳解的變化3X1+4X2=2400X1=0之解X*=(0,600)為最佳解塑膠的可行性範圍下限=2X1+1X2=2*(0)+1*600=600Productiontime限制式3X1+4X2≤2400 已投入成本(Sunkcosts):未被包括在目標函數係數之計算當中的資源成本-ShadowPrice為該資源額外一單位的價值 淨利潤可以將已投入成本$3800由目標函數值中扣除 影子價格的正確解釋Thecorrectinterpretationofshadowprices(p.83)1000磅塑膠每磅$3→TotalCost=$3000ProductionTime$20/hr→TotalCost=$20*40=$800不管一週實際使用多少塑膠與ProductionTime，$3000+$800=$3800都必須支付，故為已投入成本 已包括成本(Includedcosts):被包括在目標函數係數之計算當中的資源成本─ShadowPrice為高於該資源之現有單位價值之額外的價值 見p.84表格2.5說明影子價格的正確解釋Thecorrectinterpretationofshadowprices(p.83)塑膠每磅$3→塑膠影價每磅=$3.4→管理者願意為額外塑膠磅數多支付$6.8(已包括成本)ProductionTime$0.33/min(or$20/hr)，ProductionTime影價每分鐘=$0.4→管理者願意為額外ProductionTime多支付$0.73其他後最佳性變動(p.84)OtherPost-OptimalityChanges 加入一個新限制式(Additionofaconstraint) 刪除一個限制式(Deletionofaconstraint)決定最佳解是否滿足此限制式Yes,thesolutionisstilloptimalNo,re-solvetheproblem(thenewobjectivefunctionisworsethantheoriginalone)決定刪除的限制式是否為束縛限制式 Yes,re-solvetheproblem(thenewobjectivefunctionisbetterthantheoriginalone) No,thesolutionisstilloptimal其他後最佳性變動(p.84)OtherPost-OptimalityChanges 刪除變數(Deletionofavariable) 增加變數(Additionofavariable)─考慮淨邊際利潤(NetMarginalProfit)決定被刪除變數在最佳解中是否為0Yes,thesolutionisstilloptimalNo,re-solvetheproblem(thenewobjectivefunctionisworsethantheoriginalone)其他後最佳性變動(p.85)OtherPost-OptimalityChanges【範例】X3=新產品大水槍產量每一個大水槍需3lb塑膠與5min生產時間每打利潤$10Max8X1+5X2+10X3 (每週總利潤)subjectto 2X1+1X2+3X3≤1000(塑膠原料,Plastic,ShadowPrice=$3.4) 3X1+4X2+5X3≤2400(生產時間,ProductionTime,SP=$0.4) X1+X2+X3≤700(最大產量,Totalproduction,SP=$0) X1-X2≤350(組合,SP=$0) Xj>=0,j=1,2,3(非負值,Nonnegativity)淨邊際利潤=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0))=-$2.2<0大水槍不具生產價值X*=(320,360,0)仍為最佳解其他後最佳性變動(p.85)OtherPost-OptimalityChanges 左手係數的變動(Changesintheleft-handsidecoefficients.)2.5使用ExcelSolver尋找最佳解與分析結果 點選Galaxy.xls，可見輸入試算表 點選工具\規劃求解(Solver)，可見下列對話視窗.使用ExcelSolver 點選Galaxy.xls，可見輸入試算表.$D$7:$D$10<=$F$7:$F$10 點選Galaxy.xls，可見輸入試算表$D$7:$D$10<=$F$7:$F$10ByChangingcells$B$4:$C$4SetTargetcell$D$6使用ExcelSolver按Solve以求最佳解使用ExcelSolver–最佳解使用ExcelSolver–最佳解Solver能提供分析報告與最佳解使用ExcelSolver–解答報表AnswerReport使用ExcelSolver–敏感性分析報表SensitivityReport 不可行性(Infeasibility):一模型中無可行點(p.96) 無窮性(Unboundness):一模型中可行解存在，但目標函數沒有限制。目標函數值為無限大(在極大化問題)或無限小(在極小化問題)(p.98) 多重解(Alternatesolution):一模型中有一個以上的可行點使目標函數為最佳(p.98)無單一最佳解之模型不可行模型InfeasibleModel不可行模型Solver呈現之結果Solver呈現無法找到可行解之結果無窮性Unboundedsolution可行區域無窮性模型Solver呈現之結果Solver呈現SetCell值無法收斂之結果 Solver沒有提醒”多重最佳解”存在的情形 有”多重最佳解”的LP模型，則某個變數Xj的目標函數的allowableincreaseorallowabledecrease為0. 以Solver尋找多重最佳解的程序如下：(p.99) 觀察到某個變數Xj中 多重最佳解模型Solver呈現之結果Allowableincrease=0,或Allowabledecrease=0. 加入一個限制式: Objectivefunction=Currentoptimalvalue. IfAllowableincrease=0,changetheobjectivetoMaximizeXj IfAllowabledecrease=0,changetheobjectivetoMinimizeXj Excel試算表多重最佳解模型Solver呈現之結果成本最小化問題 海軍海上糧食:Texfoods,Calration. 最小化海上糧食總成本 維持維他命A，D與鐵之基本需求 決策變數(Decisionvariables) X1(X2)--Thenumberoftwo-ounceportionsof Texfoods(Calration)productusedinaserving. TheModelMinimize0.60X1+0.50X2Subjectto 20X1+50X2³100 VitaminA 25X1+25X2³100VitaminD 50X1+10X2³100Iron X1,X2³0Costper2oz.%VitaminAprovidedper2oz.%required成本最小飲食問題 10245FeasibleRegionVitamin“D”constraintVitamin“A”constraintTheIronconstraint成本最小飲食問題–圖解法 Summaryoftheoptimalsolution Texfoodproduct=1.5portions(=3ounces) Calrationproduct=2.5portions(=5ounces) Cost=$2.15perserving. TheminimumrequirementforVitaminDandironaremetwithnosurplus. Themixtureprovides155%oftherequirementforVitaminA.成本最小飲食問題Excel試算表 線性規劃軟體可以求解大型線性模型 大多數線性規劃軟體使用的技巧 單形法(SimplexMethod)(原理部分見補充CD3) 內點法(InteriorPointMethod) 整數線性規劃軟體使用的技巧 如切面法(CuttingPlaneMethod) 分支界限法(BranchandBoundPointMethod)(原理部分見補充CD3)LP程式的代數解法