对偶问题的分析.ppt

1,第三章 线性规划问题的对偶与灵敏度分析,3.1线性规划的对偶问题概念、理论及经济意义 3.2线性规划的对偶单纯形法 3.3线性规划的灵敏度分析,本章内容重点,2,线性规划原问题,例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。,3,一、对偶问题： 它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力 若另外一个工厂要求租用该厂的设备A、B、C ，那么该厂应如何确定合理的租金。 设 y1 ，y2 ，y3 分别为每工时设备 A、B、C 的租金。,3.1线性规划对偶问题,4,设备的租金收入不能低于自己组织生产时的获利收入： 3y1+2y2 1500（不少于甲产品的利润） 2y1+y2+3y3 2500（不少于乙产品的利润） 用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润 租方希望在满足上述条件下尽量要求全部设备的总租金越少越好，即 Min W = 65y1+ 40y2 + 75y3,5,对偶变量的经济意义可以解释为对工时及原材料的单位定价 若工厂自己不生产产品A、B和C，将现有的工时及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低） 当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的： Zmax=Wmin=8,6,原问题的对偶问题DP： Min W= 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 2y1+y2+3y3 2500 y1, y2 , y3 0,7,Max z = 1500x1 + 2500x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原问题 3x2 75 x1 ,x2 0 Min W = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 2y1+y2+3y3 2500 对偶问题 y1, y2 , y3 0,8,原问题求极大化，对偶问题求极小化 从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 从数据b、C的位置看：在两个规划模型中，b和C的位置对换。,9,对偶问题与原问题的对比,原问题（对偶问题） 对偶问题（原问题） 目标函数max 目标函数min 不同 0 约束 0 变量 不同 条件 = 无约束 0 变量 0 约束 相同 无约束 条件 =,10,11,例3.1 写出下面线性规划的对偶规划模型,12,Max z = x1 - x2+5x3-7x4 s.t. x1 + 3 x2 -2 x3 + x4 = 25 2 x1 + 7x3 + 2x4 -60 2 x1 + 2x2 -4x3 30 x4 -5 x4 10 x1 , x2 , 0 x3 , x4取值无约束,13,Min f = 25y1 60y2+30y3-5y4+10y5 s.t. y1 + 2y2 +2 y3 1 3 y1 +2y3 -60 -2 y1 + 7y2 -4y3 = 5 y1 + 2y2 + y4+ y5 =-7 y1 取值无约束 y3 , y5 0 y2 , y4 0,14,对称性定理 对偶问题的对偶是原问题。 主对偶定理 若(LP)和(DP)均可行，那么(LP)和(DP)均有最优解,且最优值相等。 如果原问题有最优解，则其对偶问题也一样具有最优解，且有max z=min w。,二、对偶问题的基本性质,15,弱对偶定理 若 x, y 分别为（LP) 和（DP）的可行解，那么cTx bTy。 推论 若LP（或DP）可行，那么LP（或DP）无有限最优解(有无界解)的充分必要条件是DP（或LP）无可行解。 ？当LP（或DP）无可行解时，则DP（或LP）具有无界解。 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。,16, 最优性准则定理 若x,y分别(LP)，(DP)的可行解,且cTx=bTy ，那么x,y分别为(LP)和(DP)的最优解。,17,三、影子价格,市场价格 影子价格 ，确切的定义是：一个线性规划对偶问题的最优解（简称为“对偶最优解”）。 对偶变量yi ：代表对一个单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价。 bi 是线性规划原问题约束条件右端项，它代表第i种资源的拥有量。,18,影子价格是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。 若x*,y* 分别为（LP）和（DP）的最优解， 那么， cT x* = bT y* 。 根据 w= bTy*=b1y1*+b2y2*+bmym* 可知 w/ bi = yi* yi* 表示 bi 变化1个单位对目标W 产生的影响，称 yi* 为 bi的影子价格。,19,企业可以根据现有资源的影子价格，对资源的使用有两种考虑： 第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。 第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。,20,需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。,21,利用最优单纯形表求对偶问题最优解 标准形式： 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,四、对偶问题的解,22,-cBB-1,I,B=(p1, p4,p2 ),B-1,最优解 x1 = 50 x2 = 250 x4 = 50 影子价格 y1 = 50 y2 = 0 y3 = 50 , yi= cBB-1 。,23,3.1线性规划的对偶问题概念、理论及经济意义 3.2线性规划的对偶单纯形法 3.3线性规划的灵敏度分析,24,对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从一个对偶可行解（检验数非正）出发；然后检验原问题的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,25,如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,26,1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选b最小的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止; 否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为入基变量,转4； 4. 作矩阵行变换使入基变量变为单位向量，转2。,27,对偶单纯形法的适用范围 适合于解如下形式的线性规划问题,在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。,28,例3.2：求解线性规划问题：,29,表格对偶单纯形法,30,3.1线性规划的对偶问题概念、理论及经济意义 3.2线性规划的对偶单纯形法 3.3线性规划的灵敏度分析,31,进一步理解最优单纯性表中各元素的含义考虑问题 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,32,aij 是随工艺技术条件的改变而改变 bi 值是根据资源投入后能产生多大经济效果来决定的一种决策选择 Cj 则是容易受到市场条件的影响,33,I,B-1,B=(p1,p4,p2 ),34,b=b+b b=B-1b Pj= B-1 Pj j=cj-CBPj=cj-CBB-1Pj=cj-YTPj,35,1. 价值系数c发生变化： m 考虑检验数 j = cj - cri arij j =1,2,n i = 1 例: Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0,36,问：c2在什么范围内变化，问题的最优解不变,30，40 可得到 0c24时，原最优解不变。,37,2.右端项 b 发生变化 先求 b， b=B-1b ，b=b+b 若 b1 增加 4，最优解有何变化？,38,0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0,b= B-1*b b=(4,0,0) T b=(0,-8,2) T b= (4,-4,4) T,39,用对偶单纯形法进一步求解，可得： x* = ( 4, 3, 2, 0, 0 )T f* = 17,40,3.增加一个变量 增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么 计算出pn+1 =B-1pn+1 , n+1=cn+1-cri ari n+1 填入最优单纯形表, 若 n+1 0 则 最优解不变； 否则，进一步用单纯形法求解。,41,例3.6: 增加x6 , p6=( 2, 6, 3 )T, c6=5,0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0 B-1p6=(2/3, 2, )T,42,用单纯形法进一步求解，可得： x* = ( 1,1.5,0,0,0,2 )T f* = 16.5,43,4.增加一个约束 增加约束一个之后，把最优解带入新的约束，若满足约束条件则最优解不变， 否则作为新的一行，填入最优单纯形表，并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。,44,例3.7: 增加3x1+ 2x215，问最优解有何变化？ X=（4，2）T不满足这个约束。,首先将约束条件标准化： 3x1+ 2x2+x6=15,45,经对偶单纯形法一步，可得最优解为（3.5, 2.25, 0, 0, 3, 2 )T，最优值为 13. 75,46,5. 系数矩阵A中元素发生变化 第一种情况：若相应的变量xj在最终单纯形表中为非基变量，那么aij的变化分析如下： 假设 pj 变化， 那么，重新计算出B-1pj 与 j j = cj - cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。,47,48,5. 系数矩阵A中元素发生变化,第二种情况：若相应的变量在最终单纯形表中为基变量，aij的变化将引起B和B-1发生变化。 例：美佳公司计划制造，两种家电，已知各制造一件时，分别占用的设备A,B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各出售一件时的获利情况如下表所示。,49,最终单纯型表如下，,若家电每件需设备A,B和调试工时变为8h,4h,1h,该产品的利润为3元/件，试重新确定该公司的最优生产计