运筹基础课程 10

1Lecture2

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

2LectureOutlineLinearProgrammingProblemLinearProgrammingModelGraphicalSolutionsofLPModelCharacteristicsofLPProblems31.线性规划问题(LPProblem)例1(生产计划问题)：某工厂在计划期内要安排A、B两种产品的生产，已知生产单位产品的利润与所需的劳力、设备台时及原材料消耗，如下：问：如何安排生产使该厂获利最大？产品A产品B资源限额劳动力设备原材料9434510360工时200台时300公斤单位产品利润70120产品单耗资源ProductionPlanningProblem4ABLaborsMachineryMaterials9hours4hours4h5h3kg10kgx1x2availabletime360hoursavailabletime200hoursavailablerawmats.300kgFormulationProcessTypically,thereare4basicelementsintheformulationprocessofanydecision-makingproblem.0)Identifytheparameters,coefficientsandRHS1)Decisionvariables2)Objectivefunction3)Constraints5FormulationProcessStep0.Identifytheparameters6产品A产品B资源限额劳动力设备原材料9434510360工时200台时300公斤单位产品利润70120产品单耗资源7FormulationProcess建立问题的线性规划模型确定决策变量—要决定的未知量设x1,x2分别表示A、B两种产品的产量确定目标函数—决策者追求的目标maxz=70x1+120x2确定约束条件—决策变量的等式或不等式来表示劳动力限制：9x1+4x2

360设备限制：4x1+5x2

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

300变量非负约束：x1

0，x2

08FormulationProcessMathematicalModel目标函数约束条件

maxz=70x1+120x29x1＋4x2

3604x1+5x2

2003x1+10x2

300x1,x2≥0决策变量s.t.AsnapshotofLPAllthemathfunctionsarelinearfunctions.Allocatinglimitedresources…amongcompetingactivitiesinabestpossiblewaybychoosingthelevelsofthoseactivitiesMostcommonapplicationsProductionPlanning,PortfolioselectionShippingpatterns…9101.线性规划问题在一组线性等式或不等式的约束之下，求一个线性函数的最大值或最小值问题，这类问题称为线性规划问题。线性规划(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.目标函数约束条件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.线性规划数学模型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.目标函数极大化约束为等式变量非负右端常数非负152.线性规划数学模型Simplifiedform162.线性规划数学模型Vectorform172.线性规划数学模型Matrixform一般称C为价值向量，b为资源向量，A为技术系数矩阵18如何将LP一般形式化为标准型？目标函数的转化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若约束条件右面的某一常数项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代替原来的目标函数。转化结果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无限制化下列线性规划为标准型maxz=2x1+2x2-4x31+4x32x1+3x2-3x31+3x32-x4=30x1+2x2-4x31+4x32+x5=80x1,x2,x31,x32,x4,x5

0结果s.t.23Terminology可行解(Feasiblesolution)：满足约束条件的一组决策变量值。可行解集(可行域Feasibleregion)：所有可行解构成的集合即为可行解集。最优解(Optimalsolution)：使目标函数取得最大值（或最小值）的可行解。24AssumptionsofLPProblems比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量也成比例。可加性假定：每个决策变量对目标函数和约束方程的影响独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和连续性假定：线性规划问题中的决策变量可取连续值；确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。253.GraphicalSolutionsofLPModel例1的数学模型：

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

3604x1+5x2

2003x1+10x2

300x1,x2

026满足9x1＋4x2

360和x1,x2

0的区域90400x1x22790400x1x240满足9x1＋4x2

3604x1＋5x2

200和x1,x2

0的区域2890400x1x2满足9x1＋4x2

3604x1＋5x2

200和3x1+10x2

300x1,x2

0的区域401002990400x1x240100可行域ABCDcorner-pointextremepoint/vertex3090400x1x240100目标函数表现为一簇以z为参数的平行线,令z=0,0=70x1+120x2,据(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无穷多组最优解例如：maxz=40x1+30x2

s.t.4x1+3x2

1202x1+x2

50x1,x2

0504030201010203040x1可行域目标函数是同约束条件：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可行域该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。x1x236无可行解(nofeasiblesolutions)例：maxz=2x1+3x2

s.t.x1+2x2

8x1

4x2

3-2x1+x2

4x1,x2

0该问题可行域为空集，即无可行解，也不存在最优解37两个结论满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合38关于解的情况唯一最优解（如上例）无穷多组最优解无界解无可行解394.线性规划问题解的性质考虑标准形式的LP问题X∈Rn,C∈Rn,b∈Rm,A∈Rm×n可行解:满足约束条件的点X=(x1,x2,…,xn)T最优解:使目标函数值达到最大的可行解40关于标准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

设B是A的m阶非奇异的子矩阵（det(B)≠0),则称矩阵B为线性规划问题的一个基

矩阵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三个向量线性无关是一个基基向量决策变量x3,x4,x5即为基B对应的基变量，而x1,x2则为与基B对应的非基变量44注意：系数矩阵的基并不是唯一的。例如：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

可行基显然，基解数目最大为个，而基可行解数不会超过基解数。即基可行解数一定是有限的.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.线性规划问题解的性质凸集(convexset)

设K是n维线性空间Rn的一个点集，若K中的任意两点X(1),X(2)的连线上的一切点X仍在K中，则称K为凸集。即：若K中的任意两点X(1),X(2)