线性规划问题对偶与灵敏度分析

《线性规划问题对偶与灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划问题的对偶与灵敏度分析线性规划的对偶问题概念、理论及经济意义线性规划的对偶单纯形法线性规划的灵敏度分析本章内容重点11.线性规划对偶问题对偶原理对偶问题定义——线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。对偶定理——只需了解原问题与对偶问题解的关系，证明从略。21.对偶问题：若第二章例2.1问题的设备都用于外协加工，工厂收取加工费。试问：设备A、B、C每工时各如何收费才最有竞争力？设y1，y2，y3分别为每工时设备A、B、C的收取费用。1.线性规划

2、对偶问题3线性规划原问题例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）150025004Maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤40原问题3x2≤75x1,x2≥0Minf=65y1+40y2+75y3s.t.3y1+2y2≥1500（不少于甲产品的利润

3、）2y1+y2+3y3≥2500对偶问题（不少于乙产品的利润）y1,y2,y3≥01.线性规划对偶问题52、对偶定义对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”1.线性规划对偶问题6一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。1.线性规划对偶问题

4、7(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。1.线性规划对偶问题8非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原

5、规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；1.线性规划对偶问题9（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+…+a1nxn=b1那么，这个等式与下面两个不等式等价1.线性规划对偶问题101.线性规划对偶问题这样，原规划模型可以写成111.线性规划对偶问题此时已转化为对称形式，直接写出对偶规划这里，把y1看作是y1=y1’-y

6、1’’，于是y1没有非负限制，关系（2）的说明完毕。121.线性规划对偶问题例3.1写出下面线性规划的对偶规划模型解先将约束条件变形为“≤”形式131.线性规划对偶问题再根据非对称形式的对应关系，直接写出对偶规划141.线性规划对偶问题153.对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）定理3-1(弱对偶定理）若x,y分别为（LP)和（DP）的可行解，那么cTx≤bTy。推论若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。1.线性规划对偶问题16定理3-2(最优性准

7、则定理)若x,y分别(LP),(DP)的可行解,且cTx=bTy，那么x,y分别为(LP)和(DP)的最优解。定理3-3(主对偶定理)若(LP)和(DP)均可行那么(LP)和(DP)均有最优解,且最优值相等。以上定理、推论对任意形式的相应性规划的对偶均有效1.线性规划对偶问题174.影子价格——是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*分别为（LP）和（DP）的最优解，那么，cTx*=bTy*。根据f=bTy*=b1y1*+b2y2*++bmym*可知f/bi=yi*

8、yi*表示bi变化1个单位对目标f产生的影响，称yi*为bi的影子价格。注意：若B是最优基，y*=(BT)-1cB为影子价格向量。1.线性规划对偶问题18影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某