管理运筹学复习材料.doc

线性规划标准形式min z = CTXest. AX = bX 0转换为标准形式的方法max Z = C1X1 + C2X2 + min Z = -C1X1 C2X2 - Ai1X1 + Zi2X2 + + AinXn Bi 增加Xn+i 0 Ai1X1 + Ai2X2 + + AinXn + Xn+I = BiXj 无符号限制 令Xj = Xj + Xj(Xj, Xj 0) 并代入原式Xj 0 令Xj = Xj （Xj 0）并代入原式基变量系数必须为单位矩阵检验数为0进基变量单纯形法(线性规划必须为标准形式，n个约束代表n个基变量，通过可行基获得单纯形表)基变量ZX1X2X3X4RHSZ11(Zj-Cj)2000离基变量X301(Yij)1103(Bi)3/1(Bi / Yij)X40010111/1具体步骤如下：（1）通过可行基画出单纯形表，Z行填目标函数系数(注意要把所有变量放左侧，即系数均乘以-1)，基变量行填约束条件系数，RHS值填目标函数值和b的值；（2）确定进基变量，选取Z行（Zj-Cj）中0且最大的列为进基变量；（3）确定离基变量，将RHS列进基变量的列，取最小值的行为离基变量（进基变量列中0的行不参与计算）；若进基变量的列均0，可判断目标函数无界，结束运算。（4）将进基变量的系数(Yij)化为1（行变换），并将进基变量的检验数（Z行）化为0，进基变量所在列的其他行也化为0；（5）检查运算结果，若Z行所有系数0，则得到最优解（如有非基变量检验数=0，则说明有多个最优解），结束运算；否则重复25步骤。对偶问题极小化问题（min）极大化问题(max)变量Xj 0aijwi Cj约束Xj : unraijwi = CjXj 0aijwi Cj约束aijXj biwj 0变量aijXj biwj : unraijXj biwj 0min z = 4x1 + 7x2 + 8x3s.t. -x1 + 3x2 + 2x3 8 2x1 - x2 + 4x3 5x1 0, x2 : unr , x3 0max y = 8w1 + 5w2s.t. -w1 + 2w2 4 3w1 - w2 = 7 2w1 + 4w2 8w1 0, w2 0互补松弛关系Xj Wm+j = 0Wi Xn+i = 0Xn+1 Xn+m X1 Xj XnWm+1 Wm+j Wm+nW1 Wm 对偶单纯形法（当原问题无法直接获得可行基时使用，注意要化为标准形式）（1）通过转换获得原问题不可行但对偶可行的基，如下例原问题引入松弛变量x4，x5约束条件乘-1，此时(0,0,0,-3,-4)原始不可行但对偶可行min z = 2x1+3x2+4x3s.t. x1+2x2+x33 2x1-x2+3x34 x1,x2,x30min z = 2x1+3x2+4x3s.t. x1+2x2+x3 - x4 =3 2x1-x2+3x3 -x5 =4 x1,x2,x3,x4,x50min z = 2x1+3x2+4x3s.t. -x1-2x2-x3 + x4 = -3 -2x1+x2-3x3 +x5 = -4 x1,x2,x3,x4,x50进基变量（2）画出初始单纯形表zx1x2x3x4x5RHS离基变量z1-2(Zj-Cj)-3-4000x40-1(Yij)-2-110-3(Bi)x50-21-301-4-2/-2Zj-Cj / Yij-4/-3迭代步骤如下：（3）若RHS列均0，则为最优解，运算结束；选取RHS列（(Bi）最小的行为离基变量；（4）若离基变量的行系数均0，则无解，运算结束；选取离基变量行0的列，计算Z行离基变量行（Zj-Cj / Yij）的值，取最小值的列为进基变量；（5）将进基变量的系数(Yij)化为1（行变换），并将进基变量的检验数（Z行）化为0，进基变量所在列的其他行也化为0；（6）重复35步骤。敏感性分析-目标函数系数C变化（须先获得最优单纯形表）系数变化值目标函数系数C-21 (1+)-100zX1X2X3X4X5RHS基变量的系数CBz10-3 (-3-)-1-20-12-2X101111060X500311110目的：C变化后（+）全部检验数仍0，计算出的取值范围。记住公式：检验数zj-cj=(CBiYij)-cj (i从1到m)规律：（1）非基变量系数变化只影响本列的检验数，且直接=检验数- （2）基变量的系数变化只影响非基变量的检验数，按公式计算即可敏感性分析-右边常数变化（须先获得最优单纯形表）灰色部分直接就是最优基的逆矩阵B-1，这是因为原始单纯形表中X4，X5和X6为单位矩阵b= B-1bZX1X2X3X4X5X6RHSZ10-40-10-2-17X101-1/401/30-2/31/3X500200116X3002/311/301/313/3目的：b变化后（+），b(RHS列)也会发生变化，需保证b中的值均0记住公式：b= B-1b 把变化后的值代进去b即可对偶问题的经济解释利润最大化(z为总利润)max z = CX (C-单位产品利润，X-生产数)s.t. AX b （aij-单位产品j消耗i资源的数量；bi-资源i的限量；化为标准形式后，引入的松弛变量Xn为对应行剩余的资源）（对偶）资源定价问题（y为总成本）min y = bTW (b-资源限量,W-资源价格)s.t. ATW CT影子价格：最优解中的wi为第i种资源的影子价格，越大代表该资源越紧缺，资源有剩余则影子价格肯定为0。机会成本：ajiwi(i从1到m)代表产品j的机会成本，表示减少一件产品所节省的资源可以增加的利润。只有产品价格定在机会成本之上，才有利可图。机会成本：对偶问题约束条件的左侧值（代入最优解）。运输问题单纯形法（需满足供求平衡，若不平衡，则转为平衡后再求解）供应量（1）通过西北角法或最小元素法求初始可行基运价Cij运输量Xij西北角法：从左上角开始，将运输量取min剩余供应量,剩余需求量，然后进行扣减；当剩余供应量(或需求量)为0时则取下一行(列)循环计算运输量。123416 147531414-14=0(1)2884132672727-8=19(2)19-13=6(3)6-6=0(4)3591066131919-6=13(5)6-6=0(6)2222-14=8(1)8-8=0(2)1313-13=0(3)1212-6=6(4)6-6=0(5)1313-13=0(6)需求量1234最小元素法：取运价最小的路线，运输量取min剩余供应量,剩余需求量，然后进行扣减；然后同样依次按运价倒序选择线路执行相应运算。16 1753131414-13=1（2）28241321272727-12=15(1)15-13=2(3)2-2=0(6)351991061919-19=0(4)2222-19=3(4)3-1=2(5)2-2=0(6)1313-13=0（3）1212-12=0(1)1313-13=0（2）（2）计算运输表的检验数(Zij-Cij)1234闭回路法：从要求检验数的格子出发，通过所有基变量获得一条闭回路，则回路的奇数转角为+，偶数转角为，然后求回路上基的运价加总（Zij），然后减自身运价得检验数，例：Z24-C24=(+3 -6 +8) 7 = -2计算所有非基变量的检验数填入表中。16 175-313142824132127(-2)27351991061922131213对偶变量法：先在表中标出u和v变量，然后对于所有基变量列出以下公式：Cij=ui+vj(简单记忆：该格的行列uv相加等于运价)，可得到多个二元方程，令最后一个vm=0，解方程算出所有u和v的值，例如：u1+v1=C11=6，u2+v1=C21=8，u3+v1=C31=5，u2+v2=C22=4，u2+v3=C23=2，u1+v4=C14=3令v4=0，算得值填进去。然后按照以下公式算出所有非基变量的检验数：Zij-Cij=ui+vj - Cij （简单记忆：该格行列uv相加减该格运价），例如Z24-C24=5+0-7=-2123416 17-55-531314u1=32824132127(-2)27u2=535199（-8）10（-11）6（-4）19u3=222v1=313v2=-112v3=-313v4=0（3）若所有检验数均0，则代表已得到最优解，结束运算；选取检验数0且最大的非基变量进基（下例中选X31进基），然后对该进基变量画闭合回路，选择奇数转角的运输量（Yij）中最小的为离基变量。例如下例中minY33,Y21=min6,8=6，X33离基。123416 147（-5）5（-5）3（-7-9）2735（11