《对偶理论及灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《对偶理论及灵敏度分析.ppt（91页珍藏版）》请在三一文库上搜索。
1、对偶理论及灵敏度分析,（一）基本要求 1、了解对偶问题的特点，熟悉互为对偶问题之间的关系 2、掌握对偶理论及其性质 3、掌握对偶单纯形法 4、掌握限制常数和价值系数、约束条件系数的变化对原最优解的影响 5、掌握增加新变量和增加新约束条件对原最优解的影响，并求出相应因素灵敏度的范围 6、了解影子价格的经济意义 （二）重点 1、对偶单纯形法 2、灵敏度分析 （三）难点 灵敏度分析,对偶理论 对偶单纯形方法 灵敏度分析,对偶理论及灵敏度分析,对偶理论,对偶问题概念： 任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解
2、有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,问题的导出,问题的导出,假设有客户提出要求，购买工厂所拥有的工时和材料，为客户加工别的产品，由客户支付工时费和材料费。那么工厂给工时和材料制订的最低价格应是多少，才值得出售工时和材料 ?,问题的导出,出卖资源获利应不少于生产产品的获利; 约束 价格应该尽量低，这样，才能有竞争力; 目标 价格应该是非负的,问题的导出,用y1和y2分别表示工时和材料的出售价格,总利润最小 min W=3y1+9y2 保证A产品利润 y1+y22 保证B
3、产品利润 y1+4y23 保证C产品利润 y1+7y23 售价非负 y10 y20,问题的导出,问题的导出,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,对称形式的对偶问题,或,对偶问题的定义,对偶问题的特点： 若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然 原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。,对偶问题的定义,非对称形式对偶问题的处理 等式约束的线性规划问题如下： （1）先将等式约束条件分解为两个不等式约束条件,对偶问题的定义,（2）按对称形式变换关系写出它的对偶问题,
4、整理得,对偶问题的定义,由此可见，yi不受正负限制。将yi代入上述 线性规划问题，得到对偶问题为；,对偶问题的定义,一般线性规划问题的对偶问题,对偶问题的定义,一般线性规划问题的对偶问题可归纳如下对应关系：,对偶问题的写出,例1标准型对偶问题,对偶问题的写出,例2,例 max =2x1+x2+3x3+x4 s.t. x1+x2+x3+x45 2x1-x2+3x3 =-4 x1 -x3+x4 1 x10,x2,x4无约束,x3 0,min =5y1-4y2+y3 s.t. y1+2y2+y3 2 y1-y2 =1 y1+3y2-y3 3 y1 +y3 =1 y10，y2无约束， y3 0,其对偶
5、问题为,对偶问题的写出,练习写出对偶问题,max =x1-x2+5x3-7x4 s.t. x1+3x2-2x3+x4=25 2x1 +7x3 +2x4 -60 2x1 +2x2 -4x3 30 x4 10 -x4 5 x1, x2 0, x3 ,x4无约束,练习,max =x1-x2+5x3-7x4 s.t. x1+3x2-2x3+x4=25 2x1 +7x3+2x4 -60 2x1 +2x2 -4x3 30 x4 10 -x4 5 x1, x2 0, x3 ,x4无约束,对偶问题的基本性质,（1）对称性： 对偶问题的对偶问题是原问题。,(P),(D),对偶问题的基本性质,（2）弱对偶性 若互
6、为对偶的线性规划分别有可行解 则其相应的目标函数值满足,对偶问题的基本性质,（3）无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,对偶问题的基本性质,（4） 最优性准则定理 若X和Y分别是互为对偶的线性规划的可行解 ，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解,对偶问题的基本性质,（5）对偶定理 若原问题有最优解，那么对偶问题也有最优解，且此时目标函数值相等。,证明：设 是原问题的最优解，它对应的基矩阵为B，则必定所有检验数：,令 ，则,即 是对偶问题的可行解 所以对偶问题的目标值,而 是原问题的最优解，其目标函数取值为：,由最优性准则定理知， 是对偶问题的
7、最优解。,（6）互补松驰性(松紧定理) ： 若 ，分别是(P),(D)问题的可行 解，那么 ,为最优解的充要条 件是： XS=0,YS =0 (即若 Ai i=0 Ai =bi 0 Pj=Cj 0 PjCj = j=0),对偶问题的基本性质,XS=0,YS =0,原问题第i个约束方程是等式约束,若原问题第i个约束方程是不等式约束,例1.已知下列线性规划问题 max =x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 xj0, j=1,2,3,4 已知其对偶问题的最优解为y1=1.2,y2=0.2 运用对偶理论找出原问题的最优解,解其对偶
8、问题为 min =20y1+20y2 s.t. y1+2y21 2y1+y22 2y1+3y23 3y1+2y24 y1,y20,(1.2,0.2),.,.,y1,互补松驰性(松紧定理),已知对偶问题的最优解 y1=1.2, y2=0.2,因y10,y20。所以x5=x6=0，即原问题为等式约束,互补松驰性(松紧定理),将y1=1.2,y2=0.2代入对偶问题的 约束条件，得 y30,y40,所以x1=x2=0,min =20y1+20y2 s.t. y1+2y2- y3 =1 2y1+y2- y4=2 2y1+3y2- y5=3 3y1+2y2- y6=4 y1,y20,互补松驰性(松紧定理
9、),x1=x2=0 x1+2x2+2x3+3x4=20 2x1+x2+3x3+2x4=20,即 x1=x2=0，x3=4,x4=4 原问题的最优解为(0,0,4,4)T,max =x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+3x420 2x1+x2+3x3+2x420 xj0, j=1,2,3,4,互补松驰性(松紧定理),（7）原问题单纯形表的检验数行对应其对偶问题的一个基解.,对偶问题的基解,YS1为对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。,对偶问题的基解,例.max =x1+4x2+3x3 s.t. 2x1+2x2+x34 x1+2x
10、2+2x36 xj0,对偶问题为 min =4y1+6y2 s.t. 2y1+y21 2y1+2y24 y1+2y23 y1,y20,对偶问题的基解,对偶问题的基本解为y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3,对偶问题的基解,X4 X5,由原问题的最终表可知， y1=1,y2=1(最优解)， ys1=2，ys2=0 ，ys3=0,其最终表为,对偶问题的基解,X2 X3,在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么?,设B是max z=CXAXb，X0的最优基， 则 z*=CBB-1b=Y*b
11、 。 对z求偏导数，得,影子价格,变量yi*的经济意义是在其他条件不变的情况下， 单位资源变化所引起的目标函数的最优值的变化。,yi*的值代表对第i种资源的估价-影子价格,这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。,影子价格,从原始问题最优表求影子价格,当B是原问题的最优基时，Y=CBB-1就是影子价格向量。,初始表,最优表,影子价格,y1=5/3,
12、y2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。 如果有客户以高于5/3的价格购买工时，则可以出售一些工时。,对偶单纯形法,对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。,根据对偶问题的对称性，单纯形表的迭代过程也可以反过来进行，即保持对偶问题的解始终是基本可行解（即C-CBB-1A0），而使原问题从基本非可行解迭代到基本可行解，从而使原问题和对偶问题同时得到最优解。这种单纯形表的应用方法称之为对偶单纯形法。,对偶单纯形法的计算步骤如下：,(1) 根据线性规
13、划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。 若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。 (2) 确定换出变量 按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xl为换出变量。,对偶单纯形法,(3)确定换入变量 在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。 若存在lj0 (j=1,2,，n), 计算,按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。 (4) 以lk为主元素，按原单纯形法在表中进行迭代运算，得到
14、新的计算表。 重复步骤(1)(4)。,对偶单纯形法,对偶单纯形法举例,例 用对偶单纯形法求解：,对偶单纯形法举例,对偶单纯形法举例,最优解为y1=5/3,y2=1/3, 最优值Z=-8,Wmin=8,对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,对偶单纯形法,例. min =3x1+4x2+5x3 s.t. x1+2x2+3x35 2x1+2x2+x36 x1,x2,x30,解 问题化为 max W=-3x1-4x2-5x
15、3 s.t. -x1-2x2-3x3+x4 =-5 -2x1-2x2-x3 +x5=-6 x1,x2,x3,x4,x50,对偶单纯形法练习,所以最优解为x1=1,x2=2,x3=0，min=11,对偶单纯形法练习,xj,对偶单纯形法的适用范围： 适合于解如下形式的线性规划问题,在引入剩余变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。,对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法
16、是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。,灵敏度分析,在生产计划线性规划问题的一般形式中， A代表企业的技术状况， b代表企业的资源状况， C代表企业产品的市场状况 在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。,在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是，则最优解如何变化，这就是灵敏度分析。 如果不是，应该如何修订原来的最优计划。更进一步，为了防止在各类
17、状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,灵敏度分析,灵敏度分析,当系数A，b，C发生改变时，目前最优基是否还最优？目前的最优解是否还最优？ 为保持目前最优基或最优解还是最优，系数A，b，C的允许变化范围是什么？ 假设每次只有一种系数变化 目标函数系数C变化 a、基变量系数发生变化； b、非基变量系数发生变化； 右端常数b变化 技术系数A发生变化 a、增加一个变量 b、增加一个约束,灵敏度分析,若B是最优基，则最优表形式如下,灵敏度分析总是在最优表上进行,灵敏度分析,例 线性规划,灵敏度分析,例 线性规划,灵敏
18、度分析,例 线性规划,3-2*（-1）-3*2=-1,当aij,bi,cj中的一个或几个发生变化时，已求得的线 性规划问题的最优解会有什么变化？如何求解新的 最优解？,价值系数C的改变,a、价值系数CN （非基变量的价值系数）发生改变,C3,C3-4,如果C34,则目前解不再是最优解,应该用单纯形方法继续求解,否则解不变。即对于C3而言,使最优解不变的条件是C34。,价值系数C的改变,价值系数CN发生改变,5,价值系数C的改变,b、价值系数CB （基变量的价值系数)发生改变,C1-3,1-4/3C1,1/3C1-1,C1-3 0, 1-4/3C10, 1/3C1-10 C13 若C13/4 则
19、x4进基，x1出基 若3 C1 则x3或x5进基，x2出基,价值系数C的改变,价值系数CB发生改变,1/2,1/2,价值系数C的改变,价值系数CB发生改变,资源数量b变化的分析,右端常数b1的改变范围,b1,4b1/3-3,3-b1/3,9/4b1 9,-3-5b1/3,资源数量b变化的分析,右端常数b1发生改变,2,资源数量b变化的分析,右端常数b1发生改变,12,例.线性规划问题 max =-x2+3x3-2x5 s.t. x1+3x2-x3 +2x5 =7 -2x2+4x3+x4 =12 -4x2+3x3 +8x5+x6 =10 xj0,资源数量 b 变化的分析,B=P2,P3,P6,要
20、使最优基不变，求b2的变动范围,要保持最优基不变，则 -14/3b234,若b2超出此范围，则b0 可用对偶单纯形法继续求解,例上题中，若令b2增加b2=30,则,将上式结果反映到最终表中，得下表,资源数量b变化的分析,求右端常数b2改变范围,b2,4-b2/3,b2/3-1,3b2 12,-b2/3-5,练习,技术系数A发生变化的分析,a、增加一个变量 若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。 若检验数非正，则原最优解仍为最优，原生产计划不变，
21、不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,增加一个变量,例.某工厂计划生产A,B,C三种产品，需要甲,乙两种资源。资源限量、每种产品的单位利润和单位产品的资源消耗量如下表所示，试确定使利润最大的生产计划。,练习：,解以x1,x2 ,x3分别表示A,B,C三种产品的产量，则该问题的线性规划模型如下：,max =2x1+3x2+x3 s.t. 1/3x1+1/3x2+1/3x31 1/3x1+4/3x2+7/3x33 x1,x2,x30,引入松驰变量，可得初始单纯形表,最终单纯形表为,假设这个工厂研制了一种新产品D，单位新产品D所需耗用的甲乙两种
22、资源分别为1/2和1/2，新产品的利润为4元，问应怎样调整生产计划？,max =2x1+3x2+x3 s.t. 1/3x1+1/3x2+1/3x31 1/3x1+4/3x2+7/3x33 x1,x2,x30,P6=B-1P6=,技术系数A发生变化的分析,b、增加一个约束 为提高产品质量，要增加一道加工工序，即会给原问题增加一个约束条件。 若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。 若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,技术系数A发生变
23、化的分析,例 增加约束,将新的约束条件引入松驰变量后，写入最终单纯形表，并把XB,XS 的系数列向量化为单位向量，再求解。,技术系数A发生变化的分析,增加约束,技术系数A发生变化的分析,c、A中某列向量的变化 （1）如果系数矩阵A中某一列向量Pj发生了变化，且其对应的变量xj为非基变量，那么Pj的变化只影响最终表中的检验数j。 若 Pj变为Pj，则j=cj-CBB-1Pj 如果j 0，则说明Pj变换后并不影响当前解； 如果j0，则说明Pj变换后影响到当前解，需要求出最终表中第j列的新数据B-1Pj填入最终表第j列，然后以xj为进基变量继续迭代，直到得到最优解。,技术系数A发生变化的分析,（2）
24、如果系数矩阵A中发生变化的列向量Pj为基变量对应的向量，则Pj变化后不仅影响变量xj的检验数，而且影响到最终表中Pj对应的向量也不再是单位列向量，即B和B-1都要变，这时要求出最终表中xj列的数，并通过迭代使该列恢复单位列向量，再根据恢复后的状态予以处理。 例 分析原计划生产产品的工艺结构发生变化。以第1章例1为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术系数向量变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?,技术系数A发生变化的分析,同时计算出x1的检验数为 c1-CBB-1P1 =4-(1.5,0.125,0)(2,5,2)T=0.375 将以上计算结果填入最终表x1的列向量位置. 得下表。,解 把改进工艺结构的产品看作产品，设x1为其产量。于是在原计算的最终表中以x1代替x1，计算对应x1的列向量。,表 2-14,可见x1为换入变量，x1为换出变量，经过迭代。,表 2-15,讨论题,已知线性规划问题,最终单纯形表,讨论题,试用灵敏度分析的方法判断 1.目标函数 或 分别在什么范围内变化，上述最优解不变； 2.约束条件右端项 ， 当一个不变时，另一个在什么范围内变化上述最优基不变； 3.问题的目标函数变为 上述最优解的变化； 4.约束条件右端项 变为 时,上述最优解的变化,