1.线性规划及单纯形法ppt课件

1、第一章第一章线性规划及其单纯形法线性规划及其单纯形法第一章第一章 线性规划及单纯形法线性规划及单纯形法 第一节 线性规划问题及数学模型 Linear Programming , LP1939年 苏 康托洛维奇1941年 美 Hichook1947年 G. B. Dantzig 单纯形法1979年 苏 哈奇安算法1984年 Karmarkar算法 LPLP是数学规划的一个重要分支，数学规划着重解决资源的是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：优化配置，一般可以表达成以下两个问题中的一个：（1 1当资源给定时，要求完成的任务最多；当资源给定时，

2、要求完成的任务最多；（2 2当任务给定时，要求为完成任务所消耗的资源最少。当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标若上述问题的目标约束都能表达成变量的线性关系，约束都能表达成变量的线性关系，则这类优化问题称则这类优化问题称LPLP问题。问题。LPLP是一种解决在线性约束条件下追求最大或最小的线性目是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。标函数的方法。一、实例一、实例例例1 生产计划问题生产计划问题 (书书P8，典型示例，典型示例)Step 1:Step 1:明确问题，设定决策变量明确问题，设定决策变量设设I I、IIII两种产品的产量分别为两种产品

3、的产量分别为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;Objective; s.t. s.t. 表示表示Su

4、bject to Subject to Step 3: Step 3: 给出目标函数给出目标函数2132xxZmax Step 4: Step 4: 整理数学模型整理数学模型例例2 污水处理问题污水处理问题 (书书P9)环保要求：环保要求：(污水量污水量/河水量河水量)0.2%， 河流自净力：河流自净力：20%500万m3200万m31.4万m3，800元/万m3 o工厂2 2万m3 ，1000元/万m3 o工厂1设设x1x1x2x2为工厂为工厂1 12 2 的日污水处理量。建的日污水处理量。建立该问题的数学模型立该问题的数学模型为：为： 0,4 . 10 . 26 . 18 . 00 . 1

5、. .8001000min:212121121xxxxxxxtsxxZOBJ二、总结二、总结 目标函数用决策变量的线性函数来表示。按问题目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。的不同，要求目标函数实现最大化和最小化。线性规划问题线性规划问题LP问题的共同特征：问题的共同特征： 每一个问题变量都用一组决策变量每一个问题变量都用一组决策变量x1, x2, , xn表表示某一方案，这组决策变量的值代表一个具体方案，这示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的且在某范围内连续取值。些变量是非负的且在某范围内连续取值。 存在一定的约束条件，这

6、些约束条件可以用一组存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。线性等式或线性不等式来表示。三、线性规划问题的一般形式三、线性规划问题的一般形式mibmnnjxbxaxaxabxaxaxabxaxaxatsxcxcxcZijmnmnmmnnnnnn,2,1,0),( : :,2,1,0),(),(),(),(.max(min)221122222121112121112211 约约束束条条件件个个数数。变变量量个个数数；四、两变量线性规划问题的图解法四、两变量线性规划问题的图解法1.线性不等式的几何意义线性不等式的几何意义 半平面半平面作出作出LP问题的可行域问题的可行

7、域作出目标函数的等值线作出目标函数的等值线移动等值线到可行域边界移动等值线到可行域边界得到最优点得到最优点2.图解法步骤图解法步骤 0,12416482.32max:21212121xxxxxxtsxxZOBJ例例1 （典型示例）：（典型示例）：4x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0) Q2(4,2)Z=2x1+3x2 做目标函数做目标函数2x1+3x2的等值线，与阴影部分的的等值线，与阴影部分的边界相交于边界相交于Q(4,2)点，表明最优生产计划为：生产点，表明最优生产计划为：生产I产品产品4件，生产件，生产II产品产品2件。件。

8、Q1(4,0)Q3(2,3)Q5(4,3)图解法意义不大，但可直观揭示有关概念。图解法意义不大，但可直观揭示有关概念。3.LP解的类型解的类型有有4类：类：（1唯一最优解唯一最优解 如例如例1的的Q2点。点。（2无穷多最优解多重解）无穷多最优解多重解）（3无界解无界解（4无可行解无可行解0 4 8 12 x1 9 6 3 可行域可行域Z=364, 6此线段上的点均为最优点x2当例当例1 的目标函数变为的目标函数变为 max Z =2x1+4x2 多重解示例多重解示例 8, 3x2可行域不闭合Z增大方向x1无界解示例无界解示例 产生原因：缺少约束条件产生原因：缺少约束条件 注注 意：可行域不闭合

9、不一定就会出现无界意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目解，这要看目标函数的性质。若目标函数是标函数是min，则有最优解。无论，则有最优解。无论有无最优解，一定有可行解。有无最优解，一定有可行解。 无可行解示例无可行解示例 无公共区域(可行域)产生原因： 有相互矛盾的约束条件。x2x14. 图解法的作用图解法的作用LPLP问题问题有可行解有可行解有最优解有最优解唯一解唯一解无穷多解无穷多解无最优解可行域为无界）无最优解可行域为无界）无可行解无解）无可行解无解）（1规律：规律： 揭示了线性规划问题有关规律和结论。揭示了线性规划问题有关规律和结论。（2结论：若结论：若LP

10、问题有最优解，则要么最优解唯一对问题有最优解，则要么最优解唯一对应其中一个顶点），要么有无穷多最优解应其中一个顶点），要么有无穷多最优解对应其中两个顶点连线上的所有点）。对应其中两个顶点连线上的所有点）。五、五、 线性规划问题的标准型线性规划问题的标准型1. 标准型的构成要素标准型的构成要素（1目标函数：目标函数：max（2约束条件：等式约束条件：等式（3变量约束：非负变量约束：非负 xj0（4资源限量：非负资源限量：非负bi 0技技术术系系数数右右端端项项，价价值值系系数数约约束束行行数数变变量量个个数数: ;,2, 1,0: : ;: ;:,2, 1,0.max22112222212111

11、2121112211ijiijjmnmnmmnnnnnnamibbcmnnjxbxaxaxabxaxaxabxaxaxatsxcxcxcZ 2. 标准型的表示方法标准型的表示方法（1解析式解析式简写的解析式简写的解析式 , 2 , 10, 2 , 1.max11 ）（）（njxmibxatsxcZjijnjijjnjj 0.maxXbAXtsCXZ亦可写成：亦可写成：0max XbAXCXZ，其中：其中： nmnmnmmnncccCbbbbxxxXaaaaaaaaaA212121212222111211 （2矩阵式矩阵式X决策变量列向量。决策变量列向量。 b约束条件右端常数资源列向量。约束条件

12、右端常数资源列向量。C目标函数价值系数行向量。目标函数价值系数行向量。 Amn约束条件左端系数矩阵。约束条件左端系数矩阵。 ),2 , 1(0.max12121222211121121njxbxPtsCXZPPPAaaaaaaaaaAaaaPjnjjjnmnmmnnnjjjj则则）（可可写写成成：矩矩阵阵时时，当当（3向量和矩阵符号式向量和矩阵符号式的的最最优优目目标标函函数数值值。问问题题函函数数值值变变号号即即为为最最小小化化最最大大化化问问题题的的最最优优目目标标。求求出出最最优优解解后后，可可转转换换成成令令，小小化化问问题题根根据据这这一一原原理理，对对于于最最，最最优优值值绝绝对对

13、值值相相同同。同同为为上上述述例例子子中中，最最优优解解相相CXZZZCXZx maxmin*3. 非标准型的标准化非标准型的标准化（1最小转换成最大最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*成成一一个个约约束束。这这样样就就把把两两个个约约束束转转换换，则则此此时时，则则，令令若若；，无无限限制制，令令若若，则则，令令若若abxxabxxaxxbxaxxxxxxxxxxnjjjjjjjjjjjjjjjj 3000;00 为为剩剩余余变变量量若若为为松松弛弛变变量量若若0,0,2211ninjijijijninjijijijxbxxabxaxbxxabxa（2不等式约束条

14、件转换成等式约束条件不等式约束条件转换成等式约束条件（3变量约束转换变量约束转换。，即即方方程程两两边边同同乘乘以以则则，即即若若1000 ijijijijibxabxab（4把把bi0转换成转换成bi0例例1 0,12416482.32max21212121xxxxxxtsxxZ )5 , 1( 01241648200032max524132154321jxxxxxxxxxxxxxZj可化为可化为例例2 化标准型化标准型型型即即可可得得到到该该问问题题的的标标准准改改为为求求，把把求求令令以以满满足足非非负负约约束束条条件件；号号两两端端同同乘乘以以在在第第三三个个约约束束条条件件号号的的左

15、左端端减减去去剩剩余余变变量量在在第第二二个个约约束束不不等等式式号号的的左左端端加加入入松松弛弛变变量量在在第第一一个个约约束束不不等等式式；，令令其其中中令令;maxmin, 1;0;0, 0,7622254543ZZZZxxxxxxxxxx 无无约约束束321321321321321,0,053327.32minxxxxxxxxxxxxtsxxxZ 0;4 ,2,1,0417431432.42max;842max4040,2343321321321321434333xjxxxxxxxxxtsxxxZxxxZxxxxxxj即即所所以以，满满足足且且；则则有有解解：令令课堂作业课堂作业1 6

16、2 , 0,25432032.42max321321321321xxxxxxxxxtsxxxZ六、标准型六、标准型LPLP问题的解问题的解 )3(0 )2(.)1(maxXbAXtsXCZT1. 基本概念基本概念）的的解解；）、（满满足足（可可行行解解32,21 ncccC其中，其中，,21 nxxxX,212222111211 mnmmnnaaaaaaaaaAmArnm )(,并假定：并假定：问问题题的的一一个个基基。为为），则则称称非非奇奇异异子子矩矩阵阵（的的为为问问题题的的系系数数矩矩阵阵，为为设设基基LP0,)(LPBBABmArAmmnm 问题的最优解；问题的最优解；）的可行解，为

17、）的可行解，为满足（满足（最优解最优解LP1。，一一般般个个数数为为问问题题，基基的的最最大大个个决决策策变变量量的的标标准准个个约约束束条条件件，对对于于CCmnmnnm LP 4 , 3 , 2 , 1, 0105342.max42132121jxxxxxxxtsxxZj例例：,10530121 A，分分别别是是：基基的的最最大大可可能能个个数数为为624 CCmn， 53211B， 03112B， 13013B， 05124B， 15025B 10016B问问题题的的基基。均均为为根根据据基基的的定定义义，LP61BB ）（令令mmmmmmmPPPaaaaaaaaaB,212122221

18、11211 问问题题的的一一个个基基。为为，则则且且LP0BB 。中中的的组组成成基基的的向向量量。如如基基向向量量mPPPB,21。，记记为为如如基基向向量量所所对对应应的的变变量量。基基变变量量TmBmxxxXxxx),(,2121 。，记为，记为基变量之外的变量。如基变量之外的变量。如非基变量非基变量TnmNnmxxXxx),(,11 时时，如如在在上上例例中中，当当基基为为 05124B为为非非基基变变量量。、为为一一组组基基变变量量，、则则对对应应的的4132xxxx为为非非基基变变量量。、为为一一组组基基变变量量，、时时，则则对对应应的的而而当当基基为为432115321xxxxB

19、 化化。而而是是随随着着基基的的变变化化而而变变一一成成不不变变的的，问问题题中中，基基变变量量并并不不是是由由此此可可见见，同同一一个个 LP，则则，求求得得一一组组基基变变量量的的值值令令解解本本基基BNXX0)( 为为基基本本解解。），（），（TBTNBXXXX0 点点。，如如典典型型示示例例图图解解法法中中的的71Q,QO解解。既既是是基基本本解解，又又是是可可行行（顶顶点点）可可行行解解本本基基)(点点。如如典典型型示示例例图图解解法法中中的的4321Q,Q,Q,Q,O解解。目目标标函函数数值值达达到到最最优优的的既既是是基基可可行行解解，又又是是使使基基最最优优解解 点点。如如典典

20、型型示示例例图图解解法法中中的的2Q基基可可行行解解对对应应的的基基。可可行行基基 基基最最优优解解对对应应的的基基。最最优优基基 4x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0) Q2(4,2)Q1(4,0)Q3(2,3)Q5(4,3)基变量基变量非非 基基 变变 量量图中的点及对应图中的点及对应的解的解x3=8x4=16x5=12x1，x2O 基可行解基可行解x1=4x3=4x5=12x2，x4Q1 基可行解基可行解x1=4x2=2x5=5x3，x4Q2 基可行解基可行解 最优解最优解x1=2x2=3x4=8x3，x5Q3 基可行解基可

21、行解x2=3x3=2x4=16x1，x5Q4 基可行解基可行解x1=4x2=3x3=2x4，x5Q5 基解基解x2=4x4=16x5=4x1，x3Q6 基解基解x1=8x4=16x5=12x2，x3Q7 基解基解x1=2, x2=2, x3=2, x4=8, x5=4K 可行解可行解K2. 可行解、基解和基可行解举例可行解、基解和基可行解举例 典型示例标准化后有典型示例标准化后有3个约束条件、个约束条件、5个决策变量，个决策变量，基的最大个数可达基的最大个数可达C53=10个，但实际上只有个，但实际上只有8个。个。约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解

22、行解3. LP标准型问题解的关系标准型问题解的关系4. LP标准型问题解的结论标准型问题解的结论 根据根据LP的图解法及解的基本概念可知：的图解法及解的基本概念可知：基解对应约束条件的交点；基解对应约束条件的交点；基可行解对应可行域的顶点基可行解对应可行域的顶点最优解一定是基可行解，一定在可行域的顶点上得到。最优解一定是基可行解，一定在可行域的顶点上得到。第二节第二节 单纯形法单纯形法 Simplex MethodSimplex Method 由线性代数知，对LP标准型问题，理论上可以求出所有基解枚举法），再通过观察找出其中基可行解，进而找出最优解。但如果变量和方程较多，比如m=50，n=10

23、0，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。 为加快计算速度，算法必须具有两个功能，一是每得到一个基可行解，就能检验是否已经最优，若是，停顿。二是若不是最优，要保证下一步得到的基可行解不劣于当前解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。 一、基本思想一、基本思想化化LP问题为标准型，问题为标准型，确定一个初始基可行解确定一个初始基可行解检验解的检验解的最优性最优性终了终了Y旋转运算枢轴运算）旋转运算枢轴运算）确定另一个基可行解确定另一个基可行解N基本思路：化基本思路：化LP问题为标准型，从

24、可行域问题为标准型，从可行域的某个基可行解一个顶点开场，转换到另一的某个基可行解一个顶点开场，转换到另一个基可行解另一个顶点），并使目标函数值得个基可行解另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代逼近法。其实质是逐步迭代逼近法。二、基本原理举例二、基本原理举例 ) 4() 5 , 1( 0) 3(124) 2(164) 1 (82) 0(00032max524132154321jxxxxxxxxxxxxxZj以以典典型型示示例例为为例例：1. 初始基可行解的确定初始基可行解的确定要得到一个初始基可行解，必须找到

25、一个初始可行基。要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，由于典型示例标准化后，x3、x4、x5的系数列向量构成单的系数列向量构成单位矩阵，该矩阵位矩阵，该矩阵B0是一个基，并且是一个可行基可以证是一个基，并且是一个可行基可以证明，标准化后的单位矩阵一定是可行基）。明，标准化后的单位矩阵一定是可行基）。) 6(320412) 5(41628212514213xxZxxxxxxx 令非基变量令非基变量x10、x2 0，得到基可行解及相应的目标，得到基可行解及相应的目标函数值，函数值，X(0) (0,0,8,16,12)T， Z(0) 0。结论：结论： （1在标准化的在

26、标准化的LP问题的约束系数矩阵中，只要存在单问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；位矩阵，就可求得初始基可行解； （2基变量确定后，目标函数和基变量均可表示成非基基变量确定后，目标函数和基变量均可表示成非基变量的代数和形式如变量的代数和形式如(6)和和(5)），从而便于求出基可行解及），从而便于求出基可行解及相应的目标函数值。相应的目标函数值。2. 最优性检验最优性检验 考察变换后的目标函数考察变换后的目标函数(6)式，非基变量式，非基变量x1、x2的系数都的系数都为正数，若让为正数，若让x1、x2取正值，则目标函数值会增大。因此，取正值，则目标函数值会增大。因此，应将

27、非基变量应将非基变量x1、x2变换成基变量。变换成基变量。结论：结论： 在非基变量的代数和形式表示的目标函数中，若非基变在非基变量的代数和形式表示的目标函数中，若非基变量的系数称为检验数为正，则目标函数值还有增加的可量的系数称为检验数为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。能，表明当前的基可行解不是最优解。3. 确定新的基可行解基变换）确定新的基可行解基变换） 单纯形法在寻找新的可行基时，是以当前的可行基为基础单纯形法在寻找新的可行基时，是以当前的可行基为基础的，即把当前的可行基中某一列用非基向量替换，从而形成的，即把当前的可行基中某一列用非基向量替换，从而形成新的可行

28、基。新的可行基。确定换入变量：一般选择正系数最大的非基变量为换入变量。确定换入变量：一般选择正系数最大的非基变量为换入变量。 本例为非基变量本例为非基变量x2。确定换出变量：其依据是确定换出变量：其依据是a保证换出的变量取值为保证换出的变量取值为0，变，变 成非基量；（成非基量；（b其它的变量取值为非负。其它的变量取值为非负。4120412) 7(016280282254223 xxxxxxx 当确定当确定x2为换入变量后，为换入变量后， x1还是非基变量，故还是非基变量，故 x10。现。现在要保证在要保证x3、x4、x50，即，即(5)当当 x2 min8/2，12/4） =3 （最小比值规

29、则）（最小比值规则）可保证可保证 x5 =0则则x5为换出变量。为换出变量。新的基变量为新的基变量为x3、x4、x2 ，新的可行基为，新的可行基为B1(P3, P4 , P2)4. 旋转迭代旋转迭代 基变量确定后，旋转迭代就是把目标函数和基变量均表基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量示成非基变量x1、x5的代数和形式。可用高斯消去法实现。的代数和形式。可用高斯消去法实现。) 9(4329413) 8(416212515214513xxZxxxxxxx 令非基变量令非基变量x10、x5 0，得到新的基可行解及相应的，得到新的基可行解及相应的目标函数值，目标函数值，X(1)

30、 (0,3,2,16,0)T， Z(1) 9。返回至第二步，。返回至第二步，直至求出最优解。直至求出最优解。 将上述方程组求解过程，用列表形式表达，即为线性规划将上述方程组求解过程，用列表形式表达，即为线性规划单纯形法。单纯形法。三、最优性检验及解的判别三、最优性检验及解的判别1. 检验数公式检验数公式代代入入目目标标函函数数将将数数和和形形式式：可可表表示示成成非非基基变变量量的的代代变变量量个个变变量量为为基基变变量量，则则基基程程中中，前前不不失失一一般般性性，设设迭迭代代过过)1()1(), 2 , 1(1mixabxxmjnmjijiii 课堂作业课堂作业2： 请给出教科书请给出教科

31、书p23 公式公式1-25的推导过程。的推导过程。)2()()()1()1(), 2 , 1(11111111111111 mijnmjmiijijiinmjjjmimijnmjijiiinmjjjmijnmjijiinmjjjmiiinjjjjnmjijiixaccbcxcxacbcxcxabcxcxcxcZmixabx代代入入目目标标函函数数将将力力，故故称称其其为为检检验验数数。问问题题是是否否达达到到最最优优的的能能具具有有判判别别由由于于可可进进一一步步简简化化成成：则则再再令令数数和和形形式式。可可表表示示成成非非基基变变量量的的代代表表明明目目标标函函数数可可写写成成：令令LP)

32、4()3()3()3()()2(, 1,1010110jjnmjjjjjjjnmjjmimiijijiixZZZcZxZcZZnmjacZbcZ 2. 最优性检验与解的判别最优性检验与解的判别 设设X(0)=(b1, b2, ,bm,0, ,0)T为对应于基为对应于基B的一个的一个基可行解。基可行解。对于最大化问题，最优性检验与解的判别如下：对于最大化问题，最优性检验与解的判别如下：（1唯一最优解唯一最优解 对于一切对于一切 j=m+1, ,n，有，有 j0，则，则X(0)为唯一最优解。为唯一最优解。（2无穷多最优解无穷多最优解 对于一切对于一切 j=m+1, ,n，有，有 j0，且至少有一个

33、，且至少有一个 m+k=0，则该则该LP问题有无穷多最优解，问题有无穷多最优解，X(0)为其中之一。为其中之一。（3无界解无界解 在在 j=m+1, ,n中，至少有一个中，至少有一个 m+k0，且对，且对i=1, ,m，有有ai,m+k0，则该，则该LP问题具有无界解。问题具有无界解。四、基变换四、基变换1. 换入变量的确定换入变量的确定2. 换出变量的确定换出变量的确定则第则第l个约方程对应的基变量个约方程对应的基变量xl为换出变量。为换出变量。),2, 1(0minmiabaablklikikiil 若若 为为换换入入变变量量所所对对应应变变量量，选选取取若若kkjjjkx 0|max 五

34、、迭代运算五、迭代运算系系数数为为主主元元素素的的以以中中的的基基变变量量为为中中的的基基变变量量，为为设设例例：133221121)1()2()1(6102332)2()1(xxxxxxxxx 为为主主元元素素系系数数的的以以2/3)4()4()3(9520233223221112/ )1( ,)1()2(23xxxxxxx 60803342133521)4( , 3)4()3(32xxxxxx第三节第三节 单纯型法的步骤单纯型法的步骤1. 化化LP问题为标准型问题为标准型,建立初始单纯型表建立初始单纯型表;步步；则则，转转第第，则则最最优优解解已已达达到到，否否若若所所有有检检验验数数30

35、. 2 )(. 3基基变变换换确确定定换换入入和和换换出出变变量量步步。转转第第为为主主元元素素进进行行旋旋转转迭迭代代以以2,. 4lka一、步骤一、步骤 为为换换入入变变量量；对对应应的的非非基基变变量量，选选取取按按kkjjjkx 0|max ;0|min为为换换出出变变量量对对应应的的基基变变量量，选选取取计计算算lllklikikiilxabaab 0,121684243221221121xxxxxxxxMaxZ化为标准型化为标准型 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj二、实例二、实例单纯型表算法单纯型表算法

36、X(0) (0,0,8,16,12)T O点点以以1为主元素进行旋转运算，为主元素进行旋转运算，x1为换入变量，为换入变量， x3为换出变为换出变量量cj 2 3 0 0 0 iCBXB b x1 x2 x3 x4 x50 x3 0 x4 j x1 cj x2 x3 x4 x5 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1 2 3 0 0 0 b816 12 XB x3 x4 x5 CB 0 0 0以以4为主元素进行旋转运算，为主元素进行旋转运算，x2为换入变量，为换入变量，x5为换出变为换出变量量 j 2 3 0 0 0 i 8/2 12/44 miijijjacc1 x2 3

37、主元列主元列主元行主元行 0 0 0 1/43 1 4 0 1 016 0 0 1 1 0 -1/22X(1) (0,3,2,16,0)T Q4点点 2 0 0 -3/4 016/4 2/1 1此时达到最优解。此时达到最优解。X*=(4,2), max Z=14。cj 2 3 0 0 0 iCBXB b x1 x2 x3 x4 x5 0 x4 3 x2 j cj 2 3 0 0 0 iCBXB b x1 x2 x3 x4 x52 x1 3x2 j 0 0 0 1/43 10 -2 0 1/4 0 x1 2 0 1 1 0 -1/22 2 0-4 128 08/2 12 x50 0 -2 1/2

38、 14 0 1 0 1/4 04 0 1/2 -1/8 0 02 10 -3/2 -1/8 0 0X(3) (4,2,0,0,4)T Q2点点X(2) (2,3,0,8,0)T Q3点点以以2为主元素进行旋转运算，为主元素进行旋转运算，x5为换入变量，为换入变量，x4为换出变为换出变量量一、最小化问题最优界判别一、最小化问题最优界判别第四节第四节 LP问题的进一步讨论问题的进一步讨论 前面讨论的前面讨论的LP问题都是以最大化目标函数作为标准型的，问题都是以最大化目标函数作为标准型的，但也有用最小化目标函数作为但也有用最小化目标函数作为LP问题标准型的构成要素的情问题标准型的构成要素的情况。二者

39、的区别如下：况。二者的区别如下：标准型标准型 比较条目比较条目 max Z=CX AX=b，X 0 min Z=CX AX=b，X 0最优解的最优解的 j 0 0 换入变量换入变量xkmax j| j 0min j| j 0换出变量换出变量xl按最小比值规则按最小比值规则 0.maxXbAXtsCXZ 0,. .maxSSXXbIXAXtsCXZ二、人工变量法二、人工变量法化为标准型化为标准型 化标准型时，若找不到单位矩阵，可人为添加非负变化标准型时，若找不到单位矩阵，可人为添加非负变量人工变量凑成单位矩阵。量人工变量凑成单位矩阵。 因人工变量是虚拟的变量，无任何物理意义，它们的因人工变量是虚

40、拟的变量，无任何物理意义，它们的取值最终必须为零，才能保证约束方程不发生变化。取值最终必须为零，才能保证约束方程不发生变化。 为此，必须把人工变量从基变量中替换出去而变成非为此，必须把人工变量从基变量中替换出去而变成非基变量，则基变量，则LP问题有解；若最优解中含有人工变量，则问题有解；若最优解中含有人工变量，则LP问题无可行解。这是问题无可行解。这是LP问题无解的判别条件。问题无解的判别条件。 0,12324112.3min32131321321321xxxxxxxxxxxtsxxxZ例例： 7, 2 , 1; 012324112.00003min7316532143217654321jxx

41、xxxxxxxxxxxtsxxxxxxxZj加入松弛变量加入松弛变量x4;剩余变量剩余变量x5;人工人工变量变量x6,x7（1） 基本思路基本思路（2目标函数的处理目标函数的处理 iiiVMCXZVMVMCXZmin)(max为为人人工工变变量量，为为（3） 计算计算1. 大大M法法(M为任意大的正数为任意大的正数) 7, 2 , 1; 012324112.003min7316532143217654321jxxxxxxxxxxxxxtsxMxMxxxxxZjcj-31100MMCBXBbx1x2x3x4x5x6x70 x4111-21100011Mx63-4120-1103/2Mx71-20

42、100011-3+6M1-M1-3M0M000 x4103-20100-1-Mx610100-11-211x31-2010001-11-M00M03M-1i j j 结果得结果得: X*=(4,1,9,0,0) T Z*=-2cj-31100MMCBXBbx1x2x3x4x5x6x70 x4123001-22-541x210100-11-2-1x31-2010001-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3M-2/3j i j 即即认认为为达达到到了了最最优优解解。所所有有

43、检检验验数数此此时时,0, j（接上表）（接上表）将将LP问题分成两个阶段来考虑问题分成两个阶段来考虑 第第I 阶段阶段: 不考虑原问题是否存在可行解，给原不考虑原问题是否存在可行解，给原LP问题问题加入人工变量，并构造仅含人工变量的目标函数和要求最加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯型法求解，若得小化；然后用单纯型法求解，若得W=0，则进行第二阶段，则进行第二阶段计算，否则无可行解。计算，否则无可行解。 第第II 阶段：将第一阶段得到的最终表除去人工变量，将阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初目标函数行的

44、系数换为原问题的系数，作为第二阶段的初始表。始表。2. 两阶段法两阶段法 0,12324112.3min32131321321321xxxxxxxxxxxtsxxxZ例例：加入松弛变量加入松弛变量x4;剩余变量剩余变量x5;人工人工变量变量x6,x7 7, 2 , 1; 012324112.)(min73165321432176jxxxxxxxxxxxxxtsIxxWj用单纯形法求解第一阶段的结果得：用单纯形法求解第一阶段的结果得：cj0000011CBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-201000116-1-30100

45、0 x4103-20100-1-1x610100-11-210 x31-2010001-0-1001030 x4123001-22-540 x210100-11-2-0 x31-2010000-0000011i j j j 此时，达到第一阶段的最优解，此时，达到第一阶段的最优解，W=0cj-31100CBXBbx1x2x3x4x50 x4123001-241x210100-1-1x31-20100-10001-3x141001/3-2/31x210100-11x390012/3-4/30001/31/3i j 由于人工变量由于人工变量x6 =x7=0,所以所以0,1,1,12,0T是该线性规划

46、问题的基可行解。于是转入第二阶段运算：是该线性规划问题的基可行解。于是转入第二阶段运算：此时达到该此时达到该LP问题的最优解：问题的最优解： X*=(4,1,9,0,0) T; 目标函数值目标函数值Z*=-2。j 三、单纯型法中存在的问题三、单纯型法中存在的问题1. 存在两个以上的最大正检验数。选择存在两个以上的最大正检验数。选择任何变量对应最大正检验数作为换任何变量对应最大正检验数作为换入变量。入变量。2. 最小比值相同。最小比值相同。LP问题出现退化现象，即基变量取值为问题出现退化现象，即基变量取值为0 0,10321122109841.6212043max4321343214321432

47、1xxxxxxxxxxxxxtsxxxxZ例例： 7 , 2 , 1;010321122109841.0006212043max7364321543217654321jxxxxxxxxxxxxxtsxxxxxxxZjcj 3/4 -20 1/2 -6 0 0 0 CBXBbx1x2x3x4x5x6x70 x501/4-8-191000 x601/2-12-1/230100 x71001000103/4-201/2-6000j cj 3/4 -20 1/2 -6 0 0 0 CBXBbx1x2x3x4x5x6x73/4x101-32-4364000 x60043/2-150100 x710010

48、0010047/221-300j 选取选取x1为换入变量；按为换入变量；按Bland算法，算法，选取下标最小的选取下标最小的x5为换出变量，得下表：为换出变量，得下表：此时换出变量为此时换出变量为x1，换入变量为，换入变量为x4，迭代后，迭代后目标函数值不变，继而出现了循环现象，达目标函数值不变，继而出现了循环现象，达不到最优解。不到最优解。解决退化的方法有：解决退化的方法有：“摄动法摄动法”、“辞典序法辞典序法”、 Bland规则等规则等1974年年Bland提出提出Bland算法规则：算法规则：为为换换出出变变量量。选选取取下下标标最最小小的的基基变变量量个个以以上上的的最最小小比比值值时

49、时，规规则则计计算算存存在在两两个个和和两两当当按按）（量量。所所对对应应的的变变量量为为换换入入变变则则选选取取 2,0|min)1(kjjk 3. 最小比值原则失效最小比值原则失效问问题题有有无无界界解解。则则此此对对应应列列向向量量，而而存存在在某某问问题题迭迭代代到到某某步步时时，当当用用单单纯纯型型法法求求解解LP, 00LP kkka 4 , 3 , 2 , 1; 0432.32max42132121jxxxxxxxtsxxZj例例：cj2300CBXBbx1x2x3x40 x36-20113x24-3101cj-Zj-121100-3经过一次迭代后可得右表经过一次迭代后可得右表

50、ZZZmiabxxxaxZZZmixabxxkkikiijkikkjnmjjjnmjijiii 当当此此时时则则其其余余非非基基变变量量非非基基变变量量令令行行解解），即即新新的的可可行行解解（不不是是基基可可其其时时可可构构造造一一个个且且其其非非基基变变量量的的若若代代数数和和形形式式：也也可可表表示示成成非非基基变变量量的的目目标标函函数数数数和和形形式式：可可表表示示成成非非基基变变量量的的代代基基变变量量中中，一一般般情情况况下下，迭迭代代过过程程说说明明：0), 2 , 1(00, 0, 0, 0), 2 , 1(01014. 在最优表中出现某在最优表中出现某非基变量检验数为非基变

51、量检验数为0 0,36431228.43max21212121xxxxxxtsxxZ例：例：CBXBbx1x2x3x4x50 x340012/3-1/34x260101/203x14100-2/31/3cj-Zj-360000-10 x46003/21-1/24x2301-3/401/43x1810100cj-Zj-360000-1cj-Zj0340001 ,0;)1(*)2()1(* XXX)0 , 0 , 4 , 6 , 4(*)1( X)0 ,6 ,0 ,3 ,8(*)2( X结论：若线性规划问题存在某非基变量检验数为结论：若线性规划问题存在某非基变量检验数为0,而其对而其对应列向量应列

52、向量Pk0,仍可判断线性规划问题有无穷多最优解。仍可判断线性规划问题有无穷多最优解。式中的式中的X* 是否能全部由单纯形法求得？是否能全部由单纯形法求得？ 1 ,0;)1(*)2()1(* XXX 课堂作业课堂作业3 第五节第五节 应用举例应用举例应用应用1：下料问题书：下料问题书P38 例例10） 现要做现要做100套钢架，每套需套钢架，每套需2.9米、米、2.1米米和和1.5米的圆钢各一根。已知原料长米的圆钢各一根。已知原料长7.4米，米，问如何下料，使用的原料最少余料最少或问如何下料，使用的原料最少余料最少或根数最少）？根数最少）？分析：分析： 最简单的做法是：每根最简单的做法是：每根7

53、.4米长的原材料各截取三种规格米长的原材料各截取三种规格的元钢一根，则料头为的元钢一根，则料头为0.9米，米，100套则浪费材料套则浪费材料90米。关键是米。关键是要设计套裁方案，不能有遗漏。要设计套裁方案，不能有遗漏。解：设解：设 x1, x2 , x3, x4 , x5分别代表五种不同的原料用量方案。分别代表五种不同的原料用量方案。方案方案2.9米米2.1米米1.5米米合计合计余料余料x11037.40 x22017.30.1x30227.20.2x41207.10.3x50136.60.8 0,100)(323100)(22100)(2.8 . 03 . 02 . 01 . 00:543

54、21532154342154321xxxxxxxxxxxxxxxtsxxxxxMinZOBJ余料最少的余料最少的LP模型：模型：根数最少的根数最少的LP模型：模型：料头最省料头最省根数最少根数最少= =解解1：x1=30，x2=10， x4=50； 料头料头Z=16，根数，根数90。与解与解1相同相同解解2: x1=100，x3=50； 料头料头Z=10，根数，根数150。与解与解1相同相同 0,100)(323100)(22100)(2.:54321532154342154321xxxxxxxxxxxxxxxtsxxxxxMinZOBJ应用应用2：配料问题书：配料问题书P38 例例11） 某

55、工厂要用三种原材料某工厂要用三种原材料C、P、H混合调混合调配出三种不同规格的产品配出三种不同规格的产品A、B、C。已知产。已知产品的规格要求、单价和原材料的供应量、单品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？价。该厂应如何安排生产使利润最大？产品名称产品名称规格要求规格要求单价单价(元元/kg）A原材料原材料C不少于不少于50%原材料原材料P不超过不超过25%50B原材料原材料C不少于不少于25%原材料原材料P不超过不超过50%35D不限不限25原材料名称原材料名称每天最多供每天最多供应量应量(kg)单价单价(元元/kg)C10065P10025H6035限限量

56、量、含含量量、变变量量约约束束条条件件有有三三类类：原原料料、的的含含量量为为、中中、的的含含量量为为、中中、的的含含量量为为、中中设设333231232221131211xxxHPCDxxxHPCBxxxHPCA解：根据题意，可将问题简化成如下表格形式：解：根据题意，可将问题简化成如下表格形式：产品名称产品名称原料原料规格要求规格要求/决策变量决策变量原料限量原料限量(kg）单价单价(元元/kg）ABDC 50%/x11 25%/x21/ x3110065P 25%/ x12 50%/ x22/ x3210025H/ x13/ x23/ x336035产品单价产品单价(元元/kg）50352

57、5 用单纯型法计算得结果：每天只生产用单纯型法计算得结果：每天只生产A产品产品200kg。分别需要原料：分别需要原料：C为为100kg；P为为50kg；H为为50kg。 总利润收入总利润收入Z=500元元/天天.3 , 2 , 1,; 0%50%5060%25100%25100.13121111232221223323132322212132221213121113312111 jixxxxxxxxxxxxxxxxxxxxxxxxxxtsij3332312322211312113323133222123121113332312322211312111004001030152515)(35)(2

58、5)(65)(25)(35)(50 xxxxxxxxxxxxxxxxxxxxxxxxxxxMaxZ 例例1：某企业拟用：某企业拟用m种资源种资源(i=1,2,m)生产生产n种产品种产品(j=1,2,n) 。已知第。已知第i种资源的数量种资源的数量为为bi，其单价为，其单价为Pi；第；第j种单位产品的产值为种单位产品的产值为Vj，消耗第，消耗第i种资源的数量为种资源的数量为aij，合同量为，合同量为ej，最高需求为最高需求为dj。问企业应如何拟定生产计划？。问企业应如何拟定生产计划？解：根据题意，设解：根据题意，设xj (j=1,2,n)为第为第j种产品的生产量。种产品的生产量。应用应用3：生产

59、计划问题：生产计划问题 njijijjjjjnjjjnjjmiijijnjjijmiinjjjmibxanjdxnjextsxcxaPVxaPxVZZZ111111121),2,1(),2,1(),2,1(.)(max例例2 （书（书P41 例例12）市场要求：市场要求： 1) 产品数量和品种；产品数量和品种； 2) 产品交货期不同。产品交货期不同。生产要求：生产要求： 1) 设备均衡且满负荷生产；设备均衡且满负荷生产； 2) 生产技术准备需要时间。生产技术准备需要时间。底底前前完完成成全全年年计计划划。种种产产品品要要求求二二月月第第两两种种产产品品下下半半年年投投产产，、假假设设第第种种产

60、产品品的的数数量量月月内内计计划划生生产产表表示示；台台时时类类设设备备的的生生产产能能力力月月内内第第表表示示类类设设备备的的台台时时数数类类产产品品需需要要的的第第表表示示加加工工单单位位类类产产品品全全年年的的计计划划量量表表示示第第种种产产品品表表示示工工厂厂生生产产的的第第类类设设备备表表示示工工厂厂的的第第设设：48512, 2 , 1)(), 2 , 1(), 2 , 1(jkxkikbijajdnjjjmiiijkikijj 种种产产品品全全年年的的产产量量为为第第一一月月份份：jdxnjdxmibxaxxtsbxaZjjjjinjjijmiiminjjij;0);, 2 ,