运筹学第02章线性规划的对偶理论

1、第二章 线性规划的对偶理论(Duality Theory)线性规划的对偶问题 对偶问题的基本性质 对偶问题的经济解释-影子价格对偶单纯形法灵敏度分析WinQSB软件应用第一节 线性规划的对偶问题 【例2-1】第一章例1-1中讨论了某企业利用三种资源生产甲乙两种产品的生产计划问题，得到其线性规划问题为： 对偶性是线性规划问题的最重要的内容之一。每一个线性规划(LP)问题必然有与之相伴而生的另一个线性规划问题，即任何一个求 max z 的LP都有一个求 min w 的LP。其中的一个问题叫“原问题”，另一个称为“对偶问题” 。一、对偶问题的提出下面从另一个角度来讨论这个问题： 假定该企业决定自己不

2、生产产品，而将现有的资源转让或出租给其他企业，那么该如何确定资源的转让价格？ 分析问题： 1、定价不能太高，否则买方无法接受，并且对买方来说，其目的是越低越好 ； 2、定价不能太低，否则企业不愿意放弃生产、出让资源 合理的价格应是对方用最少的资金购买该企业的全部资源，而该企业所获得的利润又不低于自己组织生产时所获得的利润。 解：设分别用 y1、y2和 y3 代表单位时间(h)设备、每公斤材料A、材料B的出让代价，根据假设有以下对应关系：y1y2y3 则该企业出租或转让所有资源所获得的收入，也即对方企业需要支付的资金为： 企业用1台时设备和3公斤材料A可生产一件甲产品，盈利90元，其出售这些数量

3、的资源得到的利润不能少于90元，则有： 同理，用1台时设备、2公斤材料A 、5公斤材料B可生产一件乙产品，盈利70元，出售这些数量资源得到的利润不能少于70元，则有：综上分析，可得到线性规划模型为： （LP2） 对偶问题二、对称形式下对偶问题的一般形式 满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。 对称形式的线性规划问题的原问题为：用矩阵形式表示为：对偶问题的一般形式为: 上述模型简记为： 用矩阵形式表示，对偶问题为： 将上述对称形式下线性规划的原问题与对偶问题进行比较，可以列出如下表所示的对应关系：

4、决策变量约束条件约束条件决策变量约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量b约束条件的右端项向量b约束条件系数矩阵(A的转置)约束条件系数矩阵A目标函数目标函数对偶问题原 问 题 若原问题为求极小形式的对称形式线性规划问题，对偶问题应该具有什么形式？ 原问题对偶问题若一个线性规划问题是另一个线性规划问题的对偶问题，则它们互为对偶问题。 对偶问题的对偶问题是原问题。9070 x1 x2 16y1 111636y2323665y305659070原问题对偶问题对偶问题 【例2-2】 写出下述线性规划问题的对偶问题 例中目标函数为max，若为对称形式，则约束条件应为“”号

5、，所有变量均应0。 非对称形式三、非对称形式的原对偶问题关系1目标函数为求极大，故约束条件应均为“”号约束b两边乘-1：将c写成两个不等式约束：2变量均有非负约束令：则：原问题对偶问题原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数 Max z=CX目标函数 Min w=YTb约束条件决策变量决策变量约束条件m个=n个=n个00无约束m个00无约束原问题对偶问题【例2-3】写出下列线性规划问题的对偶问题第二节 对偶问题的基本性质 一、单纯形法计算的矩阵描述(P)(D)对称形式原线性规划问题加上松弛

6、变量后为：其中，Xs=(xn+1,xn+2,，xn+m )为松弛变量，I为mm 单位矩阵。 本节的讨论先假定原问题及对偶问题为对称形式线性规划问题，即原问题为： 设B是一个可行基，也称基矩阵，若将系数矩阵 A 分为(B,N)两块，这里 N 是非基变量的系数矩阵，对应于基 B 的变量为XB，其它非基变量用XN 表示。即: 同时也将 C 分为两块(CB ,CN )，CB 是目标函数中基变量 XB 的系数行向量，CN 是目标函数中非基变量XN 的系数行向量。0CNCB j INBbXs0XsXNXB基变量非基变量初始单纯形表 将为块后的数据放入单纯形表，得：用 左乘上表第3行得：I0用 左乘下表第3

7、行，加上表第4行得： j XBCBXsXNXB非基变量基变量最终单纯形表j XBCBXsXNXB非基变量基变量最终单纯形表I0 由上表可以看出，若此时得到的是最优解，则各检验数应满足：非基变量 XN 的检验数：松弛变量 XS 的检验数：基 变 量 XB 的检验数： 由上三个检验数可以看出，它们都有乘子 ，称它为单纯乘子，用符号表示为：讨论：(1)(2) 将(1)(2)式合并，可以可以得到：(3) 1.初始表中单位阵在迭代后单纯形表中对应的位置就是B-1； 2.对于原问题的任意可行解，各松弛变量检验数的相反数恰好是其对偶问题的一个可行解，且两者具有相同的目标函数值。 上面(3)式可以写为： 将

8、同时右乘 b 得： 从上述分析可以得到如下结论：j XBCBXsXNXB非基变量基变量最终单纯形表I0即：二、对偶问题的基本性质1、对称性：对偶问题的对偶问题是原问题。对偶定义对偶定义 2、弱对偶性：设 和 分别是问题（P）和（D）的可行解，则恒有:即： 推论：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 推论：如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解 注：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之

9、亦然。 推论：若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界 3、最优性 若 和 分别是P 和D的可行解且 ，则 和 分别是问题P和D的最优解。4、强对偶性 若一对对偶问题P 和D都有可行解，则它们都有最优解，且目标函数的最优值必相等。 推论：若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等 5、互补松弛性 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。也即： cj9070000CBXBb

10、x1x2x3x4x570 x212013-1090 x1410-2100 x55 00 -1551j00-30-200若 ，即 ，则有 若 ，则有 ，即 cj9070000CBXBbx1x2x3x4x570 x212013-1090 x1410-2100 x55 00 -1551j00-30-200若 ，则有 若 ，则 【例2-4】线性规划问题为：若已知原问题的最优解为 X * =（0,0,4），z*=12 试求对偶问题的最优解。解：相应的对偶问题为：（a）（b）（c）将X* =（0, 0, 4）代入原问题中，有下式：根据互补松弛条件，必有y*1= y*2=0。代入对偶问题 (c)式，y3 =

11、3。因此，对偶问题的最优解为Y*=(0, 0, 3)，w =12（a）（b）（c）第三节 对偶问题的经济解释 影子价格 在单纯形法的迭代过程中，目标函数z=CBB-1b和检验数 CN-CBB-1N中都有单纯乘子YT=CBB-1 ，那么Y的经济意义是什么？ 从上节对偶问题的基本性质看出，当线性规划原问题求得最优解 时，其对偶问题也得到最优解 ，且代入各自的目标函数后有: 式中，bi 是线性规划原问题约束条件的右端项，它代表第 i 种资源的拥有量。 设B是问题 P的最优基：当bi 变为bi+1 时（其余右端项不变，也不影响B） 目标函数最优值变为：对 bi 求偏导数得：其经济意义是：在其它条件不变

12、的情况下，单位资源变化所引起的目标函数的最优值的变化。即 y*i 表示 z* 对 bi 的变化率。 由此可以看出， yi 表示对第 i 种资源的估价，这种估价不同于资源的市场价格，是根据资源在生产中做出的贡献而作的估价，它是针对具体企业的具体产品而存在的一种特殊价格，为区别起见，称它为“影子价格”。 一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。正确理解影子价格，可帮助决策者分析经济活动，作出有利决策。 第四节 对偶单纯形法一、对偶单纯形法的基本思路设 （P）则 （D）化为标准型:（P）（D）设B为(P)的

13、一个基，记A=(B, N)，C=(CB, CN)，X=(XB, XN)T（P）的标准型可写为：（P）（D）（D）的标准型可写为：则标准型的数学模型可用单纯形表表示为：cjCBCN0CBXBB-1bIB-1NB-1j0CN-CBB-1N-CBB-1-YTs1-YTs2-YT 若B为(P)的可行基，则 XB=B-1b 为(P)的一个基可行解，相应的检验数为0，CN-CBB-1N，-CBB-1。 令YT=CBB-1，代入(D)的约束条件中，可发现检验数行恰为对偶问题的一组基解的相反数。确定初始单纯形表j 0 ?b i 0 ?寻找新的基解单纯形法单纯形表人工变量法计算结束是否否是单纯形法对偶单纯形法

14、在单纯形表中进行迭代时，在 b 列中得到的是原问题的基可行解，此时检验数行得到的是对偶问题的一个基解。 通过逐步迭代，当对偶问题得到基可行解时，所有检验数均不大于0，此时原问题取得最优解。0-20-3000j15-15005x5001-2014x1900-131012x2700-300100j131005065x501801/302/3112x190120-1/311/304x300007090j1005065x50120102336x40160011116x30 x5x4x3x2x1bXBCB0007090Cj 根据对偶问题的对称性，若保持对偶问题的解是基可行解，而原问题在非可行解的基础上通

15、过逐步迭代得到基可行解，此时也就得到了原问题的最优解。 对偶单纯形法的基本思路： 如果存在一个对偶问题的可行基B，即对j=1,2,n，有 或，这时只要有，即原问题的解为可行解，则两者均为最优解。否则保持对偶问题为可行解，找出原问题的相邻基解，判别是否有 ，循环进行，直到使原问题也为可行解，从而两者均为最优解。 与单纯形法的标准形相比，这里没有对右端项不大于零的要求，因此，在得到的单纯型表中 b 列的值(B-1b)i 不一定非负。 若所有的(B-1b)i非负，则X为(P)的基可行解，此时X为(P)的最优解，Y为(D)的最优解；若存在某一个或几个的(B-1b)i0，则X不是(P)的可行解，需在保证

16、 Y 为(D)的基可行解的前提下进行迭代，直至找到(P)的一个可行解。 注：对偶单纯形法不是对对偶问题使用单纯形法，而是求解线性规划的另一有效方法。它之所以被称为“对偶单纯形法”，是因为该方法在求解过程中是以对偶原理和单纯形法原理为理论依据的。二、对偶单纯形法的计算步骤1、建立初始单纯形表 000100010001xnxsxm+1xmxrx1bCB2、最优性判断 检查 b 列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算； 若 b 列有负数，其中某负数对应的行没有负数,则问题无可行解 若 b 列有负数，而且所有负数对应的行都有负数，则转入下一步。3、基变换确定离基变量 为了使下一

17、个表中第r行基变量为正值，因而只有对应的非基变量才可以考虑作为进基的变量。为了使下一个表中对偶问题的解仍为可行解，令:称 为主元素， 为进基的变量。迭代因为总存在，令，其对应变量为离基的变量。确定进基变量 对新的基再检查是否所有。如果是，找到了两者的最优解；如为否，回到第2步再循环进行。 重复2-3步。【例2-5】用对偶单纯形法求解下述线性规划问题： 解：先将问题改写为：约束条件（a），(b)两端乘以“-1”得：Cj-16-36-6500CBXBby1y2y3y4y50y4-90-1-30100y5-70-1-2-501j-36y20y5j-36y2-16y1j-16-36-65301/310

18、-1/30-10-1/30-5-2/3100-40-65-1203010152-32001-5-1100-5-4-12所以，原问题最优解为 ：Y*=（30 , 20 , 0 , 0 , 0） 其对偶问题的最优解为： X*= (4 , 12)【练习】用对偶单纯形法求解下述线性规划问题： 解：将模型转化为:Cj-2-3-400CBXBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301j0 x4-2x1j-3x2-2x1j-2-3-4-10-5/21/21-1/221-1/23/20-1/2000-4-10-111/5107/5-1/5-2/52/501-1/5-2/51/

19、500-9/5-8/5-1/5所以，原问题最优解为 ：X*=（11/5 , 2/5 , 0 , 0 , 0） 其对偶问题的最优解为： Y*= (8/5 , 1/5)第五节 灵敏度分析 灵敏度分析研究的就是模型的变化对线性规划问题最优基或最优解的影响程度，主要包括以下两个问题： 参数在什么范围内变化时，原最优基和最优解不变？ 模型发生变化时，最优基和最优解会如何变化？ 线性规划问题中的参数往往是一些估计和预测的数字，当市场条件发生变化时，会影响到模型参数的变化，如： cj 值的变化； aij 随工艺技术条件的改变而改变； 资源投入情况改变，资源限制量 bi 会随之改变； 方法：将个别参数的变化直

20、接在计算得到最优解的最终单纯形 表上反映出来，并进行检查和分析。引进人工变量，编制新单纯形表，重新计算非可行解非可行解用对偶单纯形法继续迭代求最优解可行解非可行解用单纯形法继续迭代求最优解非可行解可行解最优解或最优基不变可行解可行解一、 价值系数cj 的变化分析 线性规划目标函数中变量系数 Cj 的变化仅仅影响到检验数的变化j，所以将 Cj 的变化直接反映到最终单纯形表中。 结论或继续计算的步骤对偶问题原问题表2-8 在最终单纯形表中，只可能出现如表2-8中的前两种情况之一： 若最终表中所有检验数仍然均不大于0，即对偶问题取得可行解，出现表2-8中第一种情况，问题的最优基和最优解不变； 若出现

21、大于0的检验数，即出现表2-8中第二种情况，则需使用单纯形法继续迭代求得最优解。 【例2-6】在上述第一章例1-1的某企业的例子中： 若甲产品的利润降至85元/件，而乙产品的利润增至95元/件时，该企业的最优生产计划有何变化；第一章例1-1的某企业的例子，其相应的数学模型为：若发生变化的 Cj 是非基变量的价值系数，则检验数为：若发生变化的 Cj 是基变量的价值系数，则检验数为： 若甲产品的利润不变，则乙产品的利润在什么范围内变化时，该企业的最优生产计划将不发生变化。 解：(1)将甲、乙产品的利润变化直接反映到最终单纯形表中，得：因变量 x4 的检验数大于零，故需继续用单纯形法迭代计算得： 即

22、该企业随产品甲、乙的利润变化应调整为生产甲3件，乙13件。cj8595000CBXBbx1x2x3x4x595x212013-1085x1410-2100 x55 00 -1551j00-115100cj 8595000CBXBbx1x2x3x4x595x285x10 x4j100-311/51301001/531010-1/500-850-290707090-30-20（2）设产品乙的利润为（70+）元，反映到最终单纯形表中，得表: 为使上表中的解仍为最优解，应有：解得: 即乙产品的利润 c2 的变化范围应满足：cj9070+000CBXBbx1x2x3x4x570+x212013-1090

23、 x1410-2100 x55 00 -1551j00-30-3-20+0二、资源限量bi 的变化分析 当右端项发生变化后，会引起单纯形表中b 列数字的变化，此时可能出现表中第一或第三种情况： 出现表2-8中第一种情况时，问题最优解不变； 出现表2-8中第三种情况时，用对偶单纯形法找最优解。 【例2-7】在某企业的例子中： (1)若设备和材料 B 的现有资源不变，而材料 A 的现有资源增加到51公斤时，分析企业最优计划的变化； (2)材料 A 和 B 的现有资源不变，则设备的现有资源在什么范围内变化时，问题的最优基不变？ 当发生变化后，最终单纯形表中原问题的解相应地变化为:解：将其反映到最终单

24、纯形表中得： 因上表中原问题为非可行解，用对偶单纯形法继续计算得表： cj9070000CBXBbx1x2x3x4x570 x2-3013-1090 x11910-2100 x580 00 -1551j00-30-200cj9070000CBXBbx1x2x3x4x50 x490 x10 x5j30-1-310161110065050010-20-9000由此该的最优计划改为只生产甲产品16件。设设备每天可用能力为(16+)小时，因有： 将其反映到最终单纯形表中，其b 列数字为： 解得-41/3。即设备的能力应在1249/3小时之间。 当b0时问题的最优基不变，即： 三、增加一个新变量的分析

25、【例2-8】在某企业的例子中，设企业又计划推出新型号的产品丙，生产一件所需设备台时及材料A、B分别为1小时、4公斤、3公斤，该产品的预期利润为115元件，试分析该种产品是否值得投产；如投产，该企业的最优生产计划有何变化？1.计算： 2.计算新的 增加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为： 3.若 ，原最优解不变，只需将计算得到的 和 直接写入最终单纯形表中；若 ，则按单纯形法继续迭代计算找出最优解。 解：设该企业生产丙产品 x6 件，根据题意有c6115，P6(1，4，3)T。则相应的技术系数向量为：将其反映到最终单纯形表中得表： cj9070000115CBXBbx1x2

26、x3x4x5x670 x212013-10-190 x1410-21020 x55 00 -15518j00-30-2005，故用单纯形表继续迭代计算得表： 故该新的最优生产计划应为生产甲产品 11/4件，乙产品 101/8件，丙产品5/8件cj9070000115CBXBbx1x2x3x4x5x670 x290 x1115x6jcj9070000115CBXBbx1x2x3x4x5x670 x212013-10-190 x1410-21020 x55 00 -15518j00-30-20055/800-15/85/81/81101/8019/8-3/81/8011/4107/4-1/4-1/

27、4000-165/8-185/8-5/80四、技术系数aij 的变化分析 【例2-9】在某企业的例子中，进行工艺改进后若甲产品每件需设备、材料A和材料B变为1台时、2公斤和0公斤，该产品的利润变为100元件，试重新确定企业的最优生产计划。1.计算： 引起矩阵A的变化 若xj 在最终单纯形表中为非基变量，则： 若xj在最终单纯形表中为基变量，则可能出现第四种情况。此时，需要引进人工变量，编制新的单纯形表，重新计算。2.计算新的 从而判断是否需要迭代寻找最优解。 解：先将生产消耗变化后的新产品甲看作是一种新产品，生产量为 ，仿本节三的步骤直接计算 和 并反映到最终单纯形表中。其中：将其反映到最终单

28、纯形表中： cj9010070000CBXBbx1x1x2x3x4x570 x2120113-1090 x14100-2100 x55 0-50 -1551j0300-30-200因 已变换为 ，故用单纯形法将 替换出基变量中的 ，得:cj9010070000CBXBbx1x1x2x3x4x5100 x190 x10 x5j120113-104100-2106500500100-30-120100变量x4对应检验数大于零，没得到最优解，用单纯形法迭代：cj9010070000CBXBbx1x1x2x3x4x5100 x1160111000 x44100-2100 x565 005 001j-1

29、00-30-10000该企业的最优生产计划为只生产工艺改进后的甲产品16件。五、增加一个约束条件的分析 增加一个约束条件在实际问题中相当增添一道工序。分析的方法是先将原问题最优解的变量值代入新增的约束条件，如满足，说明新增的约束未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。 【例2-10】仍以某企业为例，设甲乙产品生产完后，还需经过一道环境试验工序。甲产品每件须环境试验2小时，乙产品每件1.5小时，又环境试验工序拥有资源为24小时。试分析增加该工序后企业的最优生产计划。 解：环境试验工序的约束条件：原问题最优解不是本例的最优解 将标准化后的约束条件以x6

30、为基变量，反映到最终单纯形表中得表: cj90700000CBXBbx1x2x3x4x5x670 x212013-10090 x1410-21000 x5500 -155100 x62421.50001j00-30-2000将最优解 x1 =4，x2 =12 代入新的约束条件，得： 进行变换，得：cj90700000CBXBbx1x2x3x4x5x670 x212013-10090 x1410-21000 x5500 -155100 x6-200-0.5-0.501j00-30-2000原问题为非可行解，用对偶单纯形法迭代计算得表: cj90700000CBXBbx1x2x3x4x5x670 x290 x10 x50 x4j1601400-2010-3002-1500-200110400110-200-1000-40 添加环境试验工序后，该企业的最优生产计划为甲产品生产9/4件，乙产品生产13件。 cj90700000CBXBbx1x2x3x4x5x670 x290 x10 x30 x4jcj90700000CBXBb