运筹学期末复习.ppt

*第三章

线性规划对偶与灵敏度分析对偶规划的形式有对称形式和非对称形式。对称形式的对偶规划之间具有下面的对应关系：若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”*非对称形式的对偶规划:对非对称形式，可以按照下面的对应关系直接给出其对偶规划(1)将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面(2)、(3)中的方法处理；(2)若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；(3)若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。1、例子P67

写出下面线性规划的对偶规划模型解先将约束条件变形为“≤”形式*根据非对称形式的对应关系，直接写出对偶规划2、写出下面线性规划的对偶规划模型*灵敏度分析**理解最优单纯形表的含义考虑问题Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0其中：**设最优单纯形表灵敏度分析**ci单个变化保持最优解不变的允许范围线性规划增加一个变量bj单个变化对解的可行性的影响线性规划增加一个约束若ck是非基变量的系数：设ck变化为ck+?ck?k’=?k+?ck只要?k’≤0,即?ck≤-?k，则最优解不变；否则，将最优单纯形表中的检验数?k用?k’取代，继续单纯形法的表格计算。例Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-32x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0例：最优单纯形表从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。2、若cl是基变量的系数**设cl变化为cl+?cl，那么?j’=?j-?clalj’只要对所有非基变量?j’≤0，即?j≤?clalj，则最优解不变；否则，将最优单纯形表中的检验数?j用?j’取代，继续单纯形法的表格计算。Maxz=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥0例b增加变量增加约束下表为最优单纯形表,考虑基变量系数c2发生变化由σj=cj-(c1×a1j+c5×a5j+(c2+Δc2)×a2j)j=3,4可得到-3≤Δc2≤1时，原最优解不变。3、右端常数的变化**设分量br变化为