《管理运筹学》课件03-对偶原理.ppt

,第 3 章,Dual Principle,DP,对偶原理,第3章 对偶原理,2,3.1 线性规划的对偶关系3.2 线性规划的对偶性质3.3 对偶关系的经济解释3.4 对偶单纯形法3.5 交替单纯形法,第3章 对偶原理,第3章 对偶原理,3,3.1 线性规划的对偶关系,3.1.1 对偶问题,y1 y2 y3,由于原拟用于生产每件甲产品的1个A工时和3个c工时能创造3百元利润，所以出租上述数量的各资源的盈利起码应不低于3百元。,1y1+0y2+3y3 3,0y1+2y2+4y3 5,w=8y1+12y2+36y3,y1，y2，y3 0,第3章 对偶原理,4,3.1 线性规划的对偶关系,min w=8y1+12y2+36y3 y1+3y3 3 2y2+4y3 5 y1,y2,y3 0,s.t.,Y*=(0,1/2,1)T w*=42,X*=(4,6)T,z*=42,第3章 对偶原理,5,3.1 线性规划的对偶关系,3.1.2 对偶关系,关系1：规范对偶关系,(P1):,(D1):,我们称LP问题(P1)与(D1)为规范原始、对偶问题，并称二者之间的对应关系为规范对偶关系。,第3章 对偶原理,6,3.1 线性规划的对偶关系,1y1+0y2+3y3 3,0y1+2y2+4y3 5,min w=8y1+12y2+36y3,y1，y2，y3 0,s.t.,min 型,第3章 对偶原理,7,3.1 线性规划的对偶关系,关系2：标准形LP问题的对偶关系,第3章 对偶原理,8,3.1 线性规划的对偶关系,例1 max z=3 x1-1 x2-2 x3 3 x1+2 x2-3 x3=6 1 x1-2 x2+1 x3=4 x1,x2,x3 0,min w=6y1+4y2 3 y1+1 y2 3 2 y1-2 y2-1-3 y1+1 y2-2 y1,y2 自由,s.t.,s.t.,y1 y2,第3章 对偶原理,9,3.1 线性规划的对偶关系,关系3：一般对偶关系,第3章 对偶原理,10,3.1 线性规划的对偶关系,例2,max z=2y1+5y2+1y3 2 y1+3 y2+1y3 3 1 y1-5 y2+1y3 2 3 y1+1y3-1,=,y1 0,y2 0,y3自由,s.t.,解,第3章 对偶原理,11,3.2 线性规划的对偶性质,性质1 对称性 规范原始、对偶问题(P1)与(D1)互相对偶。性质2 弱对偶性 设X,Y分别为(P1)与(D1)的任意可行解，则 CTX bTY 性质3 最优性 设X,Y分别为(P1)与(D1)的任意可行解，则当 CTX=bTY 时，X,Y分别是(P1)与(D1)的最优解。,第3章 对偶原理,12,3.2 线性规划的对偶性质,性质4 线性规划的对偶定理 对(P1)与(D1)而言：(1)若其中一个问题有最优解，则另一个问题也有最优解，且二者最优值相等。（强对偶性）(2)若其中一个问题的解无界，则另一个问题无可行解。（无界性）注意：(2)之逆命题不成立。因为一个问题无可行解时，另一个问题可能解无界，也可能无可行解。,第3章 对偶原理,13,3.2 线性规划的对偶性质,性质5 兼容性 原始问题的检验矢给出对偶问题的一个基本解。,X*=(4,6,4,0,0)T,z*=42,y1,y2,y3,y4,y5,Y*=(0,1/2,1,0,0)T,w*=42,3,4,5,1,2,互补基本解,yi=n+i i=1,2,m,ym+j=j j=1,2,n,第3章 对偶原理,14,3.2 线性规划的对偶性质,X*=(4,6)T,Y*=(0,1)T,*b(4,6,4,0,0)T,*=(0,1,0,0)T,z*=42=w*,第3章 对偶原理,15,3.2 线性规划的对偶性质,(P)的基本解 与(D)的基本解 相互对应,且二者目标值相等。我们把这样一对基本解 与，称为(P)与(D)的互补基本解。,第3章 对偶原理,16,3.2 线性规划的对偶性质,6.互补松弛性 设=(x1,x2,xn,xn+1,xn+m)T=(y1,y2,ym,ym+1,ym+n)T是(P1)(D1)的一对互补基本解，那么,xj ym+j=0，j=1,2,n xn+i yi=0，i=1,2,m特别对非退化 的 和，若 可行，则有 xj 0 ym+j=0，j=1,2,n xn+i 0 yi=0，i=1,2,m若 可行，则有 ym+j 0 xj=0，j=1,2,n yi 0 xn+i=0，i=1,2,m,第3章 对偶原理,17,3.2 线性规划的对偶性质,7.互补松弛性 设,分别是(P1)(D1)的可行解，那么 和 分别是(P1)(D1)最优解的充分必要条件是：,xn+i 0 yi=0 yi 0 xn+i=0,xj 0 ym+j=0 ym+j0 xj=0,j=1,2,n,i=1,2,m,第3章 对偶原理,18,3.3 对偶关系的经济解释,根据对偶性质，线性规划的互补基本解目标函数值 z=cjxj bi yi=w 求z关于bi的偏导数，得,=yi,可见，对偶变量 yi 在经济上表示原始问题第 i 种资源的边际价值,即当bi单独增加一个单位时，相应的目标值z的增量z；特别对最优解来说，对偶变量的值 yi*所表示的第 i 种资源的边际价值，称为影子价值。,相等：,=,z,第3章 对偶原理,19,3.3 对偶关系的经济解释,3.3.1 对偶变量的经济解释 当目标函数值 z 表示总产值时，yi*相应地称为影子价格；当z 表示总利润时，yi*相应地称为影子利润。一、当 yi*代表影子价格（即企业的目标是实现最大总产值）时(1)对资源 i 总存量的评估。设资源 i 的市场价格为pi，那么，当 yi*pi 时，企业可以买进该资源，即增加其总存量；当 yi*pi 时，企业可以卖出该资源，即减少其总存量；这样做在经济上是合算的。,第3章 对偶原理,20,3.3 对偶关系的经济解释,(2)对资源 i 现行分配量的评估。当资源 i 在市场上脱销时，其总存量无法增加，但可酌情调整其在企业内部的现行分配量，以便获得最佳经济效益。二、当 yi*代表影子利润（即企业的目标是实现最大总利润）时：(1)对资源 i 总存量的评估。(2)对资源 i 现行分配量的评估。,第3章 对偶原理,21,3.3 对偶关系的经济解释,3.3.2 对偶问题的经济解释,由前已知:yi 一个单位的资源 i 对总产值 的贡献 bi 在这n项经营活动中，资源 i 的投入量 cj 一个单位的第 j 项经营活动所创造的产值 aji 一个单位的第 j 项经营活动消耗的资源 i 的数量 所以式意味着：这m种资源对一个单位的第 j 项经营活动的贡献，至少应当跟经营一个单位的第 j 项活动所创造的产值一样多,否则，这些资源的利用就未臻尽善。,问题(D1):,第3章 对偶原理,22,3.3 对偶关系的经济解释,而式意味着：资源 i 对产值的单位贡献不得为负，否则就不能利用这种资源。式意味着：测定各项经营活动所消耗的各种资源的总的隐含价值所能接受的最低限度。,3.3.3 互补松弛性的经济解释,考虑性质 7(1)：xj 0 ym+j=0 因有,所以 ym+j=0 必然导致,因此，性质7(1)的经济解释是:当一个单位的任一经营活动 j在严格正水平(xj 0)上经营时，它所消耗的各种资源的边际价值总和必定等于该项活动所产生的单位价值 cj。,第3章 对偶原理,23,3.3 对偶关系的经济解释,譬如范例，已知X*=(4,6,4,0,0)T，Y*=(0,1,0,0)Tx1=4 0 y4=0，则使 y1+3y3-y4=3 y1+3y3=3 类似考虑性质7(4)：xn+i 0 yi=0,i=1,2,m 其中 xn+i 是 约束 i 的松弛变量，而 xn+i 0 意味着 约束 i 有松弛部分.因此，性质7(4)的经济解释是：当资源 i 的供量未被各项经营活动耗尽时，该种资源的边际价值必定为0。按供求规律，供应过剩的货物必然跌价，以至无利可赚，甚至蚀本。譬如范例：xn+1=x3=4 0，这说明 A工时 这种资源的供量除满足甲、乙产品之需外，还多余4个工时，这就导致它的影子利润 y1=0。这意味着即便再增加它的供量，对甲、乙产品的总利润也毫无贡献,即无利可赚。,第3章 对偶原理,24,3.4 对偶单纯形法,基本思路：互补基本解均为可行必然均为最优,原始SM,前 提（始终保持）,基本解的进化路线,原始可行b 0,对偶可行 0,对偶SM,无解的判断及结果,原始解无上界对偶无可行解,原始无可行解对偶解无下界,第3章 对偶原理,25,3.4 对偶单纯形法,3.4.1 规范对偶单纯形法1把m阶LP问题化成标准形（允许其右端常数为负）,在其系数阵中找出或构造一个m阶排列阵作初始基,建立初始单纯形表。若所有检验数 j0，则转2;否则需采用人工对偶单纯形法或其他算法。2最优性检验：检查表中解列各数值bi；若所有bi0,则问题已得最优解，停止计算;否则转3。3无可行解判断：只要存在一个br0，它所在行中所有 arj0，则原始问题无可行解，对偶问题无下界，停 止；否则转4。,第3章 对偶原理,26,3.4 对偶单纯形法,4确定主元：先确定离基变量，按 min bibi 0=bl 确定第 l 行的基变量 xBl 离基，第 l 行为主行；后确定进基变量，按最大比值规则：max j/aljalj 0=k/alk 确定进基变量 xk 及主元 alk。5按主元 alk 对当前表格进行一次换基运算，得到一个新单纯形表，返2。,第3章 对偶原理,27,3.4 对偶单纯形法,例3,解,max z=-3x1-2x2,s.t.,2x1+3x2+x3=18 x1-x2 x4=2 x1+3x2 x5=10 x1,x2,x3,x4,x5 0,x1+x2+x4=2,x13x2+x5=10,第3章 对偶原理,28,3.4 对偶单纯形法,-3,-2/3,max,-3,比 值,第3章 对偶原理,29,3.4 对偶单纯形法,cj,基,解,x1 x2 x3 x4 x5,-3-2 0 0 0,2 3 1 0 0,x3x4x5,18-2-10,-1 1 0 1 0,000,-1-3 0 0 1,0 3 2 0 0 0,-3,x3x1 x2,0-3-2,4 1 0 0-3/4-1/4,4 0 0 1 3/4 5/4,2 0 1 0 1/4-1/4,-16 0 0 0 7/4 5/4,x3x4x2,0 0-2,8 1 0 1 0 1,10/3 1/3 1 0 0-1/3,-20/3 7/3 0 0 0 2/3,-16/3-4/3 0 0 1 1/3,-4/3,X*=(4,2)Tz*=16,第3章 对偶原理,30,3.4 对偶单纯形法,3.4.2 人工对偶单纯形法 当获得排列阵形式的初始基时，若检验数不全非负，就需要引进一个人工变量 x0 0，并引进一个人工约束：,(3-7),x0+x j1+x j2+x jt=M,其中,x jr 一切负检验数对应的变量(r=1,2,t),从中找出最小检验数对应的变量 xp，并将(3-7)改写成,(3-8),第3章 对偶原理,31,3.4 对偶单纯形法,将其代入目标函数和除(3-7)以外的各约束中,得到人工问题.建立初始单纯形表，必然所有检验j 0.以下可按规范对偶单纯形法的步骤运行，但 2须作以下调整：2若解列存在 bi 0，则转3;否则停止迭代.这时,若除了人工变量 x0 以外，其他变量取值均为有限，则得到原问题的最优解；否则原问题为解无界。,第3章 对偶原理,32,3.4 对偶单纯形法,例4,解 标准化,(3-9),第3章 对偶原理,33,3.4 对偶单纯形法,以 x4，x5，x6 为基变量，算得非基变量的检验数：1=-3 0，3=-1 0因1，3为负，故引入人工约束 x0+x 1+x 3=M(a)因最小检验数为1=-3，故将上式改写成x 1=M-x0-x 3 代入(3-9)中，并添上人工约束(a)，得人工问题：,第3章 对偶原理,34,3.4 对偶单纯形法,max z=-3x0-2 x2-2x3+3M,s.t.,x0-x2+2x3+x4=M-4-2 x0+3x2-x3+x5=-2M+20-3 x0+x2-2x3+x6=-3M+28 x0+x1+x3=M x0,x1,x2，x3,x4，x5，x6 0,第3章 对偶原理,35,3.4 对偶单纯形法,1 0-1 2 1 0 0,x4x5 x6 x1,M-4-2M+20-3M+28M,-2 0 3-1 0 1 0,00 00,-3 0 1-2 0 0 1,1 1 0 1 0 0 0,3M 3 0 2 2 0 0 0,28 0 0 3 0 0 0 1,x4x5x0 x1,00-30,M-28/3 1 0-1/3 2/3 0 0-1/3,16/3 0 0-2/3 4/3 1 0 1/3,4/3 0 0 7/3 1/3 0 1-2/3,28/3 0 1 1/3 1/3 0 0 1/3,基,解,x0 x1 x2 x3 x4 x5 x6,-3 0-2-2 0 0 0,cj,-3,1/3,第3章 对偶原理,36,3.4 对偶单纯形法,0-2-30,x4x3x0 x1,4 0 0 7 1 0 3-2,0 0 0-10 0 1-4 3,M-12 1 0-5 0 0-2 1,8 0 1-2 0 0-1 1,28 0 0 3 0 0 0 1,X1*=(28/3,0,0)T,X2*=(8,0,4)T,z*=28,第3章 对偶原理,37,3.4 对偶单纯形法,X*=(8+4/3,0,4-4)T,0,1,第3章 对偶原理,38,3.5 交替单纯形法,当获得排列阵初始基并构成初始单纯形表时，若互补基本解既非原始可行又非对偶可行，则可交替使用两种单纯形法，先把单纯形表化成原始可行或对偶可行，然后再按原始单纯形法或对偶单纯形法继续迭代，直到求解结束。此即交替单纯形法。,第3章 对偶原理,39,3.5 交替单纯形法,例6,解 标准化：,max z=x1+2x2,s.t.,-x1+x2+x3=-1-2x1-x2+x4=-2 x1,x2,x3,x4 0,第3章 对偶原理,40,cj,基,解,x1 x2 x3 x4,1 2 0 0,-1 1 1 0,x3x4,-1-2,-2-1 0 1,00,0-1-2 0 0,-1,x3 x2,02,2 2 1 0-1,x1x2,1 2,-3-3 0 1 1,4 3 0 0-2,-3,1 1 0-1/3-1/3,0 0 1 2/3-1/3,1 0 0 1-1,解无界,3.5 交替单纯形法,尚不能判定解无界,第3章 对偶原理,41,3.5 交替单纯形法,另例,标准化：,max z=x1-x2,s.t.,2x1+3x2+x3=-2 x1+2x2+x4=1 x1,x2,x3,x4 0,第3章 对偶原理,42,3.5 交替单纯形法,无可行解,cj,基,解,1-1 0 0,x1 x2 x3 x4,2 3 1 0,-1 1 3/2 1/2 0,2 0 1/2-1/2 1,-2 1,x3x4,00,0,-1 1 0 0,1 2 0 1,x1x4,10,-1 0 5/2 1/2 0,尚不能判定无可行解,