物流运筹学教学课件—线性规划的对偶问题

2.4 2.4 线性规划的对偶理论线性规划的对偶理论2.4.1 对偶问题2.4.2 对偶问题的基本性质2.4.3 影子价格2.4.4 对偶单纯形法2.4.1 对偶问题(1)(1)对偶问题的提出对偶问题的提出例例1 1、生产组织与计划问题、生产组织与计划问题A,BA,B各生产多少各生产多少,可获最大利润可获最大利润?可用资源可用资源煤煤劳动力劳动力仓库仓库A B1 23 20 2单位利润单位利润40 50306024Max Z=40 x1+50 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件如果因为某种原因，不愿意自己生产，而希望通如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应过将现有资源承接对外加工来获得收益，那么应如何确定各资源的如何确定各资源的使用价格使用价格？Max Z=40 x1+50 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件两个原则两个原则1.所得不得低于生产所得不得低于生产的获利的获利2.要使对方能够接受要使对方能够接受设三种资源的使用单价分别为设三种资源的使用单价分别为 y1,y2,y3y1 y2 y3生产单位产品生产单位产品A A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A A的获利的获利生产单位产品生产单位产品B B的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品B B的获利的获利y1+3 y2 40 2y1+2 y2+2y3 50 50通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W=30y1+60 y2+24y3根据原则根据原则2，对方能够接受的价格显然是越低越好，因此，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：此问题可归结为以下数学模型：Min W=30y1+60 y2+24y3 y1+3y2 402y1+2 y2+2y3 50y1,y2,y3 0s.t目标函数目标函数约束条件约束条件原线性规划问题称为原线性规划问题称为原问题原问题，此问题为此问题为对偶问题对偶问题，y1,y2,y3 称为称为影子价格影子价格(2)(2)对偶问题的形式对偶问题的形式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题为其对偶问题，其中为其对偶问题，其中yi(i=1,2,m)称为称为对偶变量对偶变量。上述对偶问题称为上述对偶问题称为对称型对偶问题对称型对偶问题。原问题简记为原问题简记为(P)，对偶问题简记为，对偶问题简记为(D)对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 Max Min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制2.4.2 对偶问题的基本性质定理定理1 1 对偶问题的对偶就是原问题对偶问题的对偶就是原问题Max W=-Ybs.t.-YA-CY0Min Z=-CXs.t.-AX-bX 0Max Z=CXs.t.AX bX 0Min W=Ybs.t.YA C Y0对偶的定义对偶的定义对偶的定义对偶的定义定理定理2 2(弱对偶定理弱对偶定理)分别为分别为(P),(D)的可行解，则有的可行解，则有C bX，yX y证明：由证明：由AX b,y 0 有有 yAX b y 由由 Ay C,X 0 有有 y A X C X所以所以C X y A X yb推论推论2、(P)有可行解有可行解,但无有限最优解，则但无有限最优解，则(D)无无可可行解。行解。定理定理3、yX,分别为分别为(P),(D)的可行解，且的可行解，且X yC=b,则它们是则它们是(P),(D)的最优解。的最优解。证明：对任证明：对任X，有，有CX b y=CXX最优最优推论推论1、(P),(D)都有可行解，则必都有最优解。都有可行解，则必都有最优解。定理定理4 4(主对偶定理主对偶定理)若一对对偶问题若一对对偶问题(P)(P)和和(D)(D)都有可行解，则它们都都有可行解，则它们都有最优解，且目标函数的最优值必相等。有最优解，且目标函数的最优值必相等。证明：证明：(1)当当X*和和Y*为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。最优解；对偶问题有下界，也存在有限最优解。(2)当当X*为原问题的一个最优解，为原问题的一个最优解，B为相应的最优基为相应的最优基,通通过引入松弛变量过引入松弛变量Xs,将问题将问题(P)转化为标准型转化为标准型令令令令所以所以Y*是对偶问题的可行解，是对偶问题的可行解，对偶问题的目标函数值为对偶问题的目标函数值为X*是原问题的最优解，原是原问题的最优解，原问题的目标函数值为问题的目标函数值为推论：推论：若一对对偶问题中的任意一个有最优解，则另一个若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：1.1.都有最优解，且目标函数最优值相等；都有最优解，且目标函数最优值相等；2.2.两个都无可行解；两个都无可行解；3.3.一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。n从两图对比可明显看到原问题无界，其对偶问题无可行解y1y2n例4 已知线性规划问题max z=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。n上述问题的对偶问题为min w=2y1+y2-y1-2y21y1+y21y1-y20y1，y20由第1约束条件，可知对偶问题无可行解；原问题虽然有可行解，但无最优解。n例5 已知线性规划问题min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。n例5 已知线性规划问题 解：先写出它的对偶问题max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20n例5 已知线性规划问题 将y1*=4/5,y2*=3/5的值代入约束条件，得=1/53，=17/55，=7/52 它们为严格不等式；由互补松弛性得 x2*=x3*=x4*=0。因y1，y20；原问题的两个约束条件应取等式，故有 x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为 X*=(1，0，0，0，1)T；w*=5定理定理5 若若 X,Y分别为分别为(P),(D)的可行解，则的可行解，则X,Y为为最优解的充要条件是最优解的充要条件是同时同时成立成立证证:(:(必要性）必要性）原问题原问题 对偶问题对偶问题 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0 0，另一个一定等于，另一个一定等于0 0影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0 02.4.3 影子价格变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。n例1的影价格及其经济解释。由表1-5可知cj23000 CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。n第1章中例1的影价格及其经济解释。这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。从图2-1可看到，设备增加一台时，代表该约束条件的直线由移至，相 应 的 最 优 解 由(4，2)变 为(4，2.5)，目 标 函 数z=24+32.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由移至，相应的最优解从(4，2)变为(2.4.25，1.875)，目标函数z=2.4.25+31.875=12.4.125。比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由移至，这时的最优解不变。n例1的影价格及其经济解释。nyi*的值代表对第i种资源的估价影子价格。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。2.影子价格在经济管理中的应用影子价格在经济管理中的应用影子价格在经济管理中的应用很多（1）影子价格能指示企业内部挖潜的方向 1）影子价格越高的资源，表明它对目标增益影响越大，同时也表明这种资源对该企业来说越稀缺和越贵重，企业的管理者就应该重视对这种资源的管理，通过挖潜革新、降低消耗或及时补充该种资源，以保证给企业带来较大的收益。即对影子价格大于零的资源都应采取措施，增加投入，以保证生产正常进行，实现利润最大化。2）对影子价格为零的资源，企业的管理者也不应忽视，这种资源对该企业来说是相对富裕的。一方面，可以向别的企业转让这种资源或者以市场价出售，以免形成积压浪费；另一方面，通过企业内部的改造、挖潜和增加对影子价格大于零的资源的投入后，使原有的剩余资源又可以得到充分利用，而变为新的紧缺资源（变为影子价格大于零）。这样不断调整、补充，真正实现资源的合理利用。（2）影子价格在企业经营决策中的作用 因为影子价格不是市场价格，它是根据企业本身的资源情况bi、消耗系数a ij和产品的利润cj 计算出来的一种价格，是新增资源所创造的价值，是边际价格。不同的企业，即使是相同的资源（例如钢材），其影子价格也不一定相同。就是同一企业，在不同的生产周期，资源的影子价格也不完全一样。因此，企业的决策者可以把本企业资源的影子价格与当时的市场价格进行比较。1）当i种资源的影子价格高于市场价格时，则企业可以买进该种资源；2）当某种资源的影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，