第二章-线性规划的对偶理论与灵敏度分析1课件.ppt

1、2 线性规划的对偶理论与灵敏度分析2-1线性规划的对偶问题 对偶:在不同的领域有着不同的诠释。在词语中，它是一种修辞方法，两个字数相等、结构相似的语句表现相关或相反的意思。在数学上表现为数式或图形的对称,命题或结构的对应 1. 对偶问题的提出 例1 第一章例1中美佳公司利用该公司资源生产两种家电产品时,其线性规划问题为122121212(1) max25156224 .5,0LPzxxxxxstxxxx项目项目I IIIII每天可用能力每天可用能力设备设备A (h)A (h) 0 05 51515设备设备B (h)B (h)6 62 22424调试程序调试程序 (h)(h)1 11 15 5利

2、润利润2 21 1 假定有某个公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美住公司愿意放弃生产活动，出让自己的资源。 美佳公司愿意让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。1. 对偶问题的提出项目III每天可用能力每天可用能力设备设备A (h) 0515设备设备B (h)6224调试程序调试程序 (h) 115利润利润211252632132yyyyy用y1，y2，y3代表单位时间设备A、设备B和调试工序的出让代价，为使美佳公司愿意出让自己的资源（出售资源后所得不应比生产产品所得少），则： 收购美佳公司应付出的代价为（总的收购价越小越好）：

3、 15y1+24y2+5y31. 对偶问题的提出项目III每天可用能力每天可用能力设备设备A (h) 0515设备设备B (h)6224调试程序调试程序 (h) 115利润利润210,12526st. 52415min )2( 32132132321yyyyyyyyyyyLP所以1. 对偶问题的提出0,52426155. 2max ) 1(212121221xxxxxxxstxxzLP)2(LP0,12526st. 52415min32132132321yyyyyyyyyyy比较LP1和LP2项目III每天可用能力每天可用能力设备设备A (h) 0515设备设备B (h)6224调试程序调试程

4、序 (h) 115利润利润21对偶问题对偶问题 minW=Yb AY CY 0maxZ=CX AX bX 0原问题原问题每个线性规划问题都存在一个与其对应的对偶问题2. 对偶问题的一般形式), 1(0.maxP1221112222121112121112211njxbxaxaxabxaxaxabxaxaxastxcxcxczjnmnmmnnnnnn）的一般形式原问题（), 1(0.min221122222112112211112211miycyayayacyayayacyayayastybybybDjnmmnnnmmmmmm）的一般形式对偶问题（矩阵形式表示原对偶问题0.max)(XbAXst

5、CXzP原问题原问题(P) 对偶问题对偶问题(D)价格系数价格系数 资源向量资源向量资源向量资源向量 价格系数价格系数最大化最大化 最小化最小化变量个数变量个数 约束个数约束个数约束个数约束个数 变量个数变量个数约束系数行约束系数行约束系数列约束系数列0.min)(YCYAstbYD互称对偶问题互称对偶问题对应关系：对应关系：3. 非对称形式的原对偶问题关系对偶变换的规则对偶变换的规则v约束条件的类型与非负条件对偶v非标准的约束条件类型对应非正常的非负条件原问题(max)对偶问题(min)技术系数矩阵 A技术系数矩阵AT价值系数 C右端项 b右端项 b价值系数 C第i 行约束条件为 型对偶变量

6、 yi 0第i 行约束条件为 型对偶变量 yi 0第i 行约束条件为 = 型对偶变量 yi 不限决策变量 xj 0第j 行约束条件为 型决策变量 xj 0第j 行约束条件为 型决策变量 xj 不限第j 行约束条件为 = 型0,510342023.54)(max 2 . 1 . 2 1221212121xxxxxxxxtsxxxf不限不限原线性规划问题原线性规划问题例例 0, 551033420223.554)(max)(max, 221221221221221221xxxxxxxxxxxxxxxtsxxxxf型标准问题型标准问题化为化为0,532532443.551020)(min 43214

7、321432143214321wwwwwwwwwwwwwwwwtswwwwwh则则应应用用标标准准型型对对偶偶变变换换规规不限经整理得令3213213213214332211, 0, 0532443. .51020)(min:, yyyyyyyyytsyyyygwwywywy练 习： 矩阵形式表示原对偶问题0.max)(XbAXstCXzP原问题原问题(P) 对偶问题对偶问题(D)价格系数价格系数 资源向量资源向量资源向量资源向量 价格系数价格系数最大化最大化 最小化最小化变量个数变量个数 约束个数约束个数约束个数约束个数 变量个数变量个数约束系数行约束系数行约束系数列约束系数列0.min)(

8、YCYAstbYD互称对偶问题互称对偶问题对应关系：对应关系：对偶变换的规则对偶变换的规则v约束条件的类型与非负条件(非负约束)对偶v非标准的约束条件类型对应非正常的非负条件原问题(max)对偶问题(min)技术系数矩阵 A技术系数矩阵AT价值系数 C右端项 b右端项 b价值系数 C第i 行约束条件为 型对偶变量 yi 0第i 行约束条件为 型对偶变量 yi 0第i 行约束条件为 = 型对偶变量 yi 不限决策变量 xj 0第j 行约束条件为 型决策变量 xj 0第j 行约束条件为 型决策变量 xj 不限第j 行约束条件为 = 型2-2 对偶问题的基本性质对偶问题的基本性质1. 对称性：一个线

9、性规划的对偶问题的对称性：一个线性规划的对偶问题的对偶问题即是原问题对偶问题即是原问题2. 弱对称性：假定弱对称性：假定X是原规划（是原规划（P）的任）的任一可行解，一可行解，Y是对偶规划（是对偶规划（D）的任一可）的任一可行解，则有行解，则有CX bTY3. 无界性：若原问题（对偶问题）为无无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解界解，则其对偶问题（原问题）无可行解4. 设设X是原问题的可行解，是原问题的可行解，Y是对偶问题的可行是对偶问题的可行解，当解，当CXbTY时，时，X，Y皆为最优解。皆为最优解。5. 强对偶性强对偶性 原规划有最优解，则对偶规划也有最原规

10、划有最优解，则对偶规划也有最优解，且最优值相同优解，且最优值相同。6. 互补松弛性互补松弛性(松紧定理松紧定理) 在线性规划问题的最优在线性规划问题的最优解中，解中，如果对应某一约束条件的对偶变量值如果对应某一约束条件的对偶变量值非非0，则该约束取严格等式，如果约束条件取，则该约束取严格等式，如果约束条件取严格不等式，其对应的对偶变量一定为严格不等式，其对应的对偶变量一定为0。2-2 对偶问题的基本性质对偶问题的基本性质原问题与对偶问题最终单纯型表的比较原问题与对偶问题最终单纯型表的比较0,12526st. 52415min 321253211432321yyyxyyyyxyyyyyy对偶变量

11、052426155. 2max 3521242113221ixyxxxyxxxyxxstxxz对偶变量Cj原问题的变量原问题的变量原问题松弛变量原问题松弛变量XBbx1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2变量变量对偶问题的剩余变量对偶问题的剩余变量对偶问题的变量对偶问题的变量y4y5y1y2y3Cj对偶问题的变量对偶问题的变量对偶问题的剩余变量对偶问题的剩余变量XBby1y2y3y4y5 y2 1/4-5/410-1/41/4y31/215/2011/2-3/2zj-cj15/2007/23/

12、2变量变量原问题松弛变量原问题松弛变量原问题变量原问题变量x3x4x5x1x2 在最优解的单纯型表中，原问题虚变在最优解的单纯型表中，原问题虚变量量( (松弛或剩余松弛或剩余) )的检验数的检验数对应对应对偶问题实对偶问题实变量变量( (对偶变量对偶变量) )的最优解，原问题实变量的最优解，原问题实变量( (决策变量决策变量) ) 的检验数对应对偶问题虚变量的检验数对应对偶问题虚变量( (松弛或剩余变量松弛或剩余变量) )的最优解。的最优解。例：例： min = 2x1+3x2+5x3+2x4+3x5 其对偶解其对偶解 y1 =4/5 y2 =3/5 Z =5 用对偶理论求用对偶理论求(P)的

13、最优解的最优解x1+x2+2x3+x4+3x5 42x1 -x2+3x3+x4+x5 3 xi 0 ( i =1 5 )(P)对偶性质的应用对偶性质的应用解：解：(D)为为maxZ =4y1+3y2y1+2y2 2 y1 - y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1 , y2 0其对偶解其对偶解 y1 =4/5 y2 =3/5将将y1 ，y2 代入，知代入，知, , 为严格不等式为严格不等式 x2 = x3 = x4 = 0 x = (1, 0, 0, 0, 1)T Z=5由由y1 ，y20知原约束为等式知原约束为等式 x1+3x5 =42x1+x5 =32 23

14、3 影子价格影子价格 当线性规划原问题求得最优解当线性规划原问题求得最优解xj*时，其时，其对偶问题也得到最优解对偶问题也得到最优解yi*，且，且 式中式中bi*是线性规划原问题约束条件的右端项，是线性规划原问题约束条件的右端项，代表第代表第i 种资源的拥有量；种资源的拥有量；对偶变量对偶变量yi*的意义代表的意义代表在资源最优利用条件下对单位第在资源最优利用条件下对单位第i 种资源的估价种资源的估价。 这种估价不是资源的市场价格，这种估价不是资源的市场价格，而是根据资而是根据资源在生产中作出的贡献而作的估价源在生产中作出的贡献而作的估价，这个概念在，这个概念在西方经济学中称为西方经济学中称为

15、影子价格影子价格miiinjjjybxcz1*1*影子价格提供的信息1. 1. 影子价格可以告诉决策者，增加哪一种资源对增影子价格可以告诉决策者，增加哪一种资源对增加效益最有利。加效益最有利。 资源1影子价格为0，增加与否对总利润没有影响。资源2影子价格为1，增加一个单位，总利润增加1，资源3影子价格为3，增加一个单位，一产品产量34件，二产品产量12，总利润218，增加3，资源3对目标函数贡献最大， v资源3售价 3 卖出获利2. 影子价格可以告诉决策者，用多大代价增加资源影子价格可以告诉决策者，用多大代价增加资源才是合算才是合算机会成本。机会成本。 如：资源如：资源3的影子价格为的影子价格

16、为3，即增加一个单位的，即增加一个单位的会使收益增加会使收益增加3，获取资源，获取资源3的代价的代价3，就可以，就可以获利。获利。3. 影子价格告诉决策者，资源利用程度影子价格告诉决策者，资源利用程度对线性规划问题的求解是确定资源的最优分配对线性规划问题的求解是确定资源的最优分配方案，对于对偶问题的求解则是确定对资源的方案，对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利恰当估价，这种估价直接涉及资源的最有效利用。用。影子价格不为零，则该资源已消耗完毕影子价格不为零，则该资源已消耗完毕 ；影子价格为零，则该资源没有充分利用影子价格为零，则该资源没有充分利用 24 对偶

17、单纯形法对某标准形式的线性规划问题对某标准形式的线性规划问题0.maxXbAXstCXz 当当所有检验数小于等于零所有检验数小于等于零（cj-zj0），），bi0；此线性规划问题取得最优解。；此线性规划问题取得最优解。若存若存在在bi0, 则用对偶单纯形法进行求解。则用对偶单纯形法进行求解。 应用对偶单纯形法进行求解时，应用对偶单纯形法进行求解时，bi的值的值不要求为正。不要求为正。 单纯形法计算的前提是单纯形法计算的前提是bi的值的值总保持非负总保持非负，对偶单纯形法计算的前提是对偶单纯形法计算的前提是检验数总保持非检验数总保持非正正。对偶单纯形法基本步骤对偶单纯形法基本步骤 max型型(

18、(min型型) )(1)、确定初始基确定初始基Bo ,作初始表，作初始表，使全部使全部j 0 ( 0)(2)、检验：检验： 若若B-1 b 0，是最优是最优。否则转否则转（3）(b)l = min (b)i -xl出基出基b0(3)、基变换，先确定出基变量、基变换，先确定出基变量xl再确定换入基变量再确定换入基变量 若若X l 所在所在行的行的alj 全全 0 ，停，原问题，停，原问题无可无可行解。行解。 若若Xl 行的行的alj 有有alj 0 ,则求则求=min =j k aljalkalj 12原问题最优解不是本例的最优解原问题最优解不是本例的最优解1223621xxxx1、x2 列不是

19、单位向量，故需进行初等变换，列不是单位向量，故需进行初等变换，Cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj000-1/4-1/2Cj210000CBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x612320001cj-zj000-1/4-1/20Cj210000CBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-

20、1/43/200 x612320001cj-zj000-1/4-1/20Cj210000CBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/20用用对偶单纯形法对偶单纯形法迭代计算得迭代计算得Cj210000CBXBbx1x2x3x4x5x60 x315/20015/4-15/202x17/21001/4-1/201x23/2010-1/43/200 x6-3/2000-1/4-3/21cj-zj000-1/4-1/20Cj210000

21、CBXBbx1x2x3x4x5x60 x3150015/20-52x141001/30-1/31x20010-1/2010 x510001/61-2/3cj-zj000-1/60-1/3 允许的增量和允许的减量表示约束条件右端值（允许的增量和允许的减量表示约束条件右端值（b b）在允许的增量与减量之间变化，影子价格不变，如车间在允许的增量与减量之间变化，影子价格不变，如车间2 2右右端项在端项在12-6,12+812-6,12+8内，增加内，增加1 1单位，总利润将增加单位，总利润将增加150150若若X X* *和和Y Y* *分别是线性规划的原问题和对偶问题分别是线性规划的原问题和对偶问题

22、的最优解，则下面有关式子中正确的是的最优解，则下面有关式子中正确的是()()A.CXA.CXYY* *b B.CXb B.CX* *YY* *b C.CXb C.CX* *=Y=Y* *b b D.CXD.CX* *YY* *b b如果原问题的某个变量无约束，则对偶问题中对应的如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为（约束条件应为（ ）A A等式等式 B B严格不等式严格不等式 C C大于等于大于等于 D D小于等于小于等于0,9010412203.1355max321321321321xxxxxxxxxtsxxxz50532321xxx已知线性规划问题：已知线性规划问题：用

23、单纯形法求解，用单纯形法求解，设已求得最终表如下设已求得最终表如下（表中（表中x x4 4，x x5 5为松弛变量）为松弛变量）Cj-551300CBXBB-1bX1X2X3X4X5X210X5-41Cj-Zj（1 1）表中有些缺项，请将其填上，并写出该线性规划问题的最优解和最优值。）表中有些缺项，请将其填上，并写出该线性规划问题的最优解和最优值。（2 2）写出所列线性规划问题的对偶问题写出所列线性规划问题的对偶问题（3 3）a a：b b1 1由由2020变为变为4545，求新的最优解；，求新的最优解； b b：c c3 3由由1313变为变为8 8，是否影响最优解？若有影响，求新的最优解；，是否影响最优解？若有影响，求新的最优解； c c：增加约束条件：增加约束条件：，求新的最优解。，求新的最优解。 精品课件精品课件！精品课件精品课件！某厂生产甲、乙、丙三种产品已知有关数如表所示。试分别回答下列问题甲乙丙原料拥有量A63545B34530单件利润4151.建立线性规划模型求使该厂获利最大的生产计划2.原材抖B不足可去市场购买，单价0.5，问该厂应否购买。3.乙、丙的利润不变，甲的利润在什么范围内变化，上述最优解不变。4.有一种新产品丁其原料消耗定额：A为3个单位B为2单价，单件利润为2.5，问该种产品是否值得安排生产。并求新的最优计划.