第2章线性规划

1、i iiiii每周可使用量每周可使用量a a（千克）（千克）1 12 25 5b b（吨）（吨）2 21 14 4c c（百工时）（百工时）4 43 39 9单位产品利润单位产品利润（万元）（万元）3 32 2问：该公司每周应生产产品问：该公司每周应生产产品i i与产品与产品iiii各多少单位，各多少单位，才能使每周的获利达到最大？才能使每周的获利达到最大？1、线性规划数学模型例例1 1、 穗羊公司例子穗羊公司例子（1 1）提出、分析问题）提出、分析问题1、线性规划数学模型 x x1 1+2x+2x2 2 55 2x 2x1 1+ x+ x2 2 44 4x 4x1 1+3x+3x2 2 99

2、 x x1 1 ,x,x2 2 0 0 （2 2）根据已知条件建立数学模型）根据已知条件建立数学模型 确定变量：确定变量：需要做哪些决策需要做哪些决策设：每周生产产品设：每周生产产品xx1 1件，产品件，产品xx2 2件，总利润件，总利润z z元元max z=3xmax z=3x1 1+2x+2x2 2stst. .目标函数目标函数约束条件约束条件1、线性规划数学模型、线性规划数学模型资源资源单位活动对资源的使用量单位活动对资源的使用量资源可资源可利用量利用量b1b2bna1a11a12a1na1a2a21a22a2na2 amam1am2amnam对对z的贡献的贡献c1c2cn生产计划问题（

3、产品组合问题）生产计划问题（产品组合问题）1、线性规划数学模型、线性规划数学模型max z= cmax z= c1 1x x1 1+c+c2 2x x2 2+ + +c cn nx xn n a a1111x x1 1+a+a1212x x2 2+ +a+a1n1nx xn na a1 1 a a2121x x1 1+a+a2222x x2 2+ +a+a2n2nx xn na a2 2 a am1m1x x1 1+a+am2m2x x2 2+ + +a amnmnx xn na am m x x1 1,x,x2 2, , ,x xn n 00st生产计划问题的数学模型：生产计划问题的数学模型

4、：设设xj（j=1,2, ,n）代表第）代表第j种产品的生产数量种产品的生产数量例例2 2 设有一批规格为设有一批规格为1010米长的圆钢筋，将它截成分米长的圆钢筋，将它截成分别为别为3 3米，米，4 4米长的预制构件的短钢筋各米长的预制构件的短钢筋各100100根，问怎根，问怎样截取最省料？样截取最省料？ 因为，因为，1010米长的钢筋截为米长的钢筋截为3 3米或米或4 4米长，共有三种截米长，共有三种截法：法：截法截法：3 3 3 1 3 3 3 1 米米截法截法：3 3 4 0 3 3 4 0 米米截法截法：4 4 0 2 4 4 0 2 米米设：按截法设：按截法，各截取各截取1010米

5、长的钢筋分别为米长的钢筋分别为x x1 1, x, x2 2, x, x3 3根，钢筋总用量为根，钢筋总用量为w w1、线性规划数学模型、线性规划数学模型0,10021003.min3213221321xxxxxxxtsxxxw例例2 2 中的问题常称为中的问题常称为下料问题下料问题1、线性规划数学模型、线性规划数学模型数学模型：数学模型： 下料问题的数学模型下料问题的数学模型：1、线性规划数学模型、线性规划数学模型min w = cmin w = c1 1x x1 1+c+c2 2x x2 2+ + +c cn nx xn n a a1111x x1 1+a+a1212x x2 2+ +a+

6、a1n1nx xn n a a1 1 a a2121x x1 1+a+a2222x x2 2+ +a+a2n2nx xn n a a2 2 a am1m1x x1 1+a+am2m2x x2 2+ + +a amnmnx xn n a am m x x1 1,x,x2 2, ,x,xn n00st（2 2）线性规划模型必须满足如下两个要求：）线性规划模型必须满足如下两个要求：目标函数必须是决策变量的线性函数；目标函数必须是决策变量的线性函数；约束条件必须是含决策变量的线性等式或不约束条件必须是含决策变量的线性等式或不等式。等式。1、线性规划数学模型、线性规划数学模型（1）线性规划数学模型的三个

7、要素：）线性规划数学模型的三个要素：决策变量、目标函数、约束条件决策变量、目标函数、约束条件maxz = 3x1+2x2 x1 +2x25 2x1+ x24 4x1+3x29x1 0, x20目标函数等值线目标函数等值线最优解最优解0 x1x2st.可行域可行域x1+2x2=52x1+x2=44x1 +3x2=912x,231x21623*21xxz可行解：可行解：将满足线性规划问题的所有约束条件的变将满足线性规划问题的所有约束条件的变量量x x1 1和和x x2 2的一组取值称为线性规划问题的一个可行解。的一组取值称为线性规划问题的一个可行解。通常用通常用x x表示。表示。可行域：可行域：可

8、行解的集合称为可行域。可行解的集合称为可行域。最优解：最优解：求解线性规划问题，就是要求使得目标函求解线性规划问题，就是要求使得目标函数取最优值（对例数取最优值（对例1 1，就是取最大值）的可行解，这，就是取最大值）的可行解，这样的可行解就称为线性规划问题的最优解。样的可行解就称为线性规划问题的最优解。 通常用通常用x x* *表示。表示。最优值：最优值：通常用通常用z z* *表示表示0 x1x22x1+x2=44x1 +3x2=9x1+2x2=5l 有唯一的最优解有唯一的最优解l 有无穷多最优解有无穷多最优解（将目标函数改为将目标函数改为z=4xz=4x1 1+3x+3x2 2）0,934

9、425234max2121212121xxxxxxxxs.t.xxzl 无界解无界解 指线性规划问题有可行解，但是在可行域，目指线性规划问题有可行解，但是在可行域，目标函数值是无界的，因而达不到有限最优值。因此标函数值是无界的，因而达不到有限最优值。因此线性规划问题不存在最优解。线性规划问题不存在最优解。0,1212332max21212121xxxxxxxxzx1x2o-3x1+2x2=1x1-2x2=10,22232422max2121212121xxxxxxxxxxzl 无可行解无可行解 指找不到一组变量能满足线性规划的所有约束指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线

10、性规划问题不存在可行解，条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。或者说可行域是空集。x1x2o2x1-3x2=2-x1+2x2=42x1+x2=2定理定理2.1 2.1 线性规划问题的可行域如果不是空线性规划问题的可行域如果不是空集，就一定是凸集。集，就一定是凸集。凸集凸集非凸集非凸集x2x1x1x2x2x1x2x1x1x2x1x2凸集凸集顶点线性规划的最优解若存在，就一定在其可线性规划的最优解若存在，就一定在其可行域的顶点上行域的顶点上图解法求解线性规划问题，指出问题是哪一图解法求解线性规划问题，指出问题是哪一类解。类解。0,42266432min21212121xx

11、xxxxxxz一般形式：一般形式：或无约束，或或，或或，或或或0)(,.,)()()(. .min)max(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz), 1(0)(), 1(),(. .max(min)11njxmibxatsxczjnjijijnjjj或无约束其中：其中：cj价值系数；价值系数； bi限定系数；限定系数； aij工艺系数、技术系数工艺系数、技术系数线性规划数学模型的一般形式的其他表示方式：线性规划数学模型的一般形式的其他表示方式：（1 1）用和号）用和号“ ”“ ”表示：表

12、示：（2 2）用向量表示：）用向量表示： 或无约束，或或或0)()(.min)max(1xbpcxnjjjxtszmmjjjjnnbbbaaacccxxx21212121,bpcx其中其中（3）用矩阵表示：）用矩阵表示：或无约束0)(),(. .max(min)xbaxtscxzn21xxxxm21bbbb),(21nccccmnmmnnaaaaaaaaaa2122221112110,.,.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz特点：特点：a、目标函数：、目标函数：maxb、约束条件

13、：等式、约束条件：等式c、决策变量、决策变量00d d、b bi i003、如何将线性规划数学模型的一般形式转化、如何将线性规划数学模型的一般形式转化为标准形式为标准形式a、目标函数：、目标函数：max “min” 令令 z = - z max z = - cxb、约束条件：等式、约束条件：等式 “” + xs 松弛变量松弛变量 “” - xs 剩余变量剩余变量c、决策变量、决策变量0 “x0” 设设 x=-x 则则x0 “x 无约束无约束” 设设 x- x=xd、bi0 “bi0” 乘乘“-1” ， -bi0543,xxx其中其中 就是分别对第一、第二、第三个约束就是分别对第一、第二、第三个

14、约束条件中添加的松弛变量。条件中添加的松弛变量。 maxz = 3x1+2x2 x1 +2x25 2x1+ x24 4x1+3x29x1 0, x20st.0,934425223max5432152142132121xxxxxxxxxxxxxxxxz（2 2）变量）变量 无约束，因此取两个变量无约束，因此取两个变量 使得使得 。在模型中，所有的。在模型中，所有的 都用都用 代替。代替。（1 1）变量）变量 是非正的，所以要将模型中的所有是非正的，所以要将模型中的所有 都都用用 代替，其中代替，其中例例3 3 化如下的线性规划问题模型为标准形式化如下的线性规划问题模型为标准形式0, 022322

15、3223min321321321321xxxxxxxxxxxxz无约束1x1x1x011xx2x0, 022 xx222xxx 2x22xx (5)(5)约束条件约束条件2 2是是“”型的，因此需要在左边加上一型的，因此需要在左边加上一个松弛变量个松弛变量 化为等式：化为等式： 也也就是就是(4)(4)约束条件约束条件1 1是是“”型的，并且右端的常数小于零。型的，并且右端的常数小于零。因此先将其左边减去一个剩余变量因此先将其左边减去一个剩余变量 化为等式，即化为等式，即然后再两端然后再两端-1-1得，得， 也就是也就是(3)(3)目标函数是求最小值的，因此令目标函数是求最小值的，因此令 ，即

16、，即zz32232132122323)23(xxxxxxxxxxz 4x2324321xxxx2324321xxxx232243221 xxxxx5x22325321xxxx2233253221 xxxxx。 0,223322322223max54322153221432213221xxxxxxxxxxxxxxxxxxxxz从而得到模型的标准形式为从而得到模型的标准形式为:练习题：将线性规划数学模型转化为标准形式练习题：将线性规划数学模型转化为标准形式1、min z= -x1+2x2-3x3 x1+2x2+3x3 7 -x1+ x2 - x3 -2 -3x1+ x2+2x3 =5 x1 , x

17、3 0 x2 无约束无约束2、min z= 2x1-2x2+3x3 -x1+ x2+ x3 = 4 -2x1+ x2 - x36 x1 0, x2 0 ，x3无约束无约束答案：答案：1、max z= x1 2 x2+ 2 x2”+ 3x3 x1 + 2 x2 2x2” +3x3 +x4 = 7 x1 x2 + x2” + x3 x5= 2 -3x1 + x2 x2” +2x3 = 5 x1 , x2 , x2” , x3 , x4 , x5 02、max z= 2x1+2x2 3x3+ 3x3” x1+ x2 + x3 x3” = 4 2x1+ x2 x3+ x3” + x4 = 6 x1,

18、x2 , x3, x3”, x4 00,.,. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz线性规划：线性规划： max z = cx ax = b x 0 可行解：满足条件可行解：满足条件、的解的解x ； 可行域：可行解的集合；可行域：可行解的集合； 最优解：满足条件最优解：满足条件使目标函数最大的可行解；使目标函数最大的可行解； 可行解可行解、最优解最优解a a称为线性规划问题的系数矩阵，并且总假定其秩称为线性规划问题的系数矩阵，并且总假定其秩等于其行数：等于其行数： 这意味着系数矩

19、阵这意味着系数矩阵a a的各的各行是线性无关的，这也表明约束方程中的各个方程行是线性无关的，这也表明约束方程中的各个方程式相互独立的。式相互独立的。0. .maxxbaxtscxz用矩阵形式表示线性规划数学模型用矩阵形式表示线性规划数学模型mnmmnnaaaaaaaaa212222111211amrank)(a线性规划的线性规划的基矩阵基矩阵(基基)、基变量基变量、非基变量非基变量例：对于线性规划问题例：对于线性规划问题 0,6323523632max432143214214321xxxxxxxxxxxxxxxz其系数矩阵为：其系数矩阵为： 31125023基矩阵（基）：基矩阵（基）：1223

20、3152和和还能找出其它基吗？线性规划的线性规划的基矩阵基矩阵(基基)、基变量基变量、非基变量非基变量基变量：基变量：就是由就是由m m个变量构成的一组变量，其系数构个变量构成的一组变量，其系数构成的行列式不等于零；反之满足系数行列式不等于成的行列式不等于零；反之满足系数行列式不等于零的一组零的一组m m个变量，就是基变量。个变量，就是基变量。非基变量：非基变量：线性规划中不是基变量的变量就是非基线性规划中不是基变量的变量就是非基变量。变量。基解：基解：令非基变量等于令非基变量等于0 0的解。的解。基可行解：基可行解：基解基解 + + 可行解可行解 线性规划的线性规划的基矩阵基矩阵(基基)、基

21、变量基变量、非基变量非基变量可行解可行解基可行解基可行解非可行解非可行解基解基解解之得解之得 。故我们得到基解。故我们得到基解注意到这个基解还是一个可行解。注意到这个基解还是一个可行解。 例如，对于上面的线性规划问题，如果取例如，对于上面的线性规划问题，如果取x x1 1，x x2 2为为基变量，则令非基变量基变量，则令非基变量x x3 3，x x4 4为零，约束方程组为为零，约束方程组为 623232121xxxx712,71521xx0, 0,712,7154321xxxx是否所有的基解都是基可行是否所有的基解都是基可行解？（选解？（选x x1 1,x,x3 3作为基变量）作为基变量）线性

22、规划的线性规划的基矩阵基矩阵(基基)、基变量基变量、非基变量非基变量选择：选择：标准形式的线性规划问题，其可行解是标准形式的线性规划问题，其可行解是 基基可行解，最优解可行解，最优解 是可行解，最优解是可行解，最优解 能能在可行域某一个顶点达到。在可行域某一个顶点达到。a a、一定、一定 b b、不一定、不一定 c c、一定不、一定不线性规划的线性规划的基矩阵基矩阵(基基)、基变量基变量、非基变量非基变量=目标函数目标函数约束条件约束条件行列式行列式0基矩阵基矩阵右边常数右边常数 定理定理2.22.2： 线性规划问题的基可行解是线性规划问题的基可行解是其可行域的顶点。其可行域的顶点。 定理定理

23、2.32.3： 线性规划问题的最优解如果线性规划问题的最优解如果存在，则一定有一个基可行解是最优解。存在，则一定有一个基可行解是最优解。 对于一般的线性规划问题（系数矩阵对于一般的线性规划问题（系数矩阵a am mn n），基解的个数最多为），基解的个数最多为c cn nm m个，从而基可个，从而基可行解的个数总是有限的。行解的个数总是有限的。例：例：maxz = 3x1+2x2 x1 +2x25 2x1+ x24 4x1+3x29x1 0, x20st.0,934425223max5432152142132121xxxxxxxxxxxxxxxxz基变量基变量x x1 1、x x2 2、x x

24、3 3，非基变量，非基变量x x4 4、x x5 5基解为（基解为（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3/23/2，1 1，3/23/2，0 0，0 0）是基）是基可行解，表示可行域的一个顶点。可行解，表示可行域的一个顶点。目标函数值为：目标函数值为：z=z=13/213/2基变量基变量x x1 1、x x2 2、x x4 4，非基变量，非基变量x x3 3、x x5 5基解为（基解为（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3/53/5，11/511/5，0 0，3/53/5，0 0）是基可行解，表示可行域的一

25、个顶点。是基可行解，表示可行域的一个顶点。目标函数值为：目标函数值为：z=z=31/531/5基变量基变量x x1 1、x x2 2、x x5 5，非基变量，非基变量x x3 3、x x4 4基解为（基解为（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（1 1，2 2，0 0，0 0，-1-1）是基解，）是基解，但不是可行解，不是可行域的一个顶点。但不是可行解，不是可行域的一个顶点。基变量基变量x x2 2、x x3 3、x x4 4，非基变量，非基变量x x1 1、x x5 5基解为（基解为（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5

26、）= =（0 0，3 3，-1-1，1 1，0 0）是基解，）是基解，但不是可行解，不是可行域的一个顶点但不是可行解，不是可行域的一个顶点基变量基变量x x2 2、x x3 3、x x4 4，非基变量，非基变量x x1 1、x x5 5基解为（基解为（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（0 0，4 4，-5-5，0 0，-3-3）是基）是基解，但不是可行解，不是可行域的一个顶点解，但不是可行解，不是可行域的一个顶点( x1, x2, x3) ( x1, x2, x4)( x1, x2, x5)( x1, x3, x4)( x1, x3, x5)( x1

27、, x4, x5)( x2, x3, x4)( x2, x3, x5)( x2, x4, x5)( x3, x4, x5)( 3/2, 1 3/2 ) z = 13/2( 3/5, 11/5, 3/5 ) z = 31/5( 1, 2, -1)( 9/4, 11/4, -1/2 )( 2, 3, 1) z = 6( 5, -6, -11 )( 3, -1, -1 )( 4, -5, -3 )( 5/2, 3/2, 3/2 ) z = 5( 5, 4, 9 ) z = 012x,231x21623*21xxz0 x1x2a(2,0)b(3/2,1)c(3/5,11/5)d(0,5/2)几何概念几

28、何概念代数概念代数概念约束直线约束直线满足一个等式约束的解满足一个等式约束的解约束半平面约束半平面满足一个不等式约束的解满足一个不等式约束的解约束半平面的交约束半平面的交集：凸多边形集：凸多边形满足一组不等式约束满足一组不等式约束的解的解约束直线的交点约束直线的交点基解基解可行域的顶点可行域的顶点基可行解基可行解目标函数等值线：目标函数等值线：一组平行线一组平行线 目标函数值等于一个目标函数值等于一个常数的解常数的解=目标函数目标函数约束条件约束条件基矩阵基矩阵右边常数右边常数=基变量基变量=换入变量换入变量换出变量换出变量目标函数目标函数约束条件约束条件右边常数右边常数=目标函数目标函数约束

29、条件约束条件新的基矩阵新的基矩阵右边常数右边常数=换入变量换入变量换出变量换出变量目标函数目标函数约束条件约束条件基矩阵基矩阵=目标函数目标函数约束条件约束条件新的基矩阵新的基矩阵右边常数右边常数=基本思路：基本思路：l首先求出初始基可行解首先求出初始基可行解l判断其是否为最优解判断其是否为最优解l如果不是最优，则迭代到其相邻的基本如果不是最优，则迭代到其相邻的基本可行解，并再次检验可行解，并再次检验求解线性规划求解线性规划0,934425223max2121212121xxxxxxxxs.t.xxz0,934425223max5432152142132121xxxxxxxxxxxxxxxxz

30、首先转化为标准形式首先转化为标准形式 基解与基可行解的性质：基解与基可行解的性质： 每个变量不是基变量就是非基变量每个变量不是基变量就是非基变量 基变量个数基变量个数 = = 方程个数方程个数 令非基变量令非基变量 = 0= 0 求解方程组可得基变量值求解方程组可得基变量值 若基解满足若基解满足x xj j0 0 ，则基解就是一个基可行解，则基解就是一个基可行解1 1、确定初始基可行解：、确定初始基可行解：100340101200121基变量为：基变量为： x3 ，x4 ，x5 非基变量为：非基变量为： x1，x2（0）z = 3x1 + 2x2（1） x1 +2x2 + x3 = 5（2）

31、2x1 + x2 + x4 = 4（3） 4x1+ 3x2 + x5 = 9初始初始基可行解基可行解x(0)=（0，0，5，4，9） z(0) = 0 2 2、最优性检测：、最优性检测：检验数：检验数：j j 0 0 时，基可行解为最优解时，基可行解为最优解 z = 3x1 + 2x2 + 0 x3 + 0 x4 + 0 x5 x(0)非最优解非最优解2 2、基可行解的转换：、基可行解的转换：换入变量：换入变量：max j 0 （0） z = 3x1 +2x2 + 0 x3 + 0 x4 + 0 x5 x1 为换入变量为换入变量换出变量：换出变量： （1） x1+2x2 + x3 = 5（2）

32、 2x1+ x2 + x4 = 4（3） 4x1+ 3x2 +x5 = 9（1 1）寻找换入、换出变量）寻找换入、换出变量x1 = 5 x3 x1 = 4/2 1/2x4x1 = 9/4 1/4 x5 x1 5 x1 4/2 x1 9/4 x1+ x3 = 5 2x1 + x4 = 4 4x1 +x5 = 9（2 2）代换，求新基可行解）代换，求新基可行解 基变量为：基变量为： x3 ，x1 ，x5 非基变量为：非基变量为： x2，x4rkrikikiiabm21i0aab),(min （0）z = 3 x1 + 2x2 （1） x1+ 2x2+ x3 = 5（2） 2x1+ x2 + x4

33、= 4（3） 4x1 +3x2 + x5 = 9（0）z = 3x1 + 2x2 （1） x3 = 3 3/2x2 +1/2x4（2） x1 = 2 1/2x2 1/2x4 （3） x5 = 1 x2 + 2 x4 基可行解基可行解x(1)=（2，0，3，0，1） z(1) = 6（0） z = 6 + 1/2x2 3/2x4 （1） 3/2x2 + x3 1/2x4 = 3（2） x1+ 1/2x2 + 1/2x4 = 2（3） x2 2x4 + x5 = 1 x x4 4 为换出变量为换出变量 最小比值原则最小比值原则: : =4/2=4/23 3、再最优性检测：、再最优性检测： （0）

34、z =6+ 1/2x2 3/2x4 检验数：检验数： 2 2= 1/20 = 1/20 x(1)非最优解非最优解4 4、基可行解的转换、基可行解的转换换入变量：换入变量： 2 2= 1/2= 1/2 x2 为换入变量为换入变量换出变量：换出变量： = 2 = 4 = 1 x5 为换出变量为换出变量（1） 3/2x2 + x3 1/2x4 = 3（2）x1+ 1/2x2 +1/2x4 = 2（3） x2 2x4 + x5 = 1（0） z = 6 + 1/2x2 3/2x4 （1） 3/2x2 + x3 1/2x4 = 3（2） x1+ 1/2x2 + 1/2x4 = 2（3） x2 2x4 +

35、 x5 = 1 基变量为：基变量为： x3 ，x1 ，x2 非基变量为：非基变量为： x4，x5基可行解基可行解x(2)=（3/2，1，3/2，0，0） z(2) = 6.5 检测：检测：（0）z = 6.5 1/2x4 1/2 x5 检验数检验数 0 0 x(2)是最优解是最优解 最优解最优解 x x* *= =（3/23/2，1 1，3/23/2，0 0，0 0） 最优目标函数值最优目标函数值 z z* *=6.5=6.5（0） z = 6 +1/2x2 3/2 x5（1） x3 = 3/2 5/2 x4 +3/2 x5（2） x1 = 3/2 3/2 x4 + 1/2 x5（3） x2

36、= 1 + 2 x4 x5 （0）z =6.5 1/2x4 1/2 x5（1） x3 +5/2 x4 3/2 x5 = 3/2（2） x1 +3/2 x4 1/2 x5 = 3/2（3） x2 2 x4 + x5 = 1100340101200121基变量为：基变量为： x3 ，x4 ，x5 非基变量为：非基变量为： x1，x2单纯型表：将一般形式变为标准形式单纯型表：将一般形式变为标准形式1、列出初始单纯形表、列出初始单纯形表 59/44/2主元主元x 4换出变量换出变量x 1换入变量换入变量基可行解基可行解（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（0

37、0，0 0，5 5，4 4，9 9）检验数：检验数：1 1 2 2 0 0 非最优解非最优解2 2、寻找换入变量，换出变量、寻找换入变量，换出变量max max j j 0 ; min0 0 ; min0 3、寻找新的基矩阵和基可行解、寻找新的基矩阵和基可行解x13211/201/20303/21-1/201010-2101/20-3/20 x3x500迭代的目标就是把主元迭代的目标就是把主元化为化为1，然后把主元所，然后把主元所在列其他系数化为在列其他系数化为03、寻找新的基矩阵和基可行解、寻找新的基矩阵和基可行解1x5换出变量换出变量x2换入变量换入变量24基可行解基可行解（x x1 1,

38、x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3 3，0 0，2 2，0 0，1 1）检验数：检验数：2 2 0 0 非最优解非最优解4 4、寻找换入变量，换出变量、寻找换入变量，换出变量max max j j 0 ; min0 0 ; min0 x133/21003/2 -1/23/20015/2 -3/21010-21000-1/2 -1/2x3x202检验：所有的检验：所有的j j0 0 得到最优解，最优解为：得到最优解，最优解为：（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3/23/2，1 1，3/23/2，0 0，0 0，），）

39、max z=6.5max z=6.5合并的单纯形表合并的单纯形表32000cbxbx1x2x3x4x5b 000 x3x4x51242131000100015495/14/29/4320000030 x3x1x50103/21/21100-1/21/2-200132124101/20-3/206032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/20,.,832625223min61654254324215321xxxxxxxxxxxxxxxxxz注意该问题已经满足标准形式的要求，而且可注意该问题已经满足标准形式的要求，而且可以找到初

40、始基变量以找到初始基变量x x1 1、x x3 3、x x6 6，只是他们在目，只是他们在目标函数中的系数不为标函数中的系数不为0 0。单纯形法的进一步讨论1-110-30cbxbx1x2x3x4x5x6b1x1120-20051x3011-12063.00 0 x602013182.67 0-403-50111x1120-20052.51x30- 1/31- 5/30-2/32/3-3x502/301/311/38/340-2/3014/305/3-7/3-1x21/210-1005/21x31/601-20-2/33/2-3x5-1/300111/311/300405/3-4例：考虑如何求

41、解下列线性规划问题例：考虑如何求解下列线性规划问题0,4222212232max321321321321321xxxxxxxxxxxxxxxz系数矩阵：系数矩阵：0,4222212232max654321632153214321321xxxxxxxxxxxxxxxxxxxxxz化为标准形式：化为标准形式：添加人工变量：添加人工变量：x7 ，x8数学模型变为：数学模型变为：0,4222212200032max6543216321853217432187654321xxxxxxxxxxxxxxxxxxxxmxmxxxxxxxz-231000-m-mcbxbx1x2x3x4x5x6x7x8b-mx7

42、2-12-100101-mx82210-100120 x6-121001004-2+4m3+m1+3m-m-m000-2x11-1/21- 1/2001/201/2-mx803-11-10-1110 x603/22-1/2011/209/202+3m3-m-1+m-m01-m0-2x1105/6-1/3-1/601/31/62/33x201-1/31/3-1/30-1/31/31/30 x6005/2-11/211-1/24008/3-5/32/30-m+5/3-m-2/31、人工变量法（大、人工变量法（大m法）法）-231000-m-mcbxbx1x2x3x4x5x6x7x8b1x36/50

43、1-2/5-1/502/51/54/53x22/5101/5-2/50-1/52/53/50 x6-3000110-12-22/500-1/57/50-m+1/5-m-3/51x33/501-2/501/52/506/53x2-4/5101/502/5-1/507/50 x5-3000110-12-1/500-1/50-7/5-m+1/5-m27/5。为了减少计算工作量，为了减少计算工作量，红色阴影部分可以不写红色阴影部分可以不写0, 0, 0, 2, 0, 2 . 1, 4 . 1, 087654321xxxxxxxx4 . 5527*z因此最优解为因此最优解为最优目标函数值为最优目标函数值

44、为注意：注意：如果在用大如果在用大m m法求解线性规划问题时，最法求解线性规划问题时，最终表的基变量中还含有人工变量，那么这个最终终表的基变量中还含有人工变量，那么这个最终表并没有给出原来问题的基可行解，从而没有给表并没有给出原来问题的基可行解，从而没有给出原来的线性规划问题最优解。这时原来线性规出原来的线性规划问题最优解。这时原来线性规划问题为划问题为无可行解无可行解。0,4222212232max321321321321321xxxxxxxxxxxxxxxz 由于由于m m不是一个确定的数，所以大不是一个确定的数，所以大m m法适宜于手工法适宜于手工计算，而不适合计算机求解。计算，而不适合

45、计算机求解。0,42222122min876543216321853217432187xxxxxxxxxxxxxxxxxxxxxxxxz第一阶段：求解辅第一阶段：求解辅助的线性规划问题助的线性规划问题00000011cbxbx1x2x3x4x5x6x7x8b1x72-12-1001011x82210-100120 x6-121001004 -4-1-3110000 x11 -1/21 -1/20 0 1/20 1x80 3 -1 1 -1 0 -1 1 1/2 1 0 x60 3/22 -1/20 1 1/20 9/20-31-110200 x11 0 5/6-1/3-1/60 1/31/62

46、/30 x20 1 -1/31/3-1/30 -1/31/31/30 x60 0 5/2-1 1/21 1 -1/24 000000110第一阶段第一阶段第二阶段（去掉人工变量，换为原来的目标函数）第二阶段（去掉人工变量，换为原来的目标函数）-231000cbxbx1x2x3x4x5x6b-2x11 0 5/6-1/3-1/60 2/33x20 1 -1/31/3-1/30 1/30 x60 0 5/2-1 1/21 4 0 0 11/3-5/32/30 1x36/50 1 -2/5-1/50 4/53x22/51 0 1/5-2/50 3/50 x6-3 0 0 0 1 1 2 -22/50 0 -1/57/50 1x33/50 1 -2/50 1/56