第二章 线性规划对偶理论 运筹学 课件

1、第二章 线性规划的对偶理论与灵敏度分析,1 线性规划理论基础及单纯形法的矩阵描述,任意线性规划化为标准形时，往往要添加松弛变量，为了求出第一个基可行解要添加人工变量。这时约束方程组的系数矩阵中含有以个子阵为单位阵，因此任意线性规划问题的标准形可用矩阵表示如下：,其中I是m阶单位阵，C=(c1,c2,cn); X=(x1,x2,xn)T,并记(AI)的第j列为Pj(j=1,2,n)。单位阵I是初始基，与I的列对应的变量是初始基变量，按此将X分为两块，X=(X X)T, X是初始基变量， X是非基变量，相应地将C分为两块C= =(C C) 现在(2.1)的目标函数可记为 f- C X- C X=0

2、 由此可将(2.1)的标准线性规划问题表示为以下形式：,设在某步迭代中的基为B，相应的m个基变量为XB，C中与XB对应的m个元素记为CB。不妨设(AI)的前m列为B，则(2.1)可表示为,即 maxf=CBXB + CNXN + CX (2.3) BXB + NXN + X=b (2.4) XB0, XN0 , X0 (2.5) 将(2.3)变为 f - CBXB - CNXN - CX=0 (2.6) (2.4)两端左乘B-1则有 XB + B-1 NXN + B-1 X= B-1 b (2.7) 并且有XB = B-1b - B-1 NXN - B-1 X (2.8) 将其代入(2.6)得

3、 f CBB-1b + CBB-1 NXN + CBB-1 X CN XN - C X=0 f + (CBB-1 N CN )XN + (CBB-1 C) X= CBB-1b (2.9),可将(2.7) ,(2.9)表示为 f 1 0 CBB-1 NCN CBB-1 C XB = CBB-1b 0 I B-1N B-1 XN B-1b X (2.10) (2.2) 和(2.10)所对应的单纯形表如下,从以上两张表可知： （1）对应初始单纯形表中的单位阵I，迭代后的单纯形表中为B-1。 （2）迭代到某一步的基可行解为 XB B-1b XN = 0 X 0 （3）若初始单纯形表中变量xj的系数向量

4、为Pj，迭代后的单纯形表中为B-1 Pj 。 （4）当CBB-1 N CN 0， CBB-1 C 0时为最优单纯形表，其解为最优解，并且CBB-1 N CN 0与 CBB-1 A C 0等价。 xj的检验数记为j= CBB-1 Pj Cj,（5）若CBB-1 N CN 0，CBB-1 C 0,这时不是最优解，应选择检验数最小的变量xk为进基变量。 （6）根据最小规则确定出基变量，即,则相应的xl为出基变量，其中Pk为进基变量xk对应的列向量，而( )j表示在圆括号内列向量的第j个元素。,（7）单纯形表中，所有非基变量的检验数大于零，则此问题有为以最优解。 （8）在最优单纯形表中，所有检验数大于

5、等于零，而某一个非基变量xk的检验数等于零，则此问题有无穷多最优解。 （9）在某单纯形表中，某一变量xk的检验数小于零，而相应Pk0则此问题无有限最优解。,2 线性规划问题的对偶问题,对偶问题概念： 任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂

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

7、量对应于对偶问题的一个约束。,一般线性规划问题的对偶问题,对偶问题对应表,例 标准型对偶问题,例：求下列线性规划的对偶,例求下列线性规划的对偶 maxz=3x1-6x2+5x3+x4,x1,x20, x3x4无限制 mins=-5y1-14y2+3y3,y1无限制，y20，y30,定理21 弱对偶定理 若互为对偶的线性规划分别有可行解 则其相应的目标函数值满足,推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。,推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。 推论3 若原始问题可行，则其目标函数无界的充要条件是

8、对偶问题没有可行解。,定理22 最优性准则定理 若X和Y分别是互为对偶的线性规划的可行解 ，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解,定理23 （主对偶定理） 若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。,证明：由两者均有可行解，则根据定理21可知两者均有界，因此均有最优解。,设B是其最优基，X是其对应的基本可行解 令A=(B N)，则：对应于基B的检验数满足,定理23 （主对偶定理）,设B是其最优基，X是其对应的基本可行解 令A=(B N)，则：对应于基B的检验数满足,对偶问题的一个可行解, 其目标值：,对偶最优解的经济含义影子价格,代表着当第i个右

9、端常数增加一个单位时，最优目标函数值的相应增量。 其含议是在目前已给定的情况下，最优目标值随资源数量变化的变化率； 其经济含义是为约束条件所付出的代价。 当B是原问题的最优基时，Y=CBB-1就是影子价格向量。,y1=5/3, y2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。 如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反,五、对偶的经济解释,1、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资

10、源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,w1 w2 wm,4、产品的机会成本,机会成本 表示减少一件产品所节省的资源可以增加的利润,机会成本,利润,差额成本,5、产品的差额成本（Red

11、uced Cost）,差额成本=机会成本 - 利润,机会成本,利润,差额成本,5、产品的差额成本（Reduced Cost）,5、互补松弛关系的经济解释,在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润 （4）机会成本大于利润的产品不安排生产,3 对偶单纯形法,设maxz=cx AX=b X0 若是的一个基，且满足： (1)B-1b0 (2)CBB-1A-C0 则基是（）的最优基，基本解 x=,为最优解,若基满足（）CBB-1A-C0 但B-1b中有负分量，则x=,不是的可行解 若令y=CBB-1 由CBA-C

12、0可得 YAC 即Y=CBB-1是LP的对偶问题 mins=yb YAC 的可行解，即基是问题（）的可行基，称基为对偶可行基，y=CBB-1为（LP）的对偶基本可行解，这样可由满足（）的对偶可行基出发，在保持对偶可行性的同时，换基迭代，直至（）成立。,对偶单纯形法的计算步骤： 如果单纯形表满足CB-A-C0，即检验数满足最优标准，但B-1b中有负分量， 可按下列步骤求解。 （1）确定出基变量。 按minB-1b|B-1b0=bk 确定bk所在行的基变量xk为出基变量。 （2）确定进基变量。 检查akj(j=1,2,n),如果所有akj 0,则问题无可行解，停止计算；否则按,若所给问题是目标函数

13、求极小，则按 确定xr为进基变量。 （3）以akr为主元素，按原单纯形法进行迭代计算，,例：用对偶单纯形法求解下列线性规划问题 min f = 2x1 + x2 s.t. 3x1 + x2 3 4x1 +3x2 6 x1 +2x2 4 x1 , x2 0 解：将问题改写成如下形式 min f = 2x1 + x2 s.t. -3x1- x2 + x3 = -3 -4x1 -3x2 +x4 = -6 x1 +2x2 +x5 = 4 x1 , x2 , x3 , x4 , x5 0,例：用对偶单纯形法求解下列线性规划问题 max f = -x1 - 4x2 -3x4 s.t. x1 + 2x2 -

14、 x3 +x4 3 -2x1 - x2 + 4x3 +x4 2 x1 , x2 , x3 , x4 0 解：将问题改写成如下形式 min f = -x1 - 4x2 -3x4 s.t. -x1 - 2x2 + x3 - x4 + x5 3 2x1 + x2 - 4x3 -x4 + x6 2 x1 , x2 , x3 , x4 , x5 , x6 0,4 灵敏度分析,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。 在实际生产过程中，上述三类因素均是在不断变化的，

15、如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,当系数A，b，C发生改变时，目前最优基是否还最优？ 为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？ 假设每次只有一种系数变化 目标系数C变化 基变量系数发生变化； 非基变量系数发生变化； 右端常数b变化 增加一个变量 增加一个约束 技术系数A发生变化,若B是最优基，则

16、最优表形式如下,灵敏度分析总是在最优表上进行,例：对下列 线性规划进行灵敏度分析,一、目标函数系数C发生改变 1、若cj为非基变量系数，则cj发生改变只会影响j的变化，当j= CBB-1 Pj Cj 0时，最优解不变；否则，应将xj作为进基变量用单纯形法迭代计算，求新的最优解。 2、若cj为基变量系数，则cj发生改变会改变CB，则可能会影响所有变量的检验数。当 CBB-1 N CN 0时，最优解不变；否则，用单纯形法迭代计算，求新的最优解。,如果C3改变,则3= CBB-1 P3 C3=4 - C30即 C34时最优解不变。若设C3=5,则目前解不再是最优解,应该用单纯形方法继续求解。,如果C

17、1改变,则当3 =CBB-1 P3 C3=3-C10, 4 =CBB-1 P4 C4=4/3C1-10, 5 =CBB-1 P5 C5=1-1/3C10, 即 C13时，最优解不变。 若C1=1/2则目前解不再是最优解,应该用单纯形方法继续求解。,二、右端常数b发生改变 bk的变化只会影响最优单纯形表中的B-1b以及最优值CBB-1b。当 B-1b 0时，最优基不变；否则，用对偶单纯形法迭代计算，求新的最优解。,如果b1改变,则当 即9/4b1 9时，最优基不变。 若b1=2则目前解不再是最优解,应该用对偶单纯形方法继续求解。,如果b2改变,则当 即3b2 12时，最优基不变。 若b2=2则目

18、前解不再是最优解,应该用对偶单纯形方法继续求解。,三、约束系数矩阵A发生改变 1、若aij为非基变量系数，则aij 发生改变只会影响j的变化，当j= CBB-1 Pj Cj 0时，最优解不变；否则，应将xj作为进基变量用单纯形法迭代计算，求新的最优解。 2、若aij 为基变量系数，则aij 发生改变会改变B-1，则可能会影响所有变量的检验数CBB-1 N CN 及约束右端项B-1b。 (1)当 CBB-1 N CN 0且B-1b0时，最优基不变； (2)当 CBB-1 N CN 0且B-1b0时，用单纯形法迭代计算，求新的最优解。,(3)当 CBB-1N CN 0且B-1b0时，用对偶单纯形法迭代计算，求新的最优解; (4)当 CBB-1N CN 0且B-1b0时，需引入人工变量现将原问题的解化为可行解，再用单纯形法迭代计算，求新的最优解。 若a13变动，则当,即a13 2/5时，最优解不变。,若a23变动，则当,即a23 4时，最优解不变。,若a12变动，,即4-a12 0, 14-11a12 0 , 3-2a12