资源描述：
《管理运筹学复习材料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、线性规划标准形式minz=CTXest.AX=bX≥0转换为标准形式的方法maxZ=C1X1+C2X2+…→minZ’=-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个基变量，通过可行基获得单纯形表)基变量Z
2、X1X2X3X4RHSZ11(Zj-Cj)2000离基变量X301(Yij)1103(Bi)3/1(Bi/Yij)X400[1]0111/1具体步骤如下：（1）通过可行基画出单纯形表，Z行填目标函数系数(注意要把所有变量放左侧，即系数均乘以-1)，基变量行填约束条件系数，RHS值填目标函数值和b的值；（2）确定进基变量，选取Z行（Zj-Cj）中>0且最大的列为进基变量；（3）确定离基变量，将RHS列÷进基变量的列，取最小值的行为离基变量（进基变量列中≦0的行不参与计算）；若进基变量的列均≦0，可判断目标函数无界
3、，结束运算。（4）将进基变量的系数(Yij)化为1（行变换），并将进基变量的检验数（Z行）化为0，进基变量所在列的其他行也化为0；（5）检查运算结果，若Z行所有系数≦0，则得到最优解（如有非基变量检验数=0，则说明有多个最优解），结束运算；否则重复2－5步骤。对偶问题极小化问题（min）极大化问题(max)变量Xj≥0<>∑aijwi≤Cj约束Xj:unr<>∑aijwi=CjXj≤0<>∑aijwi≥Cj约束∑aijXj≥bi<>wj≥0变量∑aijXj＝bi<>wj:unr∑aijXj≤bi<>wj≤0mi
4、nz=4x1+7x2+8x3s.t.-x1+3x2+2x3≥82x1-x2+4x3≤5x1≥0,x2:unr,x3≤0maxy=8w1+5w2s.t.-w1+2w2≤43w1-w2=72w1+4w2≥8w1≥0,w2≤0互补松弛关系XjWm+j=0WiXn+i=0Xn+1Xn+mX1XjXnWm+1Wm+jWm+nW1Wm对偶单纯形法（当原问题无法直接获得可行基时使用，注意要化为标准形式）（1）通过转换获得原问题不可行但对偶可行的基，如下例原问题引入松弛变量x4，x5约束条件乘-1，此时(0,0,0,-3,-4
5、)原始不可行但对偶可行minz=2x1+3x2+4x3s.t.x1+2x2+x3≥32x1-x2+3x3≥4x1,x2,x3≥0minz=2x1+3x2+4x3s.t.x1+2x2+x3-x4=32x1-x2+3x3-x5=4x1,x2,x3,x4,x5≥0minz=2x1+3x2+4x3s.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5≥0进基变量（2）画出初始单纯形表zx1x2x3x4x5RHS离基变量z1-2(Zj-Cj)-3-4000x40-1(Yij
6、)-2-110-3(Bi)x50[-2]1-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）重复3－5步骤。敏感性分析-目标函数系数C变化（须先
7、获得最优单纯形表）系数变化值目标函数系数C-21(1+＆)-100zX1X2X3X4X5RHS基变量的系数CBz10-3(-3-＆)-1-20-12-2X101111060X500311110目的：C变化后（+＆）全部检验数仍≤0，计算出＆的取值范围。记住公式：检验数zj-cj=(∑CBiYij)-cj(i从1到m)规律：（1）非基变量系数变化只影响本列的检验数，且直接=检验数-＆（2）基变量的系数变化只影响非基变量的检验数，按公式计算即可敏感性分析-右边常数变化（须先获得最优单纯形表）灰色部分直接就是最优基的
8、逆矩阵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即可对偶问题的经济解释利润最大化(
