二、线性规划问题的结构特征1.每一个问题都用一组决策变量（x,x,x）表示某一方案；它们取不同的非负值，代表不同的具体方案。2．决策变量受到一些约束条件的限制，这些约束条件可以用一组线性等式或线性不等式来表示。3．都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，目标函数可以是最大化，也可以是最小化。线性规划问题的结构特征·线性规划问题的一般形式：目标函数：Max（Min）Z=cx,+c,x, +.+cnxnai +a2x2 +..-+anx,≤(z,-)ba2r +a2x2+..-+a2nxn≤(2,=)b2约束条件：am+am2x2+...+amx,≤(z,=)bmxj,x2,",x≥0式中c,(j=1,2,",n)称为价值系数；b.(i=1,2,,m）称为技术系数：a,(i=1,2,",m,j=1,2,..",n)称为限定系数（或称右端系数）。11
11
三、线性规划问题的标准型（一）线性规划问题的标准形式（standardformofLP）:目标函数：MaxZ=Cx,+c,x, +...+c,xnaux+ax+*+anx=b约束条件：af+a*+.an*=bau+am2xz+..+amx,=bmx,x,",x,≥0b, ≥0(i-1,2,.,m)三、线性规划问题的标准型·矩阵形式简写形式nMaxZ= CXZ=ZcxjMaxJ-1AX = bs.t.[24, -,(= 1-2 )X≥0s.t.j-1b≥0x, ≥0G =1,2,..,n)b, ≥0(i =1,2,...,m)12
12
三、线性规划问题的标准型（二）标准形式的转化1．目标函数的转换+对于目标函数Minz=cjx,1两边乘（-1)则Max(-Z)=Z(-c,n,)j=1令Z'=-Z即有MaxZ'-Z(-c,)xj-1三、线性规划问题的标准型2.约束条件的转换（1）约束条件是“≤"形式：在不等式的左端加入非负的变量（也称作松弛变量）如：2x+4x≤40则可在不等式的左端加入一个松弛变量x，则该约束条件变为：2x,+4x2+x=40其中xs≥0（2）约束条件是“≥"形式：在不等式的左端减去一个非负的变量（称作剩余变量，也可称松弛变量）如：4x+2x,≥20则可在不等式的左端减去一个剩余变量x4则该约束条件变为：4x,+2xz-x，=20其中x≥013
13
三、线性规划问题的标准型（3）右端项为负值：在方程的两边乘以“一1”以保证右端项为正值如：-3x+x2-x=-20方程两边乘以一1，得3x1 - x2 + xg = 20三、线性规划问题的标准型3.决策变量的转换（1）决策变量x,≤0令x,=-x，其中x≥0将x，带入到原问题使决策变量满足大于等于零的要求（2）决策变量Xk为自由变量令=-，其中≥0≥0因为x与x之间大小关系不确定，故x可以取遍整个实数域14
14
三、线性规划问题的标准型[例3]将下面线性规划问题化为标准形式minZ=20x +25x2+30x3[5x+6x,+8x≥153x +4x, +6x,≤20si.-3x +5x, - 7xg = -12x≥0,x≤0三、线性规划问题的标准型解：令Z'=-Z,x2=-x其中x2 ≥0=-其中≥0，≥0同时引入剩余变量x4，松弛变量xs则带入方程后得：maxZ'=-20x, +25x,-30x +30x5x -6x +8x -8x, -x =153x - 4x2 +6x, -6x +x, = 20s.t.33x +5x, +7x, -7x, =12[,2,xg,g,x,x≥01
15