运筹学对偶理论l.ppt

1、运 筹 学,第二章对偶理论与灵敏度分析,1对偶问题的提出,内容一致但从相反角度提出的一对问题称为对偶问题。,引例1：某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示，问应该如何安排计划才能使该工厂获利最多？,若工厂的决策者不生产产品I、II，而是将之出租或出售，则工厂的决策者就要考虑给每种资源如何定价的问题。显然，出让这些资源的代价不应低于自己组织生产活动时的利润。已知原模型为：,对偶问题的提出,若yi为出让第i种资源的单位收益，则应有 1y1+4y2+0y32产品I 2y1+0y2+4y33产品II 则出让所得总收入，即为购买者的总支出

2、希望达到最小，因此有 min W=8y1+16y2+12y3 即得LP问题：,称这一LP问题为原LP问题的对偶问题。,对偶理论,任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,2线性规划对偶理论,2.1 原问题与对偶问题的关系,我们将前面的LP原问题与其对偶问题进行比较有： 一个问题的约束条件个数等于另一问题中变量数； 一问题目标函数系数是另一问题

3、中约束条件的右端项； 一问题约束条件为“”，另一则为“”； 一个为求极大，另一个为求极小。 上述关系可写为下表：,原问题与对偶问题的关系,例1写出下述LP问题的对偶问题。,例2写出上例中对偶问题的对偶问题。 解：先将之化为目标极大、约束为的形式得：,结论：原问题与对偶问题互为对偶。,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,对称形式的对偶问题,对偶问题的定义,例3：写出下面LP问题的对偶问题。,解：令 z-z, x1-x1, x4 x4 - x4，拆为两式得，,(-1)，(-1)，得，,直接写出其对偶问题，有,令w-w, y2-y2, y3y3y3,得，,min z2x13x25x3

4、x4 x1x23x3x45 2x12x3x44 x2x3x46 x10，x2，x30，x4无约束,对偶问题的定义,对偶问题的定义,一般线性规划问题的对偶问题,对偶问题的定义,对偶问题对应表,对偶问题的写出,例4：写出下面问题的对偶问题,对偶问题的写出,例5：写出下面问题的对偶问题,2对偶问题的基本性质,性质1（弱对偶性） 若互为对偶的LP问题(1)、(2)分别有可行解：,则其相应的目标函数值满足,(1),(2),弱对偶定理,几个推论,推论1 极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。 推论2 极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目

5、标函数值的一个上界。 推论3 若原始问题有可行解，则其目标函数无界的充要条件是对偶问题没有可行解。 注：反之不一定成立。,对偶问题的基本性质,性质2（最优性） 若X*和Y*分别是互为对偶的线性规划的可行解，且使CX*=Y*b，则X*和Y*分别是相应线性规划问题的最优解。,证：由弱对偶定理可知，对任意可行解有： CXYb 因此对于X*和Y*也分别有： CXY*b，CX*Yb 又因为 CX*=Y*b 故有Y*b Yb，CXCX*对任意的X、Y均成立，即X*、Y*是各自的最优解。,对偶问题的基本性质,性质3（强对偶性对偶定理） 若原问题和对偶问题两者均有可行解，则两者均有最优解，且此时目标函数值相同

6、。,证明：由两者均有可行解，则根据定理1可知两者均有界，因此均有最优解。,设B是其最优基，X*是其对应的最优解， 令A=(B，N)，则对应于基B的检验数满足,对偶问题的基本性质,性质3（强对偶性对偶定理）的证明,设B是其最优基，X*是其对应的最优解， 令A=(B N)，则对应于基B的检验数满足,Y*是对应对偶问题的一个可行解，其目标值：,于是，由性质2，Y*也是对应对偶问题的最优解。,对偶问题的基本性质,性质4（互补松驰性） 在LP问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。即,若y*0，则,若xj

7、*0，则,对偶问题的基本性质,性质5 1。用单纯形法求解LP问题时，迭代的每一步在得到原问题一个基本可行解时，其检验数行的(zjcj)值是其对偶问题的一个基解； 2。在单纯形表中，原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量； 3。这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量； 4。将这两个解代入各自的目标函数中有zw。,对偶问题的基本性质,例：设有线性规划问题及其对偶：,对偶问题的基本性质,例：如下两个LP问题的最终单纯形表为：,3影子价格,对偶问题最优解的经济含义影子价格,其对偶变量yi相当于是对第i种资源的估价，但它不是资源的市场

8、价格，而是按照该资源对企业生产活动的贡献做出的估计，因而称之为影子价格（Shadow Price）。 代表着当第i个右端常数增加一个单位时，最优目标函数值的相应增量。 其含义是在目前已给定的情况下，最优目标值随资源数量变化的变化率； 其经济含义是为约束条件所付出的代价。 当B是原问题的最优基时，Y=CBB-1就是影子价格向量。,影子价格举例,y1=5/3, y2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。 如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反,4对偶单纯形法,

9、对偶单纯形法并不是求对偶问题的解，而是利用对偶理论求原问题的解的方法。 基本原理：保持对偶问题为可行解（即检验数全小于等于零而不考虑其是否为可行解）的基础上，通过迭代，当原问题也为可行解（即表中解为非负）时，就得到了最优解。,对偶单纯形法举例,例：用对偶单纯形法求解：,对偶单纯形法举例,对偶单纯形法举例,对偶单纯形法,步骤： 1。建立一个初始单纯形表，使其检验数cj- zj全部0（即对其对偶问题而言是一个基本可行解）； 2。找出表中b对应列中负的最大数（若没有，即为最优），该行对应的变量即为换出变量xl； 3。找出表中xl所在行的负系数alk（若无，则无可行解），计算(cj- zj)/alk，

10、并取其最小者所对应的列的非基变量xk为换入变量； 4。以alk为主元素进行迭代，并重复直到结束。,5灵敏度分析,在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。 在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，

11、企业应当预先了解，当各项因素变化时，应当作出什么样的反应。,灵敏度分析,当系数A，b，C发生改变时，目前最优基是否还最优？ 为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？ 假设每次只有一种系数变化 目标系数C变化 基变量系数发生变化； 非基变量系数发生变化； 右端常数b变化 增加一个变量 增加一个约束 技术系数A发生变化,灵敏度分析,例：线性规划问题,灵敏度分析,灵敏度分析,3-2*（-1）-3*2=-1,检验数在单纯形表中的对应关系：,灵敏度分析,价值系数CN发生改变,c3,c3-4,如果c34，则目前解不再是最优解，应该用单纯形方法继续求解,否则解不变。即对于c3而言，使最

12、优解不变的条件是c34。,灵敏度分析,价值系数CN发生改变， c35,灵敏度分析,价值系数CB发生改变,c1-3,c1,c1,1-4/3*c1,1/3*c1-1,c1-3 0，1-4/3*c10，1/3*c1-10 解之得，3/4c13,灵敏度分析,价值系数CB发生改变，c1=1/2,得新的最优解为x2=9/4， x4=3/4，,灵敏度分析,价值系数CB发生改变，c1=4,得新的最优解为x1=3， x5=6，,灵敏度分析,右端常数b发生改变，b1变化,b1或b1,4b1/3-3,3-b1/3,9/4b19,或,-3/4b16 b1=3+b1,灵敏度分析,右端常数b发生改变，b1=2,灵敏度分析

13、,右端常数b发生改变，b1=12,灵敏度分析,右端常数b发生改变，b2变化,b2,4-b2/3,b2/3-1,3b2 12,灵敏度分析,增加一个变量 若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列 其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。 若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,灵敏度分析,设有新的产品准备生产，相应的资源消耗为,，新产品的单位利润为5单位。,灵敏度分析,增加一个约束 在企业

14、的生产过程中，经常由于工艺的变化或新材料、新方法的应用，使原来的资源条件改变，需要在原有的资源上增加使用一种或多种资源，反应到LP模型中，则是增加一个或多个约束条件。 若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。 若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。,灵敏度分析,例：增加约束,灵敏度分析,增加约束,用初等行变换把基对应的矩阵化为单位矩阵得,灵敏度分析,A中元素改变 如果N中数据改变，可以用增加一个变量来处理 如果B中元素改变，则情况较复杂，一般需要修改问题后重新求解,讨论,在极大化问题的下面的单纯形表中，六个常数，1，2， 3，1， 2之值未知（假定无人工变量），分别写出对六个未知数的约束条件，使以下各小题关于该表的说