1.2. 运筹学线性规划-单纯形法-xiao

*,work hard,*,线性规划解法Linear Programming，LP),要求：,理解线性规划概念；,理解线性规划的一般形式与标准形式，能将一般形式化为标准形式；,掌握可行解、最优解及标准形式下的基、基解、基可行解等概念。,掌握单纯形解法。,1.3,线性规划图解法,graphic solution,优点：,直观性强，计算方便,缺点：,只适用于问题中有两个变量的情况,作用：,它的解题思路和几何上直观得到的一些概念判断，对理解求解一般线性规划问题的单纯形法有很大的,启示,。,1.3.1,图解法的步骤：,1建立坐标系，将约束条件在图上表示；,2确立满足约束条件的解的范围可行域；,3绘制出目标函数的图形；,4确定最优解可行域内使目标函数最大的点。,4,6,8,4,6,3,A,B,C,D(4, 2),D,点即为最优点,2x,1,+2x,2,=12,x,1,+2x,2,=8,4x,2,=12,4x,1,=16,每个点都是一个可能解可行解,可行域,1.3.2 特殊LP的图解法多解,10,50,10,50,B,AB,段即为最优解，,多重最优解。,A,多重解原因：目标函数的斜率与某一关键约束条件的斜率相等。,特殊LP的图解法无界解,1,2,1,2,B,A,原因：各约束没有围成一个封闭的可行域，可行域是发散的。,特殊LP的图解法无可行域，真正无解,10,15,10,30,原因：有相互矛盾的约束，约束条件之间没有交集。不能形成可行域。,1.3.3,图解法总结与启示,将约束条件作到坐标图上,找出,可行域,。,找最优点,即使目标函数,最大的点,。,图解法的启示,可行域是一个,凸多边形,.,最优解一定在可行域的,边界上,一般是在,顶点上,.,LP,的解可能有,多种形式,，如多解、无界解,(,发散,无穷,),或无可行域,.,1.3.4,线性规划的解,唯一最优解,无穷多最优解,无界解,无可行解,有解,无解,线性规划的解,1.3.5,线性规划解的问题,一般,mn,，如何解？,对于存在无穷多解的问题，为求唯一解最优，最简单的方法是舍去n-m个作用不大或呈负面影响的未知数决策变量，获得m个方程、m个未知数，即可获得唯一解。,问题：1如何舍去这些决策变量？原因、准那么2如何保证舍去的这些决策变量是适宜的？,思 路：,可行解,基 基向量、基变量、非基变量,根本解,可行基,最优解,1.4 LP 解的根本概念,1可行解,满足,约束条件,的解称为线性规划问题的,可行解,。,所有可行解的集合称为,可行域,。,可行域,2基基向量、基变量、非基变量,基在约束方程组的mn阶系数矩阵,中,假设有一个mm阶的非奇异子矩阵B,那么B为该LP问题的一个基一个矩阵。,那么矩阵B由m个线性无关的列向量组成，可令其对应的列向量Pj(j=1,2,m)为基向量，对应的xj为基变量，否那么为非基及非基变量。,m,列,(,要求线性无关,),(,基,),n-m,列,(,非基,),x,1,x,2, x,m,为,基变量,x,m,1, , x,n,为,非基变量,3基解 (也叫“根本解,在包含基和非基的LP问题中，任取一个基，令所有非基变量均为0，即可解出唯一根本解基解。,假设方程组的系数矩阵A的秩为m，因为mn，故该方程组有无穷多个解，,假设前m个变量的系数变量是线性无关的，那么方程组可表达为,基解的特点：,1 基解的非零分量的数目小于等于约束方程,数目m。,2 基解是约束方程的交点。,3 基解只满足条件约束，不一定满足非负约束，因此基解中的分量有可能为负数说明线性规划有很多基解，初次选定的不一定适宜。,4 基解的个数有限，不超过 Cnm 。,基解特点,-1,例,基解特点,-2,基解特点,-3,基解特点,-4,由此可知：基与基解一一对应，且该线性规划问题的基解的个数,4基可行解和可行基,满足(1.2), (1.3) 的基解，,称为基可行解，相应,的基B为可行基。,最优解,满足1.1), (1.2), (1.3)的解称为最优解。,5可行解、基解和根本可行解的关系,求最优解路线：,可行解,基可行解,最优解,区域 交点 顶点 某顶点,1.4.2 LP解的根本性质,1预备知识 凸集、顶点,2根本定理,定理1 LP的可行域为凸集,定理2 LP可行解是根本可行解 可行解的非零向量对应的系数列向量线性无关。,定理3 根本可行解 可行域的顶点,定理4 假设有最优解，最优解一定在可行域顶点或边界上实现。,1.5 LP,的求解与单纯形法,1、线性规划解法的思路与存在问题,1 标准数学模型中，有n个未知数决策变量，m个约束方程，一般mn，且常有m0=k，即选择j0数值中的最大值，其所在的列为换入基向量，对应的变量为换入基变量。此时，此列被称为主元列Pk。,c,C,Bi, a,ij,c,j,2,3,0,0,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,2,1,0,0,0,1,2,0,1,0,0,4,0,0,0,1,0,0,4,0,0,0,1,Z,j,x,3,x,4,x,5,x,6,0,0,0,0,12,8,16,12,0,2,3,0,0,0,0,k,2,2,0,4,换入基向量,步骤四：基变量的更换：2基变量的换出,规那么从原始基变量中选择一个，取出：mini =bi/aik|aik0=l，即选择i数值中的最小值，其所在行对应的变量为换出基变量。此时，此行被称为主元行Pl。Pk和Pl交汇元素为主元素。,c,j,2,3,0,0,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,2,1,0,0,0,1,2,0,1,0,0,4,0,0,0,1,0,0,4,0,0,0,1,Z,j,x,3,x,4,x,5,x,6,0,0,0,0,12,8,16,12,0,2,3,0,0,0,0,6,4,-,3,i,计算技巧,：,初始基变量对应的,i,=,右端项,b,除以,换入基变量所在的列的对应值,。,min,i,=,b,i,/a,ik,|,a,ik,0=,l,换出基变量,主元素,步骤四：基变量的更换：3基变量的更换。,规那么：在单纯形表中，用换入变量代替换出变量，获得新的XB列符号列。同时，相应的CB数据也由换入变量的cj来替代，其余暂时不变。,c,j,2,3,0,0,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,2,1,0,0,0,1,2,0,1,0,0,4,0,0,0,1,0,0,4,0,0,0,1,Z,j,x,3,x,4,x,5,x,6,0,0,0,0,12,8,16,12,x,3,x,4,x,5,x,2,0,0,0,3,步骤四：基变量的更换：4约束方程的迭代运算，求出新的基可行解,规那么：为求解方便，一般将须新的基变量对应的列向量变成主元素为1的单位向量。此时须将x2列变成单位列向量。,c,j,2,3,0,0,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,2,1,0,0,0,1,2,0,1,0,0,4,0,0,0,1,0,0,4,0,0,0,1,Z,j,12,8,16,12,x,3,x,4,x,5,x,2,0,0,0,3,单位化方法：根据初等变换来进行。,1第四行除以4。,3,0,1,0,0,0,1/4,2第四行-2+第二行。,2,1,0,0,0,0,-1/2,3第四行-2+第一行。,6,2,0,1,0,0,-1/2,步骤五：再次校验基变量的最优性。,规那么：按照上述方法，再次进行校验。如j0，那么表示最优。如不是，那么应再次进行基变量的更换，直到到达最优。,c,j,2,3,0,0,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,2,1,0,0,0,3,1,2,0,1,0,0,2,4,0,0,0,1,0,4,0,4,0,0,0,1,-,Z,9,2,0,0,0,0,-3/4,j,12,8,16,12,x,3,x,4,x,5,x,2,0,0,0,3,3,0,1,0,0,0,1/4,2,1,0,0,0,0,-1/2,6,2,0,1,0,0,-1/2,主元列,主元行,换入变量,换出变量,主元素,c,j,2,3,0,0,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,1,-2,0,1/2,4,1,0,0,1,0,-1/2,-4,0,0,0,-4,0,2,4,0,1,0,0,1,1/4,12,Z,13,0,0,0,-2,0,1/4,j,x,3,x,4,x,5,x,6,0,0,0,0,2,2,8,3,x,3,x,1,x,5,x,2,0,2,0,3,继续进行基变量的更换,x,6,换入，,x,5,换出。,c,j,2,3,0,0,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,0,1,-1,-1/4,0,1,0,0,0,1/4,0,0,0,0,-2,1/2,1,0,1,0,1/2,-1/8,0,Z,14,0,0,0,-3/2,0,-1/8,j,0,4,4,2,x,3,x,1,x,6,x,2,0,2,0,3,所有,j,0,，最优解。,此时：,x,1,x,2,x,3,x,4,x,5,x,6,T,=4,2,0,0,0,4,T,，,z=14.,b,2 2 1 0 0 0,1 2 0 1 0 0,4 0 0 0 1 0,0 4,0 0 0 1,Z,0,2,3,0 0 0 0,6,4,3,2 3 0 0 0 0,12,8,16,12,0,0,0,0,Z,2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4,0 0 0 1,b,0,2,3,0 0 0 0,6,4,3,2 3 0 0 0 0,12,8,16,12,0,0,0,0,0,0,0,3,3 0 1 0 0 0 1/4,16 4 0 0 0 1 0,2 1 0 0 1 0 -1/2,6 2 0 1 0 0 -1/2,Z,9,2 0 0 0 0 -3/4,3,2,4,Z,2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1,0 0 0,1/4,b,9,2,0,0 0 0,-3/4,3,2,4,2 3 0 0 0 0,6,2,16,3,0,0,0,3,0,2,0,3,3 0 1 0 0 0 1/4,8 0 0 0 -4 1 2,2 1 0 0 1 0 -1/2,2 0 0 1 -2 0 1/2,Z,13,0 0 0 - 2 0 1/4,4,-,4,12,Z,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1,0 0 0,1/4,b,13,0,0,0 -2 0,1/4,4,4,12,2 3 0 0 0 0,2,2,8,3,0,2,0,3,0,2,0,3,2 0 1 0 1/2 -1/8 0,4 0 0 0 -2 1/2 1,4 1 0 0 0 1/4 0,0 0 0 1 -1 -1/4 0,Z,14,0 0 0 - 2/3 -1/8 0,总结：单纯形法的计算步骤,转化为标准型；,建立初始单纯型表, 确定初始基，求出初始基可行解一般取单位矩阵做初始基；,计算检验数，判断最优性，确定换入基变量k 。,cC Bi a ij,可只计算非基变量的，换入基变量,kmax | 0 ，,k对应的列为主元列，列对应的变量为换入变量。,计算，确定换出基变量l 。,计算i， i bi/ a ik 当a ik 0时,只计算非负的aik 对应的行，换出基变量,l mini ，,l 对应的行为主元行，主元行对应的XB中的变量换出基变量。,K 列 l 行的元素称为主元素。,主元素用alk表示。,54,练习：利用单纯形表求解线性规划,C,j,比,值,C,B,X,B,b,检验数,j,检验数s：初始时是目标函数的系数随基的调整变化,变量符号,基变量符号,随基的调整变化,基变量在目标函数中的系数变化,约束方程的常数项,约束方程的变量系数,有一个检验数,s,j,=0,，此时基解不是最优；,所有检验数,s,j,0,线性规划,56,检验数,j,8,1,0,1,0,0,6,0,1,0,1/2,0,12,3,0,0,-2,1,x,3,x,2,x,5,0,5,0,-30,3,0,0,-5/2,0,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,5,0,0,0,8,1,0,1,0,0,12,0,2,0,1,0,36,3,4,0,0,1,x,3,x,4,x,5,0,0,0,0,3,5,0,0,0,-,12/2=6,36/4=9,1,=3,0,，此解不是最优,可求基可行解的状态,继续改变基变量,线性规划,57,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,3,5,0,0,0,8,1,0,1,0,0,6,0,1,0,1/2,0,12,3,0,0,-2,1,x,3,x,2,x,5,0,5,0,-30,3,0,0,-5/2,0,8,-,4,检验数,j,4,0,0,1,2/3,-1/3,6,0,1,0,1/2,0,4,1,0,0,-2/3,1/3,x,3,x,2,x,1,0,5,3,-42,0,0,0,-1/2,-1,令,x,4,=,0,，,x,5,=0,，得,x,1,=4,，,x,2,=6,，,x,3,=4,，即,X,0,=(4,6,4,0,0),T,j,0,最优解,:,X,*,=(4,6,4,0,0),T,最优值,:,Z,*,=42,线性规划,58,练习：,由下表数据，列出使总利润最大的生产方案模型，并求利润最大的生产方案,maxZ= 12 x,1,+,8,x,2,5x,1,+,2,x,2, 150,2 x,1,+3,x,2, 100,4x,1,+2,x,2, 80,x,1, x,2,0,令产品甲的产量为,x,1,产品甲的产量为,x,2,得如下线性规划模型,59,参考答案：,maxZ= 12 x,1,+,8,x,2,5x,1,+,2,x,2, 150,2 x,1,+3,x,2, 100,4x,1,+2,x,2, 80,x,1, x,2,0,maxZ= 12 x,1,+,8,x,2,5x,1,+,2,x,2,+,x,3,= 150,2 x,1,+3,x,2,+,x,4,= 100,4x,1,+2,x,2,+,x,5,=80,x,1, x,2, x,3, x,4, x,5,0,答案：,x,1,=5,，,x,2,=,30,，,max z=300,60,【,练习题,】,1.1 某工厂可以生产产品A和产品B两种产品。生产单位产品A和B所需要的机时、人工工时的数量以及可利用资源总量由下表给出。这两种产品在市场上是畅销产品。该工厂经理要制订季度的生产方案，其目标是使工厂的销售额最大。,产品A 产品B 资源总量,机器时 6 8 120,人工时 10 5 100,产品售价元 800 300,X1=10 x2=0 z=8000,61,【,练习题,】,该工厂根据产品A和产品B的销售和竞争对手的策略，调整了两种产品的售价。产品A和B的价风格整为600元和400元。假设其它条件不变，请你帮助该工厂经理制订季度的生产方案，其目标仍然是使工厂的销售额最大。,X1=4 x2=12 z=7200,62,【,练习题,】,由于某些原因，该工厂面临产品原料供给的问题。因此，工厂要全面考虑各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价等因素。有关信息在下表中给出。,产品A 产品B 资源总量,机器时 6 8 120,人工时 10 5 100,原材料(公斤) 11 8 130,产品售价元 600 400,X1=6 x2=8 z=6800,