第3章 对偶理论及灵敏度分析

1、第 3 3 章线性规划的对偶理论及灵敏度分析 BY 蔡连侨蔡连侨北京外国语大学国际商学院北京外国语大学国际商学院北京外国语大学国际商学院蔡连侨3-2如果企业考虑把设备等资源出租，应该如何定租金，才能保证出租是合算的增加资金投入，应该如何进行合理分配在目前的生产计划情况下，如果产品价格发生变化，对生产计划是否有影响，采用新工艺对生产计划又有什么影响为了增加产量，需要再购买原材料，多高的价格是可以接受的（即采购后可增加产量，也能增加利润）采购原材料后对生产计划有什么影响北京外国语大学国际商学院蔡连侨3-3线性规划的对偶问题(Dual Problem)线性规划的对偶单纯形法(Dual Simplex

2、 Method)线性规划的灵敏度分析(Sensitivity Analysis)参数线性规划(Parametric Linear Programming)北京外国语大学国际商学院蔡连侨3-4对偶问题的提出对偶问题的形式对偶问题的基本性质影子价格北京外国语大学国际商学院蔡连侨3-5 例1（同第2章例1）：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 问题：工厂应如何安排生产可获得最大的总利润？产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500

3、北京外国语大学国际商学院蔡连侨3-6 可以建立如下的线性规划模型： 目标函数 Max z =1500 x1+2500 x2 约束条件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1, x2 0 化为标准型，利用单纯形法进行求解，得到最优解X=(5, 25, 0, 5, 0)T，最优值（利润）为70000。北京外国语大学国际商学院蔡连侨3-7最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示B设备有5个机时的剩余）， 最优值 z* = 70000 北京外国语大学国际商学院蔡连侨3-8 现在从另一个角度来讨论该问题：如果工厂考虑不安排生产，而准备把所

4、有设备出租（或用于外协加工），工厂收取租金（或加工费）。试问：设备 A、B、C 每工时各如何收费（租金或加工费）才最有竞争力？ 工厂为了获得最大利润，在为设备定价时，应保证生产某产品的设备工时所收取的费用不低于生产该产品的利润；同时，为了提高竞争力，应该使定价尽可能低北京外国语大学国际商学院蔡连侨3-9 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的收费。可以建立以下线性规划模型： Min f = 65 y1 + 40 y2 + 75 y3 s.t. 3 y1 + 2 y2 1500 （不少于甲产品的利润） 2 y1 + y2 + 3 y3 2500 （不少于乙产品的利润） y1,

5、 y2 , y3 0化为标准型，利用单纯形法进行求解，得到最优解Y=(500, 0, 500, 0, 0)T，最优值（收费）为70000。北京外国语大学国际商学院蔡连侨3-10最优解 y1 = 500 y3 = 500， 最优值 f* = 70000 北京外国语大学国际商学院蔡连侨3-11 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 65 2 x1 + x2 40 原问题原问题 3 x2 75 x1 , x2 0 Min f = 65 y1 + 40 y2 + 75 y3 s.t. 3 y1 + 2 y2 1500 2 y1 + y2 + 3 y3 2

6、500 对偶问题对偶问题 y1, y2 , y3 0北京外国语大学国际商学院蔡连侨3-12可以看到，这两个问题关系密切，用同样的原始数据目标函数MaxMin约束条件系数矩阵AAT资源常数bc目标系数cb 2个变量2个约束 3个约束3个变量 解检验数 检验数解北京外国语大学国际商学院蔡连侨3-13线性规划有一个有趣的特性，就是对于任何一个求极大的线性规划问题都存在一个与其匹配的求极小的线性规划问题，并且这一对线性规划问题的解之间还存在着密切的关系。线性规划的这个特性称为对偶性对这两个线性规划问题，一般称前者为原问题，后者是前者的对偶问题北京外国语大学国际商学院蔡连侨3-14对偶问题的提出对偶问题

7、的形式对偶问题的基本性质影子价格北京外国语大学国际商学院蔡连侨3-15如果线性规划问题的变量均具有非负约束，其约束条件当目标函数求极大时均取“”，当目标函数求极小时均取“”，则称具有对称形式对称形式下原问题和对偶问题的形式 (LP) Max z = CX (DP) Min f = YTb s.t. AX b s.t. ATY CT X 0 Y 0 “Max - ” “Min- ”北京外国语大学国际商学院蔡连侨3-16一对对称形式的对偶规划之间具有下面的对应关系若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“m

8、in，”相对应从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量从数据b、C的位置看：在两个规划模型中，b和C的位置对换两个规划模型中的变量皆非负北京外国语大学国际商学院蔡连侨3-17把对称形式的对偶规划之间的对应关系表示在表中Max zMin fx1x2xnxi 0y1a11a12a1nb1y2a21a22a2nb2ymam1am2amnbmyi 0c1c2cn北京外国语大学国际商学院蔡连侨3-18对偶问题的对偶即是原问题(DP) Min f = YTb s.t. ATY CT Y 0 (LP) Max f = -YTb s

9、.t. - ATY - CT Y 0 (DP) Min z = - CX s.t. - AX - b X 0 (LP) Max z = CX s.t. AX b X 0 北京外国语大学国际商学院蔡连侨3-19一般称不具有对称形式的一对线性规划为非对称形式的对偶规划对于非对称形式的规划，可以按照下面的对应关系进行处理并给出其对偶规划将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面的方法处理若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式也可以直接给出其对偶规

10、划北京外国语大学国际商学院蔡连侨3-20例2：写出下面线性规划的对偶规划模型 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1 + 3 x2 5 x3 2 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 没有非负限制北京外国语大学国际商学院蔡连侨3-21解：先化为对称形式（Max）“”的约束两端同乘以“1”“=”的约束等价转换为“”和“”的两个约束，再变换变量0，用变量替换，如 x2 = x2 变量无非负限制，用变量替换，如 x3 = x3 x3” Max z = x1 4 x2 + 3 x3 3 x3” s.t. 2 x1 3

11、 x2 5 x3 + 5 x3” 2 3 x1 x2 6 x3 + 6 x3” 1 x1 x2 + x3 x3” 4 x1 + x2 x3 + x3” 4 x1，x2，x3 ，x3” 0北京外国语大学国际商学院蔡连侨3-22写出对偶问题 Min f = 2 y1 y2 + 4 y3 4 y3” s.t. 2 y1 3 y2 + y3 y3” 1 3 y1 y2 y3 + y3” 4 5 y1 6 y2 + y3 y3” 3 5 y1 + 6 y2 y3 + y3” 3 y1，y2，y3 ，y3” 0北京外国语大学国际商学院蔡连侨3-23变量替换，令y2 = y2 ，y3 = y3 y3” Mi

12、n f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1 3 y1 y2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3 无非负限制北京外国语大学国际商学院蔡连侨3-24把对偶问题和原问题进行比较 Max z = x1 + 4 x2 + 3 x3 s.t. 2 x1 + 3 x2 5 x3 2原问题 3 x1 x2 + 6 x3 1 x1 + x2 + x3 = 4 x1 0，x2 0，x3 没有非负限制 Min f = 2 y1 + y2 + 4 y3 s.t. 2 y1 + 3 y2 + y3 1对偶问题 3 y1 y

13、2 + y3 4 5 y1 + 6 y2 + y3 = 3 y1 0 ，y2 0，y3无非负限制北京外国语大学国际商学院蔡连侨3-25 由此得到非对称形式的线性规划原问题和对偶问题的对应关系（对称形式也适用）原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件右端项目标函数中的系数C目标函数中的系数约束条件右端项目标函数Max z = cj xjMin f = bi yi变量n个 xj 0(0，无限制)约束条件n个aij yj(，=)cj约束条件m个aij xj(，=)bi变量m个 yi0(0，无限制)北京外国语大学国际商学院蔡连侨3-26例3：写出下面线性规划的对偶问题 Max z =

14、x1 x2 + 5 x3 7 x4 s.t. x1 + 3 x2 2 x3 + x4 = 25原问题 2 x1 7 x3 + 2 x4 60 2 x1 + 2 x2 4 x3 30 5 x4 10 ，x1，x2 0 ，x3 没有非负限制 Min f = 25 y1 60 y2 + 30 y3 5 y4 + 10 y5 s.t. y1 + 2 y2 + 2 y3 1对偶问题 3 y1 + 2 y3 1 2 y1 7 y2 4 y3 = 5 y1 + 2 y2 + y4 + y5 = 7 y1无非负限制， y2， y4 0 ， y3， y5 0 北京外国语大学国际商学院蔡连侨3-27例：写出下面运

15、输问题的对偶问题njmixnjdxmisxtsxcwMinijjmiijinjijminjijij, 2 , 1;, 2 , 10, 2 , 1, 2 , 1. .1111北京外国语大学国际商学院蔡连侨3-28对偶问题的提出对偶问题的形式对偶问题的基本性质影子价格北京外国语大学国际商学院蔡连侨3-29对偶问题的基本性质对对称形式和非对称形式都是同样适用的，但为了方便，在说明或证明时以对称形式为例（非对称形式可以化为对称形式）对称形式下原(Primal)问题和对偶(Dual)问题如下 (P) Max z = CX (D) Min f = YTb s.t. AX b s.t. ATY CT X 0

16、 Y 0 “Max - ” “Min- ”北京外国语大学国际商学院蔡连侨3-30（弱对偶定理）若X，Y分别为（P) 和（D）的可行解，那么CX YTb。证明：由变量的非负性限制，可以得到miiinjjjybxc11 minjijijnjjmiiijnjjjyxaxyaxc11111)( minjijijmiinjjijmiiiyxayxayb11111)(北京外国语大学国际商学院蔡连侨3-31弱对偶定理的推论（P）任一可行解的目标函数值是其对偶问题目标函数值的下界；（D）任一可行解的目标函数值是其原问题目标函数值的上界若（P）可行，那么（P）无有限最优解的充分必要条件是（D）无可行解若（D）可

17、行，那么（D）无有限最优解的充分必要条件是（P）无可行解若（P）、 （D）可行，那么（P）、 （D）都有最优解（P）有最优解的充分必要条件是（D）有最优解北京外国语大学国际商学院蔡连侨3-32（最优性准则定理）若X，Y分别为(P)，(D)的可行解，且CTX=YTb，则X，Y分别为(P)和(D)的最优解证明：设 X 为(P)的可行解，由弱对偶定理可得 CTX YTb = CTX 因此 X 为(P) 的最优解设 Y 为(D)的可行解，由弱对偶定理可得 YTb CTX = YTb 因此 Y 为(D) 的最优解北京外国语大学国际商学院蔡连侨3-33（主对偶定理）若(P)和(D)均可行，那么(P)和(D

18、)均有最优解，且最优值相等。证明：若(P)和(D)均可行，则由弱对偶定理的推论知 (P)和(D)均有最优解 设(P)的最优基为B，令YT= CBB-1，由=C - CBB-1A 0，对于松弛变量部分，目标函数系数为0，系数矩阵为单位阵，检验数为= - CBB-10，故Y0，且YTAC，ATY CT，因此 Y 为(D)的可行解 目标YTb = CBB-1b = CX（原问题最优值），由最优性准则定理知 Y 为 (D) 的最优解注：(P) 松弛变量的检验数的绝对值是(D)的基可行解北京外国语大学国际商学院蔡连侨3-34对称形式下原问题和对偶问题的标准形式如下 （互补松弛定理）若X 和Y 分别是 (

19、P)和(D)的最优解（对称形式的标准型下），则有 即约束取等式或对应的变量为0), 2 , 1(0), 1(11mnjxmibxxaxczMaxjiinnjjijnjjj), 2 , 1( 0), 1(11mniynjcyyaybfMinijjmmiiijmiii), 1;, 1( 0, 0njmixyyxinijmj北京外国语大学国际商学院蔡连侨3-35证明：由弱对偶定理（CXYTb）得 由主对偶定理可知最优值相等，上述不等式取“=”， miiiminjijijnjjjybyxaxc1111 miiinmiinjjijiminjijijmiiiyxyxabyxayb111111)(00, 0

20、,yxyxiinij得由 njjjmnjjjmiiijnjjjminjijijxyxcyaxcyxa111111)(00, 0,yxyxjmjij得由北京外国语大学国际商学院蔡连侨3-36对偶问题基本性质的应用利用单纯形法，求得对偶问题最优解 X=(1, 0, 0, 2, 0)T，最优值 z* = 9。由互补松弛定理，得 x1 y3 = 0， x2 y4 = 0，x3 y5 = 0，x4 y1 = 0， x5 y2 =0，因此有 y1 = 0，y3 = 0，代入第1个约束得到y2 = 9，代入其余约束得 y4 = 4， y5 = 64对于变量数量少、约束多的问题，可以利用基本性质简化求解例4：

21、 Min f = 5 y1 + y2 s.t. 3 y1 + y2 9 y1 + y2 5 y1 + 8 y2 8 y1，y2 0 Max z = 9 x1 + 5 x2 + 8 x3 s.t. 3 x1 + x2 + x3 5 x1 + x2 + 8 x3 1 x1， x2， x3 0 北京外国语大学国际商学院蔡连侨3-37对偶问题的提出对偶问题的形式对偶问题的基本性质影子价格北京外国语大学国际商学院蔡连侨3-38影子价格 (Shadow Price) 的概念若X*，Y* 分别为（P）和（D）的最优解，则 z = CX* = Y*Tb = f根据 z = b1y1*+b2y2*+bmym*

22、可知 z / bi = yi* 其中bi表示第 i 种资源的拥有量， yi*表示 bi 变化1个单位对目标 z 产生的影响，也是在资源最优利用条件下对该资源的估价，称为该资源的影子价格例如，在例1中 yi* 是对设备租金的估价注意：注意：若 B 是最优基， y*T = CBB-1北京外国语大学国际商学院蔡连侨3-39影子价格的经济含义及应用资源的市场价格是已知的，且相对比较稳定，而影子价格有赖于资源的利用情况，是未知数，随着企业生产任务、产品结构等情况的变化而发生变化影子价格是一种边际价格，说明在资源得到最优利用的条件下，增加单位资源量可以增加的收益影子价格是对现有资源实现最大效益时的一种估价

23、，实际上是一种机会成本。企业可以根据现有资源的影子价格，考虑经营策略：如果影子价格高于市场价格，可考虑买进设备，以扩大生产能力，否则不宜买进；若某设备的租费高于影子价格，可考虑出租该设备，否则不宜出租北京外国语大学国际商学院蔡连侨3-40由互补松弛定理，可知如果某种资源未得到充分利用时（松弛变量不为0），则其影子价格为0（对应变量为0）；当资源的影子价格不为0，表明该资源在生产中已耗费完毕从影子价格的含义上来考察检验数j = cj - aij yi，其中 cj 表示产品的价值，aij yi是生产该产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。当产品的价值大于隐含成本时，表明生产该产品

24、有利；否则就不安排生产。这就是检验数的经济含义影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手，以较少的局部努力，获得较大的整体效益北京外国语大学国际商学院蔡连侨3-41一般来说，对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价。这种估价涉及到资源的最有效利用，如在一个大公司内部，可借助资源的影子价格确定内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏需要指出的是，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格

25、说明增加单位资源量可以增加的收益，是指资源在一定范围内增加时的情况，当某种资源的增加超过了一定的范围，总利润的增加量就不是按照影子价格给出的数值线性地增加。这将在灵敏度分析中讨论北京外国语大学国际商学院蔡连侨3-42 影子价格的应用举例例5：某外贸公司准备购进两种产品A1，A2。购进产品A1每件需要10元，占用5平方米的空间，卖出1件可获纯利润3元；购进产品A2每件需要15元，占用3平方米的空间，卖出1件可获纯利润4元。公司现有资金1400元，有430平方米的仓库空间存放产品。根据这些条件可以建立求最大利润的线性规划模型： Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15

26、 x2 1400 5 x1 + 3 x2 430 x1, x2 0 北京外国语大学国际商学院蔡连侨3-43求解后得到最优单纯形表如下所示 ：因此，最优方案是分别购进两种产品50件和60件，公司的最大利润为390元。同时，从表中也可以看到，资金的影子价格为11/45，即增加1元用于购买产品，可以多获利润11/45元；仓库的影子价格为1/9，即增加1平方米的仓库空间，可以多获利润1/9元CBXBbx1x2x3x44x260011/9-2/93x15010-1/151/3-z-39000-11/45-1/9北京外国语大学国际商学院蔡连侨3-44假设公司现在另有一笔资金585元，准备用于投资。当然，这

27、笔资金用于购买产品或者增加仓库空间都可以使公司获得更多的利润。问题是应该如何合理安排投资，使公司能够获得更多的利润。已知增加1平方米的仓库空间需要0.8元，因此如果资金用于增加仓库空间，每投资0.8元可以多获利1/9元，即每增加1元投资可多获利5/36=0.14元；而每增加1元用于购买产品，可以多获利11/45=0.24元。因此应该把资金用于购买产品，这样可以获得更多的利润将这585元也用于购买产品，可以增加利润 585y1=58511/45=143元北京外国语大学国际商学院蔡连侨3-45这可通过对改变条件的新模型的求解结果得到验证。新模型为 Max z = 3 x1 + 4 x2 s.t.

28、10 x1 + 15 x2 1985 5 x1 + 3 x2 430 x1, x2 0 得到最优解X =(11, 125)T，总利润为533元，增加533-390=143元如果采用其他方案，利润增加量肯定小于143元。如585元中510元用于购买产品，75元用于增加仓库空间(75/0.8=93.75)。则有 Max z = 3 x1 + 4 x2 s.t. 10 x1 + 15 x2 1910 5 x1 + 3 x2 523.75 x1, x2 0 得最优解X =(47.25, 95.83)T，总利润为525.08元，只增135.08元北京外国语大学国际商学院蔡连侨3-46线性规划的对偶问题线

29、性规划的对偶单纯形法线性规划的灵敏度分析参数线性规划北京外国语大学国际商学院蔡连侨3-47单纯形法的思路对原问题的一个基本可行解，判别是否所有检验数满足最优条件。若是，即找到了问题最优解；否则，再找出相邻的目标函数值更大的基本可行解，并继续判别，直到找到最优解或判别出无最优解为止也就是说，单纯形法在求解过程中保持原问题的可行性，寻找对偶问题的可行解根据对偶问题的基本性质，当对于某个基而言，原问题的基本解是可行的，对偶问题的解也是可行的，则由两者的目标函数值相等，因此此解为最优解。是否可以保持对偶问题的可行性，然后寻找原问题的可行解，这就是对偶单纯形法的思路北京外国语大学国际商学院蔡连侨3-48

30、对偶单纯形法的基本思想从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解北京外国语大学国际商学院蔡连侨3-49对偶单纯形法求解线性规划问题过程：建立初始对偶单纯形表，对

31、应一个基本解，所有检验数均非正，转下一步若b0，则得到最优解，停止；否则，若有bk0则选k行的基变量为出基变量，转下一步若所有akj0( j = 1,2,n)，则原问题无可行解，停止；否则，若有akj0 则选 =minj / akj | akj0=r/akr，那么 xr为进基变量，转下一步以akr为转轴元，作矩阵行变换使其变为1，该列其他元变为0，转回第二步北京外国语大学国际商学院蔡连侨3-50例6：求解线性规划问题：求解线性规划问题：标准化：标准化： Max z = - 2 x1 3 x2 - 4 x3 s.t. - x1 - 2 x2 - x3 + x4 = -3 -2 x1 + x2 -

32、 3 x3 + x5 = -4 x1, x2, x3, x4, x5 0Min f = 2 x1 + 3 x2 + 4 x3 S.t. x1 + 2 x2 + x3 3 2 x1 - x2 + x3 4 x1 , x2 , x3 0北京外国语大学国际商学院蔡连侨3-51北京外国语大学国际商学院蔡连侨3-52ekeikikiabaab0minekkejejiaaa0min是是是是否否否否所有所有得到最优解计算计算原规划的基本解是可行的原规划的基本解的检验数为非正所有所有计算计算以aek为中心元素进行迭代以aek为中心元素进行迭代停没有有限最优解没有可行解单纯形法对偶单纯形法0j0ib0maxjj

33、k0miniiebbb0ika0eja北京外国语大学国际商学院蔡连侨3-53对偶单纯形法的应用前提：有一个基，其对应的基满足：单纯形表的检验数行全部非正（对偶可行）变量取值可有负数（非可行解）对偶单纯形法适合于解如下形式的线性规划问题njxmibxacxcfjnjijijnjjjj,2, 1,0,2, 10min11北京外国语大学国际商学院蔡连侨3-54在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以

34、免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算北京外国语大学国际商学院蔡连侨3-55上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由 x1 取代 x6 目标函数可改善。 北京外国语大学国际商学院蔡连侨3-561、b0,10,20, 1=0或2=0时不唯一（不考虑退化的复杂情况，需要再分情况讨论）2、b 0 时现基本解不可

35、行3、b 0, a1 0, b0,无有限最优解5、10, b0, a3 0, 3/a3 0csMinj /asjasj0csMinj /asjasj0brMin-bi/irir0北京外国语大学国际商学院蔡连侨3-72例10：例9的最优单纯形表如下 0 1/4 0 这里 B-1 = -2 1/2 1 1/2 -1/8 0 各列分别对应 b1、b2、b3 的单一变化，因此，设 b1 增加 4，则 x1, x5, x2分别变为：4+04 = 4，4+(-2)4 = -40，2+1/24=4北京外国语大学国际商学院蔡连侨3-73 用对偶单纯形法进一步求解，可得： x* = ( 4, 3, 2, 0,

36、0 )T, z * = 17北京外国语大学国际商学院蔡连侨3-74是否投产新产品增加一个变量 假设可以生产一种新产品，增加变量 xn+1，则有相应的pn+1，cn+1 计算出B-1pn+1 , n+1=cn+1-ci ai ,n+1，填入最优单纯形表，不影响解的可行性以及其余检验数 若 n+1 0 则 最优解不变；否则，进一步用单纯形法求解北京外国语大学国际商学院蔡连侨3-75例11：例9增加x6 ， p6=( 2, 6, 3 )T，c6 = 5 计算得到用单纯形法进一步求解，可得：x* = ( 1,3/2,0,0,0,2 )T z* = 33/2，应该生产新产品北京外国语大学国际商学院蔡连侨

37、3-76增加资源约束或加工工序增加一个约束有些资源由于紧缺，不能像以前一样随便使用，如电力供应有限制等，这就增加了约束；或者增加一道工序，也需要增加一个约束增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解北京外国语大学国际商学院蔡连侨3-77例12：例9增加3x1+ 2x215，原最优解不满足这个约束。引入松弛变量，得到 3 x1+ 2 x2 + x6 = 15经过行变换，可以得到北京

38、外国语大学国际商学院蔡连侨3-78经对偶单纯形法一步，可得最优解为（7/2, 9/4, 0, 2, 3, 0 )T，最优值为 55/4北京外国语大学国际商学院蔡连侨3-79生产工艺发生变化A中元素发生变化如果发生变化的元素不在基中，则与增加变量 xn+1 的情况类似，假设 pj 变化，那么，重新计算出B-1pj ，j = cj - ci ai j ，填入最优单纯形表，若 j 0 则最优解不变；否则，进一步用单纯形法求解如果发生变化的元素在基中，则B和B-1都发生变化，也可能原问题和对偶问题的解均不可行，这时需引入人工变量将原问题的解转化为可行解，再用单纯形法求解北京外国语大学国际商学院蔡连侨3

39、-80例13：例9中若原计划生产产品I的工艺有了改进，相关技术系数向量由P1=(1,4,0)T变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响? 解：把改进工艺结构的产品I看作产品I，设x1为其产量。于是在原计算的最终表中以于是在原计算的最终表中以x1代替代替x1，计算对，计算对应应x1的列向量及检验数。的列向量及检验数。8383214530248321452520812112120410111111TBPBCcPB北京外国语大学国际商学院蔡连侨3-81以x1为换入变量，x1为换出变量，经过迭代得到最优解为（16/5, 4/5, 0, 0, 12/5)T，最优值为 76

40、/5。北京外国语大学国际商学院蔡连侨3-82例14：例9中若原计划生产产品I的工艺有了改进，相关技术系数向量由P1=(1,4,0)T变为P1=(4,5,2)T，每件利润为4元，试分析对原最优计划有什么影响? 解：把改进工艺结构的产品I看作产品I，设x1为其产量。在原计算的最终表中以在原计算的最终表中以x1代替代替x1，计算对应，计算对应x1的列向量及检验数。的列向量及检验数。8218112745302481127452540812112120410111111TBPBCcPB北京外国语大学国际商学院蔡连侨3-83注意：若碰到原问题和对偶问题均为非可行解时，就注意：若碰到原问题和对偶问题均为非可

41、行解时，就需要引进人工变量后重新求解。需要引进人工变量后重新求解。北京外国语大学国际商学院蔡连侨3-84原问题和对偶问题都是非可行解，引入人工变量x6。在上表中x2所在行，用方程表示为0 x1 + x2 + 1/2 x3 2/5 x4 + 0 x5 = - 12/5引入人工变量x6后，化为 0 x1 x2 1/2 x3 + 2/5 x4 + 0 x5 + x6 = 12/5将x6作为基变量代替x2，填入表中，得到下表。北京外国语大学国际商学院蔡连侨3-85得到最优解为（2/3, 8/3, 0, 38/3, 0, 0)T，最优值为 32/3。北京外国语大学国际商学院蔡连侨3-8686多个参数同时

42、发生变化，适用100%准则。多个目标函数系数发生变化，定义变化的程度比例：为允许的最大减量）（若为允许的最大增量）（若jjjjjjjjjjDDcrcIIcrc, 0, 0然是最优的。，那么原来的最优解仍如果1jr北京外国语大学国际商学院蔡连侨3-8787多个右端项同时发生变化，定义变化的程度比例：为允许的最大减量）（若为允许的最大增量）（若jjjjjjjjjjDDbrbIIbrb, 0, 0，那么最优基不变。如果1jr北京外国语大学国际商学院蔡连侨3-88利用软件进行求解QSBLINDOEXCEL（举例说明使用方法）北京外国语大学国际商学院蔡连侨3-89线性规划的对偶问题线性规划的对偶单纯形法

43、线性规划的灵敏度分析参数线性规划北京外国语大学国际商学院蔡连侨3-90参数线性规划参数线性规划灵敏度分析时，主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。而参数线性规划是研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这个参变量的线性函数，含这个参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题。北京外国语大学国际商学院蔡连侨3-91参数线性规划参数线性规划其步骤是：对含有某参变量t的参数线性规划问题。先令t=0，用单纯形法求出最优解用灵敏度分析法，将参变量t直接反映到最终

44、表中当参变量t连续变大或变小时，观察b列和检验数行各数字的变化。若在b列首先出现某负值时，则以它对应的变量为换出变量；于是用对偶单纯形法迭代一步。若在检验数行首先出现某正值时，则将它对应的变量为换入变量；用单纯形法迭代一步在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复上一个步骤，直到b列不能再出现负值，检验数行不能再出现正值为止北京外国语大学国际商学院蔡连侨3-92参数线性规划参数线性规划参数C的变化例15：试分析以下参数线性规划问题。当参数t0时的最优解变化。0,18231224)5()23()(max21212121xxxxxxxtxttz北京外国语大学国际商学院蔡连侨3-93参数线性规划参数线性规划解 将此模型化为标准型令t=0，用单纯形法求解：0,18231224)(0)5()23()(max543