规划数学对偶理论.ppt

第1章 线性规划,线性规划模型及单纯形法（4学时）对偶理论及灵敏度分析（2学时）,第3讲 对偶理论,对偶问题的提出线性规划的对偶理论对偶问题的经济解释-影子价格,重 点：对偶问题，对偶理论，难 点：对偶理论应用基本要求：掌握对偶关系，理解对偶性质，会求影子价格，,引例：经营策略问题。甲工厂有设备和原料A、B 这些设备和原料可用于、两种产品的加工，每件产品加工所需机时数，原料A、B消耗量，每件产品的利润值及每种设备的可利用的机时数如下表。现在乙厂和甲厂协商，打算租用甲厂的设备购买资源A和B。问甲厂采取哪种经营策略，是自己生产产品还是出租设备、出让原材料？如果出租设备、出让原材料，在和乙厂协商时出租设备和出让原材料A,B的底价应是多少？,对偶问题的提出,自己生产：,原问题,引例分析：,设y1,y2和y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额,=80y1+160y2+120y3,出售资源,对偶问题,显然商人希望总的收购价越小越好,工厂希望出售资源后所得不应比生产产品所得少,目标函数 min,例1,它的对偶问题是：,YA C,min=Yb,Y0,Y=（y1，y2，y3）,1 原问题与对偶问题的关系(对称形式),线性规划的对偶理论,原关系,minw,对偶关系,maxz,x,y,原问题与对偶问题的对称形式,标准(max,)型的对偶变换,目标函数由 max 型变为 min 型对应原问题每个约束行有一个对偶变量 yi，i=1,2,m对偶问题约束为 型，有 n 行原问题的价值系数 C 变换为对偶问题的右端项原问题的右端项 b 变换为对偶问题的价值系数原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义,原问题与对偶问题的结构关系,原问题与对偶问题中的目标函数的优化方向相反（前者为极大，后者为极小）原问题的每个约束条件对应于对偶问题的一个决策变量，且约束条件的资源系数（右端的常数项）为相应决策变量的价值系数原问题的每个决策变量对应于对偶问题的一个约束条件，且决策变量的价值系数为相应约束条件的右端常数项对偶问题中的系数矩阵为原问题中的系数矩阵的转置原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量取非负约束，原问题中决策的对偶问题非负约束在对偶问题中体现为相应的约束条件取大于等于符号,非标准型的对偶变换,对偶变换的规则,max=5y1+4y2+6y3,y1+2y2,y1+y3,-3y1+2y2+y3,y1-y2+y3,=,2,3,-5,1,y1 0，,y2 0,y3无约束,对偶问题,例3 写出线性规划问题的对偶问题,minz=2x1+3x2-5x3+x4,原问题,（1）对称性：对偶的对偶就是原始问题,2 对偶问题的基本性质,为了便于讨论，下面不妨总是假设,(2)弱对偶性:若 是原问题的可行解，是对偶问题的可行解。则存在,弱对偶定理推论,原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限如果原(对偶)问题为无界解，则其对偶(原)问题无可行解如果原(对偶)问题有可行解，其对偶(原)问题无可行解，则原问题为无界解当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解,(3)强对偶性,证：由弱对偶定理推论1，结论是显然的。,若是原问题的可行解，是对偶问题可行解，当,分别是相应问题的最优解,是使目标函数取最小值的解，因此是最优解,可行解是最优解的性质(最优性准则定理),(4)对偶定理,若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等.,第1部分:证明两者均有最优解,证明分两部分,由于原问题和对偶问题均可行,根据弱对偶性,可知两者均有界,于是均有最优解.,第2部分:证明有相同的目标函数值,设 为原问题的最优解,它所对应的基矩阵是B，,则其检验数满足 C CBB1A 0,因此有对偶问题目标函数值,而原问题最优解的目标函数值为,显然 为对偶问题的可行解。,证毕,故由最优解准则定理可知 为对偶问题的最优解.,对偶定理推论,根据对偶定理第2部分的证明,可以得出:若互为对偶的线性规划问题中的任一个有最优解,则另一个也有最优解,且目标函数值相等.综上所述,一对对偶问题的解必然是下列三种情况之一:原问题和对偶问题都有最优解一个问题具有无界解,另一个问题无可行解原问题和对偶问题都无可行解,(5)互补松弛定理,证：由定理所设，可知有,设,分别是原问题和对偶问题的可行解，为原问题的松弛变量的值，为对偶问题剩余变量的值。,分别是原问题和对偶问题最优解的充分必要条件是,分别以 左乘(1)式，以 右乘(2)式后，两式相减，得,根据最优解判别定理，分别是原问题和对偶问题最优解。反之亦然。,证毕。,（1）,（2）,max z=CXs.t.AX+XS=bX,XS 0,min w=Ybs.t.AY-YS=CY,YS 0,XYS=0YXS=0,m,n,=,Y,YS,A,-I,C,n,=,A,XS,I,b,n,m,m,X,原始问题和对偶问题变量、松弛变量的维数,原始问题和对偶问题最优解之间的互补松弛关系,maxz=CX s.t.AX+XS=b X,XS0,min w=bYs.t.AY-YS=C Y,YS0,maxz=CXs.t.AXb X 0,min w=bYs.t.AYC Y0,互补松弛关系,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,原始问题的变量,对偶问题的松弛变量,(6)原问题单纯形表检验数行与对偶问题解的关系,原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然,原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解,0,证：标准化后的原问题和对偶问题的表达式为：,若B是A中的一个基，A=（B，N）,原问题解为XB=B-1b，,N=CN-CBB-1N，,Z=CBB-1b,对偶问题的约束条件：,检验数：,B=CB-CBB-1B=0，,N=CN-CBB-1N，,S=CBB-1,原问题单纯形表检验数行与对偶问题解的关系,结论：,单纯形表中的检验数行和对偶问题的解仅差一个符号,yi等于原问题的第i个方程中的松弛变量所对应的检验 数的负数,单纯形法迭代时，原问题解为基可行解，相应的检验数对应对偶问题的一个解，在原问题没有得到最优解之前，对偶问题的解为非可行解,基可行解,基可行解,非可行解,基可行解,目标函数,对偶问题,原问题,无可行解,无界解,原问题为可行解时，对偶问题不一定有可行解，当原问题为最优解，对偶问题一定有最优解,例4,试用对偶理论证明该线性规划问题无最优解。,证：该问题存在可行解，X=（0，0，0）；对偶问题为：,由第一个约束条件可知对偶问题无可行解，因此，原问题有可行解，无最优解。,例5：,试用对偶理论找出原问题的最优解。,解：原问题的对偶问题为：,已知其对偶问题的最优解为：,代入对偶问题的约束条件，,得2,3,4式为严格不等式，由互补松弛性得,因,原问题的约束条件应取等式为：,求解后得到,原问题的最优解为:,原问题的最优解为:Z*=CBB-1b=CX*=Y*b,对偶问题的经济解释-影子价格,z=CX=CBB-1b+NXN=CBB-1b,N=CN-CBB-1N,Y=CBB-1为单纯形乘子,当b为变量的情况下,当bi发生变化:,yi的经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化.yi是bi的一种估价,估价是有条件的替代方案.,于是，当某个右端常数bi变为bi时，原问题的目标函数最优值变为：,称对偶变量yi(i=1,2,m)表示原问题的第i个约束条件的影子价格.,影子价格在经济管理中的应用,(1)影子价格能指示企业内部挖潜的方向.,注意:对于影子价格为零的资源企业的资源不一定有剩余.如果有剩余,企业应该充分利用剩余的资源,开辟新的生产途径,以增加企业的总收益.,影子价格越高的资源,说明它对目标增益的影响越大,同时也表明这种资源越稀缺和贵重.,企业的管理者要重视这种资源的管理,挖掘潜力,及时组织资源,由此可以给企业带来较大的收益.,影子价格可以作为企业在接受外协加工任务时,对外协单位使用资源的收费标准,按照影子价格收费,保证了企业与外协单位双方平等互利的格局,可以促进双方合作.,(2)影子价格指导企业间的分工与协作.,(3)影子价格在新产品开发决策中的应用,A,B,B单位产品的机会成本=23/4+10+41/4=5/2,两种新产品A,B的机会成本为:,A单位产品的机会成本=13/4+20+31/4=3/2,由于投产A产品所能提供的单位利润不大于投产的机会成本,因此从经济上分析,A产品不宜投产;而B产品的机会成本小于该产品投产后所能提供的利润,因此投产B产品可以给工厂带来较大的收益.如果新产品B确实为社会所欢迎,而在资源利用上与老产品发生冲突,工厂可以考虑用B产品去更换老产品,以获得更大的经济效益.,(4)影子价格在资源购销决策中的应用.,当资源的市场价格低于影子价格,企业买进该资源,扩大生产,当资源的市场价格高于影子价格,企业应设法转让该资源.,产品价格的变动会影响到影子价格的大小,从而对资源的稀缺性产生影响.,例如设工厂现有钢材100吨，其影子价格为3/4，采用新工艺后，钢材可以节约2%，则由此带来的经济收益为：1003/42%=3/2(万元),(5)利用影子价格分析现有产品价格变动对资源紧缺情况的影响.,(6)利用影子价格分析工艺改变后对资源节约的收益,原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min,资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,y1y2ym,产品的机会成本,机会成本表示减少一件产品所节省的资源可以增加的利润,机会成本,利润,差额成本,产品的差额成本（Reduced Cost）,差额成本=机会成本-利润,互补松弛关系的经济解释,在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于或小于利润（4）机会成本大于利润的产品不安排生产,灵敏度分析所要解决的问题：系数在什么范围内变化，不会影响已获得的最优基(即最优解或最优解结构不变)。如果系数的变化超过以上范围，如何在用最简便的方法在原来最优解的基础上求得新的最优解当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。,灵敏度分析(优化后分析),系数变化后最终表的几种情况,最终表最优基B的逆B-1的位置,注意:最终表最优基B的逆B-1在最终单纯形表的位置与初始单纯形表中初始基所在的位置相对应,