第3 章对偶理论与灵敏度分析 本章内容要点 .线性规划的对偶问题的概念、理论及经济意义; .线性规划的对偶单纯形法; .线性规划的灵敏度分析。 本章核心概念 .对偶问题(dualproblem); .对偶定义(dualdefinition); .对偶定理(dualtheorems); .影子价格(shadowprice); .对偶单纯形法(dualsimplexmethod); .灵敏度分析(sensitivityanalysis)。 ■ 案例 某工厂生产A1、A2、A33种产品,这些产品都要在甲、乙、丙、丁4种设备上加工,根据 设备性能和以往的生产情况知道单位产品的加工工时、各种设备的最大加工工时限制以及 每种产品的单位利润如表3-1所示。假设工厂考虑不安排生产,而准备将所有设备出租,应 该如何合理地确定各种设备的租金? 表3- 1 案例中设备加工工时以及每种产品的利润 产品 最大加工工时限制 A1 A2 A3 工时/小时 设备甲2 1 3 70 设备乙4 2 2 80 设备丙3 0 1 15 设备丁2 2 0 50 单位利润/千元8 10 2 — 3.线性规划的对偶问题 1 线性规划有一个有趣的特性,就是对于任何一个求极大的线性规划问题都存在一个与 其匹配的求极小的线性规划问题,并且这一对线性规划问题的解之间还存在着密切的关系。 线性规划的这个特性称为对偶性。这不仅仅是数学上具有的理论问题,也是实际问题内在 ·59· 的经济联系在线性规划中的必然反映。 本节将从经济意义上研究线性规划的对偶问题,通过对对偶问题的研究,从不同的角度 对线性规划问题进行分析,从而利用有限的数据,得出更广泛的结果,间接地获得更多有用 的信息,为企业经营决策提供更多的科学依据。另外,还将利用对偶性质给出求解线性规划 的新方法———对偶单纯形法。 3.1.1 对偶问题的提出 例3.1 某工厂用A1,A2,…,Am 种资源生产B1,B2,…,Bn 种产品。现有资源数、单 位产品所需原料消耗及单位产品利润如表3-2所示。如何组织生产才能使利润最大? 表3-2 对偶问题的表述 单位产品原料消耗 B1 B2 … Bn 现有资源 资源 A1 a11 a12 … a1n b1 A2 a21 a22 … a2n b2 . . . . . . Am am1 am2 … amn bm 单位产品利润c1 c2 … cn 解 若用xj 表示产品Bj(j=1,2,…,n)的生产数量,那么这一问题的线性规划模型为 maxS =c1x1 +c2x2 + … +cnxn a11x1 +a12x2 + … +a1nxn ≤b1 a21x1 +a22x2 + … +a2nxn ≤b2 . am1x1 +am2x2 + … +amnxn ≤bm xj ≥0, j=1,2,…,n ì . í .... ... . (3-1) 现在从另一角度来讨论这一问题。假设该厂的决策者决定不生产产品B1,B2,…,Bn , 而将其所有资源A1,A2,…,Am 出租给其他单位,其原则是使别的单位愿意租赁,又使本厂 仍能得到生产原来这些产品时可以得到的最大收益。为此,工厂的决策者必须给每种资源 订出一个合理的价格,使在这种价格条件下,实现出租的目的。 设y1,y2,…,ym 分别表示出租资源A1,A2,…,Am 的单位价格,则原来生产单位产品 B1 所用的资源,按现在的单价计算,其收益为 a11y1 +a21y2 + … +am1ym 为了使工厂的收益不减少,就要求在制定价格y1,y2,…,ym 时,使这个收益不低于原来生 产单位产品B1 所得到的收益,因此,应有 a11y1 +a21y2 + … +am1ym ≥c1 同理,对产品B2,…,Bn ,也可以列出类似的约束条件,即 ·60· a12y1 +a22y2 + … +am2ym ≥c2 . a1ny1 +a2ny2 + … +amnym ≥cn 如果工厂的资源全部出租,其收入为 W =b1y1 +b2y2 + … +bmym 为了达到出租目的,本厂只能在满足大于或等于所有产品利润前提下,使其总收入尽可能的 小。因此,工厂要解决的问题就是如下的线性规划问题: minW =b1y1 +b2y2 + … +bmym a11y1 +a21y2 + … +am1ym ≥c1 a12y1 +a22y2 + … +am2ym ≥c2 . a1ny1 +a2ny2 + … +amnym ≥cn yi ≥0, i=1,2,…,m ì . í .... .... (3-2) 称式(3-1)和式(3-2)互为对偶的线性规划问题,即有时也称式(3-1)为原始问题,式(3-2) 为对偶问题。 对比式(3-1)和式(3-2),可以看到两者之间有下列关系: (1)对原始问题是求目标函数的最大值,对对偶问题是求目标函数的最小值; (2)原始问题中约束条件的个数等于对偶问题中变量的个数; (3)原始问题的收益系数成为对偶问题约束不等式右端的常数项; (4)原始问题中约束方程组每一行的系数成为对偶问题中约束方程组每一列的系数; (5)原始问题的约束条件都是“≤”,对偶问题的约束条件都是“≥”; (6)原始问题与其对偶问题可以互相转化。 这些关系如表3-3所示。 表3-3 对称式对偶关系表 变 量x1 x2 … xn 原 关 系minW y1 a11 a12 … a1n ≤ b1 y2 a21 a22 … a2n ≤ b2 . . . . . . . ym am1 am2 … amn ≤ bm 对偶关系≥ ≥ … ≥ maxS c1 c2 … cn 在这个表中,从正面看是原始问题,将它转90°后看,就是对偶问题。 3.1.2 对偶规划的形式 互为对偶的线性规划问题还可用矩阵符号表示,即原始问题为求 ·61· maxS =CX AX ≤b X ≥0 { 相应的对偶问题为求 minW =Yb YA ≥C Y ≥0 { 其中,A 是原始问题的系数矩阵(m ×n), b 是原始问题的右端常数列向量(m ×1), C 是原始问题的目标函数行向量(1×n), X 是原始问题的决策变量列向量(n×1), Y 是对偶问题的决策变量行向量(1×m )。 例3.2 写出下述线性规划的对偶问题 maxS =5x1 +8x2 3x1 +x2 ≤18 x1 -x2 ≤5 x2 ≤3 x1,x2 ≥0 ì . í ... ... 解 按照原始问题和对偶问题的相应关系,可写出对偶问题如下: minW =18y1 +5y2 +3y3 3y1 +y2 ≥5 y1 -y2 +y3 ≥8 y1,y2,y3 ≥0 ì . í .. .. 以上所介绍的原始问题与对偶问题之间的变换关系为对称形式,但是线性规划问题有 时不以对称形式出现,例如在约束条件中既有“≥”,也有“≤”和“=”,在变量中既有非负要 求也有无符号限制等。遇到这种非对称形式时,应如何从原始问题推导出它的对偶问题? 通过具体例子予以说明。 例3.3 写出下述线性规划的对偶问题 maxS =3x1 +2x2 +x3 x1 +x2 +x3 =12 (1) x1 -x2 +x3 ≤10 (2) 2x1 +x2 +x3 ≥14 (3) x1,x2 ≥0,x3 符号不限 ì . í ... ... 解 将上述非对称形式化为对称形式:先将约束方程(1)分解成两个与它等价的不等 式,即 x1 +x2 +x3 ≤12 x1 +x2 +x3 ≥12 ·62· 将后面一个乘以-1,化为 -x1 -x2 -x3 ≤-12 因约束方程(2)符合对称形式,保留不变。 把约束方程(3)改写成 -2x1 -x2 -x3 ≤-14 对符号不限的变量x3 以两个非负变量x4 与x5 之差代替,即x3=x4-x5。这样,原始问 题化为如下的对称形式: maxS =3x1 +2x2 +x4 -x5 x1 +x2 +x4 -x5 ≤12 -x1 -x2 -x4 +x5 ≤-12 x1 -x2 +x4 -x5 ≤10 -2x1 -x2 -x4 +x5 ≤-14 x1,x2,x4,x5 ≥0 ì . í .... ... . 设y'1 ,y″1 ,y'2 和y'3 为其对偶问题的变量,则对偶问题为 minW =12y'1 -12y″1 +10y'2 -14y'3 y'1 -y″1 +y'2 -2y'3 ≥3 y'1 -y″1 -y'2 -y'3 ≥2 y'1 -y″1 +y'2 -y'3 ≥1 -y'1 +y″1 -y'2 +y'3 ≥-1 y'1 ,y″1 ,y'2 ,y'3 ≥0 ì . í .... ... . 这样的对偶问题尚无法与原始问题对照,为使其与原始问题对应,需将目前的对偶问题进行 一些转换,即设y1=y'1 -y″1 ,y2=y'2 ,y3=-y'3 ,并将最后两式合并,得原始问题的对偶问 题为 minW =12y1 +10y2 +14y3 y1 +y2 +2y3 ≥3 y1 -y2 +y3 ≥2 y1 +y2 +y3 =1 y1 无符号限制,y2 ≥0,y3 ≤0 ì . í ... ... 关于非对称形式的原始问题与对偶问题的关系,一般地,如表3-4所示。 表3-4 一般对偶关系表 原始问题(或对偶问题) 对偶问题(或原始问题) 目标函数maxS 系数矩阵为A 目标函数系数为C 常数列向量为b 目标函数minW 系数矩阵为AT 常数列向量为CT 目标函数系数为bT ·63· 续表 原始问题(或对偶问题) 对偶问题(或原始问题) 约束条件 m 个 小于或等于(≤)型(第i 个) 等于(=)型(第i 个) 大于或等于(≥)型(第i 个) ì . í .. .. 变量xj n 个 ≥0 ≤0 无符号限制 ì . í .. .. 对偶变量 m 个 yi≥0 yi 无符号限制 yi≤0 ì . í .. .. 约束条件 n 个 大于或等于(≥)型(第j 个) 小于或等于(≤)型(第j 个) 等于(=)型(第j 个) ì . í .. .. 例3.4 写出下述线性规划的对偶问题 minS =x1 +3x2 -2x3 x1 +2x2 +3x3 ≥5 2x1 -x2 ≤2 x1 +x2 -2x3 =4 x1 ≤0,x2 ≥0,x3 无符号限制 ì . í ... ... 解 按照原始问题与对偶问题的相应关系,其对偶问题为 maxW =5y1+2y2+4y3 y1-2y2+y3≥1 2y1-y2+y3≤3 3y1-2y3=-2 y1≥0,y2≤0,y3 无符号限制 ì . í ... ... 3.1.3 对偶问题的基本理论 在下面的讨论中,假定线性规划的原始问题与对偶问题分别求 minS =CX, 与 maxW =Yb AX ≥b X ≥0 { YA ≤C Y ≥0 { 定理3.1 若X(0)与Y(0)分别为原始问题和对偶问题的任一可行解,则必有CX(0)≥ Y(0)b。 证 因为X(0)与Y(0)都是可行解,所以有AX(0)≥b,Y(0)A≤C。 对上述两式分别左乘Y(0)和右乘X(0)得 Y(0)AX(0) ≥Y(0)b, Y(0)AX(0) ≤CX(0) 因此 CX(0) ≥Y(0)AX(0) ≥Y(0)b 即 CX(0) ≥Y(0)b 这个定理说明,求最小值的原始问题任一可行解的目标函数值,总是不小于求最大值的对偶 ·64· 问题任一可行解的目标函数值。 从定理3.1可直接推得下述结论。 推论1 求最小值问题(原始问题)的任意一个可行解所对应的目标函数值是对偶问题 目标函数最优值的一个上界。 推论2 求最大值问题(对偶问题)的任意一个可行解所对应的目标函数值是原始问题 目标函数最优值的一个下界。 推论3 若原始问题可行,而目标函数无界(即minS→-∞),则对偶问题无可行解。 定理3.2 若X* 与Y* 分别为原始问题和对偶问题的可行解,且有CX* =Y*b,则X* 和Y* 分别是原始问题和对偶问题的最优解。 证 设X 为原始问题的任一可行解,则由定理3.1,得 CX ≥Y*b 已知 CX* =Y*b 所以 CX ≥CX* 按定义X* 为原始问题的最优解,同理可证Y* 为对偶问题的最优解。 定理3.3 (对偶定理)在互为对偶的线性规划问题中,如果其中一个有最优解,则另一 个也有最优解,且它们的最优值相等。 证 假设互为对偶问题的原始问题为标准形式,即求 minS =CX AX =b X ≥0 { 那么其对偶问题为 maxW =Yb YA ≤C Y 无符号限制{ 设X* 为原始问题的最优解,它对应的最优基为B,则相应基变量XB* =B-1b,最优值为 minS =CX* =CBB-1b 检验数为 CBB-1A -C ≤0 令 Y* =CBB-1 则 Y*A ≤C 这说明Y* 满足对偶问题的约束条件,所以Y* 是其一个可行解。将Y* 代入对偶问题的目标 函数,得 W =CBB-1b 故 ·65· CX* =Y*b 依定理3.2,Y* 是对偶问题的最优解。 同样可以证明,若对偶问题有一最优解,那么相对应的原始问题也有最优解。 推论1 在互为对偶的线性规划问题中,若原始问题的最优基为B,则对偶问题的最优 解为Y* =CBB-1。 推论2 设X* 为原始问题的一个可行解,相应的可行基为B,而Y* =CBB-1为其对偶 问题的可行解,则X* 和Y* 分别为它们的最优解。 实际上,因为Y* 为对偶问题的可行解,所以Y*A≤C,即CBB-1A-C≤0。又因为X* 为原始问题的可行解,所以X* 为其最优解,B 为最优基,从而Y* 为最优解。 定理3.4 若原始问题的最优解存在,则用单纯形法求解时,其对偶问题的最优解可同 时在最优单纯形表上得到,且顺次等于松弛变量或剩余变量对应的检验数的相反数。 证 把原始问题改写为标准形式 minS =CX AX -Xm =b X ≥0,Xm ≥0 { 设B 为其最优基,且A=(B,N),X= XB XN é . êê ù . úú ,C=(CB ,CN ) 则有 S =CBXB +CNXN BXB +NXN -Xm =b 因为B 可逆,所以 XB =B-1b -B-1NXN +B-1Xm 代入目标函数,得 S =CBB-1b - (CBB-1N -CN )XN +CBB-1Xm 即 S + (CBB-1N -CN )XN -CBB-1Xm =CBB-1b 于是有如表3-5所示的最优单纯形。 表3-5 定理3.4证明 XB XN Xm S CBB-1b 0 CBB-1N -CN -CBB-1 XB B-1b 1 B-1N -B-1 显然,对偶问题的最优解Y* =CBB-1恰为剩余变量Xm 对应的检验数的相反数。 定理3.5(互补松弛性) 若X* 与Y* 分别为原始问题和对偶问题的可行解,且Xs 和Ys 分别为它们的松弛变量,则Y*Xs =0 和YsX* =0,当且仅当X* 和Y* 分别为它们的最 优解。证 因为Xs 和Ys 分别为它们的松弛变量,所以 AX* -Xs =b, Xs ≥0 ·66· Y* A +Ys=C,Ys ≥ 0 前者左乘Y*,后者右乘X*,得 Y*AX*-Y*Xs=Y* b Y*AX*+YsX*=CX* 两式相减,得 YsX*+Y*Xs=CX*-Y* b 若Y*Xs=0且YsX*=0,则有 根据定理3.2,X*和Y*分别为最优解。 CX* =Y* b 若X*和Y*分别为最优解,则CX*=Y*b,于是 YsX* +Y*Xs= 0 又因为Ys、X*、Y*和Xs 大于或等于0,故有 YsX* =0,Y*Xs= 0 从互补松弛条件YsX* 0,0可看到以下关系: =Y*Xs= (1)若X*中某一变量xj *>0,则必有松弛变量yj =0。这意味着,若有原始变量为正, 则相应的对偶约束在最优情况下为等式。 (2)若Xs 中某一松弛变量xi >0,则相应的yi *=0。这意味着,若原始约束在最优情 况下是严格不等式,则相应的对偶变量在最优情况下为0。 完全类似地,可描述其他松弛条件的含义。 1.影子价格 3.4 在经济问题中,求原始规划maxS=CX,AX≤b,X≥0的最优解,就是求在有限资源条 件下的最佳配置及最佳效益,那么此时相应的对偶规划minW =Yb 、YA≥C、Y≥0及变量 Y 的经济意义该如何解释呢? 它对企业的经营管理能否提供一些有价值的信息? 下面来进一 步讨论这个问题。 设 B 是原始问题的最优基,X*和Y*分别为原始问题和对偶问题的最优解,S*和 W * 分别为它们的最优值,则有 S* = W * =CBB-1b=Y*b= Σ(m) yi*bi = 式中,i 它代表第i种资源可(i) 利用的数量, 可 b是原规划问题的右端常数项, 以(1) 而对偶变量yi 解释为每一个单位第 i 种资源对企业经营效益所做的贡献,或者说单位第 i 种资源在原生 产安排的机会中所创造的“价值”。像这种针对原生产安排中的各单位资源所创造的“价值” 称为某种资源的“影子价格”。值得指出的是,这种价格yi * 不是资源的市场价格,而是对资 源在生产中所做的贡献的估价。 影子价格是一种边际价格,实际上在 S* =CBB-1b=Y* b 中,对S*求 b 的偏导数,得 ·67· .S* .b =CBB-1 =Y* 即 .S* .bi =yi* 这说明在给定的生产条件下,bi 每增加一个单位,目标函数值的增量是影子价格yi* 。 下面用具体例子对影子价格进行进一步分析。 例3.5 某厂用甲、乙、丙3种原料生产A 、B 两种产品。根据单位产品的产值和3种原 料的限量,建立了如下线性规划模型: maxS =6x1 +5x2 (产值) 2x1 +6x2 ≤120 (原料甲) 4x1 +3x2 ≤32 (原料乙) x1 +x2 ≤10 (原料丙) x1,x2 ≥0 ì . í ... ... 利用单纯形法求解,得最终单纯形表如表3-6所示。 表3-6 例3.5最终单纯形表 S -52 0 0 0 -1 -2 x3 68 0 0 1 4 -18 x1 2 1 0 0 1 -3 x2 8 0 1 0 -1 4 显然,最优生产方案为产品A 生产2个,产品B 生产8个,最大产值可以达到52。 对应于松弛变量x3、x4、x5 的检验数的相反数为相应对偶问题的最优解,即 y1* =0, y2* =1, y3* =2 这些数值就分别是原料甲、乙、丙的影子价格。 原料甲的影子价格y1* =0,说明在一定范围内增加或减少这种原料,不改变企业的总 产值。在这种情况下可以断定,在业已安排的生产计划中,原料甲还有剩余。事实上,在最 优解为x1=2,x2=8时,原料甲的用量为 2x1 +6x2 =2×2+6×8=52(单位) 该原料尚剩余120-52=68(单位)。 原料乙和丙的影子价格分别为1和2,说明在现计划安排下,这两种原料都已用尽,并 且适当增加这两种原料供应,工厂的总收入还会增加。例如,原料丙增加一个单位,总收入 将增加2个单位。 总之,对于供大于求的原料,其影子价格为0,对于稀缺紧俏的原料,其影子价格往往较 大。影子价格不仅可以说明不同资源对总的经济效益会产生不同的影响,而且在市场经济 条件下它对企业的经营管理还能提供一些有价值的信息。 (1)影子价格告诉企业的经营管理者增加哪种资源,对提高效益有利。例如在上例中, 当原料丙的市场价格低于它的影子价格2时,厂家可以购进这种原料进行生产。否则,厂家 ·68· 买进这种原料就不合算。 (2)影子价格可以告诉企业的经营管理者新的产品是否有利于投产。例如,在前面例 子中,厂长打算生产一种新产品,已知单位产品耗用的3种原料分别是(2,3,2),而单位产品 的售价是8,该产品在本厂是否可以生产? 从经营的角度讲,生产该项单位产品所创造的收入(即售价)应大于该产品所消耗3种 原料的影子价格之和。由于 8> (0,1,2) 232 é . êêêê ù . úúúú =7 所以该项产品可考虑投产。如果该项产品的售价低于7,则不利投产。 (3)当市场价格变动时,可从单纯形表中直接求出各资源的新的影子价格,从而看出各 单位资源所创造的新的“价值”。例如,上例中产品A ,B 的售价由(6,5)变为(6,6),则新的 影子价格为 Y* =CBB-1 =(0,6,6) 1 4 -18 0 1 -3 0 -1 4 é . êêêê ù . úúúú =(0,0,6) 这说明原料丙显得更为重要。 以上的影子价格分析在最优生产方案中才能体现出来,即是在最优基B 不变的情况下 进行的,它的进一步分析和应用,将在3.3节讨论。 思 考 题 (1)是否每一个线性规划问题都能找到对应的有意义的对偶问题? (2)对于已求解的线性规划问题,其影子价格是否需要重新计算? 影子价格的具体 数据在哪里得到? 3.2 对偶单纯形法 对偶单纯形法并不是求解对偶问题的单纯形法,而是用对偶原理求解原线性规划问题 最优解的一种方法,习惯上叫对偶单纯形法。 3.2.1 对偶单纯形法的基本思想 3.1节讲了对偶性定理,下面可以重新审视单纯形表计算的实质,根据对偶性定理的内 容,在最优单纯形表中,b'列对应了原规划的最优解,而检验数行的后m 个分量的相反数则 对应了对偶规划的最优解,当用单纯形法的准则进行迭代计算时,b'列的值保持非负,对应 原规划的一个基本可行解,而检验数行则有些检验数为正,对应了对偶规划的一个不可行的 基本解,单纯形法迭代计算的过程就是在保持原规划的解可行的基础上,使对偶规划的解逐 ·69· 步由不可行变为可行,最后当检验数全部非正时,原规划和对偶规划同时达到最优解。而原 规划和对偶规划是相互的,同样的,也应该可以在保持对偶规划的基本解可行的基础上,通 过逐步迭代求得原规划的最优解。这就是对偶单纯形法的基本思想。 对偶单纯形法的基本思想是,从原规划的一个基本解出发,此基本解不一定可行,但它 对应着一个对偶可行解(检验数非正),所以也可以说是从一个对偶可行解出发;然后检验原 规划的基本解是否可行,即是否有负的分量,如果有小于0的分量,则进行迭代,求另一个基 本解,此基本解对应着另一个对偶可行解(检验数非正)。如果得到的基本解的分量皆非负, 则该基本解为最优解。也就是说,对偶单纯形法在迭代过程中始终保持对偶解的可行性(即 检验数非正),使原规划的基本解由不可行逐步变为可行,当同时得到对偶规划与原规划的 可行解时,便得到原规划的最优解。 3.2.2 对偶单纯形法主要步骤 在单纯形法迭代过程中,始终要求B-1b≥0,这是为了保证解的可行性,B-1b≥0称为 原始问题基本解的可行性条件,在其被满足的前提下,若CBB-1A-C≤0不满足(实际上, 这是对偶问题的可行性条件),可逐步换基迭代,直至得到所有检验数非正,从而得到原规划 问题的最优解。 由于对偶问题的对称性,当对偶问题的可行性条件CBB-1A -C≤0满足,而原规划问 题的可行性条件不满足,即B-1b 中有负数时,也可以在保证CBB-1A-C≤0的条件下换基 迭代,逐步改善原规划问题的可行性,直至得到B-1b≥0,从而得到原规划问题的最优解,这 便是对偶单纯形法的基本思路。对偶单纯形法的方法步骤如下。 (1)将原始问题化为下列标准型,以便得到对偶问题的可行基。 minS =CX AX =b, b 列元素可以为负值 X ≥0 { 建立初始单纯形表,当全部检验数CBB-1A-C≤0且B-1b≥0时,得最优解,计算终止。 (2)若在B-1b 中有bi0<0,而其中某负数所对应的行向量元素全部非负,则原规划问 题无可行解,否则转下一步。 (3)如果bi0<0,用bi0所对应的行向量中的全部负元素bij,去除检验数中与其对应的 元素,按照最小比值法则,确定轴心项,即若 θ=min b0j bij (bij { <0)}= b0r bir 则bir为轴心项,这时,xi 为离基变量,xr 为入基变量。 (4)换基迭代,使轴心项所在的列为单位向量,从而得到对应于新基的单纯形表。 (5)如果在新单纯形表中,所有bi0≥0,得最优解,求解终止。若其中仍有负数,转入步 骤(2),直至求得所有bi0≥0为止。 例3.6 用对偶单纯形法求解 minS =x1 +2x2 +3x3 ·70· x1 -x2 +x3 ≥4 x1 +x2 +2x3 ≤8 x2 -x3 ≥2 x1,x2,x3 ≥0 ì . í ... ... 解 引入松弛变量化为如下标准型: minS =x1 +2x2 +3x3 +0x4 +0x5 +0x6 -x1 +x2 -x3 +x4 =-4 x1 +x2 +2x3 +x5 =8 -x2 +x3 +x6 =-2 x1,x2,…,x6 ≥0 ì . í ... ... 得出单纯形表,即表3-7。 表3-7 例3.6初始单纯形表 S 0 -1 -2 -3 0 0 0 x4 -4 -1 1 -1 1 0 0 x5 8 1 1 2 0 1 0 x6 -2 0 -1 1 0 0 1 由于基本解不可行,需要求轴心项,进行换基迭代。因为θ=min -1 -1,-3 { -1}=1,所以, b11=-1为轴心项,换基迭代得到表3-8。 表3-8 例3.6求解过程 S 4 0 -3 -2 -1 0 0 x1 4 1 -1 1 -1 0 0 x5 4 0 2 1 1 1 0 x6 -2 0 -1 1 0 0 1 其基本解仍不可行,继续换基迭代,得到表3-9。 表3-9 例3.6最终单纯形表 S 10 0 0 -5 -1 0 -3 x1 6 1 0 0 -1 0 -1 x5 0 0 0 3 1 1 -2 x2 2 0 1 -1 0 0 -1 原问题的最优解已达到,即x1=6,x2=2,x3=0,其最优值S=10。 从以上求解过程可以看到,用对偶单纯形法求解线性规划问题时,初始解可以是非可行 解,只要检验数全部非正,就可换基迭代而不必引入人工变量,使计算简化,但是在单纯形表 中一开始就做到使对偶问题是一个基本可行解也不容易。在后面将要介绍的整数规划和灵 敏度分析中,有时需要用对偶单纯形法,它可使问题的处理得到简化。 ·71· 3.2.3 对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题: minS =Σn j=1 cjxj, cj ≥0 Σn j=1 aijxj ≥bi,i=1,2,…,m xj ≥0, j=1,2,…,n ì . í .. .. 在引入松弛变量化为标准型之后,约束等式两侧同乘-1,能够立即得到检验数全部非正的 原规划基本解,可以直接建立初始对偶单纯形表进行求解,非常方便。 对于有些线性规划模型,如果在开始求解时,不能很快使所有检验数非正,最好还是采 用单纯形法求解,因为这样可以免去为使检验数全部非正而做的许多工作。从这个意义上 看,对偶单纯形法是单纯形法的一个补充。除此之外,在对线性规划进行灵敏度分析时,有 时也要用到对偶单纯形方法来简化计算。 思 考 题 (1)总结对偶单纯形法与单纯形法的区别。 (2)对偶单纯形法适于求解线性规划问题的特征是什么? 3.3 灵敏度分析 线性规划的灵敏度分析又称优化后分析,它是对已求得最优解的线性规划问题进行分 析,了解客观环境变化对最优解的影响。假设线性规划问题已求得最优解,然而由于种种原 因,其系数A、b、C 发生了变化,那么当这些系数中的一个或几个发生变化时,问题的最优解 会有什么变化或者这些系数在一个什么范围内变化时,问题的最优解不变,这就是灵敏度分 析所要研究和解决的问题。 灵敏度分析是以一个最优基B 和最优解XB =B-1b 作为分析的基础,并利用互为对偶 问题的性质进行检验,用简便的方法求得系数变化后的最优解。下面举例说明。 例3.7 某工厂用甲、乙两种原料生产A 、B、C3种产品,每千件产品的原料消耗(吨/千 件)和利润(万元/千件)及原料总量(吨)如表3-10所示。试制订一个生产方案,在现有条件 下获利最大。 解 设x1、x2、x3 分别为3种产品的产量,那么上述问题的数学模型为 maxS =3x1 +4x2 +10x3 x1 +2x2 +3x3 ≤20 3x1 +4x2 +12x3 ≤75 x1,x2,x3 ≥0 ì . í .. .. ·72· 表3-10 例3.7基本数据 产 品 A B C 原料总量 千件产品的 原料消耗/吨 甲1 2 3 20 乙3 4 12 75 单位利润/万元3 4 10 利用单纯形法可求得最优基B=(P1,P3)的单纯形表如表3-11所示。 表3-11 例3.7最终单纯形表 S' -65 0 -43 0 -2 -13 x1 5 1 4 0 4 -1 x3 5 0 -23 1 -1 13 显然,最优方案是产品A 和C 各生产5千件,产品B 不生产,最大利润为65万元。 这里 B =(P1,P3)= 1 3 3 12 é . êê ù . úú , B-1 = 4 -1 -1 13 é . êêê ù . úúú CB =(-3,-10) B-1A = 1 4 0 4 -1 0 -23 1 -1 13 é . êêê ù . úúú C =(-3,-4,-10,0,0) 现就下面几种情况进行灵敏度分析。 3.3.1 目标函数系数的变化 首先讨论非基变量的目标函数系数的变化范围。 在上述例子中,假设产品B 的利润受市场影响有波动,即目标函数中x2 的系数有变 化,令c2=4+Δc2(Δc2 可正可负)。如果要使上面所得到的解仍为最优解,那么c2 应限制 在什么范围之内? 根据最优判别准则,应有CBB-1A-C≤0。事实上,只要保证x2 在最终 单纯形表中的检验数小于或等于0即可。即 CBB-1P2 - (-c2)≤0 即 (-3,-10) 4 -1 -1 13 é . êêê ù . úúú 24 é . êê ù . úú + (4+Δc2)=-43 +Δc2 ≤0 ·73· 即 Δc2 ≤43 也就是当c2=4+Δc2≤513 时,所得最优解和最大利润都不变。 注意:在原最优生产方案中,产品B 之所以没有安排生产,是由于其单位产品的利润相 对较低,但是,当其利润有所增大,即每千件利润大于513 万元,经营管理者就要对原生产方 案进行调整。例如,如果Δc2=73 ,即c2=613 ,这时,安排产品B 和C 进行生产,总利润还 可以增大。 其次,讨论基变量的目标函数系数的变化范围。 假设c1=3有变化,令c1=3+Δc1。因为-c1 是CB 的分量,所以当c1 变化Δc1 时,就 引起CB 的变化,从而影响非基变量检验数的改变。事实上,若要使原问题的最优解不变, 就要保证检验数CBB-1A-C≤0,即 CBB-1A -C =(- (3+Δc1),-10) 1 4 0 4 -1 0 -23 1 -1 13 é . êêê ù . úúú - (- (3+Δc1),-4,-10,0,0)≤0 即 0,- 43 -4Δc1,0,-2-4Δc1,- 13 +Δc1 . è . . . ÷ ≤0 从而有 -43 -4Δc1 ≤0 -2-4Δc1 ≤0 -13 +Δc1 ≤0 ì . í ... ... 解得 -13 ≤ Δc1 ≤13 即有 223 ≤c1 ≤313 这表明,当c1 在223≤c1≤313 之间变动时,其最优解仍为x1=x3=5,x2=0,但其最优值 随Δc1 变化而变化。 注意:当基变量的目标函数系数变化时,其最优解不变的范围,一般来说有一个上限和 一个下限。从经济意义上讲,这一点是显然的,因为x1 是基变量,所以在最优方案中要安 排生产产品A 。当其单位产品利润降到一定程度时,就应减少其产量或不生产,而单位利 ·74· 润增大到一定程度时,就要增加其产量。在这种情况下,原生产方案都要进行调整。 3.3.2 右端常数的变化 下面仍以上例来讨论这种类型的灵敏度分析。 假设b1=20有变化,令b1=20+Δb1,那么b1 变化能有多大的幅度,仍能保持原最优基 不变? 因为b 的改变与判别准则CBB-1A-C≤0无关,因此依对偶原理,要保持原最优基 不变,只要保证XB =B-1b 为可行解,即B-1b≥0即可。据此,求b1 的变化范围。 因为 B-1 = 4 -1 -1 13 é . êêê ù . úúú , b = 20+Δb1 75 é . êê ù . úú 所以 B-1b = 4 -1 -1 13 é . êêê ù . úúú 20+Δb1 75 é . êê ù . úú = 5+4Δb1 5-Δb1 é . êê ù . úú ≥0 即有5+4Δb1≥0, 5-Δb1≥0, { 解得-54 ≤Δb1≤5。 即当1834 ≤b1≤25时,原最优基仍为最优基。 同样,假设原料乙有变化,即b2=75+Δb2,按上述解法可得70≤b2≤80,即原料乙的用 量在70~80范围内变化时,原最优基不变。 注意,虽然常数项b 在一定范围内变化可使最优基不变,但是最优解的值会发生变化。 例如,令b=b+Δb,可使最优基不变,但它使最终表中原问题的解相应地变为 X'B=B-1(b +Δb) 3.3.3 增加新产品引起的变化分析 仍沿用上例,设该厂打算引进新产品D 。已知生产D 产品1000件消耗原料甲2吨,原 料乙6吨,可获利8万元。问该厂是否生产该产品和生产多少? 分析步骤如下: ① 设生产产品D 为x'4 件,其消耗系数为P'4 =(2,6)T,它在最终表中的检验数为 CBB-1P'4-c'4 =(-3,-10) 4 -1 -1 13 é . êêê ù . úúú 26 é . êê ù . úú - (-8) =-6+8=2≥0 这说明生产产品D 对该厂有利。 ② 计算产品D 在最终表中的列向量 B-1P'4 = 4 -1 -1 13 é . êêê ù . úúú 26 é . êê ù . úú =20 é . êê ù . úú ·75· 将①和②填入最终单纯形表中,如表3-12 所示。 表3-12 单纯形表 x1 x2 x3 x4 x5 x'4 S' -65 0 -4 3 0 -2 -1 3 2 x1 x3 5 5 1 0 4 -2 3 0 1 4 -1 -1 1 3 2 0 将x4作为入基变量,换基迭代,求出最优解,如表313 所示。 ③ ' 表3-13 最终单纯形表 x1 x2 x3 x4 x5 x'4 S' -80 -1 -4 -2 -4 0 0 x'4 x5 10 50 1 2 0 1 -2 3 2 3 1 2 -3 0 1 1 0 这时得最优解为x1=x2=x3=0,x' 10,x5=50, 其他产品都不生 产,可获利80 万元。 4=即仅生产产品D, 3.增加一个约束条件 3.4 假设该厂原生产过程用煤不限,但为了节约能源,今后用煤有了限制,设生产A、B、 C 3 种产品各1000 件,分别需用煤为4吨、6吨、10 吨,总限量为70 吨,那么是否需要改变原来 的最优方案? 一个新的约束条件是否影响最优解,可以利用最优解直接代入,如果最优解满足新增加 的约束条件,则约束条件等于没增加,新的约束无效。如果最优解不满足新增加的约束条 件,则约束是有效的。 该问题用煤的约束条件为 4x1+6x2+10x3≤70 将最优解x1=x3=5,x2=0代入上式,则左端等于右端,满足约束条件,原最优解不变。 如果把用煤总量限制为64 吨,即 4x1+6x2+10x3≤64 显然,该约束条件有效,对其引进松弛变量x6,使上式变为 4x1+6x2+10x3+x6=64 在原最优单纯形表中增加一行一列,并把松弛变量x6 指定为新行的基变量,即有 表3-14 。 因为x1 和x3 为基变量,所以必须对行进行初等变换,使P1 和P3 中的元素4和10 变 为0,即有表3-15 。 ·76· 表3-14 增加约束后的单纯形表 S' x1 x3 x6 -65 5 5 64 0 1 0 4 -4 3 4 -2 3 6 0 0 1 10 -2 4 -1 0 -1 3 -1 1 3 0 0 0 0 1 表3-15 求解过程 S' x1 x3 x6 -65 5 5 -6 0 1 0 0 -4 3 4 -2 3 -10 3 0 0 1 0 -2 4 -1 -6 -1 3 -1 1 3 2 3 0 0 0 1 用对偶单纯形法,求其最优解,得到表3-16 。 表3-16 求解结果 S' x1 x3 x4 -63 1 6 1 0 1 0 0 -2 9 16 9 -1 9 5 9 0 0 1 0 0 0 0 1 -5 9 -5 9 2 9 -1 9 -1 3 2 3 -1 6 -1 6 这说明,增加新的约束条件后的最优方案是产品 A 生产1000 件,产品 C 生产6000 件, 可得总利润63 万元(比原方案减少2万元)。 思考题 (1)为何要进行灵敏度分析? (2)灵敏度分析包括哪些类别,每一类别分别有什么现实意义? 本章小结 线性规划有一个有趣的特性,就是对于任何一个求极大的线性规划问题都存在一个与 其匹配的求极小的线性规划问题,并且这一对线性规划问题的解之间还存在着密切的关系。 线性规划的这个特性称为对偶性。这不仅仅是数学上具有的理论问题,也是实际问题内在 的经济联系在线性规划中的必然反映。 本章首先引入了线性规划的对偶问题,分析了线性规划问题及对偶问题的特征及在形 式上相互转换的规则。线性规划与其对偶问题有深刻的内在联系,对偶性定理说明了它们 ·77· 的关系。影子价格是对偶问题中引入的重要概念,影子价格有两种经济含义,并在现实经济 生活中得到应用。对偶单纯形法是把单纯形法思想和对偶思想结合的方法,其求解步骤与 单纯形法有一定的对应关系,对偶单纯形法有明确的适用范围,是单纯形法的重要补充。线 性规划模型中的各个系数在现实生活中可能发生变化,因此需要分析当这些系数发生变化 时对原问题解的最优性和可行性的影响,灵敏度分析主要包括5个类别,每个类别都有明确 的现实经济意义。 习 题 3 3.1 写出下列问题的对偶问题。 (1)maxS=-5x1+2x2 (2)minS=6x1+3x2 -x1+x2≤-3 2x1+3x2≤5 x1,x2≥0 ì . í .. .. 6x1-3x2+x3≥2 3x1+4x2+x3≥5 x1,x2,x3≥0 ì . í .. .. (3)maxS=5x1+6x2 (4)maxS=x1+x2 x1+2x2=5 -x1+5x2≥3 x1 无限制,x2≥0 ì . í .. .. 2x1+x2=5 3x1-x2=6 x1,x2 无符号限制 ì . í .. .. 3.2 对偶单纯形法求解下列线性规划问题。 (1)minS=x1+x2 (2)minS=4x1+12x2+18x3 2x1+x2≥4 x1+7x2≥7 x1,x2≥0 ì . í .. .. x1+3x3≥3 2x2+2x3≥5 x1,x2,x3≥0 ì . í .. .. (3)minS=3x1+2x2+x3 (4)minS=5x1+2x2+4x3 x1+x2+x3≤6 x1-x3≥4 x2-x3≥3 x1,x2,x3≥0 ì . í ... ... 3x1+x2+2x3≥4 6x1+3x2+5x3≥10 x1,x2,x3≥0 ì . í .. .. 3.3 已知线性规划问题: maxS =x1 +2x2 +3x3 +4x4 x1 +2x2 +2x3 +3x4 ≤20 2x1 +x2 +3x3 +2x4 ≤20 x1,x2,x3,x4 ≥0 ì . í .. .. 其对偶问题的最优解为y1=1.2,y2=0.2,根据对偶理论求原问题最优解。 3.4 考虑有界变量的线性规划问题: ·78·