《运筹学对偶问题》 (2)ppt课件

1、III每天可用才干每天可用才干设备设备Ah设备设备Bh调试工序调试工序h06152115245利润元利润元21例1 0,52426155s.t.2max212121221xxxxxxxxxz设设y1,y2和和y3分别表示出让资源分别表示出让资源A，B和调和调试工序的单价，那么美佳公司赞同出让的试工序的单价，那么美佳公司赞同出让的条件将是条件将是赞同出让消费产品赞同出让消费产品I的资源的资源赞同出让消费产品赞同出让消费产品II的资源的资源购买者希望用最少的代价获得这些资源，购买者希望用最少的代价获得这些资源，因此因此2632 yy125321yyy32152415minyyyz这样得到一个新的线

2、性规划问题这样得到一个新的线性规划问题0,1252652415min32132132321yyyyyyyyyyyw称这一问题是原来的称这一问题是原来的LP问题的对偶线性规问题的对偶线性规划问题或对偶问题，原来的划问题或对偶问题，原来的LP问题也称为问题也称为原问题。原问题。工程工程原问题原问题对偶问题对偶问题AbC目的函数目的函数约束条件约束条件决策变量决策变量约束条件系数矩阵约束条件系数矩阵约束条件右端项向量约束条件右端项向量目的函数系数向量目的函数系数向量max z=CX AXb X0约束条件系数矩阵转置约束条件系数矩阵转置目的函数的系数向量目的函数的系数向量约束条件的右端项向量约束条件的

3、右端项向量min w=YbAY CY 0原问题原问题max z对偶问题对偶问题min wn个决策变量个决策变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变量约束条件约束条件“型型决策变量决策变量0决策变量决策变量0约束条件约束条件“型型对称方式的对应关系对偶问题的对偶是原问题，即对偶关系是对偶问题的对偶是原问题，即对偶关系是相互对称的关系相互对称的关系非对称方式下的对偶关系原问题对偶问题原问题对偶问题max z对偶问题原问题对偶问题原问题min wn个决策变量个决策变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变量约束条件约束条件“型型约束条件约束条件“

4、型型约束条件约束条件“=型型决策变量决策变量0决策变量决策变量0决策变量无约束决策变量无约束决策变量决策变量0决策变量决策变量0决策变量无约束决策变量无约束约束条件约束条件“型型约束条件约束条件“型型约束条件约束条件“=型型0maxXbAXCXzNBNBCCCNBAXXX,00maxXbIXAXSXCXzsbBXBNXBIXbIXNXBXSNBSNB111原来添加松弛变量XS将XB的系数矩阵化为单位矩阵0, 00maxNBSNBXXCXCzXXbIXNXBXsNNBBCB CN 0XB XN XS0 XS b B N ICB CN 0CB CN 0XB XN XSCB XB B-1bI B-1

5、N B-10 CN CBB-1N CBB-1 初始单纯形表迭代后的单纯形表 在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆 在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量 XB=B-1b 系数矩阵的变化: A, IB-1A, I 在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj,并且Pj=B-1 Pj 假设迭代后的单纯形表为最终表那么该表也同时给出对偶问题的最优解工程原问题变量原问题松弛变量 x1 x2x3 x4 x5x3 15/2 0 01 5/4 15/2x1 7/2 1 00 1/4 -1/2x2 3/2 0 10 -1/4 3/2-j 0 00 1/4

6、 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最大化问题检验数的相反数给出了对偶问题的解本来在对偶关系中，原问题的变量对应着对偶问题本来在对偶关系中，原问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。的约束条件，原问题的约束条件对应着对偶变量。但在分别添加了松弛变量和剩余变量后，也可以

7、建但在分别添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系立原问题变量与对偶问题变量之间的对应关系原问题原问题对偶问题对偶问题第第i个约束条件中个约束条件中添加的松弛变量添加的松弛变量第第i个对偶变量个对偶变量第第j个变量个变量第第j个约束条件中个约束条件中添加的松弛变量添加的松弛变量注 上表中我们将松弛变量与剩余变量统称为松弛变量 弱对偶性 原问题可行解的目的函数不超越对偶问题可行解的目的函数1原问题任一可行解的目的函数值是其对偶原问题任一可行解的目的函数值是其对偶问标题的函数值的下界；反之对偶问题任一可行问标题的函数值的下界；反之对偶问题任一可行解的目的函数值是

8、原问标题的函数值的上界。解的目的函数值是原问标题的函数值的上界。2如原问题有可行解且目的函数无界即原如原问题有可行解且目的函数无界即原问题为无界解，那么对偶问题无可行解；反之问题为无界解，那么对偶问题无可行解；反之对偶问题有可行解且目的函数无界，那么原问题对偶问题有可行解且目的函数无界，那么原问题无可行解。留意该推论的逆命题不成立。无可行解。留意该推论的逆命题不成立。3假设原问题有可行解而对偶问题无可行解，假设原问题有可行解而对偶问题无可行解，那么原问标题的函数无界；反之对偶问题有可行那么原问标题的函数无界；反之对偶问题有可行解而原问题无可行解，那么原问标题的函数无界。解而原问题无可行解，那么

9、原问标题的函数无界。最优性假设原问题一个可行解目的函数等于对偶问题的某个可行解的目的函数,那么这两个可行解分别是原问题和对偶问题的最优解强对偶性假设原问题和对偶问题都有可行解,那么它们都有最优解,且最优解的目的函数值相等互补松弛性在线性规划问题的最优解中,假设对应某一约束条件的对偶变量值非零,那么其对应的约束条件取等式;反之假设一个约束条件为严厉的不等式,那么其对应的对偶变量为零在线性规划问题的最优解中,假设对应某一约束条件的对偶变量值非零,那么该约束条件中松弛变量等于零;反之假设一个约束条件中松弛变量非零,那么其对应的对偶变量为零。例p76.74 , 3 , 2 , 1, 096628342

10、max321432214214321jxxxxxxxxxxxxxxxxzj4 , 3 , 2 , 1, 01143229668min314343214214321iyyyyyyyyyyyyyyyywi而由x1=20, 得22421yyy而由x2=20, 得434321yyyy而由x3=40, 得143 yy于是得到方程组0143224434321421yyyyyyyyyy得对偶问题最优解为0, 1,53,544321yyyy注：原问题与对偶问题最优目的函数值都是 z*=4+8+4=16式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi的意义代表在资源最优利用的条件

11、下对第i种资源的估价。这种估价不是资源的市场价钱，而是根据资源在消费中作出的奉献而作的估价，为区别起见，称为影子价钱。*1*1*wybxczmiiinjjj设 和 分别是原问题和对偶问题的最优解，那么由对偶性质，有), 1(*njxj), 1(*niyi 资源的影子价钱随企业的消费义务、产品构造资源的影子价钱随企业的消费义务、产品构造的改动而改动的改动而改动 影子价钱是资源的边沿价钱影子价钱是资源的边沿价钱 资源的影子价钱也可视为一种时机本钱资源的影子价钱也可视为一种时机本钱 在消费过程中假设某种资源未得到充分利用那在消费过程中假设某种资源未得到充分利用那么其影子价钱为零；只需在资源得到充分利

12、用么其影子价钱为零；只需在资源得到充分利用时，其影子价钱才能够非零时，其影子价钱才能够非零 利用影子价钱可以阐明：单纯形法中的检验数利用影子价钱可以阐明：单纯形法中的检验数可以看成消费某种产品的产值与隐含本钱的差可以看成消费某种产品的产值与隐含本钱的差 可以利用影子价钱确定企业内部的核算价钱，可以利用影子价钱确定企业内部的核算价钱，以便控制有限资源的运用和考核下属企业运营以便控制有限资源的运用和考核下属企业运营的好坏。的好坏。例1最优目的函数值的变化：8.5变到8.75，添加1/4资源的变化：设备B的可用时间从添加一小时参考文献：参考文献：李慧：资源影子价钱分析与运营管理决策，李慧：资源影子价

13、钱分析与运营管理决策，系统工程实际与实际，系统工程实际与实际，2003年年4月号，月号，22-26单纯形法求解的根本思绪单纯形法求解的根本思绪基可行解基可行解检验数非正检验数非正坚持解的可行性坚持解的可行性对偶单纯形法的根本思绪对偶单纯形法的根本思绪对偶问题基可行解对偶问题基可行解检验数非正检验数非正原问题基可行原问题基可行解解坚持对偶问题解的坚持对偶问题解的可行性检验数非可行性检验数非正正对偶问题可行解对偶问题可行解 坚持对偶问题有基可行解,而原问题只是根本解,经过迭代,使后者的负分量个数减少，一旦成为基可行解,那么原问题与对偶问题同时实现最优解. 顺应于求解这样的顺应于求解这样的LP问题：

14、规范化后不问题：规范化后不含初始基变量，但将某些约束条件两端含初始基变量，但将某些约束条件两端乘以乘以“-1后，即可找出初始基变量。后，即可找出初始基变量。 要求：初始单纯形表中的检验数满足最要求：初始单纯形表中的检验数满足最优性条件优性条件对满足上述条件的对满足上述条件的LP问题，对偶单纯形法的问题，对偶单纯形法的步骤是：步骤是：旋转运算。然后回到第旋转运算。然后回到第2步。步。作出初始单纯形表留意要求作出初始单纯形表留意要求检查检查b列的数据能否非负，假设是，表中曾列的数据能否非负，假设是，表中曾经给出最优解；否那么转下一步经给出最优解；否那么转下一步确定换出变量：取确定换出变量：取b列最

15、小的数对应的变量列最小的数对应的变量为换出变量为换出变量确定换入变量：用检验数去除以换出变量行确定换入变量：用检验数去除以换出变量行的那些对应的负系数，在除得的商中选取其的那些对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量中最小者对应的变量为换入变量例 用对偶单纯形法求解如下的LP问题0,1252652415min32132132321xxxxxxxxxxxz化成规范方式0,1252652415max3215321432321xxxxxxxxxxxxxw0,1252652415max3215321432321xxxxxxxxxxxxxw将各约束条件两端同乘“-1得用对偶单纯形法求

16、解得注：通常很少直接运用对偶单纯形法求解线性规划问题。灵敏度分析 将讨论将讨论LP问题中的参数问题中的参数 中有一个或几个发生改动时问题的最优中有一个或几个发生改动时问题的最优解会有什么变化，或者这些参数在一个解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不多大的范围内变化时，问题的最优解不变变ijijabc,研讨的思绪 将个别参数的变化直接在计算得到的最将个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需求终单纯形表中反映出来，这样就不需求从头计算，而直接检查在参数改动后最从头计算，而直接检查在参数改动后最终表有什么改动，假设仍满足最终表的终表有什么改动，假

17、设仍满足最终表的条件，那么表中仍给出最优解，否那么条件，那么表中仍给出最优解，否那么从这个表开场进展迭代求改动以后的最从这个表开场进展迭代求改动以后的最优解。优解。灵敏度分析的步骤灵敏度分析的步骤 将参数的改动计算反映到最终表上来。详细计将参数的改动计算反映到最终表上来。详细计算公式可以运用算公式可以运用 检查原问题能否仍为可行解检查原问题能否仍为可行解 检查对偶问题能否仍为可行解检查对偶问题能否仍为可行解 对检查情况按下表进展处置对检查情况按下表进展处置jBjjjjPBCcPBPbBb111原问题原问题对偶问题对偶问题结论或继续计算步骤结论或继续计算步骤可行解可行解可行解可行解问题的最优解或

18、最优基不变问题的最优解或最优基不变可行解可行解非可行解非可行解用单纯形法继续迭代求最优用单纯形法继续迭代求最优解解非可行解非可行解可行解可行解用对偶单纯形法继续迭代求用对偶单纯形法继续迭代求最优解最优解非可行解非可行解非可行解非可行解引进人工变量，编制新的单引进人工变量，编制新的单纯形表重新计算纯形表重新计算例：在第一章美佳公司的例例：在第一章美佳公司的例1中中1假设产品假设产品I的利润降至的利润降至1.5元元/件，而产件，而产品品 II的利润增至的利润增至2元元/件，美佳公司的最件，美佳公司的最优消费方案有何改动；优消费方案有何改动；2假设产品假设产品I的利润不变，那么产品的利润不变，那么产

19、品II的利润在什么范围变化时，该公司的最的利润在什么范围变化时，该公司的最优消费方案不发生变化优消费方案不发生变化21000CbXbbx1x2x3x4x50 x37 1/2 0012 1/2-7 1/22x13 1/2 1001/4- 1/21x21 1/2 010- 1/41 1/2000- 1/4- 1/2原最终单纯形表原最终单纯形表1改动后改动后0 x46004/51-61.5 x1210- 1/5012x23011/50000-1/100-1 1/2新的最优解为：0, 6, 0, 3, 254321xxxxx最优目的函数值为：9*z2改动后改动后为使表中的解仍为最优解必需为使表中的解仍

20、为最优解必需0231, 02141aa因此产品因此产品II的利润变化范围为的利润变化范围为232 a例：在第一章美佳公司的例例：在第一章美佳公司的例1中中1假设设备假设设备A与调试工序的每天才干不与调试工序的每天才干不变，而设备变，而设备B每天的才干添加到每天的才干添加到32小时，小时，分析公司最优方案的变化；分析公司最优方案的变化；2假设设备假设设备A和和B每天可用才干不变，每天可用才干不变，那么调试工序才干在什么范围变化时，那么调试工序才干在什么范围变化时，问题的最优基不变问题的最优基不变1b由由(15，24，5)T 变为变为(15，32，5)T 后，相应地最后，相应地最终表中终表中b列的

21、数据变为列的数据变为2/ 12/112/35532152/ 34/ 102/ 14/ 102/154/ 511bBb21000CbXbbx1x2x3x4x50 x317 1/20012 1/2-7 1/22 x15 1/21001/4- 1/21 x2- 1/2010- 1/41 1/2000- 1/4- 1/20 x312 1/2010107 1/22 x15110010 x420-401-60-100-2代入原最终表2设如今每天调试工序的时间为x，那么最终表中b列的数变为xxxxbBb2362162154524152/ 34/ 102/ 14/ 102/154/511故要使最优基不变必需6,4412