运筹学 第二章对偶理论灵敏度分析.ppt

1、线性规划进一步研究,对偶原理 对偶单纯形方法 灵敏度分析,对偶原理,对偶问题概念： 任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,问题的导出,问题的导出,假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出卖工时和材料 ?,问题的导出,出卖资源获利应不少

2、于生产产品的获利; 约束 价格应该尽量低，这样，才能有竞争力; 目标 价格应该是非负的,问题的导出,用y1和y2分别表示工时和材料的出售价格,总利润最小 min W=3y1+9y2 保证A产品利润 y1+y22 保证B产品利润 y1+4y23 保证C产品利润 y1+7y23 售价非负 y10 y20,问题的导出,问题的导出,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,对偶问题的特点 若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然 原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 极大化问题的每个约束对应于极小化问题的一个变量，其每

3、个变量对应于对偶问题的一个约束。,对偶问题的定义,一般线性规划问题的对偶问题,对偶问题的定义,对偶问题对应表,对偶问题的写出,例1标准型对偶问题,对偶问题的写出,例2,例 max =2x1+x2+3x3+x4 s.t. x1+x2+x3+x45 2x1-x2+3x3 =-4 x1 -x3+x4 1 x10,x2,x4无约束,x3 0,min =5y1+4y2+y3 s.t. y1-2y2+y3 2 y1+y2 =1 y1-3y2-y3 3 y1 +y3 =1 y10，y2无约束， y3 0,其对偶问题为,对偶问题的写出,练习写出对偶问题,max =x1-x2+5x3-7x4 s.t. x1+3

4、x2-2x3+x4=25 -2x1-7x2 -2x4 60 2x1 +2x2 -4x3 30 x4 10 -x4 5 x1, x2 0, x3 ,x4无约束,练习,max =x1-x2+5x3-7x4 s.t. x1+3x2-2x3+x4=25 -2x1-7x2 -2x4 60 2x1 +2x2 -4x3 30 x4 10 -x4 5 x1, x2 0, x3 ,x4无约束,对偶问题的基本性质,对称性： 对偶问题的对偶问题是原问题。,(P),(D),弱对偶定理,定理1.弱对偶定理 若互为对偶的线性规划分别有可行解 则其相应的目标函数值满足,推论,推论1 极大化问题的任意一个可行解所对应的目标函

5、数值是其对偶问题最优目标函数值的一个下界。,推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。 推论3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。,最优性准则定理,定理2 最优性准则定理 若X和Y分别是互为对偶的线性规划的可行解 ，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解,主对偶定理,定理3 （主对偶定理） 若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。,证明：由两者均有可行解，则根据弱对偶定理可知两者均有界，因此均有最优解。,设B是其最优基，X是其对应的基本可行解 令A=(B N)，则：对应

6、于基B的检验数满足,主对偶定理,定理3 （主对偶定理）,设B是其最优基，X是其对应的基本可行解 令A=(B N)，则：对应于基B的检验数满足,对偶问题的一个可行解, 其目标值：,互补松驰性(松紧定理) ： 若X，分别是(P),(D)问题的可行 解，那么X,为最优解的充要条 件是： XS=0,YSX=0 (即若 AiX i=0 AiX=bi 0 Pj=Cj 0 PjCj =Xj=0),互补松驰性(松紧定理),XS=0,YSX=0,原问题第i个约束方程是等式约束,若原问题第i个约束方程是不等式约束,例1.求解下列线性规划问题 max =x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+

7、3x420 2x1+x2+3x3+2x420 xj0, j=1,2,3,4,解其对偶问题为 min =20y1+20y2 s.t. y1+2y21 2y1+y22 2y1+3y23 3y1+2y24 y1,y20,(1.2,0.2),.,.,y1,互补松驰性(松紧定理),用图解法得最优解 y1=1.2, y2=0.2,因y10,y20。所以x5=x6=0，即原问题为等式约束,互补松驰性(松紧定理),将y1=1.2,y2=0.2代入对偶问题的 约束条件，得 y30,y40,所以x1=x2=0,min =20y1+20y2 s.t. y1+2y2- y3 =1 2y1+y2- y4=2 2y1+3

8、y2- y5=3 3y1+2y2- y6=4 y1,y20,互补松驰性(松紧定理),x1=x2=0 x1+2x2+2x3+3x4=20 2x1+x2+3x3+2x4=20,即 x1=x2=0，x3=4,x4=4 原问题的最优解为(0,0,4,4)T,max =x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 xj0, j=1,2,3,4,互补松驰性(松紧定理),7.原问题单纯形表的检验数行对应其对偶问题的一个基解.,对偶问题的基解,YS1为对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。,对偶问题的基解,例

9、.max =x1+4x2+3x3 s.t. 2x1+2x2+x34 x1+2x2+2x36 xj0,对偶问题为 min =4y1+6y2 s.t. 2y1+y21 2y1+2y24 y1+2y23 y1,y20,对偶问题的基解,对偶问题的基本解为y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3,对偶问题的基解,由原问题的最终表可知， y1=1,y2=1(最优解)， ys1=2,其最终表为,对偶问题的基解,影子价格 是一个向量， 它的分量表示最优目标值随相应资源数量变化的变化率。 若x*,y* 分别为（LP）和（DP）的最优解， 那么， cT x* = bT y* 。 根据 f =

10、bTy*=b1y1*+b2y2*+bmym* 可知 f / bi = yi* yi* 表示 bi 变化1个单位对目标 f 产 生的影响. 称 yi* 为 bi的影子价格。 当B是原问题的最优基时，Y=CBB-1就是 影子价格向量。,影子价格,影子价格的经济含义 影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑： 第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。 第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。,影子价格,影子价格反映了不同的

11、局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。,影子价格,影子价格举例,y1=5/3, y2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。 如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反,从原始问题最优表求影子价格,当B是原问题的最优基时，=CBB-1就是影子价格向量。 由检验数的计算方法可知： =C- A 若A中有单位子矩阵，则在最优表中有：,初始表,最优表,例

12、 某工厂以一种贵重金属为原料生产两种产品，两种产品都必须经过粗加工和精加工两道工序，每个粗加工工时的成本计为1.5元，精加工工时为2.5元，每克贵金属成本为10元。 以其最大加工能力的工时计入成本，而贵金属按实际使用量计入成本。,如设A、B产品分别生产x1和x2千件， 则利润可按下式计算（单位：万元） S=6x1+7x2- （3x1+2x2）+（141.5+102.5) =3x1+5x2-46,使得毛利最大的生产计划即为如下线性规划的最优解：,max S1= 3x1+5x2 （S1=S-46） s.t. x1+7x2 140 (粗加工能力约束） 2x1+4x2 100 （精加工能力约束） 3x

13、1+2x2 120 （贵金属用量约束） x1，x2 0,用单纯形法求解可得如下最优表：,由松驰变量的检验数可知：粗加工能力的影子价格为0；精加工能力的影子价格为1.125，单位是万元/千小时；贵金属的影子价格为0.25万元/公斤。,例 Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 0,影子价格举例,cB(B)-1,I,B=(p1, p4,p2 ),B-1,最优解 x1 = 50 x2 = 250 x4 = 50 (松弛标量，表示原料A有50个

14、单位的剩余） 影子价格 y1 = 50 y2 = 0 y3 = 50 , B-1对应的检验数 cB(B)-1 。,对偶单纯形法,对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 对于标准线性规划问题：,可行基B 若B对应的基本解是可行解 最优基B 若B对应的基本解是最优解 对偶可行基B 若CBB-1是对偶问题可行解 即 C-CBB-1A0 或 检验数0,对偶单纯形法,对于标准线性规划问题：,对偶单纯形法,对于标准线性规划问题：, 找一个基，建立初始对偶单纯形表，检验数全部非正； 若b列元素非负，则已经是最优基。反之，则取相应行的基变量为出基变量； 为保证能对基的可

15、行性有所改进，则将来的主元应该为负数；为保证下一个基还能是对偶可行基，应使检验数仍为非正的。 主元变换,对偶单纯形法举例,例 用对偶单纯形法求解：,对偶单纯形法举例,对偶单纯形法举例,对偶单纯形法的基本思想 从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发； 然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,对偶单纯形法,如果得到的基本解的分量皆非负则该基本解为最优解。 也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（

16、即检验数非正），使原规划的基本解由不可行逐步变为可行。 当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,对偶单纯形法,对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。,对偶单纯形法,例. min =3x1+4x2+5x3 s.t. x1+2x2+3x35 2x1+2x2+x36 x1,x2,x30,解 问题化为 min =3x1+4x2+5x3 s.t. -x1-2x2-3x3+x4 =-5 -2x1-2x2-x3 +x5=-6 x1,x2,x3,x4,x50,对偶单纯形法练习,对偶单

17、纯形法练习,灵敏度分析,在生产计划问题的一般形式中， A代表企业的技术状况， b代表企业的资源状况， C代表企业产品的市场状况 在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。,在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优， 如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,灵敏度分析,灵敏度分析

18、,当系数A，b，C发生改变时，目前最优基是否还最优？目前的最优解是否还最优？ 为保持目前最优基或最优解还是最优，系数A，b，C的允许变化范围是什么？ 假设每次只有一种系数变化 目标系数C变化 基变量系数发生变化； 非基变量系数发生变化； 右端常数b变化 增加一个变量 增加一个约束 技术系数A发生变化,灵敏度分析,若B是最优基，则最优表形式如下,灵敏度分析总是在最优表上进行,灵敏度分析,例 线性规划,灵敏度分析,例 线性规划,灵敏度分析,例27 线性规划,3-2*（-1）-3*2=-1,为保持目前最优基还是最优，系数aij,bi,cj的允 许变化范围是什么？,当aij,bi,cj中的一个或几个发

19、生变化时，已求得的线 性规划问题的最优解会有什么变化？如何求解新的 最优解？,价值系数C的改变,价值系数CN （非基变量的价值系数）发生改变,C3,C3-4,如果C34,则目前解不再是最优解,应该用单纯形方法继续求解,否则解不变。即对于C3而言,使最优解不变的条件是C34。,价值系数C的改变,价值系数CN发生改变,5,价值系数C的改变,价值系数CB （基变量的价值系数)发生改变,C1-3,1-4/3C1,1/3C1-1,C1-3 0, 1-4/3C10, 1/3C1-10 C13 若C13/4 则x4进基，x1出基 若3 C1 则x3或x5进基，x2出基,价值系数C的改变,价值系数CB发生改变

20、,1/2,1/2,价值系数C的改变,价值系数CB发生改变,资源数量b变化的分析,右端常数b1的改变范围,b1,4b1/3-3,3-b1/3,9/4b1 9,-3-5b1/3,资源数量b变化的分析,右端常数b1发生改变,2,资源数量b变化的分析,右端常数b1发生改变,12,资源数量 b 变化的分析,资源数量变化是指系数br发生变化,其它参数不变。,原最优解为 b*=B-1b,br的变化仅引起最优解的变化,若要所得的基还是最优基，必须XB0，而其若大于零，则得到的解必为最优解。,B-1的第r列元素,例.线性规划问题 max =-x2+3x2-2x5 s.t. x1+3x2-x3 +2x5 =7 -

21、2x2+4x3+x4 =12 -4x2+3x3 +8x5+x6 =10 xj0,资源数量 b 变化的分析,B=P2,P3,P6,求b2的变动范围,max -4/(1/10),-5/(3/10)b2min-11/(-1/2) -50/3b222,要保持最优基不变，则 -14/3b234,若b2超出此范围，则b0 可用对偶单纯形法继续求解,例上题中，若令b2增加b2=30,则,将上式结果反映到最终表中，得下表,资源数量b变化的分析,右端常数b2改变范围,b2,4-b2/3,b2/3-1,3b2 12,-b2/3-5,练习,灵敏度分析,增加一个变量 若企业在计划期内，有新的产品可以生产，则在知道新产

22、品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。 若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,增加一个变量,例.某工厂计划生产A,B,C三种产品，需要甲,乙两种资源。资源限量、每种产品的单位利润和单位产品的资源消耗量如下表所示，试确定使利润最大的生产计划。,练习：,解以x1,x2 ,x3分别表示A,B,C三种产品的产量，则该问题的线性规划模型如下：,max =2x1+3x2+x3 s.t. 1/3x1+1/3x2+1/3x31 1/3x1+4/3x2+7/3x33 x1,x2,x30,引入松驰变量，可得初始单纯形表,最终单纯形表为,假设这个工厂研制了一种新产品D，单位新产品D所需耗用的甲乙两种资源分别为1/2和1/2，新产品的利润为4元，问应怎样调整生产计划？,max =2x1+3x2+x3 s.t. 1/3x1+1/3x2+1/3x31 1/3x1+4/3x2+7/3x33 x1,x2,x30,P6=B-1P6=,灵敏度分析,增加一个约束 在企业的生产过