第二章对偶问题PPT讲稿.ppt

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

1、第二章对偶问题第1页，共54页，编辑于2022年，星期二线性规划的对偶问题线性规划的对偶问题III每天可用能力每天可用能力设备设备A（h）设备设备B（h）调试工序（调试工序（h）06152115245利润（元）利润（元）21问公司应每天制造两种家电各多少件，使获取的问公司应每天制造两种家电各多少件，使获取的利润最大。利润最大。例1 第2页，共54页，编辑于2022年，星期二问题问题 美佳公司愿意以多大的代价出让自己所拥有美佳公司愿意以多大的代价出让自己所拥有的生产资源？的生产资源？第3页，共54页，编辑于2022年，星期二设设y1,y2和和y3分别表示出让资源分别表示出让资源A，B和调试和调试

2、工序的单价，则美佳公司同意出让的条件工序的单价，则美佳公司同意出让的条件将是将是同意出让生产产品同意出让生产产品I I的资源的资源同意出让生产产品同意出让生产产品IIII的资源的资源购买者希望用最少的代价获得这些资源购买者希望用最少的代价获得这些资源，因此因此第4页，共54页，编辑于2022年，星期二这样得到一个新的线性规划问题这样得到一个新的线性规划问题称这一问题是原来的称这一问题是原来的LP问题的问题的对偶线性规划对偶线性规划问题问题或或对偶问题对偶问题，原来的，原来的LP问题也称为问题也称为原问题原问题。第5页，共54页，编辑于2022年，星期二LP问题的对称形式问题的对称形式变量变量：

3、所有变量均具有非负约束：所有变量均具有非负约束约束条件约束条件：最大化问题最大化问题 所有约束条件都是所有约束条件都是“”型型的的 最小化问题最小化问题 所有约束条件都是所有约束条件都是“”型的型的第6页，共54页，编辑于2022年，星期二对称形式下的对偶关系对称形式下的对偶关系项目项目原问题原问题对偶问题对偶问题AbC目标函数目标函数约束条件约束条件决策变量决策变量约束条件系数矩阵约束条件系数矩阵约束条件右端项向量约束条件右端项向量目标函数系数向量目标函数系数向量max z=CX AXb X0约束条件系数矩阵转置约束条件系数矩阵转置目标函数的系数向量目标函数的系数向量约束条件的右端项向量约束

4、条件的右端项向量min w=YbAY CY 0第7页，共54页，编辑于2022年，星期二原问题原问题max z对偶问题对偶问题min wn个决策变量个决策变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变量约束条件约束条件“”型型决策变量决策变量0决策变量决策变量0约束条件约束条件“”型型对称形式的对应关系对偶问题的对偶是原问题，即对偶关系是相互对偶问题的对偶是原问题，即对偶关系是相互对称的关系对称的关系第8页，共54页，编辑于2022年，星期二非对称形式下的对偶关系原问题原问题（对偶问题）（对偶问题）max z对偶问题对偶问题（原问题）（原问题）min wn个决策变量个决策

5、变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变量约束条件约束条件“”型型约束条件约束条件“”型型约束条件约束条件“=”型型决策变量决策变量0决策变量决策变量0决策变量无约束决策变量无约束决策变量决策变量0决策变量决策变量0决策变量无约束决策变量无约束约束条件约束条件“”型型约束条件约束条件“”型型约束条件约束条件“=”型型第9页，共54页，编辑于2022年，星期二单纯形法的矩阵表示单纯形法的矩阵表示添加松弛变量XS将XB的系数矩阵化为单位矩阵第10页，共54页，编辑于2022年，星期二CB CN 0XB XN XS0 XS bB N ICB CN 0CB CN 0XB X

6、N XSCB XB B-1bI B-1N B-10 CN CBB-1N CBB-1 初始单纯形表迭代后的单纯形表第11页，共54页，编辑于2022年，星期二在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量 XB=B-1b系数矩阵的变化:A,IB-1A,I在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj,并且Pj=B-1 Pj若迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解第12页，共54页，编辑于2022年，星期二项目原问题变量原问题松弛变量 x1 x2x3 x4 x5x3 15/2 0 01 5/4 15

7、/2x1 7/2 1 00 1/4 -1/2x2 3/2 0 10 -1/4 3/2-j 0 00 1/4 1/2对偶问题剩余变量对偶问题变量 y4 y5y1 y2 y3项目对偶问题变量对偶问题剩余变量y1 y2 y3y4 y5y2 1/4-5/4 1 0-1/4 1/4 y3 1/215/2 0 1 1/2 -3/2j15/2 0 07/2 3/2原问题松弛变量原问题变量 x3 x4 x5x1 x2原问题最终单纯形表对偶问题最终单纯形表例1最大化问题检验数的相反数给出了对偶问题的解第13页，共54页，编辑于2022年，星期二原本在对偶关系中，原问题的变量对应着对偶问题的约原本在对偶关系中，原

8、问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。但束条件，原问题的约束条件对应着对偶变量。但在分别在分别添加了松弛变量和剩余变量后，也可以建立原问题添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系变量与对偶问题变量之间的对应关系原问题原问题对偶问题对偶问题第第i个约束条件中个约束条件中添加的松弛变量添加的松弛变量第第i个对偶变量个对偶变量第第j个变量个变量第第j个约束条件中个约束条件中添加的松弛变量添加的松弛变量注 上表中我们将松弛变量与剩余变量统称为松弛变量第14页，共54页，编辑于2022年，星期二对偶问题的基本性质对偶问题的基本性质弱对偶性

9、原问题可行解的目标函数不超过对偶问题可行解的目标函数第15页，共54页，编辑于2022年，星期二弱对偶性的推论弱对偶性的推论（1）原问题任一可行解的目标函数值是其对偶问题目标）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值函数值的下界；反之对偶问题任一可行解的目标函数值是原问题目标函数值的上界。是原问题目标函数值的上界。（2）如原问题有可行解且目标函数无界（即原问题为）如原问题有可行解且目标函数无界（即原问题为无界解），则对偶问题无可行解；反之对偶问题有可无界解），则对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。注意该推行

10、解且目标函数无界，则原问题无可行解。注意该推论的逆命题不成立。论的逆命题不成立。（3）若原问题有可行解而对偶问题无可行解，则原问题）若原问题有可行解而对偶问题无可行解，则原问题目标函数无界；反之对偶问题有可行解而原问题无可行目标函数无界；反之对偶问题有可行解而原问题无可行解，则原问题目标函数无界。解，则原问题目标函数无界。第16页，共54页，编辑于2022年，星期二最优性若原问题一个可行解目标函数等于对偶问题的某个可行解的目标函数,则这两个可行解分别是原问题和对偶问题的最优解强对偶性若原问题和对偶问题都有可行解,则它们都有最优解,且最优解的目标函数值相等互补松弛性在线性规划问题的最优解中,如果

11、对应某一约束条件的对偶变量值非零,则其对应的约束条件取等式;反之若一个约束条件为严格的不等式,则其对应的对偶变量为零第17页，共54页，编辑于2022年，星期二互补松弛性的另一种表述互补松弛性的另一种表述在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零;反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。第18页，共54页，编辑于2022年，星期二例（p76.7）原问题原问题原问题原问题对偶问题对偶问题对偶问题对偶问题将原问题最优解将原问题最优解X*=(2,2,4,0)代入原问题约束条件中得代入原问题约束条件中得第一个约束条件：第一个约束条件：

12、2+6=8，为等式，为等式第二个约束条件：第二个约束条件：第二个约束条件：第二个约束条件：4+2=64+2=6，为等式，为等式，为等式，为等式第三个约束条件：第三个约束条件：第三个约束条件：第三个约束条件：2+4=62+4=6，为等式，为等式，为等式，为等式第四个约束条件：第四个约束条件：第四个约束条件：第四个约束条件：2+2+492+2+40,得而由x2=20,得而由x3=40,得于是得到方程组得对偶问题最优解为注：原问题与对偶问题最优目标函数值都是 z*=4+8+4=16第20页，共54页，编辑于2022年，星期二第三节 影子价格第21页，共54页，编辑于2022年，星期二式中bi是线性规

13、划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi的意义代表在资源最优利用的条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格影子价格。设 和 分别是原问题和对偶问题的最优解，则由对偶性质，有第22页，共54页，编辑于2022年，星期二资源的影子价格随企业的生产任务、产品结构的资源的影子价格随企业的生产任务、产品结构的改变而改变改变而改变影子价格是资源的影子价格是资源的边际价格边际价格资源的影子价格也可视为一种资源的影子价格也可视为一种机会成本机会成本在生产过程中若某种资源未得到充分利用则其影在生产过程中若某种

14、资源未得到充分利用则其影子价格为零；只有在资源得到充分利用时，其影子价格为零；只有在资源得到充分利用时，其影子价格才可能非零子价格才可能非零利用影子价格可以说明：单纯形法中的检验数可利用影子价格可以说明：单纯形法中的检验数可以看成生产某种产品的产值与隐含成本的差以看成生产某种产品的产值与隐含成本的差可以利用影子价格确定企业内部的核算价格，以可以利用影子价格确定企业内部的核算价格，以便控制有限资源的使用和考核下属企业经营的好便控制有限资源的使用和考核下属企业经营的好坏。坏。第23页，共54页，编辑于2022年，星期二例1Max z=2x1+x2s.t.5x215 6x1+2x2 24 x1+x2

15、 5 x1,x20 x2=36x1+2x2=24x1+x2=5最优解可行域最优目标函数值的变化：8.5变到8.75，增加1/4资源的变化：设备B的可用时间从增加一小时第24页，共54页，编辑于2022年，星期二参考文献：参考文献：李慧：资源影子价格分析与经营管理决策，李慧：资源影子价格分析与经营管理决策，系统工系统工程理论与实践程理论与实践，2003年年4月号，月号，22-26第25页，共54页，编辑于2022年，星期二第四节 对偶单纯形法按对偶问题与原问题之间的关系，对最大按对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最化问题，在用单纯形法求解原问题时，最终表不但给出

16、了原问题的最优解，而且其终表不但给出了原问题的最优解，而且其检验数的相反数就是对偶问题的最优解。检验数的相反数就是对偶问题的最优解。第26页，共54页，编辑于2022年，星期二单纯形法求解的基本思路单纯形法求解的基本思路基可行解基可行解检验数非正检验数非正保持解的可行性保持解的可行性对偶单纯形法的基本思路对偶单纯形法的基本思路对偶问题基可行解对偶问题基可行解（检验数非正）（检验数非正）原问题基可行原问题基可行解解保持对偶问题解的保持对偶问题解的可行性（检验数非可行性（检验数非正正（对偶问题可行解）（对偶问题可行解）第27页，共54页，编辑于2022年，星期二保持对偶问题有基可行解,而原问题只是

17、基本解,通过迭代,使后者的负分量个数减少，一旦成为基可行解,则原问题与对偶问题同时实现最优解.第28页，共54页，编辑于2022年，星期二对偶单纯形法计算步骤适应于求解这样的适应于求解这样的LP问题：问题：标准化后不标准化后不含初始基变量，但将某些约束条件两端含初始基变量，但将某些约束条件两端乘以乘以“-1”后，即可找出初始基变量。后，即可找出初始基变量。要求：要求：初始单纯形表中的检验数满足最初始单纯形表中的检验数满足最优性条件优性条件第29页，共54页，编辑于2022年，星期二对满足上述条件的对满足上述条件的LP问题，对偶单纯形法的步问题，对偶单纯形法的步骤是：骤是：旋转运算。然后回到第旋

18、转运算。然后回到第2步。步。作出初始单纯形表（注意要求）作出初始单纯形表（注意要求）检查检查b列的数据是否非负，若是，表中已经给列的数据是否非负，若是，表中已经给出最优解；否则转下一步出最优解；否则转下一步确定换出变量确定换出变量：取：取b列最小的数对应的变量为列最小的数对应的变量为换出变量换出变量确定换入变量确定换入变量：用检验数去除以换出变量行的：用检验数去除以换出变量行的那些对应的负系数，在除得的商中选取其中最那些对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量小者对应的变量为换入变量第30页，共54页，编辑于2022年，星期二例 用对偶单纯形法求解如下的LP问题化成标准形式

19、第31页，共54页，编辑于2022年，星期二将各约束条件两端同乘“-1”得用对偶单纯形法求解得第32页，共54页，编辑于2022年，星期二最优解：最优解：x1=0,x=0,x2 2=1/4,x=1/4,x3=1/2,x=1/2,x4=0,x=0,x5=0=0最优目标函数值：最优目标函数值：最优目标函数值：最优目标函数值：w*=-8.5w*=-8.5（z*=8.5z*=8.5）注：通常很少直接使用对偶单纯形法求解线性规划问题。第33页，共54页，编辑于2022年，星期二灵敏度分析 将讨论将讨论LP问题中的参数问题中的参数 中有一个或几个发生改变时问题的最优中有一个或几个发生改变时问题的最优解会有

20、什么变化，或者这些参数在一个解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不多大的范围内变化时，问题的最优解不变变第34页，共54页，编辑于2022年，星期二研究的思路将个别参数的变化直接在计算得到的最将个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需要终单纯形表中反映出来，这样就不需要从头计算，而从头计算，而直接检查在参数改变后最直接检查在参数改变后最终表有什么改变终表有什么改变，若仍满足最终表的条，若仍满足最终表的条件，则表中仍给出最优解，否则从这个件，则表中仍给出最优解，否则从这个表开始进行迭代求改变以后的最优解。表开始进行迭代求改变以后的最优解。第3

21、5页，共54页，编辑于2022年，星期二灵敏度分析的步骤灵敏度分析的步骤将参数的改变计算反映到最终表上来。具体计算将参数的改变计算反映到最终表上来。具体计算公式可以使用公式可以使用检查原问题是否仍为可行解检查原问题是否仍为可行解检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解对检查情况按下表进行处理对检查情况按下表进行处理第36页，共54页，编辑于2022年，星期二原问题原问题对偶问题对偶问题结论或继续计算步骤结论或继续计算步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续迭代求最优用单纯形法继续迭代求最优解解非可行解非可

22、行解可行解可行解用对偶单纯形法继续迭代求用对偶单纯形法继续迭代求最优解最优解非可行解非可行解非可行解非可行解引进人工变量，编制新的单引进人工变量，编制新的单纯形表重新计算纯形表重新计算第37页，共54页，编辑于2022年，星期二价值系数变化的灵敏度分析例：在第一章美佳公司的例例：在第一章美佳公司的例1中中（1）若产品）若产品I的利润降至的利润降至1.5元元/件，而产品件，而产品II的利润增至的利润增至2元元/件，美佳公司的最件，美佳公司的最优生产计划有何改变；优生产计划有何改变；（2）若产品）若产品I的利润不变，则产品的利润不变，则产品II的利润的利润在什么范围变化时，该公司的最优生产在什么范

23、围变化时，该公司的最优生产计划不发生变化计划不发生变化第38页，共54页，编辑于2022年，星期二原最终单纯形表原最终单纯形表第39页，共54页，编辑于2022年，星期二（1）改变后）改变后新的最优解为：最优目标函数值为：第40页，共54页，编辑于2022年，星期二（2）改变后）改变后为使表中的解仍为最优解必须为使表中的解仍为最优解必须因此产品因此产品II的利润变化范围为的利润变化范围为第41页，共54页，编辑于2022年，星期二资源常数变化的灵敏度分析例：在第一章美佳公司的例例：在第一章美佳公司的例1中中（1）若设备）若设备A与调试工序的每天能力不变，与调试工序的每天能力不变，而设备而设备B

24、每天的能力增加到每天的能力增加到32小时，分析小时，分析公司最优计划的变化；公司最优计划的变化；（2）若设备）若设备A和和B每天可用能力不变，则每天可用能力不变，则调试工序能力在什么范围变化时，问题调试工序能力在什么范围变化时，问题的最优基不变的最优基不变第42页，共54页，编辑于2022年，星期二（1）b由由(15，24，5)T 变为变为(15，32，5)T 后，相应地最终表中后，相应地最终表中b列的数据变为列的数据变为代入原最终表第43页，共54页，编辑于2022年，星期二（2）设现在每天调试工序的时间为x，则最终表中b列的数变为故要使最优基不变必须第44页，共54页，编辑于2022年，星

25、期二利用Excle求解LP问题，以P45.7(2)为例第45页，共54页，编辑于2022年，星期二变量，已经赋了初值目标函数值约束条件右端值第46页，共54页，编辑于2022年，星期二第47页，共54页，编辑于2022年，星期二第48页，共54页，编辑于2022年，星期二其他专业软件：Lindo与Lingo，WinQSB例如Lingo，启动Lingo后，按图中的方式输入模型，然后点击求解的图标 。就可得到所需的最优解。第49页，共54页，编辑于2022年，星期二第50页，共54页，编辑于2022年，星期二24对偶问题为由图解法可得对偶问题最优解为 将该最优解代入对偶问题约束条件可知，第四个约束

26、条件为严格不等式，因此在原问题最优解中 而由于 因此将原问题最优解代入原问题约束条件，它们成为等式。再由于原问题最优目标函数值等于对偶问题最优目标函数值。于是原问题最优解满足方程组 第51页，共54页，编辑于2022年，星期二解方程组得原问题最优解：第52页，共54页，编辑于2022年，星期二2.5对偶线性规划为（2）直接观察可知对偶问题有解对应于该解的目标函数值 由弱对偶性，原问题的任何可行解的目标函数值都满足 第53页，共54页，编辑于2022年，星期二2.6 原问题显然有可行解。但对偶问题第一个约束条件与非负约束条件冲突，实际上，当时，第一个约束条件左端非正，因此不可能不小于正数1。这说明这些约束条件不能同时成立。故对偶问题无可行解。由弱对偶性，原问题目标函数无界。第54页，共54页，编辑于2022年，星期二