线性规划与单纯形方法PPT课件

1、第一章第一章 线性规划与单纯形法线性规划与单纯形法本章重点内容本章重点内容线性规划模型与解的主要概念线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划的单纯形法，线性规划多解分析线性规划的运用线性规划的运用建模建模第一节第一节 线性规划问题及数学模型线性规划问题及数学模型 一、实例 二、线性规划问题LP问题的共同特征 三、两变量线性规划问题的图解法 四、线性规划问题的规范型 五、规范型LP问题解的概念 六、可行解、基解和基可行解举例一、实例一、实例例例1 1 消费方案问题消费方案问题Step 1:Step 1:明确问题，设定决策变量明确问题，设定决策变量 设设I I、III

2、I两种产品的产量分别为两种产品的产量分别为x1, x2 x1, x2 。Step 2: Step 2: 确定约束条件确定约束条件产品 I II 资源限量设备 1 2 8台时原料A 4 0 16公斤原料B 0 4 12公斤 利润 2 38221 xx工工时时约约束束：1604A21 xx约约束束：原原料料1240B21 xx约约束束：原原料料0021 xx，变变量量非非负负约约束束：问应如何安排消费问应如何安排消费使该厂获利最多？使该厂获利最多？ 0124164823221212121x,xxxxx. t . sxxZmax:OBJ阐明：阐明：OBJ OBJ 表示表示Objective;Obje

3、ctive; s.t. s.t. 表示表示Subject to Subject to Step 3: Step 3: 给出目的函数给出目的函数2132xxZmax Step 4: Step 4: 整理数学模型整理数学模型例例2 现要做现要做100套钢架，每套需套钢架，每套需2.9米、米、2.1米和米和1.5米的元钢各一根。米的元钢各一根。知原料长知原料长7.4米，问如何下料，使余料最少？米，问如何下料，使余料最少？ 设设I, II, III, IV, V分别代表五种不同的原料用量方案分别代表五种不同的原料用量方案, x1, x2 , x3, x4 , x5分别代表采用各方案下料的元钢的根数。分

4、别代表采用各方案下料的元钢的根数。1234512434512351234512345:00.10.20.30.8210022100. .323100,030100500;16OBJMinZxxxxxxxxxxxs txxxxxxxxxxxxxxOBJ解得：，方案方案根数根数2.9米米2.1米米1.5米米合计合计余料余料I x11037.40IIx22017.30.1IIIx30227.20.2IVx41207.10.3Vx50136.60.8解：解：12345124345123512345:00.10.20.30.8210022100. .323100,0OBJ MinZxxxxxxxxxxx

5、stxxxxx x x x xLP(Linear Programming)LP(Linear Programming)是数学规划的一个重要分支，数是数学规划的一个重要分支，数学规划着重处理资源的优化配置，普通可以表达成以下两个问学规划着重处理资源的优化配置，普通可以表达成以下两个问题中的一个：题中的一个：1 1当资源给定时，要求完成的义务最多；当资源给定时，要求完成的义务最多；2 2当义务给定时，要求为完成义务所耗费的资源最少。当义务给定时，要求为完成义务所耗费的资源最少。 假设上述问题的目的假设上述问题的目的约束都能表达成变量的线性关系，约束都能表达成变量的线性关系，那么这类优化问题称那么这

6、类优化问题称LPLP问题。问题。 LP LP是一种处理在线性约束条件下追求最大或最小的线性是一种处理在线性约束条件下追求最大或最小的线性目的函数的方法。目的函数的方法。 目的函数用决策变量的线性函数来表示。按问题的不目的函数用决策变量的线性函数来表示。按问题的不同，要求目的函数实现最大化和最小化。同，要求目的函数实现最大化和最小化。 每一个问题变量都用一组决策变量每一个问题变量都用一组决策变量x1, x2, , x1, x2, , xnxn表示某一方案，这组决策变量的值代表一个详细方表示某一方案，这组决策变量的值代表一个详细方案，这些变量是非负且延续的。案，这些变量是非负且延续的。 存在一定的

7、约束条件，这些约束条件可以用一组线性存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。等式或线性不等式来表示。结论：线性规划是研讨在一组线性不等式或线性等式约束结论：线性规划是研讨在一组线性不等式或线性等式约束下，使得某一线性目的函数取最大或最小的极值问题。下，使得某一线性目的函数取最大或最小的极值问题。二、线性规划问题二、线性规划问题LPLP问题的共同特征问题的共同特征Max(Min) Z=c1x1+c2x2+cnxn (1) a11x1+a12x2+a1nxn ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. (2) am1x1+am

8、2x2+amnxn ( =, ) bm xj0, j=1,2, ，n (3)(1)目的函数；目的函数；(2)约束条件；约束条件；(3)决策变量非负决策变量非负n变量个数；变量个数； m约束行数；约束行数； cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数； aij技术系数；技术系数；xj决策变量决策变量线性规划模型的普通方式为：线性规划模型的普通方式为：线性规划模型的紧缩方式线性规划模型的紧缩方式11()( , )1,2,.01,2,njjjnijjijjMax Minzc xa xbims txjn n变量个数；变量个数； m约束行数；约束行数； cj价值系数；价值系数；bi右

9、端项或限额系数；右端项或限额系数； aij技术系数；技术系数；xj决策变量决策变量练习题：能否为线性规划模型？练习题：能否为线性规划模型？123123123233. .4790,1,2,3jzxxxxxxstxxxxj1231231233233. .4790,1,2,jMinzxxxxxxstxxxxjx符号不限11( , )1,2,.01,2,njjjnijjijjMaxzc xa xbimstxjn 1.1.线性不等式的几何意义线性不等式的几何意义 半平面半平面作出作出LPLP问题的可行域问题的可行域作出目的函数的等值线作出目的函数的等值线挪动等值线到可行域边境得到最优点挪动等值线到可行域

10、边境得到最优点2.2.图解法步骤图解法步骤三、两变量线性规划问题的图解法三、两变量线性规划问题的图解法2132xx 212xx 0,12416482. .32max:21212121xxxxxxtsxxZOBJ4x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30例例1Q2(4,2)Z=2x1+3x2 做目的函数做目的函数2x1+3x2的等值线，的等值线，与阴影部分的边境相交于与阴影部分的边境相交于Q2(4,2)点，阐明最优消费方点，阐明最优消费方案为：消费案为：消费I产品产品4件，消费件，消费II产品产品2件。件。Q3 目的函数目的函数z=ax1+bx2的值递增的方向与系数的

11、值递增的方向与系数a、b有关有关a 0 , b0a 0X1X2a 0 , b 0 , b0z=ax1+bx2目的函数等值线：目的函数等值线：ax1+bx2=k移项移项x2=-a/bx1+k/b目的函数等值线在纵轴目的函数等值线在纵轴上的截距为上的截距为k/b例例4 4 0,78102.46max212212121xxxxxxxtsxxZ1187654322x1876543O109x2A BCEDFGH123Z=363662:21 Zxx最优解最优解例例 用图解法求解线性规划问题用图解法求解线性规划问题12121212max2428416. .412,0Zxxxxxs txxx 4x1=164x

12、2=12x1+2x2=8x1x248Q1 4 Q4 30Q2(4,2)Z=2x1+4x2当当Z Z值由小变大时，将与值由小变大时，将与Q2Q3Q2Q3重合重合Q2Q3Q2Q3上恣意一点都是最优解上恣意一点都是最优解有无穷多最优解多重解有无穷多最优解多重解Q3(2,3)例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无界解无界解 “无有限最优解或无有限最优解或“最优解无界最优解无界约束条件过分宽松约束条件过分宽松留意：可行域不闭合不一定就会出现留意：可行域不闭合不一定就会出现无界解，这要看目的函数的性质。无界解，这要看目的函数的性质。假设目的函数是假设目的函数是minm

13、in，那么有最优解。，那么有最优解。无论有无最优解，一定有可行解。无论有无最优解，一定有可行解。121212221. .200,1,2jMaxZxxxxstxxxjx2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界独一最优解独一最优解X X* *=(1,0)=(1,0)，对应于点，对应于点A A121212221. .200,1,2jMinZxxxxstxxxjx2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无穷多

14、最优解无穷多最优解对应于点对应于点B B沿着沿着OBOB向右上方向右上方发出的射线上的一切点发出的射线上的一切点12121221. .200,1,2 jMaxZxxxxstxxxjx2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00例例 用图解法求解线性规划问题用图解法求解线性规划问题 无可行解可行域为空无可行解可行域为空121212122328416. . 412240,1,2jMaxZxxxxxs txxxxjx14x1=164x2=12x1+2x2=8x248Q1 4Q4 30-2-2x1+x2=4 无最优解无最优解3.3.图解法的作用图解法的作用 能处理少量问题能处理少量

15、问题 提示了线性规划问题的假设干规律提示了线性规划问题的假设干规律解的类型解的类型可行域类型可行域类型独一最优解独一最优解无穷多最优解无穷多最优解最优解无界最优解无界无有限最优解无有限最优解无解无解不存在可行域不存在可行域非空有界非空有界无界无界空集空集规律规律1 1：规律规律2 2： 线性规划问题的可行域为凸集线性规划问题的可行域为凸集 线性规划问题凸集的顶点个数是有限的线性规划问题凸集的顶点个数是有限的 最优解可在凸集的某顶点处到达最优解可在凸集的某顶点处到达 012012021(01)SXSXXSXXXXS（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）顶点：设 为凸集，若不存在两点，使

16、得（），则为 的一个顶点。（除顶点外，集合中任何两点的连线段都不通过顶点）基本概念基本概念12121101KnXXKXXKKaaa刮+-挝（ ）（ ）（ ）（ ）（）凸集：设 为 维空间一点集，任取两点，若（），则 为一凸集。(要求集合中的任何两点的连线段落在这个集合中) 小结：图解法的根本步骤：小结：图解法的根本步骤：1 1在直角坐标系作出可行域在直角坐标系作出可行域S S的区域的区域 普通是一个凸多边形普通是一个凸多边形2 2令目的函数值取一个知的常数令目的函数值取一个知的常数k k，作等值线：，作等值线：c1x1+c2x2=kc1x1+c2x2=k3 3对于对于maxmax问题，让目的函

17、数值问题，让目的函数值k k由小变大，即让等值线进展由小变大，即让等值线进展平移，假设它与可行域平移，假设它与可行域S S最后交于一个点普通是最后交于一个点普通是S S的一个顶的一个顶点，那么该点就是所求的最优点，假设与点，那么该点就是所求的最优点，假设与S S的一条边境重的一条边境重合，此时边境限上的点均是最优点合，此时边境限上的点均是最优点4 4将最优点所在的两条边境限所代表的方程联立求解，即得将最优点所在的两条边境限所代表的方程联立求解，即得最优解最优解X X* *，把最优解，把最优解X X* *带入目的函数，得最优值带入目的函数，得最优值Z Z* *=CX=CX* *留意：假设是求目的

18、函数最小值，等值线向反方向挪动留意：假设是求目的函数最小值，等值线向反方向挪动四、线性规划问题的规范型四、线性规划问题的规范型112211112211211222221122max. .0,1,2,0,1,2,nnnnnnmmmnnmjiZc xc xc xa xa xa xba xaxaxbs taxaxaxbxjnbim1.1.规范型规范型 1目的函数：目的函数：max2约束条件：等式约束条件：等式3变量约束：非负变量约束：非负 xj04资源限量：非负资源限量：非负bi 0规范型的构成要素规范型的构成要素2.2.线性规划规范型的紧缩方式线性规划规范型的紧缩方式111,2,.01,2,01,

19、2,Maxnjjjnijjijjizc xa xbimst xjnbim技术系数右端项价值系数约束行数变量个数: ;: ;: ;: ;:ijijabcmn3.3.线性规划规范型的向量和矩阵表达式线性规划规范型的向量和矩阵表达式矩阵式矩阵式: Max Z=CTX s.t. AX=b X0 n向量式: Max Z= cjxj j=1 n s.t. Pjxj=b j=1 xj 0, j=1,2, . ,n1111112122221222121212:,( ,.,) nnnmmmnnmnjjjmjcbxaaacbxaaaCbXAP PPaaacbxaaPa其中的的最最优优目目标标函函数数值值。问问题题

20、函函数数值值变变号号即即为为最最小小化化最最大大化化问问题题的的最最优优目目标标。求求出出最最优优解解后后，可可转转换换成成令令，小小化化问问题题根根据据这这一一原原理理，对对于于最最，最最优优值值绝绝对对值值相相同同。同同为为上上述述例例子子中中，最最优优解解相相CXZZZCXZx maxmin*4.一切一切LP问题均可化为规范型问题均可化为规范型1最小转换成最大最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*成成一一个个约约束束。这这样样就就把把两两个个约约束束转转换换，则则此此时时，则则，令令若若；，无无限限制制，令令若若，则则，令令若若abxxabxxaxxbxaxxx

21、xxxxxxxnjjjjjjjjjjjjjjjj 3000;00 为为剩剩余余变变量量若若为为松松弛弛变变量量若若0,0,2211ninjijijijninjijijijxbxxabxaxbxxabxa2不等式约束条件转换成等式约束条件不等式约束条件转换成等式约束条件3变量约束转换变量约束转换。，即即方方程程两两边边同同乘乘以以则则，即即若若1000 ijijijijibxabxab4把把bi0转换成转换成bi0例例5 5 化规范型化规范型 0,12416482.3221212121xxxxxxtsxxMaxZ )5 , 1( 01241648200032524132154321jxxxxxx

22、xxxxxxxMaxZj可化为可化为1.1.处置决策变量处置决策变量2.2.处置约束条件右端处置约束条件右端 常数项常数项3.3.约束条件不等式约束条件不等式4.4.处置目的函数处置目的函数例例6 6 化规范型化规范型型型即即可可得得到到该该问问题题的的标标准准改改为为求求，把把求求令令号号的的左左端端减减去去剩剩余余变变量量在在第第二二个个约约束束不不等等式式号号的的左左端端加加入入松松弛弛变变量量在在第第一一个个约约束束不不等等式式以以满满足足非非负负约约束束条条件件；号号两两端端同同乘乘以以在在第第三三个个约约束束条条件件；，令令其其中中令令;. 4;. 3, 1. 20;0, 0,.

23MaxMinZZZxxxxxxxxxx 无无约约束束例例：321321321321321, 0, 053327.32xxxxxxxxxxxxtsxxxMinZ1.1.处置决策变量处置决策变量2.2.处置约束条件右端处置约束条件右端 常数项常数项3.3.约束条件不等式约束条件不等式4.4.处置目的函数处置目的函数Max Z =x1+2x2+3x4-3x5+0 x6+0 x7 s.t. x1 - x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j=1,4,5,6,7

24、Max Z =x1+2x2+3(x4-x5)+0 x6+0 x7 s.t. x1 - x2 +(x4 - x5 ) +x6 = 7 x1+x2 +(x4 - x5 ) - x7 = 2 -3x1 -x2+3(x4 -x5) = 5 x20 , xj0, j=1,4,5,6,7 无约束无约束例：例：321321321321321, 0, 053327.32xxxxxxxxxxxxtsxxxMinZ最终结果最终结果中间结果中间结果 0;4 ,2 , 1,0417431432.42;8424040,2343321321321321434333xjxxxxxxxxxtsxxxZMaxxxxMaxZxx

25、xxxxj即即所所以以，满满足足；且且则则有有解解：令令课堂练习课堂练习 62 , 0,25432032.42321321321321xxxxxxxxxtsxxxMaxZ五、规范型五、规范型LPLP问题解的概念问题解的概念1111121222122212(1)(2) . .0(3),(, ( )231TnnmmmnnnMaxZC XAXbstXcxaaacxaaaCXAmn r AmaaacxLPA其中，满足（ ）、（ ）的解；满足可行解（）的可行解，为问题的最优解；优解基设最( ),0m nm mLPr Am BABBLP为问题的系数矩阵，为 的非奇异矩阵（），则称 为问题的一个基。 ) 5

26、 , 1( 01241648200032max524132154321jxxxxxxxxxxxxxZj123 100400100400121A约束系数矩阵：约束系数矩阵：x1x2x3x4x5例：例： 100400100400121A约束系数矩阵：约束系数矩阵：能够的基矩阵是能够的基矩阵是A中恣意三个列的组合，共中恣意三个列的组合，共10个。个。 0400041211B01 B 0401040212B02 B 1400040213B03 B 0001040114B04 B 1000040115B05 B 1000140016B06 B 0041000127B07 B 1040000128B08

27、B 1040100029B09 B 10001000110B010 B令令B = =( P1 , P2 , , Pm ) 且且| B | 0 ，那么称，那么称Pj (j=1,2,m) 为基向量。为基向量。与基向量与基向量Pj对应的变量对应的变量xj称为基变量，称为基变量，记为记为XB = ( x1 , x2 , , xm )T，其他的变量称为非基变量，其他的变量称为非基变量，记为记为XN = ( xm+1 , xm+2 , , xn ) T 。1112112mmmmmaaaaaa为为非非基基变变量量。、为为一一组组基基变变量量，、则则对对应应的的时时，矩矩阵阵为为如如在在典典型型示示例例中中，

28、当当基基543211040004121xxxxxB 为为非非基基变变量量。、一一组组基基变变量量，为为、时时，则则对对应应的的而而当当基基矩矩阵阵为为2154310100010001xxxxxB 化化。而而是是随随着着基基的的变变化化而而变变一一成成不不变变的的，问问题题中中，基基变变量量并并不不是是由由此此可可见见，同同一一个个LP 100400100400121A ()()00NBTTBNBXXXXXX令，求得一组基变量的值，则（，）（， ）为基本解。（顶点）既是基本解，又是可行解。既是基可行解，又是使目标函数值达到最优的解。基可行解对应的基。基 本 解基 本 可行解基最优基最优解解可行基

29、最优基对应的基。B1=(P1,P2)：基：基1212243510 xxxx 令：令：XB1=(x1,x2)x1=0， x2=2X=(0, 2, 0, 0)XB1=(0, 2)12123124243510. .0,1,2,3,4jMaxZxxxxxxxxs txj 例例：134(,)BNXxx 134(,)0BNXxx 对应于对应于B1的基解为的基解为线性规划规范型问题解的关系线性规划规范型问题解的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解例例7 7 Max Z =2x1+3x2 Max Z =2x1+3x2 s.t. x1+ s.t. x1+ 2x

30、282x28 4x1 4x1 16 16 4x2 124x2 12 x1, x2 0 x1, x2 0 六、可行解、基解和基可行解举例六、可行解、基解和基可行解举例非基非基变量变量基变量基变量图中的点图中的点x4, x5x1=4x2=3x3= -2 A基解基解x3, x5x1=2x2=3x4=8B基可行解基可行解x3, x4x1=4x2=2x5=4C基可行解基可行解x2, x4x1=4x3=4x5=12D基可行解基可行解x2, x3x1=8x4= -16x5=12E基解基解x1, x5x2=3x3=2x4=16F基可行解基可行解x1, x3x2=4x4=16x5= -4 G基解基解x1, x2

31、x3=8x4=16x5=12H基可行解基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH ) 5 , 1( 01241648200032524132154321jxxxxxxxxxxxxxMaxZj规范型规范型例例8 81187654322x1876543O109x2A BCEDFGH123f(x)=36K 0,78102.46max212212121xxxxxxxtsxxZ第二节第二节 LP LP问题的根本实际问题的根本实际一、根本概念一、根本概念12121101( )( )( )( ).,(),SnXXSXXXSS凸凸集集：设设 为为 维维欧欧氏氏

32、空空间间一一点点集集 若若任任意意两两点点、两两点点连连线线上上的的一一切切点点则则称称 为为一一凸凸集集。的的一一顶顶点点。为为则则称称成成立立使使，对对于于若若不不存存在在为为一一凸凸集集凸凸集集顶顶点点：设设）（）（SXXXXSXXSXS)0()2()1(0)2()1(0,)1(),10(,. 2 的的一一个个凸凸组组合合。为为则则称称使使得得若若存存在在个个点点，维维空空间间中中的的为为凸凸组组合合：设设）（）（）（）（）（）（）（)(211221121)(21,)1, 10( ,. 3kkiiikkkkXXXXXXXXknXXX 判别以以下图形哪些是凸集，哪些不是凸集？判别以以下图形

33、哪些是凸集，哪些不是凸集？前往前往定理定理1 LP1 LP问题的可行域为一凸集。问题的可行域为一凸集。 121122(1)(2)(1)(2)|0,000 1,(1)(1)(1)0,()SXAXbXXXSAXbXAXbXXXXAXAXXbbbXXSS（ ）（ ）（ ）（ ）（ ）（ ）证明：记，任取则，；，对于， 作则显然则因此 为一凸集。凸集的交集一定是凸集，而凸集的并集不一定是凸集二、根本定理二、根本定理引理引理 线性规划问题的可行解线性规划问题的可行解X=(x1, x2, , xn)T是基可行解是基可行解的充要条件为的充要条件为X的正分量所对应的系数列向量是线性独立的。的正分量所对应的系数

34、列向量是线性独立的。为为基基可可行行解解。所所以以由由定定义义。解解恰恰为为构构成成极极大大无无关关组组，对对应应个个与与向向量量中中取取出出时时，一一定定可可以以从从其其余余列列为为相相应应基基可可行行解解时时，它它们们恰恰为为一一个个基基，线线性性独独立立，必必有有由由于于向向量量。所所对对应应的的系系数数列列向向量量为为其其中中不不妨妨设设先先证证充充分分性性：XXPPPkmmkxxxXmkmkPPPPPPxxxkixxxxXkkkkkik,)()0 , 0 ,(,), 2 , 1(0),0 , 0 ,()1(212121212121 。由由基基可可行行解解的的定定义义可可知知再再证证必

35、必要要性性：)2(定理定理2 2 线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。I,XXLP证明：第 步先证“若是基可行解 则是问题的可行域顶点”。反证法成成立立。）（使使（）（问问题题的的可可行行解解为为、则则存存在在不不同同的的两两个个点点）（不不是是顶顶点点，设设）（）（）（）（）（）（）（）（）（）（）（）（)1 , 0(,1),;,212222121121112121 XXXxxxXxxxXLPXXxxxXXnnn即：假设即：假设X是是LP问题的可行解，那么问题的可行解，那么“X是是LP问题的基可行解问题的基可行解等价于等价于“X是是LP问题可行

36、域顶点问题可行域顶点设设X是基可行解，那么其对应的向量组是基可行解，那么其对应的向量组a1,a2, ,am线性无关线性无关(mm时，有时，有xj=xj(1)= xj(2)= 0.不不是是基基可可行行解解。所所以以线线性性相相关关，与与假假设设矛矛盾盾所所以以不不全全为为零零又又得得）（）（）（）（）（）（）（）（XaaaxxXXxxaxxamjjmmm,)(0)()(:),2()1(2121212121111 )2()1(,22221211212111)2()1(baxaxaxbaxaxaxXXmmmm ）（）（）（）（）（）（是可行域的两点，所以是可行域的两点，所以因为因为)5(;00,40

37、)0()3(2211211212211baxaxaxbxxxaaaaabAXLPxaaakkknkkkk ）即即（问问题题的的可可行行解解，则则是是由由于于）（得得：IIXX第 步：用反证法证“若是可行域顶点，则是基可行解”)3(0,., 2 , 1, 0,)0 , 0 ,(221121 kkiiiikaaaaxkixxxxX使使数数即即存存在在一一组组不不全全为为零零的的线线性性相相关关。所所对对应应的的系系数数列列向向量量则则但但不不是是基基可可行行解解。其其中中是是可可行行解解设设）（）（令令0 , 0 ,0 , 0 ,2211)2(2211)1(kkkkxxxXxxxX 连连线线的的中

38、中点点。、是是即即可可得得：、由由）（）（）（）（21)2()1(21,2121XXXXXXXX 不不是是可可行行域域的的顶顶点点。是是可可行行解解。这这证证明明、即即充充分分小小时时，可可保保证证另另外外，当当）（）（XXXmixii21),2, 1(0 111222111222(5) (4),()()()(5) (4),()()()kkkkkkxaxaxabxaxaxab得： 得： ）（处处达达到到最最优优数数在在也也是是可可行行解解，且且目目标标函函若若问问题题可可行行域域的的顶顶点点为为证证明明：设设0*)0()0()()2()1(,CXZXXLPXXXk 达达到到最最大大值值。，即即

39、目目标标函函数数在在顶顶点点为为最最优优值值，所所以以只只能能又又。所所以以则则中中最最大大者者。，使使之之为为所所有有的的到到某某一一个个顶顶点点在在所所有有的的顶顶点点中中必必能能找找。因因此此其其中中表表示示成成：不不是是顶顶点点，所所以以它它可可以以因因）（）（）（)()()0()0()()0()(1)(1)()(1)(011)(0)0(1, 0,mmmmkimikiiiimkiiikiiikiiiXCXCXCXCXCXCXCXaCXaCXXCXaCXaaXaXX 定理定理3 3 假设可行域有界，那么假设可行域有界，那么LPLP问题的目的函数一定可以在问题的目的函数一定可以在其可行域的

40、顶点上到达最优。其可行域的顶点上到达最优。引理引理 假设假设S是有界凸集，那么任何一点是有界凸集，那么任何一点XS可表示为可表示为S的顶的顶点的凸组合。点的凸组合。 线性规划问题的可行域是凸集线性规划问题的可行域是凸集( (定理定理1)1)；凸集的顶点对应；凸集的顶点对应于基可行解于基可行解( (定理定理2)2)，基可行解，基可行解( (顶点顶点) )的个数是有限的；假设的个数是有限的；假设线性规划有最优解，必在可行域某顶点上到达线性规划有最优解，必在可行域某顶点上到达( (定理定理3)3)。因此。因此, ,我们可以在有限个基可行解中寻觅最优解。我们可以在有限个基可行解中寻觅最优解。 由线性代

41、数知，对规范形由线性代数知，对规范形LP问题，用枚举法可以求出一切问题，用枚举法可以求出一切基解，再经过察看找出其中的可行解基可行解，进而找基解，再经过察看找出其中的可行解基可行解，进而找出最优解。但假设变量和方程较多，比如出最优解。但假设变量和方程较多，比如m=50，n=100，一，一切基解有能够达切基解有能够达1029个，即使计算机每秒能求解个，即使计算机每秒能求解1亿个这样亿个这样的方程组，也需求的方程组，也需求30万亿年！因此，必需寻求有效的算法。万亿年！因此，必需寻求有效的算法。 为加快计算速度，算法必需具有两个功能，一是每得到一个为加快计算速度，算法必需具有两个功能，一是每得到一个

42、解，就来检验能否曾经最优，假设是停顿。二是假设不是最优，解，就来检验能否曾经最优，假设是停顿。二是假设不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。形法。 第三节第三节 单纯形法单纯形法根本思想根本思想检验解的检验解的最优性最优性终了终了Y旋转运算消元运算旋转运算消元运算确定另一个根本可行解确定另一个根本可行解N化化LP问题为规范型，问题为规范型，确定一个初始根本可行解确定一个初始根本可行解 化化LP问题为规范型，从可行域的某问题为规范型，从可行域的某个基可行解一个顶点开场，转换到个基可行解一个顶点开场，转换到另一个

43、基可行解另一个顶点，并使另一个基可行解另一个顶点，并使目的函数值得到改善，如此反复，从而目的函数值得到改善，如此反复，从而求得问题的最优解。其本质是逐渐迭代求得问题的最优解。其本质是逐渐迭代逼近法。逼近法。一、确定初始基可行解一、确定初始基可行解Max Z=CXs.t. AX=b X0我们首先引见求初始基可行解的方法。我们首先引见求初始基可行解的方法。1.1.假设给定问题规范化后且假设给定问题规范化后且 系数矩阵系数矩阵A A中存在中存在m m个线性无个线性无关的单位列向量，那么以这关的单位列向量，那么以这m m个单位列向量构成的单位子矩阵作为个单位列向量构成的单位子矩阵作为初始基初始基B B

44、，那么，那么 ，其他，其他xj=0 xj=0是基可行解。是基可行解。2.2.大大M M法人工变量法法人工变量法0b 10BXB bb以以x2x2为主元素为主元素以以x1x1为主元素为主元素例例 2x1+ x2+ 2x3=10 (1) 3x1+ 3x2+ x3= 6 (2) x1+ 1/2x2+ x3= 5 (1)0 x1+ 3/2x2-2x3= -9 (2)(1)/ 2 ,(2)-(1)3 x1+ 0 x2+ 5/3x3= 8 (1)0 x1+ x2 - 4/3x3= -6 (2)(2) 2/3 , (1)-(2) /2二、旋转运算二、旋转运算三、检验数的意义三、检验数的意义结论：假设结论：假

45、设LPLP问题经过单纯形法迭代到某步时，一切检验数问题经过单纯形法迭代到某步时，一切检验数0,0,那么该那么该LPLP问题已得到最优解。问题已得到最优解。Max Z=CXs.t. AX=b X0假设假设cj-CBB-1Pj=j0, 那么那么ZZ0, Z0即为最优解即为最优解. (基变量的检验数基变量的检验数必为必为0)令令A=(B,N), X= XB A=(B,N), X= XB ,C=(CB,CN),C=(CB,CN) XN XN由由AX=b (B,N) XB =b BXB+NXN=b B-1BXB+B-AX=b (B,N) XB =b BXB+NXN=b B-1BXB+B-1NXN=B-1

46、b1NXN=B-1b XN XN XB=B-1b XB=B-1bB-1NXN (2)B-1NXN (2)将将(2)(2)式代入目的函数得式代入目的函数得Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN)+CNXN Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN)+CNXN XN XN = CBB-1b+(CN-CBB-1N)XN = CBB-1b+(CN-CBB-1N)XN = Z0 + (cj-CBB-1Pj)xj = Z0 + (cj-CBB-1Pj)xj xj xj为非基变量为非基变量 单纯形法举例单纯

47、形法举例 0,121684243221221121xxxxxxxxMaxZ化为规范型化为规范型 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj约束方程的系数矩阵约束方程的系数矩阵123451 2 1 0 0( ,)4 0 0 1 00 4 0 0 1AP P P P P 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj3451 0 0(,)0 1 00 0 1BP P P是基,对应于B的变量x3，x4，x5为基变量，312415282164124xxxxxxx1将将1代

48、入目的函数后得到代入目的函数后得到z=0+2x1+3x2，令非基变量令非基变量x1=x2=0.得到得到z=0，及一个基可行解，及一个基可行解X(0)=(0,0,8,16,12)T 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZjx2=3， x5为换出变量为换出变量324528216124xxxxx3将将3代入目的函数后得到代入目的函数后得到z=9+2x13/4x5，令非基变量令非基变量x1=x5=0.得到得到z=9，及一个基可行解，及一个基可行解X(1)=(0,3,2,16,0)T当将当将x2定为换入变量后，必需从定为换入变量后，必

49、需从x3，x4，x5中确定一个换出变量，并保证中确定一个换出变量，并保证x3，x4，x50，当当x1=0时，由时，由1式得到式得到2用高斯消元法，将用高斯消元法，将x2的系数列向量变换为单位列向量，得到的系数列向量变换为单位列向量，得到3154125122164134xxxxxxx 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj这时目的函数的表达式是这时目的函数的表达式是z=141.5x30.125x4，当将当将x1定为换入变量后，继续利用上述方法定为换入变量后，继续利用上述方法确定换出变量，继续迭代，再得到一个基可确定换出变量，

50、继续迭代，再得到一个基可行解行解X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30Q2 (4,2)Z=2x1+3x2 Q3对于线性规划问题：对于线性规划问题：Max Z=CTX AX=bMax Z=CTX AX=b，X0X0，可用如下三，可用如下三个判别定理来判别线性规划问题能否曾经获得最优解或为无个判别定理来判别线性规划问题能否曾经获得最优解或为无界解。界解。 判别定理判别定理1 1 设设X X为线性规划的一个基可行解，且对于一为线性规划

51、的一个基可行解，且对于一切切jJjJJ J为非基变量的下标集有为非基变量的下标集有j0j0，那么，那么X X为为线性规划的最优解。线性规划的最优解。 判别定理判别定理2 2 设设X X为线性规划的一个基可行解，且对于一为线性规划的一个基可行解，且对于一切切jJjJJ J为非基变量的下标集有为非基变量的下标集有j 0j 0，同时有，同时有某个非基变量的检验数某个非基变量的检验数k=0( kJ)k=0( kJ)，那么该线性规，那么该线性规划有无穷多最优解。划有无穷多最优解。 判别定理判别定理3 3 设设X X为线性规划的一个基可行解，假设有为线性规划的一个基可行解，假设有k0 ( kJ) k0 (

52、 kJ) ，且，且pk0pk0，即，即aik 0aik 0i=1,mi=1,m，那么该线性规划问题具有无界解无最优解。那么该线性规划问题具有无界解无最优解。一、步骤一、步骤Step 1. 化化LP问题为规范型问题为规范型,建立初始单纯形表建立初始单纯形表;Step 2. 假设一切检验数假设一切检验数0,那么最优解已到达。那么最优解已到达。 否那么否那么,计算计算 , 选取选取k 所对应的变量所对应的变量xk 为换入变量进基变量为换入变量进基变量;最大最大检验数规那么检验数规那么Step 3. 计算计算 ,选取选取l 所对应所对应的变量的变量xl 为换出变量出基变量为换出变量出基变量;最小比值规

53、那么最小比值规那么Step 4. 以以alk为主元素进展旋转运算为主元素进展旋转运算,转转Step 2;min|0illikiiklkbbaaa= = = =max|0kjjj= = 第四节第四节 单纯形法的步骤单纯形法的步骤cj CB XB b x1 x2 xm xm+1 xn j 基可行解：基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 01.1.初始单纯形表初始单纯形表c1 c2 cm cm+1 cnc1 x1 c2 x2 cm xmb1 b2 bm1 0 0 a1, m+1 a1n0 1 0 a2, m+1 a2n 0 0 1 am, m+1

54、 amn0 0 0 m+1 n-CBTB-1b对于上述单纯形表：对于上述单纯形表：1 1一个基对应一个单纯形表，且单纯形表中必需有一一个基对应一个单纯形表，且单纯形表中必需有一个初始单位基。个初始单位基。2 2从单纯形表中，可立刻得到一个基可行解：从单纯形表中，可立刻得到一个基可行解： x1=b1, x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0 x2=b2, , xm=bm , xm+1=xm+2= =xn= 03 3用检验数的计算公式很容易计算检验数，并可根据用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解能否为最优解或线性三个判

55、别定理判别上述基可行解能否为最优解或线性规划问题无最优解。规划问题无最优解。2.2.换入变量进基变量的选择换入变量进基变量的选择cj c1 c2 cm cm+1 ck cn CB XB b x1 x2 xm xm+1 xk xn c1 x1 c2 x2 cm xmb1 b2 bm 1 0 0 a1, m+1 a1k a1n 0 1 0 a2, m+1 a2k a2n 0 0 1 am, m+1 amk amnj -CBTB-1b 0 0 0 m+1 k n选取选取 所对应的变量所对应的变量xk xk 为换入变量。为换入变量。max|0kjjj= = 3.3.换出变量出基变量的选择换出变量出基变

56、量的选择cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn c1 x1 cl xl cm xmb1 bl bm 1 0 0 a1, m+1 a1k a1n 0 1 0 al, m+1 alk aln 0 0 1 am, m+1 amk amn1 l mj -CBTB-1b 0 0 0 m+1 k n选取选取 所对应的变量所对应的变量xl xl 为换出变量。为换出变量。min|0illikiiklkbbaaa= = = =4.4.旋转运算旋转运算cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn

57、c1 x1 cl xl cm xmb1 bl bm 1 0 0 a1,m+1 a1k a1n 0 1 0 al,m+1 alk aln 0 0 1 am,m+1 amk amnj ck xkbl /alk0 1/alk 0 al, m+1/alk1 aln/alk b11 -a1k/alk 0 a1, m+1 0 a1nbm0 -amk/alk1 am, m+1 0 amn二、实例二、实例 0,121684243221221121xxxxxxxxMaxZ化为规范型化为规范型 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj单纯形表算

58、法单纯形表算法cj CB XB b x1 x2 x3 x4 x5 j 以以4为主元素进展旋为主元素进展旋转运算，转运算，x2为换入变为换入变量，量，x5为换出变量为换出变量cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/4以以11为主元素进展为主元素进展运算，运算，x1x1为换入变为换入变量，量， x3 x3为换出变量为换出变量0 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0

59、0 1 0 0 4 0 0 1 2 3 0 0 004-3cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x4 3 x2 2 8 3 1 0 1 0 -1/2 - 0 0 -4 1 2 4 0 1 0 0 1/4 12j -13 0 0 -2 0 1/4 以以22为主元素进展运为主元素进展运算，算，x5x5为换入变量，为换入变量， x4x4为换出变量为换出变量cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x2 4 4 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 j -

60、14 0 0 -3/2 -1/8 0此时到达最优解：此时到达最优解：X*=(4, 2)T, Max Z=14。4x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系三、单纯形表与图解法的对应关系X1=(0,0)T, Z1=0X2=(0,3)T, Z2=9X3=(2,3)T, Z3=13X4=(4,2)T, Z4=14Q1Q2QQ3基可行解基可行解 基可行解基可行解 迭代迭代 顶点顶点 相邻的顶点相邻的顶点迭代迭代 图解法：图解法：单纯形表算法：单纯形表算法：对于极小化问题，其最优解的断定定理和进基变量的选取和对于极小化问题，其最优解的断定定理和进基变量的选取和极