运筹学_对偶问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章,LP,的对偶理论与灵敏度分析,线性规划的对偶问题,I,II,每天可用能力,设备,A,（,h,）,设备,B,（,h,）,调试工序（,h,）,0,6,1,5,2,1,15,24,5,利润（元）,2,1,问,公司应每天制造两种家电各多少件，使获取的利润最大。,例,1,问题,美佳公司愿意以多大的代价出让自己所拥有的生产资源？,设,y,1,y,2,和,y,3,分别表示出让资源,A,，,B,和调试工序的单价，则美佳公司同意出让的条件将是,同意出让生产产品,I,的资源,同意出让生产产品,II,的资源,购买者希望用最少的代价获得这些资源,，因此,这样得到一个新的线性规划问题,称这一,问题是原来的,LP,问题的,对偶线性规划问题,或,对偶问题,，原来的,LP,问题也称为,原问题,。,LP,问题的对称形式,变量,：所有变量均具有非负约束,约束条件,：,最大化问题 所有约束条件都是“,”型的,最小化问题 所有约束条件都是“,”型的,对称形式下的对偶关系,项目,原,问题,对偶问题,A,b,C,目标函数,约束条件,决策变量,约束条件系数矩阵,约束条件右端项向量,目标函数系数向量,max,z,=,CX,AX,b,X,0,约束条件系数矩阵转置,目标函数的系数向量,约束条件的右端项向量,min,w,=,Yb,AY,C,Y,0,原问题,max z,对偶问题,min w,n,个决策变量,m,个约束条件,n,个约束条件,m,个决策变量,约束条件“,”型,决策变量,0,决策变量,0,约束条件“,”型,对称形式的对应关系,对偶问题的对偶是原问题，即对偶关系是相互对称的关系,非,对称形式下的对偶关系,原问题,（对偶问题）,max z,对偶问题,（原问题）,min w,n,个决策变量,m,个约束条件,n,个约束条件,m,个决策变量,约束条件“,”型,约束条件“,”型,约束条件“,=”,型,决策变量,0,决策变量,0,决策变量无约束,决策变量,0,决策变量,0,决策变量无约束,约束条件“,”型,约束条件“,”型,约束条件“,=”,型,单纯形法的矩阵表示,添加松弛变量,X,S,将,X,B,的系数矩阵化为单位矩阵,C,B,C,N,0,X,B,X,N,X,S,0 X,S,b,B N I,C,B,C,N,0,C,B,C,N,0,X,B,X,N,X,S,C,B,X,B,B,-1,b,I B,-1,N B,-1,0 C,N,C,B,B,-1,N C,B,B,-1,初始单纯形表,迭代后的单纯形表,在,初始单纯形表中单位矩阵经过迭代后变为基矩阵,B,的逆,在初始单纯形表给出的解中基变量,X,s,=b,而在迭代后的表给出的解中基变量,X,B,=B,-1,b,系数矩阵的变化,:A,I,B,-1,A,I,在初始单纯形表中变量,x,j,的系数为,P,j,经过迭代后变为,P,j,并且,P,j,=B,-1,P,j,若,迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解,项目,原,问题变量,原,问题松弛变量,x,1,x,2,x,3,x,4,x,5,x,3,15/2,0 0,1 5/4 15/2,x,1,7/2,1 0,0 1/4 -1/2,x,2,3/2,0 1,0 -1/4 3/2,-,j,0 0,0 1/4 1/2,对偶问题剩余变量,对偶问题变量,y,4,y,5,y,1,y,2,y,3,项目,对偶问题变量,对偶问题剩余变量,y,1,y,2,y,3,y,4,y,5,y,2,1/4,-5/4 1 0,-1/4 1/4,y,3,1/2,15/2 0 1,1/2 -3/2,j,15/2 0 0,7/2 3/2,原问题松弛变量,原问题变量,x,3,x,4,x,5,x,1,x,2,原问题最终单纯形表,对偶问题最终单纯形表,例1,最大化问题检验数的相反数给出了对偶问题的解,原本在对偶关系中，原问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。但,在分别添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系,原问题,对偶问题,第,i,个约束条件中添加的松弛变量,第,i,个对偶变量,第,j,个变量,第,j,个约束条件中添加的松弛变量,注 上表中我们将松弛变量与剩余变量统称为松弛变量,对偶问题的基本性质,弱,对偶性,原问题可行解的目标函数不超过对偶问题可行解的目标函数,弱,对偶性的推论,（,1,）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是原问题目标函数值的上界。,（,2,）如原问题有可行解且目标函数无界（即原问题为无界解），则对偶问题无可行解；反之对偶问题有可行解且目标函数无界，则原问题无可行解。注意该推论的逆命题不成立。,（,3,）若原问题有可行解而对偶问题无可行解，则原问题目标函数无界；反之对偶问题有可行解而原问题无可行解，则原问题目标函数无界。,最优性,若原问题一个可行解目标函数等于对偶问题的某个可行解的目标函数,则这两个可行解分别是原问题和对偶问题的最优解,强对偶性,若原问题和对偶问题都有可行解,则它们都有最优解,且最优解的目标函数值相等,互补松弛性,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则其对应的约束条件取等式,;,反之若一个约束条件为严格的不等式,则其对应的对偶变量为零,互补松弛性的另一种表述,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零,;,反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。,例（,p76.7,）,原,问题,对偶问题,将原,问题最优解,X*=(2,2,4,0),代入原问题约束条件中得,第一个约束条件：,2+6=8,，为等式,第二个约束条件：,4+2=6,，为等式,第三个约束条件：,2+4=6,，为等式,第四个约束条件：,2+2+40,得,而由,x,2,=20,得,而由,x,3,=40,得,于是得到方程组,得,对偶问题最优解为,注：原问题与对偶问题最优目标函数值都是,z*=4+8+4=16,第三节 影子价格,式中,b,i,是线性规划原问题约束条件的右端项，它代表第,i,种资源的拥有量；,对偶变量,y,i,的意义代表在资源最优利用的条件下对第,i,种资源的估价,。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为,影子价格,。,设 和 分别是原问题和对偶问题的最优解，则由对偶性质，有,资源的影子价格随企业的生产任务、产品结构的改变而改变,影子价格是资源的,边际价格,资源的影子价格也可视为一种,机会成本,在生产过程中若某种资源未得到充分利用则其影子价格为零；只有在资源得到充分利用时，其影子价格才可能非零,利用影子价格可以说明：单纯形法中的检验数可以看成生产某种产品的产值与隐含成本的差,可以利用影子价格确定企业内部的核算价格，以便控制有限资源的使用和考核下属企业经营的好坏。,例,1,Max,z=,2,x,1,+x,2,s.t.5,x,2,15,6,x,1,+2,x,2,24,x,1,+,x,2,5,x,1,x,2,0,x,2,=3,6,x,1,+2,x,2,=,24,x,1,+,x,2,=5,最优解,可行域,最优目标函数值的变化：,8.5,变到,8.75,，增加,1/4,资源的变化：设备,B,的可用时间从增加一小时,参考文献：,李慧：资源影子价格分析与经营管理决策，,系统工程理论与实践,，,2003,年,4,月号，,22-26,第四节 对偶单纯形法,按,对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最终表不但给出了原问题的最优解，而且其检验数的相反数就是对偶问题的最优解。,单纯形法求解的基本思路,基,可行解,检验数非正,保持解的可行性,对偶单纯形法的基本思路,对偶问题基可行解,（检验数非正）,原,问题基可行解,保持对偶问题解的可行性（检验数非正,（对偶问题可行解）,保持对偶问题有基可行解,而原问题只是基本解,通过迭代,使后者的负分量个数减少，一旦成为基可行解,则原问题与对偶问题同时实现最优解,.,对偶单纯形法计算步骤,适应于求解这样的,LP,问题：,标准化后不含初始基变量，但将某些约束条件两端乘以“,-1”,后，即可找出初始基变量。,要求：,初始单纯形表中的检验数满足最优性条件,对满足上述条件的,LP,问题，对偶单纯形法的步骤是：,旋转运算。然后回到第,2,步。,作出初始单纯形表（注意要求）,检查,b,列的数据是否非负，若是，表中已经给出最优解；否则转下一步,确定换出变量,：取,b,列最小的数对应的变量为换出变量,确定换入变量,：用检验数去除以换出变量行的那些对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量,例 用对偶单纯形法求解如下的,LP,问题,化成,标准形式,将各,约束条件两端同乘“,-1”,得,用,对偶单纯形法求解得,最优解：,x,1,=0,x,2,=1/4,x,3,=1/2,x,4,=0,x,5,=0,最优目标函数值：,w*=-8.5,（,z*=8.5,）,注：通常很少直接使用对偶单纯形法求解线性规划问题。,灵敏度分析,将讨论,LP,问题中的参数 中有一个或几个发生改变时问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变,研究的思路,将,个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需要从头计算，而,直接检查在参数改变后最终表有什么改变,，若仍满足最终表的条件，则表中仍给出最优解，否则从这个表开始进行迭代求改变以后的最优解。,灵敏度分析的步骤,将,参数的改变计算反映到最终表上来。具体计算公式可以使用,检查原问题是否仍为可行解,检查对偶问题是否仍为可行解,对检查情况按下表进行处理,原,问题,对偶问题,结论或继续计算步骤,可行解,可行解,问题的最优解或最优基不变,可行解,非,可行解,用,单纯形法继续迭代求最优解,非,可行解,可行解,用,对偶单纯形法继续迭代求最优解,非,可行解,非,可行解,引进人工变量，编制新的单纯形表重新计算,价值系数,变化的灵敏度分析,例：在第一章美佳公司的例,1,中,（,1,）若产品,I,的利润降至,1.5,元,/,件，而产品,II,的利润增至,2,元,/,件，美佳公司的最优生产计划有何改变；,（,2,）若产品,I,的利润不变，则产品,II,的利润在什么范围变化时，该公司的最优生产计划不发生变化,原,最终单纯形表,（,1,）改变后,新的最优解为：,最优目标函数值为：,（,2,）改变后,为使表,中的解仍为最优解必须,因此产品,II,的利润变化范围为,资源常数,变化的灵敏度分析,例：在第一章美佳公司的例,1,中,（,1,）若设备,A,与调试工序的每天能力不变，而设备,B,每天的能力增加到,32,小时，分析公司最优计划的变化；,（,2,）若设备,A,和,B,每天可用能力不变，则调试工序能力在什么范围变化时，问题的最优基不变,（,1,）,b,由,(15,，,24,，,5),T,变为,(15,，,32,，,5),T,后，相应地最终表中,b,列的数据变为,代入原,最终表,（,2,）设现在每天调试工序的时间为,x,，,则最终表中,b,列的数变为,故要使,最优基不变必须,利用,Excle,求解,LP,问题，以,P45.7(2),为例,变量，已经赋了初值,目标函数值,约束条件右端值,其他专业软件：,Lindo,与,Lingo,，,WinQSB,例如,Lingo,，启动,Lingo,后，按图中的方式输入模型，然后点击求解的图标 。就可得到所需的最优解。,2,4,对偶问题为,由,图解法,可得对偶问题最优解为,将该最优解代入对偶问题约束条件可知，第四个约束条件为严格不等式，因此在原问题最优解中,而由于,因此将原问题最优解代入原问题约束条件，它们成为等式。再由于原问题最优目标函数值等于对偶问题最优目标函数值。于是原问题最优解满足方程组,解方程组得原问题最优解：,2.5,对偶线性规划为,（,2,）直接观察可知对偶问题有解,对应于该解的目标函数值 由弱对偶性，原问题的任何可行解的目标函数值都满足,2.6,原问题显然有可行解,。,但对偶问题,第一个约束条件与非负约束条件冲突，实际上，当,时，第一个约束条件左端非正，因此不可能不小于正数,1,。这说明这些约束条件不能同时成立。故对偶问题无可行解。由弱对偶性，原问题目标函数无界。,