chapter 2.32.4 线性规划问题的解的概念

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,上页,下页,返回,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,上页,下页,返回,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,上页,下页,返回,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,上页,下页,返回,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,上页,下页,返回,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,2.3,线性规划问题 解的概念,1,一、,LP,问题的各种解,可行解,：,满足约束条件和非负条件的决策变量的一组取值。,全部可行解的集合称为可行域。,最优解,：使目标函数达到最优值的可行解。,对应的目标函数值称为最优值。,2,3.,基,:,设,A,mn,(nm),为约束方程组的系数矩阵，其秩为,m,。,B,mm,是矩阵,A,中的一个,mm,阶的满秩子矩阵,，,则称,B,是线性规划问题的一个基（基矩阵）,。,设,B=,（,a,ij,）,mm,中的每一个列向量,P,j,(j=1,2,m),为,基向量,。与基向量,P,j,对应的变量,x,j,称为,基变量,，其他的变量称为,非基变量,。,3,基：若,B,是矩阵,A,中,mm,阶非奇异子矩阵（,B0），,则,B,是线性规划问题的一个基。不妨设：,j=1,2,m,基向量。, j=1,2,m,基变量。,j=m+1,n,非基变量。,线性规划问题解的概念,4.,基解,：,设,AX=b,是含,n,个决策变量、,m,个约束条件的,LP,的约束方程组，,B,是,LP,问题的一个基，若令不与,B,的列相应的,n-m,个分量（非基变量）都等于零，所得的方程组的解称为,方程组,AX=b,关于基,B,的基本解,，简称为,LP,的基本解,。,5,5.,基可行解,：满足非负条件的基解。,6.,可行基：,对应基可行解的基称为可行基,.,7.,退化解：,若基解,X,B,中至少有一个分量为零，称为退化解。,由此可知，退化基可行解中的非零分量一定小于,m,个,非退化解中非零分量一定等于,m,个。,6,线性规划解的关系图,非可行解,可行解,基可行解,基解,线性规划问题解的概念,例,2.6,求出下列线性规划问题的一个基、,基变量、基解、基可行解和可行基。,x,1,+x,2,+x,3,3,x,1,+4x,2,+5x,3,9,2x,1,x,2,x,3,1,x,1,x,2,x,3, 0,s.t,max Z = x,1,+2x,2,+3x,3,8,解：化为标准形式为,x,1,+ x,2,+ x,3,+ x,4,=3,x,1,+4x,2,+5x,3,+x,5,=9,2x,1,x,2,x,3,+x,6,=1,x,1,x,2,x,3,x,4,x,5,x,6, 0,s.t,max Z = x,1,+2x,2,+3x,3,+0x,4,+0x,5,+0x,6,9,由此，约束方程的系数矩阵为,;,;,;,10,矩阵秩不超过,3,，而,是一个,的满秩阵，故,是一个基,，,x,4,x,5,x,6,是基变量,，,x,1,x,2,x,3,是非基变量。,11,令,非基变量,x,1,x,2,x,3,为零,则,X,是一个,基解,。,是一个,可行基,。,因该,基解中所有变量取值为非负,，故又是基可行解，对应的基,12,2.4,线性规划的图解法,解的几何表示,13,1,什么是图解法？,线性规划的图解法就是用,几何作图,的方法,分析并求出其最优解,的过程。,求解的思路是：,先,将约束条件加以图解，求得满足约束条件的解的集合（即可行域）,，,然后,结合目标函数的要求从可行域中找出最优解。,14,例,2.7,的数学模型,目标函数,Max,Z,= 2,x,1,+ 3,x,2,约束条件,3,x,1,+ 6,x,2,24,2,x,1,+,x,2,10,x,1、,x,2, 0,x,1,x,2,10,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ,0,|,123456789,x,1,x,2,3x,1,+ 6,x,2,24,(0, 4),(8, 0),目标函数,Max,Z,= 2,x,1,+ 3,x,2,约束条件,3,x,1,+ 6,x,2,24,2,x,1,+,x,2,10,x,1、,x,2, 0,2,x,1,+,x,2,10,x,2,|,123456789,x,1,x,1,+ 2,x,2,8,图解法,2,x,1,+,x,2,10,10,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ,0,可行域,B,C,A,D,目标函数,Max,Z,= 2,x,1,+ 3,x,2,约束条件,3,x,1,+ 6,x,2,24,2,x,1,+,x,2,10,x,1、,x,2, 0,x,2,|,123456789,x,1,x,1,+ 2,x,2,8,图解法,2,x,1,+,x,2,10,10,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ,0,可行域,B,C,A,D,目标函数,Max,Z,= 2,x,1,+ 3,x,2,约束条件,3,x,1,+ 6,x,2,24,2,x,1,+,x,2,10,x,1、,x,2, 0,2,x,1,+ 3,x,2,= 6,x,2,|,123456789,x,1,x,1,+ 2,x,2,8,图解法,2,x,1,+,x,2,10,10,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ,0,B,C,A,D,目标函数,Max,Z,= 2,x,1,+ 3,x,2,约束条件,3,x,1,+ 6,x,2,24,2,x,1,+,x,2,10,x,1、,x,2, 0,3,x,1,+ 6,x,2,= 24,2,x,1,+,x,2,= 10,最优解 (4, 2),图解法求解步骤,由全部约束条件作图求出可行域；,作目标函数等值线，确定使目标函数最优的移动方向；,平移目标函数的等值线，找出最优点，算出最优值。,线性规划问题求解的 几种可能结果,(,a),唯一,最优解,x,2,6 ,5 ,4 ,3 ,2 ,1 ,0,|,123456789,x,1,(,b),无穷多,最优解,22,该线性规划的可行域为上图中四边形,OAED,（即阴影区,），虚线为目标函数等值线，箭头为目标函数值,递增的方向,。沿着箭头的方向平移目标函数等值线，发现,平移的最终,结果是目标函数等值线将与可行域的一条边界,线段,AE,重合，这个结果表明，该线性规划有,无穷多个最优解,线段,AE,上的所有点都是最优点，它们都使目标函数,取得相同的最大值,Zmax=3,。,(1/3)X,1,+(4/3)X,2,=3,(1/3)X,1,+(1/3)X,2,=1,A,B,C,D,1,2,3,4,5,6,7,8,9,1,2,3,4,5,X,1,X,2,0,23,(,c),无界解,Max,Z,=,x,1,+,x,2,-2,x,1,+,x,2,4,x,1,-,x,2,2,x,1、,x,2, 0,x,2,x,1,本例中的可行域是一个无界区域，,如图中阴影区所示。虚线为目函数,等值线，沿着箭头所指的方向平移可,以使目标函数值无限制地增大，因此,找不到最优解。这种情况通常称为,无“有限最优解”,或,“最优解无界,”,。,(,d),无可行解,Max,Z,= 2,x,1,+ 3,x,2,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,-2,x,1,+,x,2,4,x,1、,x,2, 0,可行域为空集,图解法的几点结论:,（由图解法得到的启示）,可行域是有界或无界的凸多边形。,若线性规划问题存在最优解，它一定可以在可行域的顶点得到。,若两个顶点同时得到最优解，则其连线上的所有点都是最优解。,解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,练习：,用图解法求解,LP,问题,Max,Z,= 34,x,1,+ 40,x,2,4,x,1,+ 6,x,2,48,2,x,1,+ 2,x,2,18,2,x,1,+,x,2,16,x,1、,x,2, 0,18 ,16 ,14 ,12 ,10 ,8 ,6 ,4 ,2 ,0,|,24681012141618,x,1,x,2,4,x,1,+ 6,x,2,48,2,x,1,+ 2,x,2,18,2,x,1,+,x,2,16,图解法 （练习）,18 ,16 ,14 ,12 ,10 ,8 ,6 ,4 ,2 ,0,|,24681012141618,x,1,x,2,4,x,1,+ 6,x,2,48,2,x,1,+ 2,x,2,18,2,x,1,+,x,2,16,可行域,A,B,C,D,E,图解法 （练习）,18 ,16 ,14 ,12 ,10 ,8 ,6 ,4 ,2 ,0,|,24681012141618,x,1,x,2,4,x,1,+ 6,x,2,48,2,x,1,+ 2,x,2,18,2,x,1,+,x,2,16,A,B,C,D,E,(8,0),(0,6.8),34,x,1,+ 40,x,2,= 272,图解法 （练习）,18 ,16 ,14 ,12 ,10 ,8 ,6 ,4 ,2 ,0,|,24681012141618,x,1,x,2,4,x,1,+ 6,x,2,48,2,x,1,+ 2,x,2,18,2,x,1,+,x,2,16,A,B,C,D,E,(8,0),(0,6.8),图解法 （练习）,x,2,18 ,16 ,14 ,12 ,10 ,8 ,6 ,4 ,2 ,0,|,24681012141618,x,1,4,x,1,+ 6,x,2,48,2,x,1,+ 2,x,2,18,2,x,1,+,x,2,16,A,B,C,D,E,(8,0),(0,6.8),最优解 (3,6),4,x,1,+ 6,x,2,=48,2,x,1,+ 2,x,2,=18,用图解法解线性规划,33,结 论,从上面用图解法求解案例的过程中明显感觉到对具有三个决策变量的线性规划进行图解就麻烦得多了。因此，尽管图解法具有简单、直观的优点，但它的使用是有局限性的，,对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法,，大多数情况下,仅对含有两个决策变量的线性规划才使用图解法求解,，而对含有三个及三个以上决策变量的线性规划则应考虑使用更加有效的,通用算法单纯形法,来进行求解，这将在,2.5,节加以介绍。,34,课堂练习：,对下列线性规划问题，并用图解法求最优解 。,35,讨论：如何求得基解？,第一步,模型标准化,；,第二步,按照基本解的定义,找基（非退化,3,阶方阵）,多少个？不超过 ，为什麽？怎麽找？,确定基变量和非基变量；,令非基变量为,0,，解出基变量,36,求解结果：,H,(6,4,-6,0,0),T,C(3,1,0,3,0),T,B(2,2,0,0,2),T,D(2,0,2,4,0),T,F,(,-2,0,6,0,4),T,I,(4,0,0,6,-2,),T,E,(0,-2,6,6,0),T,A(0,1,3,0,3),T,G,(0,4,0,-8,6),T,O(0,0,4,2,2),T,;,37,1,2,3,4,5,6,4,3,2,1,5,O,X,2,X,1,X,1,-x,2,=2,-x,1,+2x,2,=2,x,1,+x,2,=4,B,C,F,A,D,Z=0,Z=10,Z=14,38,第,三,步,求得的基本解和图解法对照，找出相应的点；,结论：,(1),基解对应所有可行域边界及其延长线、坐标轴之间的交点；,(2),基可行解对应可行域的顶点。,39,作业：,P55,4.,（,1,）,-,（,4,）,40,