第03章线性规划

1第 3 章 线性规划数学规划是系统工程中最重要的分析方法之一，是运筹学的主要分支。它包括线性规划、非线性规划、整数规划和动态规划等。30 年代初出现的线性规划，1947 年丹茨基（George BDantzig ）发明单纯形法，理论上才得到完善。随着电子计算机的发展，成千上万个约束条件和变量的大型线性规划问题都可以求解。因此，无论从理论的成熟性看，还是从应用的广泛性看，线性规划都是运筹学的一个重要分支。它在工业、农业、交通运输、军事和计划管理等各方面都愈来愈得到广泛地应用。l 线性规划问题及其数学模型在生产过程中，要想提高工作效率和经济效益，一般有两条途径：一是进行技术改造，改进生产手段和条件。 （比如增添设备、改进工艺、挖掘潜力等）二是在生产手段和条件都不变的情况下，改善生产的组织和计划管理，作出最优安排，使生产手段和条件得到充分的利用。线性规划方法就是解决后一类问题的工具。后一类问题又可分为两个方面：一是在一定限制条件下，使得工作成果尽可能大；二是为完成既定任务，使资源消耗尽可能小。例 3 一 1 资源利用问题。某工厂计划生产 A、B 两种产品，生产这两种产品需要煤、电力和劳动力三种资源。已知该厂可利用的煤有 360t，电力有 200kw，劳动日有 300 个，生产每千克产品的资源消耗量和能获得的利润如表 31 所示。问该厂应生产 A，B 两种产品各多少千克才能使总利润最大？解 设生产 A，B 两种产品各为 x1，x 2 kg，则该问题可归结为，求一组变量 xl，x 2 满足下列条件：使得总利润 f=7x1+12x2 取得最大值。2例 32 下料问题。某工厂制造一种机床，每台机床需 A、B、C 三种不同长度的轴各一根，其毛坯长度；A 为 2.9m，B 为 2.1m，C 为 1.5m，它们用同一种圆钢来下料，每根圆钢长为 7.4m。要造 100 台机床，问如何下料最好？试建立其数学模型（不考虑下料截口损耗） 。 ”解 将各种可能的下料方案排列如表 32。设所用圆钢总数为 f 根，第 j 种下料方案。所用圆钢数为 xj 根，则由题意,上述模型即为所求模型。通过分析表 32，发现其中的方案 3、5、7、8 的料头过长，不经济，如果把它们舍弃，对剩下的 4 种方案进行搭配，仍然可以满足题意。为此可以将上述模型简化为下列模型（保持变量下标不变） 。例 33 运输问题。设有甲、乙、丙三个仓库，存有某种货物分别为 7t、4t 和 9t。现在要把这些货物分别送往 A、 B、C、D 四个商店，其需要量分别为 3t、6t 、5t 和 6t，各仓库到各商店的每吨运费以及收、发总量如表 33 所示。现在要求确定一个运输方案：从哪一个仓库运多少货到哪一个商店，使得各个商店都能得到货物需要量，各个仓库都能发完存货，而且总的运输费用最低？试建立其数学模型。3解 记总运费为 Z，设 xij 为 i 仓库到 j 商店的货物量，其中 i=1，2，3 分别代表甲、乙、丙仓库，j=1， 2，3，4 分别代表 A、B、C 、D 商店，则根据题意：上述各例，都是要求一组非负变量，在满足一组线性等式或线性不等式的前提下，使一个线性函数取得最大值或最小值，这一类问题就称为线性规划问题。将上述问题得出的数学表达式加以概括和抽象，就可得到线性规划问题的一般数学模型：求一组变量 xj，j1，2，n，满足条件使函数取得最大值或最小值。如果简写，则线性规划问题的数学模型可以表示为(3-1)(3-2)式（31）称为目标函数，式（32）称为约束条件。式中 max（min）f 目标函数取最大（最小）值；xj决策变量，又称为生产活动或活动方式；cj决策变量在目标函数中的系数，又称为利益系数、价值或效果系数；aij决策变量在约束条件中的系数，又称为投入产出系数或技术系数；bi资源限制量；n决策变量的个数；4m约束条件（不包括非负约束条件）的个数。把满足约束条件式（32）的任意一组解称为线性规划问题的可行解，使得目标函数f 取得最优值的可行解称为线性规划问题的最优解。如何求得线性规划问题的最优解，就是本章所要讨论的中心问题。2 线性规划问题的图解法在介绍线性规划问题的一般解法之前，我们先介绍只含有两个变量的线性规划问题的图解法。图解法不仅简单而且直观，有助于了解线性规划问题求解的基本原理。例 34 考虑下列线性规划问题解 在该问题的约束条件中，共有五个不等式（包括两个非负约束条件） 。在以 xl，x 2 为坐标轴的直角坐标系中，每一个不等式的解的集合均为一个半平面。所以同时满足五个不等式的解的集合一定是五个半平面的交集，称为可行域，即凸五边形 OABCD。如图 31所示。可行域的五个顶点坐标分别为 O（0，0） ，A（0，2） ，B（l，4） ，C（4，1） ，D （2，0） 。下面讨论如何在可行域上找到使目标函数取得最小值的点，即问题的最优解。对于目标函数 f=-x1+x2，若令 f=f0 为一常数，则目标函数在坐标平面上表现为一条确定的直线，如果 f0 取不同的值时，那么目标函数在平面坐标上是一组平行直线束，直线的斜率为 1。如果知道目标函数沿某一方向移动时函数值减少（或增大） ，那么根据目标函数的优化方向，便很容易求得使目标函数取得最大值（或最小值）的解，即问题的最优解。由目标函数 f=-x1+x2 可知，如果 x1 增大，x 2 减小，则 f 减小。因此为使 f 取得最小值，目标函数线应沿着 x1 增大，x 2 减小的方向移动。显然点 C 是可行域上使 f 取得最小值的点，于是得到问题的最优解为x1=4，x 2=1对应的目标函数的最小值为min f-4+13同样，如果目标函数为求最大值，则点 B 为问题的最优解，即x1=2, x2=4对应的目标函数的最大值为max f-1+4=3。如果将例 34 中的目标函数变为 min f=-x1+2x2，约束条件不变，由于目标函数的斜率与约束条件 x1-2x22 对应的边界直线的斜率相同，根据上述方法可知，线段 CD 上的任一点都是问题的最优解，即问题有无穷多个最优解。如果将例 3-4 中的目标函数变为 max f=x1+x2，去掉约束条件 x1+x25，则问题的可行域无界，目标函数的最大值趋于无穷大。这种情况无最优解。5如果在例 3-4 的约束条件中再增加一个约束条件 x1+x26，则可行域是空集，这时无可行解，当然也就无最优解了。通过两个变量线性规划问题的图解法，可以得到如下结论：1）线性规划问题的所有可行解组成的可行域是一个凸集，即可行域上任意两点之间的连线都在可行域内。2）若一个线性规划问题存在最优解，则至少有一个最优解在可行域的顶点上达到；若在两个顶点上同时达到最优，则这两顶点连线上的任一点都是最优解，这时称有无穷多个最优解。3）若可行域呈现无界区域，则可能有最优解，也可能出现最优解无界的情形，这时称最优解不存在或无最优解。4）若可行域为空集，这时无可行解，当然也就无最优解。上述结论对于含有两个以上变量的线性规划问题同样适用。图解法虽然直观、简便，但只能用于两个，最多三个变量的线性规划问题，当变量个数超过三个时，用图解法就很难处理了。因此在后面将要介绍线性规划问题的一般解法单纯形法。3 线性规划问题的标准形式及其解的概念由于具体问题的线性规划模型是各式各样的，为了求解的方便，就需要把线性规划问题的一般数学形式化成如下标准形式下面讨论如何将一般形式的线性规划问题化为标准形式。3.1 含有不等式约束条件分两种情形讨论：1）若原问题的第 i 个约束条件为 ，则可在不等式的左边加上一个新的变量使其变为等式约束，即： 称为松弛变量。2）若原问题的第 i 个约束条件为 ，则可在不等式左边减去一个新的变量，使其变为等式约束，即 称为剩余变量，也可称为松弛变量。应该指出，引人松弛变量和剩余变量后，对目标函数无任何影响，因为它们在目标函数中的系数全为零。3.2 含有负的右边项若原问题的第 i 个约束条件的右边项 bi0，则用-1 同时乘以约束条件的两边，使右边大于 0。63.3 含有自由变量若原问题中第 j 个变量 xj 没有约束，则 xj 就叫自由变量。自由变量可用两非负变量之差代换，即，令 ，并代人约束条件和目标函数中，便可消去自由变量。3.4 目标函数为求最小值例 35 将下列线性规划问题化为标准形式。解 这个问题可以按以上介绍的标准化方法进行。1）令 ，或写成 。2）在第一个约束条件中引人松弛变量 x6，第二个约束条件中引人剩余变量 x7。3）对第三个约束条件两边同乘以-1。4）将引入的变量代入目标函数和约束条件，并令 f= -f,把求 min f 变为求 max f，于是得到该问题的标准形式为解此规划问题，得到 x4、x 5 和 max f 的值，则 x3=x4-x5，min f=max f ，从而可得到原问题的解。在讨论线性规划问题的解法之前，先来介绍一下标准形式线性规划问题的解的概念。与一般形式的线性规划问题类似，把满足约束条件式（33）的解称为可行解，把满足目标函数的可行解称为最优解，或者说使目标函数达到最大值的可行解叫最优解。对于标准形式的线性规问题，其约束条件式（33）为在此约束条件中，前 m 个等式构成线性方程组，对此方程组，若 m=n，且系数行列式不为零，则方程组有唯一组解，故不存在优化问题。若 mn，一般来说 mn，如果方程组的系数矩阵7的秩为 m，则该方程组有无穷多个解。假设前 m 个变量的系数列向量是线性独立的，构成的系数矩阵称为线性问题的一个基；称 P1、P 2、P m 为基向量，称与基向量对应的变量 x1, x2，x m。为基变量，其它变量称为非基变量。若令非基变量等于零，则可求得一个解为这样的解称为基本解，它的非零变量的个数不大于秩 m。基本解不一定都是可行的（同时要满足非负性条件） 。若基本解同时满足非负条件，就称为基本可行解，对应于基本可行解的基称为可行基。若基本可行解中的非零变量的个数小于 m，即基变量出现零值时，则此基本可行解称为退化的基本可行解。当其非零变量的个数等于 m，即基变量均为正值时，则此基本可行解称为非退化的基本可行解。显然，如果基矩阵 B 为 m 阶单位阵，则问题的一个基本可行解为线性规划问题的一个基本可行解，对应于可行域上的一个顶点。若线性规划问题有最优解，则必定在某个顶点处得到。虽然顶点数目是有限的，它不超过 采用枚举法找出所有基本可行解，然后一比较，最终可以找到最优解。但当 n、m 相当大时，这种办法是行不通的。所以下面要介绍一种更好的方法，即单纯形法。4 单纯形法单纯形法（Simplex Method）是美国学者丹茨基（GBDantzig ）于 1947 年提出的。这一方法从根本上解决了线性规划的求解问题。单纯形法的基本思路是：根据问题的标准形式，从可行域中一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点） ，并使目标函数的值逐步增大；当目标函数达到最大值时，就得到了问题的最优解。4.1 单纯形法引例下面依据例 31，来引入单纯形算法。原线性规划问题的模型为8第一步：将一般形式的线性规划问题标准化。在约束条件中引人松弛变量 x3、x 4、x 5 有第二步：确定初始基本可行解。为了确定初始基本可行解，首先要找出初始可行基。由 3 可知，如果在约束方程的系数矩阵中能找到 m 个线性无关的单位向量，就能很容易地得到问题的一个初始基本可行解。若原问题的约束条件（不包括非负约束条件，下同）为一组“” 不等式，标准化后，可以松弛变量作为基变量，其余的变量为非基变量，令非基变量等于零，便可立即得到一个初始基本可行解。对于本例，x 3、x 4、x 5 为基变量，x 1、x 2 为非基变量，则问题的一个初始基本可行解为 X0（0 0 360 200 300） T，此时的目标函数值 f7x 1+12x20，意味着工厂没有进行生产，对应的利润为零。这正是我们生产规划的开始。若原问题的约束条件为一组“”不等式或一组等式或三种约束的混合，标准化后，如果约束方程的系数矩阵中不存在 m 个线性无关的单位向量，就要设法构成 m 个不同的单位列向量。有关这个问题将在后面进行讨论。为明显起见，把基变量放在等式左边，非基变量放在等式右边，由式（36）得：相应的目标函数用非基变量表示为：从目标函数表达式可以看出：非基变量 x1、x 2 的系数都是正数，因此增加 x1 或 x2 均可使目标函数 f 增加。所以只要在目标函数的表达式中还存在有正系数的非基变量，就表明目标函数还有增加的可能，就需要将非基变量与基变量进行对换。单纯形法的实质上就是进行基变量和非基变量的代换过程。新进入左边的变量叫换入变量，被代换到右边的变量叫换出变量。每完成一次代换，就是一次选代，而对应的目标函数值就相应地有所增加，至少也与代换前相同。第三步：确定换入换出变量，进行第一次选代。在进行单纯形法迭代时，每次只能代换一个变量。一般选择正系数最大的那个非基变量为换入变量，并成为新的基变量，本例中 x2 为换入变量。同时，还要从原来的基变量中确定出一个为换出变量，成为新的非基变量。9换出变量的确定要经过计算换入变量的最大步长。x 2 作为换入变量，由于受到有关资源的限制，是不能随意安排调整的。我们把资源允许的最大调整量叫最大步长。故当 x1=0时，要保证 x3、x 4、x 50，有显然，为同时满足以上三个条件，x 2 的调整量只能是 x2=min90，40，30=30即 x2=30 是调整的最大步长。因为 x2 的最大步长是由式（3-7）中的第 3 个约束方程求得的，即当 x1=0，x 2=30 时，x50，因此 x5 就是换出变量，这样一来就得到了新的基变量 x3、x 4、x 2。 ，新的非基变量为 xl、x 5，此时需要把式（3-7）中 x2 与 x5 的位置对换。由式（ 37）中的第 3 式得将上式代人式（3-7）中的第 1，第 2 两式，消掉 x2，有把目标函数中的基变量用非基变量代替，得到调整以后的目标函数为当非基变量 xl=x50 时，得到另一个基本可行解是目标函数值 f=360。由此可见，调整 x2 后，目标函数值增加了 360。从目标函数的表达式可以看出，非变量 x1 的系数为正，说明调整 x1 将会使目标函数值继续增加，x 1 不是规划问题的最优解。第四步：确定新的换人换出变量，进行第二次迭代。由于非基变量 x5 在目标函数中的系数为-1.2，调整 x5 将使目标函数值减少，又因目标函数中只有 x1 的系数为正，于是便知 x1 是新的换人变量，而新的换出变量还要通过计算最大步长来确定。xl 的最大步长为 x1min30.77，20，100 20x1 的最大步长是由式（38）中的第二个方程确定的，对应的基变量 x4 为新的换出变量，由式（3 一 8）中的第二式得将上式代人式（38）的第一、第三式，消掉 x1，有10调整后的目标函数为当 x4=x5=0 时，可得到一个新的基本可行解为 X=(20 24 84 0 0） T，目标函数值得 f428。因为调整后的目标函数的表达式中非基变量的系数全部非正，所以 X2 为最优解。即当A 产品生产 20kg，B 产品生产 24kg，工厂才能获得最大利润 428 百元。x384 代表煤的剩余量为 84t，x 4x 50 表示电力和劳动日完全利用，没有剩余。42 单纯形表解法上面的引例说明了用单纯形法解线性规划问题的基本思路和理论依据。但在实际求解中，用上述方法比较麻烦，而且容易出错，故多采用单纯形表解法，下面仍以上面的例子来说明表上求解的步骤和方法，并引出一般线性规划问题的解法。第一步：标准化（见前解法第一步） 。第二步：找出初始基变量，并将目标函数中的基变量用非基变量代替。l）检查约束方程的系数矩阵是否含有 m 阶单位阵。若没有，则设法构造。 m 阶单位阵对应的变量为基变量，其余变量为非基变量。上面的问题中 3 阶单位矩阵对应的变量 x3、x 4、x 5 为基变量，x 1、x 2 为非基变量。2）检查目标函数中是否含有基变量，如果有，则用非基变量加以代换。上面问题的目标函数中不含有基变量，故不需代换。第三步：作初始单纯形表。初始单纯形表就是把线性规划模型中的变量和相关的系数规则地排成一种表格，它和线性规划模型具有一对应的关系。对于上面的问题，可将目标函数写成类似于约束方程的形式，即f7x l12x 20其初始单纯形表如表 34 所示。初始单纯形表的最上一行存放全体变量，最左一列存放基变量，最右一列存放约束方程右边项，中间存放约束方程组中对应变量的系数，最下一行存放目标函数中变量的系数。注意这里的目标函数中对应于基变量的系数必须为零，右下角存放目标函数中常数项的相11反数。初始单纯形表的最后一列代表一组初始可行解，每完成一次迭代，就有一个新的单纯形表。在单纯形表中，目标函数 f 所在的行叫判别数或检验数行，记为 j，j1，2，n，因为在目标函数中不含基变量，所以基变量所对应的判别数为零，如表 34 中基变量 x3、x 4、x 5 对应的判别数为零。在得到问题的一个基本可行解后，就需要判断它是否是最优解，为此下面介绍最优解的判别准则。最优解判别准则：当所有判别数全部非正时，即 j0，j1，2，n 时，对应的基本可行解为最优解。由此准则可知，经有限次迭代后，若所有判别数全部非正，则得到了问题的最优解，否则应继续迭代。这个准则和前述引例中判断最优解的方法是一致的。由表 34 可知，问题的判别数中含有正的判别数，故初始基本可行解不一定是最优解。第四步：确定主元。在所有正判别数中，最大判别数所在的列叫主元列，主元列对应的变量即为换人变量，若则 k 所在的列为主元列，对应的变量 xk 为换人变量。若上式中的最大值多于一个时，即原则上可以在 k、 r、对应的变量中任选一个作为换人变量，但为了运算过程有规可循，我们规定，取下标 k、r、 中最小的判别数对应的变量为换人变量。当主元列确定后，就可按下式确定主元。若 则 alk 所在的行叫主元行，对应的基变量为换出变量，主元列与主元行的交叉元素 alk。就是主元。当最小比值 不唯一时，任取其中一行作为主元行。显然，主元所对应的非基变量为换人变量，主元所对应的基变量为换出变量。对于上例，由知，x 2 为换人变量。由知，换出变量为 x5，主元为 10，为清楚起见，主元用方框圈起来。注意，若有一个判别数 k0，并且对一切 il ，2 ，m 有 aik0，那么该线性规划问题无解，即无有限值最优解。这就是无界解的判别准则。第五步：开始迭代。单纯形迭代实际上是对单纯形表作初等行变换。首先把换人变量放人基底，然后对主元行所有元素除以主元，化主元为 1，接着对其它行（包括目标函数行）施行行变换，化主元列其它元素为零，至此第一次迭代结束。检查表中的判别数是否全部非正，若是，则迭代终止，否则继续迭代。上面问题的第一次选代结果如表 35 所示。12根据表 35，可以写出第一次迭代后线性规划问题的约束方程为目标函数为对以上两式稍作变换就得到了第一种解法的形式。可见单纯形表解法与前述引例方法是一致的。由上表可得到问题的一个基本可行解为 X（0 30 240 50 0） T，相应的目标函数值为 f 360。因此，单纯形表的最右一列表示问题的一个基本可行解中基变量的值，右下角元素的相反数表示相应的目标函数值。因上表中的判别数不全非正，故需继续迭代。第六步：进行第二次迭代。判别数中只有 x1 对应的判别数为正，故其为新的换人变量。由知 2.5 为主元，对应的基变量 x4 为换出变量。其退出基底，x 1 进人基底，化主元为 1，主元列其它元素为零，第二次迭代结束，结果如表 36 所示。由表 36 可知，全部判别数非正，于是得到了问题的最优解为X（20 24 84 0 0） T目标函数 f 428。可见单纯形表迭代结果与 41 中迭代结果完全相同。4.3 单纯形表的另两种常见形式大多数线性规划问题标准化后，其约束方程组的系数矩阵中并不含有 m 阶单位阵。为了得到问题的一组初始基变量，通常采用的方法是在每一个约束方程中加人一个非负的虚13拟变量，这种虚拟的变量称为人工变量。对于一个标准化的线性规划问题，其约束方程为在第 i 个约束方程中加人一个人工变量 Xn+1，得到如果以 xn+l，x n+m 为基变量， x1，x n 为非基变量，便可得到问题的一个初始基本可行解为 X0（0 0 0 b1 b2 bm） T。因为人工变量是加人到原约束方程组中的虚拟变量，为了不改变原来问题的性质，就应将它们从基变量中逐渐替换掉，即使人工变量为零。处理人工变量的方法有两阶段法和大 M 法，下面我们分别介绍这两种方法。4.3.l 两阶段法两阶段法是将加入人工变量后的线性规划问题分两阶段来求解。第一阶段是借助于以下辅助线性规划问题，为原问题求得一个基本可行解。用单纯形法对上述问题求解，若得到 W0，即所有的人工变量都为零，表示原问题已得到了一个基本可行解；若 W0，即不是所有人工变量都为零，表示原问题无可行解，应停止计算。第二阶段是从第一阶段得到的基本可行解开始，继续用单纯形法进行迭代，直到找出原问题的最优解或判断无最优解。以上介绍的方法是对每个约束方程中都加人人工变量。如果原问题约束方程的系数矩阵中存在有一些单位向量，为减少计算工作量，可以只在部分约束方程中加入人工变量。下面通过一个例子说明两阶段问题的求解步骤和方法。例 36 用两阶段法求解下列线性规划问题。解 第一步：标准化。14在第一个约束条件中引入松弛变量 x4，第二个约束条件中引人剩余变量 x5，得到原问题的标准形式为第二步：确定初始基变量，并将目标函数中的基变量用非基变量代替。式（310）的约束方程中只有 x4 的系数向量为单位向量，为形成 3 阶单位矩阵，在第二和第三个约束方程中分别引入人工变量 x6 和 x7，得第一阶段的规划问题为x4，x 6，x 7 为初始基变量，把目标函数 w 中的基变量用非基变量代替，有即如果原问题的目标函数中也含有基变量时，也必须用非基变量代替。第三步：作初始单纯形表。作初始单纯形表的基本要求与前面介绍的完全一样，唯一的区别是增加了第一阶段问题的目标函数 W 行，见表 37。第四步：确定主元。第一阶段问题以 W 为目标函数，主元的确定方法与前面相同。15第五步：进行第一阶段迭代。与前述方法相同，即换出变量退出基底，换人变量进人基底，化主元为 1，主元列其它元素（包括 f 行的元素）为零，完成一次迭代。若行的判别数不全非正，则继续选代。该问题经过二次迭代后，w 行的判别数全部非正，且有 max w0，故得到了原问题的一组基变量 x4、x 2、x 3，至此第一阶段迭代结束。第六步：进行第二阶段迭代。从第一阶段的最终单纯形表中去掉人工变量 x6、x 7 所对应的列及 w 行，得到第二阶段的单纯形表，如表 38 所示。经过一次迭代后，判别数全部非正，得到原问题的最优解为X（4 1 9 0 0） T相应的目标函数值 f2。4.3.2 大 M 法大 M 法的基本思路是对于标准形式的线性规划问题，引人人工变量后将其改造为其中 M 为充分大的正数，记为 M1，下面举例说明大 M 法的具体迭代过程。例 37 求解下列线性规划问题。解 引人剩余变量和人工变量将上面的线性规划模型化为标准形式如下16根据模型式（313）建立初始单纯形表，如表 39 所示。因为 M 是充分大的数，所以判别数行的全部元素小于等于零，说明此表已达到最优，最优解为则由此可见，凡约束条件为大于或等于型不等式时，均需引入人工变量，在目标函数中，人工变量前面均应乘上系数 M，M1，而且，在极大值问题中，M 前面为负号。这样，可以确保在获得最优解时消去人工变量，如果人工变量不能通过迭代而消去，则说明该问题无最优解。到此为止，对于任何形式的线性规划问题，总可以利用单纯形法、两阶段法或大 M 法对其求解。5 改进单纯形法对于较简单的线性规划问题，可以用单纯形表法求解。但当线性规划问题的规模较大时，用单纯形表求解是非常困难的，甚至是不可能的。为此就出现了一种新的算法改进单纯形法。这种方法从实质上来说是一种矩阵算法，主要是通过基矩阵求逆来实现单纯形迭代。同时，这种方法是用计算机求解线性规划问题的主要算法。对于标准形式的线性规划问题 )143(0,max2121212121 nmnmnxbxaaxccf 如果令17则式（314）可用矩阵形式表示为如果用列向量 Pj，j1，2，n 代表矩阵 A 的第 j 列，则有设前 m 个列向量是线性独立的，则 B（P 1 P2 Pm）为线性规划问题的基矩阵。其余列向量构成的矩阵 N（ Pm+1 Pn）称为非基子矩阵。A（B N） 。基矩阵 B 对应的变量为基变量 ，用 XB 表示，X B（x l x2 xm） T，非基子矩阵 N 对应的变量为 非基变量，用 XN 表示，X N=(xm+1 xn)T，则有 X（X B XN） T。同样地，C 可以表示为 C=（ CB CN） ，C B=（c 1 c2 cm） ，C N=（c m+1 cn） 。于是式（3 一 15）可改写为)0( )(1111NBCABCB18如果判别数 ，则 为问题的最优可行解，相应的目标函数值 ，否则，应确定新的基矩阵 B1 继续迭代。我们知道，单纯形迭代实际上是由一个基矩阵到另一个基矩阵的过程，而且每次迭代只能是一个变量换入，一个变量换出，即基阵中只有一个列向量发生变化。设 BO=（P 1 P2. Pl Pm）为初始基矩阵。若对应的判别数行向量 。不全非正，即基矩阵 B0 不是最优基，根据前述方法确定的换人变量为 xk，换出变量 xl，则以列向量 Pk 代换 Pl得到新的基矩阵为 。由前面的推导可知，如果求得了 ，那么就可以求出一组新的基本可行解、相应的目标函数值和判别数等。由此可见，在改进单纯形法计算中，关键是每次迭代时基矩阵的逆阵 B-1。下面讨论其求法。与单纯形表解法类似，改进单纯形法通常也是用 m 个单位向量构成的单位阵作为初始基矩阵，即以列向量 Pk 代换 Pl后，得到的新基矩阵为因此，基矩阵求逆实际上就是计算形如上式这种矩阵的逆，根据线性代数的理论，不难求得 Bl 的逆 Bl-1 为19改进单纯形法的计算步骤与单纯形法类似，下面通过一个具体实例加以说明。例 38 用改进单纯形法求解下列线性规划问题。解 第一步：标准化。引人松弛变量 x3，x 4，x 5，得第二步：确定初始可行解。由上式得取 x3、x 4、x 5 为初始基变量，初始基为则有由此可得非基变量的列向量为20初始基本可行解为相应的目标函数值为非基变量判别数为以上结果可列成表 311 的形式。实际上表 311 是一种特殊形式的单纯形表，它是按表 310 的格式构造的。因 N00，故 BO 不是最优基。第三步：确定新基，进行第一次迭代。由 max 1， 2 12， xl 为换入变量，P 10 为换入列向量。由可知，6 为主元，x 5 为换出变量，新的基变量为 x3，x 4，x 1，故得新基 B1 为此时有21由此可得XB0=b因 20，故 B1 不是最优基，以上结果可用表 312 表示。第四步：确定新基，进行第二次迭代。 20，故 x2 为换入变量，P 21 为换人列向量同样地，按照第二步的方法可知，x 3 为换出变量，P 3l 为换出列向量，新的基变量为x2、x 4、x l，所得到的新基为此时有22由此可得因判别数 N20，所以迭代终止，得到问题的最优解为X（114 94 0 l2 0） T相应的目标函数值f2314上述结果可用表 313 表示。从以上运算过程可以看出，作为手算来说，采用改进单纯形并不方便，而且很容易出错，但对于计算机而言，用改进单纯形法不仅可以节约内存，而且运算量较小，所以对求解大型的线性规划问题较为有利。6 对偶单纯形法6.1 线性规划的对偶问题我们先看一个简单的例子，然后提出对偶问题。例 39 某厂在计划期内要安排生产 A、B 两种产品，这两种产品分别需要在甲、乙、丙三种不同的设备上加工，有关数据如表 314 所示。问应如何安排生产计划才能使利润最大？23解 如果设 A、 B 两种产品生产的件数分别为 xl、x 2，则这个问题可以归结为求解下列线性规划问题（LP 1）现在从另一个角度来考虑这个问题。假设该厂的决策者，决定不生产产品 A、B 而将生产设备的有效台时用于接受外加工来收取加工费。此时就要考虑给每台设备的台时如何定价。设 y1、y 2 、y 3 分别表示设备甲、乙、丙每台时的价格。在定价时必须考虑到，将生产一件产品 A 的各设备的台时用于外加工时，所得加工费不得低于生产一件产品 A 可得的利润，即否则该厂不会接受外加工，而宁愿自己生产产品 A。同理有若把设备的所有台时都用于外加工，总的收人为因为在定价时，受市场调节的影响不能把价格任意提高，故其定价方案只有使总收人g（即委托加工单位支出的总加工费用）尽可能低，才能得到其它单位的委托加工。因此该厂只能得到 g 的最小值，于是，这个问题可以用下列线性规划描述（LP 2）显然，当 min g=max f 时，工厂决策者认为这两种考虑具有相同的结果，都是最优方案。比较 LP1 和 LP2，可知它们之间有着密切的联系，两者包含有相同的数据，只是位置不同而已。如果称前者为原问题，则后者就叫前者的对偶问题，反过来也是如此，即两者互为对偶问题。更一般地，若原问题为24则对偶问题为其中 yi 叫做对偶变量。若表示成矩阵形式，则有其中 A 是 mn 矩阵，C 是 n 维向量，b 是 m 维列向量， X 是 n 维列向量、为原问题的变量，Y 是 m 维行向量、为对偶问题的变量。上式称为对偶关系的对称形式（或叫对偶标准形式） ，一般情况下，原问题与对偶问题的变换关系可归纳为表 315 所列的对应关系。若原规划问题的约束条件中含有约束，可在其两边同乘以-1，统一为约束。这里，右边项没有符号限制。根据表 3 一 15，可以写出下列一对线性规划问题：式（325）称为对偶关系的非对称形式。例：求标准线性规划问题的对偶问题解：先将标准线性规划问题化为等价的 LP 问题250max0ax0maxXbACfXbAfXbACf其对偶问题为 无 符 号 限 制YCAbgVUCAbgVUYmin0,)(,min例 310 写出下列线性规划问题的对偶问题。解 用1 乘第二个约束条件的两端，把它变成约束，根据表 315 即可写出其对偶问题为如果求这个问题的对偶，显然就得到了原问题的对偶问题。6.2 对偶问题的基本性质下面介绍对偶问题的几条重要性质，以揭示原问题的解与对偶问题的解之间的一些重要关系，并为后面讨论对偶单纯形法奠定基础。1）若 X 和 Y 分别是原问题和对偶问题的任一可行解，则必有 CXYb ，即 fg2）若 X*和 Y*分别为原问题和对偶问题的可行解，且可行解对应的原问题和对偶问题的目标函数值相等，即 CX*Y*b，则 X*、Y* 分别为原问题和对偶问题的最优解。3）若原问题和对偶问题之一的最优解无界，则另一个无可行解；若其中之一无可行解，则另一个的最优解无界或无可行解。也就是说，原问题和对偶问题之一无最优解，则另一个也无最优解。4）若原问题和对偶问题之一有最优解，则另一个也有最优解，且两者的最优目标函数值相等。5）若原问题的最优解为 XBB -1b，则对偶问题的最优解为 YC BB-1。6）根据原问题最优单纯形表中的判别数可以读出对偶问题的最优解。对于第 6 个性质下面作一说明。设原问题和对偶问题为式（324） ，在原问题的约束条件中分别引人松弛变量 Xs 和剩26余变量 Ys，其中 Xs 为 m 维列向量，Y s 为 n 维列向量，有设 B 为原问题的一个最优基，则原问题可改写为相应的对偶问题为这里 Ys（Y s1 Ys2） ，Y s1 是对应于原问题中基变量 XB 的剩余变量，Y s2 是对应于原问题中非基变量 XN 的剩余变量。原问题的最优解为 XBB -1b，相应的基变量 XB 的判别数为 0，非基变量 XN 的判别数为 CN CBB-1N，松弛变量 Xs 的判别数为 C BB-1，把对偶问题的最优解 YC BB-1 代人上式得由此可见，原问题的最优单纯形表中的判别数对应于对偶问题的最优解的负值。它们的关系如表 316 所示。同样地若原问题和对偶问题为武（325）所示的非对称形式，则可得到表 317 所示的结果。根据表 3-17 可知，原问题最优表中的判别数对应于对偶问题最优解中剩余变量的负值，而对偶决策变量的值 YC BB-1 看起来还不能直接从表 317 中读出。当然，如果知道了B-1 和 CB 就可以直接计算出 Y 来，但下面讨论如何从表 317 中直接读出对偶变量的值。假定在原问题的约束条件的系数矩阵中有一个 m 阶单位阵，以此为初始可行基进行迭代得到最优基 B，则在最优表 316 中，原来为单位阵的地方就变成了 B-1，而在初始表中和 B-1 相对应的基矩阵 B 正好位于和最优表 316 中的单位阵相对应的位置，若用 CI 表示和初始表中单位阵相对应变量的价值系数向量，则在最优表 316 中 B-1 下的判别数将是 CIC BB-1。因而若由最优表 316 中 B-1 下的判别数减去相应的价值系数，则正好得到其对偶问题最优解的负值，即：Y C BB1 ，特别地，当初始表中的单位阵是由引人松弛变量后而形成的，则有 CI0。在这种情况下，最优表 316 中 B1 下面的判别数就27正好等于其对偶问题的最优解的负值。下面以例 39 加以说明。设式（320）为原问题式（321）为对偶问题，在原问题的约束条件中引人松弛变量 x3、x 4、x 5，按单纯形法得原问题的初始表和最优表分别为表 318 和表 3 一 19。由表 319 知，原问题的最优解为 X（35 10 25 0 0） T，最优目标函数值为max f 215在表 318 中，松弛变量 x3，x 4，x 5 的系数矩阵构成单位阵，故在最优表 319 中对应的系数矩阵为最优基的逆阵且对应的判别数等于它在对偶问题式（321）中的最优解的负值。即：Y（y1 y2 y3）（0 1 3） ，相应的目标函数值为 min gmax f 215。另一方面，Y 也可按式 YC BB1 计算，由于最优表中的单位阵对应于基变量x3、x 1、x 2，所以它们在初始表 318 中的系数列向量构成最优基 B，故 CB（c 3 c1 c2）（0 5 4） ，则有相应的目标函数值为为了验证按上述方法确定的对偶问题的最优解的正确性，按单纯形法对对偶问题式（321）进行迭代，得对偶问题的最优表如表 320 所列。表中 y6，y 7 为人工变量，gg 。由表 320 可知，对偶问题式（3-21）的最优解和最优目标函数值与上述方法求得的完全相同。由此可见，从表 320 的判别数中也可以直接读出原问题的最优解，这一点给28我们一个重要的启示，即在求解线性规划问题时，可在原问题和对偶问题中挑选容易求解的进行求解计算，只要求出它的最优解，另一个的最优解也就很容易地得到。一般来说，线性规划求解的工作量在很大程度上取决于约束条件数目的多少，约束条件多，基矩阵的阶数高，计算量大。因此，对于约束条件多，变量少的规划问题，其对偶规划的约束条件少，变量多，若对对偶规划求解，就可减少计算工作量。6.3 对偶问题的经济意义影子价格我们仍以例 39 为依据，其原问题和对偶问题的模型分别为通过求解，原问题和对偶问题的最优解分别为为了分析对偶问题的经济意义，我们对原规划及其对偶问题的求解进行图示分析，见图32。在图 32 中，增画了三条直线（用虚线描述） ，分别是这三条直线分别代表三种资源（各台设备可利用的台时数）各增加 1 个单位后的边界线。若资源 b1，b 2 保持不变，仅使 b345 增加 1 个单位，则最优点变为 H（34，12） ，此时就是说，原模型总利润的增量刚好等于对偶模型的变量 y3 的最优解。而变量 y3 是对应于原29模型的第 3 个约束条件即资源 b3 的。所以，y 3 的取值反映了资源 b3 的单位增量所带来的利润的增加量。换言之，y 33 反映了资源 b3 的一种单位价格，称为“影子价格” 。由此可见，某一约束条件的影子价格表示为当它所对应的约束条件右端的常数增加一个单位时（假设原问