管理运筹学(讲义)A-1.doc

第一章 线性规划与单纯形法(liner program and simplex algorithm) 第一节 线性规划问题及其数学模型1. 问题的提出线性规划问题有两大类型，各举例如下：例1 某工厂在计划期内要安排生产和两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示，该厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该厂获利最多？设备128台时原材料A4016 Kg原材料B0412 Kg解：对这样的问题用数学的语言来描述，就称为建立数学模型，简称建模。数学模型指用数学方法(字母、符号、数字等)对研究对象的数量关系所进行的定量描述。该问题是要求如何安排生产方案，即生产多少和两种产品，才能使所获得的利润最大，为此，设和两种产品的产量分别为x1和x2，x1和x2称为决策变量，显然，x1和x2的产量越大，所获得利润也越大，但x1和x2的产量要受到材料设备等资源的约束。如对于设备资源，生产和两种产品消耗的总台时数为x12 x2不能超过设备的有效台时数，即必须要满足下列条件：同样地，对于原材料A、B，也需满足下列条件：由于x1和x2是产品的产量，所以，x1和x2的取值自然限制在：在满足上述各个条件后，再考虑如何使得总利润最大(总利润为产品和的利润之和)，即，这里，max表示要求最大值。所以，该生产计划问题的数学模型可表示为： 用数学语言描述，就是求一组的值，使之在满足下列约束条件条件下：使目标函数的值尽量大。这里，s.t.是subject to的缩写，表示受约束于。例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3,在两个工厂之间有一条流量为每天200万支流，第一化工厂每天排放含有某种有害物质的工业污水2万m3，第二化工厂每天排放含有这种有害物质的工业污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂之前，有20可自然净化，根据环保要求，河流中工业污水的含量应不大于0.2%，这两个工厂都需要各自处理一部分工业污水，第一化工厂处理工业污水的成本是1000元/万m3，第二化工厂处理工业污水的成本是800元/万m3，现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小？200万m3500万m3工厂2工厂1解：该问题是问两个工厂各应处理多少污水，使得污水处理费用最小。设第一化工厂每天处理污水为x1万m3，第二化工厂每天处理污水为x2万m3，显然，两个工厂处理污水越少，费用就越小，但处理污水量，必须要满足环保要求，受环保标准的限制，环保要求两个工厂附近河流的污水含量都不得大于0 .2,所以，对第一化工厂处理污水量x1必须满足下列要求： 同样，对第二化工厂，处理污水量x2也必须满足： 由于两个工厂每天处理污水量不会大于各自的排放量，所以有，两个工厂处理污水量又自然限制于：在这些要求下，使得总费用最小，记为。所以，该环保问题的数学模型为：线性规划所研究的两类问题，一类是所谓“增产”问题：现有的资源一定，如何安排使用，使得创造的利润、收益等最大，如例1；另一类是所谓“节约”问题：任务一定，如何统筹安排，以尽可能少的资源去完成，如例2。所有的线性规划问题，尽管各个问题的具体内容不同，但都可归结为这两类问题。例3 （房地产开发）某房屋开发公司拟根据市场的需求修建二居室、三居室和四居室住宅。公司要求其规划部门确定各类住宅的户数，以获得最大利润。约束如下：工程造价不超过900万元；总户数不能少于350户；基于市场分析，各类住宅在总户数中所占比例为：二居室不大于20，三居室不大于60，四居室不大于40；各类住宅造价（户）：二居室 2万元，三居室 2.5万元，4居室 3万元各类住宅利润（户）：二居室 2000元，三居室 3000元，4居室 4000元。分析：这是一个在资源一定的情况下的求收益最大的问题，即“增产”问题。决策变量：设拟修建的二居室、三居室和四居室的户数分别为约束：目标函数：要求寻找使得公司预计利润最大的开发方案，此问题的数学模型为：s.t.从上面例子看到，线性规划问题是求极值问题,而且是求条件极值的问题,但这与多元函数微积分中求条件极值问题不同, 多元函数微积分中求条件极值的限制条件必须是等式的,而且自变量的个数要比限制条件个数多,才能用拉格朗日方法求解,所以,不能用微积分的方法求解上面的问题,属于线性规划研究的内容。2. 线性规划问题的数学模型 一般形式从上面建立的线性规划模型来看，这些模型都包括三部分：1 都有一组决策变量，是问题要确定的未知量，当决策变量的值确定后，就是得到问题的一个具体方案。一般地，一个线性规划问题有很多具体方案可供选择，求解线性规划问题就是从众多的可行方案中，寻求最优方案，使得设备材料等资源得到充分利用，避免任一选择其它方案造成资源浪费，达到最优的经济效果。2 都有约束条件，用决策变量的线性等式或不等式表示，决策变量在取值时必须要满足这些约束条件。一般地，决策变量的取值都要求是非负的，在约束条件中， 称为非负性约束条件。这一条件在有的问题中没有或只对部分变量有。3 都有一个目标函数，是决策变量的线性函数，表示问题所要达到的优化目标。不同的问题优化目标的要求不同，有的要求最大化，用max表示，有的要求最小化，用min表示。在这些模型中，约束条件和目标函数都是线性的，所以，称为线性规划问题；如果在约束条件和目标函数中有非线性式子，则称为非线性规划。线性规划问题的数学模型的一般形式为：或简写为求和形式，所以说，线性规划问题指求解一组变量，使其既满足约束条件，又使得线性的目标函数取得极值的一类最优化问题，称为线性规划问题。将一个实际问题抽象成线性规划模型(即建立线性规划模型)，一般可按照以下步骤进行：1 确定决策变量。确定问题的哪些量为决策变量，有时容易确定，有的问题需要分析后才能选定，这是很关键的一步。一般地，问题问什么就确定什么为决策变量，对于不太复杂的问题，可直接采用这个方法来设置决策变量。2 找出所有的限制，即约束条件。每个问题在实现时都要受到一定条件的约束，通过分析后，要找出所有的约束条件，不能遗漏，约束条件通常用一组决策变量的线性等式或不等式表示。3 明确目标函数。根据问题优化目标的要求确定目标函数，并要用决策变量的线性函数表示，可以是最大化或最小化。3. 线性规划问题的标准形式在线性规划模型中，目标函数、约束条件和决策变量可能有各种不同的形式，如目标函数可以是最大化max或最小化min，约束条件类型可以是、或是、或是，决策变量也可以非正、非负或无约束。为了便于讨论，规定线性规划问题的标准形式如下：或简写，需要注意的是，在标准型中约束条件中的右端项必须是：，如果某一约束条件的右端项为负数，则必须乘以1。有时为了讨论方便，还可写成向量形式和矩阵形式：向量形式： 式中， ， , ,矩阵形式： 式中，任何一个一般形式的线性规划问题，都可以通过下面方法化为标准形式：1 如果目标函数为求最小化，即，则只需将目标函数改为求最大化，令，得， 因为在满足相同的约束条件下，使达到最小化的解，也必定使达到最大化。2 如果某个约束条件的右端项为负数，则应将该约束条件两边乘以(-1)。3 约束条件的标准化，分两种情况： 如果约束条件为“”形式，可在不等式左边加上一个非负的新变量，把不等号改成等号，这个新变量称为松弛变量； 如果约束条件为“”形式，可在不等式左边减去一个非负的新变量，把不等号改成等号，这个新变量称为剩余变量，有时也称为松弛变量；4 如果有的变量有非正约束，即，则可令，用 非负变量代替；5 如果有无约束变量,或称自由变量,可令,用两个非负的新变量代替,新变量为非负, 的符号由的大小确定。例3 将下列线性规划问题化为标准型解：令，求,将目标函数由变为;为无约束变量，令，并代入目标函数和约束条件；将第一个约束条件加上松弛变量，使其变成等式；将第二个约束条件减去剩余变量，使其变成等式；所以，该问题的标准型为：4. 线性规划问题的解的概念设一般线性规划问题的标准型为：约束方程组的系数矩阵的秩为m,且m n。可行解：满足线性规划所有约束条件的解，称为线性规划问题的可行解，可行解的全体称为可行域。最优解：使目标函数值达到最优的可行解叫做线性规划的最优解。基(基矩阵)：设A是约束方程组的系数矩阵，秩为m，B是矩阵A中阶非奇异子矩阵(即)，则称B为线性规划问题的一个基。如果B是A中m阶的满秩方阵(即B是由A中m列线性无关的列向量构成)，则B就是线性规划问题的一个基。在基中的各个列向量称为基向量，它们对应的变量称为基变量，基以外的各个列向量称为非基向量，与它们对应的变量称为非基变量。确定一个基后，相应的基变量也就确定了，共有m个，非基变量有n-m个。在矩阵A中，如果前m列是线性无关的列向量，那么，则可作为一个基， ； 其中，为m个基向量，为基变量。基本解(基解)：当基B确定后，在约束方程组中令非基变量全等于0，就可以唯一解出基变量的一组值。基变量的值和非基变量的值合起来，就是线性规划问题相应基B的基本解(基解)。令非基变量，解方程组就可得出一个基解为： 。基解是约束方程组的一个特殊的解，基解的总数不会超过个，且每个基解的非零分量的个数不大于m.基本可行解(基可行解)：满足变量非负约束条件的基本解，称为基本可行解。显然，基本可行解的数目也不会超过个，一般基本可行解的数目小于基解的数目。可行基：对应于基本可行解的基，称为可行基。最优基：若一个基可行解是最优解，则它对应的基就叫做最优基。退化解：若基解中非零分量的个数小于m个时，这个基解就是退化解。例4 在下列的线性规划问题中找出满足约束条件的所有基本解.指出哪些是基本可行解,并代入目标函数,确定那一个是最优解.解: 则 是基解,但不是基本可行解. 则 则是基解,且是基本可行解. 则 则是基解,且是基本可行解. 则 则是基解,但不是基本可行解. 则 则是基解,但不是基本可行解.第二节 线性规划的图解法线性规划模型建立以后,要找出最优方案,还得需要运用适当的方法来求解，求解线性规划问题的通用方法主要是图解法和单纯形法。当然也有些其它的方法可以用来求解线性规划问题，但基本上都是针对某一特定类型的问题，只适合于个别的具体情况。图解法是利用几何作图的方法直接找出最优解。图解法的特点是直观、易于理解，但只能用于求解仅含两个变量(至多三个变量)简单的线性规划问题，即二维(或三维)线性规划问题，实际意义不大，因为实际问题中很少仅含两个变量。但图解法有助于我们理解线性规划的求解原理，而且，在求解过程中得出的一些结论对多维线性规划问题也是适用的。当然，单纯形法不受变量和约束条件的限制，可以用来求解多维线性规划问题。图解法的基本思想：先将所有的约束条件加以图解(即用直线或平面在坐标面上表示出来)，求出满足约束条件的可行域；然后，再根据目标函数的优化要求，确定优化方向，最终从可行域中求出最优解。图解法求解步骤如下：1 建立坐标系，将所有约束条件在坐标平面上用直线绘出；2 确定可行域，即由代表约束条件的直线所围成的公共区域；3 绘出目标函数等值线，确定优化方向；4 确定最优解和最优值。例5 用图解法求解下列线性规划问题解：首先，建立坐标系，绘制约束条件所代表的直线。在坐标平面上，非负约束条件，表示的取值只能在第一象限；不等式约束条件表示一个半平面(左平面或右平面，上平面或下平面)，表示那个半平面取决于约束条件不等号的方向和不等式左边式子的正负号，可采用试点法来判定，用坐标原点(0,0)代入判断。表示着以为直线边界的左下方半平面；表示着以为直线边界的左半平面；表示着以为直线边界的下半平面。Q3484Q4Q1Q2x1x2C4x2 =12x1+ 2x2 =8在座标平面上，同时满足所有约束条件的点的集合是一个凸多边形0Q1Q2Q3Q4(阴影区域)，在这个阴影区域内每一点(包括边界点)都满足约束条件，每一点就是一个可行解，所有点的集合称为可行域或可行解集。这个可行解集是一个凸集。再绘制目标函数等值线和确定优化方向。在坐标平面上，目标函数表示一族平行的等值线。等值线方程为：，它是一条斜率为,纵轴截距为的等值线。因为目标函数是求最大化,所以,当z值增大时,等值线向右上方平移,平移方向(或优化方向)与等值线的法线方向一致,当等值线在可行域内平移而不超出可行域，到达边界点Q2点时,目标函数达到最大值,Q点坐标即为最优解。即，。在这里，如果目标函数是求最小化，当z值减小时，等值线向右下方平移，平移方向与等值线的负法线方向一致。所以，确定目标函数的优化方向可按下列规则：当求目标函数最大化(max),应沿着目标函数等值线的法线正方向平移；当求目标函数最小化(min),应沿着目标函数等值线的法线负方向平移；目标函数等值线法线(正方向)向量端点坐标就是目标函数价值系数C1和C2。在这个线性规划问题中，可行域是有界的(闭合的凸多边形)，求解结果是有唯一的最优解，但对于其它的线性规划问题，它的解还可能有以下3种情况：1 有无穷多最优解在上面例子中，如果将目标函数改为，那么，目标函数等值线将与约束条件的边界线平行，在可行域上平移等值线，目标函数达到最大值时将与可行域的Q2Q3边线重合，在Q2Q3上任一点都将使目标函数值达到最大，所以，线性规划问题将有无穷多最优解(多重解)。Q3484Q4Q1Q2x1x2Cx1 +2x2 = 84x2 =124x1 =164x1x22 无界解如果有如下线性规划问题：从图中可以看出，这个线性规划的可行域是无界的，目标函数等值线在目标值增大方向上可以无限制地平移都不会超过可行域，目标函数值可以趋于无穷大，目标函数值无上界，这种线性规划问题有可行解，但无最优解，称为无界解或无有限最优解。出现这种情况一般是建立模型遗漏某些约束条件造成的。3 无可行解x1x2如果有下列线性规划问题从图中可以看出，这几个约束条件不能形成一个公共区域，也就是说，可行域是空集，这个线性规划将没有可行解，也就没有最优解。出现这种情况主要是建模本身有错误，约束条件之间相矛盾。注意的是，线性规划的求解结果情况，要将约束条件和目标函数求极值情况结合起来分析，如上面第1或2种情况，如果线性规划是求最小化问题，还是有唯一最优解，而不是多重解或无界解。从线性规划的图解法，可以得出一个很重要的结论：线性规划有最优解，它一定是在可行域某个顶点(极点)得到，而不是在可行域内某个点，而可行域顶点数总是有限的，这就给求解带来了简便。可行域的顶点对应于基可行解。如果在两个顶点得到最优解，则它们连线上任一点都是最优解，因而有多重解。第三节 单纯形法一. 基本概念和基本定理1. 基本概念凸集 设K是n维欧氏空间的一点集，若任意两点 的连线上的一切点；则称K为凸集。凸组合 设是n维欧氏空间中的k个点，若存在，使则称的凸组合。顶点 设K是凸集，；若X不能用不同的两点和 的线性组合表示为则称X为K的一个顶点(或极点)。2. 基本定理：定理1 若线性规划问题存在可行域，则其可行域是凸集。引理1 线性规划问题的可行解为基可行解的充要条件是X的正分量的系数列向量是线性独立的。定理2 线性规划问题的基本可行解X对应于可行域D的顶点。引理2 若K是有界凸集，则任何一点可表示为K的顶点的凸组合。定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。结论：线性规划问题的所有可行解构成的集合是凸集，它有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，一定是在某个顶点上得到。二. 单纯形法原理从前面的结论知道，线性规划的最优解一定是在可行域的极点上得到，这样就避免了从可行域中无穷多个点来寻找最优解，使得问题求解大为简单。而且可行域的每个极点又和基可行解一一对应。所以，单纯形法求解思想就是先将线性规划问题化为标准型，求出一个基可行解，称为初始基可行解，再检验这个解是否最优(解的检验)，如果不是，则从这个初始基可行解开始，沿着凸集的边缘寻找下一个极点或基可行解（基变换），并判断得到的基可行解是否最优，如果是最优解，目标函数值达到最优值，计算结束，否则，在这个基础上，再继续寻找和判断，直到求出最优解。从一个基可行解得到另一个基可行解，需要进行基变换。由于基可行解的数目是有限的，所以这样求下去总能得到最优解，但并不需要求出所有的基可行解。下面通过一个简单例子来说明单纯形法的基本思想。例： 求基可行解，必须要找出一个基，从约束方程的系数矩阵中，可以看出，基矩阵应是33阶，的系数列向量是单位向量，线性独立，构成一个单位阵，可作为一个基矩阵，即三个基向量对应的基变量是，非基变量是，通过改写约束方程，将基变量用非基变量表示， 令非基变量，可得到一个基可行解：，将上式代入目标函数，得，相应的目标值为Z0。显然，这个解不是最优解，工厂的利润为0(两种产品没有安排生产，)。对进行分析，可以看到，非基变量的系数为正，如果安排任意一种产品的生产都可以使目标值增大，使得工厂的利润增大，也就是要使变量的取值由零变成一个正值，由非基变量变成基变量。所以，在目标函数中只要还有正系数的非基变量，目标值就还有增大的可能，因此，要使目标值继续增大，就需要将非基变量和基变量进行对换。为使目标值尽快达到最优，一般选择正系数大的非基变量作为换入变量，为换入变量。由于基变量个数是固定的，所以，在确定了换入变量同时，还需要确定一个基变量作为换出变量，要从基变量中选择一个， 的值将从零增加到一个正值， 但的增加量必须受约束条件的限制，必须要保证原基变量满足非负条件，即(仍是非基变量，为0) 所以，只能取：当的值由零增大到3时，基变量取值最先变为零，而仍保持非负，这就确定用换，作为换出变量，换出为非基变量，所以，新的基变量为，非基变量为。再求以为基变量的基可行解，同样，将基变量用非基变量表示， 令非基变量，可得到一个基可行解：，将上式代入目标函数，得，相应的目标值为Z9。对进行分析，非基变量的系数还是正的，说明目标函数值还能增大，由于只有一个非基变量系数为正，因此，确定为换入变量，换出变量按照下列方法确定：(令0) 所以，对应的为换出变量，新的基变量为新的基变量为，非基变量为。再求以为基变量的基可行解，同样，将基变量用非基变量表示，令非基变量，可得到一个基可行解：，将上式代入目标函数，得，相应的目标值为Z13。还需要继续迭代，最后，得到基可行解为：，目标函数式子：，目标值为Z14。再分析上面式子，非基变量的系数全为负数，目标函数值不可能再增大。为最优解，目标最优值为14。也就是工厂安排产品生产4件，产品生产2件，最大可获得利润14元。1. 初始基可行解的确定单纯形法是从初始基可行解开始迭代的，要确定初始基可行解，首先需要找出一个初始可行基。设有以下线性规划问题(化为标准型后)，在这个线性规划的系数矩阵(系数列向量)中，可以看出，它有m个线性独立的单位列向量，构成一个单位矩阵，那么，这个单位矩阵就可作为一个初始可行基。对于一般的线性规划问题化为标准型后，能否找到一个单位阵作为初始可行基，有以下几种情况：1 如果线性规划所有的约束条件是“”形式的不等式，当在每个不等式左边加上一个非负的松弛变量化为标准型后，由这些松弛变量系数列向量构成的矩阵就是一个单位阵，可作为初始可行基。标准型后: 2 如果线性规划的约束条件是“”和“”形式，在化为标准型后，一般不存在单位阵，需要添加人工变量，构造一个单位阵作为初始可行基，这部分在后面再讲。需要注意的是，在线性规划的系数矩阵中，不能任意选择一个基作为初始可行基，因为任选一个基求出的基变量值有可能是负数。所以，一定要以单位阵作为初始可行基。有了初始可行基后，就可以求出初始基可行解。将上式移项后(用非基变量表示基变量),得，令，得初始基可行解，2. 最优性检验与解的判别在每一步迭代后,都应检验一下基可行解是否为最优解,从而决定迭代过程是否停止还是继续进行，这就是所谓最优性检验。在每一步迭代后,迭代结果可能有几种情况，是唯一最优解，无穷多最优解，还是无界解或无可行解，需要建立相应的解的判别准则。1 最优性检验数在确定了初始可行基后，基变量用非基变量表示的一般形式为，如果初始基可行解不是最优解，经过迭代后，再对变量及其系数重新进行编号后，新的基变量仍可用非基变量表示，将上式代入目标函数，得，令 非基变量检验数 目标函数用非基变量表示2 解的判别定理对进行分析，可以得出关于解的几个判别定理：1 最优解判别定理：若为对应于基B的一个基可行解，且对于一切有，则为最优解。2 无穷多最优解判别定理：若为对应于基B的一个基可行解，对于一切有，又存在某个非基变量的检验数，则线性规划有无穷多最优解。3 无界解判别定理：若为一基可行解,有一个,并且对那么该线性规划问题无界解(或称无最优解).需要注意的是,上面提到的解的判别定理,只是针对目标函数求最大化,如果是目标函数求最小化，又不将目标函数改为标准型，解的判别准则需要改动，最优解判别应改为；无穷多最优解判别也应改为；无界解判别定理中的应改为。3. 基变换如果迭代后，经过解的判别不是最优解，也不属于无界解，那么，就应当进行基变换。基变换的目的是为了将原可行基换成新的可行基，从而得到一个新的基可行解。基变换是通过基变量和非基变量的交换来实现的，也就是要将某一基变量换出，变成非基变量，同时，还要将某一非基变量换入，变成基变量。1 换入变量的确定换入变量的确定可以根据来分析，如果在迭代中，非基变量的检验数仍然大于零，这就意谓非基变量值增加还可以使目标函数值增大，这时可以考虑将非基变量换入到基变量中去，也就称为换入变量。当有多个非基变量的检验数大于零，为了使目标函数值尽快增加，减少迭代次数，一般选择最大的正检验数所对应的非基变量为换入变量，即若，则为换入变量。2 换出变量的确定确定换出变量的原则是保持解的可行性。也就是说，当换入变量由零增加到某一值时，使得原基可行解的某一个正分量变为零，而其它分量仍保持非负，则即为换出变量。具体实现可按照最小比值规则进行。下面导出最小比值规则：在确定了初始可行基后，基变量用非基变量表示的一般形式为，展开后，得，在上面约束方程中，如果得到的基可行解经判断不是最优解，就需要进行基变换。如果确定为换入变量，值将由零增大为某一正值，从约束方程可以看出，值增大(其它非基变量仍为零)，基变量值将减小，但必须保持非负，所以，值即只能取，在迭代中，在对变量及其系数重新编号、整理后，可表示为，则对应的值正好为零,变为非基变量。所以, 为换出变量。4. 迭代(旋转运算)在确定了换入变量和换出变量之后，就要把和的位置进行对换，把所对应的系数列向量变成单位向量，这样就得到了新的可行基，这些变换可通过对系数矩阵的增广矩阵进行初等行变换来实现。这也就是所谓旋转运算。换入变量和换出变量的系数列向量分别为， ； 将变为单位向量，可通过对系数矩阵的增广矩阵进行初等行变换来实现，系数矩阵的增广矩阵如下式： (1)变换步骤:1 将增广矩阵中的第L行除以,得到, (2)2 将增广矩阵中列的各个元素, 变为1,其它元素都变换为零。对于其它行的变换：将(2)式乘以后，再加到(1)式的第i行，得到新的第i行.3 经过初等变换后的新的增广矩阵是: (3)4 由(3)式可以看到,的系数列向量构成单位矩阵,它是新的可行基,当非基变量为零时,可得到一新的基可行解,在上面的系数矩阵变换中,元素称为主元素,它所在列称为主元列,它所在行称为主元行, 元素变换后为1。例6 对下列约束方程组进行基变换: 为基变量,为非基变量,令为零,可得一个基可行解,.现确定为换出变量,为换入变量,变换后, 令为零,可得一个基可行解,.第四节 单纯形法的计算单纯形法将整个计算过程都集中到一系列表中进行的，这个表就是单纯形表。单纯形表的形式如下：Cjc1cmcm+1cniCBXBbx1xmxm+1xnc1x1b110a1,m+1a1,n1c2x2b200a2,m+1a2,n2cmxmbm01am,m+1am,nm000将线性规划化为标准型后,按照下列要求将有关内容填入表中.XB列中填入基变量,;CB列中填入基变量的价值系数,在迭代过程中随基变量的变化而改变;b列中填入约束方程组右端项;Cj行中填入所有变量的价值系数,包括松弛变量、剩余变量及人工变量；Cj行的下一行填入所有的变量；i列中的数字在确定换入变量后，按规则计算后填入；最后一行为检验数行，对应的非基变量的检验数按下式计算：基变量的检验数均为零；b列最后有关数值表示Z的值，是目标函数值的相反数。上面这表称为初始单纯形表，单纯形法以这张表为起点进行迭代，每迭代一次就得到一张新的单纯形表，可求出新的基可行解。计算步骤：1 将线性规划问题标准化，确定初始可行基，建立初始单纯形表，求出初始基可行解；2 检验各非基变量的检验数；如果，则本表得到的基可行解就是最优解，停止计算，否则，转入下一步；3 在所有的检验数中，若有某个对应的系数列向量，则该线性规划问题无界解，停止计算，转入下一步；4 根据，确定为换入变量，所对应的系数列称为主元列；根据，可确定为换出变量，行称为主元行，主元列与主元行交叉处的元素称为主元素；5 以主元素为基准，将主元素变为1，主元列变成单位向量； 同时，还要将XB列中的换为，以及改变CB列中相应的价值系数，得到一张新的单纯形表，重复第2步至第5步，直至求出最优解为止。例7 用单纯形法求解下列线性规划问题解：1将线性规划问题标准化，确定初始可行基，建立初始单纯形表；松弛变量对应的系数列向量为单位向量，可作为一个初始可行基，建立的初始单纯形表如下：Cj23000CBXBbx1x2x3x4x50x381210040x41640010-0x5120(4)0013j023000可得到一个初始基可行解：。计算各非基变量的检验数，基变量的检验数；将检验数填入表中最后一行，b列最后一行为0。2经计算，非基变量检验数，因此，取 对应的变量为换入变量；再取对应的为换出变量，并将值填入表中；所在列和所在行的交叉元素为主元素(4);3以交叉元素(4)为基础,进行旋转运算,将主元素所在列变成单位向量,同时,将XB列中替换.注意:在进行旋转运算时(初等行变换),要包括b列数值。经过计算b列数值为，于是，得到新的基可行解为：，目标值为z=9。Cj23000CBXBbx1x2x3x4x50x32(1)010-1/220x4164001043x2301001/4-j920003/4再计算非基变量的检验数： 和4 经计算，对应的为换入变量，重复上述步骤，可得下表：Cj23000CBXBbx1x2x3x4x52x121010-1/20x4800-41(2)43x2301001/412j1300-201/42x141001/400x5400-21/213x22011/2-1/80j1400-3/2-1/80从上表最后一行可以看出，所有的检验数都已经为负数或零，说明目标函数值已不可能再继续增大，所以，最优解，最优目标值为。例8 (无界解)用单纯形表求下列线性规划:s.t.解:加入松弛变量后,单纯形表计算如下:Cj41000CBXBbx1x2x3x4x50x32-111000x44(1)-401040x581-20018j0410000x360-31104x141-40100x540(2)0-112j00170-400x312001-1/23/24x112100-121x22010-1/21/2j00009/2-17/2经过两次迭代后,非基变量x4的检验数为正,对应的列向量都为负,所以为无界解.例9 (无穷多最优解)用单纯形法求解下列线性规划问题：解： Cj32000iCBXBbx1x2x3x4x50x34-12100-0x4143201040x53(1)-10013j0320000x370110170x450(5)01-313x131-1001-j-90500-30x36001-1/5(8/5)15/42x210101/5-3/5-3x14100-1/52/510j-14000-100x515/4005/8-1/812x213/4013/81/803x15/210-1/41/40j-14000-10由于，所以，有无穷多最优解，其中之一的最优解为最优值为。第五节 单纯形法的进一步讨论一 人工变量法我们已经知道，单纯形法求解是由一个初始可行基确定的初始基可行解开始迭代的，而且是以一个单位矩阵作为初始可行基，对于约束条件是“”形式的不等式，在这些约束条件的左端添加松弛变量转换为标准型后，就可以构成一个单位矩阵作为初始可行基。但对于含有“”和“”形式的约束条件，加入松弛变量和剩余变量化为标准型后，一般不存在一个单位矩阵可作为初始可行基，对于这样的线性规划问题，可采取人造基的方法，人为地添加人工变量，构造单位矩阵作为初始可行基。就是对于“”形式的不等式，减去一个非负的剩余变量再加上一个非负的人工变量；对于“”形式，可加上一个非负的人工变量。如， 标准型后： 添加人工变量后： 在约束条件中，的系数列向量就构成一个单位矩阵，可作为初始可行基，是基变量。但人工变量是后加到约束条件中的变量，是虚拟变量，这些变量在迭代结束后，必须为零，也就是说人工变量必须要从基变量中替换出来，变成非基变量，如果人工变量不能从基变量中替换出来(基变量中含有人工变量)，则原线性规划问题无解，因为后一个线性规划的解不是原线性规划的解，可能会不满足原线性规划的约束条件。如果在迭代结束后，人工变量为零，基变量中不含有人工变量，则原线性规划问题有解。如何使得人工变量从基变量中替换出来，有两种方法：大M法和两阶段法。1 大M法：大M法也称大M单纯形法，大M法与前面介绍的单纯形法，在计算表格、计算步骤等方面都一样，只是增加了处理大M系数的内容。大M法就是假定人工变量在目标函数中的系数为M，M是一个很大的正数。注意的是，在目标函数求max和min时，大M系数符号不同。 当目标函数求最大化max时，在目标函数中，给所有的人工变量都指定一个“M”系数，即只要在基变量中存在人工变量，目标函数就不可能实现最大化。 当目标函数求最小化min时，在目标函数中，给所有的人工变量都指定一个“+M”系数，即只要在基变量中存在人工变量，目标函数就不可能实现最小化。例10 用大M法求解下列线性规划问题解：为构造一个初始可行基，分别在约束条件中添加松弛变量、剩余变量和人工变量，并在目标函数中给人工变量加上“M” 系数，松弛变量和剩余变量在目标函数中的系数仍然是0，得，由于目标函数是求最小化,所以,最优判别条件应是所有变量的检验数。Cj-31100MMiCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20(1)00011cj-zj-3+6M1-M1-3M0M000x4103-20100-1Mx610(1)00-11-211x31-2010001cj-zj-11-M00M03M-10x412(3)001-22-541x210100-11-21x31-2010001cj-zj-10001M-1M+1-3x141