线性规划的对偶问题(1).ppt

《线性规划的对偶问题(1).ppt》由会员分享，可在线阅读，更多相关《线性规划的对偶问题(1).ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章第二章 线性规划的对偶理论与线性规划的对偶理论与灵敏度分析灵敏度分析 线性规划的对偶问题线性规划的对偶问题 对偶问题的基本性质对偶问题的基本性质 影子价格影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 参数线性规划参数线性规划12.1 线性规划的对偶问题线性规划的对偶问题一、对偶问题的提出一、对偶问题的提出支持对偶理论的基本思想是：每一个线性规划问题都存在一个与其对偶的问题。在求一个问题的解的同时，也给出了另一个问题的解。例：二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式线性规划问题具有对称形式，若：变量非负 目标函数求极大值时，约束方程均为 目标函数求极小值

2、时，约束方程均为2二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式对称形式的LP问题(LP1)：其对偶问题为(LP2)：注：对称形式的注：对称形式的LP问问题题,对对b没有非负要求。没有非负要求。3二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式 LP1：LP2：4二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式项目原问题对偶问题A约束系数矩阵约束系数矩阵的转置b资源向量价格系数C价格系数资源向量目标函数max z=CXmin w=Yb约束条件AXbAY C决策变量X0Y05二、对称形式下对偶问题的一般形式二、对称形式下对偶问题的一般形式练习:给

3、出下述LP问题的对偶问题:6三、非对称形式的原三、非对称形式的原-对偶问题的关系对偶问题的关系1.非对称转化为对称LP问题的步骤目标函数及变量约束的转化同标准形式的转化；约束方程若为等式则令:约束方程若为”，则两侧同乘以“-1”，8三、非对称形式的原三、非对称形式的原-对偶问题的关系对偶问题的关系P50 例题2.线性规划原问题同对偶问题的对应关系如下：原问题 对偶问题 目标函数Max 目标函数Min m个 m个 0 0约束条件 =无约束 决 策 变 量 n个 n个 0 0 决策变量 无约束 =约 束 条 件 资源向量b 价值系数b 价值系数C 资源向量C约束条件系数矩阵A 约束条件系数矩阵A9

4、三、非对称形式的原三、非对称形式的原-对偶问题的关系对偶问题的关系练习:给出下述LP问题的对偶问题:102.2 对偶问题的基本性质对偶问题的基本性质LP1：LP2：本节讨论的问题假定原问题及对偶问题为对称形式12对称形式的线性规划问题：13-3010000CB基bx1x2x3x4x5x6x70 x5411101000 x61-21-1-10100 x790310001-30100000 x50000-1/211/2-1/20 x23011/30001/3-3x11102/31/20-1/21/600300-3/21/2140-3010000CB基bx5x2x1x3x4x5x6x70 x5411

5、1101000 x6101-2-1-10100 x790301000100-3100000 x501000-1/211/2-1/20 x230101/30001/3-3x110012/31/20-1/21/6000300-3/21/2BB-115一、单纯形算法的矩阵描述一、单纯形算法的矩阵描述 对称形式的LP：加上松驰变量Xs后为(LP2)：16一、单纯形算法的矩阵描述一、单纯形算法的矩阵描述LP2的初始单纯形表及经过若干步迭代后某一步的单纯形表如下：项目非基变量基变量XBXNXS0XSbBNIcj-zjCBCN0项目XBXNXSCBXBB-1bIB-1NB-1cj-zj0基变量非基变量B为某

6、步单纯形表中基变量在初始单纯形中对应的矩阵N由A中去掉B后剩下的列向量组成表表1表表2CN-CB B-1N-CB B-117一、单纯形算法的矩阵描述一、单纯形算法的矩阵描述1.为xj在表2中的系数，为xj在表1中的系数，则有：2.若表2为最终单纯形表，则有：由C=CB CN A=B N，上式可改为：结论：(2.1)18一、单纯形算法的矩阵描述一、单纯形算法的矩阵描述结论：3.令 ，则2.1式可以写为；说明 为对偶问题的可行解。将这个解代入对偶问题的目标函数，有：即原问题有最优解，则对偶问题存在可行解，且它们的目标函值相等。称CBB-1为单纯形乘子19二、对偶问题的基本性质二、对偶问题的基本性质

7、1.对称性2.弱对偶性推论：(1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。(2)如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。(3)如原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。20二、对偶问题的基本性质二、对偶问题的基本性质(2)如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。(3)如原问题有可行解而

8、对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。(2)如原问题有可行解且目标函数值无界，则其对偶问题无如原问题有可行解且目标函数值无界，则其对偶问题无可行解；可行解；反之对偶问题有可行解且目标函数值无界，则反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。其原问题无可行解。(3)如原问题有可行解而对偶问题无可行解，则原问题目标如原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；函数值无界；反之对偶问题有可行解而其原问题无可行反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。解，则对偶问题的目标函数值

9、无界。原问题有可行解，则原问题目标函数原问题有可行解，则原问题目标函数无界的无界的充要条件充要条件是对偶问题无可行解。是对偶问题无可行解。(2)如原问题有可行解且目标函数值无界，则其对偶问题无如原问题有可行解且目标函数值无界，则其对偶问题无可行解；可行解；反之对偶问题有可行解且目标函数值无界，则反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。其原问题无可行解。(3)如原问题有可行解而对偶问题无可行解，则原问题目标如原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；函数值无界；反之对偶问题有可行解而其原问题无可行反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界

10、。解，则对偶问题的目标函数值无界。对偶问题有可行解，则对偶问题目标函对偶问题有可行解，则对偶问题目标函数无界的数无界的充要条件充要条件是原问题无可行解。是原问题无可行解。21二、对偶问题的基本性质二、对偶问题的基本性质3.最优性4.强对偶性5.互补松驰性注:上述针对对称形式证明的对偶问题的性质,同样适用于非对称形式的LP问题.22二、对偶问题的基本性质二、对偶问题的基本性质6.非对称形式的LP问题的互补松驰性 设 为原问题的最优解 为对偶问题的最优解若 ,则有:若 ,则有:若 ,则有:若 ,则有:232.4 对偶单纯形法对偶单纯形法241.列出满足对偶问题为可行解满足对偶问题为可行解的初始单纯

11、形表2.若所有bi（i=1,2,m）均大于等于0,则单纯形表中的解即为原问题的最优解，否则转下一步。3.2.确定换出基变量出基变量：br=minbi|bi0 xr为换出基变量为换出基变量4.3.确定换入基变量入基变量：5.xs为换入基变量为换入基变量6.4.用换入变量替换换出变量，得到一个新的基基，对这个基进行初等行变换为单位阵，对新的基再检查是否所有bi大于等于0，是，则得到原问题的最优解，否则，转第2步。一、对偶单纯形法计算步骤例1：用对偶单纯形法求解下列LP问题26在确定换入、换出基变量时，必须保证对偶问题的解为可行解，即检验数小于等于0，下面证明证明 的选取可以的选取可以保证对偶问题解

12、的可行性。保证对偶问题解的可行性。27二、对偶单纯形法的概念在对偶可行基的基础上进行的单纯形法，称为对偶单纯形法。优点：省去了引入人工变量的麻烦缺点：对偶问题的基可行解不易找到作用：灵敏度分析的工具使用前提：初始单纯形表各中检验数非正28练习：用对偶单纯形法求解下述LP问题：293.确定换入基入基变量：xs为换入基变量为换入基变量注:若LP问题的标准形式为:其对偶单纯形法的求解步骤确定换入基变量的原则如下:其它步骤同目标函数为极大值情况其它步骤同目标函数为极大值情况311524500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101152450024y21/3011

13、/6-1/600y5-1/3-50-2/3-1/3115014024y21/4-5/410-1/45y31/215/2011/2-3/215/2007/23/2例1:322.5 灵敏度分析灵敏度分析一、灵敏度分析的含义指对系统或事务因周围条件的变化显示出来的敏感程度的分析。二、灵敏度分析的步骤1.将参数（cj,aij,bi）的改变通过计算反映到最终单纯形表最终单纯形表中；2.检查原问题的解是否仍为可行的；3.检查对偶问题的解是否仍为可行的；4.按下表所列情况得出结论或决定继续计算的步骤。33最优解不变最优解不变单纯形法迭代单纯形法迭代对偶单纯形法迭代对偶单纯形法迭代引入人工变量，重新迭代计算引

14、入人工变量，重新迭代计算可行解非可行解可行解非可行解可行解可行解非可行解非可行解结论或继续计算的步骤结论或继续计算的步骤对偶问题对偶问题原问题原问题表 2-934三、分析cj的变化四、分析bi的变化五、增加一个变量xj的分析六、分析aij的变化七、增加一个约束条件的分析35三、分析cj的变化线性规划目标函数中变量系数cj的变化仅仅影响到检验数，所以将cj的变化直接反映到最终单纯形表中，只可能出现表2-9中的第一、二一、二两种情况。例5：在美佳公司例子中，(1)若家电的利润降至1.5元/件,而家电的利润增至2元/件,美佳公司最优生产计划有何变化?(2)若家电的利润不变,而家电的利润在什么范围内变

15、化时,该公司的最优生产计划不发生变化。36四、分析bi的变化右端项 bi 的变化在实际问题中反映为可用资源数量的变化，bi的变化反映到最终单纯形表中将引起b列数字变化，可能出现表2-9中的第一一、三三两种情况。例6：在美佳公司例子中，(1)若设备A和调试工序的每天可用能力不变,而设备B每天的可用能力增加到32h,分析公司最优计划的变化。(2)若设备A和设备B每天可用能力不变,则调试工序可用能力在什么范围内变化时,问题的最优基不变。37五、增加一个变量xj的分析增加一个变量在实际问题中反映为增加一种新的产品，可能出现表2-9中的第一、二一、二两种情况。1.计算新增加变量在最终单纯形表中的列变量；

16、2.计算新增加变量的检验数；3.若检验数小于等于零，则只需将计算得到的列向量和检验数写入最终单纯形表；若检验数大于零，则按照单纯形法继续迭代计算。38例7：在美佳公司例子中，设该公司又计划推出新型号的家电，生产一件所需设备进制 A，B 及调试工序的时间分别为 3h,4h,2h，该产品的预期盈利为3元/件，试分析该种产品是否值得投产,该公司的最优生产计划有何变化。解：设该公司生产家电 x6件39cj 2 1 0 0 0 CB 基 b x1 x2 x3 x4 x5 0 x3 15/2 2 x1 7/2 1 x2 3/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1

17、/4 3/2 0 0 0 -1/4 -1/23x6-7021 0 x3 51/4 2 x1 7/2 3 x6 3/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 0 -1/2 0 -1/8 -5/4 040六、分析aij的变化aij的变化使线性规划的约束系统矩阵A发生变化。若变量xj在最终单纯形表中为非基变量非基变量，其约束条件中系数aij的变化可参照增加一个变量的情况进行处理。若变量在最终单纯形表中为基变量基变量，则aij的变化将使B及 B-1发生变化。因此有可能引起原问题和对偶问题均为非可行解。可能出现表2-9中的所有可能的

18、情况。41例8：在美佳公司例子中，若家电每件需设备A，B及调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。解：先将生产工时变化后的新家电看作是一种新产品，生产量为 ，仿例7的步骤直接计算检验数和列向量，将其反映到最终单纯形表。42cj21000CB基bx1x2x3x4x5021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj-zj000-1/4-1/23/211/21/21/23因x2已变换为 ，故用单纯形算法将 替换出基变量中的x2，并在下一个表中不再保留x2，得下表。43cj21000CB基bx1x2x

19、3x4x5021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj-zj000-1/4-1/23/211/21/21/23344cj23000CB基bx1x2x3x4x5021x3x1x2-92301000110041/2-1/2-24-23cj-zj0001/2-53原问题与对偶问题均为非可行解，故先设法使原问题变为可行解。第1行的约束可写为：两端同乘以-1，再加上人工变量x6得：45100-1/61/60-1/24-1/121/80010103/811/415/8x5x1x20210-1/3-5/2400cj-zj3-M+5/241/241/

20、12-1/8cj23000CB基bx1x2x3x4x5-M21x6x1x2923010001-100-41/2-1/224-23cj-zj00-M1/2-4M-5+24M30100-M46七、增加一个约束条件的分析增加一个约束条件在实际问题中相当于增添一道工序，分析的方法是先将原问题最优解的变量值代入新增的约束条件，如满足，说明新增的约束未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。例9：设家电，经过调试后，还需要经过一道环境试验工序。家电每件须环境试验3h，家电每件须环境试验2h，又环境试验工序每天生产能力为12h。分析增加该工序后的美佳公司最优生产计

21、划。新增约束条件为:47cj21000CB基bx1x2x3x4x50210 x3x1x215/27/23/2120103001210005/41/4-1/40-15/2-1/23/20cj-zj000-1/4-1/200001048cj21000CB基bx1x2x3x4x50210 x3x1x215/27/23/2-3/20100001010005/41/4-1/4-1/4-15/2-1/23/2-3/2cj-zj000-1/4-1/200001049cj21000CB基bx1x2x3x4x50210 x3x1x254010100001010005/21/3-1/21/60001cj-zj000-1/60-1/3-5-1/31-2/30502.6 参数线性规划参数线性规划参数线性规划的形式：或：51参数线性规划问题的分析步骤：(1)令 =0，求解得最终单纯形表(2)将 或 项反映到最终单纯形表中(3)随 值的增大或减小，观察原问题或对偶问题，确定现有解允许 值的变动范围，若超出这个范围，用单纯形法或对偶单纯形法求新的解。(4)重复第(3)步，一直到 的值继续增大或减小时，表中的解不再出现变化为止。P71 例105253