第二章 23单纯形法1

1、2.3 2.3 单纯形法单纯形法 本节通过一个引例，可以了解本节通过一个引例，可以了解利用单纯形法求解线性规划问题利用单纯形法求解线性规划问题的思路，并将每一次的结果与图的思路，并将每一次的结果与图解法作一对比，其几何意义更为解法作一对比，其几何意义更为清楚。清楚。引例引例0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz求解线性规划问题的基本思路求解线性规划问题的基本思路1 1、构造初始可行基；、构造初始可行基；2 2、求出一个基本可行解（顶点）、求出一个基本可行解（顶点）3 3、最优性检验：判断是否最优解；、最优性检验：判断是

2、否最优解；4 4、基变化，转、基变化，转2 2。要保证目标函数值比。要保证目标函数值比 原来更优。原来更优。从线性规划解的性质可知求解从线性规划解的性质可知求解线性规划问题的基本思路。线性规划问题的基本思路。第第1 1步步 确定初始基本可行解确定初始基本可行解 1 0 00 1 00 0 1),(543PPPB令：1 0 0 4 00 1 0 0 40 0 1 2 1),.,(51PPA根据根据显然显然 ， 可构成初等可行基可构成初等可行基B 。543,PPP 为基变量543,xxx 第第2 2步步 求出基本可行解求出基本可行解 12(0)12(0) 0230,(0,0,8,16,12)Zxx

3、xxXX代入目标函数令：得一基本可行解3124152 8 2 164 12 4 xxxxxxx基变量用非基基变量用非基变量表示，并变量表示，并令非基变量为令非基变量为 0时对应的解时对应的解是否是最优解？第第3 3步步 最优性检验最优性检验分析目标函分析目标函数数zxx02312检验数检验数0 时，时， 无解无解换基，继续换基，继续xxz1200 ,只要取只要取 或或 的的 值可能增大。值可能增大。换入？基变量换入？基变量换出？基变量换出？基变量考虑将考虑将 或或 换入为基变换入为基变量量21 xx第第4 4步步 基变换基变换l换入基变量换入基变量：2211210320 xxxxz（即选最大非

4、负检验数对应的变量）一般选取一般选取 对应的变量对应的变量12max(,)12,xx1,20, 均可换入均可换入。换入变量 x22x针对目标函数针对目标函数l换出变量换出变量使换入的变量越大越好使换入的变量越大越好同时，新的解要可行。同时，新的解要可行。针对约束条件针对约束条件选非负 的最小者对应的变量换出i2x为换入变量，应换出为换入变量，应换出 ？ 变量。变量。为换出变量变量：为换入变量，确定换出522542323) 4/12, , 2/ 8min( 04 12 0 16 02 8 xxxxxxxx3)4/12, 2/8min(0,min2323222121kaababab3124152

5、8 + 20 164 0 12 40 xxxxxxx（）思考：当 时会怎样？02ka没有有没有有限最优限最优解解因此，基由因此，基由 变为变为BPPP()342 转第转第2步：基变量用非基变量表示。步：基变量用非基变量表示。 第第3步：最优性判断步：最优性判断 检验数检验数 存在正，按第存在正，按第4步换基继续迭代步换基继续迭代 均非正，停止均非正，停止 （这时的解即是最优解）（这时的解即是最优解）2x为换入变量，应换出 变量。为换出变量变量：为换入变量，确定换出522542323) 4 /12, , 2 / 8min( 04 12 0 16 02 8 xxxxxxxx345()BPPP 转转

6、 第第2步步31541251 2 2 164 1 3 4xxxxxxx5(11)0,(0,3,2,16,0)Xxx 令：得一基可行解3124125 82 16 4 1 3 4xxxxxxx 3124152 8 2 164 12 4 xxxxxxx12151513 2323 3-=9244 Zxxxxxx代入目标函数 继续迭代继续迭代, , 可得到可得到: :( 3( 234)( 4 , 2 , 0 , 01 41 .50 .1 2 5( 2 , 3, 0 , 8 ,4 )0 ),ZxxXX目 标 函 数 为 ：最优值最优解l结合图形法分析（单纯形法的几何意义）6 5 4 3 2 1 0 x2|

7、123456789x1)0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目标函数43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目标函数为：43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目标函数为：A(0,3)B(2,3)C(4,2)D(4,0)单纯形法迭代原理单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单单纯形法

8、迭代原理纯形法迭代原理。单纯形法计算流程单纯形法计算流程初始基本可行解初始基本可行解是否最优解或是否最优解或无有限最优解无有限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY考虑标准形式的线性规划问题：Max z = c1x1 + c2x2 + + cnxn s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 . . . am1 x1 + am2 x2 + + amn xn = bm x1 , x2 , , xn 0 x1 c1 b1 a11 a12 . a1n x2 c2 b2 a21

9、a22 . a2nx = . c = . B = . A = . . . . . . . . . xn cn bm am1 am2 . amn 单单 纯纯 形形 法法这里，矩阵A A表示为：A = ( p1 ，p2 ，pn ) ，其中 pj = ( a1j ，a2j ，amj )T Rm。若找到一个可行基，无防设B = ( p1 ，p2 ，pm ) ，则m个基变量为 x1 , x2 , , xm，n-m个非基变量为 xm+1 ，xm+2 ，xn 。 通过运算，所有的基变量都可以用非基变量来表示：单单 纯纯 形形 法法单单 纯纯 形形 法法 x1=b1-（a1m+1xm+1+a1m+2xm+2+

10、a1nxn） x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）( 2-11 ) . . . xm=bm-（amm+1xm+1+amm+2xm+2+amnxn） 把它们代入目标函数，得把它们代入目标函数，得 z = z+ m+1xm+1+ m+2xm+2+ nxn ( 2-12 )其中其中 j=cj-（c1a1j + c2a2j + + cm amj） 我们把我们把由非基变量表示的目标函数形式称为基由非基变量表示的目标函数形式称为基B B相应的目标函数典式典式。 寻找一个寻找一个初始的可行基初始的可行基和相应基本可行解（极和相应基本可行解（极点）点）, ,确定基变量、非基变量以

11、及基变量、非基变量确定基变量、非基变量以及基变量、非基变量（全部等于（全部等于0 0）和目标函数的值，并将目标函数和基）和目标函数的值，并将目标函数和基变量分别用非基变量表示；变量分别用非基变量表示；单纯形法的基本步骤： （1 1） 确定初始的基本可行解确定初始的基本可行解l观察法观察法:直接观察得到初始可行基直接观察得到初始可行基l约束条件约束条件: 加入松弛变量即形成可行基。加入松弛变量即形成可行基。l约束条件约束条件: 加入非负人工变量加入非负人工变量, 以后讨论以后讨论. 线性规划线性规划标准形式标准形式：ax. .0TMzc xstAxbx矩阵形式：101,2,.,njjjjp xb

12、xjn或变量系数矩阵中总会存在变量系数矩阵中总会存在一个单位矩阵，即为初始一个单位矩阵，即为初始可行基。可行基。当约束条件为当约束条件为：101,2,.,njjjjp xbxjn1njjjp xsb 松弛变量的系数矩阵为单位阵当约束条件为当约束条件为：101,2,.,njjjjp xbxjn构造人工基构造人工基大大MM法法1111112211221112 . . .,.,0 mmnnmmnnmmmmmnnmnxaxa xbxaxa xbxaxaxbx xx 不妨设不妨设 为松弛变量，为松弛变量，则约束方程组可表示为则约束方程组可表示为12,mx xx （1 1） 确定初始的基本可行解确定初始的

13、基本可行解 约束条件约束条件: 加入松弛变量即形成可行基。加入松弛变量即形成可行基。 111111222112111 . . . .0 mmnnmmnnmmmmmmnnmnxbaxa xxbaxaxxbaxaxxx令：有：12 (1(,.,0,0,.,0)2,. )miiXxbimb bb是一初始基可行解。 （1 1） 确定初始的基本可行解确定初始的基本可行解 在用非基变量表示的目标函数表达式（在用非基变量表示的目标函数表达式（2-122-12）中，）中，我们称非基变量我们称非基变量x xj j的系数（或其负值）为的系数（或其负值）为检验数检验数记为记为 j j 。 若若所有所有 j j 非正

14、，则当前的基本可行解就是最非正，则当前的基本可行解就是最优解，计算结束；优解，计算结束；（显然所有基变量的检验数必为零：因为目标函数是显然所有基变量的检验数必为零：因为目标函数是仅由非基变量表示的）。仅由非基变量表示的）。 否则，转（否则，转（3 3）。）。单纯形法的基本步骤：z = z+ m+1xm+1+ m+2xm+2+ nxn ( 2-12 )（2 2） 判断现行的基本可行解是否最优判断现行的基本可行解是否最优 j=cj-（c1a1j + c2a2j + + cm amj）（3 3） 基本可行解的改进基本可行解的改进 基变换基变换 如果现行的基本可行解不是最优解，即存在如果现行的基本可行

15、解不是最优解，即存在正的检正的检验数验数，则需在原基本可行解的基础上寻找一个新的基本，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。可行解，并使目标函数值有所改善。具体做法具体做法是：是：先从检验数为正的非基变量中确定一个先从检验数为正的非基变量中确定一个进基变量进基变量（换入变量）（换入变量），使它从非基变量变成基变量，使它从非基变量变成基变量，再从原来的基变量中确定一个再从原来的基变量中确定一个出基变量（换出变出基变量（换出变量）量），使它从基变量变成非基变量。，使它从基变量变成非基变量。由此可得一个由此可得一个新的基本可行解新的基本可行解，这样的变换一定能使目

16、，这样的变换一定能使目标函数值有所增加。标函数值有所增加。单纯形法的基本步骤：进基变量的确定进基变量的确定 当某个当某个j j0 0时，非基变量时，非基变量x xj j变为基变量，变为基变量，从当前值从当前值0 0开始增加时，目标函数值随之增大，开始增加时，目标函数值随之增大，故我们要选检验数大于故我们要选检验数大于0 0的非基变量换到基的非基变量换到基 变量中去（称之为变量中去（称之为进基变量进基变量）。）。 若有两个以上的若有两个以上的j j0 0，则为了使目标函数，则为了使目标函数 增加得更大些，一般选其中的增加得更大些，一般选其中的j j最大者最大者的非基的非基 变量为进基变量。变量为

17、进基变量。0maxjjk出基变量的确定出基变量的确定最小比值原则最小比值原则 在用非基变量表示的基变量的表达式（在用非基变量表示的基变量的表达式（2-112-11）中，观察进）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到增加过程中首先减少到0 0的变量的变量x xr r ，满足，满足， = min= min bbi i /a/aijij aaijij 0 0 = = bbr r / /aarjrj这个基变量这个基变量x xr r称为称为“出基变量出基变量”。当进基变量的值增加到当进基变量的值增加到 时

18、，出基变量时，出基变量x xr r的值降为的值降为0 0时，基时，基本可行解就移动到了相邻的基本可行解（极点），转（本可行解就移动到了相邻的基本可行解（极点），转（4 4）。）。如果进基变量的值增加时，所有基变量的值都不减少，即如果进基变量的值增加时，所有基变量的值都不减少，即所有所有aij 非正非正，则表示，则表示可行域是不封闭可行域是不封闭的，且的，且目标函数值随进基目标函数值随进基变量的增加可以无限增加变量的增加可以无限增加，此时，不存在有限最优解，计算结，此时，不存在有限最优解，计算结束；束； x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn） x2=b2-（a2m+1

19、xm+1+a2m+2xm+2+a2nxn）( 2-11 ) . . . xm=bm-（amm+1xm+1+amm+2xm+2+amnxn） 进基变量进基变量的系数的系数 将进基变量作为新的基变量，出基变量作为新将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重目标函数值。在新的基变量、非基变量的基础上重复（复（1 1）。）。单纯形法的基本步骤 （4 4）. .求改进了的基本可行解求改进了的基本可行解 例例2.102.10：用单纯形法的基本思路解例：用单纯形法的基本思路解例2

20、.82.8的线性规划问题的线性规划问题 Max Max z z = 1500 = 1500 x x1 1 + 2500 + 2500 x x2 2 s.t. 3 s.t. 3 x x1 1 + 2 + 2 x x2 2 + + x x3 3 = 65= 65 2 2 x x1 1 + + x x2 2 + + x x4 4 = 40 = 40 3 3 x x2 2 + + x x5 5 = 75 = 75 x x1 1 , x, x2 2 , x, x3 3 , x , x4 4 , x, x5 5 0 0单单 纯纯 形形 法法第一次迭代第一次迭代：（1 1）取初始可行基取初始可行基B B10

21、10= (= (p p3 3 , p, p4 4 , p, p5 5) )，那么那么x x3 3 ，x x4 4 ，x x5 5为基变量，为基变量，x x1 1 ，x x2 2为为非基变量。非基变量。将基变量和目标函数用非基变量表示：将基变量和目标函数用非基变量表示： z z =1500=1500 x x1 1+2500+2500 x x2 2 x x3 3 = 65 - 3 = 65 - 3 x x1 1 - 2 - 2 x x2 2 x x4 4 = 40 - 2 = 40 - 2 x x1 1 - - x x2 2 x x5 5 = 75 - 3 = 75 - 3 x x2 2当非基变量

22、当非基变量x x1 1，x x2 2=0=0时时，相应的基变量和目标函数值为，相应的基变量和目标函数值为x x3 3=65=65，x x4 4=40=40，x x5 5= 75= 75，z z = 0 = 0，得到当前的基本可行解得到当前的基本可行解：X X（0）=(0,0,65,40,75)=(0,0,65,40,75)T T，z z = 0 = 0 。这个解对应于图。这个解对应于图2-72-7的的D D、E E交点。交点。 3 2 1 0 0A = （P1 ,P2 ,P3 ,P4 ,P5）=2 1 0 1 0 0 3 0 0 1这个基本可行解的经济意义：工厂没有安排生产甲、乙这个基本可行解

23、的经济意义：工厂没有安排生产甲、乙产品，设备未被利用，所以工厂的利润为零。产品，设备未被利用，所以工厂的利润为零。 （2 2）选择进基变量选择进基变量。在目标函数。在目标函数z z = 1500 = 1500 x x1 1 + + 2500 2500 x x2 2中，非基变量中，非基变量x x1 1，x x2 2（即没有安排生产产品（即没有安排生产产品甲、乙）甲、乙）的系数都是正数，因此的系数都是正数，因此 x x1 1 ，x x2 2进基都可以进基都可以使目标函数使目标函数z z增大增大。（从经济意义上讲，工厂安排生。（从经济意义上讲，工厂安排生产产品甲或乙，利润就可增加）产产品甲或乙，利润

24、就可增加） 取初始可行基取初始可行基B B1010= (= (p p3 3 , p, p4 4 , p, p5 5) )，目标函数用非基变量表示：目标函数用非基变量表示： z z =1500=1500 x x1 1+2500+2500 x x2 2但但x x2 2的系数为的系数为25002500，绝对值比，绝对值比x x1 1的系数的系数15001500大，因此大，因此把把x x2 2作为进基变量可以使目标函数作为进基变量可以使目标函数z z增加更快。增加更快。选择选择x x2 2为进基变量为进基变量，使，使x x2 2的值从的值从0 0开始增加，另一个非基变量开始增加，另一个非基变量x x1

25、 1保持零值不变。保持零值不变。（3 3）确定出基变量确定出基变量。在约束条件在约束条件 x x3 3 = 65 - 3 = 65 - 3 x x1 1 - 2 - 2 x x2 2 x x4 4 = 40 - 2 = 40 - 2 x x1 1 - - x x2 2 x x5 5 = 75 = 75 - 3 - 3 x x2 2中，由于中，由于进基变量进基变量x x2 2在在3 3个约束条件个约束条件中的系数都是负数，当中的系数都是负数，当x x2 2的值从的值从0 0开始增加时，基变量开始增加时，基变量x x3 3 、x x4 4 、x x5 5的值分别从当前的值的值分别从当前的值6565

26、、4040和和7575开始减少，开始减少，当当x x2 2增加增加到到2525时，时，x x5 5首先下降为首先下降为0 0，成为非基变量，成为非基变量， x x5 5 为出基变量为出基变量。这这时，新的基变量为时，新的基变量为x x3 3 、x x4 4 、x x2 2 ，新的非基变量为新的非基变量为x x1 1 、x x5 5 ，当前的基本可行解和目标函数值为：当前的基本可行解和目标函数值为：x x（1 1）= (0= (0，2525，1515，1515，0)0)T T，z z = 62500= 62500。这个解对应于图中的。这个解对应于图中的C C、D D交点。交点。初始基本可行解：初

27、始基本可行解：x=(0,0,65,40,75)T，z = 0选择选择x2为进基变量为进基变量说明了：每生产一件产品乙，需要占用各设备的机时数说明了：每生产一件产品乙，需要占用各设备的机时数（2,1,3），由其中的薄弱环节就确定了产品乙的产量。），由其中的薄弱环节就确定了产品乙的产量。由设备由设备C的设备能力确定了产品乙的产量的设备能力确定了产品乙的产量x2=75/3=25（1 1）当前的可行基为）当前的可行基为B B7 7 = (= (p p2 2 , p, p3 3 , , p p4 4) )。将基变量和目标函数用非基变量表示将基变量和目标函数用非基变量表示： z z = 62500 + 1

28、500 = 62500 + 1500 x x1 1 (2500/3) (2500/3) x x5 5 x x2 2 = 25 = 25 (1/3) (1/3) x x5 5 x x3 3 = 15 - 3 = 15 - 3 x x1 1 + (2/3) + (2/3) x x5 5 x x4 4 = 15 - 2 = 15 - 2 x x1 1 + (1/3) + (1/3) x x5 5 （2 2）选择进基变量选择进基变量。在目标函数中，。在目标函数中，x x1 1进基可以使目标进基可以使目标函数函数z z增大，于是选择增大，于是选择x1进基，使进基，使x x1 1的值从的值从0 0开始增加

29、开始增加, , 另另一个非基变量一个非基变量x x5 5保持零值不变。保持零值不变。 (3)(3)确定出基变量确定出基变量。在约束条件中，当。在约束条件中，当x x1 1的值从的值从0 0开始增开始增加时，加时，x x3 3首先下降为首先下降为0 0成为非基变量。这时，新的基变量成为非基变量。这时，新的基变量为为x x1 1 、x x2 2 、x x4 4 ，新的非基变量为，新的非基变量为x x3 3 、x x5 5 ，当前的基本当前的基本可行解和目标函数值为：可行解和目标函数值为：x x（2） = (5= (5，2525，0 0，5 5，0)0)T T，z z = 70000= 70000。这个解对应于图中的。这个解对应于图中的A A、C C交点。交点。第二次迭代：第二次迭代：非基变量非基变量x x1 1的系数为正，目标值还可增大，的系数为正，目标值还可增大，x x（1 1）不是最优解不是最优解（1 1）当前的可行基为）当前的可行基为B B2 2 = (= (p p1 1 , , p p2 2