重庆工商大学：《管理运筹学》课程教学课件（讲稿）第一章 线性规划及单纯型法

山重二间大学一用矩阵表示z = CXnaxC一价值向量AX = bb一资源向量X≥0X一决策变量向量(000==(P, P2..., P)mmn0

– 用矩阵表示                           0 . 0 0 ( , ,., ) 0 . . . 0 1 2 1 11 1 n m mn n P P P a a a a A X 0 max    X AX b Z CX C—价值向量 b—资源向量 X—决策变量向量

山重二间大学一般线性规划问题的标准形化等价于maxz'=- CXmin Z=CX "\"约束：加入非负松驰变量例:Z = 2x, +3x2maxX +2x2 ≤ 84x1≤164x ≤ 12X≥ 0, xz≥ 0

• min Z=CX 等价于 max Z’ = - CX • “” 约束：加入非负松驰变量 一般线性规划问题的标准形化 例：                0 0 4 12 4 16 2 8 max 2 3 1 2 2 1 1 2 1 2 x x x x x x Z x x

亚重庭二商大学一般线性规划问题的标准形化'=-CXmin Z=CX 等价于 max Z'""约束：加入非负松驰变量例:Z =2x, +3x, +0x3 +0x4 +0xsmaxX, + 2x2 + X = 84X1+ x4 = 164X2+ Xs = 12X1,X2,X3,X4,X, ≥ 0

• min Z=CX 等价于 max Z’ = - CX • “” 约束：加入非负松驰变量 一般线性规划问题的标准形化 例：                     , , , , 0 4 12 4 16 2 8 max 2 3 0 0 0 1 2 3 4 5 2 5 1 4 1 2 3 1 2 3 4 5 x x x x x x x x x x x x Z x x x x x

重庭二间大学·可正可负（即无约束）这时可令='-X"；，X"≥0·变量x;≤0，令x,'=-x;即可"N去非负剩余变量+X6Max例:minz = -xi+2x2-x,一Xx1+2+ ≤- X2 + ≥ 2x1S.t- 3x1 + X2 +2x3 = 5X,x≥0,,无约束=x4-x

• “” 约束： 减去非负剩余变量；                       1 2 3无约束 1 2 3 1 2 3 1 2 3 1 2 3 , 0 , 3 2 5 2 7 . min 2 3 x x x x x x x x x x x x s t z x x x                       1 2 3无约束 1 2 3 1 2 3 1 2 3 1 2 3 , 0 , 3 2 5 2 7 . min 2 3 x x x x x x x x x x x x s t z x x x Max  x6 x7 例： 3 4 5 x x x 3 4 5 x x x xk • 可正可负（即无约束）； 这时可令 xk= xk ’− xk ’’ ; xk ’, xk ’’  0 • 变量 xj 0，令 xj ’ =−xj 即可

山重展二商大学解：标准形为z =x -2x +3(x4 -x)+0x +0xmax=7X+x + (x4 -x)+x-x =2-x + (x -x)Xis.t=5-3x +x +2(x -xg)X,,X4,Xs,X,X ≥0

解 ：标准形为                              , , , , , 0 3 2( ) 5 ( ) 2 ( ) 7 . max 2 3( ) 0 0 1 2 4 5 6 7 1 2 4 5 1 2 4 5 7 1 2 4 5 6 1 2 4 5 6 7 x x x x x x x x x x x x x x x x x x x x st z x x x x x x