运筹基础课程 3

1Lecture3

SimplexMethod湖南大学工商管理学院主讲：E-mail:

2LectureOutlineSimplexmethodFurtherdiscussionsProgrammingofSimplexApplicationsGeorgeBernardDantzig(8Nov1914–13May2005)InventorofsimplexmethodPreliminaryCornerpointfeasiblesolution(CPFsolution)–intersectionofn(ormore;n-numberofvariables)constraintboundaries;

CPFsolutionsarecommonlyreferredtoasextremepoints(orvertices)AdjacencyForanyLPwithndecisionvariablestwoCPFsolutionsareadjacenttoeachotheriftheyshare(n-1)constraintboundariesEdgeEdgeoffeasibleregion–intersectionofthe(n-1)constraintboundariessharedbytwoadjacentCPFsolutions3Terms4Corner-pointsolutionsConstraintboundary

theboundaryimpliedbyaconstraintintersectionoftheconstraintboundariesEdge5(0,1,1)(1,1,0)(1,0,1)x1x2x3(1,1,1)Solutionofx1=1x2=1x3=1three-dimensionalcase61.Simplexmethod——Basicidea由于线性规划问题的最优解必定会在顶点达到，而顶点（基可行解）又是有限的。单纯型法的基本思想正是在有限的基可行解中寻找最优解HowtodetermineifaCPFisoptimal?7Z=12Z=27x1=4,x2=0isnotoptimalConsiderCPFsolution(4,0)Isitoptimal?HowtodetermineifaCPFisoptimal?8Z=36Z=27isx1=2,x2=6optimal?Z=30NowconsiderCPFsolution(2,6)Isitoptimal?Whichdirectionisbetter?9Startfromhere…ObservationsWeonlyconsiderCPFsolutionsWecandeterminetheoptimalitybycheckingtheadjacentCPFsolutionsIfaCPFsolutionisnotoptimal,wemovealongtheedgetoreachabetterCPFsolution10Geometricinterpretationofthesimplexmethod11Step0(Initialization)ChoosetheoriginastheinitialCPFsolutionStep

1IfcurrentCPFsolutionisoptimal(nobetteradjacentCPFsolutions),stop.Step2Otherwise,consideralladjacentCPFsolutions.SelecttheonethatincreasesZatafastestrate.ReturntoStep1.Summarizetheproceduretofindoptimalsolutionasfollows:Geometricinterpretationofthesimplexmethod12InitialCPFsol.Optimal?(optimalitytest)EndFindabettersol.alongtheedge(anotheriteration)NYe1e3e4e5e2012Geometricinterpretationofthesimplexmethod130Initialization,choosex=(0,0)asinitialsolutionZ=3x1+5x2=0Reason?1Movealongedgee1,ComputeadjacentCPF:x=(0,6),Z=3x1+5x2=30Whymovealonge1

insteadofe5?optimal2Movealonge2,computeadjacentCPF:x=(2,6), Z=3x1+5x2=36Fromgeometrytoalgebra…

Chapter2.3.2Page17.151.单纯形法——求解过程YNIterativeloop找出一初始基及其可行解判断基可行解是否为最优解转换可行基使目标函数有所改进，并求出相应的基可行解停止找出一初始基及其可行解转换可行基使目标函数有所改进，并求出相应的基可行解停止161.单纯形法——三个问题如何得到初始可行基？如何判断当前基可行解是否达到最优？如何转换到另一个基可行解？17如何判断达到最优？

设已找到SLP的一个可行基B,不妨就设其由矩阵A的前m列组成，将该基变为单位向量后，其形式为(典式)：典式：指系数阵含有一个m阶单位阵，且右端项非负x1+a’1,m+1xm+1+…+a’1,nxn

=b’1

x2+a’2,m+1xm+1+…+a’2,nxn

=b’2

xm+a’m,m+1xm+1+…+a’m,nxn

=b’m…18可得代入目标函数,可得σj(检验数)显然基变量对应的检验数σj=0(j=1,…,m)19显见,若所有非基变量σj

0(j=m+1,…,n)时,则对应的基可行解为最优解(最优解判别准则)。z=z0+∑σjxj

=z0+σm+1xm+1+σm+2xm+2+…+σnxn特别的，若其中某个σk=0，则有无穷多最优解。如何判断达到最优？20若存在σk>0,考虑xk由0增加到θ,其它非基变量仍保持为0,显然目标函数值:z=z0+σkθ

——随着θ的增大,目标函数值越大考虑对应变量系数(1)若则xi=b’i-θa’ik

0,因而对应可行解由于θ越大,目标值越大，而对应的解又都可行，因而具有无界解如何转换到另一个基可行解？选σk

=max{σj|σj>0}21(2)若P’k有正分量为了保证解可行，需xi=b’i-θa’ik

0因而θ最大只能取

设选xk为入基变量，xl为出基变量(称为θ

规则)使用初等行变换将主元变为从而实现xk入基，xl出基22基变换(旋转变换)23线性规划解的判别定理判别定理1：设X为线性规划的一个基可行解，且对所有j有σj

0,则X为线性规划的最优解.判别定理2：设X为线性规划的一个基可行解，且对所有j有σj

0,同时有某个非基变量的检验数σk＝0，则该线性规划有无穷多最优解.判别定理3：设X为线性规划的一个基可行解，若存在σk>0,且pk

0，则该线性规划问题具有无界解（无最优解）24单纯形表(SimplexTableau)25maxz=3x1-3x2+5x4-x5x1-2x3+2x4=12

x2-2x3=1

-4x3+3x4+x5=27x1,…,x5

0Cj3-305-1bθCBXBX1X2X3X4X5

10-22001-20000-431z6例X1X2X53-3-100-420主元12127进基变量出基变量s.t.26Cj3-305-1bθCBXBX1X2X3X4X5

-3-1X2x51/20-11001-20000-4316127z旋转变换——迭代计算(1)27Cj3-305-1bθCBXBX1X2X3X4X5

-3-1X2X51/20-11001-200-3/20-101619旋转变换——迭代计算(2)5X428全小于等于0计算系数Cj3-305-1bθCBXBX1X2X3X4X5

5-3-1X4X2X51/20-11001-200-3/20-101619z-10-20018最优值29用单纯形法求解下例

maxz=70x1+120x29x1＋4x2

3604x1+5x2

2003x1+10x2

300x1,x2

0s.t.

maxz=70x1+120x29x1+4x2+x3=

3604x1+5x2+x4

=

2003x1+10x2+x5

=

300x1,…,x5

0s.t.化为标准型30取松弛变量x3,x4,x5为基变量Cj70120000bθCBXBX1X2X3X4X5

000X3X4X59410045010310001360200300z70120000360/4=90200/5=40300/10=30Tab.131Tab.2Cj70120000bθCBXBX1X2X3X4X5

00120X3X4X27.8010-0.42.5001-0.50.31000.12405030z34000-12360030.762010032Tab.3Cj70120000bθCBXBX1X2X3X4X5

070120X3X1X2001-3.121.161000.4-0.2010-0.120.16842024z000-13.6-5.242803390400x1x240100可行域ABCD表1表2表3单纯形表——矩阵运算34ConsideringthecorrespondingfeasiblebasicinTab.3单纯形表计算小结35(1)将问题化为标准型,找出初始可行基,建立初始单纯形表;(2)计算检验数，若各检验数σj≤0,则已得到最优解,可停止计算;否则进入(3)；(3)若存在σk>0,且相应的列P’k≤0,则问题无界,停止计算;否则进入(4)；(4)据max{σj|σj>0}=σk,确定xk

为入基变量,相应的列为主元列；计算θ=min{bi/a’ik|a’ik>0}=b’l/a’lk,以确定出基变量xl,相应的行为主元行,主元列与主元行的交a’lk为主元,进入(5);(5)进行旋转变换,把xk

所对应的列变换为单位列向量(主元a’lk变为1)。单纯形表计算小结(续)36旋转变换具体运算如下：①把主元行除以主元a’lk得到新表最先行(新表xk

所在行);②对于i≠l,新表第i行=旧表第i行-

a’ik

×(新表最先行)其中a’ik

是旧表第i行与主元列的交。将XB列中的xl换为xk,得到新的单纯形表，转回(2)。372.单纯形法的进一步讨论如何得到初始可行基？人工变量法：人为添加几个非负变量构成m阶单位矩阵大M法 目标函数人工变量的价值系数赋为-M

(M为非常大的正数)两阶段法第一阶段：构造一辅助线性规划问题，其目标函数为人工变量之和最小第二阶段：以第一阶段的解为初始基可行解38大M法的例子用大M法求解下列线性规划minz=-3x1+x2+x3s.t.x1-2x2+x3

11-4x1+x2+2x3

3-2x1+x3=1x1,x2,x3

039化成标准型maxz’=3x1-x2-x3s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1,x2,x3,x4,x5

0没有现成的m阶单位矩阵，引入人工变量x6,x7maxz’=3x1-x2-x3-Mx6-Mx7s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1,x2,x3,x4,x5,x6,x7

040CjbθCBXB0-M-MX4X6X71131z3-6M-1+M-1+3M0-M00X1X2X3X4X5

X6X71-211000-4120-110-20100013-1-100-M-M检验数大于0大M法的例子41113/21CjbθCBXB0-M-MX4X6X71131z-4M3-6M-1+M-1+3M0-M00X1X2X3X4X5

X6X71-211000-4120-110-20100013-1-100-M-M大M法的例子42大M法的例子-1-CjbθCBXB0-M-1X4X6X31011zM+11-1+M00-M0-3M+1X1X2X3X4X5

X6X73-20100-10100-11-2-20100013-1-100-M-M旋转变换并替换新的基变量，得到新的单纯形表43大M法的例子4--CjbθCBXB0-1-1X4X2X31211zM+11000-1-M+1-M-1X1X2X3X4X5

X6X73001-20-50100-11-2-20100013-1-100-M-M旋转变换并替换新的基变量，得到新的单纯形表44大M法的例子CjbθCBXB3-1-1X1X2X3419z2000-1/3-1/3-M+1/3-M+2/3X1X2X3X4X5

X6X71001/3-2/30-5/30100-11-20012/3-4/30-7/33-1-100-M-M旋转变换并替换新的基变量，得到新的单纯形表全小于等于0基变量不含M45两阶段法的例子maxw’=-x6-x7(minw=x6＋x7)s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1,x2,x3,x4,x5,x6,x7

0上例，引入人工变量后第一阶段：求以下辅助问题46第一阶段113/21CjbθCBXB0-1-1X4X6X71131w-4-6130100X1X2X3X4X5

X6X71-211000-4120-110-201000100000-1-147第一阶段-1-CjbθCBXB0-10X4X6X31011w-10100-10-3X1X2X3X4X5

X6X73-20100-10100-11-2-201000100000-1-148第一阶段CjbθCBXB000X4X2X31211w000000-1-1X1X2X3X4X5

X6X73001-22-50100-11-2-201000100000-1-1w=0删除49第二阶段CjbθCBXB0-1-1X4X2X31211z-21000-1X1X2X3X4X5

3001-20100-1-201003-1-1004--50第二阶段CjbθCBXB3-1-1X1X2X3419z2000-1/3-1/3X1X2X3X4X5

1001/3-2/30100-10012/3-4/33-1-10051StopIfallσj≤0Multipleoptimalsols.UnboundedNofeasiblesol.Onlyanoptimalsol.ListthenewsimplextableauReplacebasicvarxl

withnonbasicxkFind

σk=max{σj|

σj>0}

Computeσj=cj-zj

AYNNNIterativeLoopIfthereareartfcl.

varsinbasicvarsYIfσk>0&aik≤0

NYIfthereisσj=0forsomenonbasicvarsYCompute52输入：变量个数n，约束条件个数m，选择目标函数类型;约束方程组系数矩阵A，操作符，目标函数系数开始调整：目标函数为max；限定限量b为非负加入松弛变量Xs,使得AX+Xs=b,并列出初始表令：A¹=（A,I）；C¹=（C,0）；

b¹=b；单纯形法程序流程图如下:存在σ¹j>0是选择主元素列k存在a¹ik>0是选择主元素行lθ=min{|a¹ik>0}换元后计算各行新的系数1、a¹lj

=；

2、a¹ij=a¹ij–a¹ik*a¹lj

σ¹j=c¹j–c¹s*a¹lj

输出最优解和最优值否否无有界优解结束53使用软件OR求解线性规划544.线性规划应用举例例1(人力资源分配的问题)．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?55解：设xi

表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：minx1+x2+x3+x4+x5+x6

约束条件：s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥056

例2:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？线性规划应用举例57解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5

分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下的数学模型。目标函数：Max15x1+10x2+7x3+13x4+9x5

约束条件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥058线性规划应用举例例、某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？59假设x1,x2,x3,x4,x5分别为上面前5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5

约束条件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0解：设计下列8种下料方案60线性规划应用举例例（投资问题）某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；据测定每万元每次投资的风险指数如下表,问：

(a)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？

(b)应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？61

解：1）确定决策变量：连续投资问题设xij(i=1-5，j=1、2、3、4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42C