第二章对偶理论ppt课件.ppt

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

1、认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目第二章第二章 LP的对偶理论的对偶理论(dual theory)1 1 对偶问题的提出对偶问题的提出2 2 原问题与对偶问题原问题与对偶问题3 3 对偶问题的基本性质对偶问题的基本性质4 4 对偶问题的经济意义对偶问题的经济意义影子价格影子价格5 5 对偶单纯形法对偶单纯形法6 6 灵敏度分析灵敏度分析7 7 参数线性规划参数线性规划1认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 1 1 对偶问题的提出对

2、偶问题的提出一、对偶问题的提出一、对偶问题的提出在理论上和实践上，对偶理论都是在理论上和实践上，对偶理论都是LP中一个十中一个十分重要和有趣的概念。支持对偶理论的基本思想是，分重要和有趣的概念。支持对偶理论的基本思想是，每一个每一个LP问题都存在一个与其对偶的问题，原问问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶的并进行描述，组成一对互为对偶的LP问题。在求问题。在求出一个问题解的时候，也同时可以得到另一个问题出一个问题解的时候，也同时可以得到另一个问题的解。下面通过一个例子看一下对偶问题

3、的经济意的解。下面通过一个例子看一下对偶问题的经济意义。义。2认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目美佳公司计划制造甲乙两种产品。已知各美佳公司计划制造甲乙两种产品。已知各制造一件产品时分别占用设备制造一件产品时分别占用设备A,B的台时，的台时，每天可用于这两种产品的能力，各售出一每天可用于这两种产品的能力，各售出一件时的获利能力如下表。问该公司应制造件时的获利能力如下表。问该公司应制造两种产品各多少件，获取的利润最大？两种产品各多少件，获取的利润最大？项目项目甲甲乙乙每天可用能力每天可用能力设备设备A1517设备

4、设备B6224利润利润213认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 MAX Z=2X1+X2 满足条件：满足条件：X1+5X2 17 6X1+2X2 24 X10,X20列出线性规划模型为列出线性规划模型为：4认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目现从另一个角度提出问题：假定东方公司想把美佳公司现从另一个角度提出问题：假定东方公司想把美佳公司（的资源（的资源)收买过来，它至少应付出多大代价（底线），收买过来，它至少应付出多大代价（底线）

5、，才能使美佳公司愿意放弃生产活动，出让自己的才能使美佳公司愿意放弃生产活动，出让自己的资源资源？显然，该企业愿意出让的条件是，出让的价格不应低显然，该企业愿意出让的条件是，出让的价格不应低于同等数量资源由自己组织生产活动时获取的利润。于同等数量资源由自己组织生产活动时获取的利润。分析：设分析：设y1,y2分别表示单位时间（分别表示单位时间（h）设备）设备A、设备、设备B的出让代价，则从东方公司来看，希望用最小的代价把全的出让代价，则从东方公司来看，希望用最小的代价把全部资源收买过来，部资源收买过来，故有：故有：minw=17y1+24y2因生产一件甲产品需两种设备分别为因生产一件甲产品需两种设

6、备分别为1、6小时，盈利小时，盈利2元，生产一件乙产品需两种设备分别为元，生产一件乙产品需两种设备分别为5、1小时，盈利小时，盈利1元。元。从美佳公司来看，出让资源获得的利润应不少于自己组从美佳公司来看，出让资源获得的利润应不少于自己组织生产获得的利润。因此有：织生产获得的利润。因此有：y1+6y2 25y1+2y2 15认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 要使收买成功，双方的要求都必要使收买成功，双方的要求都必须满足，于是得到出让资源问题的线须满足，于是得到出让资源问题的线性规划数学模型：性规划数学模型：mi

7、n w=17 y1+24 y2 y1+6y2 2 5 y1+2 y2 1 y1 0,y2 0于是我们得到两个线性规划：于是我们得到两个线性规划：6认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目原问题：原问题：LP1 1:maxZ=2XmaxZ=2X1 1+X+X2 2 X X1 1 +5X+5X2 2 17 17 6X6X1 1+2X+2X2 2 24 24 X X1 1 0,X 0,X2 2 0 0对偶问题：对偶问题：LP2 2：minw=17y1+24y2y1+6y2 2 5y1+2y2 1y1 0,y2 0我们把我们

8、把LP2称为称为LP1的对偶问题；若把的对偶问题；若把LP2看成原问题，则看成原问题，则LP1就是就是LP2的对的对偶问题。偶问题。比较两者，看有什么规律？比较两者，看有什么规律？7认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1）目标函数的目标互为相反）目标函数的目标互为相反(max,min)；2）目标函数的系数是另一个约束条件右端的向）目标函数的系数是另一个约束条件右端的向量；量；3）约束系数矩阵是另一个的约束系数矩）约束系数矩阵是另一个的约束系数矩阵的转阵的转置；置；4）约束方程的个数与另一个的变量的个数相等；）约束

9、方程的个数与另一个的变量的个数相等；5）约束条件在一个问题中为）约束条件在一个问题中为“”，在另一个问，在另一个问题中为题中为“”。8认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目二、对偶问题的一般提法（对称形式下对偶问题的一般提二、对偶问题的一般提法（对称形式下对偶问题的一般提法）法）看书看书P41原问题：原问题：m种资源种资源bi(i=1m)生产生产n种产品种产品xj(j=1n)，获，获利分别为利分别为cj(j=1n)元，元，aij为工艺系数，则原问题为为工艺系数，则原问题为Maxz=cjxjaijxjbi(i=1m)

10、xj0(j=1n)对偶问题：设将上述资源出售定价为对偶问题：设将上述资源出售定价为yi（i=1m），使获），使获得收益不低于原企业生产产品出售获得的收益，则应满足得收益不低于原企业生产产品出售获得的收益，则应满足Minw=biyiaijyicj(j=1n)yi0(i=1m)9认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目三、三、LP的对偶问题也可以从数学的角度引出来的对偶问题也可以从数学的角度引出来（了解）（了解）检验数为检验数为 B B=CB B-CB BB-1B(1)N N=CN N-CB BB-1N(2)-Y=CB

11、BB-1(1)(2)合到一起，合到一起，检验数一般形式为检验数一般形式为：=C-CB BB-1A令令Y=CB BB-1，称为单纯形乘子称为单纯形乘子当所有当所有 j 0时，时，YA CY 0又又Z=CX=CB Bb=CB BB-1b=Yb=W,所以：所以：minw=Ybst.YA CY 010认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目从例子看到，原问题为求从例子看到，原问题为求max，对偶问题为求，对偶问题为求min，因为：，因为：（1）对偶问题的可行解（）对偶问题的可行解（Y=CB BB-1）满足原问题）满足原问题的

12、最优化条件（的最优化条件（0）；）；（2）因此对原问题来说，只有最优解（）因此对原问题来说，只有最优解（X=B-1b）才是其对偶问题的可行解。才是其对偶问题的可行解。（3）也即原问题的最优解目标函数值是它的对偶问也即原问题的最优解目标函数值是它的对偶问题可行解目标函数值最小的一个。题可行解目标函数值最小的一个。(注意对偶问题求注意对偶问题求min)(Z=CX=CB Bb=CB BB-1b=Yb=W)（4）由此可知，原问题目标函数的最大值对应于对由此可知，原问题目标函数的最大值对应于对偶问题的目标函数的最小值。偶问题的目标函数的最小值。CX Yb（具体见第三节基本性质）（具体见第三节基本性质）1

13、1认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目一、对偶关系（对称形式）一、对偶关系（对称形式）一、对偶关系（对称形式）一、对偶关系（对称形式）2 2 原问题与原问题与对偶问题对偶问题对偶问题对偶问题原问题原问题对偶问题对偶问题maxz=CXminw=Ybst.AX bst.YA CX 0 Y 0看书上表看书上表2.1，验证对应关系，验证对应关系对称性：对称性：LP的原问题与对偶问题之间存在对称关系，即的原问题与对偶问题之间存在对称关系，即LP对偶问题的对偶是原问题对偶问题的对偶是原问题结论：结论：LP对偶问题与原问题互为

14、对偶。对偶问题与原问题互为对偶。看例看例2，通过例子得出结论，通过例子得出结论第一步，化为对称形式下的原问题形式；第二步，根据对第一步，化为对称形式下的原问题形式；第二步，根据对应关系写出其对偶问题；第三步，做一变换，得到原问题应关系写出其对偶问题；第三步，做一变换，得到原问题。12认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目二、非对称形式原问题与对偶问题之间的关系二、非对称形式原问题与对偶问题之间的关系看例看例3，是一个最小化问题，是一个最小化问题第一步，化为对称形式下的对偶问题形式（第一步，化为对称形式下的对偶问题形

15、式（min，变，变量非负）；量非负）；第二步，引入对偶变量（根据原问题约束条件符号来设的）第二步，引入对偶变量（根据原问题约束条件符号来设的），根据对应关系写出其对偶问题；，根据对应关系写出其对偶问题；第三步，变换为一般形式。第三步，变换为一般形式。设原问题的三个约束条件的设原问题的三个约束条件的对偶变量分别为对偶变量分别为y1、y2、y3(每每一个约束条件对应一个对偶变量一个约束条件对应一个对偶变量)由此，对于非对称形式原问题与对偶问题之间的关系可用由此，对于非对称形式原问题与对偶问题之间的关系可用下表反映：下表反映：13认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国

16、家对扶贫工作高度重视，已经展开了“精准扶贫”项目原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数maxz 目标函数目标函数minw 资源系数资源系数价值系数价值系数 价值系数价值系数资源系数资源系数变量变量原变量个数为原变量个数为n个个第第j个个xj变量变量 0第第j个个xj变量变量 0,第第j个个xj变量无约束变量无约束行约束个数为行约束个数为n个个第第j个约束取个约束取 第第j个约束取个约束取 第第j个约束取个约束取=约束约束条件条件约束约束条件条件行约束个数为行约束个数为m个个第第i个约束取个约束取 第第i个约束取个约束取 第第i个约束取个

17、约束取=对偶变量对偶变量m个个第第i个变量个变量yi 0第第i个变量个变量yi 0第第i个变量个变量yi无约束无约束变量变量 约束条件系数矩阵约束条件系数矩阵A A14认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例：给出下列线性规划的对偶问题：例：给出下列线性规划的对偶问题：MAXZ=X1+2X2+X3X1+X2X3 2y1X1X2+X3=1y2st.2X1+X2+X3 2y3X1 0,X2 0,X3无约束无约束15认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精

18、准扶贫”项目例：给出下列线性规划的对偶问题：例：给出下列线性规划的对偶问题：MAXZ=X1+2X2+X3X1+X2X3 2y1X1X2+X3=1y2st.2X1+X2+X3 2y3X1 0,X2 0,X3无约束无约束其对偶问题为：其对偶问题为：minw=2y1+y2+2y3y1+y2+2y3 1X1st.y1-y2+y3 2X2-y1+y2+y3=1X3y1 0,y2无约束，无约束，y3 016认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例：给出下列线性规划的对偶问题：例：给出下列线性规划的对偶问题：minZ=2X1+8

19、X2-4X3X1+3X23X3 30y1-X1+5X2+4X3=80y2st.4X1+2X2-4X3 50y3X1 0,X2 0,X3无约束无约束17认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例：给出下列线性规划的对偶问题：例：给出下列线性规划的对偶问题：minZ=2X1+8X2-4X3X1+3X23X3 30y1-X1+5X2+4X3=80y2st.4X1+2X2-4X3 50y3X1 0,X2 0,X3无约束无约束其对偶问题为：其对偶问题为：MAXw=30y1+80y2+50y3y1-y2+4y3 2x1st.3y

20、1+5y2+2y3 8x2-3y1+4y2-4y3=-4x3y1 0,y2无约束，无约束，y3 018认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目l先相同，后相反；先相反，后相同先相同，后相反；先相反，后相同l最大化问题找其对偶问题，约束条件与其最大化问题找其对偶问题，约束条件与其对偶变量的符号对偶变量的符号相同相同，而其变量的符号与，而其变量的符号与其对应约束条件的符号其对应约束条件的符号相反相反；l最小化问题找其对偶问题，约束条件与其最小化问题找其对偶问题，约束条件与其对偶变量的符号对偶变量的符号相反相反，而其变量的

21、符号与，而其变量的符号与其对应约束条件的符号其对应约束条件的符号相同相同。19认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3 3 对偶问题的基本性质对偶问题的基本性质原问题原问题对偶问题对偶问题maxz=CXminw=Ybst.AX bst.YA CX 0Y 0可行解可行解XY本本节节讨讨论论先先假假定定原原LP与与对对偶偶问问题题为为对对称称形形式式的的线线性性规规划划问问题题，然然后后说说明明对对偶偶问问题题的的基基本本性性质在非对称形式（一般形式）时也适用。质在非对称形式（一般形式）时也适用。性性质质是是就就对对称

22、称形形式式提提出出的的，可可行行平平行行的的推推广广到到一一般般形形式式的的问问题题中中去去，只只不不过过叙叙述述上上也也要要有有相相应的变动。应的变动。20认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1、弱对偶性：、弱对偶性：CXYbX，Y是可行解是可行解（证明用到了上面两个约束条件）（证明用到了上面两个约束条件）性性质质含含义义：极极大大化化问问题题的的任任一一可可行行解解的的目目标标函函数数值值，不不大大于于对对偶偶问问题题的的任任一一可可行行解解的目标函数值。也即：的目标函数值。也即：原问题任一可行解的目标函数值

23、是其对偶原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标任一可行解的目标函数值是其原问题目标函数值的上界。函数值的上界。21认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目已知线性规划问题已知线性规划问题:maxZ=4x1+7x2+2x3s.t.应用对偶理论证明该问题最优解的目标应用对偶理论证明该问题最优解的目标函数值不大于函数值不大于25.22认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度

24、重视，已经展开了“精准扶贫”项目2、最优性：、最优性：当原问题与对偶问题均有当原问题与对偶问题均有可行解可行解X、Y，且当，且当CX=Yb时，时，则则X、Y分别是原问题与对偶问题的最优解。分别是原问题与对偶问题的最优解。（由性质（由性质1证明）证明）（隐含：两者都存在可行解，则均存（隐含：两者都存在可行解，则均存在最优解）在最优解）23认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目已知线性规划问题：已知线性规划问题：MAXZ=3x1+2x2-x1+2x243x1+2x214x1x23x1，x20（1）写出对偶问题；（）写出

25、对偶问题；（2）利用对偶）利用对偶问题性质证明原问题和对偶问题都存在问题性质证明原问题和对偶问题都存在最优解。最优解。24认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3、无界性：、无界性：如果原问题（对偶问题）有无界解，如果原问题（对偶问题）有无界解，则对偶问题（原问题）无可行解。则对偶问题（原问题）无可行解。即原问题有可行解且目标函数值无界（可达正无穷）即原问题有可行解且目标函数值无界（可达正无穷），则其对偶问题无可行解；反之对偶问题有可行解，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界（可达负无穷），则

26、其原问题无且目标函数值无界（可达负无穷），则其原问题无可行解。（性质可行解。（性质1，CXYb，YbCX）如果原问题无可行解时，对偶问题无可行解或具有如果原问题无可行解时，对偶问题无可行解或具有无界解无界解对偶问题无可行解时，原问题无可行解或具有无界对偶问题无可行解时，原问题无可行解或具有无界解解（原问题有可行解，对偶问题无可行解，则（原问题有可行解，对偶问题无可行解，则原问题原问题有无界解）有无界解）25认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目已知线性规划问题已知线性规划问题:maxZ=x1+x2s.t.试应用对偶

27、理论证明上述线性规划问题试应用对偶理论证明上述线性规划问题无最优解。（无界解属于无最优解）无最优解。（无界解属于无最优解）26认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目已知线性规划问题已知线性规划问题maxZ=x1-x2+x3x1-x34x1x2+2x33x1x2x30 试试应应用用对对偶偶理理论论证证明明上上述述线线性性规规划划问问题无最优解题无最优解.（无界解属于无最优解）（无界解属于无最优解）27认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目

28、4、强对偶性（对偶定理）：若原问题有最、强对偶性（对偶定理）：若原问题有最优解，则对偶问题也一定有最优解，且目优解，则对偶问题也一定有最优解，且目标函数值相等。标函数值相等。证明：证明：Z=CX=CBb=CBB-1b=Yb=W根据性质根据性质2，Y是对偶问题最优解是对偶问题最优解28认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目小结：小结：1、原问题有可行解原问题有可行解，则对偶问题：，则对偶问题：有可行解，则两者均具有最优解；有可行解，则两者均具有最优解；无可行解，则原问题具有无界解。无可行解，则原问题具有无界解。2、原

29、问题无可行解原问题无可行解，则对偶问题可以无，则对偶问题可以无可行解或者无界解。可行解或者无界解。3、原问题无界解，原问题无界解，对偶问题无可行解。对偶问题无可行解。（无界性）（无界性）4、原问题有最优解，原问题有最优解，对偶问题有最优解，对偶问题有最优解，且且CX=Yb。（。（对偶定理）对偶定理）29认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目5 5、互补松弛性：、互补松弛性：、互补松弛性：、互补松弛性：变量为变量为变量为变量为“0”0”时时时时，其对应约束条件为，其对应约束条件为，其对应约束条件为，其对应约束条件为“

30、=”“=”；约束条件为；约束条件为；约束条件为；约束条件为“”时，其对应对偶时，其对应对偶时，其对应对偶时，其对应对偶变量为变量为变量为变量为“0”“0”（线性规划问题的约束条件与对偶变量一一对应）（线性规划问题的约束条件与对偶变量一一对应）（线性规划问题的约束条件与对偶变量一一对应）（线性规划问题的约束条件与对偶变量一一对应）(一个一个一个一个问题的约束条件和另一个问题的变量对应，一个问题的变问题的约束条件和另一个问题的变量对应，一个问题的变问题的约束条件和另一个问题的变量对应，一个问题的变问题的约束条件和另一个问题的变量对应，一个问题的变量和另一个问题的约束条件对应量和另一个问题的约束条件

31、对应量和另一个问题的约束条件对应量和另一个问题的约束条件对应)已知线性规划问题已知线性规划问题minZ=8X1+6X2+3X3+6X4STX1+2X2+X433X1+X2+X3+X46X3+X42X1+X32Xj0j=1,2,3,4已知原问题最优解为：已知原问题最优解为：X=（1,1,2,0）T试利用对偶性质求对偶问题的最优解。试利用对偶性质求对偶问题的最优解。30认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例例:已知下列线性规划问题的对偶问已知下列线性规划问题的对偶问题的最优解为题的最优解为(6/5,1/5),求该线性

32、求该线性规划问题的最优解规划问题的最优解.MAXZ=X1+2X2+3X3+4X4X1+2X2+2X3+3X4 20Y1 2X1+X2+3X3+2X4 20Y2X1,X2,X3,X4031认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目解解:其对偶问题为其对偶问题为:MINW=20Y1+20Y2+5Y3Y1+2Y211)X12Y1+Y222)X22Y1+3Y2 33)X33Y1+2Y2 44)X4Y10,Y2 032认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫

33、”项目将解代入到对偶问题的四个约束条件可得将解代入到对偶问题的四个约束条件可得1*1.2+2*0.21;2*1.2+0.21;2*1.23*0.2=3;3*1.2+2*0.2=4那么由互补松驰性得，那么由互补松驰性得，x1=0;x2=0。再由。再由y1,y20得，原问题的两个约束条件均取等号，这得，原问题的两个约束条件均取等号，这样联立方程样联立方程从而从而:原问题的约束变为原问题的约束变为:2X3+3X4=203X3+2X4=20解此方程得解此方程得:X3=X4=4于于是是原原问问题题的的最最优优解解为为:(0,0,4,4)目目标标函函数数值值z=28.33认识到了贫困户贫困的根本原因，才能

34、开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目已知线性规划问题已知线性规划问题minW=2X1+3X2+5X3+2X4+3X5STX1+X2+2X3+X4+3X542X1X2+3X3+X4+X53Xj0j=1,2,3,4,5已已知知对对偶偶问问题题最最优优解解为为：Y1=4/5Y2=3/5Z=5试利用对偶性质求原问题的最优解。试利用对偶性质求原问题的最优解。34认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目解：由互补松弛定理可得方程：解：由互补松弛定理可得方程：3X1+X5=42X1+

35、X5=3解此方程组可得：解此方程组可得：X1=1，X5=1所以原问题的最优解是：所以原问题的最优解是：X=（1,0,0,0,1）TZ=5 35认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目.已知线性规划问题：已知线性规划问题：其最优解为其最优解为（a）求）求k的值；的值；（b）写出并求其对偶问题的最优解。）写出并求其对偶问题的最优解。36认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目解：先写出其对偶问题如下：解：先写出其对偶问题如下：由及互补松弛性质得

36、由及互补松弛性质得解得解得37认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目l小结：小结：l给出原问题的最优解，其不等于给出原问题的最优解，其不等于0的变量对应对的变量对应对偶问题的约束条件取偶问题的约束条件取“=”，代入原问题约束条，代入原问题约束条件，为件，为“”时，其对应对偶变量为时，其对应对偶变量为“0”；l给出对偶问题的最优解，其不等于给出对偶问题的最优解，其不等于0的变量对应的变量对应对原问题的约束条件取对原问题的约束条件取“=”，代入对偶问题约，代入对偶问题约束条件，为束条件，为“”时，其对应对偶变量为时，其

37、对应对偶变量为“0”；38认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 6、a、单纯形法迭代每一步同时，其检验数行的、单纯形法迭代每一步同时，其检验数行的相反数得到其对偶问题的一个基解（相反数得到其对偶问题的一个基解（不一定基可行不一定基可行解解）；）；b、松弛变量、剩余变量与变量的对应关系；、松弛变量、剩余变量与变量的对应关系；c、互相对应的变量在一个、互相对应的变量在一个LP中为基变量，在另一中为基变量，在另一个个LP中为非基变量；中为非基变量；d、Z=W。（这个定理在非对称形式下有所不同）（这个定理在非对称形式下有

38、所不同）39认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目w1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量原始问题的松弛变量原始问题的松弛变量xjwm+j=0wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于040认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度

39、重视，已经展开了“精准扶贫”项目目标函数值目标函数值原问题原问题可行解可行解非可行解非可行解对偶问题对偶问题可行解可行解最优最优ZZmax非可行解非可行解ZZmax-41认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目44 影子价格DP的经济解释上节性质上节性质6，在单纯形法的每步迭代中有目标函数，在单纯形法的每步迭代中有目标函数l对对偶偶变变量量yi的的意意义义代代表表对对一一个个单单位位第第i种种资资源的估价，称为源的估价，称为影子价格（影子价格（shadowprice）。42认识到了贫困户贫困的根本原因，才能开始对症下

40、药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1、影子价格不同于市场价格、影子价格不同于市场价格:b代表资源代表资源的拥有量的拥有量,yi代表在资源最优利用条件下代表在资源最优利用条件下对单位资源的估价，但不是市场价，而是对单位资源的估价，但不是市场价，而是对资源在生产中做出的贡献的估价，一般对资源在生产中做出的贡献的估价，一般称为影子价格。市场价格是已知的，而影称为影子价格。市场价格是已知的，而影子价格则与资源的利用情况有关，利用的子价格则与资源的利用情况有关，利用的好，影子价格就高，反之亦然。（用到不好，影子价格就高，反之亦然。（用到不同地方，价值不一样）同地方

41、，价值不一样）43认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2、影子价格是一种边际价格（对偶变量、影子价格是一种边际价格（对偶变量yi在经在经济上表示原问题第济上表示原问题第i种资源的种资源的边际价值）边际价值）。将。将z对对bi求偏导得求偏导得，这说明，这说明yi的值相当于在给定的值相当于在给定的生产条件下，的生产条件下，bi每增加一个单位的资源时，目每增加一个单位的资源时，目标函数标函数z的增量。的增量。对偶问题最优解对偶问题最优解y的经济意义：在其它条件不变的经济意义：在其它条件不变的情况下，的情况下，单位资源的

42、变化所引起的目标函数最单位资源的变化所引起的目标函数最优值的变化。优值的变化。在最优条件下在最优条件下,Z=Yb,目标函数是资源量的函数。目标函数是资源量的函数。44认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3、影子价格又是一种机会成本。当市场价大于影子价、影子价格又是一种机会成本。当市场价大于影子价格，卖出资源；当市场价小于影子价格，买入资源，组格，卖出资源；当市场价小于影子价格，买入资源，组织生产。织生产。4、互补松弛性的解释。、互补松弛性的解释。aijbi时，时，yi=0,当当yi0时，有时，有aij=bi，表明

43、生产过程中如果某种资源没有得到充分利，表明生产过程中如果某种资源没有得到充分利用，该种资源的影子价格为用，该种资源的影子价格为0;当该种影子价格不为零时，当该种影子价格不为零时，表示该种资源已消耗尽。表示该种资源已消耗尽。判断题：判断题：（1）若某种资源的影子价格等于）若某种资源的影子价格等于k，在其他条件不变的，在其他条件不变的情况下，当该种资源增加情况下，当该种资源增加5个单位时，相应的目标函数个单位时，相应的目标函数最大值将增加最大值将增加5k吗？（其它资源的拥有量还足够用时）吗？（其它资源的拥有量还足够用时）（2）已知）已知yi为某线性规划问题的对偶问题最优解中第为某线性规划问题的对偶

44、问题最优解中第i个分量，若个分量，若yi=0，能否肯定在有优生产计划中第，能否肯定在有优生产计划中第i种资源种资源一定有剩余。一定有剩余。45认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目5、单纯形法中检验数的经济意义。、单纯形法中检验数的经济意义。j=cj-ciaij=cj-aijyi cj aijyi cj aijyi 6、解的应用。利用影子价格可以有效控制和、解的应用。利用影子价格可以有效控制和使用资源，例如对紧缺资源的控制使用资源，例如对紧缺资源的控制(择优分配择优分配);作为同类企业经济效益的评估标准作为同类企业

45、经济效益的评估标准;通过帮通过帮助企业提高工艺和管理水平助企业提高工艺和管理水平,降低资源的耗费降低资源的耗费来提高资源的影子价格。来提高资源的影子价格。46认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目7、影子价格说明了不同资源对总的经济效益产生影子价格说明了不同资源对总的经济效益产生的影响，因此对企业经营管理提供一些有价值的信的影响，因此对企业经营管理提供一些有价值的信息：息：增加哪一种资源最有利。增加哪一种资源最有利。影子价格反映了不同的影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。局部或个体的增量

46、可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益；力，获得较大的整体效益；花多大代价增加该资源才最有利；花多大代价增加该资源才最有利；衡量资源使用是否合理；衡量资源使用是否合理；告诉经营者补给紧缺资源的数量，不要盲目大量告诉经营者补给紧缺资源的数量，不要盲目大量补给；补给；产品价格变动对资源的影响；产品价格变动对资源的影响；售价多少。售价多少。提示设备出租或原材料转让的基价。提示设备出租或原材料转让的基价。w 47认识

47、到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目l8、理解时注意几点：、理解时注意几点：l影子价格是针对约束条件而言的，约束条件可以为影子价格是针对约束条件而言的，约束条件可以为资源约束，也可以为产量约束，这时产品的产量不超过资源约束，也可以为产量约束，这时产品的产量不超过市场需求量，影子价格含义为：扩大销售对总产值的影市场需求量，影子价格含义为：扩大销售对总产值的影响。响。l若原问题的价值系数若原问题的价值系数Cj表示单位产值，则表示单位产值，则yi 称为称为影子价格；影子价格；影子价格；影子价格；若原问题的价值系数若原问题的

48、价值系数Cj表示单位利润，表示单位利润，则则yi 称为称为影子利润影子利润。l影子价格不是固定不变的，当约束条件、产品利润影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。等发生变化时，有可能使影子价格发生变化。l本章分析的是在最优解的最优基没有变化的前提本章分析的是在最优解的最优基没有变化的前提下进行的（其它资源够用）。即影子价格的经济含义，下进行的（其它资源够用）。即影子价格的经济含义，是指资源在一定范围内增加时的情况，当某种资源的增是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个加超过了这个“一定的范围一定的范围”时，总利润的增加量则不时，总

49、利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。在灵敏度分析一节中讨论。48对偶的经济解释对偶的经济解释1、原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题单位产品的利润（元单位产品的利润（元/件）件）产品产量（件）总利润（元总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源（剩余的资源（吨）吨）消耗的资源（吨）消耗的资源（吨）补充理解内容：补充理解内容：492、对偶问题对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资

50、源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的种资源的影子价格（影子价格（ShadowPrice）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润maxz=miny503、资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于051w1w2wm4、产品的机会成本