运筹学第二章 线性规划2.1-2

1、第章线性规划第章线性规划2.1线性规划的模型与图解法线性规划的模型与图解法2.2单纯形法单纯形法2.1 线性规划的模型与图解法线性规划的模型与图解法2.1.1问题的引入问题的引入l如何合理使用有限的人力，物力和资金，如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。使得收到最好的经济效益。 某工厂可生产甲、乙两种产品，需消耗煤、电、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：油三种资源。现将有关数据列表如下： 试拟订使总收入最大的生产方案。试拟订使总收入最大的生产方案。资源单耗产品资源单耗产品 资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 44 5

2、 3 10360200300单位产品价格单位产品价格 7 12121212121212xx kgmaxZ7x12x9x4x3604x5x2003x10 x300 x ,x0设甲乙产品产量分别为 和决策变量则目标函数约束条件 甲甲 乙乙 资源限量资源限量 煤煤(t) 9 4 360 电（电（kwh) 4 5 200 油（油（t） 3 10 300 单价（万元）单价（万元） 7 12l如何合理地搭配（混合）材料，以最经如何合理地搭配（混合）材料，以最经济的方式，达到配比要求。济的方式，达到配比要求。（3 3）下料问题）下料问题l如何截取原材料，在达到截取要求的情如何截取原材料，在达到截取要求的情况

3、下，使废料最少况下，使废料最少料长料长7.47.4米，截成米，截成2.92.9、2.12.1、1.51.5米各米各200200根。根。如何截取余料最少？如何截取余料最少？ 方案方案料型料型 1 2 3 4 5 2.9米米 2.1米米 1.5米米 1 2 0 1 0 0 0 2 2 1 3 1 2 0 3 合计合计 残料残料 7.4 7.3 7.2 7.1 6.6 0 0.1 0.2 0.3 0.8(j(j=1,2,3,4,5)=1,2,3,4,5)+0.8x+0.8x5 5 练习练习1 1：某畜牧厂每日要为牲畜购买饲料以使其获取某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场

4、上可选择的饲料有四种养分。市场上可选择的饲料有M、N两种。两种。有关数据如下：有关数据如下：试决定买试决定买M与与N二种饲料各多少公斤而使支出的总费用二种饲料各多少公斤而使支出的总费用为最少？为最少？410售价 0.4 0.6 2.0 1.7牲畜每日每头需要量 0 0.1 0.2 0.1N 0.1 0 0.1 0.2 M每公斤含营养成分 A B C D饲料解：设购买M、N饲料各为 ，则 12104min zxx12121212120.100.400.10.60.10.22.00.20.11.7,0 xxxxxxxxx x21,xx2.1.2 线性规划的一般模型与标准型线性规划的一般模型与标准型

5、一、一般模型一、一般模型规划问题的数学模型包含三个组成要素：规划问题的数学模型包含三个组成要素：（1）决策变量）决策变量：指决策者为实现规划目标：指决策者为实现规划目标采取的方案措施，是问题中要确定的未采取的方案措施，是问题中要确定的未知量。知量。（2）目标函数：）目标函数：指问题要达到的目的要求，指问题要达到的目的要求，表示为决策变量的函数。表示为决策变量的函数。（3）约束条件：）约束条件：指决策变量取值时受到的指决策变量取值时受到的各种可用资源的限制，表示为含决策变各种可用资源的限制，表示为含决策变量的等式或不等式。量的等式或不等式。 1 12211 11221121 1222221 12

6、212max(min)( , )( , )( , ),( )0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xa xa xbx xx 一般地，线性规划模型一般地，线性规划模型： 简记为：简记为：11max(min)( , ) 1,2,( )0 1,2,njjjnijjijjZc xa xbimxjn 矩阵表示为：矩阵表示为： 12121211121212221212max(min)()( )( ,)( ,)( ,)( ,.,) nTnTmnnnmmmnZc ccx xxb bbaaaaaaP PPaaa CXAXbX0CXbA其中：价值系数向量决策变

7、量向量资源向量技术系数矩阵例1：123123123123123123123min425742410,0min(4, 2,1)5714124100Zxxxxxxxxxx x xxZxxxxxxxx矩阵表示为：二、线性规划问题的标准形式二、线性规划问题的标准形式标准形式要求：标准形式要求：（1）目标最大化（）目标最大化（max）（2）约束是）约束是“=”约束约束（3）右端项非负）右端项非负（4）所有变量非负）所有变量非负标准型标准型0)0(maxXbbAXCXZ化标准型：化标准型：(1)minZ=2x1+4x2 (令令Z=-Z) maxZ=-2x1-4x2(2)-x1+x2+4x32 (引入松弛变

8、量引入松弛变量x4) -x1+x2+4x3+x4=2 松弛变量的意义：未被充分利用的资源（松弛变量的意义：未被充分利用的资源（c4=0）(3)-x1+x2+4x32 (引入剩余变量引入剩余变量x5) -x1+x2+4x3-x5=2 剩余变量的意义：超用的资源（剩余变量的意义：超用的资源（c5=0） (4)xj0 (令令xj=-xj) xj0(5)xj为自由变量为自由变量 (令令xj=xj-xj) xj0,xj0例例2：将下面的线性规划模型化为标准型：将下面的线性规划模型化为标准型为自由变量321321321321321, 0, 06454273273minxxxxxxxxxxxxxxxZ ,:

9、33311xxxxxZZ令解引入松弛变量x4,剩余变量x5思考题：思考题：1、松弛变量、松弛变量(剩余变量剩余变量)的实际意义是什么？的实际意义是什么？2、松弛变量、松弛变量(剩余变量剩余变量)在目标函数中的系数是多少？在目标函数中的系数是多少？为自由变量321321321321321, 0, 06454273273minxxxxxxxxxxxxxxxZ0, , , 6 4454 27 33200 773max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ则：练习：将下面的线性规划模型化为标准型练习：将下面的线性规划模型化为标准型0,

10、 0894232515579min321321321321321xxxxxxxxxxxxxxxZ为自由变量0, , , ,89 423 225155 77009 max54322153221322143221543221xxxxxxxxxxxxxxxxxxxxxxxxxxZ ,:22233xxxxxZZ令解0, 0894232515579min321321321321321xxxxxxxxxxxxxxxZ为自由变量x1,x2,x3为实际变量x4为剩余变量x5为松弛变量广义松弛变量引入剩余变量x4,松弛变量x52.1.3 线性规划模型的图解法（适用于线性规划模型的图解法（适用于2个变个变量的一般

11、型）量的一般型）一、线性规划问题的解的概念一、线性规划问题的解的概念 设线性规划问题的一般型为设线性规划问题的一般型为0)(),(max(min)XbAXCXZ（1）可行解：满足全部约束条件的决策变量）可行解：满足全部约束条件的决策变量X为可行解；全为可行解；全 部可行解的集合部可行解的集合R称为可行解域。称为可行解域。（2）最优解：使目标函数为最大（或最小）的可行解）最优解：使目标函数为最大（或最小）的可行解X*。二、线性规划的图解法二、线性规划的图解法图解法步骤：图解法步骤：（1）根据约束条件画出可行解域；）根据约束条件画出可行解域；（2）画出目标函数的等值线；）画出目标函数的等值线；（3

12、）求出最优解。）求出最优解。x1x209040405030100Dl1l2l30,3001032005436049127max) 1 (2121212121xxxxxxxxxxZ例例3 用图解法求解下列线性规划问题用图解法求解下列线性规划问题可行域可行域目标函数等值线目标函数等值线A有唯一最优解（顶点有唯一最优解（顶点D）解直线解直线l2,l3组成的线性方程组成的线性方程组得：组得：X*=(20,24)T最优生产最优生产方案方案Z*=720+1224=428最大收入最大收入(2)在模型在模型(1)中，目标函中，目标函数改为数改为 maxZ=3x1+10 x2，其，其他不变。他不变。 易知，目标

13、函数等值易知，目标函数等值线与直线线与直线l3平行，平行， 故线段故线段AD上的点均为上的点均为最优解。最优解。 有无穷多最优解有无穷多最优解 x209040405030100Dl1l2l3AX10,164127max)3(21121xxxxxZx1x204可行域无界，在可行域可行域无界，在可行域上没有使目标函数值为上没有使目标函数值为有限的最优解。有限的最优解。无有限最优解（无界解）无有限最优解（无界解）0,2212max)4(21212121xxxxxxxxZ1x2012x1-1不存在所有约束条件的不存在所有约束条件的公共范围公共范围无可行解无可行解小结：（1）线性规划问题解的情况在可行域

14、某条边上达到多重在可行域某顶点处达到唯一有最优解有限最优解可行域无界，且达不到无界解无最优解可行解公共范围不存在所有约束条件的无可行解: )(:（2）线性规划问题解的线性规划问题解的两个重要结论两个重要结论l 线性规划的可行域是凸多面体线性规划的可行域是凸多面体l 线性规划的最优解在可行域的顶点上线性规划的最优解在可行域的顶点上凸多面体凸多面体凹多面体极点（顶点）u思考题思考题:约束条件不等式的几何意义是什么？约束条件不等式的几何意义是什么？怎样做图？怎样做图？2.2单纯形法（适用于多个变量的标准型）单纯形法（适用于多个变量的标准型）2.2.1单纯形法的原理与基本概念单纯形法的原理与基本概念一

15、一.原理原理 单纯形法是一种迭代算法，它利用线性单纯形法是一种迭代算法，它利用线性规划最优解在可行域顶点上达到这一结论。规划最优解在可行域顶点上达到这一结论。首先确定一个初始顶点，用某种方法判别它首先确定一个初始顶点，用某种方法判别它是否最优解，若不是最优解，则设法去寻找是否最优解，若不是最优解，则设法去寻找一个更好的顶点。由于顶点个数是有限的，一个更好的顶点。由于顶点个数是有限的，经过有限次迭代后，必达到最优点。经过有限次迭代后，必达到最优点。0maxXbAXCXZ为：设线性规划的标准形式mARmnPPPaaaaaaaaaAnmnmmnn)()(),.,(.21212222111211二二.

16、基本概念基本概念1.基与基变量基与基变量基基( (又称基矩阵又称基矩阵):):A A中的中的m m阶可逆子阵，记为阶可逆子阵，记为B(|B|0)B(|B|0)其余部分称作非基，记为其余部分称作非基，记为N N基向量基向量: :基基B B中的列中的列P Pj j非基向量非基向量: :非基非基N N中的列中的列p pj j基变量基变量: :与基向量同下标的变量与基向量同下标的变量x xj j，记作，记作X XB B( (有有m m个分量个分量) )非基变量非基变量: :与非基向量同下标的变量，记作与非基向量同下标的变量，记作X XN N( (有有n-mn-m个个分量分量) )2.基本解与基本可行解

17、基本解与基本可行解基本解：基本解：令非基变量为令非基变量为0，所得到的解，称为基本解。，所得到的解，称为基本解。基本可行解：基本可行解：非负的基本解称为基本可行解，它所非负的基本解称为基本可行解，它所 对应的基为可行基对应的基为可行基。=目标函数约束条件行列式0基矩阵右边常数)4 , 3 , 2 , 1(032124421321jxxxxxxxj：某线性规划约束例),(10120121A4321pppp系数矩阵1221N1001B11非基可取基21 43P,P P,P非基向量：基向量：T21NT43B2143)x,(xX )x,(xXx,x x,x非基变量：基变量：思考题：一个思考题：一个mn

18、阶系数阵阶系数阵A中基的个数最多为多少？中基的个数最多为多少？例例5：某线性规划约束中：某线性规划约束中11112131213122(1)1122,1211112,121( ,)230,211(3, 1,0)TBNTAbBNXx xXxxxxxxxxX 如取基非基基变量，非基变量令则方程组变为基本解22213221312313(2)2121,112( ,)2200,11(0,0,1),BTBNTBNXx xXxxxxxxxxX 如取基非基基变量，非基变量令则方程组变为基本可行解为可行基例6x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1 +3x2 +x3 +x4 =1

19、5 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3 基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基本解为（基本解为（x1，x2，x3，x4，x5，x6）T=（5，3，1，0，0，0）T是基本可行解，表示可行域的一个极点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=20 x1+3x2+x4=152x1+3x2=18x1-x2=3基变量基变量x1、x2、x4，非基变量，非基变量x3、x5、x6基本解为基本解为（x1，x2，x3，x4，x5，x6）T=（27/5，12/5，0，2/5，0，0）T是基本可行解，表示可行域的一个极

20、点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=18x1+3x2=152x1+3x2+x5=18x1-x2=3基变量基变量x1、x2、x5，非基变量，非基变量x3、x4、x6基本解为（基本解为（x1，x2，x3，x4，x5，x6）T=（6，3，0，0，-3，0）T是基本解，但不是可行解，不是一个极点。是基本解，但不是可行解，不是一个极点。x1+3x2=152x1+3x2=18x1-x2+x6=3基变量基变量x1、x2、x6，非基变量，非基变量x3、x4、x5基本解为（基本解为（x1，x2，x3，x4，x5，x6）T=（3，4，0，0，0，4）T是基本可行解，表示可行域的

21、一个极点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量基变量x2、x3、x4，非基变量，非基变量x1、x5、x6基本解为基本解为（x1，x2，x3，x4，x5，x6）T=（0，21/2，27/2，-30，0，0）T是基本解，但不是可行解是基本解，但不是可行解。3x2+x3=153x2-x3+x5=18-x2+x3=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基本解为（基本解为（x1，x2，x3，x4，x5，x6）T=（0，3，6，0，15，0）T是基本

22、可行解，表示可行域的一个极点。是基本可行解，表示可行域的一个极点。目标函数值为：目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基变量基变量x1、x2、x3，非基变量，非基变量x4、x5、x6基本解为基本解为（x1，x2，x3，x4，x5，x6）T=（0，11/2，-3/2，0，0，10）T是基本解但不是可行解。是基本解但不是可行解。三三.两个重要结论：两个重要结论：（1）可行域的顶点一定是基本可行解）可行域的顶点一定是基本可行解（2）最优解存在，一定在基本可行解处达到）最优

23、解存在，一定在基本可行解处达到思考题：四个重要结论有何重要意义？思考题：四个重要结论有何重要意义？几何概念几何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交集约束半平面的交集(凸多边形凸多边形)满足一组不等式约束的解满足一组不等式约束的解约束直线的交点约束直线的交点基本解基本解可行域的极点可行域的极点基本可行解基本可行解目标函数等值线目标函数等值线(一组平行线一组平行线) 目标函数值等于一个常数的解目标函数值等于一个常数的解2.2.2单纯形法的步骤单纯形法的步骤枚举法枚举法:找出所有基本

24、可行解找出所有基本可行解比较其目标函数值比较其目标函数值最大者最大者 最优最优单纯形法单纯形法: :找出一个基本可行解找出一个基本可行解检验其是否最优检验其是否最优是是停止停止 否否 再找一个更好的基本可行解再找一个更好的基本可行解1.1.确定一个初始基本可行解确定一个初始基本可行解 法大位阵，仍取中不含单位阵，人造单中含单位阵，取取初始可行基MIBAIBAB000与与B0对应的解称之为初始基本可行解。对应的解称之为初始基本可行解。2.检验一个基本可行解是否最优检验一个基本可行解是否最优 不妨取可行基为不妨取可行基为B=(P1,P2,Pm) 则则N=(Pm+1,Pm+2,Pn) 系数阵：系数阵

25、：A=(B,N)TNBXXX),(可行解非基变量基变量TnmNTmBXxXxxX),.,(),.,(11),(NBCCC 价值系数),.,(),.,(11nmNmBccCccCbAX 由bXXN)(B,NB则bBNXBX-1N-1BN-1-1BNXB-bBX bNXXNB BNNBBNBNBXCXCXXCCZ),(则CXZ 由NNNXCNXBbBC)(11BNBNBXNBCCbBCz)(11),.,(11nmBNNNBCC记),.,1(1nmjPBCCjBjj-非基变量的检验数非基变量的检验数-第j个非基变量的检验数非基变量的检验数最最优优0 0b bB BX X可可行行解解当当前前基基此此时

26、时, ,可可使使Z Z最最大大，0 0时时, ,0 0时时，只只有有当当X X若若1 1N NN N本1BNNZC B bX1BCbAXB两边左乘以进一步地，将bBCAX-1B1BCB则A)XBC-(Cb-1B1BCBAX)BC-b(-1B1BCCXCXZB),.,(ABC-C21-1Bn记变量变量X的检验数的检验数),.,2 , 1(PBC-C-1Bjnjjj第第j个变量个变量xj的检验数的检验数当当j j0 0时时, ,基本可行解基本可行解X=(BX=(B-1-1b,0)b,0)T T达到最优达到最优解解, ,否则将寻找一个更好的基本可行解否则将寻找一个更好的基本可行解.3.寻找一个更好的

27、基本可行解寻找一个更好的基本可行解(1)原理原理 基变换基变换设设A=(p1,pl,pm, pm+1,pm+2,pk,pn) x1,xl,xm, xm+1,xm+2, ,xk, xn 当前基当前基 换基方式换基方式:换基原则换基原则: 解仍可行（解仍可行（XB0）换出原则换出原则当前非基当前非基先先换入一列换入一列pk 相应的相应的xk称为进基变量称为进基变量后换出一列换出一列pl 相应的相应的xl称为出基变量称为出基变量改善改善Z新新比比Z旧旧好好换入原则换入原则(2)基变换法基变换法进基对应的时，取求kjkpZ0maxmax 保证目标函数增加更快保证目标函数增加更快检验数的意义：非基变量每

28、增加一个单位，目标函数增加的量。检验数的意义：非基变量每增加一个单位，目标函数增加的量。出基对应的取likikiilppBpBbB0)( |)()(min111保证保证XB0得新基后转入第二步。得新基后转入第二步。=目标函数约束条件基矩阵右边常数=基变量图示：=进基变量离基变量目标函数约束条件右边常数=目标函数约束条件新的基矩阵右边常数=进基变量离基变量目标函数约束条件基矩阵=目标函数约束条件新的基矩阵右边常数=思考题：思考题：1.最优性用什么来检验？检验数公式最优性用什么来检验？检验数公式? 2.检验数的意义是什么？检验数的意义是什么？2.2.3 单纯形表单纯形表 对每个确定的可行基对每个确

29、定的可行基B，单纯形表的结构为：，单纯形表的结构为： CjC1 C2 CnCB XB B-1bx1 x2 xnCB XB bP1 P2 Pn j1 2 n其中其中:CB基变量所对应的价值系数基变量所对应的价值系数 XB基变量基变量 b=B-1b Pj=B-1Pj j=Cj-CBB-1Pj(j=1,2,.,n) B=0基变量的检验数基变量的检验数0,3212max121212121xxxxxxxxZ）（例例7 用单纯形法求解下列线性规划问题用单纯形法求解下列线性规划问题0,321200max43214213214321xxxxxxxxxxxxxxZ解：化为标准型初始单纯形表为：初始单纯形表为：0

30、) 3 , 1 , 0 , 0(1001),()0()0(10104300ZXCpBCCbbBPPBTjjBjjX2进基32103021321222242304213211xxxxxxxxxxxxx(2=10),相应的系数列为主元列2为主元素为主元素X3出基用消元法得到新的单纯型表用消元法得到新的单纯型表单纯型表的简化计算单纯型表的简化计算 -对角法则对角法则272) 1(13252) 1(12212) 1(10对角法则的解释：第k列第j列第l行blalkaij第i行biaikaljbl/alk0alj/alkbi-blaik/alk1aij-aikalj/alkaikalkaljaijaij

31、=aij-aikalj/alk Cj -1 1 0 0 CB XB B-1b X1 X2 X3 X4 0 X3 1 1 2 1 0 0 X4 3 2 -1 0 1 j -1 1 0 0 2/1)27, 0 ,21, 0(272131121021121021,1102),()1()1(111421ZXbBbBPPBTTZX2/1)27, 0 ,21, 0(*最终单纯形表N00中最大者所对应的变量先进基，未必是最快中最大者所对应的变量先进基，未必是最快的。的。X*0 x1x2用单纯形法求解线性规划问题用单纯形法求解线性规划问题适用条件适用条件:典则式模型典则式模型0maxXbAXCXZ基本步骤基本

32、步骤:一一.化标准型化标准型二二.填写初始单纯型表填写初始单纯型表三三.判断当前基本可行解是否最优判断当前基本可行解是否最优判别条件判别条件:j0(j=1,2,n)或或N0若存在某若存在某k0,则确定进基变量则确定进基变量方法方法:取正检验数中最大者对应的变量为进取正检验数中最大者对应的变量为进基变量基变量.四四.确定出基变量确定出基变量方法方法:采用最小比值判别法采用最小比值判别法用用B-1b中的元素除以主元列中正的系数取最中的元素除以主元列中正的系数取最小比值小比值,其对应的变量作为出基变量其对应的变量作为出基变量.五五.用初等行变换法将主元列中的主元素化用初等行变换法将主元列中的主元素化

33、为为1,其余元素化为其余元素化为0,得到新单纯型表得到新单纯型表.六六.重复第重复第3步步,直到直到j0为止为止.0,102515535 . 2max221212121xxxxxxxxZ）（0,10251553005 . 2max43214213214321xxxxxxxxxxxxxxZ解：化为标准型 Cj 2.5 1 0 0 CB XB B-1b X1 X2 X3 X4 0 X3 15 3 5 1 0 0 X4 10 5 2 0 1 j 2.5 1 0 0 TZX5)0,9 ,0,2(*最优解为N0, 有最优解 Cj 2.5 1 0 0 CB XB B-1b X1 X2 X3 X4 0 X3

34、 9 0 19/5 1 -3/5 2.5 X1 2 1 2/5 0 1/5 j 0 0 0 -1/2 进一步，让进一步，让x2进基，进基，x3出基出基 Cj 2.5 1 0 0 CB XB B-1b X1 X2 X3 X4 1 X2 45/19 0 1 5/19 -3/19 2.5 X1 20/19 1 0 -2/19 5/19 j 0 0 0 -1/2 N0, 有最优解TZX5)0 , 0 ,19/45,19/20(*最优解为N0且N中至少有一个为0，有无穷多最优解0,42122max321212121xxxxxxxxZ）（0,4210022max43214213214321xxxxxxxx

35、xxxxxxZ解：化为标准型 Cj 2 2 0 0 CB XB B-1b X1 X2 X3 X4 0 X3 1 -1 1 1 0 0 X4 4 -1 2 0 1 j 2 2 0 0 1 10,0,但相应列上的系数但相应列上的系数P P1 1=(-1,-1)=(-1,-1)T T0,0,0,但相应列上的系数但相应列上的系数P Pk k0,0,有无界有无界解解线性规划的矩阵表示0,. .,maxNBNBNBNBXXbXXNBtsXXCCz0. .maxXbAXtsCXz=0,. .)(max1111NBNBNTNBBXXNXBbBXt sXCNBCbBCz=0,. .maxNBNBNNBBXXbN

36、XBXtsXCXCz=0,. .max11NBNBNNBBXXNXBbBXtsXCXCz0.maxXbAXtsXCz0,. .maxNBNBNNBBXXbNXBXtsXCXCz0,. .max11NBNBNNBBXXNXBbBXtsXCXCz0,. .)(max1111NBNBNBNBXXNXBbBXt sXNBCCbBCzcj-CBB-1Pj=cj-zj 称为非基变量的检验数（Reduced Cost）B-1Pj=pj， B-1b= b ，CBB-1b=z02.2.4大大M法法原理原理: 如线性规划问题系数矩阵中，不存在单位如线性规划问题系数矩阵中，不存在单位阵作为初始可行基，此时，需要通过

37、填加人工阵作为初始可行基，此时，需要通过填加人工变量给出单位初始可行基。变量给出单位初始可行基。)5 , 4 , 3 , 2 , 1(0242822234min3153214321321jxxxxxxxxxxxxxxZj)3 , 2 , 1(0242822234min. 831321321321jxxxxxxxxxxxxZj例)7 , 6 , 5 , 4 , 3 , 2 , 1(0242822)(00234min7316532143217654321jxxxxxxxxxxxxxMMxMxxxxxxZj为任意大的正数)5 , 4 , 3 , 2 , 1(0242822234min31532143

38、21321jxxxxxxxxxxxxxxZjx1,x2,x3实际变量实际变量x4 松弛变量松弛变量x5 剩余变量剩余变量x6,x7人工变量人工变量100010001,7640PPPB例例9.用大用大M法求解下面线性规划问题法求解下面线性规划问题)41(010234210854235max) 1 (432143214321jxxxxxxxxxxxxxZj解解:引入人工变量引入人工变量x5,x6)6 , 5 , 4 , 3 , 2 , 1(010234210854235max6432154321654321jxxxxxxxxxxxMxMxxxxxZj得：最优解为：3400 , 0 ,35,35*Z

39、XT)51(052151565935121510max)2(321321321321jxxxxxxxxxxxxxZj解解:增加松弛变量增加松弛变量x4,x5，剩余变量，剩余变量x6，人工变量，人工变量x7)71(052151565935000121510max76321532143217654321jxxxxxxxxxxxxxxMxxxxxxxZj得： Cj 10 15 12 0 0 0 -M CB XB B-1b X1 X2 X3 X4 X5 X6 X7 0 X4 9 5 3 1 1 0 0 0 0 -M X5 X7 15 5 -5 2 6 1 15 1 0 0 1 0 0 -1 0 1 j

40、 10+2M 15+M 12+M 0 0 -M 0 Cj 10 15 12 0 0 0 -M CB XB B-1b X1 X2 X3 X4 X5 X6 X7 10 X1 9/5 1 3/5 1/5 1/5 0 0 0 0 -M X5 X7 24 7/5 0 0 9 -1/5 16 3/5 1 -2/5 1 0 0 -1 0 1 j 0 9-1/5M 10+3/5M -2/5M 0 -M 0 人工变量人工变量x7=1/20，所以原问题无可行解。，所以原问题无可行解。（补充）两阶段法（补充）两阶段法(大大M法的补充）法的补充）求解问题：求解问题： max z=-3x1+x3 x1+ x2+x34

41、-2x1+ x2-x31 3x2+x3=9 xj0(j=1,2,3)化标准型化标准型: max z=-3x1+0 x2+x3+0 x4+0 x5 x1+ x2+x3+x4 =4 -2x1+ x2-x3 -x5 =1 3x2+x3 =9 xj0(j=1,2,5)min w=x6+x7 x1+ x2+x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xj0(j=1,2,7) X*=(0,5/2,3/2,0,0,0,0)T W*=0 max z=-3x1+x3+0 x4+0 x5 x1+ x2+x3+x4 =4 -2x1+ x2- x3 -x5 =1 3x2+x3 =9 xj0(j=1,2,7) X=(0,5/2,3/2,0,0)Tmin w=x6+x7 max z=-3x1+x3+0 x4+0 x5 x1+ x2+