第4章 对偶理论与灵敏度分析.ppt

《第4章 对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《第4章 对偶理论与灵敏度分析.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 主要内容：主要内容：对偶规划对偶理论对偶单纯形算法14.1对偶问题的提出对偶问题的提出 现从另一个角度来讨论，假定工厂考虑不现从另一个角度来讨论，假定工厂考虑不安排生产，而是出售原材料，出租工时或转产安排生产，而是出售原材料，出租工时或转产新产品等。问如何定价，可使工厂获利不低于新产品等。问如何定价，可使工厂获利不低于安排生产所获得的收益，且又能使这些定价具安排生产所获得的收益，且又能使这些定价具有竞争力？有竞争力？设出售原料的定价为毎公斤设出售原料的定价为毎公斤y y1 1元，元，出租工出租工时的定价为毎工时时的定价为毎工时y y2 2元元.从工厂考虑，这些定价从工厂考虑，这些定

2、价下的获利不应低于安排生产所获得的收益。否下的获利不应低于安排生产所获得的收益。否则工厂宁可生产，而不出售或出租或转产等则工厂宁可生产，而不出售或出租或转产等,由此考虑出售或出租或转产的数学模型由此考虑出售或出租或转产的数学模型.2对偶问题对偶问题?任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义 假设有商人要向厂方购买资源假设有商人要向厂方购买资源A和和B，问他们谈判原料问他们谈判原料价格的模型是怎样的？价格的模型是怎样的？3原问题原问题简单的生产计划问题简单的生产计划问题 如何安排一天的生产计划，使企业利润最大？某工厂生产甲、乙两种产品，单位产品利润、耗工耗料及工料限额为下表4解：

3、解：限制条件限制条件：“s.t.”:Subject to目标函数决策变量约束条件5新问题新问题简单的生产计划问题简单的生产计划问题 设出售原料的定价为毎公斤设出售原料的定价为毎公斤y y1 1元，元，出租工时的出租工时的定价为毎工时定价为毎工时 元元.6 例例 生产计划问题生产计划问题 某工厂用三种原料生产三种产品，已知某工厂用三种原料生产三种产品，已知的条件如表的条件如表2.1.1所示，试制订总利润最大所示，试制订总利润最大的生产计划。的生产计划。单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品

4、的利润（千元）3547 （原问题）（原问题）8*对偶问题9 原问题与对偶问题的关系（一）对称形式的对偶问题比较上述的两个互为对偶问题：101、一个问题中的约束条件个数等于它的对偶问题中的变量数。2、一个问题中目标函数的系数是其对偶问题中约束条件的右端项。3、约束条件在一个问题中为“”，则在其对偶问题中为“”.4、目标函数在一个问题中求最大值，在其对偶问题中则为求最小值。显然：对称形式的对偶问题，若已知其中一个问题，立即就可以写出相应的对偶问题。11 表表2.13 2.13 对偶变换的规则对偶变换的规则约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的12

5、原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 MaxZ目标函数目标函数 MinW约束条件数：约束条件数：m个个第第 i个个 约约 束束 条条 件件 类类 型型 为为“”第第 i个个 约约 束束 条条 件件 类类 型型 为为“”第第i个约束条件类型为个约束条件类型为“=”对偶变量数：对偶变量数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 决策变量数：决策变量数：n个个第第j个变量个变量0第第j个变量个变量0第第j个变量是自由变量个变量是自由变量 约束条件数：约束条件数：n第第 i个个 约约 束束 条条

6、件件 类类 型型 为为“”第第 i个个 约约 束束 条条 件件 类类 型型 为为“”第第i个约束条件类型为个约束条件类型为“=”13课堂练习：写出下面线性规划的对偶规划：课堂练习：写出下面线性规划的对偶规划：14下面的答案哪一个是正确的？为什麽下面的答案哪一个是正确的？为什麽？（原原问问题题是是极极小小化化问问题题，因因此此应应从从原原始始对对偶偶表的表的右边右边往往左边左边查！查！）15（二）非对称形式的对偶问题 （1）如果原问题约束中包含等式约束，如AX=b等价于 162.4.3 对偶问题的基本性质定理1、对称性定理：对称性定理：对偶问题的对偶是原问题。2、弱对偶定理：若X(0)是原问题的

7、可行解,Y(0)是对偶问题的可行解,则有CX(0)Y(0)b.3、最优性定理：若X(0)是原问题的可行解,Y(0)是对偶问题的可行解,且有CX(0)=Y(0)b则 X(0)、Y(0)分别是原问题和对偶问题的最优解。4、对偶定理：若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等。5、互补松弛性定理：X*、Y*分别是原问题和对偶问题的可行解，则 X*、Y*是最优解的充分必要条件是X*YS=0和Y*XL=06、解的对应定理：原问题的单纯形表的检验数行对应其对偶问题的一个基解.由解的对应定理可知，当在检验数行得到对偶问题的解可行时，原问题已达到最优解。17对偶定理对偶定理 是是揭揭

8、示示原原始始问问题题的的解解与与对对偶偶问问题的解之间重要关系题的解之间重要关系的的一系列定理。一系列定理。18 2.4.4 对偶单纯形法对偶单纯形法 什麽是对偶单纯形法？什麽是对偶单纯形法？对对偶偶单单纯纯形形法法是是应应用用对对偶偶原原理理求求解解原原始始线线性性规规划划的的一一种种方方法法在在原原始始问问题题的的单单纯形表格上进行纯形表格上进行对偶处理对偶处理。注意：注意：不是解对偶问题的单纯形法！不是解对偶问题的单纯形法！192.4.4 对偶单纯形法1、两种方法的特点单纯形法特点：在保持基可行解的情况下，每迭代一次，就使目标函数值增大一次，当问题取得最优解时，目标函数达到最大值。对偶单

9、纯形法特点：将单纯形法应用于对偶问题的计算，在保持对偶问题有可行解的基础上，每迭代一次，就使目标函数值减少一次，当问题得到最优解时，目标函数取到最小值。202、对偶单纯形法的计算步骤（1）把对偶问题化为标准形，但允许主约束条件右边常数 为任意数。(注意到这里并不需引进人工变量)（2）通过对约束等式两边同乘“1”产生初始基（单位矩阵），列出初始表。（3）确定“出基”变量：21出基原则：小于0的 中最小者（绝对值最大者）所对应的行变量。即在所有 0中，对应的变量yr出基，yr所在行为主元行。原问题的进基原则：中最小对应的列变量。（4）确定“进基”变量 若主元行中没有负元素，可以证明问题没有可行解，

10、计算结束。（原问题中：若主元列都是负元素，可以证明问题有无数可行解，无最优解。）否则，按最小比值原则确定进基变量：（5）用进基变量替换出基变量得到新基，继续迭代。（6）重复35步。2223约束条件两端乘以“-1”得24 cj -15 -24 -5 0 0CBYBb y1 y2 y3 y4 y500y4y5-2-1 0 -6 -1 1 0-5 -2 -1 0 1 w 0 15 24 5 0 0-240y2y51/3-1/3 0 1 1/6 -1/6 0-5 0 -2/3-1/3 1 w-8 15 0 1 4 0-24-5y2y31/41/2-5/4 1 0 -1/4 1/4 15/2 0 1 1

11、/2 -3/2 w-17/2 15/2 0 0 2/7 3/2原问题的最优解为(0,1/4,1/2),最优值为17/225由上例得结论：（1）当约束条件为“”时，不必引进人工变量，使计算简化。（2）由对偶问题的性质知道：用单纯形法求解L.P问题时，每一次迭代可得一个基解，这时检验数行的数是对偶问题的一个基解。原问题的松驰变量对应着对偶问题的决策变量，对偶问题的松驰变量对应着原问题的决策变量。在一个问题中是基变量，则在另一个问题中就是非基变量，反之亦然。（3）对偶问题的解正是原问题的最优表中松驰变量 在检验数行中的数。反之，原问题的解正是对偶问题的最优表中松驰变量 在检验数行中的数。（4）对偶问

12、题的解yi称为资源的影子价格。26 原问题 对偶问题 每次迭代，检验数行的数 基解（最优表中是最优解 -影子价格）松馳变量 决策变量 决策变量 松馳变量 基变量 非基变量 非基变量 基变量 目标函数值 =目标函数值 练习P.30例14272.4.5 对偶变量的经济意义和影子价格1、影子价格（Shadow Pyice)：对资源在生产中做出的贡献而做出的评价。它不是市场价格。资源的市场价格是已知的，而影子价格有赖于资源的利用情况，是未知的。对偶变量的经济意义就是影子价格.2、影子价格是一种边际价格。（随着资源量的改变而改变）283、没有最优决策，就没有影子价格。影子价格真实反映了资源在最优决策下对

13、总收益（目标函数值）的影响和贡献大小。由松紧定理知，影子价格为正数，表明该种资源在最优决策下已充分利用耗尽，并成为进一步增加总收益的紧缺资源（短线资源），影子价格为零，表明该种资源在最优决策下尚有剩余（长线资源）。4、影子价格是机会成本。当某种资源的市场价格低于影子价格时，可购进该种资源，组织和增加生产。当某种资源的市场价格高于影子价格时，可卖出该种资源，不安排生产或提高产品价格。当某种资源的市场价格等于影子价格时，则处于平衡状态。5、有效利用资源的影子价格指导经济活动是有积极意义。29 复习单纯形法（复习单纯形法（P16的例的例5）引例引例：解：解L.P问题问题30 cj 4 3 0 0CB

14、XBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 11226/3 Z 0 -4 -3 0 004x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3413 Z104/3 0 -1/3 0 4/334x2x1 4 6 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5注意注意:哪个数是影子价格哪个数是影子价格?有可意义有可意义?312.52.5灵敏度分析灵敏度分析(优化后分析优化后分析)一、一、问题的提出：问题的提出：在前面的讨论中都假定问题中的在前面的讨论中都假定问题中的aij ,bi ,cj 是是已知常数。

15、但在实际中，这些数据大多数是预测、已知常数。但在实际中，这些数据大多数是预测、统计、评估的结果。因而有必要分析：统计、评估的结果。因而有必要分析：（1）当这些参数中的一个或多个发生变化时，）当这些参数中的一个或多个发生变化时，问题的最优解会发生什么变化？问题的最优解会发生什么变化？（2）这些参数在多大范围内变化时，问题的）这些参数在多大范围内变化时，问题的最优解才不会改变。最优解才不会改变。（3）若问题的最优解起了变化，怎样在先前）若问题的最优解起了变化，怎样在先前优化的基础上迅速求得新的最优方案？优化的基础上迅速求得新的最优方案？32二、最优单纯形表中各块与各系数的关系二、最优单纯形表中各块

16、与各系数的关系 CCBXB b X b A ZCBB-1b CBB-1A-C各块与各系数的关系：各块与各系数的关系：（1 1）B B-1-1A A与与a aijij 有关；（有关；（2)B2)B-1-1b b与与a aijij,b,bi i 有关有关;（3)3)C CB BB B-1-1A-CA-C与与a aijij,c,cj j有关有关;（4 4）Z=CZ=CB BB B-1-1b b与与 a aijij,b bi i,c cj j 都有关。都有关。注意：注意：B B为最为最优优基，其相应元素及基，其相应元素及b b，A A的元素都是的元素都是初始表初始表中的相中的相应元素。应元素。CCBX

17、B b X B-1b B-1A ZCBB-1b CBB-1A-C 初始表最优表33 由上，分析可以从以下两方面入手：由上，分析可以从以下两方面入手：（1）数据的变化是否影响基）数据的变化是否影响基B B的初始可行的初始可行性（性（B B-1-1b0b0);（2）数据的变化是否影响基）数据的变化是否影响基B B的对偶可行的对偶可行性（性（C CB BB B-1-1A-C0A-C0);从五个方面开展讨论：从五个方面开展讨论：（1 1）价值系数）价值系数c cj j的变化分析的变化分析 （2 2）资源数量）资源数量b bi i的变化分析的变化分析 (3)(3)技术系数技术系数a aijij的变化分析

18、的变化分析 (4)(4)对增加约束条件分析对增加约束条件分析 (5)(5)增加一个变量的分析增加一个变量的分析(不讲不讲)342.5.1 2.5.1 价值系数价值系数c cj j的变化分析的变化分析(1)(1)若若c cj j是最优表中非基变量是最优表中非基变量x xj j的系数（此情况实际中很少的系数（此情况实际中很少)当当c cj j c cj j+c cj j，为保持原基，为保持原基B B的最优性，须的最优性，须 35例1 已知L.P问题 s.t 解得 最终表如下：Cj 2 1 0 0 0CBXB b x1 x2 x3 x4 x5 021X3x1 x27.53.51.5 0 0 1 5/

19、4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 Z8.5 0 0 0 1/4 1/236试确定：（试确定：（1 1）当目标函数变为）当目标函数变为maxZmaxZ=5x=5x1 1+1.5x+1.5x2 2时，最优解会时，最优解会出现什么变化出现什么变化;(2)(2)目标函数变为目标函数变为maxZmaxZ=(2+=(2+c)xc)x1 1+x+x2 2时，时，c c在什在什么范围内变化，最优解不变。么范围内变化，最优解不变。解（解（1 1）将目标函数系数的变化直接反映到最终表：）将目标函数系数的变化直接反映到最终表：Cj5 1.5 0 0 0CBXB bx1 x2

20、 x3 x4 x5 051.5X3x1 x27.53.51.50 0 1 5/4 -5/21 0 0 1/4 -1/20 1 0 -1/4 3/2 Z19.75 0 0 0 7/8 -1/437 因因x5的检验数为负，继续迭代得新解为的检验数为负，继续迭代得新解为 x1=4,x2=0 :Cj 5 1.5 0 0 0CBXB b x1 x2 x3 x4 x5 050X3x1 x51541 0 5 1 0 0 1 1/3 0 1/6 0 0 2/3 0 -1/6 1 Z20 0 1/6 0 5/6 038（2）将目标函数系数的变化直接反映到最终表，为使表中解将目标函数系数的变化直接反映到最终表，为

21、使表中解为最优，应有为最优，应有 Cj 2+c 1 0 0 0CBXB b x1 x2 x3 x4 x5 02+c 1X3x1 x215/27/23/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 Z 0 0 0+1/4+1/4c 1/2-1/2c39例例2 以以2.3.2引例引例(P.32例例15）的最终表为例，设基变）的最终表为例，设基变量量 x x1 1 的系数的系数 c c1 1变化为变化为c c1 1+cc1 1，在最优性不变条，在最优性不变条件下试确定件下试确定c c1 1 的范围。的范围。解：直接将解：直接将c c1 1+c c1

22、1 代入最终表并计算得下表代入最终表并计算得下表(见下见下页页)。为保持原基为保持原基B B最优性，解不等式组最优性，解不等式组40 Cj4+c1 3 0 0CBXB b x1 x2 x3 x434+c1x2 x1 46 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36+6c1 0 0 1/5-2/5c1 6/5+3/5c1412.5.2资源数量的变化分析资源数量的变化分析当资源数量当资源数量bk的值有变化时，由于的值有变化时，由于bk的变化与的变化与B-1,A和和C无关，仅与无关，仅与B-1b，CB B-1b有关。因此，当有关。因此，当42 例例3 3 在例在例1 1中中 (1)(

23、1)若第若第2 2个约束条件的右端项增大到个约束条件的右端项增大到32,32,分析最优解的变化分析最优解的变化.(2)(2)若第若第2 2个约束条件变为个约束条件变为 在什么范围内变化在什么范围内变化,表中基为最优基表中基为最优基.43将其加到最终表的基变量将其加到最终表的基变量b这一列得这一列得 Cj 2 1 0 0 0CBXB b x1 x2 x3 x4 x5 021X3x1 x235/211/2-1/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 Z 0 0 0 1/4 1/244因表中原问题为非可行解，用对偶法继续计算得因表中原问题为非可

24、行解，用对偶法继续计算得新的最优解新的最优解 x1=5 z.*=10 Cj 2 1 0 0 0CBXB b x1 x2 x3 x4 x5 020X3x1 x41552 0 5 1 0 0 1 1 0 0 1 0 -4 0 1 -6 Z10 0 1 0 0 24546 Cj 2 1 0 0 0CBXB b x1 x2 x3 x4 x5 021X3x1x2 15/2+5/47/2+1/43/2-1/4 0 0 1 5/4-15/2 1 0 0 1/4-1/2 0 1 0 -1/4 3/2 Z 0 0 0 1/4 1/247482.5.3 技术系数的变化分析技术系数的变化分析 因引进新技术、新工艺改

25、变了技术系数因引进新技术、新工艺改变了技术系数aij，将引起，将引起最优解、最优值的变化。最优解、最优值的变化。1、基变量、基变量xj的技术系数的技术系数aij改变。则在原最优表中改变。则在原最优表中用新变量用新变量x/j和相应的和相应的 列系数列系数B-1 p/j 代替代替xj和和B-1pj 继继续迭代求解：续迭代求解：（1）若）若bi0，检验系数不全非负，用单纯形法；，检验系数不全非负，用单纯形法；（2）若）若bi0，检验系数全非负，用对偶单纯形法；，检验系数全非负，用对偶单纯形法；（3）若）若bi0，检验系数不全非负，说明原问题和，检验系数不全非负，说明原问题和其对偶问题都没有可行解（无

26、法其对偶问题都没有可行解（无法“换基换基”），则只能引），则只能引进人工变量，编制新单纯形表重新计算。进人工变量，编制新单纯形表重新计算。49例例4 在在P.6的例的例1 中若生产产品甲的工艺有了改进，其技中若生产产品甲的工艺有了改进，其技术系数向量变为术系数向量变为p1/=(1,2)T，相应甲产品的每件利润为，相应甲产品的每件利润为6元。试分析对原计划有什么影响。元。试分析对原计划有什么影响。解：把改进工艺结构的产品甲视为甲解：把改进工艺结构的产品甲视为甲/，设，设x1/是其产是其产量，在最终表中用量，在最终表中用x1/,B-1 p1/代替代替x1,p1.其中其中 见下表：50 cj 6 3

27、 0 0CBXBb x/1 x2 x3 x436x2x/146-1/5 1 3/5 -2/5 4/5 0 -2/5 3/5-15/2 Z48-9/5 0 -3/5 12/536x2x/111/215/2 0 1 1/2 -1/4 1 0 -1/2 3/411-Z123/2 0 0 -3/2 15/406X3x/111 13 0 2 1 -1/2 1 1 0 1/2 Z78 0 3 0 3512 2、非基变量、非基变量x xj j的技术系数的技术系数a aijij改变。改变。由于只影响基由于只影响基B B的对偶可行性，而不影响的对偶可行性，而不影响B B的的可行性。可行性。522.5.42.5.

28、4增加一个主约束条件的分析增加一个主约束条件的分析 增加一个主约束条件，在实际问题中相当于增增加一个主约束条件，在实际问题中相当于增加一道工序。加一道工序。分析步骤：把原问题最优解代入这新增的约束分析步骤：把原问题最优解代入这新增的约束条件中：条件中：若满足，则说明这约束不起作用，原最优解不若满足，则说明这约束不起作用，原最优解不变。变。(不起作用的约束不起作用的约束)若不满足若不满足(起作用的约束起作用的约束),),则将新增的约束直接则将新增的约束直接映到最终表（增加一行一列映到最终表（增加一行一列（松驰变量（松驰变量新变量）新变量），继续求解），继续求解。(注意到这时新增的变量是基变注意到

29、这时新增的变量是基变量量).).53例例5 5 在例在例1 1中增加一个约束条件中增加一个约束条件3x3x1 1+2x+2x2 212,12,试分析最试分析最优解的变化。优解的变化。解解 因因3 37/2+27/2+23/2=27/23/2=27/21212，故将约束条件写成，故将约束条件写成3x3x1 1+2x+2x2 2+x+x6 6=12,=12,并取并取x x6 6为基变量，直接反映到最终表。为基变量，直接反映到最终表。Cj 2 1 0 0 0 0CBXB b x1 x2 x3 x4 x5 x60210X3x1 x2x67.53.51.512 0 0 1 5/4 -15/2 0 1 0

30、 0 1/4 -1/2 0 0 1 0 -1/4 3/2 0 3 2 0 0 0 1 Z 0 0 0 1/4 1/2 0 54注意把注意把a a4141=3 a=3 a4242=2=2 通过行变换化为通过行变换化为0 0，保持，保持x x1 1,x,x2 2为基变量。为基变量。Cj 2 1 0 0 0 3CBXB b x1 x2 x3 x4 x5 x60210X3x1 x2x615/27/23/2-3/2 0 0 1 5/4 -15/2 0 1 0 0 1/4 -1/2 0 0 1 0 -1/4 3/2 0 0 0 0 -1/4-3/2 1 Z 0 0 0 1/4 1/2 0 55用对偶法迭代

31、得最优解为用对偶法迭代得最优解为x1=4,x2=0,Z*=24=8 Cj 2 1 0 0 0 0CBXB b x1 x2 x3 x4 x5 x60210X3x1 x2x515401 0 0 1 5/2 0 -5 1 0 0 1/3 0 -1/3 0 1 0 -1/2 0 1 0 0 0 1/6 1 -2/3 Z8 0 0 0 1/6 0 1/3 56 2.5.5 增加一个变量的分析增加一个变量的分析 增加一个变量在实际问题中反映为增加一种新增加一个变量在实际问题中反映为增加一种新产品产品.1、特点：约束不等式的系数阵增加一列，目标、特点：约束不等式的系数阵增加一列，目标函数增加一项，约束不等式

32、不增加。函数增加一项，约束不等式不增加。2、分析步骤是：、分析步骤是：（1 1）在最优表中填上一列：在最优表中填上一列：P P/n+1n+1=B=B-1-1P Pn+1n+1 57例例6 6 在例在例1 1中增加一个变量中增加一个变量x x6 6,有有c c6 6=3,P=3,P6 6=(3,4,2)=(3,4,2)T T试试分析最优解的变化分析最优解的变化.58将其反映到最终表中将其反映到最终表中：Cj 2 1 0 0 0 3CBXB b x1 x2 x3 x4 x5 x6021X3x1 x27.53.51.5 0 0 1 5/4 -15/2 -7 1 0 0 1/4 -1/2 0 0 1 0 -1/4 3/2 2 Z 0 0 0 1/4 1/2 -1 59继续迭代得 Cj 2 1 0 0 0 3CBXB b x1 x2 x3 x4 x5 x6023X3x1 x65/47/23/4 0 7/2 1 3/8 -9/4 0 1 0 0 1/4 -1/2 0 0 1/2 0 -1/8 3/4 1 Z 0 1/2 0 1/8 5/4 0 602.6 运输问题及其解法 2.6.1 运输问题的数学模型 2.6.2 产销平衡问题的表上作业法 2.6.3产销不平衡问题的解法61