北邮运筹学ch1-3 线性规划的标准型.ppt

运筹学北京邮电大学 Linear Programming Linear Programming § 线性规划的标准型 Normalized form of LP 2017-3-26 Page 1 of 9 在用单纯法求解线性规划问题时,为了讨论问题方便,需将线性规划模型化为统一的标准形式。线性规划的标准型线性规划问题的标准型为 (有时求最小值) ; xj为非负。 bi都大于或等于零; 运筹学北京邮电大学 Linear Programming Linear Programming § 线性规划的标准型 Normalized form of LP 2017-3-26 Page 2 of 9 ?????????????????????????m ib njx bxaxaxa bxaxaxa bxaxaxai j m n mn m m nn nn,,2,1,0 ,,2,1,0 2211 2 2 2 22 21 1 1 2 12 1 11?????????????????? max( 或 min)Z=c1x1+c2x2+ …+cnxn 运筹学北京邮电大学 Linear Programming Linear Programming § 线性规划的标准型 Normalized form of LP 2017-3-26 Page 3 of 9 ??? nj jjxcZ 1 maxm injx bxa j nj ij ij,,2,1,,2,1,0 1?????????????或用矩阵形式:??????0 max X b AX CX Z 或写成下列形式: 运筹学北京邮电大学 Linear Programming Linear Programming § 线性规划的标准型 Normalized form of LP 2017-3-26 Page 4 of 9 ),,,( 21 2 12 1 21 2 22 21 1 12 11 n m n mn mm n b b bbx x xXaaa aaa aaaA??????????= ; ; ;??????????????????????????????????????? 1 2 , , , ) Tn X x x x L =( ??????0 max X b AX CX Z其中:通常 X记为: 。称A为约束方程的系数矩阵, m是约束方程的个数, n是决策变量的个数, 一般情况 m≤n,且 r(A)=m。运筹学北京邮电大学 Linear Programming Linear Programming § 线性规划的标准型 Normalized form of LP 2017-3-26 Page 5 of 9 【例 】将下列线性规划化为标准型 3213 minxxxZ????????????????????????无符号要求、、 321 321 321 32100 )3(523 )2(3 )1(82xxx xxx xxx xxx【解】(1)因为 x3无符号要求,即 x3取正值也可取负值,标准型中要求变量非负,所以令 0,, ''3 '3 ''3 '33???xx