运筹学-1、线性规划

1、1运筹学运筹学Operations Research2 运筹学运筹学是一门应用科学是一门应用科学 ，它广泛应用现有的，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据门问题，为决策者选择最优决策提供定量依据。 运筹学作为一门新兴的学科是在第二次世界大运筹学作为一门新兴的学科是在第二次世界大战期间出现的战期间出现的 。当时英美成立了名为当时英美成立了名为“运作研究运作研究” ( Oprtational Research)小组，通过科学方法的运用小组，通过科学方法的运用成功地解决了许多非常复杂的战略和战术问

2、题。成功地解决了许多非常复杂的战略和战术问题。3 例如如何合理运用雷达有效地对付德国空袭；例如如何合理运用雷达有效地对付德国空袭；对商船队如何进行编队护航，在船队遭受德国潜艇对商船队如何进行编队护航，在船队遭受德国潜艇攻击时使船队损失最少；反潜深水炸弹在各种情况攻击时使船队损失最少；反潜深水炸弹在各种情况下如何调整其爆炸深度，才能增加对德国潜艇的杀下如何调整其爆炸深度，才能增加对德国潜艇的杀伤力等伤力等 ；军队营养物质供应问题。；军队营养物质供应问题。 运筹学课程的一般内容有：运筹学课程的一般内容有：线性规划、整数规线性规划、整数规划、非线性规划、动态规划、图与网络分析、排队划、非线性规划、动

3、态规划、图与网络分析、排队论、对策论、存贮论、决策论等。论、对策论、存贮论、决策论等。4线性规划线性规划56 例例1: :( (生产计划问题生产计划问题) )某工厂生产某工厂生产 I I、IIII 两种产两种产品品。每件产品的单位利润，所消耗的两种材料数、每件产品的单位利润，所消耗的两种材料数、设备工时及这两种材料、设备工时的限额如下表：设备工时及这两种材料、设备工时的限额如下表： I IIIII资源限量资源限量 设备设备材料材料A A材料材料B B1402048台时台时16kg12kg 利润利润23712121212max2328416.412,0Zxxxxxstxx x解：解：设设 x1、

4、x2分别表示两种产品的产量，那么该问分别表示两种产品的产量，那么该问题的数学模型可以表示为：题的数学模型可以表示为：8第第i 种资源的拥有量为种资源的拥有量为bi ;i=1,2,m ,生产一个单位第生产一个单位第j种产品需要消耗第种产品需要消耗第i 种资源的数量为种资源的数量为aij;第第j种产品的利润（单价种产品的利润（单价,产值）为产值）为cj 。j =1,2,n。上述问题推广到一般情况：上述问题推广到一般情况：有有m种不同资源（例如原材料，动力资源，资金，劳力种不同资源（例如原材料，动力资源，资金，劳力等）可以用来生产等）可以用来生产n种不同产品。假设有关的数据为：种不同产品。假设有关的

5、数据为：设设x1、x2、xn 分别表示分别表示n种产品的产量，则其数种产品的产量，则其数学模型为：学模型为：91 12211 11221121 1222221 12212max.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx10 例例2： (配料问题配料问题) 一饲养场饲养动物出售，每只一饲养场饲养动物出售，每只动物每天至少需要动物每天至少需要700克蛋白质克蛋白质， 30克矿物质，克矿物质，100毫克维生素。现有四种饲料可供选用，各种饲料每公毫克维生素。现有四种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示；斤

6、营养成分含量及单价如下表所示； 饲料饲料营养成分营养成分 需要量需要量蛋白质蛋白质3 2 1 5700克克矿物质矿物质1 0.5 0.2 230克克维生素维生素0.5 1 0.3 2.5100毫克毫克单价单价(元元/公公斤斤)0.8 1.2 0.6 2 四种饲料各采购多少，才能使总费用最小？四种饲料各采购多少，才能使总费用最小？11 解：解：设设 x1、x2、 x3、 x4分别表示四种饲料的采分别表示四种饲料的采购量，那么该问题的数学模型可以表示为：购量，那么该问题的数学模型可以表示为：12341234123412341234min0.81.20.623257000.50.2230.0.50.

7、32.5100,0Zxxxxxxxxxxxxstxxxxx x x x12上述模型推广到一般情况为：上述模型推广到一般情况为：每只动物每天至少需要每只动物每天至少需要有有m种不同种不同营养成分营养成分bi；有有n种饲料可供选用，每公斤种饲料可供选用，每公斤第第j种种饲料所含饲料所含第第i种种营营养成分量为养成分量为aij;第第j种种饲料的单价饲料的单价为为cj 。i=1,2,m， j=1,2,n。设设x1、x2、xn 分别表示分别表示n种种饲料饲料的采购量，则其的采购量，则其数学模型为：数学模型为：如何采购才能使总费用最小？如何采购才能使总费用最小？131 12211 11221121 122

8、2221 12212min.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbsta xaxaxbx xx14 例例3：（运输问题）运输问题）设有两个砖厂设有两个砖厂A1 、A2 ，产，产量分别为量分别为23万块、万块、27万块，现将其产品联合供应三万块，现将其产品联合供应三个施工现场个施工现场B1 、 B2 、 B3 ，其需要量分别为，其需要量分别为17万万块、块、18万块、万块、15万块。各产地到各施工现场的单位万块。各产地到各施工现场的单位运价如下表：运价如下表：问如何调运才能使总运费最省？问如何调运才能使总运费最省？ 现场现场砖厂砖厂 B1 B2

9、 B3A15147A2618915解：解：设设xijij表示从砖厂表示从砖厂A Ai运往现场运往现场B Bj j的数量的数量 ( (i=1=1，2;j=1,22;j=1,2，3),3),则其数学模型如下：则其数学模型如下：111213212223111213212223112112221323min51476189232717.18150(1,2,1,2,3)ijZxxxxxxxxxxxxxxstxxxxxij1617 1 12211 11221121 1222221 12212max(min).( , ).( , ).( , ),.,0nnnnnnmmmnnmnZc xc xc xa xa

10、xa xba xa xa xba xaxaxbx xx 18 例例4： （投资问题（投资问题 ） 某投资公司在第一年初有某投资公司在第一年初有100万元资金，每年都有如下的投资方案可供考虑采万元资金，每年都有如下的投资方案可供考虑采纳：纳：“假使第一年投入一笔资金，第二年又继续投入假使第一年投入一笔资金，第二年又继续投入此资金的此资金的50%，那么到第三年就可回收第一年投入资，那么到第三年就可回收第一年投入资金的两倍金额金的两倍金额” 。投资公司要设法决定最优的投资策。投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。略使第六年所掌握的资金最多。解：解：设设x1为第一年的投资为第一年的

11、投资; x2为为 第一年的保留资金；第一年的保留资金；100 ：21 xx则设设x3为第二年新的投资；为第二年新的投资； x4为第二年的保留资金；为第二年的保留资金；2431)2( ：xxxx则19设x5为第三年新的投资；为第三年新的投资；x6为第三年的保留资金；为第三年的保留资金；146532)2( ：xxxxx则368752)2( ：xxxxx则设设x7为第四年新的投资；第四年的保留资金为为第四年新的投资；第四年的保留资金为x8；设设x9为第五年的保留资金：第五年不再进行新的投资，因为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到第七年才能回收。为这笔投资要到第七年才能回收。

12、589722 ：xxxx则约束条件保证每年满足如下的关系：追加投资金约束条件保证每年满足如下的关系：追加投资金额额+新投资金额新投资金额+保留资金保留资金=可利用的资金总额。可利用的资金总额。20到第六年实有资金总额为到第六年实有资金总额为x9+2x7，整理后得到，整理后得到下列线性规划模型：下列线性规划模型：7912123413456356785789m ax2100222042220.4222042200,1, 2,9jZxxxxxxxxxxxxxs txxxxxxxxxxj21 例例5：（下料问题）下料问题） 某一机床需要用甲、乙、某一机床需要用甲、乙、丙三种规格的钢轴各一根，这些轴的规

13、格分别是丙三种规格的钢轴各一根，这些轴的规格分别是2.9,2.1, 1.5(m),这些钢轴需要用同一种圆钢来做，圆这些钢轴需要用同一种圆钢来做，圆钢长度为钢长度为7.4m。现在要制造。现在要制造100台机床，最少要用多台机床，最少要用多少根圆钢来生产这些钢轴？少根圆钢来生产这些钢轴？ 解：解：第一步：设一根圆钢切割成甲、乙、丙三第一步：设一根圆钢切割成甲、乙、丙三种钢轴的根数分别为种钢轴的根数分别为y1,y2,y3，则切割方式可用不等，则切割方式可用不等式式2.9y1+2.1y2+1.5y37.4 表示，求这个不等式的有实表示，求这个不等式的有实际意义的非负整数解共有际意义的非负整数解共有8组

14、，也就是有组，也就是有8种不同的种不同的下料方式，如下表所示：下料方式，如下表所示：22 方案方案规格规格12345678y1(2.9m)21110000y2(2.1m)02103210y3(1.5m)10130234余料余料0.10.30.901.10.20.81.4设设x1、x2、x8 表示按表示按8 8种方案下料的圆种方案下料的圆钢钢根数，根数，则问题的数学模型为：则问题的数学模型为： 2387654321minxxxxxxxxZ1234235671346782100232100323410001 28.,jxxxxxxxxxs txxxxxxxj，24251 12211 1122112

15、1 1222221 12212max(min).( , ).( , ).( , ),.,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xaxaxbx xx 262711221111221121122222112212max .,.,0 nnnnnnmmmnnmnZc xc xc xa xaxaxbaxaxaxbs taxaxaxbxxx目标函目标函数最大数最大约束条约束条件等式件等式决策变决策变量非负量非负28 11max 1,2,.0 1,2,.,njjjnijjijjZc xa xbims txjn291max.0 1,2,.njjjjZCXP

16、 xbstxjn111222jjjnmmjaxbaxbX P b .xba其中：其中：12nC(c ,c ,.c )30C价值向量价值向量b资源向量资源向量X决策变量向量决策变量向量A资源消耗系数矩阵资源消耗系数矩阵11121212221212 ( ,.,)nnnmmmnaaaaaaAP PPaaamaxs.t 0ZCXAXbX311) 若目标函数为：若目标函数为：minZ=CX，则令，则令Z= - -Z ,于是得于是得到到max Z= - -CX 2) 若若约束条件约束条件为：为：1 122,kkknnka xa xa xb引进松弛变量引进松弛变量xn+1 , 使：使：1 1221kkknn

17、nka xa xa xxb显然：显然：11 1220.nkkkknnxba xa xa x32若若约束条件约束条件为：为：1 122,kkknnka xa xa xb引进松弛变量引进松弛变量xn+1 , 使：使：1 1221kkknnnka xa xa xxb显然：显然：11 1220nkkknnkxa xa xa xb若若xk无无非负约束非负约束 ，则令：，则令：/,0,0kkkkkxxxxx33123123123123123min3283325,0Zxxxxxxxxxxxxx xx 、 无约束例例1：将下列线性规划化为标准形将下列线性规划化为标准形解：解：标准形为：标准形为：1233123

18、34123351233123345max3328332()50Zxxxxxxxxxxxxxxxxxxxxxxxx、 、 、 、 、34 可行解可行解：满足：满足AX=b, XAX=b, X0 0的解的解X X称为线性称为线性规划问题的规划问题的可行解可行解。 可行域可行域：可行解的全体称为：可行解的全体称为可行域可行域。 最优解最优解：使：使Z=CXZ=CX达到最大值的可行解称达到最大值的可行解称为为最优解最优解。 max . 0ZCXAXbstX标准型标准型35标准形的假定标准形的假定( ),0,010.irank Ammnbbi(1)矩阵A的秩(2).若有可对第 个约束方程两边同时乘以.3

19、6基基：若若B是矩阵是矩阵A中中mm阶非奇异子矩阵，则称阶非奇异子矩阵，则称B是线性规划问题的一个是线性规划问题的一个基基。不妨设：。不妨设：11121212221212 ( ) mmmmmmmaaaaaaBP PPaaa,1,2,jPjm,1,2,jxjm,1,2,jxjmmn 基向量 基变量 非基变量37,( ,),(,),BBNNXAB N CC CXX此时max.0ZCXAXbstXmax(,)( ,).,0BBNNBNBNXZCCXXB NbXstXX38max.,0BBNNBNBNZC XC XBXNXbstXX两边同时左乘两边同时左乘B-1-1得到：得到： 11BNXB bB N

20、X1120,( ,)TNBmXXB bb bb令则 约束方程化为：约束方程化为：BNBXbNX12( ,0,0,0)TmXb bb于是得解：于是得解：39 基本解基本解：上面求出的：上面求出的X称为对应基称为对应基B下的下的基本解基本解 基本可行解基本可行解：非负的基解：非负的基解X X称为称为基本可行解基本可行解 可行基可行基：对应基可行解的基称为：对应基可行解的基称为可行基可行基 基本最优解基本最优解：最优的基可行解称为：最优的基可行解称为基本最优解基本最优解 最优基最优基：对应基本最优解的基称为：对应基本最优解的基称为最优基最优基4012345123142512345max230002

21、84 16. 4 12,0Zxxxxxxxxxxstxxx x x x x例例7: 解：解：系数矩阵为：系数矩阵为：1 0 0 4 00 1 0 0 40 0 1 2 1),.,(521PPPA41易知：易知：都是基。都是基。72458345(,),(,)BP P PBP P P112321243125( ,),( ,),( ,),BP P PBP P PBP P P413551456234( ,),( ,),(,),BP P PBP P PBP P P相应基本解及目标函数值为：相应基本解及目标函数值为：913410235(,),(,)BP P PBP P P不是基。不是基。42 可以看到可以

22、看到B2、B3、B4、B6、B7、B8是是可行基，可行基， B3是最是最优基优基, B1、B5不是不是可行基。可行基。 基基x1x2x3x4x5ZB14 43 3-2-20 00 01717B22 23 30 08 80 01313B34 42 20 00 04 41414B44 40 04 40 012128 8B58 80 00 0-16-1612123232B60 03 32 216160 09 9B70 04 40 016165 51212B80 00 08 8161612120 043 线性规划解的关系图线性规划解的关系图可行解可行解 基可行解基可行解 基本最优解基本最优解44121

23、21212max2328416.412,0Zxxxxxstxx x例例2:2:454 3 2 1 0 x2| | | | |12 3 45x1x1 + 2x2 84x1 164 x2 122x1 + 3x2 5等值线等值线可行域可行域(4,2)CABD最优解最优解X=(4,2)T最优值最优值Z=14Z= 2x1 + 3x2 x1 + 2x2 84x1 164x2 12(1,1)46(2,3)4 3 2 1 0 x2| | | | |12 3 45x1CABD最优解最优解X(1)=(4,2)TX(2)=(2,3)T最优值最优值Z=16(4,2)当当=0.5时时X =0.5(4,2)T+0.5(2

24、,3)T=(3, 2.5)T 12121212max2428416.412,0Zxxxxxs txx x有无穷多个最优解即具有多重解,通解为X=X(1)+(1-) X(2) 01例例3:47246x1x2246最优解最优解X=(3,1)T最优值最优值Z=5(3,1)例例4:1212121212min2364.3600Zxxxxxxstxxxx、48246x1x2246无界解无界解(无最优解无最优解)例例5:1212121212max2364.3600Zxxxxxxstxxxx、49x1x2O10203040102030405050无可行解无可行解即无最优解即无最优解例例6:1212121212

25、max342401.530.500,0Zxxxxxxstxxxx5051由以上例题可知，由以上例题可知，线性规划的解有线性规划的解有4种形式种形式：2.有无穷多最优解有无穷多最优解3.有无界解有无界解4.无可行解无可行解1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.有唯一最优解有唯一最优解52 凸集凸集：设设K是是n维欧氏空间维欧氏空间En的一个点集。若任的一个点集。若任意两点意两点X(1)、X(2)K的连线上的一切点的连线上的一切点X(1)+(1- -)X(2)K，01 ，则称，则称K为为凸集凸集。 53 凸组合凸组合： 设设X(1)、 X(2)、 、X(k)是是n

26、 n维欧氏空间维欧氏空间En的的k k个点，若存在个点，若存在1、 2、 、k ,且且0 i 1, 1+ 2+ +k =1，使得：，使得：X=1X(1) + 2X(2) + +k X(k)则称则称X是是X(1)、 X(2)、 、X(k)的的凸组合凸组合。 顶点顶点： 设设K是凸集，是凸集，XK；若；若X不能用不能用K中中不同的两点不同的两点X(1)、 X(2)的的线性组合表示为：线性组合表示为：则则X 称为称为K的一个的一个顶点顶点(或或极点极点)。X=X(1)+(1- -)X(2)， 0 1 。 X54定理定理1 1：若：若LPLP问题存在可行解，则其可行域问题存在可行解，则其可行域1,0n

27、jjjjDXp xb x证证: 设设(1)(1)(1)(1)12,TnXxxx(2)(2)(2)(2)12,TnXxxx是是D内的任意两点，且内的任意两点，且X(1) X(2)。 是凸集。是凸集。55则有则有 ：(1)(1)1,0,1,2,njjjjp xb xjn(2)(2)1,0,1,2,njjjjp xb xjn令令X=(x1, x2, ，xn)T为为X(1)、 X(2)连线上的任连线上的任意一点，即：意一点，即：X=X(1)+(1- -)X(2)， 0 1 。 X的分量是的分量是xj=xj(1)+(1-1-) xj(2) ，将它代入约束条件，得到将它代入约束条件，得到56(1)(2)1

28、11nnjjjjjjp xp x1bbb(1)(2)11(1)nnjjjjjjjp xpxx又因又因 xj(1)、xj(2) 0，0，1- -0，所以所以xj 0 ，j=1、2 、 、n 。于是于是X为可行解，即为可行解，即D是凸集。是凸集。57 定理定理：如果如果LP问题存在可行解问题存在可行解，则则一定存一定存在在基可行解基可行解。 若若1, 2, ，k线性相关，即存在一组不全线性相关，即存在一组不全为零的数为零的数i ,i=1、2 、 、k （其中至少有一个正（其中至少有一个正数）数）, 使得使得:证证:设设X=(x1 , x2 , , xk , 0 , , 0)T为为可行解可行解，若，

29、若向量向量1, 2, ，k线性无关，则线性无关，则X就是一个就是一个基可基可行解。否则，可通过下列步骤一个构造出一个基行解。否则，可通过下列步骤一个构造出一个基可行解可行解。 由下式定义一个新的点，令由下式定义一个新的点，令1 1220kkPPPX58其中其中于是有于是有,1,2,0,1,jjjjxxjkxjkn min|0jsjjsxx0,1,2,jjjxxjk 特别地特别地：0sssxx 将代入约束条件将代入约束条件X1110nknjjjjjjjjj kAXP xP xP 59110kkjjjjjjP xPbb 由此可见是一个可行解，但的正分由此可见是一个可行解，但的正分量比的量比的正分量

30、少一个。若的正分量所对应正分量少一个。若的正分量所对应的系数列向量是线性无关的，则就是一个基的系数列向量是线性无关的，则就是一个基可行解，如若不然，继续以上步骤直到得到一个可行解，如若不然，继续以上步骤直到得到一个基可行解。基可行解。 XXXX60定理定理3：LP问题的可行解问题的可行解X=(x1 , x2 , , xn)T为基为基可行解的充要条件是可行解的充要条件是X的正分量所对应的系数列的正分量所对应的系数列向量是线性无关的。向量是线性无关的。 证证: 1) 1)必要性：由基可行解的定义可知。必要性：由基可行解的定义可知。 2）充分性充分性：设可行解：设可行解X的的正分量正分量x1,x2,

31、xk所对所对应的列应的列向量向量p1, p2, ,pk线性无关，则必有线性无关，则必有km；当；当k=m时，它们恰好构成一个基，从而时，它们恰好构成一个基，从而X=(x1,x2, ,xk , 0, ,0)T为相应的基可行解。为相应的基可行解。 当当km时，则一定可以从其余的列向量中取出时，则一定可以从其余的列向量中取出m-k个列向量与个列向量与p1, p2, ,pk构成最大的线性无关向量组构成最大的线性无关向量组,其对应的基解恰为其对应的基解恰为X，由定义可知它是基可行解。，由定义可知它是基可行解。61定理定理4 4：线性规划问题的线性规划问题的基可行解基可行解对应于可行域对应于可行域的的顶点

32、顶点。 证：证： 不失一般性，假设可行解不失一般性，假设可行解X的前的前k个分量为正个分量为正。1(1)kjjjP xb现在分两步来证明，分别用反证法。现在分两步来证明，分别用反证法。 1)若若X不是基可行解，则它一定不是可行域的顶点。不是基可行解，则它一定不是可行域的顶点。根据根据定理定理2，若，若X不是基可行解，则其正分量所对应的不是基可行解，则其正分量所对应的列向量列向量p1, p2, ，pk线性相关，即存在一组不全为零线性相关，即存在一组不全为零的数的数i ,i=1、2 、 、k , 使得使得: :故故62用一个用一个0的数乘式的数乘式(2)式再分别与式再分别与(1)式相加式相加和相减

33、，这就得到和相减，这就得到现取现取11220(2)kkPPP111222()()()kkkxPxPxPb111222()()()kkkxPxPxPb(1)1122(),(),(),0,0TkkXxxx(2)1122(),(),(),0,0TkkXxxx由由X(1)、 X(2)可以得到：可以得到：(1)(2)1122XXX即表示即表示X是是X(1)、 X(2)连线的中点。连线的中点。63另一方面，当另一方面，当 充分小时，可保证充分小时，可保证 即即X(1)、 X(2)是可行解。是可行解。 这就证明了这就证明了X不是可行域不是可行域D的顶点。的顶点。(1)(1)(1)(1)12(,)TnXxxx

34、(2)(2)(2)(2)12(,)TnXxxx2) 2) 若若X不是可行域不是可行域D的顶点，的顶点，则它一定不是基则它一定不是基可行解：可行解：0 ,1,2,iixik 因为因为X不是可行域不是可行域D D的顶点，则在可行域的顶点，则在可行域D D中可找到不同的两个点中可找到不同的两个点X(1) X(2) ：使得使得 X=X(1)+(1- -)X(2)， 0 0 时，时， Z02x13x2只要取只要取x1 100或或x2 20 0 , Z Z 的值可能增大。的值可能增大。 2376第第4 4步步 基变换基变换121 1220230zxxxx换入变量 （即选最大检验数对应的变量）一般选取一般选

35、取 对应的变量12(,)max12,xx12,0,均可均可换入。2x77 换出变量换出变量使换入的变量越大越好使换入的变量越大越好同时，新的解要可行。同时，新的解要可行。选非负选非负的最小者对应的变量换出的最小者对应的变量换出312415282164 12 4 xxxxxxx2x为换入变量，应换出为换入变量，应换出 ？ 变量。变量。为换出变量变量：为换入变量，确定换出522542323) 4/12, , 2/ 8min( 04 12 0 16 02 8 xxxxxxxx22min0min(8/2, ,12/4)3kkkbaa思考：思考： 当当a/k2k20 0 时会怎时会怎样？样？5min(8

36、/2, ,12/4)3x为换出变量78 转第转第2步：基变量用非基变量表示。步：基变量用非基变量表示。 第第3步：最优性判断步：最优性判断 检验数检验数 存在正，按第存在正，按第4步换基继续迭代步换基继续迭代 均非正，停止均非正，停止 （这时的解即是最优解）（这时的解即是最优解）2x为换入变量，应换出为换入变量，应换出 变量。变量。为换出变量变量：为换入变量，确定换出522542323) 4 /12, , 2 / 8min( 04 12 0 16 02 8 xxxxxxxx1342()BPPP因此，基由因此，基由 0345()BPPP变为变为79转转 第第2步步进基315412512 2164

37、 1 3 4xxxxxxx153 924Zxx代入目标函数15342(1)0,2,16,3(0,3,2,16,0)TxxxxxX令：则得一基可行解312415282164 12 4 xxxxxxxZ02x13x2803154125122164 1 3 4xxxxxxxmin(2 1,16 4, )2 13,xx故 进基出基因此，基由因此，基由 l确定换出变量确定换出变量1342()BPPP2142()BPPP变为变为811352435125428423xxxxxxxx135142(2)0,2,8,3(2,3,0,8,0)TxxxxxX令：则得一基可行解进基进基153154125392412 2

38、164 1 3 4Zxxxxxxxxx351 1324Zxx代入目标函数基变量用非基变量表示为：基变量用非基变量表示为：82148min( ,3)4254,xx故 进基出基1352435125428423xxxxxxxx1l确定换出变量确定换出变量因此，基由因此，基由 2142()BPPP3152()BPPP变为变为831441534211234284422xxxxxxxx134152(3)0,4,4,2(4,2,0,0,4)TxxxxxX令：得一基可行解0最优解最优解14Z 最优值1352435125428423xxxxxxxx13431 1428Zxx代入目标函数3511324Zxx基变量

39、用非基变量表示为：基变量用非基变量表示为：84下面我们用矩阵的初等变换来表示上述求解过程。下面我们用矩阵的初等变换来表示上述求解过程。 12345 b 812100164001001200014230000PPP P PbAC12345121434 b 2010164001030100900120PPPPP12345121144 b 2101080041301001300220PPPPP12345141211283128 b 4100040021201014000PPPPP85 x2x1(1)(0,3,2,16,0)TX 结合图形法分析(单纯形法的几何意义)(0) (0,0,8,16,12)

40、TXA(0,3)B(2,3)C(4,2)O(0,0)(0)(0,0,3,16,12)X(2)(2,3,0,8,0)TX(3)(4,2,0,0,4)TX86 为书写规范和便于计算，对单纯形法为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。下面介绍用单纯形表称为最终单纯形表。下面介绍用单纯形表计算线性规划问题的原理。表计算线性规划问题的原理。87 设设 是一个可行基，是一个可行基，

41、12( )mBP PP1 12211 11221121 1222221 12212max .,.,0 nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xbs taxaxaxbx xx88121111121111221222212121 mmnmmnmmnmmmmmmmmnbxxxxxbaaaaabaaaaabaaaaa初等行变换初等行变换89用矩阵表示为：用矩阵表示为：1111()()()Bb ABb BB b I B N N121111122121 111mmnmnmnmmmmnbxxxxxbaabaabaa112212, ,0mmmmxb xbxbxxxn

42、由此得基可行解：由此得基可行解：是否为最优，是否为最优，如何由表得到如何由表得到判断？判断？90( ,)BNXAXB NbX(,) BBNBBNNNXZCCC XC XX检验数的计算：检验数的计算：BNBXNXb11BNXB bB NX11()BNNNCB bB NXC X11()NBBNCCBXCbB N0NNZX911(1,2, )jjBjcC B Pjmmn110(1,2,)iiBiiBcC B PcCim 1(1,2, )iiBicC B P in非基变量的检验数为：非基变量的检验数为：基变量的检验数为：基变量的检验数为：故所有变量的检验数统一表示为：故所有变量的检验数统一表示为：92

43、 单纯形表：单纯形表：1211111221210121 11 1mmnmnmnmmmmnmmnbxxxxxbaabaabaazE单位阵单位阵B-1N非基阵非基阵基变量基变量XB非基变量非基变量XNN01111BBB bB AC B bCC B A11110BNBB bIB NC B bCC B N93xxxxmn12 2 1 0 0 0 jc BCbBX检验数 1mbbxxm1ccm1单纯形表结构 单纯形表单纯形表 24/65/1minA0znmcccc21C94xxxxmn12 2 1 0 0 0 24/65/1C检验数1 mbbxxm1ccm1单纯形表结构 单纯形表单纯形表A0z1( ,0

44、,0)TmXbb基可行解：jc BCbBXmin95单纯形表结构 单纯形表单纯形表xxxxmn12 2 1 0 0 0 24/65/1C检验数1mbbxxm1ccm1A0z10BCZB bjc BCbBXmin96单纯形表结构单纯形表结构xxxxmn12 2 1 0 0 0 24/65/1C检验数bbm1xxm1ccm1A0zjcmjjaa1jjc BCbBXmin00 iijiiji Bi Bjjjjji Bzcbzc aczZZx令：令：检验数 单纯形表单纯形表97单纯形表结构 单纯形表单纯形表xxxxmn12 2 1 0 0 0 24/65/1C检验数 1mbbxxm1ccm1A0zkm

45、mkmaa, 1km 0设此设此为主列为主列0minilimkiimklmkbbaaal主行主行jc BCbBXmin98单纯形表结构单纯形表结构 单纯形表单纯形表xxxxmn12 2 1 0 0 0 24/65/1C检验数 1mbbxxm1ccm1Akmmkmaa, 1km lkmla,主元主元jc BCbBXmin0z99max , b0 . 0ZCXAXbstX对资源约束模型对资源约束模型100max0 . ,0sssZCXXAXI XbstX X 化标准型后化标准型后()AA I易知易知 B B = =I I 是可行基。是可行基。对应对应00bAIC101用单纯形表求解LP问题1221

46、21212max25156224.5,0Zxxxxxs txxxx例例2:2: 用单纯形表求解用单纯形表求解LPLP问题问题102解解: : 化标准形化标准形123452312412515max20005156224.5,0Zxxxxxxxxxxstxxxxx则则B=(P3 P4P5)是一个可行基。是一个可行基。初始单纯形表为：初始单纯形表为：103cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 min 0 0 0 x3 x4 x5 15 24 5 0 6 1 5 2 1 1 0 0 0 1 0 0 0 0 0 1 24/6 5/1 cj- -zj 0 2 1 0 0

47、0 0 0 主元化为1主列单位向量x4换出,x1换入表表1：列初始单纯形表：列初始单纯形表 （单位矩阵对应的变量为基变量）（单位矩阵对应的变量为基变量）检验数中最大者检验数中最大者对应的列为主列对应的列为主列104cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 min 0 0 0 x3 x4 x5 15 24 5 0 6 1 5 2 1 1 0 0 0 1 0 0 0 0 0 1 24/6 5/1 cj- -zj 0 2 1 0 0 0 0 0 0 2 0 x3 x1 x5 15 4 1 0 1 0 5 1/3 2/3 1 0 0 0 1/6 - -1 1/ /6 6

48、0 0 0 1 15/5 12/1 3/2 cj- -zj -8 0 1/3 0 - -1 1/ /3 3 0 0 表表2：换基：换基 （初等行变换，主列化为单位向量，主元为（初等行变换，主列化为单位向量，主元为1）1050检验数最优解为最优解为X=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)T T最优目标函数值最优目标函数值maxZ=17/2maxZ=17/2106问题：线性规划问题：线性规划问题化为标准形时，问题化为标准形时，若约束条件的系数若约束条件的系数矩阵中不存在单位矩阵中不存在单位矩阵，如何构造矩阵，如何构造初始可行基？初始可行基？ 107112211

49、11221121122222112212 Z.,.,0nnnnnnmmmnnmnmaxc xc xc xa xaxaxbaxaxaxbs taxaxaxbxxx加入加入人工变量人工变量设线性规划问题的标准形为：设线性规划问题的标准形为：10811 112211121 12222221 122121,. . . ,.,.,nnnnnnmmmnnn mmnnn ma xa xa xxba xa xa xxba xa xa xxbx xx xx0加入人工变量加入人工变量, ,构造初始可行基构造初始可行基. .109是一初始基可行解。则：为非基变量，为基变量，令： ),.,0,.0 ,0(,., ,.

50、,21)0(2121TmnmnnnbbbXxxxxxx约束条件已改变，目标函数如何调整？1101 1、大、大 M M 法法目标函数中添加目标函数中添加“罚因子罚因子”-M-M（M M是任意大的正数）是任意大的正数）为人工变量系数，只要人为人工变量系数，只要人工变量工变量00，则目标函数，则目标函数不可能实现最优不可能实现最优。人工变量在目标函数中的系数为人工变量在目标函数中的系数为 - -M, 其中，其中，M 为任意大的正数。为任意大的正数。1110.,., . . ., 1212211222222121111212111mnnnmmnnmnmmnnnnnnxxxxxbxxaxaxabxxax

51、axabxxaxaxa1 1221 Z.nnnn mmaxc xc xc xMxMx构造新的线性规划：构造新的线性规划：112目标函数中添加目标函数中添加“罚因子罚因子”-M-M为人工变量系数，只要人为人工变量系数，只要人工变量工变量00，则目标函数，则目标函数不可能实现最优。不可能实现最优。求解结果出现检验数非正求解结果出现检验数非正 .用单纯形法求解用单纯形法求解1) 若基变量中含非零的人工变量，若基变量中含非零的人工变量， 则原问题无可行解；则原问题无可行解；0j2) 若基变量中不含非零的人工变量，若基变量中不含非零的人工变量，则原问题有最优解。则原问题有最优解。113123123123

52、131233 2 114 23.2 1,0minZxxxxxxxxxstxxx x x 例例3: 求解线性规划问题求解线性规划问题11412345123412351312345max3002 11423. 2 1,0Zxxxxxxxxxxxxxstxxx x x x x 解解: :加入松弛变量标准化为：加入松弛变量标准化为：1151234567max300ZxxxxxMxMx l加入人工变量构造初始可行基加入人工变量构造初始可行基. . 1234123561371234567 2 1142 3. 2 1,0 xxxxxxxxxstxxxx x x x x x x则则B=(P4 P6 P7)是一

53、个可行基（人造基）是一个可行基（人造基）借用为基变量借用为基变量初始单纯形表为：初始单纯形表为：1(1,2, )jjBjcC B Pjn检验数为116表表1（初始单纯形表）（初始单纯形表）cj- -zj 4 M 3 -6 M -1 + M -1 + 3 M 0 -M 0 0 117118检验数均非正，此为检验数均非正，此为最终单纯形表最终单纯形表最优解为最优解为X=(4,1,9,0,0)T ，原规划最优目标函数值原规划最优目标函数值minZ=-2max2Z 1192 2、两阶段法、两阶段法M在计算机上在计算机上处理处理困难。困难。分阶段处理分阶段处理先求先求初始可行基，初始可行基，再求解。再求

54、解。1201211 112211121 12222221 12212 . . . ,.,mnnnnmmmnnmmminyyya xa xa xyba xa xa xybsta xaxa xybx xx1,.,0nmyy 目标函数仅含目标函数仅含人工变量，并要求人工变量，并要求实现最小化。实现最小化。 若其最优解的若其最优解的目标函数值不为目标函数值不为0，也即最优解的基，也即最优解的基变量中含有非零的变量中含有非零的人工变量，则原线人工变量，则原线性规划问题无可行性规划问题无可行解。解。第一阶段第一阶段: : 构造如下的线性规划问题构造如下的线性规划问题 （称为辅助规划）（称为辅助规划） 12

55、1 1) 若若0，则原问题无可行解。，则原问题无可行解。2) 若若=0，进入第二阶段。，进入第二阶段。a. 若基变量中不含人工变量，则此最优若基变量中不含人工变量，则此最优基就是原问题的一个可行基；基就是原问题的一个可行基；b. 若基变量中含有人工变量，则还原为若基变量中含有人工变量，则还原为方程方程:0rrjjrn iijiya xay用单纯形法求解用单纯形法求解122若这时所有的若这时所有的 全为全为0.即即 则表明原问题中第则表明原问题中第r个方程是多余的，可以去个方程是多余的，可以去掉掉多余方程多余方程。0rrn iiiyay求和式中的变量皆为非基变量求和式中的变量皆为非基变量.rja

56、 若至少有某个若至少有某个 不为不为0.则以其为主元做则以其为主元做换基迭代换基迭代,可将可将yr从基变量中去掉从基变量中去掉.rja123例例4：123123123131233 2 114 23.2 1,0minZxxxxxxxxxstxxx x x 124解解: :加入松弛变量标准化为：加入松弛变量标准化为：12345123412351312345max3002 11423. 2 1,0Zxxxxxxxxxxxxxstxxx x x x x 125671234123561371234567 min 2 114 2 3.2 1,0 xxxxxxxxxxxstxxxx x x x x x x构

57、造第一阶段辅助规划并求解构造第一阶段辅助规划并求解则则B=(P4 P6 P7)是一个可行基（人造基）是一个可行基（人造基）初始单纯形表为：初始单纯形表为：1(1,2, )jjBjcC B Pjn检验数为126cj 0 0 0 0 0 -1 -1 CB XB b x1 x2 x3 x4 x5 x6 x7 min 0 -1 -1 x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 0 0 1 11/1 3/2 1/1 cj- -zj 0 0 0 0 0 -1 -1 0 -1 0 x4 x6 x3 10 1 1 3 0 -2 -2

58、1 0 0 0 1 1 0 0 0 -1 0 0 1 0 - -1 1 -2 1 1/1 cj- -zj 1 0 1 0 0 -1 0 - -3 3 第一阶段、求第一阶段、求min cj- -zj 4 -6 1 3 0 -1 0 0 127得到辅助规划的最终表，由此进入第二阶段。得到辅助规划的最终表，由此进入第二阶段。128辅助规划的最终表辅助规划的最终表不含人工变量不含人工变量且且=0=0129cj 3 -1 -1 0 0 CB XB b x1 x2 x3 x4 x5 min 0 -1 -1 x4 x2 x3 12 1 1 3 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 1

59、2/3 cj- -zj 3 -1 -1 0 0 130最优解为最优解为X=(4,1,9,0,0)T ，原规划最优目标函数值原规划最优目标函数值minZ=-2检验数均非正，此为检验数均非正，此为最终单纯形表最终单纯形表max2Z 131 例：例：某工厂利用三种资源生产两种产品，某工厂利用三种资源生产两种产品， 有关数据如下表有关数据如下表：一、对偶问题的提出一、对偶问题的提出原料原料A原料原料B设备设备C利润利润(百元百元)0612521115公斤公斤24公斤公斤 5台时台时产品产品产品产品资源限量资源限量132如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家设设 产量产量 产量产量1

60、x2x122121212m ax251 5622 4. 5 ,0zxxxxxs txxxx厂家考虑将资源转让出去？厂家考虑将资源转让出去？133 设：原料设：原料A A 百元公斤百元公斤 原料原料B B 百元公斤百元公斤 设备设备C C 百元台时百元台时1y2y3y收收购购方方 付出的代价最小，付出的代价最小， 且让对方能接受。且让对方能接受。出让收益应不低于出让收益应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。134 原料原料A 原料原料B设备设备C利润利润(百元百元)0612521115公斤公斤24公斤公斤 5台时台时资源限量资源限量 厂家能接受的条件：厂家能接受