运筹学教程第3章.pptx

1第三章 线性规划问题的对偶与灵敏度分析线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析本章内容重点第1页/共53页21.1.线性规划对偶问题 对偶原理 对偶问题定义 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。对偶定理 只需了解原问题与对偶问题解的关系，证明从略。第2页/共53页3 1.1.对偶问题：若第二章例2.12.1问题的设备都用于外协加工，工厂收取加工费。试问：设备 A A、B B、C C 每工时各如何收费才最有竞争力？设 y y1 1，y y2 2，y y3 3 分别为每工时设备 A A、B B、C C 的收取费用。1.1.线性规划对偶问题第3页/共53页4线性规划原问题 例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500第4页/共53页5 Max z=1500 x1+2500 x2 s.t.3x1+2x2 65 2x1+x2 40 原问题原问题 3x2 75 x1,x2 0 Min f=65y1+40y2+75y3 s.t.3y1+2y2 1500 （不少于甲产品的利润）2y1+y2+3y3 2500 对偶对偶问题问题 （不少于乙产品的利润）y1,y2,y3 01.1.线性规划对偶问题第5页/共53页6 2、对偶定义 对称形式：互为对偶 (LP)Max z=cT x (DP)Min f=bT y s.t.Ax b s.t.AT y c x 0 y 0 “Max-”“Min-”1.1.线性规划对偶问题第6页/共53页7 一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。1.1.线性规划对偶问题第7页/共53页8 (2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。1.1.线性规划对偶问题第8页/共53页9 非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。（1）将 模 型 统 一 为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；1.1.线性规划对偶问题第9页/共53页10 （3）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个 约束为等式。下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+a1nxn=b1 那么，这个等式与下面两个不等式等价1.1.线性规划对偶问题第10页/共53页111.1.线性规划对偶问题这样，原规划模型可以写成第11页/共53页121.1.线性规划对偶问题 此时已转化为对称形式，直接写出对偶规划这里，把 y1 看作是 y1=y1-y1，于是 y1 没有非负限制，关系（2）的说明完毕。第12页/共53页131.1.线性规划对偶问题 例3.1 写出下面线性规划的对偶规划模型解 先将约束条件变形为“”形式第13页/共53页141.1.线性规划对偶问题 再根据非对称形式的对应关系，直接写出对偶规划第14页/共53页151.1.线性规划对偶问题第15页/共53页16 3.对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）定理3-1(弱对偶定理）若 x,y 分别为（LP)和（DP）的可行解，那么cTx bTy。推论 若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。1.1.线性规划对偶问题第16页/共53页17 定理3-2(最优性准则定理)若x,y分别(LP),(DP)的可行解,且cTx=bTy，那么x,y分别为(LP)和(DP)的最优解。定理3-3(主对偶定理)若(LP)和(DP)均可行 那么(LP)和(DP)均有最优解,且最优值相等。以上定理、推论对任意形式的相应性规划的对偶均有效1.1.线性规划对偶问题第17页/共53页18 4.4.影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*分别为（LP）和（DP）的最优解，那么，cT x*=bT y*。根据 f=bTy*=b1y1*+b2y2*+bmym*可知 f/bi=yi*yi*表示 bi 变化1个单位对目标 f 产生的影响，称 yi*为 bi的影子价格。注意：若 B 是最优基，y*=(BT)-1 cB 为影子价格向量。1.1.线性规划对偶问题第18页/共53页19 影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。1.1.线性规划对偶问题第19页/共53页201.1.线性规划对偶问题 （2）影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是第20页/共53页21 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。1.1.线性规划对偶问题第21页/共53页22 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。1.1.线性规划对偶问题第22页/共53页23 5.由最优单纯形表求对偶问题最优解 标准形式：Max z=50 x1+100 x2 s.t.x1+x2+x3 =300 2x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 01.1.线性规划对偶问题第23页/共53页24-c-cB BT TB B-1-1I IB B=(p p1 1,p,p4 4,p,p2 2)oTB B-1-1最优解 x1=50 x2=250 x4 =50影子价格 y y1 1=50 =50 y y2 2=0 =0 y y3 3 =50,=50,B B-1-1对应的检验数 T T=c cB BT TB B-1-1 。1.1.线性规划对偶问题第24页/共53页25 对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。2.2.对偶单纯形法第25页/共53页26 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原 规划的可行解时，便 得到原规划的最优解。2.2.对偶单纯形法第26页/共53页27 对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。2.2.对偶单纯形法第27页/共53页28 1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0(j=1,2,n)，则原问题无可行解,停止;否则,若有akj0 则选 =minj/akjakj0=r/akr那么 xr为进基变量,转4；4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。对偶单纯形法求解线性规划问题过程：2.2.对偶单纯形法第28页/共53页29例3.2：求解线性规划问题：标准化：Max z=-2x1-3x2 -4x3 s.t.-x1-2x2-x3+x4=-3 -2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0Min f=2x1+3x2+4x3 S.t.x1+2x2+x3 3 2x1-x2+x3 4 x1,x2,x3 0 2.2.对偶单纯形法第29页/共53页30表格对偶单纯形法2.2.对偶单纯形法第30页/共53页31单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法0csMinj/asjasj0brMin-bi/airair03.3.灵敏度分析第45页/共53页46 例3.5:上例最优单纯形表如下 3.3.灵敏度分析第46页/共53页47 0 0.25 0 这里 B B-1=-2 0.5 1 0.5-0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1,x5,x2分别变为：4+04=4,4+(-2)4=-40,2+0.54=4用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)T f*=173.3.灵敏度分析第47页/共53页48 增加一个变量 增加变量 xn+1 则有相应的pn+1,cn+1。那么 计算出B B-1pn+1,n+1=cn+1-cri ari n+1 填入最优单纯形表,若 n+1 0 则 最优解不变；否则，进一步用单纯形法求解。3.3.灵敏度分析第48页/共53页49例3.6:例3.4增加x6,p6=(2,6,3)T,c6=5 计算得到用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T f*=16.53.3.灵敏度分析第49页/共53页50 增加一个约束 增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。3.3.灵敏度分析第50页/共53页51例3.7:例3.4增加3x1+2x215，原最优解不满足这个约束。于是3.3.灵敏度分析经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为 13.75第51页/共53页52 A A中元素发生变化(只讨论 N 中某一列变化情况）与增加变量 xn+1 的情况类似，假设 pj 变化。那么，重新计算出 B B-1pj j=cj-cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。（例子从略）3.3.灵敏度分析第52页/共53页53感谢您的观看！第53页/共53页