線性規(guī)劃與整數(shù)規(guī)劃模式

1線性規(guī)劃與整數(shù)規(guī)劃模式

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

function)

線性規(guī)劃模型由下列三個部分組成:一組決策變數(shù)(Asetofdecisionvariables)一個特定的目標(biāo)函數(shù)(Anobjectivefunction)一組「線性」的限制式(Asetofconstraints)2.1線性規(guī)劃簡介

IntroductiontoLinearProgramming3線性規(guī)劃簡介

IntroductiontoLinearProgramming線性規(guī)劃重要性許多現(xiàn)實(shí)問題本身就適用線性規(guī)劃模型

已存在許多有效的求解技巧已存在許多著名的成功應(yīng)用實(shí)例ManufacturingMarketingFinance(investment)AdvertisingAgriculture4線性規(guī)劃重要性線性規(guī)劃軟件包之所產(chǎn)生的結(jié)果提供有用的「如果…則」“what…

if”的分析信息線性規(guī)劃簡介

IntroductiontoLinearProgramming5線性規(guī)劃模型之假設(shè)

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

，即某函數(shù)之總價值只能藉由線性加總求得「連續(xù)性」(Continuity)之假設(shè)變量值必須再某一個可行范圍內(nèi)1單位產(chǎn)品$4，3Hrs生產(chǎn)500單位產(chǎn)品$4*500=$2000，3*500=1,500Hrs生產(chǎn)6典型范例

TheGalaxyIndustriesProductionProblem

Galaxy生產(chǎn)兩種玩具模型:宇宙光SpaceRay.射擊手Zapper.

資源限制(Resources)1000磅特殊塑料化合物(specialplastic)每周40小時生產(chǎn)時間(40hrsofproductiontimeperweek)7市場需求(Marketingrequirement)每周總產(chǎn)量至多700打SpaceRays周產(chǎn)量不能過Zappers350打以上技術(shù)系數(shù)(Technologicalinputs)(Table2.2)

SpaceRays每打需要2pounds塑料與3分鐘生產(chǎn)時間Zappers每打需要1pound塑料與4分鐘生產(chǎn)時間典型范例

TheGalaxyIndustriesProductionProblem8

生產(chǎn)需求:

SpaceRay每打利潤(profit)$8，Zappers每打利潤(profit)$5盡量多生產(chǎn)SpaceRay，剩余資源再生產(chǎn)Zapper目前生產(chǎn)計劃:

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

TheGalaxyIndustriesProductionProblem8(450)+5(100)9 管理是尋求一個生產(chǎn)排程為了是能增加公司的利潤Managementisseekingaproductionschedulethatwillincreasethecompany’sprofit.10

線性規(guī)劃模式可以提供一種深入與聰明之方法來解決此問題Alinearprogrammingmodel canprovideaninsightandan intelligentsolutiontothisproblem.11決策變數(shù)(Decisionsvariables):X1=每周生產(chǎn)的SpaceRays打數(shù)X2=每周生產(chǎn)的Zappers打數(shù)目標(biāo)函數(shù)(ObjectiveFunction):

極大化每周總利潤

典型范例線性規(guī)劃模式

TheGalaxyLinearProgrammingModel12

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

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

￡2400(生產(chǎn)時間,ProductionTime) X1+X2

￡700(最大產(chǎn)量,Totalproduction) X1-X2

￡350(組合) Xj>=0,j=1,2(非負(fù)值,Nonnegativity)典型范例線性規(guī)劃模式

TheGalaxyLinearProgrammingModel132.3 線性規(guī)劃模式圖形分析

GraphicalAnalysisofLinearProgramming滿足模型全部限制式的所有點(diǎn)集合稱為

Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda

可行區(qū)域FEASIBLEREGION14

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

目標(biāo)函數(shù)(objectivefunction)可行點(diǎn)(threetypesoffeasiblepoints)15Thenon-negativityconstraints(非負(fù)限制式)X2X1圖形分析–可行區(qū)域

GraphicalAnalysis–theFeasibleRegion161000500FeasibleX2InfeasibleProduction

Time限制式3X1+4X2￡

2400

Totalproduction限制式X1+X2￡

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

GraphicalAnalysis–theFeasibleRegion171000500FeasibleX2InfeasibleProduction

Time

限制式3X1+4X2￡2400

Totalproduction

限制式X1+X2￡700(多余)500700Mix限制式X1-X2￡

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

GraphicalAnalysis–theFeasibleRegion可行點(diǎn)(feasiblepoints)有三種內(nèi)部點(diǎn)Interiorpoints.邊界點(diǎn)Boundarypoints.端點(diǎn)Extremepoints.18以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution19尋求最佳解圖解程序(p.71)

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

continueuntilitbecomesinfeasibleOptimalProfit=$43605007001000500X2X1紅色線段Profit=$125020最佳解(p.69)

SummaryoftheoptimalsolutionSpaceRaysX1*=320dozenZappersX2*=360dozenProfit Z

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

2X1+1X2=1000(塑料原料,Plastic) 3X1+4X2=2400(生產(chǎn)時間,ProductionTime)Excel電子表格束縛方程式(BindingConstraints):等式被滿足之限制式21最佳解(p.70~71)

Summaryoftheoptimalsolution總產(chǎn)量(Totalproduction)680打(not700打)

SpaceRays產(chǎn)量只超過Zappers40打

非束縛方程式(Non-BindingConstraints)：最佳點(diǎn)不在其等式之限制式寬松(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ā)生在”端點(diǎn)”上(端點(diǎn)

最佳解之候選人,True/False)兩個束縛方程式的交點(diǎn)形成一個”端點(diǎn)”或”角點(diǎn)”端點(diǎn)與最佳解(p.72)

Extremepointsandoptimalsolutions端點(diǎn)：可行區(qū)域的角點(diǎn)2X1+X2=1000

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

X1=0之解23若多重最佳解存在，則目標(biāo)函數(shù)必定平行其中一個限制式多重最佳解

Multipleoptimalsolutions多重最佳解之任何加權(quán)平均值亦為一組最佳解X1=(350,0)最佳解1X2=(0,600)最佳解2X=αX1+(1-α)X2,α∈[0,1]亦為最佳解目標(biāo)函數(shù)Z242.4最佳解敏感性分析之角色

TheRoleofSensitivityAnalysis oftheOptimalSolution(p.75)

輸入?yún)?shù)之變動對于最佳解之敏感度為何?

從事敏感性分析之原因：輸入?yún)?shù)可能只是估計值或最佳估計值模型建立在一個動態(tài)環(huán)境，因此有些參數(shù)可能變動“如果..會”(“What-if”)分析可以提供經(jīng)濟(jì)地與作業(yè)地信息.25

最佳范圍(RangeofOptimality)

(p.76)當(dāng)其他因素保持不變時，在不改變最佳解之情況下，目標(biāo)函數(shù)某系數(shù)可以變動多少?(p.77)最佳解將不會改變，若目標(biāo)函數(shù)系數(shù)仍在最佳范圍內(nèi)不改變其他輸入?yún)?shù)目標(biāo)函數(shù)某系數(shù)乘上一個非零正數(shù)，則目標(biāo)函數(shù)會改變.(1)目標(biāo)函數(shù)系數(shù)之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.266001000500800X2X1Max8X1+5X2Max4X1+5X2Max3.75X1+5X2Max2X1+5X2目標(biāo)函數(shù)系數(shù)之敏感性分析SensitivityAnalysisof

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

ObjectiveFunctionCoefficients.增加C1系數(shù)，由8→10最佳解仍包含(320,360)(320,360)同理，C2系數(shù)的最佳范圍:[4,10.67](Canyoufindit?)28一個變數(shù)Xj

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

>0)縮減成本RCj為此變數(shù)Xj每增加一單位(DXj=1)，目標(biāo)函數(shù)會改變的值C1=2X*=(0,600)

X1=0→C1=3.75X*=(320,360)

X1=320>0RC1=-?Z1=-(3.75-2)=-1.75縮減成本Reducedcost(p.78)296001000500800X2X1Max3.75X1+5X2Max2X1+5X2目標(biāo)函數(shù)系數(shù)之敏感性分析

縮減成本(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.7530問題：若其他參數(shù)不變之前提下，若右手值變動一個單位，對于目標(biāo)函數(shù)之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解(2)右手邊數(shù)值之敏感性分析(p.78)SensitivityAnalysisof

Right-HandSideValues31發(fā)現(xiàn)：任意變動束縛函數(shù)(BindingConstraints)之右手值，都會改變目前最佳解非束縛函數(shù)(Non-BindingConstraints)之右手值，當(dāng)變動數(shù)量少于寬松(slack)或剩余(surplus)量時，都不會改變目前最佳解此結(jié)果可以由影子價格(ShadowPrice)來解釋右手邊數(shù)值之敏感性分析SensitivityAnalysisof

Right-HandSideValues32影子價格ShadowPrices(p.80)若其他輸入?yún)?shù)不變之前提下，限制式的影子價格

是當(dāng)其對應(yīng)的右手值增加一個單位時，對最佳目標(biāo)函數(shù)值的變動量331000500X2X15002X1+1x2<=1000最佳解由(320,360)→(320.8,359.4)Productiontime限制式

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

X*=(320.8,359.4)Z*=$4363.4當(dāng)右手值增加(例如由1000→1001)則可行區(qū)域擴(kuò)大影子價格ShadowPrice–圖形表示graphicaldemonstrationPlastic限制式Shadowprice=4363.40–4360.00=3.4034可行性范圍RangeofFeasibility(p.81)若其他輸入?yún)?shù)不變之前提下右手值的可行性范圍是影子價格依然不變的右手值可以變動的范圍.在可行性范圍內(nèi)，目標(biāo)函數(shù)之改變量Changeinobjectivevalue=

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

￡700TotalProduction成為新的束縛限制式(NewBindingConstraint)36塑料的可行性范圍RangeofFeasibility1000500X2X1600Plastic限制式Productiontime限制式3X1+4X2≤2400請注意看：當(dāng)塑膠數(shù)量增加時最佳解的變化TotalProduction限制式X1+X2≤700

塑料的可行性范圍

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

￡100037塑料的可行性范圍RangeofFeasibility1000500X2X1600Plastic限制式2X1+1X2

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

下限=2X1+1X2=2*(0)+1*600=600Productiontime限制式3X1+4X2≤240038已投入成本(Sunkcosts):

未被包括在目標(biāo)函數(shù)系數(shù)之計算當(dāng)中的資源成本-ShadowPrice為該資源額外一單位的價值凈利潤可以將已投入成本$3800由目標(biāo)函數(shù)值中扣除

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

TotalCost=$3000ProductionTime$20/hr→TotalCost

=$20*40=$800

不管一周實(shí)際使用多少塑料與ProductionTime，$3000+$800=$3800都必須支付，故為已投入成本39已包括成本(Includedcosts):被包括在目標(biāo)函數(shù)系數(shù)之計算當(dāng)中的資源成本─ShadowPrice為高于該資源之現(xiàn)有單位價值之額外的價值見p.84表格2.5說明影子價格的正確解釋Thecorrectinterpretationofshadowprices(p.83)塑料每磅$3→塑料影價每磅=$3.4

→管理者愿意為額外塑料磅數(shù)多支付$6.8(已包括成本)ProductionTime$0.33/min(or$20/hr)，ProductionTime影價每分鐘=$0.4

→管理者愿意為額外ProductionTime多支付$0.7340其他后最佳性變動(p.84)

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

thantheoriginalone)No,thesolutionisstilloptimal41其他后最佳性變動(p.84)

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

OtherPost-OptimalityChanges【范例】X3=新產(chǎn)品大水槍產(chǎn)量每一個大水槍需3lb塑料與5min生產(chǎn)時間每打利潤$10Max8X1+5X2+

10X3 (每周總利潤)subjectto 2X1+1X2+3X3≤1000(塑料原料,Plastic,ShadowPrice=$3.4) 3X1+4X2+5X3≤2400(生產(chǎn)時間,ProductionTime,SP=$0.4) X1+X2+X3≤700(最大產(chǎn)量,Totalproduction,SP=$0) X1-X2≤350(組合,SP=$0) Xj>=0,j=1,2,3(非負(fù)值,Nonnegativity)凈邊際利潤=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0))=-$2.2<0

大水槍不具生產(chǎn)價值

X*=(320,360,0)仍為最佳解43其他后最佳性變動(p.85)

OtherPost-OptimalityChanges左手系數(shù)的變動(Changesintheleft-handsidecoefficients.)442.5使用ExcelSolver尋找最佳解與分析結(jié)果點(diǎn)選Galaxy.xls，可見輸入電子表格點(diǎn)選工具\(yùn)規(guī)劃求解(Solver)，可見下列對話窗口.EqualTo:ByChangingcells這些單元格包含

決策變數(shù)$B$4:$C$4加入限制式按此鍵…SetTargetcell$D$6此單元格包含

目標(biāo)函數(shù)值$D$7:$D$10$F$7:$F$10所有具有相同方向之限制式必須包含在一個”Excel限制式”.45使用ExcelSolver點(diǎn)選Galaxy.xls，可見輸入電子表格.EqualTo:$D$7:$D$10<=$F$7:$F$10ByChangingcells這些單元格包含

決策變數(shù)$B$4:$C$4SetTargetcell$D$6此單元格包含

目標(biāo)函數(shù)值點(diǎn)選

“選項(xiàng)/Option”并勾選”線性規(guī)劃”與“非負(fù)”.46點(diǎn)選Galaxy.xls，可見輸入電子表格EqualTo:$D$7:$D$10<=$F$7:$F$10ByChangingcells$B$4:$C$4SetTargetcell$D$6使用ExcelSolver按Solve以求最佳解47使用ExcelSolver–最佳解48使用ExcelSolver–最佳解Solver能提供分析報告與最佳解49使用ExcelSolver–解答報表AnswerReport50使用ExcelSolver–敏感性分析報表SensitivityReport51不可行性(Infeasibility):

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

(p.98)多重解(Alternatesolution):一模型中有一個以上的可行點(diǎn)使目標(biāo)函數(shù)為最佳(p.98)無單一最佳解之模型52

1Nopoint,simultaneously,liesbothabovelineand

belowlinesand.12323不可行模型InfeasibleModel53不可行模型Solver呈現(xiàn)之結(jié)果Solver呈現(xiàn)無法找到可行解之結(jié)果54無窮性

Unboundedsolution可行區(qū)域Maximize目標(biāo)函數(shù)55無窮性模型Solver呈現(xiàn)之結(jié)果Solver呈現(xiàn)SetCell值無法收斂之結(jié)果56Solver沒有提醒”多重最佳解”存在的情形有”多重最佳解”的LP模型，則某個變量Xj

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

多重最佳解模型Solver呈現(xiàn)之結(jié)果Allowableincrease=0,或Allowabledecrease=0.57加入一個限制式:

Objectivefunction=Currentoptimalvalue.IfAllowableincrease=0,change