Chapter1线性规划及其单纯形法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,运筹学教程,第一章 线性规划及单纯形法,1-1,线性规划问题及其数学模型,1-2,图解法,1-3,单纯形法原理,1-4,单纯形法计算步骤,1-5,单纯形法的进一步讨论,引 言,线性规划是运筹学的重要分支，也是运筹学中最基本的内容。早在,1939,年，前苏联著名数学家康特洛维奇研究了运输和下料等问题，编著了,生产组织和计划中的数学方法,一书，为线性规划的研究奠定了基础。,1947,年,Dantgig,提出了一般线性规划的算法,单纯形法。尔后,Kuhn,提出了线性规划的对偶理论，使线性规划的理论和方法日趋完善成熟。,随着电子计算机的产生与发展，线性规划在工业、农业、商业、交通运输业、建筑业、军事等行业的计划和管理及决策分析中得到了广泛与深入的应用，取得了良好的效果。目前，线性规划正以它具有理论成熟，计算简单精确，适应性强，应用面广的特点引起了工程技术人员、管理人员和经济学者的重视。它已成为重要的优化技术和手段。,4/28/2026,2,一、线性规划问题的数学模型,在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优，这就是规划方法。,例,1,美佳公司计划制造,、,两种家电产品。已知各制造一件时分别占用的设备,A,、,B,的,台时、调试时间、调试工序每天可用于这两种家电的能力、各售出一件时的获利情况，如表,1-1,所示。问该公司应制造两种家电产品各多少件，使获取的利润为最大？,1-1,线性规划问题及其数学模型,返回第一章目录,4/28/2026,3,1-1,线性规划问题及其数学模型,用数学语言来描述这个问题。假设美佳公司每天制造,、,两种家电产品的数量分别是,x,1,和,x,2,件,。,max,约束条件,目标函数,Z2x,1,x,2,5x,2,15,6x,1,2x,2,24,x,1,x,2,5,x,1,，x,2,0,这就是例,1,的数学模型,4/28/2026,4,运筹学基础及应用,第一章例,2,【,例,2】,某企业计划生产,I,、,两种产品。这两种产品都要分别在,A,、,B,、,C,、,D,四种不同设备上加工。按工艺资料规定，生产每件产品,I,需占用各设备分别为,2,、,1,、,4,、,0,小时，生产每件产品,B,，需占用各设备分别为,2,、,2,、,0,、,4,小时。已知设备计划期内用于生产这两种产品的能力分别为,12,、,8,、,16,、,12,小时，又知每生产一件产品,I,企业能获得,2,元利润、每生产一件产品,企业能获得,3,元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大？,4/28/2026,5,产品,资源,产品,产品,生产能力（,h,）,设备,A,（,h,）,2,2,12,设备,B,（,h,）,1,2,8,设备,B,（,h,）,4,0,16,设备,B,（,h,）,0,4,12,利润（元,/,件）,2,3,假设：,计划期内生产,产品,x,1,件，,产品,x,2,件。,4/28/2026,6,例2,捷运公司拟在下一年度的,1,4,月份的,4,个月内租用仓库堆放物资。已知各月份所需仓库面积数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如表,1-2,所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签定租借合同的最优决策，目的是使所付租借费用最小。,4/28/2026,7,假设用,x,ij,表示捷运公司第,i,（,i,1,，,2,，,，,4,）,个月月初签订租借期为,j,（,j,1,，,2,，,，,4,）,个月的仓库面积数,(,单位为,100m,2,）。则,min z2800(x,11,+x,21,+x,31,+x,41,)+4500(x,12,+x,22,+x,32,)+6000(x,13,+x,23,)+7300 x,14,x,11,+x,12,+x,13,+x,14,15,x,12,+x,13,+x,14,+x,21,+x,22,+x,23,10,x,13,+x,14,+x,22,+x,23,+x,31,+x,32,20,x,14,+x,23,+x,32,+x,41,12,x,ij,0 (i1，2，4；j1，2，4）,租借期为一个月的仓库面积,租借期为二个月的仓库面积,租借期为三个月的仓库面积,租借期为四个月的仓库面积,一月份拥有的租借面积,二月份拥有的租借面积,三月份拥有的租借面积,四月份拥有的租借面积,一月份仓库需求面积约束,二月份仓库需求面积约束,三月份仓库需求面积约束,四月份仓库需求面积约束,非负约束,4/28/2026,8,组成线性规划模型的三个要素,max Z2x,1,x,2,5x,2,15,6x,1,2x,2,24,x,1,x,2,5,x,1,，x,2,0,目标函数,：,约束条件,（,1,）变量（决策变量）,:,它是规划中要确定的未知量，是用数量方式来表示的方案或措施，可由决策者决定和控制。,（,2,）目标函数：,它是决策变量的函数，是决策者在一定的限制条件下希望得到的结果。,（,3,）约束条件：,指决策变量取值时受到的各种资源条件的限制，通常用等式或不等式来表达。,其中，,x,ij,0,叫做非负约束。,由于目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，所以此类模型称为线性规划的数学模型。,实际问题中，线性的含义有二：,一是,严格的比例性,，即某种产品对资源的消耗量和可获得的利润与其生产数量严格成比例。,二是,可迭加性,。即生产多种产品对某种资源的消耗量等于各产品对该项资源的消耗量之和。,4/28/2026,9,模型中，,c,j,称为价值系数。,b,i,是资源限制量。,a,ij,称为技术系数或工艺系数。,二、线性规划模型的一般形式,假设线性规划问题中含有,n,个变量，,m,个约束方程。则线性规划模型的一般形式为：,max(,或,min)z,c,1,x,1,+,c,2,x,2,+,c,n,x,n,a,11,x,1,+,a,12,x,2,+,a,1,n,x,n,（,或，,）,b,1,a,21,x,1,+,a,22,x,2,+,a,2,n,x,n,（,或，,）,b,2,a,m,1,x,1,+,a,m,2,x,2,+,a,mn,x,n,（,或，,）,b,m,x,1,x,2,x,n,0,简写为：,向量形式：,矩阵形式：,4/28/2026,10,三、线性规划问题的标准形式,若得出的线性规划模型不是标准形式，应通过下列方法将其化为标准形式：,1.,目标函数为求极小值的情况，即,本教材规定，线性规划模型的标准形式为：,其特点是：,(1),目标函数求极大；,(2),约束条件取等式；,(3),变量非负；,(4),约束条件右边常数为正值。,化为标准形式的方法是，令,z,z,，,则,4/28/2026,11,三、线性规划问题的标准形式,3.,约束条件为不等式的情况,。,当约束条件为,“,”,时，在约束符号的左边加上一个松弛变量，将,“,”,变为,“,”,；,如,6x,1,+2x,2,24,化为标准形式为,6x,1,+2x,2,x,3,24,，,x,3,0,。,当约束条件为,“,”,时，在约束符号的左边减去一个剩余变量，将,“,”,变为,“,”,；,如,10 x,1,+12x,2,18,化为标准形式为,10 x,1,+12x,2,x,3,18,，,x,3,0,。,4.,对变量无约束的情况,。如,x,在,（，）,之间变化，即,x,的取值可正可负时，令,x,x,x,代入线性规划模型即可，其中,x,0,，,x0,。,5.,对于,x,0,的情况,，令,x,x,，,显然,x,0,。,2.,若约束条件右边常数项,b,i,m,），,其秩为,m,，,B,是矩阵,A,中的一个,m,m,阶的满秩子矩阵，称,B,是线性规划问题的一个基,。,系数矩阵,基,：,图解法,返回第一章目录,4/28/2026,17,一、线性规划问题的解的概念,基,B,中的每一个列向量,P,j,(,j=1,，,2,，,，,m,）,称为,基向量,，,与基向量,P,j,对应的变量,x,j,称为,基变量,；,除基变量以外的变量称为,非基变量,。,基解,：,在约束方程中，将非基变量移到等式右边,：,P,1,P,2,P,m,令非基变量,x,m+1,x,m+2,x,n,0,，,得,可解得,m,个基变量的唯一解为,：,X,B,（,x,1,，,x,2,，,，,x,m,）,T,。,加上非基变量取,0,的值，得,X,（,x,1,x,2,，,x,m,0,0,）,T,。,这就是线性规划问题的基解,。,4/28/2026,18,基可行解,：满足非负约束的解称为基可行解。,可行基,：对应于基可行解的基称为可行基。,例：,找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解,。,max z,2x,1,+3x,2,+x,3,x,1,+x,3,5,x,1,+2x,2,+x,4,10,x,2,+x,5,4,x,15,0,一、线性规划问题的解的概念,解,：,用穷举法找出该线性规划问题的全部基解。打,者为基可行解。,最优解为：,x,1,2,，,x,2,4,，,x,3,3,，,x,4,0,，,x,5,0,与,最优解对应的目标函数值为,z,19,4/28/2026,19,凸集,设,C,为,n,维欧氏空间的一个点集。若对于,C,中任意两点,X,1,，,X,2,满足,X,1,+(1-,)X,2,C (0,1),则称,C,为凸集,。,也就是说，如果,X,1,C,，,X,2,C,，,则线段,X,1,X,2,上的所有点,X,也属于,C,。,即,：,X,X,1,+(1-,)X,2,C (0,1),称,C,为凸集,。,从直观上看，凸集没有凹入部分，其内部没有孔洞。,二、凸集和顶点,凸集,凸集,凸集,凸集,凸集,凸集,4/28/2026,20,不是凸集,不是凸集,不是凸集,不是凸集,二、凸集和顶点,顶点,设,K,为凸集,，,XC,，,若,X,不能用,C,中不同的两点,X,1,，,X,2,的线性组合表示为,X,X,1,+(1-,)X,2,C (0,1),则称,X,为,C,的一个顶点（或极点）。即,X,不能成为,C,中任何线段的内点。,4/28/2026,21,三、,线性规划的基本定理,定理,1,：若线性规划问题存在可行解，则问题的可行域是凸集。,引理 线性规划的可行解,X,=(,x,1,x,2,x,n,),为基可行解的充要条件是,X,的正分量所对应的系数列向量线性独立。,定理,2,：线性规划的基本可行解对应于其可行域的顶点。,定理,3,若线性规划问题有最优解，一定存在一个基可行解是最优解。,单纯形法迭代原理,4/28/2026,22,定理,1,：若线性规划问题存在可行解，则问题的可行域是凸集。,证明 若满足线性规划约束条件,线性规划的基本定理的证明,P,j,x,j,b,j=1,n,的所有点组成的,集合,C,是凸集,则,C,内任意两点,X,1,，,X,2,连线上的点也必然在,C,内。,设,X,1,=(x,11,x,12,，,x,1n,),T,X,2,=(x,21,x,22,，,x,2n,),T,为,C,内任意两点，即,X,1,C,，,X,2,C,，将,X,1,，,X,2,代入约束条件，有,P,j,x,1j,b,j=1,n,P,j,x,2j,b,j=1,n,；,（1-9）,X,1,，,X,2,连线上任意一点可表示为：,X,a,X,1,（,1,a,）,X,2,（,0,a1,)(1-10),将（,1-9,）代入（,1-10,）得：,所以,X,1,C,，,X,2,C,。,由于集合中任意两点连线上的点均在集合内，所以,C,为凸集。,4/28/2026,23,引理 线性规划的可行解,X,=(,x,1,x,2,x,n,),为基可行解的充要条件是,X,的正分量所对应的系数列向量线性独立。,证：（1）必要性。由基可行解的定义得证。,（2）充分性。若向量,P,1,P,2,P,k,线性独立，则必有,km,时；当,k=m,时，它们恰好构成一个基，从而,X=(x,1,x,2,x,m,0,0),T,为相应的基可行解。,当,k,m,时，则一定可以从其余列向量中找出,(,m,-,k,),个与,P,1,P,2,P,k,构成一个基，其对应的解恰为,X,，,所以根据定义它是基可行解。,返回,4/28/2026,24,定理,2,：,线性规划的基本可行解对应于其可行域的顶点。,证,:,本定理需要证明,:X,是可行域顶点,X,是基可行解。,用反证法证明：,X,不是可行域的顶点,X,不,是基可行解。,（,1,）,X,不是基可行解,X,不是可行域的顶点。,假设,X,的前,m,个分量为正，有,4/28/2026,25,由引理知,P,1,P,2,P,m,线性相关，即存在一,组不全为零的数,i,(i=1,2,，,m),使得,d,1,P,1,+,d,2,P,2,+,d,m,P,m,=0(1.12),将（,1.12,）乘以一个不全为零的数,得,md,1,P,1,+,md,2,P,2,+,md,m,P,m,=0(1.13),(1.13)+(1.11),得：,(x,1,md,1,)P,1,+(x,2,md,2,)P,2,+(x,m,md,m,)P,m,=b,(1.11)-(1.13),得：,(x,1,md,1,)P,1,+(x,2,md,2,)P,2,+(x,m,md,m,)P,m,=b,令,X,(1),=(x,1,md,1,),(x,2,md,2,),(x,m,md,m,),0,0,X,(2),=(x,1,md,1,),(x,2,md,2,),(x,m,md,m,),0,0,又,m,可以这样来选择，使得对所有,i=1,2,m,有,x,i,md,i,0,即,X,不是可行域的顶点。,引理,4/28/2026,26,（,2,）,X,不是可行域的顶点,X,不是基本可行解。,设,X,(x,1,x,2,0,0),T,不是可行域的顶点，因而可以找到可行域内另外两个不同点,Y,和,Z,，有,X=,a,Y+(1-,a,)Z (0,a,1),或可写为：,x,j,=,a,y+(1-,a,)z,j,;(0,a,0,1-,a,0,故当,x,j,=0,时，必有,y,i,=z,i,=0,(1.14)-(1.15),得：,因,(y,j,z,j,),不全为零，故,P,1,P,2,P,r,线性相关，即,X,不是基可行解。,4/28/2026,27,定理,3,若线性规划问题有最优解，一定存在一个基可行解是最优解。,证：设,X,(0),=(x,1,0,x,2,0,x,n,0,),是线性规划的一个最优解，,若,X,(0),不是基可行解，由定理,2,知,X,(0),不是顶点，一定能在可行域内找到通过,X,(0),的直线上的另外两个点（,X,(0),+,md,)0,和（,X,(0),md,）,0,。,将这两个点代入目标函数有,C(X,(0),md),CX,(0),C,md;,C(X,(0),md),CX,(0),C,md,因,CX,(0),为目标函数的最大值，故有,CX,(0),CX,(0),C,md,；,CX,(0),CX,(0),C,md,由此知,C,md,0,，即有,C(X,(0),md),CX,(0),C(X,(0),md),。,如果（,X,(0),md,）或,(X,(0),md),仍,不是基可行解，按上面的方法继续做下去，最后一定可以找到一个基可行解，使目标函数值等于,CX,(0),，,问题得得证。,4/28/2026,28,四、单纯形法迭代原理,基本思路,：,先找出一个基可行解，判断它是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直到求得最优解或判断问题无解为止,。,在,约束条件,（,1.16,）,的系数矩阵中，总可以找到一个单位矩阵：,确定初始基可行解,4/28/2026,29,基阵,P,1,P,2,P,m,称为,基向量,，与其对应的变量,x,1,x,2,x,m,称为,基变量,，模型中的其它变量称为,非基变量,。,在约束条件中令所有的非基变量等于零，即可得到一个解：,X,(x,1,x,2,x,m,x,m+1,x,n,),T,（,b,1,b,2,b,m,0,0),T,因,b0,，,所以,X,满足非负约束，是一个基可行解。,从一个基可行解转换为相邻的基可行解,定义：,两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。,4/28/2026,30,设,初始基可行解中的前,m,个为基变量为：,X,(0),(x,1,0,x,2,0,x,m,0,0,，,0),T,将其代入约束条件,（,1.16,）有,系数矩阵的增广矩阵为：,因,P,1,P,2,P,m,是一个基，其它向量,P,j,可用这个基的线性组合来表示：,4/28/2026,31,或,将（,1.20,）式乘上一个正数,0,得,（,1.19,）,+,（,1.21,）并整理得：,由（,1.22,）式找到满足约束方程组,的,另一个点,X,(1),有,X,(1),(x,1,0,-,q,a,1j,x,2,0,-,q,a,2j,x,m,0,-,q,a,mj,0,q,0),T,其中,q,是,X,(1),的第,j,个,坐标的值。,要使,X,(1),是一个基本可行解，必须使,x,i,0,q,a,ij,0 1.23,）,令这,m,个不等式中至少有一个等号成立。故可令,4/28/2026,32,由式,（,1.24,）,知,因,a,lj,0,，,故由矩阵元素组成的行列式不为零,，,P,1,P,2,P,l-1,P,l,P,l+1,P,m,是一个基,。,在上述增广矩阵中作初等变换，将第,l,行,乘上,（,1/,a,lj,),再分别乘以,（,-,a,ij,)(,i,=1,2,l,-1,l,+1,m,),加到各行去，则增广矩阵左半部分变成单位矩阵。,所以，,X,(1),是一个可行解。,与,变量,x,l,1,x,1,l,-1,x,1,l,+1,x,m,x,j,对应的向量经重新排列后得,又因,b,l,/,a,lj,q,，,所以,b,=(,b,1,-,q,a,1,j,b,l,-1,-,q,a,l,-1,j,b,l,+1,-,q,a,l,+1,j,b,m,-,q,a,mj,),T,由此,X,(1),是同,X,(0),相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵,。,4/28/2026,33,3.,最优性检验和解的判别,将基本可行解,X,(0),和,X,(1),分别代入目标函数得,式中，因为,q,0,所以只要,就有,z,(1),z,(0),。,4/28/2026,34,最优性检验和解的判别准则,（,1,）,当所有,s,j,0,时,，,当前基可行解是线性规划问题的最优解；,（,2,）,当所有,s,j,0,，,若对某个非基变量,x,j,有,c,j,z,j,0,则该线性规划问题有无穷多个最优解；若对所有非基变量有,s,j,0,，,线性规划问题有唯一最优解。,（,3,）,若存在,s,j,0,，,又,P,j,0,，,则表明线性规划问题有无界解。,4/28/2026,35,1-4,单纯形法计算步骤,第一步：求初始基可行解，列出初始单纯形表。,c,j,c,1,c,m,c,j,c,n,C,B,基,b,x,1,x,m,x,j,x,n,c,1,x,1,b,1,1,0,a,1j,a,1n,c,2,x,2,b,2,0,0,a,2j,a,2n,c,m,x,m,b,m,0,1,a,mj,a,mn,c,j,z,j,0,0,基变量及其值,问题中所有变量,单位矩阵,非基变量系数向量,P,j,表示为基向量线性组合时的系数，因基向量是单位向量，故有,P,j,=a,1j,P,1,+a,2j,P,2,+a,mj,。,各变量在目标函数中的系数值,各,基变量在目标函数中对应的系数,检验数,s,j,=c,j,-z,j,=c,j,-(c,1,a,1j,+c,2,a,2j,+c,m,a,mj,),返回第一章目录,4/28/2026,36,第二步：最优性检验,若,单纯形表中所有检验数,c,j,z,j,0,，,且基变量中不含有人工变量，则得到线性规划问题的最优解，计算结束；若存在,c,j,z,j,0,，,而,P,j,0,，,则问题为无界解，计算结束；否则转下一步,。,第三步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。,1.,确定换入基的变量。只要有检验数,s,j,0,，,其对应的,x,j,就可以作为换入基的变量，当有一个以上检验数大于零时，从中找出最大的一个,s,k,，,其对应的变量,x,k,为换入基的变量（简称换入变量）。,2.,确定换出基的变量。用,P,k,列的系数分别去除常数项，找出最小比值,确定,x,l,为换出基的变量，元素,a,lk,决定了从一个基可行解到相邻基可行解的转移去向，所以，称,a,lk,为主元。,4/28/2026,37,3.,用换入变量,x,k,替换换出变量,x,l,，,作初等变换，得到一个新的单纯形表。,初等变换的方法是,：,将主元化为,1,，主元所在列的其它元素化为,0,。,第四步：重复第二、三两步，直到得出计算结果。,例,5,用单纯形法求解线性规划问题,解：在约束方程中加松弛变量，将该线性规划问题化为标准形式,其约束条件系数矩阵的增广矩阵为：,P,1,P,2,P,3,P,4,b,P,5,基变量为,x,3,、,x,4,、,x,5,；,非基变量为,x,1,、,x,2,。,单位矩阵,构成一个基,4/28/2026,38,令非基变量,x,1,、,x,2,等于零，的初始基本可行解为：,X,(0),(0,0,15,24,5),T,初始单纯形表,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,0,x,4,24,6,2,0,1,0,0,x,5,5,1,1,0,0,1,c,j,z,j,2,1,0,0,0,因为存在,s,1,2,0,，,s,2,1,0,。,所以初始基可行解不是最优解。,选择最大检验数对应的非基变量作为换入变量。,求最小比值，确定换入变量。,主元列,主元行,将主元化为,1,，主元所在列的其它元素化为,0,。,4/28/2026,39,迭代运算,初始单纯形表,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,0,x,4,24,6,2,0,1,0,0,x,5,5,1,1,0,0,1,c,j,z,j,2,1,0,0,0,第一次迭代的单纯形表,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,c,j,z,j,x,3,x,1,x,5,0,2,0,1,4,1/3,0,1/6,0,0,15,5,1,0,0,0,1,2/3,0,-1/6,1,0,1/3,0,-1/3,0,4/28/2026,40,迭代运算,第一次迭代的单纯形表,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,2,x,1,4,1,1/3,0,1/6,0,0,x,5,1,0,2/3,0,-1/6,1,c,j,z,j,0,1/3,0,-1/3,0,第二次迭代的单纯形表,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,c,j,z,j,x,3,x,1,x,2,0,2,1,1,0,3/2,0,-1/4,3/2,0,1,7/2,0,1/4,-1/2,0,0,15/2,1,5/4,-15/2,0,0,0,-1/4,-1/2,4/28/2026,41,迭代运算结果,最终单纯性表,（第二次的结果）,c,j,2,1,0,0,0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,2,x,1,7/2,1,0,0,1/4,-1/2,1,x,2,3/2,0,1,0,-1/4,3/2,c,j,z,j,0,0,0,-1/4,-1/2,因为所有检验数,s,j,0,，,且基变量中不含人工变量，所以得到线性规划问题的最优解为：,代入目标函数得：,4/28/2026,42,1-5,单纯形法的进一步讨论,一、人工变量法,线性规划模型化为标准形式后，若其约束条件的系数矩阵中不含有单位矩阵，需加人工变量，以便求解。,例,6,用单纯形法求解线性规划问题,P,4,P,6,P,7,罚因子，任意大负值,人工变量,返回第一章目录,4/28/2026,43,单纯形法求解过程,c,j,-3,0,1,0,0,-M,-M,C,B,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,4,1,1,1,1,0,0,0,-M,x,6,1,-2,1,-1,0,-1,1,0,-M,x,7,9,0,3,1,0,0,0,1,c,j,z,j,-2M-3,4M,1,0,-M,0,0,0,x,4,0,x,2,-M,x,7,c,j,z,j,1,-2,1,-1,0,-1,1,0,0,3,3,2,1,1,-1,0,0,6,6,4,0,3,-3,1,s,1,3030(2)+(M)66M3,6M3,s,2,00001+(M)00,0,s,3,1020(1)+(M)4,4M1,4M1,s,4,00100+(M)0,0,0,s,5,0010(1)+(M)3,3M,3M,s,6,M0(1)01+(M)(3)4M,4M,s,7,M0000+(M)10,0,4/28/2026,44,单纯形法求解过程,c,j,-3,0,1,0,0,-M,-M,C,B,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,3,3,0,2,1,1,-1,0,0,x,2,1,-2,1,-1,0,-1,1,0,-M,x,7,6,6,0,4,0,3,-3,1,c,j,z,j,6M-3,0,4M+1,0,3M,-4M,0,0,x,4,0,x,2,-3,x,1,c,j,z,j,1,1,0,2/3,0,1/2,-1/2,1/6,0,3,1,1/3,0,0,0,1/3,0,0,0,0,1,-1/2,1/2,-1/2,0,0,3,0,3/2,-M-3/2,-M+1/2,4/28/2026,45,单纯形法求解过程,c,j,-3,0,1,0,0,-M,-M,C,B,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,0,0,0,0,1,-1/2,1/2,-1/2,0,x,2,3,0,1,1/3,0,0,0,1/3,-3,x,1,1,1,0,2/3,0,1/2,-1/2,1/6,c,j,z,j,0,0,3,0,3/2,-M-3/2,-M+1/2,0,x,4,0,x,2,1,x,3,c,j,z,j,1,0,3/2,3/2,0,3/4,-3/4,1/4,0,1,-1/2,5/2,0,-1/4,1/4,1/4,0,0,0,0,1,-1/2,1/2,-1/2,0,0,-9/2,0,-3/4,-M+3/4,-M-1/4,所有检验数均,0,，且人工变量为零，,得到问题的最优解。,X,(0,5/2,3/2,0,0),T,;z,3x,1,x,3,3/2,两阶段法,4/28/2026,46,检验数计算,c,j,-3,0,1,0,0,-M,-M,C,B,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,4,1,1,1,1,0,0,0,-M,x,6,1,-2,1,-1,0,-1,1,0,-M,x,7,9,0,3,1,0,0,0,1,c,j,z,j,-2M-3,4M,1,0,-M,0,0,单纯形法求解过程,4/28/2026,47,二、两阶段法,对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。,第一阶段：构造只包括人工变量的目标函数，保持原问题约束条件不变，求第一阶段目标函数极小化的解。,判断：,当所,有,s,j,0,时，,若,人工变量为,0,，第一阶段的目标函数值也为,0,，则得到第一阶段最优解，转入第二阶段计算。否则，原问题无解。,第二阶段：去掉人工变量，将目标函数该为原问题的目标函数，继续迭代，寻找线性规划问题的最优解。,4/28/2026,48,用,两阶段法求解线性规划问题,x,6,、,x,7,是人工变量。,解,：,1),构造第一阶段的目标函数。,2,）将第一阶段的目标函数化为标准形式：,3,）列单纯形表计算求解。,4/28/2026,49,c,j,0,0,0,0,0,-1,-1,C,B,基,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,x,4,4,1,1,1,1,0,0,0,-1,x,6,1,-2,1,-1,0,-1,1,0,-1,x,7,9,0,3,1,0,0,0,1,c,j,-z,j,-2,4,0,0,-1,0,0,0,x,4,3,3,0,2,1,1,-1,0,0,x,2,1,-2,1,-1,0,-1,1,0,-1,x,7,6,6,0,4,0,3,-3,1,c,j,-z,j,6,0,4,0,3,-4,0,0,x,4,0,0,0,0,1,-1/2,1/2,-1/2,0,x,2,3,0,1,1/3,0,0,0,1/3,0,x,1,1,1,0,2/3,0,1/2,-1/2,1/6,c,j,-z,j,0,0,0,0,0,-1,-1,表1-11,表,1-12,4/28/2026,50,表1-12,c,j,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,4,0,0,0,0,1,-1/2,0,x,2,3,0,1,1/3,0,0,-3,x,1,1,1,0,2/3,0,1/2,c,j,-z,j,c,j,-z,j,-3,0,1,0,0,0,0,3,0,3/2,x,4,x,2,x,3,0,0,1,1,0,3/4,0,3/2,3/2,0,1,-1/2,5/2,0,0,0,0,1,-1/2,0,-1/4,-9/2,0,0,0,-3/4,因为所有,s,j,0,所以得到问题的最优解为：,X=(0,5/2,3/2,0,5),T,;z,（,-3,）,0,3/2,3/2,表,1-11,4/28/2026,51,三、单纯形法计算中的几个问题,1.,目标函数极小化时解的判别,。以所有检验数,s,j,0,作为判别表中解是否最优的标志，或将其化为极大化问题求解。,2.,退化。按最小比值确定换出变量时，有时同时出现两个相同的最小值，从而使下一个表的基可行解出现一个或多个基变量等于,0,的退化解。,原因：是模型中存在多余的约束，使多个基可行解对应同一顶点。存在退化解，就可能出现迭代运算循环。,解决办法：在同等条件下，始终选择下标值最小的变量作为换入变量，下标值最大的变量作为换出变量。,3.,无可行解的判别。求解过程中，若出现所有检验数,s,j,0,，,而基变量中仍含有非零的人工变量，表明问题无解。,4/28/2026,52,例,7,用单纯形法求解线性规划问题,标准化,加人工变量,c,j,2,1,0,0,-M,C,B,基,b,x,1,x,2,x,3,x,4,x,5,0,x,3,2,1,1,1,0,0,-M,x,5,6,2,2,0,-1,1,c,j,-z,j,2+2M,1+2M,0,-M,0,2,x,1,-M,x,5,c,j,-z,j,1,2,1,1,0,0,0,2,0,-2,-1,1,0,0,-2-2M,-M,0,4/28/2026,53,四、单纯形法小结,1.,一般线性规划模型化为标准形式的方法,线性规划模型,化为标准形式,变量,x,j,0,不变,x,j,0,令,x,j,x,j,，,则,x,j,0,x,j,无约束,令,x,j,x,j,x,j,；,x,j,0,，,x,j,0,约束条件,右端项,b,i,0,不变,b,i,0,约束条件两端乘“,-1”,形式,b,i,x,si,b,i,b,i,x,ai,b,i,b,i,x,si,x,ai,b,i,目标函数,极大或极小,max z,不变,min z,令,z,z,，,化为求,max z,变量前的系数,加松弛变量,x,s,时,max z,0,x,si,加人工变量,x,a,时,max z,Mx,ai,4/28/2026,54,Y,单纯形法计算步骤框图,找出初始基可行解,列出初始单纯形表,计算检验数,s,j,所有,s,j,0,对某一,s,j,0,有,P,j,0,迭代运算,用,x,k,替换,x,l,列出新的单纯形表,将主元化为,1,，主元所在列的其他元素化为,0,。,无界解,基变量中含非,零的人工变量,存在非基变量,检验数为零,无,可行解,无穷多最优解,唯一最优解,N,N,Y,Y,N,Y,N,4/28/2026,55,应用举例,用长,8,m,的角钢切割钢窗用料。每付钢窗含,1.5,m,的料,2,根，,1.45,m,的,2,根，,1.3,m,的,6,根，,0.35,m,的,12,根。若需钢窗用料,100,付，问最少需切割,8,m,长的角钢多少根？试建立其线性规划数学模型。,解,：为了节省材料，可以考虑各种套裁下料方案（见下表）。,料头为零的套裁方案表,x,2,x,1,x,3,x,4,x,5,x,6,x,7,x,8,x,9,假设变量,4/28/2026,56,假设按表列九个方案切割,8,m,长的角钢分别为,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,x,9,根。则该线性规划问题的数学模型为：,求一组决策变量,x,j,(,j,=1,2,9),满足约束条件,使目标函数,取最小值。,4/28/2026,57,*最优解如下*,目标函数最优值为,:223.75,变量 最优解 相差值,-,x 1 0 0,x 2 31.607 0,x 3 0 0,x 4 101.964 0,x 5 16.607 0,x 6 0 0,x 7 0 0,x 8 0 0,x 9 73.571 0,4/28/2026,58,某农场有,100,公顷土地及,15000,元资金可用于发展生产。农场劳动力情况为秋冬季,3500,人日，春夏季,4000,人日。各季劳动力本场用不了时可外出干活，春夏季外出干活收入为,2.1,元,/,人日，秋冬季外出干活收入为,1.8,元,/,人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养动物时每头奶牛需投资,400,元，每只鸡需投资,3,元。养奶牛时每头需拨出,1.5,公顷土地种饲草并占用人工：秋冬季为,100,人日，春夏季为,50,人日，年净收入为,400,元,/,每头奶牛。养鸡时不占用土地，需人工为：每只鸡秋冬季需,0.6,人日，春夏季为,0.3,人日，年净收入为,2,元,/,每只鸡。农场现有鸡舍允许最多养,3000,只鸡，牛栏允许最多养,32,头奶牛。三种作物每年需要的人工及收入情况见下表。现需确定该农场的经营方案，使每年净收入最大。试建立该问题的线性规划数学模型。,单位：人日,/,公顷,4/28/2026,59,解：,衣题意，该农场全年的生产经营活动主要有：种作物、饲养动物和外出干活。设,x,1,大豆种植面积（公顷）；,x,2,玉米种植面积（公顷）；,x,3,小麦种植面积（公顷）；,x,4,奶牛饲养量（头）,x,5,鸡饲养量（只）；,x,6,秋冬季外出干活劳力（人日）,x,7,春夏季外出干活劳力（人日）,该问题的线性规划模型为：,（土地资源约束）,（资金约束）,（秋冬季劳动力约束）,（春夏季劳动力约束）,（牛栏约束）,（鸡舍约束）,4/28/2026,60,*最优解如下*,目标函数最优值为,:19172.5,变量 最优解 相差值,-,x 1 0 19,x 2 50.833 0,x 3 0 24.4,x 4 3.75 0,x 5 0 .493,x 6 1345.833 0,x 7 0 1.06,4/28/2026,61,第六节 数据包络分析,4/28/2026,62,