1Lecture2

LinearProgramming(LP)湖南大學工商管理學院主講：E-mail:

2LectureOutlineLinearProgrammingProblemLinearProgrammingModelGraphicalSolutionsofLPModelCharacteristicsofLPProblems31.線性規(guī)劃問題(LPProblem)例1(生產(chǎn)計劃問題)：某工廠在計劃期內(nèi)要安排A、B兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品的利潤與所需的勞力、設(shè)備臺時及原材料消耗，如下：問：如何安排生產(chǎn)使該廠獲利最大？產(chǎn)品A產(chǎn)品B資源限額勞動力設(shè)備原材料9434510360工時200臺時300公斤單位產(chǎn)品利潤70120產(chǎn)品單耗資源ProductionPlanningProblem4ABLaborsMachineryMaterials9hours4hours4h5h3kg10kgx1x2availabletime360hoursavailabletime200hoursavailablerawmats.300kgFormulationProcessTypically,thereare4basicelementsintheformulationprocessofanydecision-makingproblem.0)Identifytheparameters,coefficientsandRHS1)Decisionvariables2)Objectivefunction3)Constraints5FormulationProcessStep0.Identifytheparameters6產(chǎn)品A產(chǎn)品B資源限額勞動力設(shè)備原材料9434510360工時200臺時300公斤單位產(chǎn)品利潤70120產(chǎn)品單耗資源7FormulationProcess建立問題的線性規(guī)劃模型確定決策變量—要決定的未知量設(shè)x1,x2分別表示A、B兩種產(chǎn)品的產(chǎn)量確定目標函數(shù)—決策者追求的目標maxz=70x1+120x2確定約束條件—決策變量的等式或不等式來表示勞動力限制：9x1+4x2

360設(shè)備限制：4x1+5x2

200原材料限制：3x1+10x2

300變量非負約束：x1

0，x2

08FormulationProcessMathematicalModel目標函數(shù)約束條件

maxz=70x1+120x29x1＋4x2

3604x1+5x2

2003x1+10x2

300x1,x2≥0決策變量s.t.AsnapshotofLPAllthemathfunctionsarelinearfunctions.Allocatinglimitedresources…amongcompetingactivitiesinabestpossiblewaybychoosingthelevelsofthoseactivitiesMostcommonapplicationsProductionPlanning,PortfolioselectionShippingpatterns…9101.線性規(guī)劃問題在一組線性等式或不等式的約束之下，求一個線性函數(shù)的最大值或最小值問題，這類問題稱為線性規(guī)劃問題。線性規(guī)劃(LP,LinearProgramming)11max(min)z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

(=,

)b1

a21x1+a22x2+…+a2nxn

(=,

)b2

….

am1x1+am2x2+…+amnxn

(=,

)bm

xj

(

)0,j=1,2,…,n2.LinearProgrammingModelGeneralforms.t.目標函數(shù)約束條件2.LinearProgrammingModelm:#of

resources. n:#of

activities. Z=measureofperformance.xj=adecisionvariablethatindicateshowmuchyouaredoingofactivityjforj=1,2,…,n.cj

=increaseinZthatwouldresultfromeachunitincreaseinlevelofeachactivityj.bi=theamountofresourceithatisavailableforallocationtoactivitiesfori=1,2,…,m.aij=amountofres.iconsumedbyeachunitofactivityj.122.LinearProgrammingModelDataneededforaLPmodelinvolvingtheallocationofresourcestoactivities13142.線性規(guī)劃數(shù)學模型Standardformmaxz=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2

….

am1x1+am2x2+…+amnxn

=bm

xj

0,j=1,2,…,n

bi

0,i=1,2,…,ms.t.目標函數(shù)極大化約束為等式變量非負右端常數(shù)非負152.線性規(guī)劃數(shù)學模型Simplifiedform162.線性規(guī)劃數(shù)學模型Vectorform172.線性規(guī)劃數(shù)學模型Matrixform一般稱C為價值向量，b為資源向量，A為技術(shù)系數(shù)矩陣18如何將LP一般形式化為標準型？目標函數(shù)的轉(zhuǎn)化max

z=-min(-z)0z-zx19如何將LP一般形式化為標準型？ModelconstraintstransformationIftheconstraintsare

“

”inequality,thenaddanewvariablexn+i,calledaslackvariable,totheleftsideofeachconstraintIftheconstraintsare

“

”inequality,thensubtractanewvariablexn+i,calledasurplusvariable,totheleftsideofeachconstraint∑aijxj

bi

→∑aijxj+xn+i=bi∑aijxj

bi

→∑aijxj-xn+i=bi20如何將LP一般形式化為標準型？VariablesTransformation若變量xk

0，令x’k=-xk若變量xk無限制(正和負都可以)，則引進兩個非負變量xk1，xk2

0，令xk=xk1-xk2若約束條件右面的某一常數(shù)項bi<0，這時只要在bi相對應的約束方程兩邊乘上-1AnyformofLPcanbetransformedintoStandardLP.21例將下列問題化成標準型:minz=-x1+2x2-3x3x1+x2+x3

7

x1-x2+x3

2-3x1+x2+2x3=5

x1,x2

0,x3無限制s.t.解：對自由變量x3

，用x31-

x32代替，對于第一個不等式約束添加松弛變量x4，對于第二個不等式約束減去剩余變量x5

，再用z=-z代替原來的目標函數(shù)。轉(zhuǎn)化結(jié)果maxz=x1-2x2+3x31-3x32

x1+x2+x31-x32+x4=7

x1-x2+x31-x32-x5=2-3x1+x2+2x31-2x32=5

x1,x2,x31,x32,x4,x5

0s.t.22課堂練習s.t.maxz=2x1+2x2-4x3x1+3x2-3x3

30x1+2x2-4x3

80x1,x2

0,x3無限制化下列線性規(guī)劃為標準型maxz=2x1+2x2-4x31+4x32x1+3x2-3x31+3x32-x4=30x1+2x2-4x31+4x32+x5=80x1,x2,x31,x32,x4,x5

0結(jié)果s.t.23Terminology可行解(Feasiblesolution)：滿足約束條件的一組決策變量值?？尚薪饧?可行域Feasibleregion)：所有可行解構(gòu)成的集合即為可行解集。最優(yōu)解(Optimalsolution)：使目標函數(shù)取得最大值（或最小值）的可行解。24AssumptionsofLPProblems比例性假定：決策變量變化引起的目標函數(shù)的改變量和決策變量的改變量成比例，每個決策變量的變化引起約束方程左端值的改變量和該變量的改變量也成比例。可加性假定：每個決策變量對目標函數(shù)和約束方程的影響獨立于其他變量的，目標函數(shù)值是每個決策變量對目標函數(shù)貢獻的總和連續(xù)性假定：線性規(guī)劃問題中的決策變量可取連續(xù)值；確定性假定：線性規(guī)劃問題中的所有參數(shù)都是確定的參數(shù)。線性規(guī)劃問題不包含隨機因素。253.GraphicalSolutionsofLPModel例1的數(shù)學模型：

maxz=70x1+120x2s.t.9x1+4x2

3604x1+5x2

2003x1+10x2

300x1,x2

026滿足9x1＋4x2

360和x1,x2

0的區(qū)域90400x1x22790400x1x240滿足9x1＋4x2

3604x1＋5x2

200和x1,x2

0的區(qū)域2890400x1x2滿足9x1＋4x2

3604x1＋5x2

200和3x1+10x2

300x1,x2

0的區(qū)域401002990400x1x240100可行域ABCDcorner-pointextremepoint/vertex3090400x1x240100目標函數(shù)表現(xiàn)為一簇以z為參數(shù)的平行線,令z=0,0=70x1+120x2,據(jù)(0,0),(10,-35/6)，利用兩點法可畫出第一條直線。z=70x1+120x2ABCDParallellinesdifferentZvalues3190400x1x240100當平行線與B(20,24)點相交時z值最大z=70×20+120×24=4280z=70x1+120x2BACDSummaryoftheGraphicalMethodDrawtheconstraintboundarylineforeachconstraint.Usetheorigin(oranypointnotontheline)todeterminewhichsideofthelineispermittedbytheconstraint.Findthefeasibleregionbydeterminingwhereallconstraintsaresatisfiedsimultaneously.Determinetheslopeofoneobjectivefunctionline.Allotherobjectivefunctionlineswillhavethesameslope.Moveastraightedgewiththisslopethroughthefeasibleregioninthedirectionofimprovingvaluesoftheobjectivefunction.Stopatthelastinstantthatthestraightedgestillpassesthroughapointinthefeasibleregion.Theoptimalsolutionpointisthelastpointtheobjectivefunctiontouchesasitleavesthefeasibleregion.32QuestionsHowtofindfeasibleregionandsolutionsforathree-variableLPproblem33manualworkImpossibleMorethan3variables34無窮多組最優(yōu)解例如：maxz=40x1+30x2

s.t.4x1+3x2

1202x1+x2

50x1,x2

0504030201010203040x1可行域目標函數(shù)是同約束條件：4x1+3x2

120平行的直線x2=

Z/30-（4/3）x1ABCA(0,40),B(15,20)令x(1)=(0,40),x(2)=(15,20)x=αx(1)+(1-α)x(2)(0

α

1)maxz=1200Multipleoptimalsolutions35無界解

Unbounded/nooptimalsolutions例：maxz=x1+x2

s.t.-2x1+x2

40x1-x2

20x1,x2

0可行域該可行域無界，目標函數(shù)值可增加到無窮大，稱這種情況為無界解或無最優(yōu)解。x1x236無可行解(nofeasiblesolutions)例：maxz=2x1+3x2

s.t.x1+2x2

8x1

4x2

3-2x1+x2

4x1,x2

0該問題可行域為空集，即無可行解，也不存在最優(yōu)解37兩個結(jié)論滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實可以推廣到更多變量的場合。最優(yōu)解必定能在凸多邊形的某一個頂點上取得，這一事實也可以推廣到更多變量的場合38關(guān)于解的情況唯一最優(yōu)解（如上例）無窮多組最優(yōu)解無界解無可行解394.線性規(guī)劃問題解的性質(zhì)考慮標準形式的LP問題X∈Rn,C∈Rn,b∈Rm,A∈Rm×n可行解:滿足約束條件的點X=(x1,x2,…,xn)T最優(yōu)解:使目標函數(shù)值達到最大的可行解40關(guān)于標準LP問題的幾個概念基(basic)基向量(basicvector)基變量、非基變量(basicvariable,non-basicvariable基解(basicsolution)基可行解(basicfeasiblesolution)可行基(feasiblebasis)41AX=b,秩(A)=m,m<n,至少有一個m階子式行列式值不能于0。a11…a1m

a1m+1

…a1na21…a2m

a2m+1…a2n………….…….am1…amm

amm+1…amnP1…PmBPm+1…PnN

設(shè)B是A的m階非奇異的子矩陣（det(B)≠0),則稱矩陣B為線性規(guī)劃問題的一個基

矩陣B=(P1,

…,Pm),其列向量Pj

稱為對應基B的基向量

矩陣N=(Pm+1,

…,Pn),其列向量Pj

稱為對應基N的非基向量42A=(P1…Pm

Pm+1…Pn)=(BN)基向量非基向量X=(x1…xm

xm+1…xn)T=(XBXN)T基變量非基變量43

例如：maxz=70x1+120x2s.t.9x1+4x2+

x3=3604x1+5x2+

x4=2003x1+10x2+x5=300x1,…,x5

0三個向量線性無關(guān)是一個基基向量決策變量x3,x4,x5即為基B對應的基變量，而x1,x2則為與基B對應的非基變量44注意：系數(shù)矩陣的基并不是唯一的。例如：45AX=b

的求解AX=b(BN)XBXN=bB-1BXB+B-1NXN=B-1b=>XB=B-1b-B-1NXN=>BXB+NXN=b令XN=0XB=B-1bXN=0X=B-1b0基解若B-1b

0，則X

0X基可行解B

可行基顯然，基解數(shù)目最大為個，而基可行解數(shù)不會超過基解數(shù)。即基可行解數(shù)一定是有限的.46基解、基可行解、可行基對于某一特定的基B，非基變量取0值的解，稱為基解滿足非負約束條件的基本解，稱為基可行解與基可行解對應的基，稱為可行基47例如：對于前例，對于基令非基變量x1,x2=0得到一基解X(0)＝（0，0，360，200，300），且它是基可行解，因而B是可行基而對基令非基變量x1,x3=0對應的基解X(0)＝（0，90，0，－250，－600）則不是基可行解，因而B不是可行基484.線性規(guī)劃問題解的性質(zhì)凸集(convexset)

設(shè)K是n維線性空間Rn的一個點集，若K中的任意兩點X(1),X(2)的連線上的一切點X仍在K中，則稱K為凸集。即：若K中的任意兩點X(1),X(2)