2线性规划图解法和单纯形法汇总

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线线 性性 规规 划及单纯形法划及单纯形法Linear ProgrammingLinear Programming第一章第一章Chapter1 线性规划线性规划 (Linear Programming) LP的数学模型的数学模型 图解法图解法 单纯形法单纯形法 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 LP模型的应用模型的应用1. 规划问题规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用

2、，获得最大的效益，这就是规划问题。这就是规划问题。（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大. .）例例1.1 如图所示，如何截取如图所示，如何截取x使铁皮所围成的容积最使铁皮所围成的容积最大？大？ x xa a

3、xxav 220 dxdv0)2()2()2(22 xaxxa6ax 例例1.2 某厂生产两种产品，某厂生产两种产品，下表给出了单位产品所需资下表给出了单位产品所需资源及单位产品利润源及单位产品利润 问：应如何安排生产计划，才问：应如何安排生产计划，才能使总利润最大？能使总利润最大？ 解：解：1.1.决策变量：设产品决策变量：设产品I I、IIII的产量的产量 分别为分别为 x1、x22.2.目标函数：设总利润为目标函数：设总利润为z z，则有：，则有： max z = 2 x1 + x23.3.约束条件：约束条件： 5x2 15 6x1+ 2x2 24 x1+ x2 5 x1， x20 x1

4、=3.8, x2=1.2, z=22.8例例1.3 已知资料如下表所示，已知资料如下表所示，问如何安排生产才能使利润问如何安排生产才能使利润最大？或如何考虑利润大，最大？或如何考虑利润大，产品好销。产品好销。 设设 备备产产 品品 A B C D利润利润（元）（元） 2 1 4 0 2 2 2 0 4 3 有有 效效 台台 时时12 8 16 12解：解：1.1.决策变量：设产品决策变量：设产品I I、IIII的产量的产量分别为分别为 x1、x22.2.目标函数：设总利润为目标函数：设总利润为z z，则，则有：有： max z = 2 x1 + x23.3.约束条件：约束条件： x1 0 ,

5、x2 0 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12例例1.4 某厂生产三种药物，某厂生产三种药物，这些药物可以从四种不同的这些药物可以从四种不同的原料中提取。下表给出了单原料中提取。下表给出了单位原料可提取的药物量位原料可提取的药物量 解：解：要求：生产要求：生产A种药物至少种药物至少160单位；单位；B种药物恰好种药物恰好200单位，单位，C种药物不超过种药物不超过180单位，且单位，且使原料总成本最小。使原料总成本最小。1.1.决策变量：设四种原料的使用决策变量：设四种原料的使用 量分别为：量分别为：x1、x2 、x3 、x42.2.目标函数：设总成本为目

6、标函数：设总成本为z min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.3.约束条件：约束条件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 200 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x4 0 例例1.5 某航运局现有船只种类、数量以及计划期内各条航某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：线的货运量、货运成本如下表所示：航线号航线号船队船队类型类型编队形式编队形式货运成本货运成本（千元队）（千元队）货运量货运量（千吨）（千吨）拖轮拖轮A型型驳船驳船B型型驳船驳船1112362

7、521436202322472404142720船只种类船只种类船只数船只数拖拖 轮轮30A型驳船型驳船34B型驳船型驳船52航线号航线号合同货运量合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？问：应如何编队，才能既完成合同任务，又使总货运成本为最小？解：解：设：设：xj为第为第j号类型船队的队数（号类型船队的队数（j = 1，2，3，4），）， z 为总货运成本为总货运成本则：则： min z = 36x1 + 36x2 + 72x3 + 27x4 x1 + x2 + 2x3 + x4 30 2x1 + 2x3 34 4x2 + 4x3 + 4x4 52

8、25x1+20 x2 200 40 x3+20 x4 400 xj 0 （ j = 1,2,3,4）11221111221111221max (min) () () 00nnnnmmmnnmnzc xc xc xa xa xa xbaxaxaxbxx )21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 简写为：简写为：) (21ncccC nxxX1 mjjjaaP1 mbbB1max (min) () 0 jjzCXP xBX 其中：其中： mnmnaaaaA1111 0 )( (min) maxXBAXCXZ其中：其中：) (21ncccC

9、nxxX1 mbbB16. 线性规划问题的标准形式线性规划问题的标准形式11max.1,2,0,1,2,njjjnijjijjZc xa xbstimxjn特点：特点：(1) 目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3) 决策变量决策变量xj为非负。为非负。 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)，可化为求极大值问题。，可化为求极大值问题。 jjxczmin也就是：令也就是：令 ，可得到上

10、式。，可得到上式。zz jjxczzmax即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx 0, jjxx 变量的变换变量的变换 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。 ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量 常量常量 bi0 的变换的变换: :约束方程两边乘以约束方程两边乘以（1）例例1.6 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式 ,0,52324 7 532min32132132132132

11、1无无约约束束xxxxxxxxxxxxxxxZ用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求 ，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以33xx 3x0,33 xx(2) 第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3) 第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(4) 第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右将右端常数项

12、化为正数；端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然; 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：标准形式如下： 例例1.7 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321xxxxxxxxxxxxxxxZ为无约束

13、（无非负限制）为无约束（无非负限制） 解解: : 用用 替换替换 ，且，且 ， 54xx 3x0,54 xx将第将第3 3个约束方程两边乘以（个约束方程两边乘以（1 1）将极小值问题反号，变为求极大值将极小值问题反号，变为求极大值标准形式如下：标准形式如下： 0,5 )(252 )( 7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76, xx引入变量引入变量 12121212m in2385340 ,Zxxxxxxxx 无 约 束0 x ,x ,x ,x ,xx)x(xxx)x(xx)x(xxZaxm111

14、1654364354343435832例例1.8 将线性规划问题化为标准型将线性规划问题化为标准型解：解： 例例1.9 将线性规划问题化为标准型将线性规划问题化为标准型解：解：Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1 , x3 , x4 0； x2无约束 Max z = 3x15x2+5x2”8x3 +7x4 s.t. 2x13x2+3x2”+5x3+6x4+x5= 28 4x1+2x2-2x

15、2”+3x3-9x4-x6= 39 -6x2+6x2”-2x3-3x4-x7 = 58 x1 ,x2,x2”,x3 ,x4 ,x5 ,x6 ,x7 0 7. 7. 线性规划问题的解线性规划问题的解11max(1)(1,2,)(2).0,1,2,(3)njjjnijjijjZc xa xbimstxjn线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。 可行解可行解：满足约束条件：满足约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的

16、集合为可行域。的集合为可行域。 最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。 基：基：设设A为约束条件为约束条件的的mn阶系数矩阵阶系数矩阵(mn)，其秩为，其秩为m，B是矩阵是矩阵A中中m阶满秩子方阵（阶满秩子方阵（ B 0），称），称B是规划问题的是规划问题的一个基。设：一个基。设：) (11111mmmmmppaaaaB 称称 B中每个列向量中每个列向量Pj ( j = 1,2, , m) 为基向量。与基向量为基向量。与基向量Pj 对应的变量对应的变量xj 为为基变量基变量。除基变量以外的变量为。除基变量以外的变量为非基变量非基变量。 基解：基解：某一确定

17、的基某一确定的基B，令非基变量等于零，由约束条件，令非基变量等于零，由约束条件方程方程解出基变量，称这组解为基解。在基解中变量取非零解出基变量，称这组解为基解。在基解中变量取非零值的个数不大于方程数值的个数不大于方程数m，基解的总数不超过，基解的总数不超过 基可行解：基可行解：满足变量非负约束条件的基本解，简称基可满足变量非负约束条件的基本解，简称基可行解。行解。 可行基：可行基：对应于基可行解的基称为可行基。对应于基可行解的基称为可行基。mnC非可行解非可行解可可行行解解基解基解基可行解基可行解例例1.10 求线性规划问题的所有基矩阵。求线性规划问题的所有基矩阵。 5 , 1, 022610

18、3524max53214321321jxxxxxxxxxxxxZj解解: 约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 10261001115Ar(A)=2，2阶子矩阵有阶子矩阵有10个，其中基矩阵只有个，其中基矩阵只有9个，即个，即 100116010211120101015061111005261161015987654321BBBBBBBBB线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标

19、准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决策只有两个决策变量的线性规划问题，这时可以通过图解的方法变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观的优点，便于初来求解。图解法具有简单、直观的优点，便于初学者窥探线性规划基本原理和几何意义。学者窥探线性规划基本原理和几何意义。 解题步骤解题步骤4 将最优解代入目标函数，求出最优值。将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的在直角平面坐标系中画出所有的约束等式约束等式，并找出，并找出所有约束条件的公共部分，称为可行域，可行域中所有约束条件的公共部分，称为可

20、行域，可行域中的点即为可行解。的点即为可行解。 2 标出标出目标函数目标函数值增加或者减小的方向。值增加或者减小的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向目标函数值增加的方向平行移动平行移动，找与可行域最后，找与可行域最后相交的点，该点就是最优解。相交的点，该点就是最优解。max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例例1.11 用图解法求解线性规划问题用图解法求解线性规划问题x1

21、x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z = 2X1 + X2max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X

22、1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域min Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行

23、域可行域此点是唯一最优解此点是唯一最优解 006346321212121xxxxxxxx、246x1x2246无界解无界解( (无最优解无最优解) )max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Zx1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)0,050305 .140221212121 xxxxxxxxmax Z=3x1+4x2例例1.7 由图解法得到的几种情况由图解法得到的几种情况 根据以上例题，进一步分析讨论可知线性规划的可行域和根据以上例题，进一步分析讨论可知线性规划的可行域

24、和最优解有以下几种可能的情况：最优解有以下几种可能的情况： 1.可行域为封闭的有界区域可行域为封闭的有界区域 (a)有唯一的最优解；有唯一的最优解； (b)有无穷多个最优解；有无穷多个最优解； 2.可行域为封闭的无界区域可行域为封闭的无界区域 (c)有唯一的最优解；有唯一的最优解； (d)有无穷多个最优解；有无穷多个最优解； (e)目标函数无界目标函数无界(即虽有可行解，但在可行域中，目标函数即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少可以无限增大或无限减少)，因而没有有限最优解。，因而没有有限最优解。 3.可行域为空集可行域为空集 (f)没有可行解，原问题无最优解没有可行解，原

25、问题无最优解 由图解法得到的启示由图解法得到的启示(1)线性规划问题解的情况：线性规划问题解的情况： 唯一最优解；无穷多最优解；无界解；无可行解唯一最优解；无穷多最优解；无界解；无可行解(2) 线性规划问题的可行域是凸集（凸多边形）线性规划问题的可行域是凸集（凸多边形）x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()17.2 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z可行域可行域max Z = 2X1 + X2 (3) 最优解一定是在

26、凸集的某个顶点最优解一定是在凸集的某个顶点 解题思路解题思路 先找出凸集的任一顶点，计算其目标函数值，再与先找出凸集的任一顶点，计算其目标函数值，再与周围顶点的目标函数值比较，如不是最大（或最小），周围顶点的目标函数值比较，如不是最大（或最小），继续比较，直到找出最大（或最小）为止。继续比较，直到找出最大（或最小）为止。学习要点：学习要点：1. 通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）（唯一最优解；无穷多最优解；无界解；无可行解）2. 作图的关键有三点：作图的关键有三点： (1) 可行解区域要画正确可行解区域要画正确

27、 (2) 目标函数增加的方向不能画错目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动目标函数的直线怎样平行移动 连接几何形体中任意两点的线段仍完全在该几何形连接几何形体中任意两点的线段仍完全在该几何形体之中。体之中。 有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。凸集凸集凸集：如果集合凸集：如果集合C中任意两个点中任意两个点X1、X2，其连线上的所有点，其连线上的所有点也都是集合也都是集合C中的点，称中的点，称C为凸集。为凸集。凸集凸集凸集凸集不是凸集不是凸集2112, 0(11)CCaCaXXXa X有凸集凸集凸集凸集顶顶 点点 顶点：如果凸集顶点：如果凸集C中不存在

28、任何两个不同的点中不存在任何两个不同的点X1，X2，使，使X成为这两个点连线上的一个点成为这两个点连线上的一个点2112,11(0)XXXa XCCXaCa不存在几个基本定理的证明几个基本定理的证明定理定理1 若线性规划问题存在可行解，则问题的可行域是凸集若线性规划问题存在可行解，则问题的可行域是凸集。 思路：若满足线性规划约束条件 的所有点组成的几何图形C是凸集，根据凸集的定义，C内任意两点 X1, X2连线上的点也必然在C内 。【证】设 为 C 内任意两点，即 ，将X1, X2代入约束条件有X1, X2连线上任意一点可以表示为：1njjjP xb111121221222(,) ,(,)TT

29、nnXxxxXxxx12,XC XC1211;(1.8)nnjjjjjjP xbP xb1212(1)(01)(1)(01,1, )(1.9)jjjXaXa Xaxaxa xajn将(1.9)代入约束条件并由式(1.8)得：所以 。由于集合内任意两点连线上的点均在集合内，所以 C 为凸集。1211122111(1)nnjjjjjjjnnnjjjjjjjjjP xP axa xPaxP xPaxabbabb12(1)XaXa XC一个引理 引理引理 线性规划问题的可行解线性规划问题的可行解 为基可行解的的充要条件是为基可行解的的充要条件是X的正分量所对的正分量所对应的系数列向量是线性独立的。应的

30、系数列向量是线性独立的。 【证】必要性由基可行解的定义是显然的。 充分性：若向量P1, P2, , Pk是线性独立的，则必有km。 1) 当k=m时，它们恰好构成一个基，从而相应的基可行解为 2) 当k0 得1mjnPPPb1,11112,1222,1100010001mjnmjnm mmjmnmaaabaaabaaab12mPPP1,mPP1101.16mjijiimjijiiPa PPa P或（）1()01.17mjijiiPa P（）式(1.15)+式(1.17)，并经过整理后有由上式找到满足约束方程组 的另外一个点：其中 是 的第j 个坐标的值。 要使 是一个基可行解，因 0，故应对所

31、有i=1,.,m存在且这m个不等式中至少有一个等号成立，因为当 时，上式显然成立。01()1.18miijijixaPPb（）1mjjjP xb(1)X(1)X00iijxa(1)0011(,0, ,0)TjmmjXxaxa0ija 这样 中正分量最多有m个，容易证明m个向量线性无关，故只需按式(1.20)来确定 的值， 就是一个新的基可行解。(1)X(1)X00min0(1.20)ilijiijijxxaaa00()0()iijilxail111,llmjPPPPP令基本可行解和可行基的变换基本可行解和可行基的变换(1)00001111,11,(,0,0, ,0)TjlljlljmmjXxa

32、xaxaxa(0)00000111(,0,0)TlllmXxxxxx111,llmjPPPPP111,lllmPPPPP基本可行解：基本可行解：可行基：可行基：换出基换出基换入基换入基STEP3 最优性检验和解的判别最优性检验和解的判别将基可行解 分别代入目标函数得因 0为给定，所以只要有 通常简写为 ，它是对线性规划问题的解进行最优性检验的标志。(0)(1) XX和(0)01(1)010(0)111()()()miiimiiijjimmmiijiijjiijiiizc xzc xacc xcc azcc a(1)(0)1()0,mjiijicc azz就有。1()mjiijicca() jj

33、jcz或1.当所有的 时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，现有顶点对应的基可行解即为最优解最优解。2.当所有 时，对某个非基变量 xj 有 ，且按公式(1.20)可找到0，这表明可以找到另一顶点（基可行解）目标函数也达到最大。由于该两点连线上的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无有无穷多最优解穷多最优解。3.如果存在某个 又Pj向量的所有分量aij0。换基时对任意 0, 恒有 因取值可无限大，在由X(0)换到X(1)时目标函数值也可无限大，则线性规划问题存在无界解存在无界解。0j0j()0jjcz0,j00,iijxa求解线

34、性规划问题 LP规划问题的最优解可从基可行解（顶点）中找到 图解法有局限性； 枚举法计算量大；0,12416482.32max21212121xxxxxxtsxxz解：第一第一:将该问题化成标准形5 , 2 , 1, 012416482.00032max524132154321jxxxxxxxxt sxxxxxzj第二第二: 找初始可行解(即一个顶点)。 系数矩阵 A=(P1 P2 P3 P4 P5) 0 , 0 , 0 , 3 , 2,12168,1004001004001210.maxCbAXbAXt sCXz矩阵形式 因为P3 ，P4， P5 线性独立，故B=(P3 , P4, P5)构

35、成一个基，其对应的基变量x3，x4， x5，解出来为（用非基变量表示基变量用非基变量表示基变量） x3 =8- x1-2x2 x4 =16-4x1 (1) x5 =12- 4x2XB = B-1 b B-1NXN将(1)代入目标函数中得 z=0+2x1+3x2令非基变量 x1=x2=0，则有z=0。这时得到一个基可行解： X(0) =(0,0,8,16,12) T -原点第三第三:判别 从目标函数z=0+2x1+3x2中得知，非基变量x1和x2的系数为正，因此，将非基变量换入基后可使目标函数增大，转入第四步第四：第四：换基(旋转迭代) 确定换入变量：由于非基变量x2的系数（正）贡献最大，故需换

36、入的基变量为x2。 换入变量已定，必须从x3，x4，x5换出一个，并且要保证其余均是非负的，即x3，x4， x50。当x1=0时，有x3 =8- 2x2 0 x4 =16 0 x5 =12- 4 x2 0 x2换入基，换入基，x1未换未换入，还是非基变入，还是非基变量量 只要选择 x2 =min (8/2，-，12/4)=3，对应基变量x5 =0，从而确定用x2和和x5对换对换，即将x5 换出，（用非用非基变量表示基变量基变量表示基变量） 2x2+ x3 =8- x1 x4 =16- 4 x1 4x2 =12- x5 用高斯消去法（行变换），得 x3 =2- x1+ 1/2x5 x4 =16-

37、 4 x1 x2 =3- 1/4 x5 （2）将上式代入原目标函数中得z=9+2x1-3/4x5（1） 返回第三步： 从z=9+2x1-3/4x5，非基变量x1的系数是正的，还可增大。重复上述步骤。由于x1的系数是正的，则x1为转入变量，再由当x5=0时 x3 =2- x1 0 x4 =16- 4 x1 0 x2 =3 0 只要选x1=min2，16/4，-=2上式就成立，因为x1= 2时，基变量x3=0，从而由由x1换出换出x3令非基变量x1和x5为零有z=9，又得到另一个基可行解 X(1) =(0,3,2,16,0) T 顶点Q4 x1+2x2 =8- x3 4x1 +x4 =16 (3)

38、 4x2 =12- x5高斯消去法（行变换）得 x1 =2- x3 +1/2x5 0 x4 =8-2 x5 +4 x3 0 x2 =3- 1/4 x5 0 代入目标函数中，得 z=13-2 x3 +1/4x5令非基变量x3= x5=0有z=13，又得到另一个基可行解 X(2) =(2,3,0,8,0) T 顶点Q3 ;（2）用非基变量表示基变量用非基变量表示基变量同理，返回第三步，再迭代，x5作为转入变量只要取x5=min-，8/2，12=4就有上式成立。 x5=4时， x4=0，故用x5换换x4 x1 =4- 1/4 x4 x5 =4-1/2 x4 +2 x3 x2 =2+1/8 x41/2

39、 x3 令x3=0，有 x1 =2+1/2x5 0 x4 =8-2 x5 0 x2 =3- 1/4 x5 0 （3）+高斯0Q4Q3Q2Q11123234X1X2x1+2x2 =84x1=164x2=12代入得 z=14-3/2 x3 -1/8 x4 ，令x3 =x4=0得z=14。新的基可行解为 X(3) =(4,2,0,0,4) T 顶点Q2 (最优解)最优目标值z=14 。(0,3,2,16,0)(0,0,8,16,12)(2,3,0,8,0)(4,2,0,0,4)单纯形表单纯形表jc11mmnccccLLLLBCBXb1 mcc1 mxx1 mbb11 mmnxxxxLLLLi1 m1

40、,11,11001mnm mmnaaaaLLLLMMMMMMMMLLLL0 01mjjiijjjicc aczj0iikjkjbaa其中：1,1,11mmmii mnii niicc acc a确确定定换换出出基基确定换确定换入基入基例例1.12 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解 0,30340243max21212121xxxxxxxxZ解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3 3、x4 4则标准型为则标准型为: : 0,30340243max432142132121xxxxxxxxxxxxZ2）求出线性规划的初始基可行解，

41、列出初始单纯形表。）求出线性规划的初始基可行解，列出初始单纯形表。cj3400icB基基bx1x2x3x40 x34021100 x43013013400 1311421()3(0 20 1)31cc ac a 检验数检验数j 22321422()4(0 1 0 3)4cc ac a 3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。0 j4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单

42、纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变作为换入变量，当有一个以上检验数大于量，当有一个以上检验数大于0时，一般选择最大的一个时，一般选择最大的一个检验数，即：检验数，即： ，其对应的，其对应的xk作为作为换入换入变量变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择 ，选最小的选最小的对应基对应基变量作为变量作为换出变量换出变量。0 j0|max jjkmin0illikiklkbbaaa主元素主元素用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的基。替换基变量中的换出变量，得到一个新的基。对应

43、新的基可以找出一个新的基可行解，并相应地可以画出对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。一个新的单纯形表。5）重复）重复3）、）、4）步直到计算结束为止。）步直到计算结束为止。在新表中的基仍应该是单位矩阵在新表中的基仍应该是单位矩阵，则应将主元素所对应的，则应将主元素所对应的列列(换入基换入基)变成单位向量，包括约束条件的系数矩阵，基变成单位向量，包括约束条件的系数矩阵，基对应的值，检验数等对应的值，检验数等换入变量换入变量xk的检验数应为的检验数应为0高斯变高斯变换换cj3400iCB基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2j j j 换入列换入列bi /ai2，ai204010换换出出行行将将3化为化