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

1,線性規劃與整數規劃模式LinearandIntegerProgrammingModels,Chapter2,2,線性規劃模型(LinearProgrammingmodel)是在一組線性的限制式(asetoflinearconstraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標函數(objectivefunction)線性規劃模型由下列三個部分組成:一組決策變數(Asetofdecisionvariables)一個特定的目標函數(Anobjectivefunction)一組線性的限制式(Asetofconstraints),2.1線性規劃簡介IntroductiontoLinearProgramming,3,線性規劃簡介IntroductiontoLinearProgramming,線性規劃重要性許多現實問題本身就適用線性規劃模型已存在許多有效的求解技巧已存在許多著名的成功應用實例ManufacturingMarketingFinance(investment)AdvertisingAgriculture,4,線性規劃重要性線性規劃套裝軟體之所產生的結果提供有用的如果則“whatif”的分析資訊,線性規劃簡介IntroductiontoLinearProgramming,5,線性規劃模型之假設AssumptionsforLinearProgramming,參數具有確定性(certainty)目標函數與限制式符合固定規模報酬之假設(constantreturnstoscale)疊加性之假設：決策變數間沒有互動性，即某函數之總價值只能藉由線性加總求得連續性(Continuity)之假設變數值必須再某一個可行範圍內,1單位產品$4，3Hrs生產,500單位產品$4*500=$2000，3*500=1,500Hrs生產,6,典型範例TheGalaxyIndustriesProductionProblem,Galaxy生產兩種玩具模型:宇宙光SpaceRay.射擊手Zapper.資源限制(Resources)1000磅特殊塑膠化合物(specialplastic)每週40小時生產時間(40hrsofproductiontimeperweek),7,市場需求(Marketingrequirement)每週總產量至多700打SpaceRays週產量不能過Zappers350打以上,技術係數(Technologicalinputs)(Table2.2)SpaceRays每打需要2pounds塑膠與3分鐘生產時間Zappers每打需要1pound塑膠與4分鐘生產時間,典型範例TheGalaxyIndustriesProductionProblem,8,生產需求:SpaceRay每打利潤(profit)$8，Zappers每打利潤(profit)$5盡量多生產SpaceRay，剩餘資源再生產Zapper,目前生產計畫:SpaceRays=450dozenZapper=100dozenProfit=$4100perweek,典型範例TheGalaxyIndustriesProductionProblem,9,管理是尋求一個生產排程為了是能增加公司的利潤Managementisseekingaproductionschedulethatwillincreasethecompanysprofit.,10,線性規劃模式可以提供一種深入與聰明之方法來解決此問題Alinearprogrammingmodelcanprovideaninsightandanintelligentsolutiontothisproblem.,11,決策變數(Decisionsvariables):X1=每週生產的SpaceRays打數X2=每週生產的Zappers打數目標函數(ObjectiveFunction):極大化每週總利潤,典型範例線性規劃模式TheGalaxyLinearProgrammingModel,12,Max8X1+5X2(每週總利潤)subjectto2X1+1X21000(塑膠原料,Plastic)3X1+4X22400(生產時間,ProductionTime)X1+X2700(最大產量,Totalproduction)X1-X2350(組合)Xj=0,j=1,2(非負值,Nonnegativity),典型範例線性規劃模式TheGalaxyLinearProgrammingModel,13,2.3線性規劃模式圖形分析GraphicalAnalysisofLinearProgramming,滿足模型全部限制式的所有點集合稱為Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda,可行區域FEASIBLEREGION,14,圖形表示法(graphicalpresentation)所有限制式(alltheconstraints)目標函數(objectivefunction)可行點(threetypesoffeasiblepoints),15,Thenon-negativityconstraints(非負限制式),X2,X1,圖形分析可行區域GraphicalAnalysistheFeasibleRegion,16,1000,500,Feasible,X2,Infeasible,ProductionTime限制式3X1+4X22400,Totalproduction限制式X1+X2700(多餘),500,700,X1,700,圖形分析可行區域GraphicalAnalysistheFeasibleRegion,17,1000,500,Feasible,X2,Infeasible,ProductionTime限制式3X1+4X22400,Totalproduction限制式X1+X2700(多餘),500,700,Mix限制式X1-X2350,Plastic限制式2X1+X21000,X1,700,圖形分析可行區域(p.6768)GraphicalAnalysistheFeasibleRegion,可行點(feasiblepoints)有三種,內部點Interiorpoints.,邊界點Boundarypoints.,端點Extremepoints.,18,以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution,19,尋求最佳解圖解程序(p.71)Thesearchforanoptimalsolution,由任一個profit開始,sayprofit=$1,250.,往利潤增加方向移動increasetheprofit,ifpossible.,持續平行移動到無法增加為止continueuntilitbecomesinfeasible,OptimalProfit=$4360,500,700,1000,500,X2,X1,紅色線段Profit=$1250,20,最佳解(p.69)Summaryoftheoptimalsolution,SpaceRaysX1*=320dozenZappersX2*=360dozenProfitZ*=$4360此最佳解使用了所有的塑膠原料(plastic)與生產時間(productionhours).2X1+1X2=1000(塑膠原料,Plastic)3X1+4X2=2400(生產時間,ProductionTime),Excel試算表,束縛方程式(BindingConstraints):等式被滿足之限制式,21,最佳解(p.7071)Summaryoftheoptimalsolution,總產量(Totalproduction)680打(not700打)SpaceRays產量只超過Zappers40打,非束縛方程式(Non-BindingConstraints)：最佳點不在其等式之限制式寬鬆(Slack)：限制式右邊與左邊的差額，代表資源的剩餘數量,X1+X2=6800RC1=-Z1=-(3.75-2)=-1.75,縮減成本Reducedcost(p.78),29,600,1000,500,800,X2,X1,Max3.75X1+5X2,Max2X1+5X2,目標函數係數之敏感性分析縮減成本(p.79),(1,599.25)Z=2998.25,(0,600)Z=3000,X11,X1=1(由X1=0X1=1)Z=2998.25-3000=-1.75RC1=-1.75,30,問題：若其他參數不變之前提下，若右手值變動一個單位，對於目標函數之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解,(2)右手邊數值之敏感性分析(p.78)SensitivityAnalysisofRight-HandSideValues,31,發現：任意變動束縛函數(BindingConstraints)之右手值，都會改變目前最佳解非束縛函數(Non-BindingConstraints)之右手值，當變動數量少於寬鬆(slack)或剩餘(surplus)量時，都不會改變目前最佳解此結果可以由影子價格(ShadowPrice)來解釋,右手邊數值之敏感性分析SensitivityAnalysisofRight-HandSideValues,32,影子價格ShadowPrices(p.80),若其他輸入參數不變之前提下，限制式的影子價格是當其對應的右手值增加一個單位時，對最佳目標函數值的變動量,33,1000,500,X2,X1,500,2X1+1x2=1000,最佳解由(320,360)(320.8,359.4),2X1+1x2=1001,當右手值增加(例如由10001001)則可行區域擴大,影子價格ShadowPrice圖形表示graphicaldemonstration,Shadowprice=4363.404360.00=3.40,34,可行性範圍RangeofFeasibility(p.81),若其他輸入參數不變之前提下右手值的可行性範圍是影子價格依然不變的右手值可以變動的範圍.在可行性範圍內，,目標函數之改變量Changeinobjectivevalue=影價Shadowprice*右手值變量Changeintherighthandsidevalue,35,塑膠的可行性範圍RangeofFeasibility(p.81),1000,500,X2,X1,500,2X1+1x2=0,j=1,2,3(非負值,Nonnegativity),淨邊際利潤=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0)=-$2.20大水槍不具生產價值X*=(320,360,0)仍為最佳解,43,其他後最佳性變動(p.85)OtherPost-OptimalityChanges,左手係數的變動(Changesintheleft-handsidecoefficients.),44,2.5使用ExcelSolver尋找最佳解與分析結果,點選Galaxy.xls，可見輸入試算表點選工具規劃求解(Solver)，可見下列對話視窗.,45,使用ExcelSolver,點選Galaxy.xls，可見輸入試算表.,$D$7:$D$10=$F$7:$F$10,46,點選Galaxy.xls，可見輸入試算表,$D$7:$D$10=$F$7:$F$10,ByChangingcells,$B$4:$C$4,SetTargetcell,$D$6,使用ExcelSolver,按Solve以求最佳解,47,使用ExcelSolver最佳解,48,使用ExcelSolver最佳解,Solver能提供分析報告與最佳解,49,使用ExcelSolver解答報表AnswerReport,50,使用ExcelSolver敏感性分析報表SensitivityReport,51,不可行性(Infeasibility):一模型中無可行點(p.96)無窮性(Unboundness):一模型中可行解存在，但目標函數沒有限制。目標函數值為無限大(在極大化問題)或無限小(在極小化問題)(p.98)多重解(Alternatesolution):一模型中有一個以上的可行點使目標函數為最佳(p.98),無單一最佳解之模型,52,不可行模型InfeasibleModel,53,不可行模型Solver呈現之結果,Solver呈現無法找到可行解之結果,54,無窮性Unboundedsolution,可行區域,55,無窮性模型Solver呈現之結果,Solver呈現SetCell值無法收斂之結果,56,Solver沒有提醒”多重最佳解”存在的情形有”多重最佳解”的LP模型，則某個變數Xj的目標函數的allowableincreaseorallowabledecrease為0.以Solver尋找多重最佳解的程序如下：(p.99)觀察到某個變數Xj中,多重最佳解模型Solver呈現之結果,Allowableincrease=0,或Allowabledecrease=0.,57,加入一個限制式:Objectivefunction=Currentoptimalvalue.IfAllowableincrease=0,changetheobjectivetoMaximizeXjIfAllowabledecrease=0,changetheobjectivetoMinimizeXjExcel試算表,多重最佳解模型Solver呈現之結果,58,成本最小化問題,海軍海上糧食:Texfoods,Calration.最小化海上糧食總成本維持維他命A，D與鐵之基本需求,59,決策變數(Decisionvariables)X1(X2)-Thenumberoftwo-ounceportionsofTexfoods(Calration)productusedinaserving.TheModelMinimize0.60X1+0.50X2Subjectto