第03章线性规划

1、第3章 线性规划数学规划是系统工程中最重要的分析方法之一，是运筹学的主要分支。它包括线性规划、非线性规划、整数规划和动态规划等。30年代初出现的线性规划，1947年丹茨基（George BDantzig）发明单纯形法，理论上才得到完善。随着电子计算机的发展，成千上万个约束条件和变量的大型线性规划问题都可以求解。因此，无论从理论的成熟性看，还是从应用的广泛性看，线性规划都是运筹学的一个重要分支。它在工业、农业、交通运输、军事和计划管理等各方面都愈来愈得到广泛地应用。l 线性规划问题及其数学模型在生产过程中，要想提高工作效率和经济效益，一般有两条途径：一是进行技术改造，改进生产手段和条件。（比如增

2、添设备、改进工艺、挖掘潜力等）二是在生产手段和条件都不变的情况下，改善生产的组织和计划管理，作出最优安排，使生产手段和条件得到充分的利用。线性规划方法就是解决后一类问题的工具。后一类问题又可分为两个方面：一是在一定限制条件下，使得工作成果尽可能大；二是为完成既定任务，使资源消耗尽可能小。例3一1 资源利用问题。某工厂计划生产A、B两种产品，生产这两种产品需要煤、电力和劳动力三种资源。已知该厂可利用的煤有360t，电力有200kw，劳动日有300个，生产每千克产品的资源消耗量和能获得的利润如表31所示。问该厂应生产A，B两种产品各多少千克才能使总利润最大？ 解 设生产A，B两种产品各为x1，x2

3、 kg，则该问题可归结为，求一组变量xl，x2满足下列条件：使得总利润f=7x1+12x2取得最大值。例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种方案进行搭配，仍然

4、可以满足题意。为此可以将上述模型简化为下列模型（保持变量下标不变）。例33 运输问题。设有甲、乙、丙三个仓库，存有某种货物分别为7t、4t和9t。现在要把这些货物分别送往A、B、C、D四个商店，其需要量分别为3t、6t、5t和6t，各仓库到各商店的每吨运费以及收、发总量如表33所示。 现在要求确定一个运输方案：从哪一个仓库运多少货到哪一个商店，使得各个商店都能得到货物需要量，各个仓库都能发完存货，而且总的运输费用最低？试建立其数学模型。解 记总运费为Z，设xij为i仓库到j商店的货物量，其中i=1，2，3分别代表甲、乙、丙仓库，j=1，2，3，4分别代表A、B、C、D商店，则根据题意：上述各例

5、，都是要求一组非负变量，在满足一组线性等式或线性不等式的前提下，使一个线性函数取得最大值或最小值，这一类问题就称为线性规划问题。 将上述问题得出的数学表达式加以概括和抽象，就可得到线性规划问题的一般数学模型：求一组变量xj，j1，2，n，满足条件使函数取得最大值或最小值。如果简写，则线性规划问题的数学模型可以表示为 (3-1) (3-2)式（31）称为目标函数，式（32）称为约束条件。式中max（min）f目标函数取最大（最小）值；xj决策变量，又称为生产活动或活动方式；cj决策变量在目标函数中的系数，又称为利益系数、价值或效果系数； aij决策变量在约束条件中的系数，又称为投入产出系数或技术

6、系数； bi资源限制量； n决策变量的个数； m约束条件（不包括非负约束条件）的个数。把满足约束条件式（32）的任意一组解称为线性规划问题的可行解，使得目标函数f取得最优值的可行解称为线性规划问题的最优解。如何求得线性规划问题的最优解，就是本章所要讨论的中心问题。2 线性规划问题的图解法 在介绍线性规划问题的一般解法之前，我们先介绍只含有两个变量的线性规划问题的图解法。图解法不仅简单而且直观，有助于了解线性规划问题求解的基本原理。例34 考虑下列线性规划问题解 在该问题的约束条件中，共有五个不等式（包括两个非负约束条件）。在以xl，x2为坐标轴的直角坐标系中，每一个不等式的解的集合均为一个半平

7、面。所以同时满足五个不等式的解的集合一定是五个半平面的交集，称为可行域，即凸五边形 OABCD。如图 31所示。可行域的五个顶点坐标分别为O（0，0），A（0，2），B（l，4），C（4，1），D（2，0）。 下面讨论如何在可行域上找到使目标函数取得最小值的点，即问题的最优解。 对于目标函数f=-x1+x2，若令f=f0为一常数，则目标函数在坐标平面上表现为一条确定的直线，如果f0 取不同的值时，那么目标函数在平面坐标上是一组平行直线束，直线的斜率为1。如果知道目标函数沿某一方向移动时函数值减少（或增大），那么根据目标函数的优化方向，便很容易求得使目标函数取得最大值（或最小值）的解，即问题的最

8、优解。 由目标函数f=-x1+x2可知，如果x1增大，x2减小，则f减小。因此为使f取得最小值，目标函数线应沿着x1增大，x2减小的方向移动。显然点C是可行域上使f取得最小值的点，于是得到问题的最优解为 x1=4，x2=1对应的目标函数的最小值为min f-4+13 同样，如果目标函数为求最大值，则点B为问题的最优解，即 x1=2, x2=4对应的目标函数的最大值为 max f-1+4=3。 如果将例 34中的目标函数变为 min f=-x1+2x2，约束条件不变，由于目标函数的斜率与约束条件x1-2x22对应的边界直线的斜率相同，根据上述方法可知，线段CD上的任一点都是问题的最优解，即问题有

9、无穷多个最优解。 如果将例3-4中的目标函数变为max f=x1+x2，去掉约束条件x1+x25，则问题的可行域无界，目标函数的最大值趋于无穷大。这种情况无最优解。 如果在例3-4的约束条件中再增加一个约束条件x1+x26，则可行域是空集，这时无可行解，当然也就无最优解了。 通过两个变量线性规划问题的图解法，可以得到如下结论： 1）线性规划问题的所有可行解组成的可行域是一个凸集，即可行域上任意两点之间的连线都在可行域内。 2）若一个线性规划问题存在最优解，则至少有一个最优解在可行域的顶点上达到；若在两个顶点上同时达到最优，则这两顶点连线上的任一点都是最优解，这时称有无穷多个最优解。 3）若可行

10、域呈现无界区域，则可能有最优解，也可能出现最优解无界的情形，这时称最优解不存在或无最优解。 4）若可行域为空集，这时无可行解，当然也就无最优解。上述结论对于含有两个以上变量的线性规划问题同样适用。图解法虽然直观、简便，但只能用于两个，最多三个变量的线性规划问题，当变量个数超过三个时，用图解法就很难处理了。因此在后面将要介绍线性规划问题的一般解法单纯形法。3 线性规划问题的标准形式及其解的概念由于具体问题的线性规划模型是各式各样的，为了求解的方便，就需要把线性规划问题的一般数学形式化成如下标准形式 下面讨论如何将一般形式的线性规划问题化为标准形式。3.1 含有不等式约束条件 分两种情形讨论：1）

11、若原问题的第 i个约束条件为，则可在不等式的左边加上一个新的变量使其变为等式约束，即：称为松弛变量。2）若原问题的第i个约束条件为，则可在不等式左边减去一个新的变量，使其变为等式约束，即称为剩余变量，也可称为松弛变量。 应该指出，引人松弛变量和剩余变量后，对目标函数无任何影响，因为它们在目标函数中的系数全为零。3.2 含有负的右边项 若原问题的第i个约束条件的右边项bi0，则用-1同时乘以约束条件的两边，使右边大于0。3.3 含有自由变量 若原问题中第j个变量xj没有约束，则xj就叫自由变量。自由变量可用两非负变量之差代换，即，令，并代人约束条件和目标函数中，便可消去自由变量。3.4 目标函数

12、为求最小值例35 将下列线性规划问题化为标准形式。解 这个问题可以按以上介绍的标准化方法进行。 1）令，或写成。 2）在第一个约束条件中引人松弛变量x6，第二个约束条件中引人剩余变量x7。 3）对第三个约束条件两边同乘以-1。 4）将引入的变量代入目标函数和约束条件，并令f'=-f,把求 min f变为求 max f'，于是得到该问题的标准形式为 解此规划问题，得到 x4、x5和 max f的值，则 x3=x4-x5，min f=max f，从而可得到原问题的解。 在讨论线性规划问题的解法之前，先来介绍一下标准形式线性规划问题的解的概念。 与一般形式的线性规划问题类似，把满足约

13、束条件式（33）的解称为可行解，把满足目标函数的可行解称为最优解，或者说使目标函数达到最大值的可行解叫最优解。对于标准形式的线性规问题，其约束条件式（33）为 在此约束条件中，前m个等式构成线性方程组，对此方程组，若m=n，且系数行列式不为零，则方程组有唯一组解，故不存在优化问题。若mn，一般来说mn，如果方程组的系数矩阵的秩为m，则该方程组有无穷多个解。假设前m个变量的系数列向量是线性独立的，构成的系数矩阵称为线性问题的一个基；称P1、P2、Pm为基向量，称与基向量对应的变量x1, x2，xm。为基变量，其它变量称为非基变量。若令非基变量等于零，则可求得一个解为这样的解称为基本解，它的非零变

14、量的个数不大于秩m。基本解不一定都是可行的（同时要满足非负性条件）。若基本解同时满足非负条件，就称为基本可行解，对应于基本可行解的基称为可行基。若基本可行解中的非零变量的个数小于m，即基变量出现零值时，则此基本可行解称为退化的基本可行解。当其非零变量的个数等于m，即基变量均为正值时，则此基本可行解称为非退化的基本可行解。显然，如果基矩阵B为m阶单位阵，则问题的一个基本可行解为线性规划问题的一个基本可行解，对应于可行域上的一个顶点。若线性规划问题有最优解，则必定在某个顶点处得到。虽然顶点数目是有限的，它不超过采用枚举法找出所有基本可行解，然后一比较，最终可以找到最优解。但当n、m相当大时，这种办

15、法是行不通的。所以下面要介绍一种更好的方法，即单纯形法。4 单纯形法单纯形法（Simplex Method）是美国学者丹茨基（GBDantzig）于 1947年提出的。这一方法从根本上解决了线性规划的求解问题。 单纯形法的基本思路是：根据问题的标准形式，从可行域中一个基本可行解（一个顶点）开始，转换到另一个基本可行解（顶点），并使目标函数的值逐步增大；当目标函数达到最大值时，就得到了问题的最优解。4.1 单纯形法引例 下面依据例 31，来引入单纯形算法。原线性规划问题的模型为第一步：将一般形式的线性规划问题标准化。在约束条件中引人松弛变量x3、x4、x5有 第二步：确定初始基本可行解。 为了确

16、定初始基本可行解，首先要找出初始可行基。由3可知，如果在约束方程的系数矩阵中能找到m个线性无关的单位向量，就能很容易地得到问题的一个初始基本可行解。若原问题的约束条件（不包括非负约束条件，下同）为一组“” 不等式，标准化后，可以松弛变量作为基变量，其余的变量为非基变量，令非基变量等于零，便可立即得到一个初始基本可行解。对于本例，x3、x4、x5为基变量，x1、x2为非基变量，则问题的一个初始基本可行解为X0（0 0 360 200 300）T，此时的目标函数值f7x1+12x20，意味着工厂没有进行生产，对应的利润为零。这正是我们生产规划的开始。 若原问题的约束条件为一组“”不等式或一组等式或

17、三种约束的混合，标准化后，如果约束方程的系数矩阵中不存在m个线性无关的单位向量，就要设法构成m个不同的单位列向量。有关这个问题将在后面进行讨论。 为明显起见，把基变量放在等式左边，非基变量放在等式右边，由式（36）得：相应的目标函数用非基变量表示为：从目标函数表达式可以看出：非基变量x1、x2的系数都是正数，因此增加x1或x2均可使目标函数f增加。所以只要在目标函数的表达式中还存在有正系数的非基变量，就表明目标函数还有增加的可能，就需要将非基变量与基变量进行对换。单纯形法的实质上就是进行基变量和非基变量的代换过程。新进入左边的变量叫换入变量，被代换到右边的变量叫换出变量。每完成一次代换，就是一

18、次选代，而对应的目标函数值就相应地有所增加，至少也与代换前相同。 第三步：确定换入换出变量，进行第一次选代。 在进行单纯形法迭代时，每次只能代换一个变量。一般选择正系数最大的那个非基变量为换入变量，并成为新的基变量，本例中x2为换入变量。同时，还要从原来的基变量中确定出一个为换出变量，成为新的非基变量。换出变量的确定要经过计算换入变量的最大步长。x2作为换入变量，由于受到有关资源的限制，是不能随意安排调整的。我们把资源允许的最大调整量叫最大步长。故当x1=0时，要保证x3、x4、x50，有 显然，为同时满足以上三个条件，x2的调整量只能是 x2=min90，40，30=30即x2=30是调整的

19、最大步长。因为x2的最大步长是由式（3-7）中的第3个约束方程求得的，即当x1=0，x2=30时，x50，因此x5就是换出变量，这样一来就得到了新的基变量x3、x4、x2。，新的非基变量为xl、x5，此时需要把式（3-7）中x2与x5的位置对换。由式（37）中的第3式得将上式代人式（3-7）中的第1，第2两式，消掉x2，有把目标函数中的基变量用非基变量代替，得到调整以后的目标函数为当非基变量xl=x50时，得到另一个基本可行解是目标函数值f=360。由此可见，调整x2后，目标函数值增加了360。 从目标函数的表达式可以看出，非变量x1的系数为正，说明调整x1将会使目标函数值继续增加，x1不是规

20、划问题的最优解。 第四步：确定新的换人换出变量，进行第二次迭代。由于非基变量x5在目标函数中的系数为-1.2，调整x5将使目标函数值减少，又因目标函数中只有x1的系数为正，于是便知x1是新的换人变量，而新的换出变量还要通过计算最大步长来确定。xl的最大步长为 x1min30.77，20，10020x1的最大步长是由式（38）中的第二个方程确定的，对应的基变量x4为新的换出变量，由式（3一8）中的第二式得将上式代人式（38）的第一、第三式，消掉x1，有调整后的目标函数为 当x4=x5=0时，可得到一个新的基本可行解为 X=(20 24 84 0 0）T，目标函数值得 f428。 因为调整后的目标

21、函数的表达式中非基变量的系数全部非正，所以X2为最优解。即当A产品生产20kg，B产品生产24kg，工厂才能获得最大利润428百元。x384代表煤的剩余量为 84t，x4x50表示电力和劳动日完全利用，没有剩余。42 单纯形表解法 上面的引例说明了用单纯形法解线性规划问题的基本思路和理论依据。但在实际求解中，用上述方法比较麻烦，而且容易出错，故多采用单纯形表解法，下面仍以上面的例子来说明表上求解的步骤和方法，并引出一般线性规划问题的解法。 第一步：标准化（见前解法第一步）。 第二步：找出初始基变量，并将目标函数中的基变量用非基变量代替。 l）检查约束方程的系数矩阵是否含有m阶单位阵。若没有，则

22、设法构造。m阶单位阵对应的变量为基变量，其余变量为非基变量。 上面的问题中3阶单位矩阵对应的变量x3、x4、x5为基变量，x1、x2为非基变量。 2）检查目标函数中是否含有基变量，如果有，则用非基变量加以代换。上面问题的目标函数中不含有基变量，故不需代换。 第三步：作初始单纯形表。 初始单纯形表就是把线性规划模型中的变量和相关的系数规则地排成一种表格，它和线性规划模型具有一对应的关系。 对于上面的问题，可将目标函数写成类似于约束方程的形式，即 f7xl12x20其初始单纯形表如表34所示。 初始单纯形表的最上一行存放全体变量，最左一列存放基变量，最右一列存放约束方程右边项，中间存放约束方程组中

23、对应变量的系数，最下一行存放目标函数中变量的系数。注意这里的目标函数中对应于基变量的系数必须为零，右下角存放目标函数中常数项的相反数。 初始单纯形表的最后一列代表一组初始可行解，每完成一次迭代，就有一个新的单纯形表。在单纯形表中，目标函数f所在的行叫判别数或检验数行，记为j，j1，2，n，因为在目标函数中不含基变量，所以基变量所对应的判别数为零，如表34中基变量x3、x4、x5对应的判别数为零。 在得到问题的一个基本可行解后，就需要判断它是否是最优解，为此下面介绍最优解的判别准则。 最优解判别准则：当所有判别数全部非正时，即j0，j1，2，n时，对应的基本可行解为最优解。 由此准则可知，经有限

24、次迭代后，若所有判别数全部非正，则得到了问题的最优解，否则应继续迭代。这个准则和前述引例中判断最优解的方法是一致的。由表34可知，问题的判别数中含有正的判别数，故初始基本可行解不一定是最优解。 第四步：确定主元。 在所有正判别数中，最大判别数所在的列叫主元列，主元列对应的变量即为换人变量，若则k所在的列为主元列，对应的变量xk为换人变量。若上式中的最大值多于一个时，即原则上可以在k、r、对应的变量中任选一个作为换人变量，但为了运算过程有规可循，我们规定，取下标k、r、中最小的判别数对应的变量为换人变量。当主元列确定后，就可按下式确定主元。若则alk所在的行叫主元行，对应的基变量为换出变量，主元

25、列与主元行的交叉元素alk。就是主元。当最小比值不唯一时，任取其中一行作为主元行。显然，主元所对应的非基变量为换人变量，主元所对应的基变量为换出变量。对于上例，由知，x2为换人变量。由知，换出变量为x5，主元为10，为清楚起见，主元用方框圈起来。 注意，若有一个判别数k0，并且对一切 il，2，m有aik0，那么该线性规划问题无解，即无有限值最优解。这就是无界解的判别准则。 第五步：开始迭代。 单纯形迭代实际上是对单纯形表作初等行变换。首先把换人变量放人基底，然后对主元行所有元素除以主元，化主元为1，接着对其它行（包括目标函数行）施行行变换，化主元列其它元素为零，至此第一次迭代结束。检查表中的

26、判别数是否全部非正，若是，则迭代终止，否则继续迭代。上面问题的第一次选代结果如表35所示。根据表35，可以写出第一次迭代后线性规划问题的约束方程为目标函数为 对以上两式稍作变换就得到了第一种解法的形式。可见单纯形表解法与前述引例方法是一致的。由上表可得到问题的一个基本可行解为X（0 30 240 50 0）T，相应的目标函数值为 f 360。因此，单纯形表的最右一列表示问题的一个基本可行解中基变量的值，右下角元素的相反数表示相应的目标函数值。因上表中的判别数不全非正，故需继续迭代。 第六步：进行第二次迭代。判别数中只有x1对应的判别数为正，故其为新的换人变量。由知2.5为主元，对应的基变量x4

27、为换出变量。其退出基底，x1进人基底，化主元为1，主元列其它元素为零，第二次迭代结束，结果如表36所示。 由表36可知，全部判别数非正，于是得到了问题的最优解为 X（20 24 84 0 0）T目标函数 f 428。可见单纯形表迭代结果与41中迭代结果完全相同。4.3 单纯形表的另两种常见形式 大多数线性规划问题标准化后，其约束方程组的系数矩阵中并不含有m阶单位阵。为了得到问题的一组初始基变量，通常采用的方法是在每一个约束方程中加人一个非负的虚拟变量，这种虚拟的变量称为人工变量。对于一个标准化的线性规划问题，其约束方程为在第i个约束方程中加人一个人工变量Xn+1，得到 如果以xn+l，xn+m

28、为基变量，x1，xn为非基变量，便可得到问题的一个初始基本可行解为X0（0 0 0 b1 b2 bm）T。因为人工变量是加人到原约束方程组中的虚拟变量，为了不改变原来问题的性质，就应将它们从基变量中逐渐替换掉，即使人工变量为零。处理人工变量的方法有两阶段法和大M法，下面我们分别介绍这两种方法。4.3.l 两阶段法 两阶段法是将加入人工变量后的线性规划问题分两阶段来求解。第一阶段是借助于以下辅助线性规划问题，为原问题求得一个基本可行解。 用单纯形法对上述问题求解，若得到W0，即所有的人工变量都为零，表示原问题已得到了一个基本可行解；若W0，即不是所有人工变量都为零，表示原问题无可行解，应停止计算

29、。 第二阶段是从第一阶段得到的基本可行解开始，继续用单纯形法进行迭代，直到找出原问题的最优解或判断无最优解。 以上介绍的方法是对每个约束方程中都加人人工变量。如果原问题约束方程的系数矩阵中存在有一些单位向量，为减少计算工作量，可以只在部分约束方程中加入人工变量。下面通过一个例子说明两阶段问题的求解步骤和方法。例36 用两阶段法求解下列线性规划问题。 解 第一步：标准化。在第一个约束条件中引入松弛变量x4，第二个约束条件中引人剩余变量x5，得到原问题的标准形式为第二步：确定初始基变量，并将目标函数中的基变量用非基变量代替。式（310）的约束方程中只有x4的系数向量为单位向量，为形成3阶单位矩阵，

30、在第二和第三个约束方程中分别引入人工变量x6和x7，得第一阶段的规划问题为x4，x6，x7为初始基变量，把目标函数w中的基变量用非基变量代替，有即 如果原问题的目标函数中也含有基变量时，也必须用非基变量代替。 第三步：作初始单纯形表。作初始单纯形表的基本要求与前面介绍的完全一样，唯一的区别是增加了第一阶段问题的目标函数W行，见表37。 第四步：确定主元。 第一阶段问题以W为目标函数，主元的确定方法与前面相同。 第五步：进行第一阶段迭代。 与前述方法相同，即换出变量退出基底，换人变量进人基底，化主元为1，主元列其它元素（包括f行的元素）为零，完成一次迭代。若行的判别数不全非正，则继续选代。 该问

31、题经过二次迭代后，w行的判别数全部非正，且有 max w0，故得到了原问题的一组基变量x4、x2、x3，至此第一阶段迭代结束。 第六步：进行第二阶段迭代。从第一阶段的最终单纯形表中去掉人工变量x6、x7所对应的列及w行，得到第二阶段的单纯形表，如表38所示。 经过一次迭代后，判别数全部非正，得到原问题的最优解为 X（4 1 9 0 0）T相应的目标函数值f2。4.3.2 大M法大M法的基本思路是对于标准形式的线性规划问题，引人人工变量后将其改造为其中 M为充分大的正数，记为M1，下面举例说明大M法的具体迭代过程。例37 求解下列线性规划问题。解 引人剩余变量和人工变量将上面的线性规划模型化为标

32、准形式如下根据模型式（313）建立初始单纯形表，如表39所示。因为M是充分大的数，所以判别数行的全部元素小于等于零，说明此表已达到最优，最优解为则 由此可见，凡约束条件为大于或等于型不等式时，均需引入人工变量，在目标函数中，人工变量前面均应乘上系数 M，M1，而且，在极大值问题中，M前面为负号。这样，可以确保在获得最优解时消去人工变量，如果人工变量不能通过迭代而消去，则说明该问题无最优解。 到此为止，对于任何形式的线性规划问题，总可以利用单纯形法、两阶段法或大M法对其求解。5 改进单纯形法 对于较简单的线性规划问题，可以用单纯形表法求解。但当线性规划问题的规模较大时，用单纯形表求解是非常困难的

33、，甚至是不可能的。为此就出现了一种新的算法改进单纯形法。这种方法从实质上来说是一种矩阵算法，主要是通过基矩阵求逆来实现单纯形迭代。同时，这种方法是用计算机求解线性规划问题的主要算法。对于标准形式的线性规划问题如果令则式（314）可用矩阵形式表示为如果用列向量Pj，j1，2，n代表矩阵A的第j列，则有设前m个列向量是线性独立的，则B（P1 P2 Pm）为线性规划问题的基矩阵。其余列向量构成的矩阵N（Pm+1 Pn）称为非基子矩阵。A（B N）。基矩阵B对应的变量为基变量，用XB表示，XB（xl x2 xm）T，非基子矩阵N对应的变量为非基变量，用 XN表示，XN=(xm+1 xn)T，则有 X（

34、XBXN）T。同样地，C可以表示为C=（CBCN），CB=（c1c2cm），CN=（cm+1cn）。于是式（3一15）可改写为 如果判别数，则为问题的最优可行解，相应的目标函数值，否则，应确定新的基矩阵B1继续迭代。 我们知道，单纯形迭代实际上是由一个基矩阵到另一个基矩阵的过程，而且每次迭代只能是一个变量换入，一个变量换出，即基阵中只有一个列向量发生变化。设 BO=（P1 P2. Pl Pm）为初始基矩阵。若对应的判别数行向量。不全非正，即基矩阵B0不是最优基，根据前述方法确定的换人变量为xk，换出变量xl，则以列向量Pk代换Pl得到新的基矩阵为。由前面的推导可知，如果求得了，那么就可以求出一

35、组新的基本可行解、相应的目标函数值和判别数等。由此可见，在改进单纯形法计算中，关键是每次迭代时基矩阵的逆阵B-1。下面讨论其求法。 与单纯形表解法类似，改进单纯形法通常也是用m个单位向量构成的单位阵作为初始基矩阵，即以列向量Pk代换Pl后，得到的新基矩阵为 因此，基矩阵求逆实际上就是计算形如上式这种矩阵的逆，根据线性代数的理论，不难求得 Bl的逆 Bl-1为改进单纯形法的计算步骤与单纯形法类似，下面通过一个具体实例加以说明。例38 用改进单纯形法求解下列线性规划问题。解 第一步：标准化。引人松弛变量x3，x4，x5，得第二步：确定初始可行解。由上式得取x3、x4、x5为初始基变量，初始基为则有

36、由此可得非基变量的列向量为初始基本可行解为相应的目标函数值为非基变量判别数为 以上结果可列成表311的形式。实际上表311是一种特殊形式的单纯形表，它是按表310的格式构造的。因N00，故 BO不是最优基。第三步：确定新基，进行第一次迭代。由max 1，2 12，xl为换入变量，P10为换入列向量。由可知，6为主元，x5为换出变量，新的基变量为x3，x4，x1，故得新基B1为此时有由此可得XB0=b因20，故B1不是最优基，以上结果可用表 312表示。第四步：确定新基，进行第二次迭代。20，故x2为换入变量，P21为换人列向量同样地，按照第二步的方法可知，x3为换出变量，P3l为换出列向量，新

37、的基变量为x2、x4、xl，所得到的新基为此时有由此可得因判别数N20，所以迭代终止，得到问题的最优解为X（114 94 0 l2 0）T相应的目标函数值f2314上述结果可用表313表示。从以上运算过程可以看出，作为手算来说，采用改进单纯形并不方便，而且很容易出错，但对于计算机而言，用改进单纯形法不仅可以节约内存，而且运算量较小，所以对求解大型的线性规划问题较为有利。6 对偶单纯形法6.1 线性规划的对偶问题 我们先看一个简单的例子，然后提出对偶问题。 例39 某厂在计划期内要安排生产A、B两种产品，这两种产品分别需要在甲、乙、丙三种不同的设备上加工，有关数据如表314所示。问应如何安排生产

38、计划才能使利润最大？解 如果设A、B两种产品生产的件数分别为xl、x2，则这个问题可以归结为求解下列线性规划问题（LP1）现在从另一个角度来考虑这个问题。假设该厂的决策者，决定不生产产品A、B而将生产设备的有效台时用于接受外加工来收取加工费。此时就要考虑给每台设备的台时如何定价。设y1、y2 、y3分别表示设备甲、乙、丙每台时的价格。在定价时必须考虑到，将生产一件产品A的各设备的台时用于外加工时，所得加工费不得低于生产一件产品A可得的利润，即否则该厂不会接受外加工，而宁愿自己生产产品A。同理有若把设备的所有台时都用于外加工，总的收人为因为在定价时，受市场调节的影响不能把价格任意提高，故其定价方

39、案只有使总收人g（即委托加工单位支出的总加工费用）尽可能低，才能得到其它单位的委托加工。因此该厂只能得到g的最小值，于是，这个问题可以用下列线性规划描述（LP2） 显然，当min g=max f时，工厂决策者认为这两种考虑具有相同的结果，都是最优方案。 比较LP1和LP2，可知它们之间有着密切的联系，两者包含有相同的数据，只是位置不同而已。如果称前者为原问题，则后者就叫前者的对偶问题，反过来也是如此，即两者互为对偶问题。更一般地，若原问题为则对偶问题为其中yi叫做对偶变量。若表示成矩阵形式，则有其中A是m×n矩阵，C是n维向量，b是m维列向量，X是n维列向量、为原问题的变量，Y是m维

40、行向量、为对偶问题的变量。上式称为对偶关系的对称形式（或叫对偶标准形式），一般情况下，原问题与对偶问题的变换关系可归纳为表315所列的对应关系。 若原规划问题的约束条件中含有约束，可在其两边同乘以-1，统一为约束。这里，右边项没有符号限制。根据表3一15，可以写出下列一对线性规划问题：式（325）称为对偶关系的非对称形式。例：求标准线性规划问题的对偶问题解：先将标准线性规划问题化为等价的LP问题其对偶问题为例310 写出下列线性规划问题的对偶问题。解 用1乘第二个约束条件的两端，把它变成约束，根据表315即可写出其对偶问题为 如果求这个问题的对偶，显然就得到了原问题的对偶问题。6.2 对偶问题

41、的基本性质 下面介绍对偶问题的几条重要性质，以揭示原问题的解与对偶问题的解之间的一些重要关系，并为后面讨论对偶单纯形法奠定基础。 1）若X和Y分别是原问题和对偶问题的任一可行解，则必有 CXYb，即 fg 2）若X*和Y*分别为原问题和对偶问题的可行解，且可行解对应的原问题和对偶问题的目标函数值相等，即CX*Y*b，则X*、Y*分别为原问题和对偶问题的最优解。 3）若原问题和对偶问题之一的最优解无界，则另一个无可行解；若其中之一无可行解，则另一个的最优解无界或无可行解。也就是说，原问题和对偶问题之一无最优解，则另一个也无最优解。 4）若原问题和对偶问题之一有最优解，则另一个也有最优解，且两者的

42、最优目标函数值相等。 5）若原问题的最优解为 XBB-1b，则对偶问题的最优解为 YCBB-1。 6）根据原问题最优单纯形表中的判别数可以读出对偶问题的最优解。 对于第6个性质下面作一说明。设原问题和对偶问题为式（324），在原问题的约束条件中分别引人松弛变量Xs和剩余变量Ys，其中Xs为m维列向量，Ys为n维列向量，有设B为原问题的一个最优基，则原问题可改写为相应的对偶问题为这里Ys（Ys1 Ys2），Ys1是对应于原问题中基变量XB的剩余变量，Ys2是对应于原问题中非基变量XN的剩余变量。原问题的最优解为XBB-1b，相应的基变量XB的判别数为0，非基变量XN的判别数为CNCBB-1N，松

43、弛变量Xs的判别数为 CBB-1，把对偶问题的最优解 YCBB-1代人上式得 由此可见，原问题的最优单纯形表中的判别数对应于对偶问题的最优解的负值。它们的关系如表316所示。同样地若原问题和对偶问题为武（325）所示的非对称形式，则可得到表317所示的结果。 根据表3-17可知，原问题最优表中的判别数对应于对偶问题最优解中剩余变量的负值，而对偶决策变量的值YCBB-1看起来还不能直接从表317中读出。当然，如果知道了B-1和CB就可以直接计算出Y来，但下面讨论如何从表317中直接读出对偶变量的值。假定在原问题的约束条件的系数矩阵中有一个m阶单位阵，以此为初始可行基进行迭代得到最优基 B，则在最

44、优表316中，原来为单位阵的地方就变成了B-1，而在初始表中和B-1相对应的基矩阵B正好位于和最优表316中的单位阵相对应的位置，若用CI表示和初始表中单位阵相对应变量的价值系数向量，则在最优表 316中 B-1下的判别数将是CICBB-1。因而若由最优表316中B-1下的判别数减去相应的价值系数，则正好得到其对偶问题最优解的负值，即：YCBB1 ，特别地，当初始表中的单位阵是由引人松弛变量后而形成的，则有CI0。在这种情况下，最优表316中B1下面的判别数就正好等于其对偶问题的最优解的负值。下面以例39加以说明。设式（320）为原问题式（321）为对偶问题，在原问题的约束条件中引人松弛变量x

45、3、x4、x5，按单纯形法得原问题的初始表和最优表分别为表318和表3一19。 由表319知，原问题的最优解为X（35 10 25 0 0）T，最优目标函数值为max f 215在表318中，松弛变量x3，x4，x5的系数矩阵构成单位阵，故在最优表319中对应的系数矩阵为最优基的逆阵且对应的判别数等于它在对偶问题式（321）中的最优解的负值。即：Y（y1 y2 y3）（0 1 3），相应的目标函数值为min gmax f 215。另一方面，Y也可按式YCBB1计算，由于最优表中的单位阵对应于基变量x3、x1、x2，所以它们在初始表318中的系数列向量构成最优基B，故CB（c3 c1 c2）（0

46、 5 4），则有相应的目标函数值为为了验证按上述方法确定的对偶问题的最优解的正确性，按单纯形法对对偶问题式（321）进行迭代，得对偶问题的最优表如表320所列。表中y6，y7为人工变量，g'g。 由表320可知，对偶问题式（3-21）的最优解和最优目标函数值与上述方法求得的完全相同。由此可见，从表320的判别数中也可以直接读出原问题的最优解，这一点给我们一个重要的启示，即在求解线性规划问题时，可在原问题和对偶问题中挑选容易求解的进行求解计算，只要求出它的最优解，另一个的最优解也就很容易地得到。一般来说，线性规划求解的工作量在很大程度上取决于约束条件数目的多少，约束条件多，基矩阵的阶数高

47、，计算量大。因此，对于约束条件多，变量少的规划问题，其对偶规划的约束条件少，变量多，若对对偶规划求解，就可减少计算工作量。6.3 对偶问题的经济意义影子价格我们仍以例39为依据，其原问题和对偶问题的模型分别为通过求解，原问题和对偶问题的最优解分别为为了分析对偶问题的经济意义，我们对原规划及其对偶问题的求解进行图示分析，见图32。在图32中，增画了三条直线（用虚线描述），分别是这三条直线分别代表三种资源（各台设备可利用的台时数）各增加1个单位后的边界线。若资源b1，b2保持不变，仅使b345增加 1个单位，则最优点变为H'（34，12），此时就是说，原模型总利润的增量刚好等于对偶模型的变

48、量y3的最优解。而变量y3是对应于原模型的第3个约束条件即资源b3的。所以，y3的取值反映了资源b3的单位增量所带来的利润的增加量。换言之，y33反映了资源b3的一种单位价格，称为“影子价格”。由此可见，某一约束条件的影子价格表示为当它所对应的约束条件右端的常数增加一个单位时（假设原问题的最优基不变），原问题目标函数最优值增加的数值。如果花费某种代价（3）去获得b3，即当b3这种资源的市场价格低于影子价格时，企业就应买进这种资源。但这样做是有限度的，因为由图32可知，直线x1x245或xlx246如果过分右移是没有意义的。如果资源b190，b345保持不变，仅使 b280增加一个单位，则最优点

49、变为 H"（36，9），此时就是说，资源b2的影子价格为y21，其余讨论同上。 如果资源b280，b345，保持不变，仅使b190增加一个单位，则最优点仍为H（35，10），fmax215，其增量fmax0y1。就是说，资源b1的影子价格为y10，这说明用设备的台时数没有充分利用，还有剩余，当其用于外加工时，只有收取加工费，且不管为多少，对该厂来说都是有利的。但是这种对外加工是有限度的，否则，直线x13x290下移过多将影响最优解。 例311 一个大学教授用部分时间从事于咨询工作。通过这项工作，他的总收人将有所提高，该教授掌握了咨询补偿的基本规律：“一个专家的价值正比于厂商和专家之间

50、的距离”。也就是说，要求咨询的单位愈远，他得到的报酬愈多。遗憾的是，旅行时间也将增加。目前他有较多的咨询机会，但可用时间有限，他希望详细分析这种情况，他是否要雇助手？如果这样，他应付多少工资？ 解 设：x1每月为A企业咨询的小时数（利润：10元h） x2每月为B企业咨询的小时数（利润：12元h） x3每月为C企业咨询的小时数（利润：16元h）进一步假定该教授每月有40h用于咨询工作，并且希望他的旅行时间每月在24h以内。每小时咨询工作所要求的旅行时间对于企业A、B、C来说分别为0.1h、0.2h、0.2h。教授估计三个企业每月要求最大的咨询时间分别是80h、60h、20h。据此，我们可以很快建

51、立该问题的线性规划模型。式中 f从事咨询工作每月可得的利润总和（元月）。对偶问题的模型为式中 g各种资源全部利用后的收益总和；y1资源 1的单位贡献（咨询时间的价值）；y2资源2的单位贡献（旅行时间的价值）；y3资源3的单位贡献（为A咨询的价值）；y4资源4的单位贡献（为B咨询的价值）；y5资源5的单位贡献（为C咨询的价值）。用单纯形法求解该问题，得到原问题和对偶问题的最优解为注意到：每月增加教授咨询时间lh，每月可多得酬金12元。这就确定了为助手提供的支付金，雇请薪金每月小于12元的助手将增加教授的月收人。 此外，还看到公司C的咨询价值，超过每月20h后，是每小时4元。由于假定只能给它每月2

52、0h，就不能利用这个结果。所以教授应该为助手支付每小时小于12元的工资。助手每工作lh，教授每月额外收人（12元助手小时工资）。显然，这个结果存在上限；否则，附加酬金没有限制。在灵敏度分析中将对如何确定这种限制进行详细的分析。6.4 对偶单纯形法 在用单纯形进行迭代时，在bi列中得到问题的基本可行解，而在判别数行得到的是对偶问题的非可行解。这是因为在达到最优解之前，判别数即 YAC，显然 YCBB-1不满足对偶问题的约束条件 YAC。通过逐步迭代，当判别数行得到的对偶问题的解也是可行解时，即 CYA0或 YAC时，CBXBYb，由性质2知，此时原问题和对偶问题同时达到了最优解。 根据对偶问题的

53、对称性，也可以这样来考虑：若保持对偶问题的解是可行解，即CYA0，而原问题在非可行解的基础上，即B-1b中至少有一个负分量，通过迭代逐步达到基本可行解，这样也得到了原问题和对偶问题的最优解。因为这种方法是从对偶问题的可行性出发来求解原问题的最优解，故把它称做对偶单纯形法。这种方法的优点是原问题的初始解不一定是基本可行解，即可以从非可行解开始迭代。下面通过一个例题来介绍对偶单纯形法的计算步骤。 例312 用对偶单纯形法求解下列线性规划问题解 第一步：标准化。引人剩余变量x3，x4，x5，并令f'f， 则有 显然，如果要用单纯形法求解，则需引人三个人工变量，再用两阶段法或大M法进行求解，若用下面介绍的对偶单纯形法就简单多了。 第二步：找初始基变量，并将目标函数中的基变量用非基变量代替。为了找出基变量，先在约束方程的系数矩阵中形成m阶单位阵，为此用1乘式（327）约束方程两端，得 显然，x3，