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

1、第二章 对偶理论与灵敏度分析,2.1 线性规划的对偶问题,2.2 对偶问题的基本性质,2.3 影子价格,2.4 对偶单纯形法,2.5 灵敏度分析,2.1 线性规划的对偶问题,对偶问题的提出,对称形式的对偶问题,对称形式 变量非负，求极大时约束条件取号、求极小时约束条件取号.,对称形式的对偶问题,1,若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然。 2,原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵。 3,极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。 4,原问题与对偶问题互为对偶问题。,对偶问题的特点,非对称形式的对偶问题,非对称形式

2、的对偶问题,2.2 对偶问题的基本性质,推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。,推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。,推 论,推论3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。,若X和Y分别是互为对偶的线性规划的可行解 ，且使 CX=Yb，则X和Y分别是相应线性规划问题的最优解。,性质2：最优性准则,若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。 若原问题最优基为B，则其对偶问题最优解Y*=CBB-1,性质3：强对偶性（对偶定理）,性质4：互

3、补松弛性,最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,最优解X*=(x1, x2 , x3, x4 , x5) (7/2,3/2,15/2,0,0),最优解y*=(y1, y2 , y3, y4 , y5) (0,1/4,1/2,0,0),y1 0,y2 1/4,y3 1/2,x1 7/2,x2 3/2,2.3 影子价格,最优解X*=(x1, x2 , x3, x4 , x5) (7/2,3/2,15/20,0)，最优值:Z*= 17/2,原问题,对偶问题,最优解y*=(y1, y2 , y3, y4 ,

4、 y5) (0,1/4,1/2,0,0)，最优值:Z*= 17/2,当线形规划原问题与对偶问题同时取得最优解时，其对偶最优解yi 代表在资源最优利用条件下对单位第i种资源的估价，这个估价称为这种资源的影子价格。 其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。,原问题是利润最大化的生产计划问题,Max z= c1 x1 + c2 x2 + . + cnxn a11x1 + a12 x2 +.+ a1n xn+ x n+1 =b1 a21x1 + a22 x2 +.+ a2n xn + x n+2 =b2 . am1x1 + am2 x2 +.+ amn xn

5、+ x n+m=bm x1,x2,x n+m0,总利润（元）,单位产品的利润（元/件）,产品产量（件）,消耗的资源（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,资源限量（吨）,Min w= b1 y1 + b2 y2 + . + bmym a11y1 + a21 y2 +.+ am1 ym ym+1 = c1 a12y1 + a22 y2 +.+ am2 ym ym+2 = c2 . a1ny1 + a2n y2 +.+ amn ym ym+n = cn y1,y2,ym+n0,资源价格（元/吨）,资源限量（吨）,总利润（元）,对偶问题的最优解y1、y2、.、ym称为m种资源的影子价

6、格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,对偶问题是资源定价问题,1、影子价格依赖于资源的利用情况，各企业不同。,影子价格的经济解释,2、影子价格表示的是资源的一种边际价格。,影子价格越大，说明这种资源越是相对紧缺；影子价格越小，说明这种资源相对不紧缺 若某种资源影子价格为零，则说明此资源未得到充分利用；若不为零，则表明该资源得到充分利用。,y1 y2 ym,增加单位资源可以增加的利润,减少一件产品可以节省的资源,3、影子价格代表一种机会成本,机会成本a1jy1+ a2jy2+ aijyi+ amjym 表示减少一件产品所节省的资源可以增加

7、的利润,机会成本,利润,差额成本,4、产品的差额成本（Reduced Cost）,差额成本=机会成本 - 利润,在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润 （4）机会成本大于利润的产品不安排生产,影子价格的经济含义,在单纯形法中，原问题的最优解满足： （1）是基本解；（2）可行；（3）检验数 0 （YAC），即对偶解可行。 单纯形算法是从满足（1）、（2）的一个基可行解出发，转换到另一个基可行解，一直迭代到（3）得到满足，即对偶解可行为止。 对偶单纯形法则是从满足（1）、（3）的一个对偶可行解出发，以基变

8、量值是否全非负为检验数，连续迭代到（2）得到满足，即原问题的基解可行为止。 两种算法结果是一样的，区别是对偶单纯形法的初始解不一定可行，只要求所有检验数都非正，在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基解可行，从而取得问题的最优解,2.4 对偶单纯形法,单纯形法与对偶单纯形法比较,单纯形法的步骤,对偶单纯形法的步骤,如何用？,例:,1,4/3, ,1,2,j,4/5,2, ,1,j,所以：X*=(x1,x2)T=(11/5,2/5)T Z*=28/5,如何用？,对应B的基解：,存在检验数0,不可行,单纯形法,对偶单纯形法？,用大M法求解,或用两阶段法求解,灵敏度分析的两把尺子：

9、 j =Cj-CBB-1pj 0； xB = B-1b 0,假设每次只有一种系数变化 价值系数C变化（单位产品利润变化） 右端常数b变化（资源拥有量变化）,2.5 灵敏度分析（Lindo求解）,当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基不变，系数A，b，C的允许变化范围是什么？,第一章例1中，若家电的利润降至1.5元/件，家电的利润增至2元/件，最优生产计划是否改变；,第一章例1中，若其它资源不变，而设备B的能力增加到32h，分析公司最优计划的变化；,第一章例1， 美佳公司生产状况如下表,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNC

10、TION VALUE 1) 8.500000 VARIABLE VALUE REDUCED COST X1 3.500000 0.000000 X2 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 7.500000 0.000000 3) 0.000000 0.250000 4) 0.000000 0.500000 NO. ITERATIONS= 2,max 2x1 + x2 st 2) 5x2 =15 3) 6x1 + 2x2 =24 4) x1 + x2 =5 end,RANGES IN WHICH THE BASIS IS UN

11、CHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 2.000000 1.000000 1.000000 X2 1.000000 1.000000 0.333333 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 15.000000 INFINITY 7.500000 3 24.000000 6.000000 6.000000 4 5.000000 1

12、.000000 1.000000,max 2x1 + x2 st 2) 5x2 =15 3) 6x1 + 2x2 =24 4) x1 + x2 =5 end,THE TABLEAU ROW (BASIS) X1 X2 SLK 2 SLK 3 SLK 4 1 ART 0.000 0.000 0.000 0.250 0.500 8.500 2 SLK2 0.000 0.000 1.000 1.250 -7.500 7.500 3 X1 1.000 0.000 0.000 0.250 -0.500 3.500 4 X2 0.000 1.000 0.000 -0.250 1.500 1.500,DAK

13、OTA家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。若要求桌子的生产量不超过5 件，如何安排三种产品的生产可使利润最大？,用DESKS、TABLES 和CHAIRS 分别表示三种产品的生产量，建立LP 模型，输入如下。,MAX 60DESKS + 30TABLES + 20CHAIRS ST 2) 8DESKS + 6 TABLES + CHAIRS =48 3) 4DESKS + 2 TABLES + 1.5CHAIRS =20 4) 2DESKS + 1.5TABLES + 0.5CHAIRS =8 5) TABLES =5 END,LP OPTIMUM FOUND A

14、T STEP 2 OBJECTIVE FUNCTION VALUE 1) 280.0000 VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 24.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 10.000000 5) 5.000000 0.000000 NO. ITERATIONS= 2,MAX 60DESKS +

15、30TABLES + 20CHAIRS ST 2) 8DESKS + 6 TABLES + CHAIRS =48 3) 4DESKS + 2 TABLES + 1.5CHAIRS =20 4) 2DESKS + 1.5TABLES + 0.5CHAIRS =8 5) TABLES =5 END,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE DESKS 60.000000 20.000000 4.0

16、00000 TABLES 30.000000 5.000000 INFINITY CHAIRS 20.000000 2.500000 5.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000,MAX 60DESKS + 30TABLES + 20CH

17、AIRS ST 2) 8DESKS + 6 TABLES + CHAIRS =48 3) 4DESKS + 2 TABLES + 1.5CHAIRS =20 4) 2DESKS + 1.5TABLES + 0.5CHAIRS =8 5) TABLES =5 END,THE TABLEAU ROW (BASIS) DESKS TABLES CHAIRS SLK 2 SLK 3 SLK 4 SLK 5 1 ART 0.000 5.000 0.000 0.000 10.000 10.000 0.000 280.000 2 SLK 2 0.000 -2.000 0.000 1.000 2.000 -8

18、.000 0.000 24.000 3 CHAIRS 0.000 -2.000 1.000 0.000 2.000 -4.000 0.000 8.000 4 DESKS 1.000 1.250 0.000 0.000 -0.500 1.500 0.000 2.000 5 SLK 5 0.000 1.000 0.000 0.000 0.000 0.000 1.000 5.000,MAX 60DESKS + 30TABLES + 20CHAIRS ST 2) 8DESKS + 6 TABLES + CHAIRS =48 3) 4DESKS + 2 TABLES + 1.5CHAIRS =20 4)

19、 2DESKS + 1.5TABLES + 0.5CHAIRS =8 5) TABLES =5 END,奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。 试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题： 1） 若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天

20、最多购买多少桶牛奶？ 2） 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？ 3） 由于市场需求变化，每公斤A1的获利增加到30 元，应否改变生产计划？,补充问题,max 72x1 + 64x2 st milk) x1 + x2 =50 time) 12x1 + 8x2 =480 shop) 3x1 =100 end,LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL