1.3线性规划问题的标准型式 13线性规划问题的标准型式 M 目标函数 maxZ=C1x1+C2x+…+C, 1x+a12x2+…+a1nxn=b a C21X1+ 2x+…+a2nX 22 -b 约束条件: ·· ax,+ax +.+.x= mn n 13*2 ≥0
1.3 线性规划问题的标准型式 + + + = + + + = + + + = = + + + 0 a max z c 1 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 1 n m m m n n n n n n n n n x ,x , ,x a x a x a x b a x a x a x b x a x a x b x c x c x M : 约束条件： 目标函数： 1.3 线性规划问题的标准型式
1.3线性规划问题的标准型式 线性规划问题的几种表示形式 用向量形式表示的标准形式线性规划 M1:目标函数:maxz=CX b 约束条件: j=1 x≥0,j=1,2,,n C=(c1,c2 X1 X P b j=1,2, x b
1.3 线性规划问题的标准型式 ( ) ; j , , n b b b ;b a a a ;P x x x X C c ,c , ,c ; x , j , , ,n P x b M : max z CX m j m j j j n n j n j j j '' 1 2 0 1 2 2 1 2 1 2 1 1 2 1 1 = = = = = = = = 约束条件： = 目标函数： 用向量形式表示的标准形式线性规划 线性规划问题的几种表示形式
1.3线性规划问题的标准型式 用矩阵形式表示的标准形式线性规划 M1:目标函数:maxz=CX 约束条件:4x=b X≥0 系数矩阵:A= 零向量0=:资源向量:b 决策变量向量:X=(x1,x2…,x,)
1.3 线性规划问题的标准型式 用矩阵形式表示的标准形式线性规划 ( ) ( ) T n n m m n n '' X x ,x , ,x P ,P , P ; a a a a A X AX b M : max z C X 1 2 m 1 1 2 1 1 1 1 1 b b b 0 0 0 0 = = = = = = = 决策变量向量： 零向量： ；资源向量： 系数矩阵： 约束条件： 目标函数：
1.3线性规划问题的标准型式 如何将一般线性规划转化为标准形式的线性规划 (1)若要求目标函数实现最小化,即minz=CX,则只需将目标函数最小 化变换求目标函数最大化,即令z-,于是得到maxz=-CX (2)约束条件为不等式。分两种情况讨论: ●若约束条件为“<”型不等式,则可在不等式左端加入非负松弛变 把原“<”型不等式变为等式约束 ●若约束条件为“”型不等式,则可在不等式左端减去一个非负剩 余变量(也称松弛变量),把不等式约束条件变为等式约束。 (3)若存在取值无约束的变量x可令 xk=xk一xk x,x4≥0
1.3 线性规划问题的标准型式 ' " k k k x = x − x (1) 若要求目标函数实现最小化，即min z =CX，则只需将目标函数最小 化变换求目标函数最大化，即令z′= −z，于是得到max z′= −CX。 (2) 约束条件为不等式。分两种情况讨论： ⚫若约束条件为“≤”型不等式，则可在不等式左端加入非负松弛变 量，把原“≤”型不等式变为等式约束； ⚫若约束条件为“≥”型不等式，则可在不等式左端减去一个非负剩 余变量(也称松弛变量)，把不等式约束条件变为等式约束。 (3) 若存在取值无约束的变量xk ,可令 , 0 ' " xk xk 如何将一般线性规划转化为标准形式的线性规划
1.3线性规划问题的标准型式 例3将例1的数学模型化为标准形式的线性规划。 例1的数学模型在加入了松驰变量后变为 maxz=2x,+3x2= max ==2x,+3x2+x3+x4+x5 x1+2x<8 x1+2x2+x3 =8 4x <16 4x +x4=16 4x<12 4. +x5=12 x1,x,≥0 1,2,43,4 x≥0
1.3 线性规划问题的标准型式 例3 将例1的数学模型化为标准形式的线性规划。 例1的数学模型在加入了松驰变量后变为 + = + = + + = + = + = + + + + 0 4 12 4 16 2 8 0 4 12 4 16 2 8 2 3 2 3 1 2 3 4 2 5 1 4 1 2 3 1 2 2 1 1 2 1 2 1 2 3 4 5 x ,x ,x ,x ,x x x x x x x x x ,x x x x x max z x x max z x x x x x