IE10_OR06 CH2 线性规划的对偶理论与灵敏度分析1.ppt

1、第6讲内容，第1章软件应用补充，总结和练习讲解CH2线性规划的对偶理论和灵敏度分析2.1线性规划的对偶问题2.2对偶问题的基本性质2.3影子价格2.4对偶单纯形法2.5灵敏度分析2.6参数线性规划和软件应用补充。用软件解决线性规划问题(演示)Lindo Excel Solver北方理工学院软件，第1章线性规划和单纯形法(摘要)，1。线性规划的概念(1)线性规划模型的组成决策变量目标函数：最大(最小)Z(决策变量的线性函数)约束：S.T .(满足具有决策变量的线性等式或不等式)，(2)一般形式：max=C1 x1c 2 x2 cnxn s . t . a 11x 1 a12x 2 a1n xn=

2、B1 a21x 1 a22x 2 a2n xn=B2 am1x 1 m22 mnxn=bmxj 0；j=1，2，n bi0I=1，2，m，(3)标准形式，线性规划的标准形式具有以下四个特征：目标最大化；约束是线性方程；决策变量不是负的；右端项不是负数。(4)剩余变量、松弛变量及其含义；2)线性规划解的概念；(1)概念：凸集、可行解、可行域、最优解、最优值、基、基本变量、基本解、基本可行解、可行基和最优基。(2)可行域、基本解、基本可行解和最优基之间的关系。图解法：(1)建立直角坐标系(2)说明约束条件和寻找可行解(3)说明表示目标函数的直线和目标函数的增加(或减少)方向(4)寻找最优解(4)单

3、纯形法(1)理论基础定理如果LP问题可行域存在，那么可行域就是凸集定理。线性规划问题的基本可行解与可行域的顶点之间存在一一对应的定理。如果线性规划问题有一个最优解，那么必须有一个基本可行解，即最优解。(2)单纯形法计算步骤，线性规划求解流程图，(5)大M法和两阶段法，(1)目标函数中人工变量的系数由大M法确定：如果目标函数为maxZ，则系数为-M；否则，就是m计算方法：单纯形法，(2)两阶段法，第一阶段：求解一个目标函数只包含人工变量且最小化的线性规划问题，其最优表有两种情况：如果目标函数的最优值为0，人工变量将被去掉，第二阶段：如果目标函数的最优值不为0，原问题没有可行解， 第二阶段：去除第

4、一阶段的人工变量，将第一阶段得到的最优解作为初始基本可行解，用单纯形法继续迭代，直到得到原问题的最优解。 练习1.7 (2) (4)，2.1线性规划的对偶问题。首先，提出了问题。一个工厂可以生产两种产品，需要消耗三种资源：煤、电和油。相关数据如下：尝试制定一个生产计划，使总收入最大化。此时，另一家制造商提出购买其所有的煤炭、电力和石油资源，并希望尽可能少花钱。尝试为买家建立线性规划模型。例2称为例1的对偶问题，表示为(d)，例1称为例2的原问题，表示为(p)。例2称为例1的对偶问题，表示为(d)，例1称为例2的原问题，表示为(p)。在步骤1中发现的低压最佳目标函数值1) 428.0000可变值

5、降低成本X1 20.000000 0.000000 X2 24.000000 0.000000行松弛或盈余双重价格2)84.0000000 0.0000003)0.000000 1.360000 4)0.0000000.5200000迭代次数=1其次，对称形式对偶问题的一般形式，(P)、(D)，是最常见的对偶模型，称之为对称对偶模型。它们之间有一个非常对称的对应关系：原始问题(p)对偶问题(d)目标最大类型目标最小类型有N个变量(非负)，N个约束(大于或等于)，m个约束(小于或等于)和m个变量(非负)价格系数资源向量价格系数技术系数矩阵技术系数矩阵转置，对称形式：相互对偶(LP)最大z=CT

6、x (DP)最小f=Bt y s . t . ax b . t . at y CT x 0y 0 max- min-，min，b，a非对称形式下的原-对偶问题之间的关系，参见P52表2-2，总结对称形式和非对称形式之间的对偶，原问题和对偶问题之间的关系如下表所示，例3:写出以下线性规划的对偶规划模型，例4:写出以下线性规划的对偶规划模型，然后根据非对称形式的对应关系直接写出对偶规划。首先，将约束条件转化为“形式”，2.2对偶问题的基本性质，1。单纯形法的矩阵描述，最大值=CX S.T.Ax=Bx0A=B，N，C=(CB，CN)，X=，则有：最大值=CBXBCNXN X . t . BXBNXN

7、=XN0XB=B-1 B- 1N xN=CB(B-1 B-1N xN)CNXN=CBB-1 B(CN-CBB-1N)XN，xbxn，单纯形表zxbxn0i b-1n b-1b10cn对偶问题的基本性质，2。弱对偶定理对偶问题(min)的任何可行解Y0的目标函数值总是不小于原问题(max)的任何可行解X0的目标函数值，弱对偶定理推导出max问题的任何可行解的目标函数值是对偶min问题的目标函数值的下限。最小问题任何可行解的目标函数值是其对偶最大问题目标函数值的上限。如果原最大(最小)问题是无界的，那么它的对偶最小(最大)问题就没有可行解。如果原始的max(min)问题没有可行解，那么原始问题是无

8、界的。如果原问题的可行解x0的目标函数值等于对偶问题的可行解y0的目标函数值，那么X0和Y0分别是相应问题的最优解。从弱对偶定理推出1，证明结论是明显的。也就是说，CX0=Y0b CX，Y0b=CX0 Yb。证书已完成。4主对偶定理如果原问题和对偶问题都有可行解，它们都有最优解，并且它们的最优解的目标函数值相等。对偶定理如果(p)有一个最优解，(d)也有一个具有相同最优值的最优解。证明：把松弛变量Xs加到(p)上，并把它变成，让它的最佳基是b，最后的表是，它的测试数是，问题：(1)从性质5，我们可以知道对偶问题的最佳解的表达式是Y*=？(2)有必要为Y*重新求解(d)吗？CBB-1，不需要。它

9、可以从原问题(p)的单纯形最终表中得到。请指出其对偶问题的最优解及其价值。6。互补松弛(弹性定理):如果x分别是问题(p)和(d)的可行解，那么当且仅当XS=0，YSX=0(即如果AIX I=0aix=bi0pj=cj0pjc=XJ=0)，则x是最优解，为了解决它，写出它的对偶问题，min，并把它代入对偶问题的约束，得到第二、第三和第四个约束是严格不等式，第一和第五个约束是严格等式，它们是通过互补松弛得到的；同样，因为原始问题的两个约束应该相等，所以存在最大值，它是在求解之后获得的；因此，原问题的最优解是，7。原问题的单纯形表的校验码行对应于其对偶问题的一个基本解。对应关系见表：XB XN xs0cn-CB-1n-CB-1YS1YS2-y，YS1为原问题中基本变量XB对应的残差变量，YS2为原问题中非基本变量XN对应的残差变量，设B为原问题之一。然后a=(b，n)max=cbx bcnxnbxnxs=bxb，xn，xs0。相应地，对偶问题可以表示为min=yby-ys1=cbyn-YS2=CNY，YS1，ys20，让Y=CBB-1