《运筹学--对偶理论课件.ppt》由会员分享，可在线阅读，更多相关《运筹学--对偶理论课件.ppt（80页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 LP的对偶理论的对偶理论(dual theory)1 1 对偶问题的提出对偶问题的提出2 2 原问题与对偶问题原问题与对偶问题3 3 对偶问题的基本性质对偶问题的基本性质4 4 对偶问题的经济意义对偶问题的经济意义影子价格影子价格5 5 对偶单纯形法对偶单纯形法6 6 灵敏度分析灵敏度分析7 7 参数线性规划参数线性规划1 1 1 对偶问题的提出对偶问题的提出一、对偶问题的提出一、对偶问题的提出在理论上和实践上，对偶理论都是在理论上和实践上，对偶理论都是LP中一个十中一个十分重要和有趣的概念。支持对偶理论的基本思想是，分重要和有趣的概念。支持对偶理论的基本思想是，每一个每一个LP
2、问题都存在一个与其对偶的问题，原问问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶的并进行描述，组成一对互为对偶的LP问题。在求问题。在求出一个问题解的时候，也同时可以得到另一个问题出一个问题解的时候，也同时可以得到另一个问题的解。下面通过一个例子看一下对偶问题的经济意的解。下面通过一个例子看一下对偶问题的经济意义。义。2【例例1】：美佳公司计划制造甲乙两种产品。已知各制造美佳公司计划制造甲乙两种产品。已知各制造一件产品时分别占用设备一件产品时分别占用设备A,B的台时，每天可用于这两的台时，每
3、天可用于这两种产品的能力，各售出一件时的获利能力如下表。问该种产品的能力，各售出一件时的获利能力如下表。问该公司应制造两种产品各多少件，获取的利润最大？公司应制造两种产品各多少件，获取的利润最大？项目项目甲甲乙乙每天可用能力每天可用能力设备设备A1517设备设备B6224利润利润213 MAX Z=2X1+X2 满足条件：满足条件：X1+5X2 17 6X1+2X2 24 X10,X20列出线性规划模型为列出线性规划模型为：4现从另一个角度提出问题：假定东方公司想把美佳公司现从另一个角度提出问题：假定东方公司想把美佳公司（的资源（的资源)收买过来，它至少应付出多大代价（底线），收买过来，它至少
4、应付出多大代价（底线），才能使美佳公司愿意放弃生产活动，出让自己的才能使美佳公司愿意放弃生产活动，出让自己的资源资源？显然，该企业愿意出让的条件是，出让的价格不应低显然，该企业愿意出让的条件是，出让的价格不应低于同等数量资源由自己组织生产活动时获取的利润。于同等数量资源由自己组织生产活动时获取的利润。分析：设分析：设y1,y2分别表示单位时间（分别表示单位时间（h）设备）设备A、设备、设备B的出让代价，则从东方公司来看，希望用最小的代价把全的出让代价，则从东方公司来看，希望用最小的代价把全部资源收买过来，部资源收买过来，故有：故有：minw=17y1+24y2因生产一件甲产品需两种设备分别为因
5、生产一件甲产品需两种设备分别为1、6小时，盈利小时，盈利2元，生产一件乙产品需两种设备分别为元，生产一件乙产品需两种设备分别为5、2小时小时，盈利，盈利1元元。从。从美佳公司来看，出让资源获得的利润应不美佳公司来看，出让资源获得的利润应不少于自己少于自己组织组织生产获得的利润。因此有：生产获得的利润。因此有：y1+6y2 25y1+2y2 15 要使收买成功，双方的要求都必须满足，要使收买成功，双方的要求都必须满足，要使收买成功，双方的要求都必须满足，要使收买成功，双方的要求都必须满足，于是得到出于是得到出于是得到出于是得到出让资源问题的线性规划数学模型：让资源问题的线性规划数学模型：让资源问
6、题的线性规划数学模型：让资源问题的线性规划数学模型：min 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我们把我们把LP2称为称为LP1的对偶问题；若把的对偶问题；若把LP
7、2看成看成原问题，则原问题，则LP1就是就是LP2的对偶问题。的对偶问题。比较两者，看有什么规律？比较两者，看有什么规律？71）目标函数的目标互为相反）目标函数的目标互为相反(max,min)；2）目标函数的系数是另一个约束条件右端的）目标函数的系数是另一个约束条件右端的向量；向量；3）约束系数矩阵是另一个的约束系数矩）约束系数矩阵是另一个的约束系数矩阵的阵的转置；转置；4）约束方程的个数与另一个的变量的个数相）约束方程的个数与另一个的变量的个数相等；等；5）约束条件在一个问题中为）约束条件在一个问题中为“”，在另一个，在另一个问题中为问题中为“”。8二、对偶问题的一般提法（对称形式下对偶问题
8、的二、对偶问题的一般提法（对称形式下对偶问题的一般提法）一般提法）看书看书P41原问题：原问题：m种资源种资源bi(i=1m)生产生产n种产品种产品xj(j=1n)，获，获利分别为利分别为cj(j=1n)元，元，aij为工艺系数，则原问题为为工艺系数，则原问题为Maxz=cjxjaijxjbi(i=1m)xj0(j=1n)对偶问题：设将上述资源出售定价为对偶问题：设将上述资源出售定价为yi（i=1m），使获），使获得收益不低于原企业生产产品出售获得的收益，则应满足得收益不低于原企业生产产品出售获得的收益，则应满足Minw=biyiaijyicj(j=1n)yi0(i=1m)9三、三、LP的对偶
9、问题也可以从数学的角度引出来的对偶问题也可以从数学的角度引出来（了解）（了解）检验数为检验数为 B B=CB B-CB BB-1B(1)N N=CN N-CB BB-1N(2)-Y=-CB 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）对偶问题的可行
10、解（）对偶问题的可行解（Y=CB BB-1）满足原问题的最优）满足原问题的最优化条件（化条件（0）；）；（2）因此对原问题来说，只有最优解（）因此对原问题来说，只有最优解（X=B-1b）才是）才是其对偶问题的可行解。其对偶问题的可行解。（3）也即原问题的最优解也即原问题的最优解目标函数值目标函数值是它的对偶问题可是它的对偶问题可行解目标函数值最小的一个。行解目标函数值最小的一个。(注意对偶问题求注意对偶问题求min)(Z=CX=CB Bb=CB BB-1b=Yb=W)（4）由此可知，原问题目标函数的最大值对应于对偶问由此可知，原问题目标函数的最大值对应于对偶问题的目标函数的最小值。题的目标函数
11、的最小值。（具体见第三节基本性质）（具体见第三节基本性质）11一、对偶关系（一、对偶关系（一、对偶关系（一、对偶关系（对称对称形式形式）2 2 原问题与原问题与对偶问题对偶问题对偶问题对偶问题原问题原问题对偶问题对偶问题maxz=CXminw=Ybst.AX bst.YA CX 0 Y 01、看书看书上表上表2.1，验证，验证对应关系对应关系2、看教材例看教材例1。写出最大化问题的对偶问题。写出最大化问题的对偶问题3、对称性对称性：LP的原问题与对偶问题的原问题与对偶问题之间存在之间存在对称对称关系，关系，即即LP对偶问题的对偶是对偶问题的对偶是原问题。原问题。看看例例2，通过例子得出结论，通
12、过例子得出结论第一步，化为对称形式下的原问题形式；第二步，根据对第一步，化为对称形式下的原问题形式；第二步，根据对应关系写出其对偶问题；第三步，做一变换，得到原问题应关系写出其对偶问题；第三步，做一变换，得到原问题结论：结论：LP对偶问题与原问题互为对偶。对偶问题与原问题互为对偶。12二、非对称形式原问题与对偶问题之间的关系二、非对称形式原问题与对偶问题之间的关系看看例例3，是一个最小化问题，是一个最小化问题第一步，化为对称形式下的对偶问题形式（第一步，化为对称形式下的对偶问题形式（min，变量，变量非负）；非负）；第二步，引入对偶变量（根据原问题约束条件第二步，引入对偶变量（根据原问题约束条
13、件符号来符号来设），设），根据对应关系写出其对偶问题；根据对应关系写出其对偶问题；第三步，变换为一般形式。第三步，变换为一般形式。设原问题的三个约束条件的设原问题的三个约束条件的对偶变量分别为对偶变量分别为y1、y2、y3(每一个约束条件对应一个对偶变量每一个约束条件对应一个对偶变量)由此由此，对于非对称形式原问题与对偶问题之间，对于非对称形式原问题与对偶问题之间的关的关系可用系可用下表反映：下表反映：13原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数maxz 目标函数目标函数minw 资源系数资源系数价值系数价值系数 价值系数价值系数资源系数
14、资源系数变量变量原变量个数为原变量个数为n个个第第j个个xj变量变量 0第第j个个xj变量变量 0,第第j个个xj变量无约束变量无约束行约束个数为行约束个数为n个个第第j个约束取个约束取 第第j个约束取个约束取 第第j个约束取个约束取=约束约束条件条件约束约束条件条件行约束个数为行约束个数为m个个第第i个约束取个约束取 第第i个约束取个约束取 第第i个约束取个约束取=对偶变量对偶变量m个个第第i个变量个变量yi 0第第i个变量个变量yi 0第第i个变量个变量yi无约束无约束变量变量 约束条件系数矩阵约束条件系数矩阵A A14【例例2】：给出下列线性规划的对偶问题：给出下列线性规划的对偶问题：M
15、AXZ=X1+2X2+X3X1+X2X3 2y1X1X2+X3=1y2st.2X1+X2+X3 2y3X1 0,X2 0,X3无约束无约束15【例例2】：给出下列线性规划的对偶问题：给出下列线性规划的对偶问题：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【例例3】：给出下列线性规划的对偶问题：给出下列线性规划的对偶问题：
16、minZ=2X1+8X2-4X3X1+3X23X3 30y1-X1+5X2+4X3=80y2st.4X1+2X2-4X3 50y3X1 0,X2 0,X3无约束无约束17【例例3】：给出下列线性规划的对偶问题：给出下列线性规划的对偶问题：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.3y1+5y2+2y3 8x2-3y1+4y2-4y3=-4x3y1 0,y2无约束，无约束，y3
17、 018l先相同，后相反；先相反，后相同先相同，后相反；先相反，后相同l最大化问题找其对偶问题，约束条件与其最大化问题找其对偶问题，约束条件与其对偶变量的符号对偶变量的符号相同相同，而其变量的符号与，而其变量的符号与其对应约束条件的符号其对应约束条件的符号相反相反；l最小化问题找其对偶问题，约束条件与其最小化问题找其对偶问题，约束条件与其对偶变量的符号对偶变量的符号相反相反，而其变量的符号与，而其变量的符号与其对应约束条件的符号其对应约束条件的符号相同相同。193 3 对偶问题的基本性质对偶问题的基本性质原问题原问题对偶问题对偶问题maxz=CXminw=Ybst.AX bst.YA CX 0
18、Y 0可行解可行解XY本节讨论先假定原本节讨论先假定原LP与对偶问题为对称形式的与对偶问题为对称形式的LP问问题，然后说明对偶问题的基本性质在非对称形式（一般形题，然后说明对偶问题的基本性质在非对称形式（一般形式）时也适用。式）时也适用。性质是就对称形式提出的，可行平行的推广到一般性质是就对称形式提出的，可行平行的推广到一般性质是就对称形式提出的，可行平行的推广到一般性质是就对称形式提出的，可行平行的推广到一般形式的问题中去，只不过叙述上也要有相应的变动。形式的问题中去，只不过叙述上也要有相应的变动。形式的问题中去，只不过叙述上也要有相应的变动。形式的问题中去，只不过叙述上也要有相应的变动。2
19、01、弱对偶性：、弱对偶性：CXYbX，Y是可行解是可行解（证明用到了上面两个约束条件）（证明用到了上面两个约束条件）性性质质含含义义：极极大大化化问问题题的的任任一一可可行行解解的的目目标标函函数数值值，不不大大于对偶问题的任一可行解的目标函数于对偶问题的任一可行解的目标函数值。值。也即：也即：原原问题任一可行解的目标函数值是其对偶问题目标问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的是其原问题目标函数值的上界。上界。【例例4】已知线性规划问题已知线性规划问题:maxZ=4x
20、1+7x2+2x3s.t.应用对偶理论证明该问题最优解的目标函数值不大于应用对偶理论证明该问题最优解的目标函数值不大于25.212、最优性：、最优性：当原问题与对偶问题均有可行解当原问题与对偶问题均有可行解X、Y，且且当当CX=Yb时，时，则则X、Y分别是原问题与对偶问题的分别是原问题与对偶问题的最优解。（由性质最优解。（由性质1证明）证明）（隐含：两者都存在可行解，则均存在（隐含：两者都存在可行解，则均存在最优解）最优解）【例例5】已知线性规划问题：已知线性规划问题：MAXZ=3x1+2x2-x1+2x243x1+2x214x1x23x1，x20（1）写出对偶问题；（）写出对偶问题；（2）利
21、用对偶问题性质证明原问）利用对偶问题性质证明原问题和对偶问题都存在最优解。题和对偶问题都存在最优解。223、无界性：、无界性：如果原问题（对偶问题）有无界解，则对偶如果原问题（对偶问题）有无界解，则对偶问题（原问题）无可行解。问题（原问题）无可行解。即即原问题有可行解且目标函数值无界（可达正无穷），原问题有可行解且目标函数值无界（可达正无穷），则其对偶问题无可行解；反之对偶问题有可行解且目标函则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界（可达负无穷），则其原问题无可行解。（性质数值无界（可达负无穷），则其原问题无可行解。（性质1，CXYb，YbCX）因此，因此，如果如果原问题无可
22、行解时，对偶问题无可行解或具有原问题无可行解时，对偶问题无可行解或具有无界解无界解对偶问题无可行解时，原问题无可行解或具有无界解对偶问题无可行解时，原问题无可行解或具有无界解（原问题有可行解，对偶问题无可行解，则（原问题有可行解，对偶问题无可行解，则原问题原问题有无界有无界解）解）23【例例6】已知已知线性规划问题线性规划问题maxZ=x1-x2+x3x1-x34x1x2+2x33x1x2x30 试试应应用用对对偶偶理理论论证证明明上上述述线线性性规规划划问问题题无无最最优优解解.（无界解属于无最优解）（无界解属于无最优解）244、强对偶性（对偶定理）：、强对偶性（对偶定理）：若原问题有最若原
23、问题有最优解，则对偶问题也一定有最优解，且目优解，则对偶问题也一定有最优解，且目标函数值相等。标函数值相等。证明：证明：Z=CX=CBb=CBB-1b=Yb=W根据性质根据性质2，Y是对偶问题最优解是对偶问题最优解25小结：小结：1、原问题有可行解原问题有可行解，则对偶问题：，则对偶问题：有可行解，则两者均具有最优解；有可行解，则两者均具有最优解；无可行解，则原问题具有无界解。无可行解，则原问题具有无界解。2、原问题无可行解原问题无可行解，则对偶问题可以无可行解或，则对偶问题可以无可行解或者无界解。者无界解。3、原问题无界解，原问题无界解，对偶问题无可行解。对偶问题无可行解。（无界性）（无界性
24、）4、原问题有最优解，原问题有最优解，对偶问题有最优解，且对偶问题有最优解，且CX=Yb。（对偶定理）对偶定理）265 5、互补松弛性：、互补松弛性：、互补松弛性：、互补松弛性：变量为变量为变量为变量为“0”0”时时时时，其对应约束条件为，其对应约束条件为，其对应约束条件为，其对应约束条件为“=”=”；约束条件为；约束条件为；约束条件为；约束条件为“”时，其对应对偶时，其对应对偶时，其对应对偶时，其对应对偶变量为变量为变量为变量为“0”0”（线性规划问题的约束条件与对偶变量一一对应）（线性规划问题的约束条件与对偶变量一一对应）（线性规划问题的约束条件与对偶变量一一对应）（线性规划问题的约束条件
25、与对偶变量一一对应）(一个一个一个一个问题的约束条件和另一个问题的变量对应，一个问题的变问题的约束条件和另一个问题的变量对应，一个问题的变问题的约束条件和另一个问题的变量对应，一个问题的变问题的约束条件和另一个问题的变量对应，一个问题的变量和另一个问题的约束条件对应量和另一个问题的约束条件对应量和另一个问题的约束条件对应量和另一个问题的约束条件对应)【例例7】已知已知线性规划问题线性规划问题minZ=8X1+6X2+3X3+6X4STX1+2X2+X433X1+X2+X3+X46X3+X42X1+X32Xj0j=1,2,3,4已知原问题最优解为：已知原问题最优解为：X=（1,1,2,0）T试利
26、用对偶性质求对偶问题的最优解。试利用对偶性质求对偶问题的最优解。27【例例8】:已知下列线性规划问题的对偶问题的已知下列线性规划问题的对偶问题的最优解为最优解为(6/5,1/5),求该线性规划问题的最求该线性规划问题的最优解优解.MAXZ=X1+2X2+3X3+4X4X1+2X2+2X3+3X4 20Y1 2X1+X2+3X3+2X4 20Y2X1,X2,X3,X4028解解:其对偶问题为其对偶问题为:MINW=20Y1+20Y2+5Y3Y1+2Y211)X12Y1+Y222)X22Y1+3Y2 33)X33Y1+2Y2 44)X4Y10,Y2 029将解代入到对偶问题的四个约束条件可得将解代
27、入到对偶问题的四个约束条件可得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.30【例例9】已知已知线性规划问题线性规划问题minW=2X1+3X2+5X3+2X4
28、+3X5STX1+X2+2X3+X4+3X542X1X2+3X3+X4+X53Xj0j=1,2,3,4,5已知对偶问题最优解为：已知对偶问题最优解为：Y1=4/5Y2=3/5Z=5试利用对偶性质求原问题的最优解。试利用对偶性质求原问题的最优解。31解：由互补松弛定理可得方程：解：由互补松弛定理可得方程：3X1+X5=42X1+X5=3解此方程组可得：解此方程组可得：X1=1，X5=1所以原问题的最优解是：所以原问题的最优解是：X=（1,0,0,0,1）TZ=5 32.【例例10】已知已知线性规划问题：线性规划问题：其其最优解为最优解为（a）求）求k的值；的值；（b）写出并求其对偶问题的最优解。
29、）写出并求其对偶问题的最优解。33解：先写出其对偶问题如下：解：先写出其对偶问题如下：由及互补松弛性质得由及互补松弛性质得解得解得34l小结：小结：l给出原问题的最优解，其不等于给出原问题的最优解，其不等于0的变量对应对的变量对应对偶问题的约束条件取偶问题的约束条件取“=”，代入原问题约束条，代入原问题约束条件，为件，为“”时，其对应对偶变量为时，其对应对偶变量为“0”；l给出对偶问题的最优解，其不等于给出对偶问题的最优解，其不等于0的变量对应的变量对应对原问题的约束条件取对原问题的约束条件取“=”，代入对偶问题约，代入对偶问题约束条件，为束条件，为“”时，其对应对偶变量为时，其对应对偶变量为
30、“0”；35 6、a、单纯形法迭代每一步同时，其检验数行的、单纯形法迭代每一步同时，其检验数行的相反数得到其对偶问题的一个基解（相反数得到其对偶问题的一个基解（不一定基可行不一定基可行解解）；）；b、松弛变量、剩余变量与变量的对应关系；、松弛变量、剩余变量与变量的对应关系；c、互相对应的变量在一个、互相对应的变量在一个LP中为基变量，在另一中为基变量，在另一个个LP中为非基变量；中为非基变量；d、Z=W。（这个定理在非对称形式下有所不同）（这个定理在非对称形式下有所不同）36w1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的
31、变量对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量原始问题的松弛变量原始问题的松弛变量xjwm+j=0wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于037目标函数值目标函数值原问题原问题可行解可行解非可行解非可行解对偶问题对偶问题可行解可行解最优最优ZZmax非可行解非可行解ZZmax-3844 影子价格DP的经济解释上节性质上节性质6，在单纯形法的每步迭代中有目标函数，在单纯形法的每步迭代中有目标函数l对对偶偶变变量量yi的的意意义义代代表表对对一一个个单单位位第第i种种资资源的估价
32、，称为源的估价，称为影子价格（影子价格（shadowprice）。391、影子价格不同于市场价格、影子价格不同于市场价格:b代表资源代表资源的拥有量的拥有量,yi代表在资源最优利用条件下对代表在资源最优利用条件下对单位资源的估价，但不是市场价，而是单位资源的估价，但不是市场价，而是对对资源在生产中做出的贡献的估价资源在生产中做出的贡献的估价，一般称，一般称为影子价格。市场价格是已知的，而影子为影子价格。市场价格是已知的，而影子价格则与资源的利用情况有关，利用的好，价格则与资源的利用情况有关，利用的好，影子价格就高，反之亦然。（用到不同地影子价格就高，反之亦然。（用到不同地方，价值不一样）方，价
33、值不一样）402、影子价格是一种边际价格影子价格是一种边际价格（对偶变量（对偶变量yi在经在经济上表示原问题第济上表示原问题第i种资源的种资源的边际边际价值）价值）。将将z对对bi求偏导得求偏导得，这说明，这说明yi的值相当于在给定的值相当于在给定的生产条件下，的生产条件下，bi每增加一个单位的资源时，目每增加一个单位的资源时，目标函数标函数z的增量。的增量。对偶问题最优解对偶问题最优解y的经济意义：在其它条件不变的经济意义：在其它条件不变的情况下，的情况下，单位资源的变化所引起的目标函数最单位资源的变化所引起的目标函数最优值的变化。优值的变化。在最优条件下在最优条件下,Z=Yb,目标函数是资
34、源量的函数。目标函数是资源量的函数。413、影子价格又是一种机会成本。、影子价格又是一种机会成本。当市场价大于影子价当市场价大于影子价格，卖出资源；当市场价小于影子价格，买入资源，组格，卖出资源；当市场价小于影子价格，买入资源，组织生产。织生产。4、互补松弛性的解释。、互补松弛性的解释。aij bi时，时，yi=0,当当yi 0时，有时，有aij=bi，表明生产过程中如果某种资源没有得到充分利，表明生产过程中如果某种资源没有得到充分利用，该种资源的影子价格为用，该种资源的影子价格为0;当该种影子价格不为零时，当该种影子价格不为零时，表示该种资源已消耗尽。表示该种资源已消耗尽。判断题：判断题：（
35、1）若某种资源的影子价格等于）若某种资源的影子价格等于k，在其他条件不变的，在其他条件不变的情况下，当该种资源增加情况下，当该种资源增加5个单位时，相应的目标函数个单位时，相应的目标函数最大值将增加最大值将增加5k吗？（其它资源的拥有量还足够用时）吗？（其它资源的拥有量还足够用时）（2）已知）已知yi为某线性规划问题的对偶问题最优解中第为某线性规划问题的对偶问题最优解中第i个分量，若个分量，若yi=0，能否肯定在有优生产计划中第，能否肯定在有优生产计划中第i种资源种资源一定有剩余。一定有剩余。425、单纯形法中检验数的经济意义。、单纯形法中检验数的经济意义。j=cj-ciaij=cj-aijy
36、i cj aijyi cj aijyi 6、解的应用。、解的应用。利用影子价格可以有效控制和使用利用影子价格可以有效控制和使用资源，例如对紧缺资源的控制资源，例如对紧缺资源的控制(择优分配择优分配);作为同类作为同类企业经济效益的评估标准企业经济效益的评估标准;通过帮助企业提高工艺通过帮助企业提高工艺和管理水平和管理水平,降低资源的耗费来提高资源降低资源的耗费来提高资源的影子价的影子价格格;确定内部结算价格；确定上交的利润额。确定内部结算价格；确定上交的利润额。437、影子价格说明了不同资源对总的经济效益产生的影响，、影子价格说明了不同资源对总的经济效益产生的影响，因此对企业经营管理提供一些有
37、价值的信息：因此对企业经营管理提供一些有价值的信息：增加哪一种资源最有利。影子价格反映了不同的局部或增加哪一种资源最有利。影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益；手。这样可以用较少的局部努力，获得较大的整体效益；花多大代价增加该资源才最有利；花多大代价增加该资源才最有利；衡量资源使用是否合理；衡量资源使用是否合理；告诉经营者补给紧缺资源的数量，不要盲目大量补给；
38、告诉经营者补给紧缺资源的数量，不要盲目大量补给；产品价格变动对资源的影响；产品价格变动对资源的影响；售价多少。提示设备出租或原材料转让的基价。售价多少。提示设备出租或原材料转让的基价。448、理解时注意几点：、理解时注意几点：影子价格是影子价格是针对约束条件针对约束条件而言的，约束条件可以为资源而言的，约束条件可以为资源约束，也可以为产量约束，这时产品的产量不超过市场约束，也可以为产量约束，这时产品的产量不超过市场需求量，影子价格含义为：扩大销售对总产值的影响。需求量，影子价格含义为：扩大销售对总产值的影响。若原问题的价值系数若原问题的价值系数Cj表示单位产值，则表示单位产值，则yi 称为称为
39、影子影子影子影子价格；价格；价格；价格；若原问题的价值系数若原问题的价值系数Cj表示单位利润，则表示单位利润，则yi 称为称为影子利润影子利润影子利润影子利润。影子价格不是固定不变的，当约束条件、产品利润等影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生发生变化时，有可能使影子价格发生变化。变化。本节分析本节分析的是在最优解的最优基没有变化的前提下进的是在最优解的最优基没有变化的前提下进行的（行的（其它资源够用其它资源够用）。即影子价格的经济含义，是指）。即影子价格的经济含义，是指资源在资源在一定范围内增加时一定范围内增加时的情况，当某种资源的增加超的情况，当某种
40、资源的增加超过了这个过了这个“一定的范围一定的范围”时，总利润的增加量则不是按时，总利润的增加量则不是按照影子价格给出的数值线性地增加照影子价格给出的数值线性地增加。更进一步分析结合。更进一步分析结合灵敏度分析来讨论。灵敏度分析来讨论。注意：影子价格的重点是对它的理解和在实践中的应用。注意：影子价格的重点是对它的理解和在实践中的应用。451、原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题单位产品的利润（单位产品的利润（元元/件）件）产品产量（件）总利润（元总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/件）件）剩余的资源（剩余的资源（
41、吨）吨）消耗的资源（吨）消耗的资源（吨）补充理解内容补充理解内容：对偶的经济解释对偶的经济解释462、对偶问题对偶问题资源限量（吨）资源限量（吨）资源价格（元资源价格（元/吨）吨）总利润（元）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的种资源的影子价格（影子价格（ShadowPrice）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润maxz=miny473、资源影子价格的性质资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小
42、，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于048w1w2wm4、产品的机会成本、产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源49机会成本机会成本利润利润差额成本差额成本5、产品的差额成本（、产品的差额成本（ReducedCost）差额成本差额成本=机会成本机会成本-利润利润506、互补松
43、弛关系的经济解释、互补松弛关系的经济解释在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产51 5 5 对偶单纯形法对偶单纯形法从从DLP的性质和前面的例子的性质和前面的例子我们知道：在我们知道：在原原问题的最优单纯形表中，将松弛变量的检验数的问题的最优单纯形表中，将松弛变量的检验数的相反数代入相反数代入DLP的目标函数，可发现的目标函数，
44、可发现:1)两个函数值相等，进而发现两个函数值相等，进而发现:2)检验数的相反数是检验数的相反数是DLP的最优解的最优解.也也就就是是在在一一个个最最优优单单纯纯形形表表中中可可以以同同时时得得到到原原问题和问题和DLP的最优解。的最优解。52 我们再进一步分析单纯形法：我们再进一步分析单纯形法：单单纯纯形形法法实实质质上上是是从从原原LP为为可可行行解解而而DLP为为不不可可行行解解向向DLP为为可可行行解解转转化化，那那么么我我们们可可否否从从DLP为为可可行行解解，原原LP为为不不可可行行解解向向原原LP为为可可行行解解转转化化呢呢？于于是是我我们们就就得得到到一一个个新新的的方方法法：
45、对对偶偶单纯形法。单纯形法。对对偶偶单单纯纯形形法法实实质质是是单单纯纯形形法法应应用用于于对对偶偶问问题的计算。题的计算。对对偶偶单单纯纯形形法法基基本本思思路路：允允许许b列列出出现现负负数数，而而保保持持所所有有的的检检验验数数全全都都非非正正的的情情况况下下（对对偶偶问问题题为为可可行行解解），进进行行换换基基迭迭代代，使使b列列全全化化成成非非负负数数（原原问问题题为为可可行行解解），而而检检验验数数保保持持全全非非正正，从而得到原问题的最优解。从而得到原问题的最优解。53步骤：步骤：1、允许、允许b列出现负数的情况下，填初始单纯形列出现负数的情况下，填初始单纯形表，保持检验数行全非
46、正。表，保持检验数行全非正。2、如果、如果b列出现某个或某几个负数，则进行换基列出现某个或某几个负数，则进行换基迭代：迭代：1）先定出基变量：先定出基变量：b列中列中负数绝对值最大负数绝对值最大的对应的变量的对应的变量（Xr）；2）次定入基变量：用检验数行除以第次定入基变量：用检验数行除以第r行对应的行对应的负系数取比值最小者负系数取比值最小者对应的变量（对应的变量（Xs）为入基变量）为入基变量;3）以）以ars为主元素做行初等变换：将为主元素做行初等变换：将ars化为化为1，所在列，所在列，其他元素化为其他元素化为0，得到新的系数矩阵，填新的单纯形表。，得到新的系数矩阵，填新的单纯形表。3、
47、重复、重复2直到直到b列中无负数而所有列中无负数而所有 j全非正从而得最优解。全非正从而得最优解。54【例例11】用用对偶单纯形法求解下列线性规划对偶单纯形法求解下列线性规划minZ=5X1+2X2+6X32X1+4X2+8X324st.4X1+X2+4X38X10,X20,X30解解:将问题改为如下形式将问题改为如下形式:MAX(-Z)=-5X1-2X2-6X3+0X4+0X5-2X1-4X2-8X3+X4=-24st.-4X1-X2-4X3+X5=-8X1,X2,X3,X4,X5,055基变量基变量X1X2X3X4X5bX4-2-4-810-24X5-4-1-401-8Z-5-2-6000
48、最小最小原始不原始不可行可行对对偶偶可可行行进基进基出出基基基变量基变量X1X2X3X4X5bX21/212-1/406X5-7/20-2-1/41-2Z-40-2-1/201256基变量基变量X1X2X3X4X5bX2-310-1/214X37/4011/8-1/21Z-1/200-1/4-114 原问题的最优解为：原问题的最优解为：X1=0,X2=4,X3=1；对偶问题的最优解为：对偶问题的最优解为：y1=，y2=157注意几点：注意几点：1、对偶问题有可行解（为无界解），原问题无可、对偶问题有可行解（为无界解），原问题无可行解的判断：当行解的判断：当br0时，对时，对j=1,2n有有ar
49、j0；2、用对偶单纯形法求解时，当所有的约束条件为、用对偶单纯形法求解时，当所有的约束条件为“”时，不必引入人工变量使计算简化；时，不必引入人工变量使计算简化；3、在初始单纯形表其对偶问题应是基可行解这点、在初始单纯形表其对偶问题应是基可行解这点（j 0，目标函数系数皆为负，目标函数系数皆为负）对多数）对多数LP很难很难实现，因此，对偶单纯形法一般不单独使用，而实现，因此，对偶单纯形法一般不单独使用，而主要用于灵敏度分析及整数规划等有关问题中；主要用于灵敏度分析及整数规划等有关问题中；584、适用条件适用条件：有一个基，其对应的基满足：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶
50、可行）；单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解变量取值可有负数（非可行解）因因此此，对对偶偶单单纯纯形形法法主主要要适适合合于于解解如如下下形形式式的的线性规划问题：线性规划问题：59 在引入松弛变量化为标准型之后，约束等式在引入松弛变量化为标准型之后，约束等式两侧同乘两侧同乘-1-1，能够立即得到检验数全部非正的，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。表进行求解，非常方便。对于有些线性规划模型，如果在开始求解时对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，