第一章线性规划12-2-19

1、第一章第一章 线性规划及单纯形法线性规划及单纯形法 Linear Programming (LP)Linear Programming (LP)北京物资学院运筹学教学课件北京物资学院运筹学教学课件北京物资学院信息学院北京物资学院信息学院 第一节第一节 线性规划问题的数学模型线性规划问题的数学模型第二节第二节 两变量线性规划问题的图解法两变量线性规划问题的图解法第三节第三节 单纯形法的原理单纯形法的原理第四节第四节 单纯形法的计算步骤单纯形法的计算步骤第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论第六节第六节 线性规划应用举例线性规划应用举例本章内容本章内容第一节第一节 线性规划问题的数

2、学模型线性规划问题的数学模型线性规划是运筹学中研究较早、发展较快、应用较广、线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。资源的数学方法。线性规划研究的问题线性规划研究的问题：极大化问题：面对一定的资源，要求充分利用，极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。以获得最大的经济效益。极小化问题：给定一项任务，要求统筹安排，尽极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务量做到用最少的人力、物力资源去完成这一任务。一、实例：一、实

3、例： 生产安排问题生产安排问题 运输问题运输问题二、线性规划问题的结构特征二、线性规划问题的结构特征 线性规划问题的特征线性规划问题的特征 线性规划问题的一般形式线性规划问题的一般形式 线性规划问题的标准形式线性规划问题的标准形式 一般形式向标准形式的转化一般形式向标准形式的转化本节内容安排本节内容安排一、实例一、实例例例1 1 生产安排问题生产安排问题 某工厂拥有某工厂拥有A A、B B、C C三种类型的设备，生产甲、乙两种产三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时

4、数如下表所示：可以获得的利润以及三种设备可利用的时数如下表所示： 产品甲产品甲产品乙产品乙设备时数设备时数设备设备A A3 32 26565设备设备B B2 21 14 40 0设备设备C C0 03 37575利润（元利润（元/ /件）件）1500150025002500 问题：工厂应如何安排生产可获得最大的总利润？问题：工厂应如何安排生产可获得最大的总利润？可控因素：生产两种产品的数量，设分别为可控因素：生产两种产品的数量，设分别为x1 , x2，目标是生产利润最大，设生产利润为目标是生产利润最大，设生产利润为z. z. 利润函数为：利润函数为：1215002500zxx限制条件：三台设备

5、的使用时间不超过设备能力的限制条件：三台设备的使用时间不超过设备能力的限制限制设备设备A:A: 3 3x1 1+2+2x2 26565设备设备B:B: 2 2x1 1+ + x2 24040设备设备C:C: 3 3x2 27575蕴涵约束：产量为非负蕴涵约束：产量为非负 x1 0, x2 0目标函数目标函数约束条件约束条件121212212max1500250032652403750,0zxxxxxxxxx 设生产甲乙两种产品的数量分别为设生产甲乙两种产品的数量分别为x1, ,x2件件，总利总利润为润为z. .在处理产、供、销的经济活动中，会经常遇到在处理产、供、销的经济活动中，会经常遇到物资

6、调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、物资调拨的运输问题。如粮棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售化肥、木材等物资要由若干个产地调运到若干个销售地。问题是，怎样制定合理的调运方案才能使总运输地。问题是，怎样制定合理的调运方案才能使总运输费用最少？这类问题称为运输问题费用最少？这类问题称为运输问题例例2 2 运输问题运输问题 设要从甲地调出物资设要从甲地调出物资20002000吨，从乙地调出物资吨，从乙地调出物资600600吨，吨，从丙地调出物资从丙地调出物资500500吨，分别供应给吨，分别供应给A A地地17001700吨、吨、B B地地1100110

7、0吨、吨、C C地地200200吨、吨、D D地地100100吨。已知每吨运费如下表所吨。已知每吨运费如下表所示。示。假定运费与运量成正比例，问怎样才能找到一个总运假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？费最省的调拨计划？丙丙1726384315375151 乙乙1572521 甲甲D DC CB BA A销地销地产地产地单位：元单位：元 / / t tx22x11x12x13x21x23x31x32x33x14x24x34问题分析：问题分析： 可控因素：可控因素：从三个产地到四个销地的运输量；从三个产地到四个销地的运输量； 目标：目标： 总运费最省；总运费最省； 限制

8、条件：限制条件：各个产地的产量和销地的需求量的限制各个产地的产量和销地的需求量的限制 。用用 （i=1,2,3; =1,2,3; j=1,2,3,4=1,2,3,4）分别表示从甲乙丙三个产地运往分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。四个销地的物资数量。ijx则该问题的数学模型为则该问题的数学模型为111213142122232431323334min21257155151371543382617zxxxxxxxxxxxx 11121314212223243132333411213112223213233314243420006005001700. .1100200100

9、0,1,2,3;1,2,3,4ijxxxxxxxxxxxxxxxs txxxxxxxxxxij 简化表达式简化表达式34114131min1,2,3. .1,2,3,401,2,3;1,2,3,4ijijijijijijjiijzc xxais txbjxij 二、线性规划问题的结构特征：二、线性规划问题的结构特征：1 1. 线性规划问题的特征线性规划问题的特征；（1 1）都有一组决策变量。）都有一组决策变量。（2 2）都有一组线性的约束条件，它们是线性等式）都有一组线性的约束条件，它们是线性等式或不等式。或不等式。（3 3）都有一个确定的目标，这个目标可以表示成）都有一个确定的目标，这个目标

10、可以表示成决策变量的线性函数，根据问题不同，有的要求实决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。现极大化，有的要求实现极小化。线性规划问题的本质：研究在一组线性约束下，线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题一个线性函数的极值问题。所以称为线性规划所以称为线性规划 linear programming (LP)2. 2. 线性规划问题的一般形式线性规划问题的一般形式1122max(min).nnzc xc xc x 1111221121122222112212.( , ).( , ).( , ),.,0nnnnmmmnnmna xa xa

11、 xba xa xa xba xa xa xbx xx s.t（1）（2）（3）一般形式的简化表达一般形式的简化表达1( , )1,2,.,01,2,.,nijjijja xbimxjn 1max(min)njjjzc x 规范形式规范形式极大化问题极大化问题极小化问题极小化问题11221111221121122222112212min. .,.,0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xaxbs taxaxaxbxxx 11221111221121122222112212max. .,.,0nnnnnnmmmnnmnzc xc xc xa xa xa x

12、ba xa xaxbs taxaxaxbxxx 3. 3. 线性规划的标准形式线性规划的标准形式1maxnjjjzc x 10nijjijja xbx (1,2,.,)im (1,2,., )jn s.t.1122max.nnzc xc xc x 1111221121122222112212.,.,0nnnnmmmnnmna xa xa xba xa xa xba xa xa xbx xx s.t（1）（2）（3）标准形式的简化表达标准形式的简化表达标准形式的矩阵表达标准形式的矩阵表达max0ZCXAXbX mnmmnnaaaaaaaaaA.212222111211nxxxX21mbbbb21

13、ncccC21标准形式的向量表达标准形式的向量表达1max0njjjZCXP xbX 12jjjmjaaPa 标准形式的特点标准形式的特点：(1).目标函数极大化目标函数极大化(2).约束条件全部是等式约束条件全部是等式(3).所有的变量都是非负的所有的变量都是非负的(4).约束条件右端常数为非负的约束条件右端常数为非负的4. 4. 一般形式向标准形式的转化一般形式向标准形式的转化：(1) 目标函数极大化目标函数极大化对于极小化的目标函数对于极小化的目标函数 可以等价地转化成求可以等价地转化成求1njjjzc x 1()njjjzzc x 的极大化的极大化。(2) 不等式约束化等式约束不等式约

14、束化等式约束对于对于 形的不等式，可以在不等式的左边加上形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。变量称为松弛（剩余）变量。 ( ) 例如：例如：1nijjija xb 1nijjn iija xxb 1nijjija xb 1nijjn iija xxb (3) 自由变量化非负变量的自由变量化非负变量的差差自由变量可以用两个非负变量的差代替，例如对于自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量一个符号无限制的变量 ，可以引进两个非负变量，可以引进两个非负变量 并设

15、并设jx0,0jjxxjjjxxx(4) 约束条件右端的负常数化为正常数约束条件右端的负常数化为正常数对于右端常数为负数的约束，可以两端同时乘以对于右端常数为负数的约束，可以两端同时乘以-1-1。取值小于等于取值小于等于0的变量，可以用一个非负变量的相的变量，可以用一个非负变量的相反数表示。反数表示。例例 将下列将下列LPLP问题化成标准形式问题化成标准形式121212121min222250zxxxxxxxxx s.t.122122312241225122345max()2()22()2()5,0zxxxxxxxxxxxxxxxx xxxxx s.t.课堂练习：将下列课堂练习：将下列LP问题

16、化成标准形式问题化成标准形式12312312312312min232832532360,0zxxxxxxxxxxxxxx 123312334123351233123345max 2328322532336,0zxxxxxxxxxxxxxxxxxxxxxxxx 33311,zzxxxxx 解解：令令作业：作业：见公共邮箱见公共邮箱 bwu_ 密码：密码：123456第二节第二节 两变量线性规划问题的图解法两变量线性规划问题的图解法一、一、几个概念几个概念二、二、两变量两变量LPLP问题的图解法问题的图解法可行解可行解：任何一组满足所有约束条件的决策变量值：任何一组满足所有约束条件的决策变量值 称

17、为称为L LP P问题的一个可行解。问题的一个可行解。12,.,nxxx最优解最优解：使目标函数达到最大（小）值的可行解。：使目标函数达到最大（小）值的可行解。最优值最优值：最优解对应的目标函数值。：最优解对应的目标函数值。可行域可行域：所有可行解的集合称为可行域。：所有可行解的集合称为可行域。,0DX AXb X 一、几个概念一、几个概念：二、两变量二、两变量LP问题的图解法问题的图解法图解法是根据平面直角坐标系和二元一次方程图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。（不等式）的特点设计的。1. 1. 图解法的一般步骤图解法的一般步骤：（1 1） 建立直角坐标系，以建立

18、直角坐标系，以 为横轴，为横轴， 为纵轴。为纵轴。1x2x（2 2） 将约束条件在直角坐标系中表示，并找出可行域将约束条件在直角坐标系中表示，并找出可行域。（3 3）作出目标函数的等值线簇，找出目标函数值的增加）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。（或减小）方向，用箭头表示。（4 4）确定出问题的最优解。若为极大（小）化问题，）确定出问题的最优解。若为极大（小）化问题，目标函数沿增加（减小）方向平移，与可行域的最后目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。一个交点即为最优解。例例1 1 用图解法解下列线性规划问题用图解法解下列线性规划

19、问题1212122480326000 xxxxxx 12max6050zxx 最优解最优解 x*=(10,15)T, , 最优值最优值 z*=60 10+50 15=1350.0 1 0 20 30 4 0 1 0 2 0 3 0 x2 x1(1)(2)(10,15)可行域有界可行域有界, ,有唯一最优解有唯一最优解z =0z =600课堂练习：用图解法求课堂练习：用图解法求解下列解下列LP问题问题121212212max150025003265240. . 3750,0zxxxxxxs txxx x1x2 最优解为最优解为X=(5，25)T，最优值，最优值 70000。 例例2 2、1212

20、12212max2263212. . 20,0zxxxxxxs txxx 无穷多最优解无穷多最优解x1x2 12121212max22. .1,0 zxxxxs txxxx 例例3 3、无有限无有限最优解最优解x1x2 12121212min22. .1,0 zxxxxs txxx x 可行域无界可行域无界, 有唯一最优解有唯一最优解x1x2 例例4 4、12121212min32 1. . 236,0 zxxxxs txxx x x1x2 可行域为空可行域为空, 无可行解无可行解例例5 5、1212121212max232212284 16. . 4120,0zxxxxxxxs txxx 0

21、1 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4 2)课堂练习课堂练习:用图解法求解用图解法求解可行域是空集。可行域是空集。可行域存在，则一定是一个凸多边形可行域存在，则一定是一个凸多边形. .无无有限有限最优解（可行域一定无界）。最优解（可行域一定无界）。最优解存在且唯一，则一定在顶点上达到。最优解存在且唯一，则一定在顶点上达到。最优解存在且不唯一，一定存在一个顶点是最优解。最优解存在且不唯一，一定存在一个顶点是最优解。2. 2. 图解法求解两变量图解法求解两变量LPLP问题时可能出现的情况问题时可能出现的情况：3. 3. 两变量线性规划问题解的性质两变量线性规划问题解

22、的性质 1. 1. 两变量线性规划问题的可行域是若干个半平两变量线性规划问题的可行域是若干个半平面的交集，它是一个有界或无界的凸多边形，并面的交集，它是一个有界或无界的凸多边形，并且有有限个顶点。且有有限个顶点。2. 2. 对于给定的线性规划问题，如果它有最优解，对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。最优解总可以在可行域的某个顶点上达到。第三节第三节 单纯形法的原理单纯形法的原理一、一、可行区域的几何结构可行区域的几何结构二、二、基可行解及线性规划的基本定理基可行解及线性规划的基本定理三、三、单纯形法的原理单纯形法的原理单纯形方法（单纯形方法（Simpl

23、ex Method）是是G.B.Dantzing 在在1947年提出的。年提出的。 一、可行区域的几何结构一、可行区域的几何结构1.1. 基本假设基本假设2.2. 凸集及其性质凸集及其性质3.3. 可行域的凸性可行域的凸性4.4. 问题问题1. 1. 基本假设基本假设凸集凸集：设设S是是n维欧氏空间的一个点集，若任意两点维欧氏空间的一个点集，若任意两点X(1) S, X(2) S 的连线上的一切点的连线上的一切点 X(1)+ (1- )X(2) S, (0 1); 则称则称S为一个凸集。为一个凸集。性质性质：任意多个凸集的交集仍然是任意多个凸集的交集仍然是凸集凸集。2. 2. 凸集及性质凸集及

24、性质顶点顶点：设设S是凸集，是凸集，X S；若对任何若对任何X(1) S和和 X(2) S， X(1) X(2)，以及任何以及任何0 m)，其秩为其秩为m，B是是A中的一个中的一个m阶满秩子方阵，称阶满秩子方阵，称B是线性规划问题的一个基是线性规划问题的一个基。B中每一个列向量称为一个中每一个列向量称为一个基向量基向量，与基向量对应的变量称，与基向量对应的变量称为为基变量基变量。其余变量称为。其余变量称为非基变量非基变量。不失一般性，设不失一般性，设 11111.mmmmmaaBPPaa则则Pj（j=1，2m）是基向量，是基向量，xj（ j=1，2m ）是基变量。是基变量。 xj（ j=m+1

25、，n ）是非基变量。是非基变量。基解基解：在约束方程组中令所有的非基变量：在约束方程组中令所有的非基变量xm+1=x m+2=x n=0，得得11112211211222221122.mmmmmmmmmma xa xaxba xa xaxbaxaxaxb 此方程组有唯一解此方程组有唯一解XB=(x1，x2，xm)T，将这个解将这个解加上非基变量取加上非基变量取0的值有的值有X=(x1，x2，xm,0,0)T,称称X为线性规划问题的基解。为线性规划问题的基解。显然，基解中取非零值的变量个数不超过显然，基解中取非零值的变量个数不超过m，基解的总数不超过基解的总数不超过Cnm个。个。基可行解基可行解

26、：满足非负约束的基解称为基可行解。：满足非负约束的基解称为基可行解。可行基可行基：对应于基可行解的基。：对应于基可行解的基。可行解可行解基解基解基可行解基可行解用矩阵形式表示的基解用矩阵形式表示的基解考虑标准形式的线性规划问题：考虑标准形式的线性规划问题：max0zCXAXbX ( ,),BNXAB NXX令令111BNBXB NXB b 左左乘乘得得10,NBXXB b 令令得得10B bX 即即( ,),BBNNAXbXB NbBXNXbX 代代入入得得即即例如例如LPLP问题问题221004001005001A 1345100010001BPPP 2145200410001BPPP是它的

27、两个基，对应的基解分别为是它的两个基，对应的基解分别为12(0,0,12,16,15)(6,0,0, 8,15)TTXX 可见可见X1是基可行解，故是基可行解，故B1是可行基。而是可行基。而X2不是基可行不是基可行解，故解，故B2不是可行基。不是可行基。根据以上定义根据以上定义121231425max232212416. .5150,1,2,.,5jzxxxxxxxs txxxj 基基基解基解是否基可行解是否基可行解目标函数值目标函数值(x1, x2, x3, x4, x5)(P1,P2,P4)(3, 3, 0, 4, 0)是是15(P1,P2,P5)(4, 2, 0, 0, 5)是是14(P

28、2,P3,P4)(0, 3, 6, 16, 0)是是9(P1,P3,P5)(4, 0, 4, 0, 15)是是8(P3,P4,P5)(0, 0, 12, 16, 15)是是0(P1,P2,P3)(4, 3, -2, 0, 0)否否17(P1,P4,P5)(6, 0, 0, -8, 15)否否12(P2,P4,P5)(0, 6, 0, 16, -15)否否182. 2. 线性规划的基本定理线性规划的基本定理引理引理：LP问题的可行解问题的可行解X是基可行解的充要条件是它是基可行解的充要条件是它的正分量所对应的的正分量所对应的A中的列向量线性无关。中的列向量线性无关。定理定理2 2：线性规划问题的

29、基可行解对应可行域的顶：线性规划问题的基可行解对应可行域的顶点。（点。（X是基可行解是基可行解X是可行域的顶点）（基可是可行域的顶点）（基可行解个数有限）行解个数有限）定理定理3 3：一个一个LP问题，若有最优解，则一定存在一问题，若有最优解，则一定存在一个基可行解是最优解。个基可行解是最优解。3. 3. 问题问题1)1) 如何得到第一个基可行解？如何得到第一个基可行解？2)2) 如何判别一个基可行解是否最优？如何判别一个基可行解是否最优？3)3) 如果当前的基可行解不是最优，如何从一个如果当前的基可行解不是最优，如何从一个基可行解转化到另一个基可行解？基可行解转化到另一个基可行解？三、单纯形

30、法原理三、单纯形法原理1.确定初始基可行解确定初始基可行解2.最优性检验和解的判别最优性检验和解的判别3.基可行解的改进基可行解的改进情况情况1 1 约束条件全部是约束条件全部是“ ”型不等式且右端常数非负型不等式且右端常数非负（化成标准形后，约束条件系数矩阵含有单位子矩阵）（化成标准形后，约束条件系数矩阵含有单位子矩阵）加上松弛变量，化为标准形式：加上松弛变量，化为标准形式： 1. 1. 确定初始基可行解确定初始基可行解11max 1,2,. .0 1,2,.njjjnijjijjzc xa xbims txjn 111max0 1,2,. .0 1,2,. ,1,.nmjjn ijinij

31、jn iijjzc xxa xxbims txjn nnm 111max0 1,2,. .0 1,2,. ,1,.nmjjn ijinijjn iijjzc xxa xxbims txjn nnm 其约束条件系数矩阵为其约束条件系数矩阵为111212122212.10.0.01.0.00.1nnmmmnaaaaaaaaa令其中的单位矩阵作为基，可得初始基可行解令其中的单位矩阵作为基，可得初始基可行解12(0,0,.0,.,)TmXb bb 考虑标准形式的考虑标准形式的LP问题问题假设可行域非空，假设可行域非空， A为一为一 m n实矩阵，实矩阵，r(A)=m 0，而，而 ij 0，则原问，则原

32、问题无界；题无界； 如果某个非基变量的检验数如果某个非基变量的检验数 j 0，且至少存在一个，且至少存在一个i，使得使得 ij 0，则可以找到一个新的基可行解，则可以找到一个新的基可行解X1，使得，使得CX1CX。3. 3. 基可行解的改进基可行解的改进1) 1) 基的修改：基的修改：进基变量、出基变量的选取准则。进基变量、出基变量的选取准则。2) 2) 迭代：迭代：得到新基对应的典式。得到新基对应的典式。基的修改准则：新基与原有基有基的修改准则：新基与原有基有m-1 个相同的基个相同的基变量，只有一个基变量不同。变量，只有一个基变量不同。进基变量进基变量：从非基变量变为基变量的变量：从非基变

33、量变为基变量的变量。出基变量出基变量：由基变量变为非基变量的变量。：由基变量变为非基变量的变量。1) 1) 进基变量的选取原则进基变量的选取原则：最优性原则最优性原则：若：若 k 0,则与则与 k 相对应的变量相对应的变量xk 是非基是非基变量，当变量，当xk 变为基变量时，它的值由变为基变量时，它的值由0变为正数，比变为正数，比如说如说xk= 0，其余的非基变量仍取值为零。由其余的非基变量仍取值为零。由(3.4)式知，对应新解的目标函数值为式知，对应新解的目标函数值为z=z0+ K z0，显显然然 越大目标函数值越大越大目标函数值越大。可行性原则（最小比值原则）可行性原则（最小比值原则）：

34、的取值应保的取值应保证新解仍然是基可行解。证新解仍然是基可行解。2)2) 出基变量的选取原则出基变量的选取原则进基变量和出基变量的选取准则进基变量和出基变量的选取准则例例:求解下列线性规划问题求解下列线性规划问题12121224803260. .00 xxxxs txx 12max6050zxx O 1 0 20 30 4 0 1 0 2 0 3 0 x2 x1(1)(2)B (10,15)AC121231241234max60502480. . 3260,0zxxxxxs txxxxxxx 化成标准形式（典式）化成标准形式（典式）约束条件系数矩阵含单位矩阵；约束条件系数矩阵含单位矩阵；目标函

35、数中基变量系数为目标函数中基变量系数为0 0。O 1 0 20 30 4 0 1 0 2 0 3 0 x2 x1(1)(2)B (10,15)AC第一个基可行解第一个基可行解X0=(0,0,80,60)T目标函数值为目标函数值为0对应可行域顶点对应可行域顶点O(0，0).121231241234max60502480. . 3260,0zxxxxxs txxxxxxx 让让x1进基，不妨假设进基，不妨假设x1 ， x2仍为非基变量。目标函数仍为非基变量。目标函数值为值为 60 。从最优性角度看，从最优性角度看， 越大越好越大越好为了保持解的可行性，原先的基变量取值必须满足为了保持解的可行性，原

36、先的基变量取值必须满足3434280360,0 xxxx 3480206030 xx 802603 综上得到80 60min,2043 348022040603200 xx X4出基，新的基变量为出基，新的基变量为X1 ，X3，对应的典式可以由对应的典式可以由方程组的初等变换得到方程组的初等变换得到121231241234max60502480. . 3260,0zxxxxxs txxxxxxx 242341241234max1200102082403321. .2033,0zxxxxxs txxxxxxx 新的基可行解：新的基可行解：X1=(20,0,40,0)T, 对应的目标函数值为对应的

37、目标函数值为1200。对应可行域对应可行域C点。点。242341241234max1200102082403321. .2033,0zxxxxxs txxxxxxx 取取x2为进基变量，为进基变量，40158/320302/3 x3为出基变量。为出基变量。3423413412341535max13504231158411. .1042,0zxxxxxs txxxxxxx 新的基可行解：新的基可行解：X1=(10,15,0,0)T, 对应的目标函数值为对应的目标函数值为1350。对应可行域对应可行域B点。点。检验数均非正，所以已得到检验数均非正，所以已得到最优解。最优解。当当xk= 0成为基变量

38、以后，其余非基变量仍然取成为基变量以后，其余非基变量仍然取值为值为0。设新基对应的基可行解为。设新基对应的基可行解为X1=(x11, xn1)T,则则X1应满足约束条件，即应满足约束条件，即011111111221122211.01,2,.njjj mmmknnnmmkknnmmmmmkkmnnmjMaxzzxxxxxxxxxxxxxxjn 由于由于xi1必须是非负的，即必须是非负的，即11111222110,1,2,.,jkkmmkmxxxxjn 11111222110000kkkmmmkxxxx 如果如果 ik 0，显然只要显然只要 0，就有就有xi1 = i- ik 0 ，对对于于 ik

39、0，就要求就要求iik 所以所以 应满足应满足0miniik 假定至少有一个假定至少有一个ai k0，i=1,2,m，并且所有的并且所有的 i 0,则则0 0，从最优性原则出发，让从最优性原则出发，让 取值尽量大，即取取值尽量大，即取00minitiktkaa然后把然后把xt从原有的基中取出来，得到一组新的基可行解从原有的基中取出来，得到一组新的基可行解11110111101111101010100kjktttkttttkmmmkxxxxxxx 其其余余X1 使目标函数取值使目标函数取值 z1=z0+ k 0 z0.注意：注意：1. 1. 在选取在选取进基变量进基变量时，若有几个非基变量的检验

40、数都时，若有几个非基变量的检验数都是正数，则可以任意选取一个正检验数对应的非基变量是正数，则可以任意选取一个正检验数对应的非基变量作为进基变量，一般选取最大正检验数对应的非基变量。作为进基变量，一般选取最大正检验数对应的非基变量。但实际情况表明这种策略不一定最好。但实际情况表明这种策略不一定最好。2. 2. 在选取在选取出基变量出基变量时，若有几个比值同时达到最小，时，若有几个比值同时达到最小，可以任意选择一个，但在新的基本可行解中这些对应分可以任意选择一个，但在新的基本可行解中这些对应分量均为零。从而新的基本可行解是一个退化的基本可行量均为零。从而新的基本可行解是一个退化的基本可行解。假若问

41、题是非退化的，则不会出现这种情况。解。假若问题是非退化的，则不会出现这种情况。迭代（新的基可行解对应的典式的确定）迭代（新的基可行解对应的典式的确定）利用线性方程组的等价变换将约束条件和目标函数利用线性方程组的等价变换将约束条件和目标函数化成新基对应的典式，从而求出新的基可行解及相化成新基对应的典式，从而求出新的基可行解及相应的检验数应的检验数第四节第四节 单纯形方法的计算步骤单纯形方法的计算步骤Step 1Step 1 将线性规划问题化成典式将线性规划问题化成典式, ,求出各个非基变量求出各个非基变量的检验数的检验数. .Step 2Step 2 判断所有非基变量的检验数是否非正判断所有非基

42、变量的检验数是否非正, ,若是若是, ,则则结束结束; ;否则转否则转step 3. .Step 3Step 3 选取一个检验数大于零的非基变量为进基变量选取一个检验数大于零的非基变量为进基变量; ;Step 4Step 4 若进基变量所对应的约束条件系数全为非正数若进基变量所对应的约束条件系数全为非正数, ,则原问题无界则原问题无界, ,结束结束; ;否则否则, ,按最小比值原则确定出基变按最小比值原则确定出基变量量; ;Step 5Step 5 进行迭代进行迭代( (用方程组的初等变换法确定新的基用方程组的初等变换法确定新的基对应的典式及检验数对应的典式及检验数),),转转step 2.

43、.121212212max1500250032652403750,0zxxxxxxxxx 例例1 1：利用单纯形法求下列线性规划问题：利用单纯形法求下列线性规划问题将该问题化成标准形式（也是典式）将该问题化成标准形式（也是典式）1212312425max15002500326524037501,2,3,4,5jzxxxxxxxxxxxj 基变量是：基变量是：x3 ，x4 ，x5 ，非基变量是非基变量是 x1 x2求出第一个基可行解求出第一个基可行解X0=(0,0,65,40,75)T，非基变量非基变量的检验数均为正数，所以的检验数均为正数，所以X0不是最优解。不是最优解。确定进基变量确定进基变

44、量 x2，按照最小比值原则确定出基变量按照最小比值原则确定出基变量x5，最小比值是最小比值是 0=25. 求出新基对应的典式求出新基对应的典式250015321353114531253max6250015003152152501,2,3,4,5jzxxxxxxxxxxxj 1212312425max15002500326524037501,2,3,4,5jzxxxxxxxxxxxj 22313133(1)(3)(2)(3)(3)x 利利用用（）式式消消去去X1=(0,25,15,15,0)T目标函数值为目标函数值为62500。250015321353114531253max6250015003

45、152152501,2,3,4,5jzxxxxxxxxxxxj 确定进基变量确定进基变量 x1，按照最小比值原则确定出基变按照最小比值原则确定出基变量量x3，最小比值是最小比值是 0=5. 求出新基对应的典式求出新基对应的典式1323(1)(2)(1) 35121353921345391253max70000500500552501,2,3,4,5jzxxxxxxxxxxxj X*=(5,25,0, 5,0)T目标函数值为目标函数值为70000。当前的解是最优解当前的解是最优解利用（利用（1）消去目标函数中的）消去目标函数中的x1单纯形表单纯形表= - cn+i bi j = cj - cn+

46、i 11mmiijjiijjjiizc bcc acz 其其中中，CBXBbc1c2cmcm+1cnx1x2xmxm+1xnc1x1b110 1m+1 1n:cmxmbm01 mm+1 mn检验数检验数z000 m+1 n用单纯形表求解例用单纯形表求解例1121212212max1500250032652403750,0zxxxxxxxxx 解：先化成标准形式解：先化成标准形式1212312425125max150025003265240375,.,0zxxxxxxxxxxxxxBXBbx1x2x3x4x50 x365321000 x440210100 x575030

47、01 j0150025000000 x3153010-2/30 x4152001-1/32500 x22501001/3 j-625001500000-2500/31500 x15101/30-2/90 x4500-2/311/92500 x22501001/3 j-7000000-5000-50032.5402557.512121212max2543280,0zxxxxxxxx 例例2 2：利用单纯形法求下列线性规划问题：利用单纯形法求下列线性规划问题将该问题化成标准形式（也是典式）将该问题化成标准形式（也是典式）121324125max25432801,2,3,4,5jzxxxxxxxxx

48、xj 基变量是：基变量是：x3 ，x4 ，x5 ，非非基变量是基变量是x1 x2填入单纯形表求解填入单纯形表求解25000CBXBbx1x2x3x4x50 x34101000 x43010100 x5812001 j0250000 x34101005x23010100 x52100-21 j-15200-500 x320012-15x23010102x12100-21 j-19000-1-2 3442最优解最优解X*=(2,3,2,0,0)T，最优值最优值19。例例3 3：用单纯形法求解线性规划问题（多解问题）：用单纯形法求解线性规划问题（多解问题）1212121212max44. .6,0z

49、xxxxxxs txxxx 解解: : 化成标准形式化成标准形式填入单纯形表求解填入单纯形表求解(5,1)(1,5)12123124125max44. .60,1,2,.5jzxxxxxxxxs txxxxj 11000CBXBbx1x2x3x4x50 x34-111000 x441-10100 x5611001 j0110001x24-111000 x48001100 x5220-101 j-420-1001x25011/201/20 x48001101x1110-1/201/2 j-60000-14611x21010-1/21/20 x38001101x151001/21/2 j-6000

50、0-1108最优解最优解X1=(1,5,0,8,0)T，最优值最优值6。最优解最优解X2=(5,1,8,0,0)T，最优值最优值6。实际上实际上X1与与X2的连线上的任意点都是最优解的连线上的任意点都是最优解.(5,1)(1,5)例例4 4：用单纯形法求解线性规划问题（无有限最优解的：用单纯形法求解线性规划问题（无有限最优解的情况）情况）解：化成标准形（典式）解：化成标准形（典式）（5，0）（0，5）1212121225. . 2510,0Max zxxxxs txxxx 12123124123425. . 2510,0Max zxxxxxs txxxxxxx 2100CBXBbx1x2x3x

51、40 x35-11100 x4102-501 j0 2 1 000 x3100-3/211/2 2 x15 1 -5/2 0 1/2 j-10060 -1 5X2的检验数为正，但约束条件中的检验数为正，但约束条件中x2的系数全为负，的系数全为负，因此该问题无有限最优解。因此该问题无有限最优解。12123124123425. . 2510,0Max zxxxxxs txxxxxxx 第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论在给定的在给定的LP问题的标准形式中，如果约束条件系数矩问题的标准形式中，如果约束条件系数矩阵阵A中含有一个中含有一个m阶单位矩阵，并且阶单位矩阵，并且b 0，则

52、我们已经则我们已经找到了一个明显的基可行解，并且约束方程组已经是典找到了一个明显的基可行解，并且约束方程组已经是典式，这时可以直接填入单纯形表中进行迭代。但是实际式，这时可以直接填入单纯形表中进行迭代。但是实际问题往往并非如此，因此我们需要寻找第一个基可行解，问题往往并非如此，因此我们需要寻找第一个基可行解，通常使用两种常用的方法求解第一个基可行解。通常使用两种常用的方法求解第一个基可行解。1.大大M法法2.两阶段法两阶段法考虑标准形式的线性规划问题考虑标准形式的线性规划问题1. 大大M法法112211112211211222221122.01,2,.nnnnnnmmmnnmjMax zc x

53、c xc xa xa xa xba xa xaxbaxaxaxbxjn 112211112211211222221122.01,2,.nnnnnnmmmnnmjMax zc xc xc xa xa xa xba xa xaxbaxaxaxbxjn 112211111221112112222221122.01,2,. ,.nnnn mnnnnnnmmmnnn mmjMax zc xc xc xMxMxa xa xa xxba xa xaxxbaxaxaxxbxjnnm 原问题原问题辅助问题辅助问题人工变量人工变量T T12m12m显显然然辅辅助助问问题题的的约约束束条条件件已已经经化化成成了了典

54、典式式，X=(0,0,.,0,b ,b ,.b )X=(0,0,.,0,b ,b ,.b ) 是是辅辅助助问问题题的的一一个个基基可可行行解解。X是原问题是原问题的基可行解的基可行解0XXX是辅助问题是辅助问题的基可行解。的基可行解。为了得到原问题的一个基可行解，只要将辅助问题为了得到原问题的一个基可行解，只要将辅助问题的基可行解中的人工变量全部变为非基变量即可。的基可行解中的人工变量全部变为非基变量即可。为此，将人工变量加到辅助问题的目标函数中并赋为此，将人工变量加到辅助问题的目标函数中并赋予系数予系数-M。（。（M可以看成惩罚系数）可以看成惩罚系数）添加添加M以后，直接求解辅助问题，可能有

55、两种情况：以后，直接求解辅助问题，可能有两种情况：1.辅助问题的最优解中人工变量全部是非基变量，辅助问题的最优解中人工变量全部是非基变量，此时去掉人工变量直接得到原问题的最优解。此时去掉人工变量直接得到原问题的最优解。2.2.在辅助问题的最优解中某些人工变量是基变量在辅助问题的最优解中某些人工变量是基变量且取值非零，此时原问题无可行解。且取值非零，此时原问题无可行解。例例5：用大：用大M法求解下列线性规划问题法求解下列线性规划问题1312312323123max342139,0zxxxxxxxxxxxxx 131234123523max3421390,1,.5jzxxxxxxxxxxxxxj

56、化标准型化标准型添加人工变量得辅助问题添加人工变量得辅助问题1367123412356237max3421390,1,.7jzxxMxMxxxxxxxxxxxxxxj -30100-M-MCBXBbx1x2x3x4x5x6x70 x441111000-Mx61-21-10-110-Mx790310001 j10M-2M-34M10-M000 x4330211-100 x21-21-10-110-Mx7660403-31 j6M6M-304M+103M-4M00 x400001-1/21/2-1/20 x23011/30001/3-3x11102/301/2-1/21/6 j300303/2-M

57、-3/2-M+1/21x33/23/20103/4-3/41/40 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/4 j-3/2-9/2000-3/4-M+3/4-M-1/44131193/2例例6 6：用单纯形法求解线性规划问题：用单纯形法求解线性规划问题12121212max232212. .214,0zxxxxs txxxx 12123124max232212. .2140(1,2,.4)jzxxxxxs txxxxj 1251231245max232212. .2140(1,2,.5)jzxxMxxxxs txxxxxj 添加人工变量，化成典式添加人

58、工变量，化成典式2300-MCBXBbx1x2x3x4x50 x31222100-Mx514120-11 j14M2+M3+2M0-M03x26110.500-Mx52-10-1-11 j2M-18-1-M0-1.5-M-M0所有的检验数都不大于零，人工变量所有的检验数都不大于零，人工变量X5 仍留在仍留在基变量中且不为零，故原问题无可行解。基变量中且不为零，故原问题无可行解。 672. 2. 两阶段法两阶段法第一阶段：寻找原问题的一个基可行解第一阶段：寻找原问题的一个基可行解 第二阶段：求原问题的最优解第二阶段：求原问题的最优解通过求解一个目标函数只含有人工变量的通过求解一个目标函数只含有人

59、工变量的辅助问题辅助问题实现实现。112211112211211222221122.01,2,.nnnnnnmmmnnmjMax zc xc xc xa xa xa xba xa xaxbaxaxaxbxjn 11111221112112222221122.01,2,. ,.nn mnnnnnnmmmnnn mmjMingxxa xa xa xxba xa xaxxbaxaxaxxbxjnnm 原问题原问题辅助问题辅助问题第一阶段解的情况第一阶段解的情况1. 第一阶段人工变量取值为第一阶段人工变量取值为0 0，目标函数值也为，目标函数值也为0 0。此时得到原问题的第一个基可行解。结束第。此时得

60、到原问题的第一个基可行解。结束第一阶段，去掉人工变量，进入第二阶段求原问题一阶段，去掉人工变量，进入第二阶段求原问题的最优解。的最优解。2. 2. 第一阶段最优解的基变量中含有人工变量，第一阶段最优解的基变量中含有人工变量，表明原问题无可行解。表明原问题无可行解。例例7 7：用两阶段法求解下列线性规划问题：用两阶段法求解下列线性规划问题1312312323123max342139,0zxxxxxxxxxxxxx 131234123523max3421390,1,.5jzxxxxxxxxxxxxxj 化标准型化标准型第一阶段的线性规划问题为第一阶段的线性规划问题为67123412356237mi