第第1章章 线性规划线性规划线性规划模型及单纯形法线性规划模型及单纯形法 （4 4学时）学时）对偶理论及灵敏度分析对偶理论及灵敏度分析 （2 2学时）学时）1第第3讲讲 对偶理论对偶理论对偶问题的提出对偶问题的提出线性规划的对偶理论线性规划的对偶理论线性规划的对偶理论线性规划的对偶理论对偶问题的经济解释对偶问题的经济解释-影子价格影子价格重重 点：对偶问题，对偶理论，点：对偶问题，对偶理论， 难难 点：对偶理论应用点：对偶理论应用基本要求：掌握对偶关系，理解对偶性质，基本要求：掌握对偶关系，理解对偶性质， 会求影子价格，会求影子价格，2n引例：经营策略问题。甲工厂有设备和原料引例：经营策略问题。甲工厂有设备和原料A A、B B 这些设这些设备和原料可用于备和原料可用于、两种产品的加工，每件产品加工两种产品的加工，每件产品加工所需机时数，原料所需机时数，原料A A、B B消耗量，每件产品的利润值及每消耗量，每件产品的利润值及每种设备的可利用的机时数如下表。现在乙厂和甲厂协商，种设备的可利用的机时数如下表。现在乙厂和甲厂协商，打算租用甲厂的设备打算租用甲厂的设备购买资源购买资源A和和B 。问甲厂采取哪种。问甲厂采取哪种经营策略，是自己生产产品还是出租设备、出让原材料经营策略，是自己生产产品还是出租设备、出让原材料？如果出租设备、出让原材料，在和乙厂协商时出租设？如果出租设备、出让原材料，在和乙厂协商时出租设备和出让原材料备和出让原材料A,BA,B的底价应是多少？的底价应是多少？对偶问题的提出对偶问题的提出 设设 备备原料原料A原料原料B 1 4 0 2 0 4 80台时 160kg 120kg23盈利盈利3自己生产：自己生产：原问题原问题引例分析：4l设设y y1 1 , ,y y2 2和和y y3 3分别表示出租单位设备台时分别表示出租单位设备台时的租金和出让单位原材料的租金和出让单位原材料A,BA,B的附加额的附加额=80y1+160y2+120y3出售资源对偶问题l显然商人希望总的收购价越小越好显然商人希望总的收购价越小越好l工厂希望出售资源后所得不应比生产产品所得少工厂希望出售资源后所得不应比生产产品所得少 目标函数目标函数 min5例例1它的对偶问题是：它的对偶问题是：YAYA Cmin = YbYbY Y0 0Y Y=（y1，y2，y3）61 1 原问题与对偶问题的关系原问题与对偶问题的关系( (对称形式对称形式) )线性规划的对偶理论线性规划的对偶理论78 原关系minw对偶关系maxzxy原问题与对偶问题的对称形式原问题与对偶问题的对称形式9 标准标准( (max,max, ) )型的对偶变换型的对偶变换n目标函数由目标函数由 max max 型变为型变为 min min 型型n对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量 yi，i=1,2,1,2,m mn对偶问题约束为对偶问题约束为 型，有型，有 n n 行行n原问题的价值系数原问题的价值系数 C C 变换为对偶问题的右端项变换为对偶问题的右端项n原问题的右端项原问题的右端项 b b 变换为对偶问题的价值系数变换为对偶问题的价值系数n原问题的技术系数矩阵原问题的技术系数矩阵 A A 转置后成为对偶问题的技术系转置后成为对偶问题的技术系数矩阵数矩阵n原问题与对偶问题互为对偶原问题与对偶问题互为对偶l对偶问题可能比原问题容易求解对偶问题可能比原问题容易求解l对偶问题还有很多理论和实际应用的意义对偶问题还有很多理论和实际应用的意义10原问题与对偶问题的结构关系原问题与对偶问题的结构关系n原问题与对偶问题中的目标函数的优化方向相反（前原问题与对偶问题中的目标函数的优化方向相反（前者为极大，后者为极小）者为极大，后者为极小）n原问题的每个约束条件对应于对偶问题的一个决策变原问题的每个约束条件对应于对偶问题的一个决策变量，且约束条件的资源系数（右端的常数项）为相应量，且约束条件的资源系数（右端的常数项）为相应决策变量的价值系数决策变量的价值系数n原问题的每个决策变量对应于对偶问题的一个约束条原问题的每个决策变量对应于对偶问题的一个约束条件，且决策变量的价值系数为相应约束条件的右端常件，且决策变量的价值系数为相应约束条件的右端常数项数项n对偶问题中的系数矩阵为原问题中的系数矩阵的转置对偶问题中的系数矩阵为原问题中的系数矩阵的转置n原问题约束条件中的小于等于符号对应于对偶问题中原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量取非负约束，原问题中决策的对偶问题非的对偶变量取非负约束，原问题中决策的对偶问题非负约束在对偶问题中体现为相应的约束条件取大于等负约束在对偶问题中体现为相应的约束条件取大于等于符号于符号11 非非标准标准型的对偶变换型的对偶变换12 对偶变换的规则对偶变换的规则13max=5y1+4y2+6y3y1 +2y2y1 + y3-3y1+2y2+y3y1- y2+ y3=23-5 1y1 0，y2 0,y3无约束无约束对偶问题例例3 3 写出线性规划问题的对偶问题写出线性规划问题的对偶问题minz=2x1+3x2-5x3+x4原问题原问题 x1+x2- 3x3 +x4 5 2x1+ 2x3 -x44 x2 + x3 +x4=6 x1 0 ,x2, x3 0, x4无约束14（1）对称性：对偶的对偶就是原始问题min =-CXs.t. -AX -bX 0max z=-Ybs.t. -YA -CY 0min =Ybs.t. YA C Y 0max z=CXs.t. AX bX 0对偶的定义对偶的定义对偶的定义对偶的定义2 对偶问题的基本性质对偶问题的基本性质 为了便于讨论，下面不妨总是假设为了便于讨论，下面不妨总是假设15(2) 弱对偶性: :若若 是原问题的可行解，是对偶是原问题的可行解，是对偶问题的可行解。则存在问题的可行解。则存在对偶问题对偶问题( (min)min)的任何可行解的任何可行解Y Y，其目标函数值总是其目标函数值总是不小于原问题不小于原问题( (max)max)任何可行解任何可行解X X的目标函数值的目标函数值16 弱弱对偶定理推论对偶定理推论原问题的任何可行解目标函数值是其对偶问题目标函原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限原问题目标函数值的上限n如果原如果原( (对偶对偶) )问题为无界解，则其对偶问题为无界解，则其对偶( (原原) )问题无问题无可行解可行解n如果原如果原( (对偶对偶) )问题有可行解，其对偶问题有可行解，其对偶( (原原) )问题无可问题无可行解，则原问题为无界解行解，则原问题为无界解n当原问题当原问题( (对偶问题对偶问题) )为无可行解为无可行解, ,其对偶问题其对偶问题( (原问原问题题) )或具有无界解或无可行解或具有无界解或无可行解17 (3)强对偶性证：由弱对偶定理推论证：由弱对偶定理推论1 1，结论是显然的。，结论是显然的。 若是原问题的可行解，是对偶问题可行解，当若是原问题的可行解，是对偶问题可行解，当 , , , , 分别是相应问题的最优解分别是相应问题的最优解是使目标函数取最小值的解，因此是最优解是使目标函数取最小值的解，因此是最优解 可行解是最优解的性质可行解是最优解的性质(最优性准则定理最优性准则定理)18 (4) (4) 对偶对偶定理定理 若原问题和对偶问题两者皆可行若原问题和对偶问题两者皆可行,则两者均则两者均有最优解有最优解,且此时目标函数值相等且此时目标函数值相等.第第1部分部分:证明两者均有最优解证明两者均有最优解证明分两部分证明分两部分由于原问题和对偶问题均可行由于原问题和对偶问题均可行,根据弱根据弱对偶性对偶性,可知两者均有界可知两者均有界,于是均有最于是均有最优解优解.19第第2部分部分:证明有相同的目标函数值证明有相同的目标函数值 设设 为原问题的最优解为原问题的最优解它所对应的基矩阵是它所对应的基矩阵是B B，则其检验数满足则其检验数满足 C C C CB BB B 1 1A A 0 0 因此有对偶问题目标函数值因此有对偶问题目标函数值而原问题最优解的目标函数值为而原问题最优解的目标函数值为显然显然 为对偶问题的可行解。为对偶问题的可行解。证毕故由最优解准则定理可知故由最优解准则定理可知 为对偶问题的最优解为对偶问题的最优解. .20对偶定理推论对偶定理推论n根据对偶定理第根据对偶定理第2 2部分的证明部分的证明, ,可以得出可以得出: :若互为若互为对偶的线性规划问题中的任一个有最优解对偶的线性规划问题中的任一个有最优解, ,则另则另一个也有最优解一个也有最优解, ,且目标函数值相等且目标函数值相等. . 综上所述综上所述, ,一对对偶问题的解必然是下列三种一对对偶问题的解必然是下列三种情况之一情况之一: :n原问题和对偶问题都有最优解原问题和对偶问题都有最优解n一个问题具有无界解一个问题具有无界解, ,另一个问题无可行解另一个问题无可行解n原问题和对偶问题都无可行解原问题和对偶问题都无可行解21 (5)互补松弛互补松弛定理定理证：由定理所设，可知有 设设 , , 分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解， 为为原问题的松弛变量的值，为对偶问题剩余变量的原问题的松弛变量的值，为对偶问题剩余变量的值。值。 , , 分别是原问题和对偶问题最优解的充分分别是原问题和对偶问题最优解的充分必要条件是必要条件是分别以分别以 左乘左乘(1)(1)式，以式，以 右乘右乘(2)(2)式后，两式相减，得式后，两式相减，得 根据最优解判别定理，根据最优解判别定理， 分别是原问题和对偶问题最优分别是原问题和对偶问题最优解。反之亦然。解。反之亦然。证毕。（1）（2）22max z=CXs.t.AX+XS=bX, XS 0min w=Ybs.t. AY-YS=CY, YS 0XYS=0YXS=0mn=YYSA-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数23原始问题和对偶问题最优解之间的互补松弛关系原始问题和对偶问题最优解之间的互补松弛关系maxz=CX s.t. AX+XS=b X, XS0min w=bYs.t. AY-YS=C Y, YS0maxz=CXs.t. AXb X 0min w=bYs.t. AYC Y0对偶引进松弛变量引进松弛变量XYS=0 YXS=0互补松弛关系互补松弛关系互补松弛关系互补松弛关系X，XsY，Ys24y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0，另一个一定等于0原始问题的变量原始问题的变量对偶问题的松弛变量对偶问题的松弛变量25(6)原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数行与对偶问题解的关系n原问题单纯形表检验数的相反数对应对偶原问题单纯形表检验数的相反数对应对偶问题的一个基解问题的一个基解. .显然显然, ,原问题最终单纯形原问题最终单纯形表检验数的相反数对应对偶问题的一个基表检验数的相反数对应对偶问题的一个基可行解可行解026证：标准化后的原问题和对偶问题的表达式为证：标准化后的原问题和对偶问题的表达式为：若若B B是是A A中的一个基，中的一个基，A=A=（B B，N N）27原问题解为原问题解为XB=B-1b ，N= CN-CBB-1N，Z=CBB-1b对偶问题的约束条件：对偶问题的约束条件：0检验数：检验数：B= CB-CBB-1B=0，N= CN-CBB-1N，S=CBB-1原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数行与对偶问题解的关系28结论：结论：v单纯形表中的检验数行和对偶问题的解单纯形表中的检验数行和对偶问题的解仅差一个符号vyi等于原问题的第等于原问题的第i个方程中的松弛变量所对应的检验个方程中的松弛变量所对应的检验 数的负数数的负数v单纯形法迭代时，原问题解为基可行解，相应的单纯形法迭代时，原问题解为基可行解，相应的检验数对应对偶问题的一个解，在原问题没有得到检验数对应对偶问题的一个解，在原问题没有得到最优解之前，对偶问题的解为非最优解之前，对偶问题的解为非可行解可行解基可行解基可行解非可行解基可行解目标函数对偶问题原问题无可行解无界解原问题为可行解时，原问题为可行解时，对偶问题不一定有可对偶问题不一定有可行解，当原问题为最行解，当原问题为最优解，对偶问题一定优解，对偶问题一定有最优解有最优解29例例4试用对偶理论证明该线试用对偶理论证明该线性规划问题无最优解。性规划问题无最优解。证：证：该问题存在可行解，该问题存在可行解，X=（0，0，0）；）；对偶问题为：对偶问题为：由第一个约束条件可知由第一个约束条件可知对偶问题无可行解，因对偶问题无可行解，因此，原问题有可行解，此，原问题有可行解，无最优解。无最优解。30例例5：试用对偶理论找出原问题的最优解。试用对偶理论找出原问题的最优解。解：解：原问题的对偶问题为：原问题的对偶问题为：已知其对偶问题的最优解为：已知其对偶问题的最优解为：31代入对偶问题的约束条件，代入对偶问题的约束条件，得得2,3,4式为严格不等式，由互补松弛性得式为严格不等式，由互补松弛性得因因原问题的约束条件应取等式为：原问题的约束条件应取等式为：求解后得到求解后得到原问题的最优解为原问题的最优解为:32原问题的最优解为原问题的最优解为:Z Z* *=C=CB BB B-1-1b=CXb=CX* *=Y=Y* *b b对偶问题的经济解释对偶问题的经济解释-影子价格影子价格z=CX=Cz=CX=CB BB B-1-1b b+ +N NX XN N =C=CB BB B-1-1b bN N= = C CN N-C-CB BB B-1-1N NY=CY=CB BB B-1-1为单纯形乘子为单纯形乘子当当b为变量的情况下为变量的情况下,当当bi发生变化发生变化:yi的经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化.yi是bi的一种估价,估价是有条件的替代方案.33n于是，当某个右端常数于是，当某个右端常数b bi i变为变为b bi i时，原问题的时，原问题的目标函数最优值变为：目标函数最优值变为：称对偶变量yi(i=1,2,m)表示原问题的第i个约束条件的影子价格.34影子价格在经济管理中的应用影子价格在经济管理中的应用(1)(1)影子价格能指示企业内部挖潜的方向影子价格能指示企业内部挖潜的方向. .注意:对于影子价格为零的资源企业的资源不一定有剩余.如果有剩余,企业应该充分利用剩余的资源,开辟新的生产途径,以增加企业的总收益.影子价格越高的资源,说明它对目标增益的影响越大,同时也表明这种资源越稀缺和贵重.企业的管理者要重视这种资源的管理,挖掘潜力,及时组织资源,由此可以给企业带来较大的收益.35n影子价格可以作为企业在接受外协加工任务时,对外协单位使用资源的收费标准,按照影子价格收费,保证了企业与外协单位双方平等互利的格局,可以促进双方合作.(2)影子价格指导企业间的分工与协作.36 产品产品资源资源影子价格影子价格( (万元万元) )钢材钢材煤煤机时机时 1 2 1 2 2 1 2 1 3 4 3 43/43/40 01/41/4单位利润单位利润( (万元万元) ) 1 3 1 3(3)影子价格在新产品开发决策中的应用ABB B单位产品的机会成本单位产品的机会成本=2=23/4+10+41/4=5/23/4+10+41/4=5/2两种新产品两种新产品A,BA,B的机会成本为的机会成本为: :A A单位产品的机会成本单位产品的机会成本=13/4+20+31/4=3/2=13/4+20+31/4=3/237由于投产由于投产A A产品所能提供的单位利润不大于投产的机产品所能提供的单位利润不大于投产的机会成本会成本, ,因此从经济上分析因此从经济上分析, ,A A产品不宜投产产品不宜投产; ;而而B B产品产品的机会成本小于该产品投产后所能提供的利润的机会成本小于该产品投产后所能提供的利润, ,因此因此投产投产BBBB确实为社会所欢迎确实为社会所欢迎, ,而在资源利用上与老产品而在资源利用上与老产品发生冲突发生冲突, ,工厂可以考虑用工厂可以考虑用B B产品去更换老产品产品去更换老产品, ,以获以获得更大的经济效益得更大的经济效益. .(4)影子价格在资源购销决策中的应用.当资源的市场价格低于影子价格,企业买进该资源,扩大生产,当资源的市场价格高于影子价格,企业应设法转让该资源.38n产品价格的变动会影响到影子价格的大小,从而对资源的稀缺性产生影响.例如设工厂现有钢材例如设工厂现有钢材100吨，其影子价格为吨，其影子价格为3/4，采用新工艺后，钢材可以节约采用新工艺后，钢材可以节约2%，则由此带来，则由此带来的经济收益为：的经济收益为： 1003/42%=3/2(万元万元)(5)利用影子价格分析现有产品价格变动对资源紧缺情况的影响.(6)利用影子价格分析工艺改变后对资源节约的收益利用影子价格分析工艺改变后对资源节约的收益39原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）40对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的影子价格（种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润 max z=min 41资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于042y1y2ym产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源43机会成本利润差额成本产品的差额成本（Reduced Cost）差额成本差额成本=机会成本机会成本 - 利润利润44互补松弛关系的经济解释互补松弛关系的经济解释在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于或小于利润）安排生产的产品机会成本等于或小于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产45灵敏度分析所要解决的问题：灵敏度分析所要解决的问题：系系数数在在什什么么范范围围内内变变化化，不不会会影影响响已已获获得得的的最优基最优基( (即最优解或最优解结构不变即最优解或最优解结构不变) )。如如果果系系数数的的变变化化超超过过以以上上范范围围，如如何何在在用用最最简简便便的的方方法法在在原原来来最最优优解解的的基基础础上上求求得得新新的的最优解最优解当当线线性性规规划划问问题题增增加加一一个个新新的的变变量量或或新新的的约约束束，如如何何在在原原来来最最优优解解的的基基础础上上获获得得新新的的最最优解。优解。灵敏度分析灵敏度分析(优化后分析优化后分析)46系数变化后最终表的几种情况系数变化后最终表的几种情况原问题原问题对偶问题对偶问题 结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解非可行解非可行解非可行解非可行解可行解可行解非可行解非可行解可行解可行解非可行解非可行解表中的解仍为最优解表中的解仍为最优解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解用对偶单纯形法继续迭代用对偶单纯形法继续迭代引入人工变量引入人工变量, ,编制新的单纯编制新的单纯形表形表, ,求最优求最优47最终表最优基最终表最优基B的逆的逆B-1的位置的位置n注意:最终表最优基B的逆B-1在最终单纯形表的位置与初始单纯形表中初始基所在的位置相对应B BI II IB B-1-148