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

第二章线性规划的对偶理论与灵敏度分析§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.1)的标准线性规划问题表示为以下形式：设在某步迭代中的基为B，相应的m个基变量为XB，C中与XB对应的m个元素记为CB。不妨设(AI)的前m列为B，则(2.1)可表示为即maxf=CBXB+CNXN+CⅡXⅡ(2.3)BXB+NXN+XⅡ=b(2.4)XB≥0,XN≥0,XⅡ≥0(2.5)将(2.3)变为f-CBXB-CNXN-CⅡXⅡ=0(2.6)(2.4)两端左乘B-1则有XB+B-1NXN+B-1XⅡ=B-1b(2.7)并且有XB=B-1b-B-1NXN-B-1XⅡ(2.8)将其代入(2.6)得f–CBB-1b+CBB-1NXN+CBB-1XⅡ–CNXN-CⅡXⅡ=0f+(CBB-1N–CN)XN+(CBB-1–CⅡ)XⅡ=CBB-1b(2.9)可将(2.7),(2.9)表示为f10CBB-1N–CNCBB-1–CⅡXB=CBB-1b0IB-1NB-1XNB-1bXⅡ(2.10)(2.2)和(2.10)所对应的单纯形表如下基变量XBXNXⅡ解fCⅡB-CBCⅡN-CN0CⅡbXⅡBNIb基变量XBXNXⅡ解f-CB-CN00XⅡBNIb基变量XBXNXⅡ解f0CBB-1N–CNCBB-1–CⅡCBB-1bXBIB-1NB-1B-1b从以上两张表可知：（1）对应初始单纯形表中的单位阵I，迭代后的单纯形表中为B-1。（2）迭代到某一步的基可行解为XBB-1bXN=0XⅡ0（3）若初始单纯形表中变量xj的系数向量为Pj，迭代后的单纯形表中为B-1Pj。（4）当CBB-1N–CN≥0，CBB-1–CⅡ≥0时为最优单纯形表，其解为最优解，并且CBB-1N–CN≥0与CBB-1A–CⅠ≥0等价。xj的检验数记为σj=CBB-1Pj–Cj（5）若CBB-1N–CN0，CBB-1–CⅡ0,这时不是最优解，应选择检验数最小的变量xk为进基变量。（6）根据最小θ规则确定出基变量，即则相应的xl为出基变量，其中Pk为进基变量xk对应的列向量，而()j表示在圆括号内列向量的第j个元素。（7）单纯形表中，所有非基变量的检验数大于零，则此问题有为以最优解。（8）在最优单纯形表中，所有检验数大于等于零，而某一个非基变量xk的检验数等于零，则此问题有无穷多最优解。（9）在某单纯形表中，某一变量xk的检验数小于零，而相应Pk≤0则此问题无有限最优解。§2线性规划问题的对偶问题对偶问题概念：任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。ABC拥有量工时1113材料1479单件利润233假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出卖工时和材料?•出卖资源获利应不少于生产产品的获利;约束•价格应该尽量低，这样，才能有竞争力;目标•价格应该是非负的用y1和y2分别表示工时和材料的出售价格总利润最小minW=3y1+9y2保证A产品利润y1+y2≥2保证B产品利润y1+4y2≥3保证C产品利润y1+7y2≥3售价非负y1≥0y2≥0ABC拥有量工时1113材料1479单件利润233对称形式的对偶问题对称形式的对偶问题对偶问题的特点•若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然•原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵•极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。一般线性规划问题的对偶问题原问题（对偶问题）对偶问题（原问题）目标函数maxZ目标函数minZ约束条件：m个第i个约束类型为“≤”第i个约束类型为“≥”第i个约束类型为“＝”变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量约束条件：n个第j个约束类型为“≥”第j个约束类型为“≤”第j个约束类型为“＝”对偶问题对应表•例标准型对偶问题例：求下列线性规划的对偶例求下列线性规划的对偶maxz=3x1-6x2+5x3+x4x1,x2≥0,x3x4无限制mins=-5y1-14y2+3y3y1无限制，y2≥0，y3≥0定理2－1弱对偶定理若互为对偶的线性规划分别有可行解则其相应的目标函数值满足推论1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。推论2极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推论3若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。定理2－2最优性准则定理若X和Y分别是互为对偶的线性规划的可行解，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解证明：由弱对偶定理可知，对任意可行解有，CX≤Yb因此对于X和Y也将分别有CX≤YbCX≤Yb又因为CX=Yb故有Yb≤YbCX≤CX定理2－3（主对偶定理）若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。证明：由两者均有可行解，则根据定理2－1可知两者均有界，因此均有最优解。设B是其最优基，X是其对应的基本可行解令A=(BN)，则：对应于基B的检验数满足定理2－3（主对偶定理）设B是其最优基，X是其对应的基本可行解令A=(BN)，则：对应于基B的检验数满足对偶问题的一个可行解,其目标值：对偶最优解的经济含义――影子价格代表着当第i个右端常数增加一个单位时，最优目标函数值的相应增量。其含议是在目前已给定的情况下，最优目标值随资源数量变化的变化率；其经济含义是为约束条件所付出的代价。当B是原问题的最优基时，Y=CBB-1就是影子价格向量。ABC拥有量工时1113材料1479单件利润233y1=5/3,y2=1/3即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、wm称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=miny3、资源影子价格的性质■影子价格越大，说明这种资源越是相对紧缺■影子价格越小，说明这种资源相对不紧缺■如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0w1w2wm4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源机会成本利润差额成本05、产品的差额成本（ReducedCost）差额成本=机会成本-利润机会成本利润差额成本5、产品的差额成本（ReducedCost）5、互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产§3对偶单纯形法设ＬＰmaxz=cxAX=bX≥0若Ｂ是ＬＰ的一个基，且满足：(1)B-1b≥0(2)CBB-1A-C≥0则基Ｂ是（ＬＰ）的最优基，基本解x=为最优解若基Ｂ满足（２）CBB-1A-C≥0但B-1b中有负分量，则x=不是ＬＰ的可行解若令y=CBB-1由CＢB－１A-C≥0可得YA≥C即Y=CBB-1是LP的对偶问题ＤＰmins=ybYA≥C的可行解，即基Ｂ是问题（ＤＰ）的可行基，称基Ｂ为对偶可行基，y=CBB-1为（LP）的对偶基本可行解，这样可由满足（２）的对偶可行基出发，在保持对偶可行性的同时，换基迭代，直至（１）成立。对偶单纯形法的计算步骤：如果单纯形表满足CＢB-１A-C≥0，即检验数满足最优标准，但B-1b中有负分量，可按下列步骤求解。（1）确定出基变量。按min{B-1b|B-1b0}=bk确定bk所在行的基变量xk为出基变量。（2）确定进基变量。检查akj(j=1,2,…,n),如果所有akj≥0,则问题无可行解，停止计算；否则按若所给问题是目标函数求极小，则按确定xr为进基变量。（3）以akr为主元素，按原单纯形法进行迭代计算，例：用对偶单纯形法求解下列线性规划问题minf=2x1+x2s.t.3x1+x2≥34x1+3x2≥6x1+2x2≤4x1,x2≥0解：将问题改写成如下形式minf=2x1+x2s.t.-3x1-x2+x3=-3-4x1-3x2+x4=-6x1+2x2+x5=4x1,x2,x3,x4,x5≥0基变量x1x2x3x4x5解f-2-10000x3x4x5-3-1100-4-301012001-3-64f-2/300-1/302x3x2x5-5/301-1/304/310-1/30-5/3002/31-12-1f00-2/5-1/5012/5x1x2x410-3/51/50014/5-3/5000-1113/56/50例：用对偶单纯形法求解下列线性规划问题maxf=-x1-4x2-3x4s.t.x1+2x2-x3+x4≥3-2x1-x2+4x3+x4≥2x1,x2,x3,x4≥0解：将问题改写成如下形式minf=-x1-4x2-3x4s.t.-x1-2x2+x3-x4+x5≥32x1+x2-4x3-x4+x6≥2x1,x2,x3,x4,x5,x6≥0基变量x1x2x3x4x5x6解f1403000x5x6-1-21-11021-4-101-3-2f021210-3x1x612-11-100-3-2-3213-8f01/201/221/2-7x1x317/205/2-2-1/203/213/2-1-1/274§4灵敏度分析在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化①目标系数C变化基变量系