运筹学课件ch01s4-6

1、4.1 单纯型表v为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似。v将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组。第4节 单纯型法的计算步骤线性规划的方程组0111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxczbxaxaxbxaxaxbxaxax线性规划的方程组v为了便于迭代运算，可将上述方程组写成增广矩阵形式01000001000010211211,21, 211, 1121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxz线性规划的方程组v若将z看作不参与基变换的基变量，它与

2、x1,x2,xm的系数构成一个基，这时可采用行初等变换将c1,c2,cm变换为零，使其对应的系数矩阵为单位矩阵。得到miiimmiininmimiimmnmmnmnmnmmbcbbbaccaccaaaaaabxxxxxz121111,11,21, 211, 11210001000001000010表1-2线性规划的方程组v表1-2的说明XB列中填入基变量，这里是x1，x2,，xm；CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的；b列中填入约束方程组右端的常数；cj行中填入基变量的价值系数c1,c2,cn；i列的数字是在确定换入变量后，按规则计算后填入；最后一行称为

3、检验数行，对应各非基变量xj的检验数是miijijnjacc1, 2 , 1,4.2 计算步骤v表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。v计算步骤：(1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。(2) 计算各非基变量xj的检验数， 检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。miijijjacc1,njj, 2 , 1, 04.2 计算步骤(3)在j0,j=m+1,n中，若有某个k对应xk的系数列向量Pk0，则此问题是无界，停止计算。 否则，转入下一步。(4) 根据max(j0)=k，确定xk为换入变量，按规则计算lklikikia

4、baab0min4.2 计算步骤(5) 以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量 将XB列中的xl换为xk，得到新的单纯形表。重复(2)(5)，直到终止。行第变换laaaaPmklkkkk0100214.2 计算步骤v现用例1的标准型来说明上述计算步骤v(1) 取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(0)=(0,0,8,16,12)Tv将有关数字填入表中，得到初始单纯形表，见表1-3。表中左上角的cj是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数，它们都为零。5 , 2 , 1012416482

5、5241321jxxxxxxxxj5432100032maxxxxxxz4.2 计算步骤cj 2 3 0 0 0 CB XB b x 1 x 2 x 3 x 4 x 5 0 x 3 8 1 2 1 0 0 8/2=4 0 x 4 16 4 0 0 1 0 - 0 x 5 12 0 4 0 0 1 12/4=3 -z 0 2 3 0 0 0 表 1-34.2 计算步骤v计算非基变量的检验数 各非基变量的检验数为1=c1z1=2(01+04+00)=22=c2z2=3(02+00+04)=3 填入表1-3的底行对应非基变量处。4.2 计算步骤(2) 因检验数都大于零，且 P1，P2有正分量存在，

6、转入下一步； (3) max(1,2)=max(2,3)=3，对应的变量 x2为换入变量， 计算 341201628022,minaabminiiii 它所在行对应的x5为换出变量，x2所在列和x5所在行的交叉处 4称为主元素或枢元素(pivot element)4.2 计算步骤 (4) 以4为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为(0,0,1)T,在XB 列中将x2 替换x5 ,于是得到新表1-4. cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 2 1 0 1 0 -1/2 2 0 x4 16 4 0 0 1 0 4 3 x2 3 0 1

7、 0 0 1/4 - -z -9 2 0 0 0 -3/4 换人变量换出变量主元素4.2 计算步骤 (5) 检查表1-4的所有cjzj,这时有c1z1=2；说明x1应为换入变量。重复(2)(4)的计算步骤，得表1-5。 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 2 1 0 1 0 -1/2 - 0 x4 8 0 0 -4 1 2 4 3 x2 3 0 1 0 0 1/4 12 -z -13 0 0 -2 0 1/4 换人变量换出变量主元素因为还存在检验数0，继续进行迭代。4.2 计算步骤 (6) 表1-6最后一行的所有检验数都已为负或零。这表示目标函数值

8、已不可能再增大，于是得到最优解cj 2 3 0 0 0 CB XB b x1 x2 x3 X4 x5 2 x1 4 1 0 1 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 -z -14 0 0 -3/2 -1/8 0 X*=X(3)=(4,2,0,0,4)T 目标函数的最大值 z*=14例 用单纯形法解线性规划问题00524261552max212121221xxxxxxxxxz解：化为标准型0524261550002max515214213254321xxxxxxxxxxxxxxz00012cj-zj5100115x5040102624x4

9、00015015x30 x5x4x3x2x1b基基CB00012Cj0-1/301/303/21-1/602/301x501201/601/314x1230015015x30cj-zj-1/2-1/40003/2-1/40103/2x21-1/21/40017/2x12-15/25/410015/2x30cj-zjx5x4x3x2x1b基基CB00012CjZ*=17/2, X*=(7/2,3/2, 15/2,0,0)有唯一最优解下表是用单纯形法计算时某一表格，已知该线性规划的目标函下表是用单纯形法计算时某一表格，已知该线性规划的目标函数为数为max z=5x1+3x2，约束形式为，约束形式为

10、，x3，x4为松弛变量，当前为松弛变量，当前目标函数值为目标函数值为10：Cj5300CB基基bx1x2x3x405x3x12ACD0E101/51cj-zjB-1FG (1)计算计算A-G的值的值 (2)表中解是否为最优解表中解是否为最优解A=2、B=0、C=0、D=1、E=4/5、F=0、G=-5解是最优解解是最优解练习练习下表是用单纯形法计算时某一表格，已知目标函数为下表是用单纯形法计算时某一表格，已知目标函数为maxZ=28x4+x5+2x6，约束形式为，约束形式为，x1， x2， x3为松弛变量，当为松弛变量，当前目标函数值为前目标函数值为14：(1)计算计算A-G的值的值 (2)表

11、中解是否为最优解表中解是否为最优解CjCB基基bx1x2x3x4x5x6x6x2x4A503600DE-14/32F00115/20100cj-zjBC00-1G（1） 7，6，0，1，0，1/3，0（2）表中解是最优解）表中解是最优解练习练习 用单纯形法解线性规划问题用单纯形法解线性规划问题 0042222max2121212121xxxxxxxxxxz解：化为标准型解：化为标准型,初始单纯形表如下初始单纯形表如下0001100101010012111-2-1224x3x4x5000 x5x4x3x2x1b基基CB00011Cjjjzc jjzc 00-130001010121-2-3-11

12、00266x1x4x5100 x5x4x3x2x1b基基CB00011Cj解无界练习练习 用单纯形法解线性规划问题用单纯形法解线性规划问题 00348242max21212121xxxxxxxxz解：化为标准型解：化为标准型,初始单纯形表如下初始单纯形表如下Cj24000CB基基bx1x2x3x4x5000 x3x4x5843110201100010001cj-zj24000Z*=20, *=(2,3,0,2,0)Z*=20, *=(4,2,0,0,1)Cj24000CB基基bx1x2x3x4x5004x3x4x2243110001100010-201cj-zj2000-4204x1x4x22

13、231000011-10010-221cj-zj00-200204x1x5x24121000010-1/21/211/2-1/2010cj-zj00-200有无穷多个解有无穷多个解第5节 单纯形法的进一步讨论v5.1 人工变量法v5.2 退化v5.3 检验数的几种表示形式第5节 单纯形法的进一步讨论5.1 人工变量法设线性规划问题的约束条件其中没有可作为初始基的单位矩阵，则分别给每一个约束方程加入人工变量xn+1,xn+m，得到0,; 0,1122112222212111212111mnmnmnnmnmmnnnnnnxxxxbxxaxaxabxxaxaxabxxaxaxanjjjbxP15.1

14、 人工变量法v以xn+1,，xn+m为基变量，并可得到一个mm单位矩阵。令非基变量x1,xn为零，便可得到一个初始基可行解X(0)=(0,0,0,b1,b2,bm)Tv因为人工变量是后加入到原约束条件中的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。v基变量中不再含有非零的人工变量，这表示原问题有解。v若在最终表中当所有cjzj0，而在其中还有某个非零人工变量，这表示原问题无可行解。v以下讨论如何解含有人工变量的线性规划问题。5.1 人工变量法 例例8 现有线性规划问题，试用大M法求解。0,123241123min32131321321321xxxxxxxxxxxxxxz1.大M法5

15、.1 人工变量法解解 在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6,x7，得到0,12324112003min76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxz 这里M是一个任意大的正数。 5.1 人工变量法 因本例的目标函数是要求min，所以用所有cjzj0来判别目标函数是否实现了最小化.用单纯形法进行计算时，见表1-6。5.1 人工变量法在表1-6的最终计算结果可看出，已得到最优解：x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z = 25.1 人工变量法v以下介绍求解含有人工变量线性规划

16、问题的两阶段法。v第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。2.两阶段法两阶段法5.1 人工变量法v第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如0,000min1212211222222121111212111211mnnnmmnnmmmnnnnnnnmnnxxxxxbxxaxaxabxxaxaxabxxaxaxaxxxxx约束条件目标函数5.1 人工变量法v第一阶段求解用单纯形法求解上述模型。若得到的最有值w=0，说明原问题存在基可行解，可以进行

17、第二段计算。否则原，问题无可行解，应停止计算。v第二阶段求解从第一阶段计算得到的最终表中除去人工变量，将目标函数行的系数，换为原问题的目标函数系数，作为第二阶段计算的初始表。各阶段的计算方法及步骤与第3节介绍的单纯形法相同。 5.1 人工变量法v例例9 试用两阶段法求解如下线性规划问题：0,123241123min32131321321321xxxxxxxxxxxxxxz约束条件目标函数5.1 人工变量法v解解: : 先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：0,12324112min765432173165321432176xxxxxxxxxxxxxxxxxxx

18、xx约束条件目标函数5.1 人工变量法表 1-75.1 人工变量法v第一阶段用单纯形法求解，见表1-7。求得的结果是w=0，最优解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0v因为人工变量x6=x7=0，所以(0，1，1，12，0)T是原线性规划问题的基可行解。v于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，填入原问题的目标函数系数，进行第二阶段计算，见表1-8。5.1 人工变量法表 1-8从表1-8得到最优解：x1=4,x2=1,x3=9,目标函数值 z=25.2 退化v在单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代

19、中就有一个或几个基变量等于零，这就出现了退化解。v这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，又返回到B1，即出现计算过程的循环，便永远达不到最优解。 5.2 退化v尽管实际计算过程中循环现象极少出现，但还是有可能发生的。如何解决这问题? 先后有人提出了“摄动法”，“字典序法”。1974年由勃兰特(Bland)提出一种简便的规则，简称勃兰特规则：(1) 选取cjzj0中下标最小的非基变量xk为换入变量，即k=min(j cjzj0 )(2) 当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量

20、为换出变量。按勃兰特规则计算时，一定能避免出现循环。5.3 检验数的几种表示形式v本书以max z=CX；AX=b，X0为标准型，以cjzj0，（j=1,2,n）作为最优解的判别准则。v由于还有其他形式的问题，为了避免混淆，将有关情况归纳如下：设x1,x2,xm为约束方程的基变量，于是可得nmjjijiimixabx1, 2 , 1,5.3 检验数的几种表示形式将它们代入目标函数后，可有两种表达形式)371 ()()() 1 (10111nmjjjjminmjmijijijiixzczxaccbcz)381 ()()()2(10111 nmjjjjminmjmijjijiiixczzxcacb

21、cz判别准则的选择当要求目标函数实现最大化时，若用(1-37)式来分析，就需要用cjzj0,（j=1,2，,n）作为判别准则；若用(1-38)式来分析，就需要用zjcj0,（j=1,2,n）作为判别准则。当要求目标函数实现最小化时，可用(1-37)式或(1-38)式来分析，这时可分别用cjzj0或zjcj0，（j=1,2,n）来判别目标函数是否已达到最小。几种判别准则的汇总标准型 检验数 max z=CX AX=b,X0 min z=CX AX=b,X0 cj-zj zj-cj 0 0 0 0 5.4 单纯形法小结v(1) 根据实际问题给出数学模型，列出初始单纯形表。进行标准化，见表1-10。

22、分别以每个约束条件中的松弛变量或人工变量为基变量，列出初始单纯形表。表1-10第6节 应用举例v一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型。 (1) 要求解问题的目标函数能用数值指标来表示，且为线性函数； (2) 存在着多种方案及有关数据； (3) 要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。第6节 应用举例v例例10 合理利用线材问题合理利用线材问题。现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。v解：解：最简单做法是，在每一根原材料上截取2.9m，2.1

23、m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头。若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用。见表1-11。表1-11第6节 应用举例v为了得到100套钢架，需要混合使用各种下料方案。设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5。根据表1-11的方案，可列出以下数学模型：0,1003231002210028 . 03 . 02 . 01 . 00min54321532154342154321xxxxxxxxxxxxxxxxxxx

24、xz第6节 应用举例v在以上约束条件中加入人工变量x6,x7,x8；然后用表1-12进行计算。表1-12第6节 应用举例v第1次计算cj 0 0.1 0.2 0.3 0.8 -M -M -M i CB XB b x1 x2 x3 x4 x5 x6 x7 x8 -M -M 1 x6 x7 x1 200/3 100 100/3 0 0 1 5/3 0 1/3 -2/3 2 2/3 1 2 0 -1 1 1 1 0 0 0 1 0 -1/3 0 1/3 200/3 100/2 cj-zj 0 -0.1+5/3M -0.2+4/3M -0.3+3M -0.8 0 0 -4/3M 第6节 应用举例v第2

25、次计算第6节 应用举例v最终计算表（第3次计算）cj 0 0.1 0.2 0.3 0.8 -M -M -M i CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0.1 -0.3 0 x2 x4 x1 10 50 30 0 0 1 1 0 0 -1 1 1 0 1 0 -9/10 1/3 13/10 3/5 0 -1/5 -3/10 1/3 1/10 -1/5 0 2/5 cj-zj 0 0 0 0 -0.74 -M +0.06 -M +0.12 -M -0.02 由计算得到最优下料方案是：按方案下料30根；方案下料10根；方案下料50根。即需90根原材料可以制造100套钢架。有

26、非基变量的检验数为零，所以存在多重最优解 。第6节 应用举例v例例11 （配料问题）某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1-13和表1-14。该厂应如何安排生产，使利润收入为最大? 解：解： 如以AC表示产品A中C的成分，AP表示产品A中P的成分，依次类推。表1-13第6节 应用举例v根据表1-13有：)391 (21,41,41,21BBBBAAAAPCPC这里 AC+AP+AH=A； BC+BP+BH=B (1-40)将(1-40)逐个代入(1-39)并整理得到02141210414

27、14304143410212121HPCHPCHPCHPCBBBBBBAAAAAA第6节 应用举例v表1-14表明这些原材料供应数量的限额。加入到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不超过60kg。原材料名称 每天最多供应量（kg） 单价/(元/kg) C 100 65 P 100 25 H 60 35 表1-14第6节 应用举例v由此得约束条件AC+BC+DC100AP+BP+DP100AH+BH+DH60v在约束条件中共有9个变量，为计算和叙述方便，分别用x1,x9表示。令x1=Ac, x2=Ap, x3=AH,x4=BC, x5=BP, x6

28、=BH,x7=DC, x8=DP, x9=DH.第6节 应用举例v约束条件可表示为：0,60100100021212104141430414341021212191963852741654654321321xxxxxxxxxxxxxxxxxxxxxxx第6节 应用举例v目标函数目的是使利润最大，即产品价格减去原材料的价格为最大。产品价格为：50(x1+x2+x3)产品A 35(x4+x5+x6) 产品B 25(x7+x8+x9) 产品D原材料价格为：65(x1+x4+x7)原材料C 25(x2+x5+x8) 原材料P 35(x3+x6+x9) 原材料Hv为了得到初始解，在约束条件中加入松弛变量

29、x10 x16，得到数学模型：第6节 应用举例v例11的线性规划模型0,601001000212121041414304143410212121010401030152515max18109116963158521474113654126541132110321161514131211109754321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz约束条件目标函数第6节 应用举例v最优解用单纯形法计算，经过四次迭代，得最优解为： x1=100,x2=50,x3=50这表示：需要用原料C为100kg，P为50kg，H为50kg，构成产品A。即每天只

30、生产产品A为200kg，分别需要用原料C为100kg，P为50kg，H为50kg。从最终计算表中得到，总利润是z=500元/天。第6节 应用举例v例例12 生产与库存的优化安排问题生产与库存的优化安排问题 某工厂生产五种产品(i=1,5)，上半年各月对每种产品的最大市场需求量为dij(i=1,5;j=1,6)。已知每件产品的单件售价为Si元，生产每件产品所需要工时为ai，单件成本为Ci元；该工厂上半年各月正常生产工时为rj(j=1,6)，各月内允许的最大加班工时为rj;Ci为加班单件成本。又每月生产的各种产品如当月销售不完，可以库存。库存费用为Hi(元/件月)。假设1月初所有产品的库存为零，要

31、求6月底各产品库存量分别为ki件。现要求为该工厂制定一个生产计划，在尽可能利用生产能力的条件下，获取最大利润。第6节 应用举例 解：解：设xij和xij分别为该工厂第i种产品的第j个月在正常时间和加班时间内的生产量；yij为i种产品在第j月的销售量，wij为第i种产品第j月末的库存量。根据题意，可用以下模型描述： (1) 各种产品每月的生产量不能超过允许的生产能力，表示为：51516 , 1,6 , 1,ijiiijiijrxajrxa第6节 应用举例(2) 各种产品每月销售量不超过市场最大需求量 yi jdij (i=1,5;j=1,6)(3) 每月末库存量等于上月末库存量加上该月产量减掉当

32、月的销售量(4) 满足各变量的非负约束 iiiijijijjiijkjiyxx601, 06 , 1; 5 , 1其中xij0, xij0, yij0, (i=1,5；j=1,6)wij0(i=1,5；j=1,5)第6节 应用举例(5) 该工厂上半年总盈利最大可表示为： 51615161maxijijijiijiijiijiHxCxCySz第6节 应用举例例例1313 连续投资问题连续投资问题 某部门在今后五年内考虑给下列项目投资，已知：v项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；v项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元

33、；v项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；v项目D，五年内每年初可购买公债，于当年末归还，并加利息6%。v该部门现有资金10万元，问它应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大?第6节 应用举例 解：解： (1) 确定决策变量 这是一个连续投资问题，与时间有关。但这里设法用线性规划方法，静态地处理。以xiA,xiB,xiC,xiD(i=1,2,，5)分别表示第i年年初给项目A，B，C，D的投资额，它们都是待定的未知变量。根据给定的条件，将变量列于表1-15中。项目 第一年 第二年 第三年 第四年 第五年 A x1A x2A x3A x4A / B / / x3B / / C / x2C / / / D x1D x2D x3D x4D x5