运筹学LP的对偶问题与灵敏度分析

1、第3章 LP的对偶问题与灵敏度分析1 1 原问题与对偶问题原问题与对偶问题 大自然中任何事物之间的关系均可以用阴阳八卦的思想来理解，有着生生相克的特性。一件事物有正面，还有反面；有积极作用，还有消极作用。对偶问题正是如此！ 阴阳机器厂在计划期内生产、两种产品，已知生产单位产品所需设备A、B、C台时如下：产品产品资源限量设备A11300台时设备B21400台时设备C01250台时该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应该怎样安排生产，才能获利最多？ 设产品的计划产量为x1，产品的计划产量为x2， 则有线性规划问题LP1： 目标函数： 约束条件：0,250400

2、2300. .10050max212212121xxxxxxxtsxxz 现假定有另一八卦机器厂，该厂的规模较小一些，想租用阴阳厂的设备进行生产。那么阴阳厂的领导应该给自己的设备制定一个怎样的出租价格呢？ 设出租设备A、B、C的价格分别定为 y1、y2、y3。该问题可从两个角度进行分析：对于阴阳厂，总租金应当不低于原利润： 生产产品所需设备台时不应当低于原利润： 生产产品所需设备台时不应当低于原利润：对于八卦厂，希望支付的总租金最少，即：50221yy100321yyy321250400300minyyyf 因此可以建立另一线性规划问题LP2： 目标函数： 约束条件：0,100502. .25

3、0400300min32132121321yyyyyyyyt syyyf 在这种情况下，我们称LP1、LP2互为对偶问题，即一个为原问题，另一个则为对偶问题。 原问题 对偶问题), 2 , 1( 0), 2 , 1(. .min11miynjcyat sybfimijiijmiii), 2 , 1(0), 2 , 1(. .max11njxmibxatsxczjnjijijnjjj 用矩阵形式，可表达为： 原问题 对偶问题0YCYAYbTTTtsf. .min0XbAXCX.maxtsz 在上例中，原问题与对偶问题的矩阵形式可以写作： 原问题 对偶问题032132132110050101211

4、. .)250400300(minyyyyyytsyyyf0212121250400300101211. .)10050(maxxxxxtsxxz二者之间的关系： 原问题中求目标函数极大化问题，对偶问题中求目标函数极小化问题。 原问题中约束条件的个数等于对偶问题中变量的个数。 原问题约束条件中符号为 号，对偶问题中约束条件符号为 号。 原问题目标函数的系数是其对偶问题约束条件的右端项。可用如下表格来表示：原问题（求极大）右端项对偶问题（求极小）b1 y1b2 y2. . . .bm ymc1 c2 cnx1 x2 xna11 a12 a1na21 a22 a2n. . . . . . . .

5、am1 am2 amn b1b2. bm右端项 c1 c2 cn例1：写出下述线性规划问题的对偶问题0,2003510046440632. .643max321321321321321xxxxxxxxxxxxtsxxxz解：第一步：将5x1-3x2+x3 =200转换成： 5x1-3x2+x3200 和 5x1-3x2+x3200,然后将所有的约束条件写成（亦可），有0,200352003510046440632. .643max321321321321321321xxxxxxxxxxxxxxxtsxxxz第二步：令与上式中四个约束条件对应的对偶变量分别为y1,y2,y3,y3(因为它俩来自于

6、同一个约束条件），则有对偶问题：0 , ,6 64 33433 5562. . 200200100440min33213321332133213321yyyyyyyyyyyyyyyytsyyyyf第三步：再令y3=y3-y3，则有最终的对偶问题：无约束321321321321321, 0,6643433562. .200100440minyyyyyyyyyyyytsyyyf例2：写出下述LP的对偶问题：0, 030351546324624. .347min32132321321321xxxxxxxxxxxtsxxxz无约束按照上述三个步骤，求得其对偶问题为：无约束32132132121321,

7、 0, 033464562734. .301524maxyyyyyyyyyyytsyyyf原问题与对偶问题互化关系表：原问题与对偶问题互化关系表：原问题（对偶问题）原问题（对偶问题）目标函数（目标函数（max）对偶问题（原问题）对偶问题（原问题）目标函数（目标函数（min）个个变变量量无约束无约束目标函数中变量的系数目标函数中变量的系数约个约个束束 条条 件件 约束条件右端项约束条件右端项个个 约约 束束 条条= 件件约束条件右端项约束条件右端项个个 变变 量量无约束无约束目标函数中变量的系数目标函数中变量的系数2 对偶问题的基本性质化标准形：)3(0,)2(.) 1 (MaxssXXbXAX

8、TSCXZ设有LP问题： 0.MaxXbAXTSCXZ不违背一般，设B是一个可行基，与B相应，做矩阵分块如下： 一、单纯形法的矩阵描述),(),(),(NBACCCXXXNBNB式（1），（2）可表示为：(,) (,)( ,) (,)TBNBNTBNSZCCXXB NXXXb即：)5()4(bXNXBXXCXCZsNBNNBB式（5）两端左乘B-1得：)6(111bBXBNXBXsNB由式（6）得：)7(111sNBXBNXBbBX 带入式（4）得： 由式（8）得单纯形法的最优性条件为：111111()()(8)BBNNBNsNNBNBNBsZC XC XCB bB NXB XC XC B b

9、CC B N XC B X0011BCNBCCBBN二、单纯形表的矩阵结构 由（7），（8）可构造单纯形表：三、对偶规划与原规划最优解的关系当原问题得到最优解时，必有： 0011BCNBCCBBN令： ，上式等价为：1BCYB0YCYA可知这是对偶规划的一个可行解且此时： ，可见对偶规划与原规划最优解的目标函数值相等，不是偶然的。zbBCYbWB1四、由原规划最终单纯形表确定对偶规划最优解 考察单纯形表结构，可在原规划得到最优解时，同时直接得到对偶规划最优解，这已经是明确的问题。 并且由： 还可发现对偶问题的最优解y= 实际是原问题松弛变量的检验数的相反数。110sBsBCBExCB 松 弛

10、变 量的 检 验 数1BC B举例MAX 50 x1+100 x2+0s1+0s2+0s3. S.T. x1 + x2+ s1+ 0s2+ 0s3=300, 2x1 + x2+ 0s1+ s2+ 0s3=400, 0 x1 + x2+ 0s1+ 0s2+ s3=250, x1,x2,s1,s2,s30迭代次数基变量CB x1 x2 s1 s2 s3 b比值bi/aij 50 100 0 0 0 2x1S2x2500100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 15050250Zj 50 100 50 0 50 0 0 -50 0 -5027500jjjzc Lindo求解

11、对偶问题 min 300y1+400y2+250y3 st y1+y2=50 y1+y2+y3=100 end五、对偶问题基本性质五、对偶问题基本性质其对偶问题的最优解。是是原问题的最优解，则，且有是其对偶问题的可行解是原问题的可行解，最优性。如果恒有是其对偶的可行解，则是原问题的可行解，弱对偶性。如果), 1(), 1(), 1(), 1(. 2), 1(), 1(. 11111miynjxybxcmiynjxybxcmiynjxijnjmiiijjijnjmiiijjij. 0.0. 5minmax,. 4. 311injijijnjijijiybxabxayfz，则如果，则如果为零，也即

12、对偶变量一定格不等式，则其对应的反之如果约束条件取严取严格等式；为非零，则该约束条件约束条件的对偶变量值果对应某一划问题的最优解中，如互补松弛性。在线性规。解，且有偶问题也一定具有最优则其对优解理）。如果原问题有最强对偶性（或称对偶定解。问题（原问题）无可行，则其对偶对偶问题）具有无界解无界性。如果原问题（6.zf线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有：3 3 对偶单纯形法对偶

13、单纯形法单纯形法是在保持原问题的所有约束条件的常数大于等于零的情况下，通过迭代，使得所有的检验数都小于等于零，最后求得最优解。对偶单纯形法则是在保持原问题的所有检验数都小于等于零的情况下，通过迭代，使得所有约束条件的常数都大于等于零，最后求得最优解。优点：初始解可以是非可行解；对于一些大于等于号约束条件可以不添加人工变量，只需把两边同乘以-1，化成小于等于约束。缺点：1.不是所有初始解其检验数都小于等于零。 在单纯形法中，原问题的最优解满足：对偶单纯形法计算步骤如下：11jjj1 LB=C0Y=BBC B PC B步骤确定原问题（ ）的初始基 ，使得所有检验数，即是对偶可行解，建立初始单纯形表

14、。-1B-1-1-12 X =B b0minB bB b0B bllj步骤检查基变量的取值，若，则已得最优解，计算停；否则求（） （）（）jkkk 0=min/0/Xljljljl步骤3 若所有a，则原问题无可行解，计算停；否则，计算aaa确定对应的为旋入变量。k4 lk2l步骤以a 为主元作（ ， ）旋转变换，得新的单纯形表，转步骤 。可以证明，按上述方法进行迭代，所得解始终是对偶可行解。 例1 已知线性规划问题 试分析1和2分别在什么范围内变化时，问题的最优解不变。4 灵敏度分析灵敏度分析 1122121212max(2)(3)2212416. .515,0zxxxxxstxx x一、目标

15、函数中系数一、目标函数中系数Cj的灵敏度分析的灵敏度分析 分析：此例中目标函数的系数cj的变化仅仅影响到检验数j的变化，所以将Cj的变化直接反映到最终单纯形表中。 解：当1=2=0时，上述LP问题的最终单纯形表如上表所示。（i）对基变量x1的目标函数系数进行灵敏度分析：将1的变化反映到最终单纯形表中：表中的解仍为最优解的条件是：-1-1/210 -1/5+1/510 故有-211时，该LP问题的最优解不变。（ii）类似的可以得到，其他条件不变的情况下，2-1时，该LP问题的最优解不变。-2/5+1/5（3+ 2 ）二、约束条件右端常数项二、约束条件右端常数项bi的灵敏度分析的灵敏度分析例2 L

16、P问题121212212max501003002400A. .250B,0zxxxxxxstxx x设备台时原料原料分别分析右端常数项在什么范围内变化时，最优基不变。分析：原问题的最终单纯形表如下为，11*111012 110200100bBb 1*15050 20250bb15025右端常数项的灵敏度分析：（i）使问题最优基不变的条件是 （ii）类似的，使问题最优基不变的第二个约束条件右端常数项的变化范围是：2-50 (iii）同样，-50350 即200250+3300时，对偶价格不变，原问题的最优基不会发生变化。三、增加一个量的灵敏度分析三、增加一个量的灵敏度分析实际中，增加一个变量的计

17、算步骤如下：实际中，增加一个变量的计算步骤如下：（1）计算）计算 ;（2）计算）计算 ；（3）若）若 ，只需将，只需将 和和 的值直接反映到最终单纯形的值直接反映到最终单纯形表中，原最优解不变；表中，原最优解不变；若若 ，则按单纯形法继续迭代计算。，则按单纯形法继续迭代计算。1jjjjBjczcC BP1jjpBp0jjpj0j例例3 在例在例1中，若增加一个变量中，若增加一个变量x6，有，有c6=4，P6=(2,4,5)T，试分析问，试分析问题的最优解的变化。题的最优解的变化。解：解：61/2 01/52242 0 3214/5441 0 1/544 3 1001/555 166041PB

18、P 代入最后一张单纯形表中，有16 例5：某工厂计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原料的消耗，以及资源的限制，如下表所示：资源限制设备11300台时原料A21400千克原料B01250千克 该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少个产品和 产品才能使工厂获利最多？补充（约束方程系数矩阵A灵敏度分析）该问题的数学模型为： OBF: MAX 50 x1+100 x2. S.T. x1+x2 300, 2x1+x2 400, x2 250 xj 0 迭代次数基变量CB x1 x2 s1 s2 s3 b比值bi/a

19、ij 50 100 0 0 0 2x1S2x2500100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 15050250Zj 50 100 50 0 50 0 0 -50 0 -5027500jjjzc 其最终单纯形表如下： 现假设该厂除了生产、产品外，现试制成一种新产品，已知生产产品，每件需要设备2台时，并消耗A原料0.5公斤，B原料1.5公斤，获利150元，问该厂是否应该生产该产品和生产多少？ 解：显然x3是非基变量。主要来计算x3的检验数。经过初等行变换，x3所在列的系数变成：025175150,1755 . 11005 . 0505 . 125 . 05 . 15 .

20、021001121016666zcz这时，61pB迭代次数基变量CB x1 x2 s1 s2 s3 x3 b比值 50 100 0 0 0 150 x1S2x2500100 1 0 1 0 -1 0.5 0 0 -2 1 1 -2 0 1 0 0 1 1.55050250Zj 50 100 50 0 50 175 0 0 -50 0 -50 -2527500jjjzc 新单纯形表如下： 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要设备1.5台时，并消耗A原料2公斤，B原料1公斤，获利160元，问该厂的原生产计划是否需要修改？035125160,12511005 . 050105 . 0125 . 11001121016666zcz这时，61pB 解：x3所在列的系数变成：迭代次数基变量CB x1 x2 s1 s2 s3 x3 b比值 50 100 0 0 0 160 2x1S2x2500100 1 0 1 0 -1 0.5 0 0 -2 1 1 0 0 1 0 0 1 15050250100250Zj 50 100 50 0 50 125 0 0 -50 0 -50 3527500jjjzc 新单纯形表如下：迭代次数基变量CB x1 x2 s1 s2 s3 x3 b