線性規(guī)劃模式Linear-Programming-Models課件

線性規(guī)劃模式

LinearProgrammingModelsChapter31線性規(guī)劃模式

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

function)

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

線性規(guī)劃簡介

IntroductiontoLinearProgramming2線性規(guī)劃模型(LinearProgrammingmode線性規(guī)劃簡介

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

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

IntroductiontoLinear線性規(guī)劃重要性線性規(guī)劃套裝軟體之所產(chǎn)生的結(jié)果提供有用的「如果…則」“what…

if”的分析資訊線性規(guī)劃簡介

IntroductiontoLinearProgramming4線性規(guī)劃重要性線性規(guī)劃簡介

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

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

，即某函數(shù)之總價(jià)值只能藉由線性加總求得「連續(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)5線性規(guī)劃模型之假設(shè)

AssumptionsforLin典型範(fàn)例

TheGalaxyIndustriesProductionProblem

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

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

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

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

TheGalaxyIndustriesProductionProblem7市場需求(Marketingrequirement)技術(shù)係

生產(chǎn)需求:

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

SpaceRays=450dozen Zapper =100dozen Profit =$4100perweek典型範(fàn)例

TheGalaxyIndustriesProductionProblem8(450)+5(100)8生產(chǎn)需求:目前生產(chǎn)計(jì)畫:典型範(fàn)例

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

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

極大化每週總利潤

典型範(fàn)例線性規(guī)劃模式

TheGalaxyLinearProgrammingModel11決策變數(shù)(Decisionsvariables):典型範(fàn)例

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)典型範(fàn)例線性規(guī)劃模式

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

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

Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda

可行區(qū)域FEASIBLEREGION13線性規(guī)劃模式圖形分析

Graphic

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

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

GraphicalAnalysis–theFeasibleRegion15Thenon-negativityconstraints1000500FeasibleX2InfeasibleProduction

Time限制式3X1+4X2￡

2400

Totalproduction限制式X1+X2￡

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

GraphicalAnalysis–theFeasibleRegion161000500FeasibleX2InfeasiblePro1000500FeasibleX2InfeasibleProduction

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.171000500FeasibleX2InfeasiblePro以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution18以圖形求解是為了尋求最佳解SolvingGraphical尋求最佳解圖解程序(p.71)

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

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

Thesearchf最佳解(p.69)

SummaryoftheoptimalsolutionSpaceRaysX1*=320dozenZappersX2*=360dozenProfit Z

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

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

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

Summaryofthe若一個線性規(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之解22若一個線性規(guī)劃問題有一組最佳解，此最佳解一定發(fā)生在”端點(diǎn)”上若多重最佳解存在，則目標(biāo)函數(shù)必定平行其中一個限制式多重最佳解

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

TheRoleofSensitivityAnalysis oftheOptimalSolution(p.75)

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

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

TheRoleof

最佳範(fàn)圍(RangeofOptimality)

(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ù)之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.25最佳範(fàn)圍(RangeofOptimality)(p6001000500800X2X1Max8X1+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.75266001000500800X2X1Max8X1+5X26001000400600800X2X1Max8X1+5X2Max3.75X1+5X2Max10X1+5X2C1係數(shù)的最佳範(fàn)圍:[3.75,10]目標(biāo)函數(shù)係數(shù)之敏感性分析SensitivityAnalysisof

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

=0的縮減成本RCj為目標(biāo)函數(shù)係數(shù)需要增加量的負(fù)值(-DZj)，使得最佳解中該變數(shù)為正數(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)28一個變數(shù)Xj=0的縮減成本RCj為目標(biāo)函數(shù)係數(shù)需要增加量的6001000500800X2X1Max3.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.75RC1=-1.75296001000500800X2X1Max3.75X1+問題：若其他參數(shù)不變之前提下，若右手值變動一個單位，對於目標(biāo)函數(shù)之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解(2)右手邊數(shù)值之敏感性分析(p.78)SensitivityAnalysisof

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

Right-HandSideValues31發(fā)現(xiàn)：右手邊數(shù)值之敏感性分析SensitivityAn影子價(jià)格ShadowPrices(p.80)若其他輸入?yún)?shù)不變之前提下，限制式的影子價(jià)格

是當(dāng)其對應(yīng)的右手值增加一個單位時，對最佳目標(biāo)函數(shù)值的變動量32影子價(jià)格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當(dāng)右手值增加(例如由1000→1001)則可行區(qū)域擴(kuò)大影子價(jià)格ShadowPrice–圖形表示graphicaldemonstrationPlastic限制式Shadowprice=4363.40–4360.00=3.40331000500X2X15002X1+1x2<=1000可行性範(fàn)圍RangeofFeasibility(p.81)若其他輸入?yún)?shù)不變之前提下右手值的可行性範(fàn)圍是影子價(jià)格依然不變的右手值可以變動的範(fàn)圍.在可行性範(fàn)圍內(nèi)，目標(biāo)函數(shù)之改變量Changeinobjectivevalue=

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

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

塑膠的可行性範(fàn)圍

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

￡100036塑膠的可行性範(fàn)圍RangeofFeasibility1塑膠的可行性範(fàn)圍RangeofFeasibility1000500X2X1600Plastic限制式2X1+1X2

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

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

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

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

TotalCost=$3000ProductionTime$20/hr→TotalCost

=$20*40=$800

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

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

→管理者願意為額外ProductionTime多支付$0.7339影子價(jià)格的正確解釋Thecorrectinterpre(3)其他後最佳性變動(p.84)

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

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

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

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

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

OtherPost-OptimalityChanges【範(fàn)例】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)淨(jìng)邊際利潤=$10-($3.4*(3)+$0.4*(5)+$0*(1)+$0*(0))=-$2.2<0大水槍不具生產(chǎn)價(jià)值

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

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

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

OtherPost-O使用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限制式”.44使用ExcelSolver尋找最佳解與分析結(jié)果點(diǎn)選Ga使用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ù)”.45使用ExcelSolver點(diǎn)選Galaxy.xls，可見點(diǎn)選Galaxy.xls，可見輸入試算表EqualTo:$D$7:$D$10<=$F$7:$F$10ByChangingcells$B$4:$C$4SetTargetcell$D$6使用ExcelSolver按Solve以求最佳解46點(diǎn)選Galaxy.xls，可見輸入試算表EqualTo:$使用ExcelSolver–最佳解47使用ExcelSolver–最佳解47使用ExcelSolver–最佳解Solver能提供分析報(bào)告與最佳解48使用ExcelSolver–最佳解Solver能提供使用ExcelSolver–解答報(bào)表AnswerReport49使用ExcelSolver–解答報(bào)表AnswerRe使用ExcelSolver–敏感性分析報(bào)表SensitivityReport50使用ExcelSolver–敏感性分析報(bào)表Sensiti不可行性(Infeasibility):

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

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

1Nopoint,simultaneously,liesbothabovelineand

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

Unboundedsolution可行區(qū)域Maximize目標(biāo)函數(shù)54無窮性

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

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

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

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

Excel試算表多重最佳解模型Solver呈現(xiàn)之結(jié)果57加入一個限制式:

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

內(nèi)點(diǎn)法(InteriorPointMethod)整數(shù)線性規(guī)劃軟體使用的技巧如切面法(CuttingPlaneMethod)分支界限法(BranchandBoundPointMethod)(原理部分見補(bǔ)充CD3)

LP程式的代數(shù)解法58線性規(guī)劃軟體可以求解大型線性模型LP程式的代數(shù)解法58線性規(guī)劃模式

LinearProgrammingModelsChapter359線性規(guī)劃模式

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

function)

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

線性規(guī)劃簡介

IntroductiontoLinearProgramming60線性規(guī)劃模型(LinearProgrammingmode線性規(guī)劃簡介

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

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

IntroductiontoLinear線性規(guī)劃重要性線性規(guī)劃套裝軟體之所產(chǎn)生的結(jié)果提供有用的「如果…則」“what…

if”的分析資訊線性規(guī)劃簡介

IntroductiontoLinearProgramming62線性規(guī)劃重要性線性規(guī)劃簡介

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

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

，即某函數(shù)之總價(jià)值只能藉由線性加總求得「連續(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)63線性規(guī)劃模型之假設(shè)

AssumptionsforLin典型範(fàn)例

TheGalaxyIndustriesProductionProblem

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

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

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

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

TheGalaxyIndustriesProductionProblem65市場需求(Marketingrequirement)技術(shù)係

生產(chǎn)需求:

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

SpaceRays=450dozen Zapper =100dozen Profit =$4100perweek典型範(fàn)例

TheGalaxyIndustriesProductionProblem8(450)+5(100)66生產(chǎn)需求:目前生產(chǎn)計(jì)畫:典型範(fàn)例

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

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

極大化每週總利潤

典型範(fàn)例線性規(guī)劃模式

TheGalaxyLinearProgrammingModel69決策變數(shù)(Decisionsvariables):典型範(fàn)例

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)典型範(fàn)例線性規(guī)劃模式

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

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

Thesetofallpointsthatsatisfyalltheconstraintsofthemodeliscalleda

可行區(qū)域FEASIBLEREGION71線性規(guī)劃模式圖形分析

Graphic

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

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

GraphicalAnalysis–theFeasibleRegion73Thenon-negativityconstraints1000500FeasibleX2InfeasibleProduction

Time限制式3X1+4X2￡

2400

Totalproduction限制式X1+X2￡

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

GraphicalAnalysis–theFeasibleRegion741000500FeasibleX2InfeasiblePro1000500FeasibleX2InfeasibleProduction

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.751000500FeasibleX2InfeasiblePro以圖形求解是為了尋求最佳解SolvingGraphicallyforanOptimalSolution76以圖形求解是為了尋求最佳解SolvingGraphical尋求最佳解圖解程序(p.71)

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

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

Thesearchf最佳解(p.69)

SummaryoftheoptimalsolutionSpaceRaysX1*=320dozenZappersX2*=360dozenProfit Z

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

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

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

Summaryofthe若一個線性規(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之解80若一個線性規(guī)劃問題有一組最佳解，此最佳解一定發(fā)生在”端點(diǎn)”上若多重最佳解存在，則目標(biāo)函數(shù)必定平行其中一個限制式多重最佳解

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

TheRoleofSensitivityAnalysis oftheOptimalSolution(p.75)

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

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

TheRoleof

最佳範(fàn)圍(RangeofOptimality)

(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ù)之敏感性分析SensitivityAnalysisof

ObjectiveFunctionCoefficients.83最佳範(fàn)圍(RangeofOptimality)(p6001000500800X2X1Max8X1+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.75846001000500800X2X1Max8X1+5X26001000400600800X2X1Max8X1+5X2Max3.75X1+5X2Max10X1+5X2C1係數(shù)的最佳範(fàn)圍:[3.75,10]目標(biāo)函數(shù)係數(shù)之敏感性分析SensitivityAnalysisof

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

=0的縮減成本RCj為目標(biāo)函數(shù)係數(shù)需要增加量的負(fù)值(-DZj)，使得最佳解中該變數(shù)為正數(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)86一個變數(shù)Xj=0的縮減成本RCj為目標(biāo)函數(shù)係數(shù)需要增加量的6001000500800X2X1Max3.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.75RC1=-1.75876001000500800X2X1Max3.75X1+問題：若其他參數(shù)不變之前提下，若右手值變動一個單位，對於目標(biāo)函數(shù)之最佳解有何影響?多少變動單位(增加或減少)，可以保持目前最佳解(2)右手邊數(shù)值之敏感性分析(p.78)SensitivityAnalysisof

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

Right-HandSideValues89發(fā)現(xiàn)：右手邊數(shù)值之敏感性分析SensitivityAn影子價(jià)格ShadowPrices(p.80)若其他輸入?yún)?shù)不變之前提下，限制式的影子價(jià)格

是當(dāng)其對應(yīng)的右手值增加一個單位時，對最佳目標(biāo)函數(shù)值的變動量90影子價(jià)格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當(dāng)右手值增加(例如由1000→1001)則可行區(qū)域擴(kuò)大影子價(jià)格ShadowPrice–圖形表示graphicaldemonstrationPlastic限制式Shadowprice=4363.40–4360.00=3.40911000500X2X15002X1+1x2<=1000可行性範(fàn)圍RangeofFeasibility(p.81)若其他輸入?yún)?shù)不變之前提下右手值的可行性範(fàn)圍是影子價(jià)格依然不變的右手值可以變動的範(fàn)圍.在可行性範(fàn)圍內(nèi)，目標(biāo)函數(shù)之改變量Changeinobjectivevalue=

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

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

塑膠的可行性範(fàn)圍

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

￡100094塑膠的可行性範(fàn)圍RangeofFeasibility1塑膠的可行性範(fàn)圍RangeofFeasibility1000500X2X1600Plastic限制式2X1+1X2

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

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

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

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

TotalCost=$3000ProductionTime$20/hr→TotalCost

=$20*40=$800

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

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

→管理者願意為額外ProductionTime多支付$0.7397影子價(jià)格的正確解釋Thecorrectinterpre(3)其他後最佳性變動(p.84)

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

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

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

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

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

OtherPost-OptimalityChanges【範(fàn)例】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