2线性规划的标准型

1、2021/8/61 第二节第二节 线性规划的标准形式线性规划的标准形式一、一、LPLP问题的标准形式问题的标准形式二、二、化标准形式化标准形式2021/8/62(一一) 代数式代数式MaxZ=C1X1+ C2X2+CnXna11X1 + a12X2 + a1nXn =b=b1 1a21X1 + a22X2 + a2nXn =b=b2 2 am1X1+ am2X2+ amnXn =b=bm mXj j 0(0(j=1,2,n) )其中其中 bi 0 (0 (i=1,2,m) )2021/8/63和式：和式： maxZ=cjxj aijxj=bi （ i=1,2,m） xj 0 （j=1,2,n）

2、j=1nnj=1(二二) 和式和式2021/8/64(三三) 矩阵型矩阵型maxZ=CXAX=bX 0 0 P P1 1 P P2 2 P Pn n a11 a12 a1n其中其中 A= A= a21 a22 a2n am1 am2 amn X1 X= X2 XnC=(C1 C2 Cn ) b1 b= b2 bm2021/8/65(四四) 向量式向量式CXZmax01XbxpnjjjC=(C1 ,C2 , ,Cn )X=(X1 ,X2 , ,Xn )Ta1ja2j amj .Pj =b1b2 bm b=.返回返回2021/8/66二、化标准形式二、化标准形式 1. 约束条件约束条件 3. 变量

3、变量 2. 目标函数目标函数 4. .右端项系数右端项系数2021/8/671. 约束条件约束条件例例1 1maxZ=2X1+ X2+0X3 +0X4+0X5 5x2 15 6x1 + 2x2 24 x1 + x2 5 xi 0+X3 =15 +X4 =24 +X5 = 5 （i=1,2）（i=1,2,3,4,5）松弛变量松弛变量2021/8/68例例2 2maxZ=2X1+ 5X2+6X3 +8X4返回返回 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)- X5 =12 - X6 =14 - X7

4、=8 剩余变量剩余变量 7）+0X5+0X6 +0X72021/8/69njjjXCZ1minnjjjXCZ1max令令Z = -Z2. 目标函数目标函数xoZ-Z2021/8/610minZ=2X1+ 5X2+6X3 +8X4maxZ = -2X1 - 5X2 -6X3 -8X4返回返回2021/8/6113. 变量变量例例3X1+2X2 8 X1 -4X2 14 X2 0 0令令X1 = -X1 -3X1 +2X2 8 -X1 - 4X2 14X1 , X2 0 0X10，2021/8/612例例3X1+2X2 8 X1 -4X2 14 X2 0 0令令X1= X1- X1 3X1 -3

5、X1 +2X2 8 X1 - X1 - 4X2 14X1 , X1 ,X2 0 0X10， X1 0X1无约束无约束，2021/8/613 例例X1+X2 5-6 X1 10X2 0 0-6+6 X1+6 10+6 令令X1 = X1 +6 0 X1 16X1 +X2 11X1 16X1 , X2 0 0返回返回2021/8/614X1+X2 +X3 -9-X1-X2 -X3 92021/8/615例：例：将将 min Z = -X1+2X2 -3X3X1+X2 +X3 7X1 -X2 +X3 2 2X1，X2 0 0，X3无限制无限制化为标准型化为标准型2021/8/616解：解： 令令X3

6、 =X4 - X5 加松弛变量加松弛变量X6 加剩余变量加剩余变量X7 令令Z= -ZmaxZ= X1 -2X2 +3X4 -3X5 X1 +X2 +X4 -X5 +X6 =7X1 -X2 +X4 -X5 - X7 =2X1 , X2 , X4 , , X7 0 02021/8/617将将minZ= 15x1 + 25x2 + 10 x3 50 x1 + 150 x2 + 90 x3 175 100 x2 - 50 x3 -30 70 x1+ 10 x2 200 30 x1 + 80 x2 + 200 x3 100 xi 0 (i =1,2)化为标准型化为标准型练习：练习：2021/8/618将将minZ= x1 + 2x2 + 3x3