线性规划模式Linear-Programming-Models课件

線性規劃模式

LinearProgrammingModelsChapter31線性規劃模式

LinearProgrammingMode線性規劃模型(LinearProgrammingmodel)是在一組「線性」的限制式(asetoflinearconstraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標函數(objective

function)

線性規劃模型由下列三個部分組成:一組決策變數(Asetofdecisionvariables)一個特定的目標函數(Anobjectivefunction)一組「線性」的限制式(Asetofconstraints)

線性規劃簡介

IntroductiontoLinearProgramming2線性規劃模型(LinearProgrammingmode線性規劃簡介

IntroductiontoLinearProgramming線性規劃重要性許多現實問題本身就適用線性規劃模型

已存在許多有效的求解技巧已存在許多著名的成功應用實例ManufacturingMarketingFinance(investment)AdvertisingAgriculture3線性規劃簡介

IntroductiontoLinear線性規劃重要性線性規劃套裝軟體之所產生的結果提供有用的「如果…則」“what…

if”的分析資訊線性規劃簡介

IntroductiontoLinearProgramming4線性規劃重要性線性規劃簡介

Introductionto線性規劃模型之假設

AssumptionsforLinearProgramming參數具有「確定性」(certainty)目標函數與限制式符合「固定規模報酬」之假設(constantreturnstoscale)「疊加性」之假設：決策變數間沒有互動性

，即某函數之總價值只能藉由線性加總求得「連續性」(Continuity)之假設變數值必須再某一個可行範圍內1單位產品$4，3Hrs生產500單位產品$4*500=$2000，3*500=1,500Hrs生產5線性規劃模型之假設

AssumptionsforLin典型範例

TheGalaxyIndustriesProductionProblem

Galaxy生產兩種玩具模型:宇宙光SpaceRay.射擊手Zapper.

資源限制(Resources)1000磅特殊塑膠化合物(specialplastic)每週40小時生產時間(40hrsofproductiontimeperweek)6典型範例

TheGalaxyIndustriesPr市場需求(Marketingrequirement)每週總產量至多700打SpaceRays週產量不能過Zappers350打以上技術係數(Technologicalinputs)(Table2.2)

SpaceRays每打需要2pounds塑膠與3分鐘生產時間Zappers每打需要1pound塑膠與4分鐘生產時間典型範例

TheGalaxyIndustriesProductionProblem7市場需求(Marketingrequirement)技術係

生產需求:

SpaceRay每打利潤(profit)$8，Zappers每打利潤(profit)$5盡量多生產SpaceRay，剩餘資源再生產Zapper目前生產計畫:

SpaceRays=450dozen Zapper =100dozen Profit =$4100perweek典型範例

TheGalaxyIndustriesProductionProblem8(450)+5(100)8生產需求:目前生產計畫:典型範例

TheGalaxy 管理是尋求一個生產排程為了是能增加公司的利潤Managementisseekingaproductionschedulethatwillincreasethecompany’sprofit.9 管理是尋求一個生產排程為了是能增加公司的利潤9

線性規劃模式可以提供一種深入與聰明之方法來解決此問題Alinearprogrammingmodel canprovideaninsightandan intelligentsolutiontothisproblem.10 10決策變數(Decisionsvariables):X1=每週生產的SpaceRays打數X2=每週生產的Zappers打數目標函數(ObjectiveFunction):

極大化每週總利潤

典型範例線性規劃模式

TheGalaxyLinearProgrammingModel11決策變數(Decisionsvariables):典型範例

Max8X1+5X2 (每週總利潤) subjectto 2X1+1X2

£1000(塑膠原料,Plastic) 3X1+4X2

£2400(生產時間,ProductionTime) X1+X2

£700(最大產量,Totalproduction) X1-X2

£350(組合) Xj>=0,j=1,2(非負值,Nonnegativity)典型範例線性規劃模式

TheGalaxyLinearProgrammingModel12 Max8X1+5X2 (每週總利潤)典型範例線線性規劃模式圖形分析

GraphicalAnalysisofLinearProgramming滿足模型全部限制式的所有點集合稱為

Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda

可行區域FEASIBLEREGION13線性規劃模式圖形分析

Graphic

圖形表示法(graphicalpresentation)所有限制式(alltheconstraints)

目標函數(objectivefunction)可行點(threetypesoffeasiblepoints)14圖形表示法(graphicalpresentationThenon-negativityconstraints(非負限制式)X2X1圖形分析–可行區域

GraphicalAnalysis–theFeasibleRegion15Thenon-negativityconstraints1000500FeasibleX2InfeasibleProduction

Time限制式3X1+4X2£

2400

Totalproduction限制式X1+X2£

700(多餘)500700Plastic限制式2X1+X2£1000X1700圖形分析–可行區域

GraphicalAnalysis–theFeasibleRegion161000500FeasibleX2InfeasiblePro1000500FeasibleX2InfeasibleProduction

Time

限制式3X1+4X2£2400

Totalproduction

限制式X1+X2£700(多餘)500700Mix限制式X1-X2£

350Plastic限制式2X1+X2£1000X1700圖形分析–可行區域(p.67~68)

GraphicalAnalysis–theFeasibleRegion可行點(feasiblepoints)有三種內部點Interiorpoints.邊界點Boundarypoints.端點Extremepoints.171000500FeasibleX2InfeasiblePro以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution18以圖形求解是為了尋求最佳解SolvingGraphical尋求最佳解圖解程序(p.71)

Thesearchforanoptimalsolution由任一個profit開始,sayprofit=$1,250.往利潤增加方向移動increasetheprofit,ifpossible...持續平行移動到無法增加為止

continueuntilitbecomesinfeasibleOptimalProfit=$43605007001000500X2X1紅色線段Profit=$125019尋求最佳解圖解程序(p.71)

Thesearchf最佳解(p.69)

SummaryoftheoptimalsolutionSpaceRaysX1*=320dozenZappersX2*=360dozenProfit Z

*=$4360此最佳解使用了所有的塑膠原料(plastic)與生產時間(productionhours).

2X1+1X2=1000(塑膠原料,Plastic) 3X1+4X2=2400(生產時間,ProductionTime)Excel試算表束縛方程式(BindingConstraints):等式被滿足之限制式20最佳解(p.69)

Summaryoftheop最佳解(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的寬鬆21最佳解(p.70~71)

Summaryofthe若一個線性規劃問題有一組最佳解，此最佳解一定發生在”端點”上(端點最佳解之候選人,True/False)兩個束縛方程式的交點形成一個”端點”或”角點”端點與最佳解(p.72)

Extremepointsandoptimalsolutions端點：可行區域的角點2X1+X2=1000

X1-X2=350之解(450,100)(320,360)2X1+X2=10003X1+4X2=2400之解(0,600)3X1+4X2=2400

X1=0之解22若一個線性規劃問題有一組最佳解，此最佳解一定發生在”端點”上若多重最佳解存在，則目標函數必定平行其中一個限制式多重最佳解

Multipleoptimalsolutions多重最佳解之任何加權平均值亦為一組最佳解X1=(350,0)最佳解1X2=(0,600)最佳解2X=αX1+(1-α)X2,α∈[0,1]亦為最佳解目標函數Z23若多重最佳解存在，則目標函數必定平行其中一個限制式多重最佳解最佳解敏感性分析之角色

TheRoleofSensitivityAnalysis oftheOptimalSolution(p.75)

輸入參數之變動對於最佳解之敏感度為何?

從事敏感性分析之原因：輸入參數可能只是估計值或最佳估計值模型建立在一個動態環境，因此有些參數可能變動“如果..會”(“What-if”)分析可以提供經濟地與作業地資訊.24最佳解敏感性分析之角色

TheRoleof

最佳範圍(RangeofOptimality)

(p.76)當其他因素保持不變時，在不改變最佳解之情況下，目標函數某係數可以變動多少?(p.77)最佳解將不會改變，若目標函數係數仍在最佳範圍內不改變其他輸入參數目標函數某係數乘上一個非零正數，則目標函數會改變.(1)目標函數係數之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.25最佳範圍(RangeofOptimality)(p6001000500800X2X1Max8X1+5X2Max4X1+5X2Max3.75X1+5X2Max2X1+5X2目標函數係數之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.最佳解仍為(320,360)(320,360)C1係數=2，最佳解為(0,600)而(320,360)不再是最佳解(0,600)減少C1係數由8→3.75266001000500800X2X1Max8X1+5X26001000400600800X2X1Max8X1+5X2Max3.75X1+5X2Max10X1+5X2C1係數的最佳範圍:[3.75,10]目標函數係數之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.增加C1係數，由8→10最佳解仍包含(320,360)(320,360)同理，C2係數的最佳範圍:[4,10.67](Canyoufindit?)276001000400600800X2X1Max8X1+5一個變數Xj

=0的縮減成本RCj為目標函數係數需要增加量的負值(-DZj)，使得最佳解中該變數為正數(Xj

>0)縮減成本RCj為此變數Xj每增加一單位(DXj=1)，目標函數會改變的值C1=2X*=(0,600)X1=0→C1=3.75X*=(320,360)X1=320>0RC1=-∆Z1=-(3.75-2)=-1.75縮減成本Reducedcost(p.78)28一個變數Xj=0的縮減成本RCj為目標函數係數需要增加量的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.75RC1=-1.75296001000500800X2X1Max3.75X1+問題：若其他參數不變之前提下，若右手值變動一個單位，對於目標函數之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解(2)右手邊數值之敏感性分析(p.78)SensitivityAnalysisof

Right-HandSideValues30問題：(2)右手邊數值之敏感性分析(p.78)Sen發現：任意變動束縛函數(BindingConstraints)之右手值，都會改變目前最佳解非束縛函數(Non-BindingConstraints)之右手值，當變動數量少於寬鬆(slack)或剩餘(surplus)量時，都不會改變目前最佳解此結果可以由影子價格(ShadowPrice)來解釋右手邊數值之敏感性分析SensitivityAnalysisof

Right-HandSideValues31發現：右手邊數值之敏感性分析SensitivityAn影子價格ShadowPrices(p.80)若其他輸入參數不變之前提下，限制式的影子價格

是當其對應的右手值增加一個單位時，對最佳目標函數值的變動量32影子價格ShadowPrices(p.80)若其他輸入1000500X2X15002X1+1x2<=1000最佳解由(320,360)→(320.8,359.4)Productiontime限制式

X*=(320,360)Z*=$43602X1+1x2<=1001

X*=(320.8,359.4)Z*=$4363.4當右手值增加(例如由1000→1001)則可行區域擴大影子價格ShadowPrice–圖形表示graphicaldemonstrationPlastic限制式Shadowprice=4363.40–4360.00=3.40331000500X2X15002X1+1x2<=1000可行性範圍RangeofFeasibility(p.81)若其他輸入參數不變之前提下右手值的可行性範圍是影子價格依然不變的右手值可以變動的範圍.在可行性範圍內，目標函數之改變量Changeinobjectivevalue=

[影價Shadowprice]*[右手值變量Changeintherighthandsidevalue]34可行性範圍RangeofFeasibility(p.塑膠的可行性範圍RangeofFeasibility(p.81)1000500X2X15002X1+1x2<=1000塑膠原料的數量可以增加到一個新限制式成為Binding為止Plastic限制式此處為不可行解Productiontime限制式TotalProduction限制式X1+X2

£700TotalProduction成為新的束縛限制式(NewBindingConstraint)35塑膠的可行性範圍RangeofFeasibility塑膠的可行性範圍RangeofFeasibility1000500X2X1600Plastic限制式Productiontime限制式3X1+4X2≤2400請注意看：當塑膠數量增加時最佳解的變化TotalProduction限制式X1+X2≤700

塑膠的可行性範圍

上限=2X1+1X2=2*(400)+300=1100X1+X2=7003X1+4X2=2400之解X*=(400,300)為最佳解2X1+1x2

£100036塑膠的可行性範圍RangeofFeasibility1塑膠的可行性範圍RangeofFeasibility1000500X2X1600Plastic限制式2X1+1X2

£1000請注意看：當塑膠數量減少時最佳解的變化X1=0成為新的束縛限制式Infeasiblesolution3X1+4X2=2400X1=0之解X*=(0,600)為最佳解塑膠的可行性範圍

下限=2X1+1X2=2*(0)+1*600=600Productiontime限制式3X1+4X2≤240037塑膠的可行性範圍RangeofFeasibility1已投入成本(Sunkcosts):

未被包括在目標函數係數之計算當中的資源成本-ShadowPrice為該資源額外一單位的價值淨利潤可以將已投入成本$3800由目標函數值中扣除

影子價格的正確解釋Thecorrectinterpretationofshadowprices(p.83)1000磅塑膠每磅$3→

TotalCost=$3000ProductionTime$20/hr→TotalCost

=$20*40=$800

不管一週實際使用多少塑膠與ProductionTime，$3000+$800=$3800都必須支付，故為已投入成本38影子價格的正確解釋Thecorrectinterpre已包括成本(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.7339影子價格的正確解釋Thecorrectinterpre(3)其他後最佳性變動(p.84)

OtherPost-OptimalityChanges加入一個新限制式(Additionofaconstraint)刪除一個限制式(Deletionofaconstraint)決定最佳解是否滿足此限制式Yes,thesolutionisstilloptimalNo,re-solvetheproblem(thenewobjectivefunctionisworsethantheoriginalone)決定刪除的限制式是否為束縛限制式Yes,re-solvetheproblem(thenewobjectivefunctionisbetter

thantheoriginalone)No,thesolutionisstilloptimal40(3)其他後最佳性變動(p.84)

OtherPos其他後最佳性變動(p.84)

OtherPost-OptimalityChanges刪除變數(Deletionofavariable)增加變數(Additionofavariable)─考慮淨邊際利潤(NetMarginalProfit)決定被刪除變數在最佳解中是否為0Yes,thesolutionisstilloptimalNo,re-solvetheproblem(thenewobjectivefunctionisworsethantheoriginalone)41其他後最佳性變動(p.84)

OtherPost-O其他後最佳性變動(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)仍為最佳解42其他後最佳性變動(p.85)

OtherPost-O其他後最佳性變動(p.85)

OtherPost-OptimalityChanges左手係數的變動(Changesintheleft-handsidecoefficients.)43其他後最佳性變動(p.85)

OtherPost-O使用ExcelSolver尋找最佳解與分析結果點選Galaxy.xls，可見輸入試算表點選工具\規劃求解(Solver)，可見下列對話視窗.EqualTo:ByChangingcells這些儲存格包含

決策變數$B$4:$C$4加入限制式按此鍵…SetTargetcell$D$6此儲存格包含

目標函數值$D$7:$D$10$F$7:$F$10所有具有相同方向之限制式必須包含在一個”Excel限制式”.44使用ExcelSolver尋找最佳解與分析結果點選Ga使用ExcelSolver點選Galaxy.xls，可見輸入試算表.EqualTo:$D$7:$D$10<=$F$7:$F$10ByChangingcells這些儲存格包含

決策變數$B$4:$C$4SetTargetcell$D$6此儲存格包含

目標函數值點選“選項/Option”並勾選”線性規劃”與“非負”.45使用ExcelSolver點選Galaxy.xls，可見點選Galaxy.xls，可見輸入試算表EqualTo:$D$7:$D$10<=$F$7:$F$10ByChangingcells$B$4:$C$4SetTargetcell$D$6使用ExcelSolver按Solve以求最佳解46點選Galaxy.xls，可見輸入試算表EqualTo:$使用ExcelSolver–最佳解47使用ExcelSolver–最佳解47使用ExcelSolver–最佳解Solver能提供分析報告與最佳解48使用ExcelSolver–最佳解Solver能提供使用ExcelSolver–解答報表AnswerReport49使用ExcelSolver–解答報表AnswerRe使用ExcelSolver–敏感性分析報表SensitivityReport50使用ExcelSolver–敏感性分析報表Sensiti不可行性(Infeasibility):

一模型中無可行點(p.96)無窮性(Unboundness):一模型中可行解存在，但目標函數沒有限制。目標函數值為無限大(在極大化問題)或無限小(在極小化問題)

(p.98)多重解(Alternatesolution):一模型中有一個以上的可行點使目標函數為最佳(p.98)無單一最佳解之模型51不可行性(Infeasibility):一模型中無可行點

1Nopoint,simultaneously,liesbothabovelineand

belowlinesand.12323不可行模型InfeasibleModel521Nopoint,simultaneously,12不可行模型Solver呈現之結果Solver呈現無法找到可行解之結果53不可行模型Solver呈現之結果Solver呈現無法找到無窮性

Unboundedsolution可行區域Maximize目標函數54無窮性

Unboundedsolution可行區無窮性模型Solver呈現之結果Solver呈現SetCell值無法收斂之結果55無窮性模型Solver呈現之結果Solver呈現SetSolver沒有提醒”多重最佳解”存在的情形有”多重最佳解”的LP模型，則某個變數Xj

的目標函數的allowableincreaseorallowabledecrease為0.以Solver尋找多重最佳解的程序如下：(p.99)觀察到某個變數Xj中

多重最佳解模型Solver呈現之結果Allowableincrease=0,或Allowabledecrease=0.56Solver沒有提醒”多重最佳解”存在的情形多重最佳解模型加入一個限制式:

Objectivefunction=Currentoptimalvalue.IfAllowableincrease=0,changetheobjectivetoMaximizeXjIfAllowabledecrease=0,changetheobjectivetoMinimizeXj

Excel試算表多重最佳解模型Solver呈現之結果57加入一個限制式:

Objectivefunction=線性規劃軟體可以求解大型線性模型大多數線性規劃軟體使用的技巧單形法(SimplexMethod)(原理部分見補充CD3)

內點法(InteriorPointMethod)整數線性規劃軟體使用的技巧如切面法(CuttingPlaneMethod)分支界限法(BranchandBoundPointMethod)(原理部分見補充CD3)

LP程式的代數解法58線性規劃軟體可以求解大型線性模型LP程式的代數解法58線性規劃模式

LinearProgrammingModelsChapter359線性規劃模式

LinearProgrammingMode線性規劃模型(LinearProgrammingmodel)是在一組「線性」的限制式(asetoflinearconstraints)之下，尋找極大化(maximize)或極小化(minimize)一個特定的目標函數(objective

function)

線性規劃模型由下列三個部分組成:一組決策變數(Asetofdecisionvariables)一個特定的目標函數(Anobjectivefunction)一組「線性」的限制式(Asetofconstraints)

線性規劃簡介

IntroductiontoLinearProgramming60線性規劃模型(LinearProgrammingmode線性規劃簡介

IntroductiontoLinearProgramming線性規劃重要性許多現實問題本身就適用線性規劃模型

已存在許多有效的求解技巧已存在許多著名的成功應用實例ManufacturingMarketingFinance(investment)AdvertisingAgriculture61線性規劃簡介

IntroductiontoLinear線性規劃重要性線性規劃套裝軟體之所產生的結果提供有用的「如果…則」“what…

if”的分析資訊線性規劃簡介

IntroductiontoLinearProgramming62線性規劃重要性線性規劃簡介

Introductionto線性規劃模型之假設

AssumptionsforLinearProgramming參數具有「確定性」(certainty)目標函數與限制式符合「固定規模報酬」之假設(constantreturnstoscale)「疊加性」之假設：決策變數間沒有互動性

，即某函數之總價值只能藉由線性加總求得「連續性」(Continuity)之假設變數值必須再某一個可行範圍內1單位產品$4，3Hrs生產500單位產品$4*500=$2000，3*500=1,500Hrs生產63線性規劃模型之假設

AssumptionsforLin典型範例

TheGalaxyIndustriesProductionProblem

Galaxy生產兩種玩具模型:宇宙光SpaceRay.射擊手Zapper.

資源限制(Resources)1000磅特殊塑膠化合物(specialplastic)每週40小時生產時間(40hrsofproductiontimeperweek)64典型範例

TheGalaxyIndustriesPr市場需求(Marketingrequirement)每週總產量至多700打SpaceRays週產量不能過Zappers350打以上技術係數(Technologicalinputs)(Table2.2)

SpaceRays每打需要2pounds塑膠與3分鐘生產時間Zappers每打需要1pound塑膠與4分鐘生產時間典型範例

TheGalaxyIndustriesProductionProblem65市場需求(Marketingrequirement)技術係

生產需求:

SpaceRay每打利潤(profit)$8，Zappers每打利潤(profit)$5盡量多生產SpaceRay，剩餘資源再生產Zapper目前生產計畫:

SpaceRays=450dozen Zapper =100dozen Profit =$4100perweek典型範例

TheGalaxyIndustriesProductionProblem8(450)+5(100)66生產需求:目前生產計畫:典型範例

TheGalaxy 管理是尋求一個生產排程為了是能增加公司的利潤Managementisseekingaproductionschedulethatwillincreasethecompany’sprofit.67 管理是尋求一個生產排程為了是能增加公司的利潤9

線性規劃模式可以提供一種深入與聰明之方法來解決此問題Alinearprogrammingmodel canprovideaninsightandan intelligentsolutiontothisproblem.68 10決策變數(Decisionsvariables):X1=每週生產的SpaceRays打數X2=每週生產的Zappers打數目標函數(ObjectiveFunction):

極大化每週總利潤

典型範例線性規劃模式

TheGalaxyLinearProgrammingModel69決策變數(Decisionsvariables):典型範例

Max8X1+5X2 (每週總利潤) subjectto 2X1+1X2

£1000(塑膠原料,Plastic) 3X1+4X2

£2400(生產時間,ProductionTime) X1+X2

£700(最大產量,Totalproduction) X1-X2

£350(組合) Xj>=0,j=1,2(非負值,Nonnegativity)典型範例線性規劃模式

TheGalaxyLinearProgrammingModel70 Max8X1+5X2 (每週總利潤)典型範例線線性規劃模式圖形分析

GraphicalAnalysisofLinearProgramming滿足模型全部限制式的所有點集合稱為

Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda

可行區域FEASIBLEREGION71線性規劃模式圖形分析

Graphic

圖形表示法(graphicalpresentation)所有限制式(alltheconstraints)

目標函數(objectivefunction)可行點(threetypesoffeasiblepoints)72圖形表示法(graphicalpresentationThenon-negativityconstraints(非負限制式)X2X1圖形分析–可行區域

GraphicalAnalysis–theFeasibleRegion73Thenon-negativityconstraints1000500FeasibleX2InfeasibleProduction

Time限制式3X1+4X2£

2400

Totalproduction限制式X1+X2£

700(多餘)500700Plastic限制式2X1+X2£1000X1700圖形分析–可行區域

GraphicalAnalysis–theFeasibleRegion741000500FeasibleX2InfeasiblePro1000500FeasibleX2InfeasibleProduction

Time

限制式3X1+4X2£2400

Totalproduction

限制式X1+X2£700(多餘)500700Mix限制式X1-X2£

350Plastic限制式2X1+X2£1000X1700圖形分析–可行區域(p.67~68)

GraphicalAnalysis–theFeasibleRegion可行點(feasiblepoints)有三種內部點Interiorpoints.邊界點Boundarypoints.端點Extremepoints.751000500FeasibleX2InfeasiblePro以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution76以圖形求解是為了尋求最佳解SolvingGraphical尋求最佳解圖解程序(p.71)

Thesearchforanoptimalsolution由任一個profit開始,sayprofit=$1,250.往利潤增加方向移動increasetheprofit,ifpossible...持續平行移動到無法增加為止

continueuntilitbecomesinfeasibleOptimalProfit=$43605007001000500X2X1紅色線段Profit=$125077尋求最佳解圖解程序(p.71)

Thesearchf最佳解(p.69)

SummaryoftheoptimalsolutionSpaceRaysX1*=320dozenZappersX2*=360dozenProfit Z

*=$4360此最佳解使用了所有的塑膠原料(plastic)與生產時間(productionhours).

2X1+1X2=1000(塑膠原料,Plastic) 3X1+4X2=2400(生產時間,ProductionTime)Excel試算表束縛方程式(BindingConstraints):等式被滿足之限制式78最佳解(p.69)

Summaryoftheop最佳解(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的寬鬆79最佳解(p.70~71)

Summaryofthe若一個線性規劃問題有一組最佳解，此最佳解一定發生在”端點”上(端點最佳解之候選人,True/False)兩個束縛方程式的交點形成一個”端點”或”角點”端點與最佳解(p.72)

Extremepointsandoptimalsolutions端點：可行區域的角點2X1+X2=1000

X1-X2=350之解(450,100)(320,360)2X1+X2=10003X1+4X2=2400之解(0,600)3X1+4X2=2400

X1=0之解80若一個線性規劃問題有一組最佳解，此最佳解一定發生在”端點”上若多重最佳解存在，則目標函數必定平行其中一個限制式多重最佳解

Multipleoptimalsolutions多重最佳解之任何加權平均值亦為一組最佳解X1=(350,0)最佳解1X2=(0,600)最佳解2X=αX1+(1-α)X2,α∈[0,1]亦為最佳解目標函數Z81若多重最佳解存在，則目標函數必定平行其中一個限制式多重最佳解最佳解敏感性分析之角色

TheRoleofSensitivityAnalysis oftheOptimalSolution(p.75)

輸入參數之變動對於最佳解之敏感度為何?

從事敏感性分析之原因：輸入參數可能只是估計值或最佳估計值模型建立在一個動態環境，因此有些參數可能變動“如果..會”(“What-if”)分析可以提供經濟地與作業地資訊.82最佳解敏感性分析之角色

TheRoleof

最佳範圍(RangeofOptimality)

(p.76)當其他因素保持不變時，在不改變最佳解之情況下，目標函數某係數可以變動多少?(p.77)最佳解將不會改變，若目標函數係數仍在最佳範圍內不改變其他輸入參數目標函數某係數乘上一個非零正數，則目標函數會改變.(1)目標函數係數之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.83最佳範圍(RangeofOptimality)(p6001000500800X2X1Max8X1+5X2Max4X1+5X2Max3.75X1+5X2Max2X1+5X2目標函數係數之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.最佳解仍為(320,360)(320,360)C1係數=2，最佳解為(0,600)而(320,360)不再是最佳解(0,600)減少C1係數由8→3.75846001000500800X2X1Max8X1+5X26001000400600800X2X1Max8X1+5X2Max3.75X1+5X2Max10X1+5X2C1係數的最佳範圍:[3.75,10]目標函數係數之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.增加C1係數，由8→10最佳解仍包含(320,360)(320,360)同理，C2係數的最佳範圍:[4,10.67](Canyoufindit?)856001000400600800X2X1Max8X1+5一個變數Xj

=0的縮減成本RCj為目標函數係數需要增加量的負值(-DZj)，使得最佳解中該變數為正數(Xj

>0)縮減成本RCj為此變數Xj每增加一單位(DXj=1)，目標函數會改變的值C1=2X*=(0,600)X1=0→C1=3.75X*=(320,360)X1=320>0RC1=-∆Z1=-(3.75-2)=-1.75縮減成本Reducedcost(p.78)86一個變數Xj=0的縮減成本RCj為目標函數係數需要增加量的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.75RC1=-1.75876001000500800X2X1Max3.75X1+問題：若其他參數不變之前提下，若右手值變動一個單位，對於目標函數之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解(2)右手邊數值之敏感性分析(p.78)SensitivityAnalysisof

Right-HandSideValues88問題：(2)右手邊數值之敏感性分析(p.78)Sen發現：任意變動束縛函數(BindingConstraints)之右手值，都會改變目前最佳解非束縛函數(Non-BindingConstraints)之右手值，當變動數量少於寬鬆(slack)或剩餘(surplus)量時，都不會改變目前最佳解此結果可以由影子價格(ShadowPrice)來解釋右手邊數值之敏感性分析SensitivityAnalysisof

Right-HandSideValues89發現：右手邊數值之敏感性分析SensitivityAn影子價格ShadowPrices(p.80)若其他輸入參數不變之前提下，限制式的影子價格

是當其對應的右手值增加一個單位時，對最佳目標函數值的變動量90影子價格ShadowPrices(p.80)若其他輸入1000500X2X15002X1+1x2<=1000最佳解由(320,360)→(320.8,359.4)Productiontime限制式

X*=(320,360)Z*=$43602X1+1x2<=1001

X*=(320.8,359.4)Z*=$4363.4當右手值增加(例如由1000→1001)則可行區域擴大影子價格ShadowPrice–圖形表示graphicaldemonstrationPlastic限制式Shadowprice=4363.40–4360.00=3.40911000500X2X15002X1+1x2<=1000可行性範圍RangeofFeasibility(p.81)若其他輸入參數不變之前提下右手值的可行性範圍是影子價格依然不變的右手值可以變動的範圍.在可行性範圍內，目標函數之改變量Changeinobjectivevalue=

[影價Shadowprice]*[右手值變量Changeintherighthandsidevalue]92可行性範圍RangeofFeasibility(p.塑膠的可行性範圍RangeofFeasibility(p.81)1000500X2X15002X1+1x2<=1000塑膠原料的數量可以增加到一個新限制式成為Binding為止Plastic限制式此處為不可行解Productiontime限制式TotalProduction限制式X1+X2

£700TotalProduction成為新的束縛限制式(NewBindingConstraint)93塑膠的可行性範圍RangeofFeasibility塑膠的可行性範圍RangeofFeasibility1000500X2X1600Plastic限制式Productiontime限制式3X1+4X2≤2400請注意看：當塑膠數量增加時最佳解的變化TotalProduction限制式X1+X2≤700

塑膠的可行性範圍

上限=2X1+1X2=2*(400)+300=1100X1+X2=7003X1+4X2=2400之解X*=(400,300)為最佳解2X1+1x2

£100094塑膠的可行性範圍RangeofFeasibility1塑膠的可行性範圍RangeofFeasibility1000500X2X1600Plastic限制式2X1+1X2

£1000請注意看：當塑膠數量減少時最佳解的變化X1=0成為新的束縛限制式Infeasiblesolution3X1+4X2=2400X1=0之解X*=(0,600)為最佳解塑膠的可行性範圍

下限=2X1+1X2=2*(0)+1*600=600Productiontime限制式3X1+4X2≤240095塑膠的可行性範圍RangeofFeasibility1已投入成本(Sunkcosts):

未被包括在目標函數係數之計算當中的資源成本-ShadowPrice為該資源額外一單位的價值淨利潤可以將已投入成本$3800由目標函數值中扣除

影子價格的正確解釋Thecorrectinterpretationofshadowprices(p.83)1000磅塑膠每磅$3→

TotalCost=$3000ProductionTime$20/hr→TotalCost

=$20*40=$800

不管一週實際使用多少塑膠與ProductionTime，$3000+$800=$3800都必須支付，故為已投入成本96影子價格的正確解釋Thecorrectinterpre已包括成本(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.7397影子價格的正確解釋Thecorrectinterpre(3)其他後最佳性變動(p.84)

OtherPost-OptimalityChanges加入一個新限制式(Additionofaconstraint)刪除一個限制式(Deletionofaconstraint)決定最佳解是否滿足此限制式Yes,thesolutionisstilloptimalNo,re-solvetheproblem(thenewobjectivefunctionisworsethantheoriginalone)決定刪除的限制式是否為束縛限制式Yes,re-solvetheproblem(thenewobjectivefunctionisbetter

thantheoriginalone)No,thesolutionisstilloptimal98(3)其他後最佳性變動(p.84)

OtherPos其他後最佳性變動(p.84)

OtherPost-OptimalityChanges刪除變數(Deletionofavariable)增加變數(Additionofavariable)─考慮淨邊際利潤(NetMarginalProfit)決定被刪除變數在最佳解中是否為0Yes,thesolutionisstilloptimalNo,re-solvetheproblem(thenewobjectivefunctionisworsethantheoriginalone)99其他後最佳性變動(p.84)

OtherPost-O其他後最佳性變動(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