重庆交通大学（重庆交通学院）：《运筹学》课程教学资源（PPT课件讲稿）对偶理论与灵敏度分析

简写形式为 maXx=∑C;x C..x. St i=1,2·m2,j=12,…,n x.20

简写形式为： i m j n j x i b n j j x ij a S t n j j x j z c 1,2, ; 1,2, , 0 . 1 1 max =  =    = =  = =         

向量和矩阵表示 ◆maxZ=CX ∑P:x=b ≥O,j=1,2,…,H ◆X=:2P1=:2/b ◆其中,C=(c1C2,Cn) ◆向量P对应的决策变量是X

向量和矩阵表示 max z=CX X= 其中，C=(c1 ,c2 ,…,cn ) 向量Pj对应的决策变量是xj .           =  = = j n j x b n j j x j P 0, 1,2, , 1                        n x x x  2 1                                               = = m b b b b mj a j a j a j P   2 1 , 2 1

矩阵形式为: ◆maxz=CX ◆stAX=B X≥0 112 nz 0

矩阵形式为： max z=CX s.t       = X 0 AX B , ; 2 , 1 1 2 21 22 2 11 12 1                           = = m P P P mn a m a m a n a a a n a a a A                           = 0 0 0 0 

◆称A为约束条件的m×n维系数矩阵, 般m0; ◇b为资源向量 ◆C为价值向量; ◆X为决策变量向量 ◆实际遇到的各种线性规划问题的数学 模型都应变换为标准形式后求解。 ◆以下讨论如何化标准型的问题:

称A为约束条件的m×n维系数矩阵， 一般m0; b为资源向量； C为价值向量； X为决策变量向量。 实际遇到的各种线性规划问题的数学 模型都应变换为标准形式后求解。 以下讨论如何化标准型的问题：

◆若要求目标函数实现最小 十化,即minz=CX,这时只 需将目标函数最小化变换 为最大化,即令z=-于是 得到maXz=CX这就和标 准型的目标函数的形式一 致了

若要求目标函数实现最小 化， 即min z=CX.这时只 需将目标函数最小化变换 为最大化，即令z`=-z,于是 得到max z`=-CX,这就和标 准型的目标函数的形式一 致了

(2)约束方程为不等式。这 里有两种情况:一种是约束方程 为‘≤’不等式,则可在‘≤’不 等式的左边加上非负松弛变量, 把原‘≤’不等式变为等式;另 种是约東方程“≥’不等式,则可 在‘≥’不等式的左端减去一个非 负剩余变量(也可称松弛变量) 把不等式约束条件变为等式约束 条件

（2） 约束方程为不等式。这 里有两种情况：一种是约束方程 为‘≤’不等式，则可在‘≤’不 等式的左边加上非负松弛变量， 把原‘≤’不等式变为等式；另一 种是约束方程‘≥’不等式，则可 在‘≥’不等式的左端减去一个非 负剩余变量（也可称松弛变量）， 把不等式约束条件变为等式约束 条件

◆(3)若存在取值无(符号) 约束的变量x,可 XI=X k ,其中x,X≥0

(3)若存在取值无（符号） 约束的变量xk ,可令xk=xk `- xk ``,其中xk ` ，xk ``≥0

下面举例说明 例3将下面的数学模型化为标准型 Max z=2x,+3x X1+2X≤8 4×1≤16 4×2≤12 X1,X2≥0

下面举例说明 例3 将下面的数学模型化为标准型。 Max z=2x1+3x2 x1+2x2≤8 4x1≤16 4x2≤12 x1，x2≥0

解 将各不等式加上松弛变量即得 MaXz=2×1+3X2 X1+2X2+X2=8 4x 1+x4=16 4×2+×512 1×2×x3X4x×5=0

解 将各不等式加上松弛变量即得 Max z=2x1+3x2 x1+2x2+x3=8 4x1+x4=16 4x2+x5 12 x1 ,x2 ,x3 ,x4, x5≥0

例3将下述线性规划问题化为标准型 min z=-x+2x-3x 3 X1+X2+X2≤7 X1-X2+X2≥2 -3x1+X2+2X2=5 X1,X2≥0×x为无约束

例3 将下述线性规划问题化为标准型 min z=-x1+2x2 -3x3 x1+x2+x3≤7 x1 -x2+x3≥2 -3x1+x2+2x3=5 x1，x2≥0,x3为无约束