《22线性规划的标准形.ppt》由会员分享，可在线阅读，更多相关《22线性规划的标准形.ppt（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一一、一一般般型型一、一般型一、一般型a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n=b=b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n=b=b2 2 （，）a am1m1x x1 1+a+am2m2x x2 2+a amnmnx xn n =b bm mx xj j 0 0 (j=1n j=1n 全部全部)2.2 2.2 线性规划的标准型线性规划的标准型S=S=c c1 1x x1 1+c+c2 2x x2 2+c cn nx xn n=c cj jx xj j求求 x xj j （j=1nj=1n）使使max
2、maxminmin满足满足：1为讨论方便起见，为讨论方便起见，规定规定：求目标函数值求目标函数值 S S最小最小 约束约束条件为等式条件为等式 全部全部变量非负变量非负 常数项常数项 b bi i 非负非负（令：（令：）（xj 松弛变量松弛变量）（max 时，令：时，令：）（等式两边乘负号）等式两边乘负号）2二、标准型二、标准型a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n=b=b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n=b b2 2 a am1m1x x1 1+a+am2m2x x2 2+a amnmnx
3、xn n =b bm mx xj j 0 0 (j=1n j=1n)minminS S=c c1 1x x1 1+c+c2 2x x2 2+c cn nx xn n3例例1 1、将下列、将下列LPLP问题化为标准型问题化为标准型(1)(1)x x3 3无非负制约无非负制约 令：令：(2(2)化化(3)(3)化约束条件为等式化约束条件为等式 引进变量引进变量 x x4 4 x x5 54三、三、标准型的简单表示法标准型的简单表示法其中：其中：1 1、矩阵表示、矩阵表示：2 2、向量表示、向量表示：三、矩阵、向量表示5写出下面线性规划问题的矩阵表示和向量表示写出下面线性规划问题的矩阵表示和向量表示
4、67例：将例：将 min Z=-Xmin Z=-X1 1+2X+2X2 2-3X-3X3 3X X1 1+X+X2 2+X+X3 3 7 7X X1 1-X-X2 2+X+X3 3 2 2 ,X ,X3 3无限制无限制化为标准型化为标准型练习练习8解：解：令令X X3 3=X=X4 4-X X5 5 加松弛变量加松弛变量X X6 6 X X7 7 （剩余变量）令令Z=-ZZ=-ZmaxZmaxZ=X=X1 1-2X-2X2 2+3X+3X4 4-3X-3X5 5 X X1 1+X+X2 2+X+X4 4-X-X5 5+X+X6 6=7=7X X1 1-X-X2 2+X+X4 4-X-X5 5-X-X7 7=2=2X X1 1,X,X2 2,X,X4 4,X,X7 7 0 09