线性规划与单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 线性规划与单纯形法,线性规划是运筹学的一个重要分支。,1947,年丹捷格提出了一般线性规划问题求解的方法,单纯形法。,知识点：,线性规划问题的有关概念,LP,（,linear programming,）,SLP,（,Standard ,）,的转换,用单纯形法求解线性规划问题,1,线性规划问题及其数学模型,1.1,线性规划问题,提出：例,1,（,P8,）、,例,2,（,P9,）,例,1【,经典例题,】:,某工厂在计划期内要安排生产,I,、,II,两种产品。已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗，如,表,1,1,所示。该工厂每生产一件产品,I,可获利,2,元，每生产一件产品,II,可获利,3,元。问,I,、,II,两种产品的产量各为多少时，使该工厂获取最大利润？,产品,I,产品,II,设备,1,2,8台时,原材料,A,4,0,16kg,原材料,B,0,4,12kg,表,1-1,分析,设,x1,，,x2,分别表示在计划期内产品,I,、,II,的产量。,I,II,汇总,约束条件,目标,设备,1,2,x,1,+2,x,2,8台时,原材料,A,4,0,4,x,1,16kg,原材料,B,0,4,4,x,2,12kg,产量,x,1,x,2,单位利润,2,3,利润,2,x,1,3,x,2,2,x,1,+3,x,2,max,建模,该生产计划问题可用数学模型表示为：,目标函数,max z,2x,1,3x,2,约束条件,x,1,2x,2,8,4x1 16,4x,2,12,x,1,，,x,2,0,性质：线性规划是一个线性的条件极值问题，可分为两类：,当一项任务确定后，如何统筹安排尽量做到以最小的人力、财力、物力等资源去完成。,已知一定数量的人力、物力、财力等资源，如何安排使用它们使完成的任务（或创的价值、实现的利润等）最多。,定义：对于求取一组变量,X,j,（,j,1,，,2,，,3n),使得它满足线性约束条件的目标函数取得极值的一类最优化问题。,特征（,P10,）,每个问题都用一组,决策变量,（,x1,，,x2,，,，,xn,）表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值是,非负的,。,存在一定的,约束条件,，这些约束条件可以用一组,线性等式或线性不等式,来表示。,都有一个要求达到的,目标,，它可用决策变量的,线性函数,（称为目标函数）来表示。按问题的不同，要求目标函数实现,最大化或最小化,。,满足以上三个条件的数学模型称为,线性规划,的数学模型。,线性规划数学模型的一般形式,目标函数,max,（,min,）,z,c1x1+ c2x2 +,cnxn,(1.1),约束条件：,a11x1 + a12x2 + + a1nxn (=, )b1,a21x1 + a22x2 + + a2nxn (=, )b2, (1.2),am1x1 +am2x2 + +,amnxn,(=, ),bm,x1, x2, ,xn,0 (1.3),方程（,1.1,）称为目标函数；,（,1.2,）、（,1.3,）称为约束条件；,（,1.3,）也称为变量的非负约束条件。,1.2,图解法,可行解，可行解集，可行域,图解法的步骤,建立平面直角坐标系,画出可行域,作出目标函数等值线，求最优解,唯一最优解、无穷多最优解、无界解、无可行解,例,1,的图解法,在以,x1,、,x2,为坐标轴的直角坐标系中，非负条件,x1,，,x2 0,是指第一象限。例,1,的每个约束条件都代表一个,半平面,。例,1,的所有约束条件为半平面交成的区域（见图中的阴影部分） 。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称,可行解,）。此阴影区域是例,1,的线性规划问题的解集合，称为,可行域,。,在这个坐标平面上，目标函数,z,2 x1,3 x2,可表示以,z,为参数、,2/3,为斜率的一族平行线：,x2,（,2/3,）,x1,z/3,。位于同一直线上的点，具有相同的目标函数值，因而称它为,“,等值线,”,。当,z,值由小变大时，直线,x2,（,2/3,）,x1,z/3,沿其法线方向向右上方移动。当移动到,Q2,点时，使,z,值在可行域边界上实现最大化。这就得到了例,1,的最优解,Q2,，,Q2,点的坐标是（,4,，,2,）。于是可计算出,z,14,。,习题,1,图解法解下列线性规划问题,(1) MaxZ 3x,1,4x,2,S.T, 2x,1,+x,2,1, x,1,+2x,2, 4,2x,1,+x,2,6,x,1, x,2,1,X,1,x,2,0,(2) MinZ 5x,1,-6x,2,S.T,x,1,+2x,2, 4,3x,1,+2x,2,6,x,1,2 x,2,0,X,1,x,2,0,1.3,线性规划问题的标准型式,线性规划问题的完整标准型式,向量和矩阵符号表达式,矩阵表达式,线性规划问题的标准化,目标函数的标准化：,MinZ=CX MaxZ =,CX ( Z=,Z),负右端系数的转换：当,b,i,0,时，两端同乘（,1,）,约束条件的标准化：对于“,“,型，则在不等式的左端加一非负变量（松弛变量），对于“,“,型，则在不等式的左端减一非负变量（剩余变量）。,决策,变量的转换： 当,x,j,0,时，令,x,j,x,j,，,则,x,j,0,； 如,x,j,无符号限制，则令,x,j,x,j,x,j,“,，,x,j,，,x,j,“ 0,例,3,：,将下述线性规划模型（例,1,）化为标准型,目标函数,max,z,2,x,1,3,x,2,约束条件,x,1,2,x,2,8,4,x,1,16,4,x,2,12,x,1,，,x,2,0,解：根据题意,用,x4,x5,替换,x3,替换，其中,x4,，,x5 0,在第一个约束不等式,号的左端加入松弛变量,x6,在第二个约束不等式,号的左端加入剩余变量,x7,令,z,z,令，把求,minz,改为求,maxz,。,得标准型,目标函数,max z,x1,2x2,3,（,x4,x5,）,约束条件,x,1,x,2,（,x,4,x,5,） ,x,6,7,x,1,x,2,（,x,4,x,5,） ,x,7,2,3x,1,x,2,2,（,x,4,x,5,） ,5,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,，,x,7,0,目标函数,min,z,x,1,2,x,2,3,x,2,约束条件,x,1,x,2,x,3,7,x,1,x,2,x,3, 2,3,x,1,x,2,2,x,3,5,x,1,，,x,2,0,，,x,3,为无约束,例,4,：,将下述线性规划问题化为标准型,在各不等式中分别加上一个松弛变量,x,3,，,x,4,，,x,5,，使不等式变为等式，便得到标准型。,目标函数,max z,2x,1,3x,2,约束条件,x,1,2x,2,x,3,8,4x,1,x,4,16,4x,2,x,5,1,x,1,，,x,2,，,x,3,，,x,4,，,x,5,0,习题,2,将下列模型化成标准型,minz,x,1,x,2,4x,3,s.t,3x,1,4x,3,-9,-x,1,+ x,2, 6,5x,1,+ 2x,3, 16,x,1, 0,x,2, 0 ,x,3,无符号限制,习题,3,将下列模型化成标准型,minz,x,1,x,2,3x,3,s.t,x,1,+ x,2,x,3,=10,5x,1,-7x,2,+3 x,3, -8,X,1,+ X,2,2,x,3, 18,x,1,0, x,2,0, x,3,无符号限制,习题,4,：,将下列模型化成标准型,min z,x,1,x,2,4x,3,s.t,3x,1,4x,3,-9,x,1,+x,2,6,5x,1,+2x,3, 1,x,1,0,x,2,0,x,3,无符号限制,解：令,z,z,，,x,1,x,，,x,3,x,3,x,3,“,引入松弛变量,x,4,，,x,6,剩余变量,x,5,，,并加以整理得：,max z ,x,1,+x,2,4,x,3,+4x,3,s.t,x,1,4,x,3,4x,3,x,4,9,x,1, +x,2,x,5,6,5x,1,+2,x,3,2x,3,“,+,x,6,16,x1 ,，,x2,，,x3 ,，,x3“,，,x4,，,x5,x6 0,习题,5,：,将下列模型化成标准型,min z,x,1,x,2,3x,3,s.t,x,1,+x,2,x,3,=10,5x,1,-7x,2,+3 x,3, -8,x,1,+,X,2,2,x,3, 18,x,1,0, x,2,0, x,3,无符号限制,习题,5,解答,解,:,令,x,2,x,2,，,x,3,x,3,x,3,“,Z=-Z,/,引入剩余变量,x,4,，,x,5,，,松弛变量,x,6,，,并加以整理得：,max z, ,x,1,x,2,3,x,3,3x,3,“,s.t,x,1,x,2,x,3,x,3,“,=10,5x,1,7x,2,3 x,3,3,x,3,“,x,4,=,8,x,1,x,2,x,5,=,2,x,3,x,3,“,x,6,=18,x,1,，,x,2,x,3,，,x,3,“,，,x,4,，,x,5,，,x,6,0,1.4,线性规划问题的解的概念,max,（或,min,）,z,CX,s.t AX,b,X0,其中,A,爲,m*n,阶矩阵，,mn,，,A,的秩为,m,。,可行解,基：中任何一组,m,个,线性无关的列向量构成的子矩阵为，称为该问题的一个基（,basis),，,与这些列向量对应的变量称为的基变量（,basic variable),，,其余变量称为的非基变量。,基可行解：对于基，令非变量为零，求得满足式,AX,b,的解，称为对应的基本解（,basic solution);,若同时又满足式 ,，这种基本解称为基本可行解，基本可行解所对应的基称为可行基。,最优基,退化解,若基本可行解中某基变量为零，称其为退化解，所对应的极点为退化极点。,例：某一,LP,问题的约束条件为,x1,x21,x1,2x22,x1,，,x20,几种解之间的关系,可行解,基,可行解,基解,非,可行解,2,线性规划问题的几何意义,2.1,基本概念,凸集,凸组合,顶点,2.2,基本定理,定理,1,线性规划问题的可行域,S,是,凸集。,引理,1,定理,2 X,为线性规划问题可行域,S,上极点的充要条件是,X,的正对应的系数列向量线性无关。,引理,2,例,5,定理,3 X,是可行域,S,上极点的充要条件是它为基本可行解。,线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。, 3,单纯形法,单纯形法的基本思想：根据问题的标准型，从可行域中一个基本可行解（一个极点）开始，转换到另一个新的基本可行解，并且使目标函数值较前有所改善。经过若干次这样的转换，最后得到问题的最优解或判断无最优解。,3.0,导入单纯形法,分别用几何法与代数法求解下列线性规划问题：,max(min) z,2x,1,+3x,2,s.t x,1,+x,2,+x,3,=2,x,2,+x,3,=1,x,1,，,x,2,，,x,3,0,解：用几何法求解：,max(min) z,2x,1,+3x,2,s.t x,1,+x,2,+x,3,=2,x,2,+x,3,=1,x,1,，,x,2,，,x,3,0,max(min) z2x,1,+3x,2,s.t x,1,=1,x,2,+x,3,=1,x,1，,x,2，,x,3,0,导入单纯形法（续,1,）,用几何法求解：,B（1，1，0）,A（1，0，1）,max z*5,min z*2,x,1,x,2,x,3,导入单纯形法（续,2,）,用,代数法求解：,max(min) z2x,1,+3x,2,s.t,x,1,=1,x,2,+x,3,=1,x,1，,x,2，,x,3,0,max z5,3x,3,s.t,x,1,=1,x,2,=1 x,3,x,1，,x,2，,x,3,0,min z2,+3x,2,s.t,x,1,=1,x,3,=1 x,2,x,1，,x,2，,x,3,0,最优解,X*=(1,0,1) min z*=2,最优解,X*=(1,1,0) max z*=5,3.1,举例,:,例,5,求解下列线性规划问题,max z,1.5x,1,+2.4x,2,+0x,3,+0x,4,+0x,5,S.t,.,x,1,+x,2,+x,3,=100,3x,1,+2x,2,+x,4,=190,2x,1,+3x,2,+x,5,=240,x,j,0(j=1,2,35),例,5,解答,解： 约束方程的系数矩阵为：,1,1,1 0 0,A=(P,1,，,P,2,，,P,3,，,P,4,，,P,5,）,3,2,0 1 0,2,3,0 0 1,初始可行基为：,1 0 0,B,（,P,3,，,P,4,，,P,5,）,0 1 0,0 0 1,用非基变量表达基变量,：,x,3,=,100,x,1,1x,2,x,4,=,190,3x,1,2x,2,（,1,。,7,）,x,5,=,240,2x,1,3x,2,例,5,解答（续,1,）,将（,1.7,）式代入目标函数得：,z= 0 +,.,x,1,+2.4x,2,令非基变量为零，,即令,x,1,0,，,x,2,0,得一个基可行解：,x,（,0,）,（,0,0,100,190,240,),此时得,z,0,非基变量的系数都是正数，因此将非基变量变换成基变量，目标函数的值就可能变大。,取,x,2,为,入基变量,（一般选择,正价值系数最大的非基变量为入基变量,，而,2.41.5,）,于是还要确定基变量,x,3,，,x,4,，,x,5,中的一个换出来成为非基变量。下面来确定换出变量：,当,x,1,=0,时（先固定,x,1,是两个非基变量中的一个）,x,3,=,100,1,x,2,0,x,4,=,190,2,x,2,0,x,5,=,240,3,x,2,0,要让,x,3,，,x,4,，,x,5,非负，且有一个为,0,，,只有选择,x,2,80,时，,才能使,x,3,x,4,x,5,同时非负。,(,此时,x,3,200,，,x,4,300,，,x,5,0),因此只有,当,x,2,=,min(100/1,190/2,240/3,),=80,时,才能使,x,3,x,4,x,5,非负的同时，有一个原来的基变量,x,5,取值为,0,，从而可以换出来成为非基变量。其中,x,3,=20, 0,，,x,4,=30, 0,，,X,5,= 0,，取,X,5,为,出基变量,（所谓的,最小比值规则,）,例,5,解答（续,2,）,x,2,100,x,2,95,x,2,80,x,2,80,？,例,5,解答（续,3,）,用非基变量表达基变量：,x,3,+x,2,=100 -x,1,x,3,=,20,1/3x,1,+1/3x,5,x,4,+2x,2,=190-3x,1,x,4,=,30,5/3x,1,+2/3x,5,（,1.8,）,3x,2,=240 -2x,1,-,x,5,x,2,=,80,2,3x,1,- 1/3x,5,将（,1.8,）式代入目标函数得：,z=192-0.1x,1,-0.8x,5,令非基变量为零，,即,x,1,0,，,x,5,0,得一个基本可行解：,x,（,1,）,（,0,80,20,30,0), z=192,由于非基变量的价值系数都是负数，而,x,1,0,，,x,5,0,，,因此当,x,1,0,，,x,5,0,时，,z,取得最大值,192,。所以,最优解,X*= x,（,1,）,（,0,80,20,30,0),目标函数值,z*=192,例,6,求线性规划问题的初始可行基：,max z=10x,1,+3x,2,+4x,3,s.T,3x,1,+6x,2,+2x,3,19,9x,1,+3x,2,+1x,3,9,x,j,0(j=1,2,3),解：引人松驰变量,x,4 ,x,5,3x,1,+6x,2,+2x,3,+,x,4,=19,9x,1,+3x,2,+1x,3,+,x,5,=9,取,x,4,，,x,5,为基变量，,初始可行基：,1 0,B=,0 1,初始基可行解为,:X =(0,0,0,19,9),3.2,初始基本可行解的确定,直接观察到一个单位矩阵，可当成初始基本可行基,.,松弛变量：对“,”,型，引入松驰变量,人造基：对“,”,或“,=”,型，引入剩余变量和人工变量,3.3,最优性检验及判断准则,用分量形式表达,求解的一次迭代结果為,:,X,i,=,b,i,/,-,a,ij,/,X,j,(,i=1,2, ,m,),Z=,c,i,X,i,+ ,c,j,X,j,=,c,i,b,i,/,-,(,c,i,a,ij,/,X,j,),+ ,c,j,X,j,=,c,i,b,i,/,+,(,C,j,-,c,i,a,ij,/,),X,j,Z=,z,0,+ ,j,X,j,用矩阵形式表达,标准型,max z=CX,s.t,AX=b,X0,A=(B,N) X=(X,B,X,N,),T,C=,(C,B,C,N,),代入,AX=b,得,B X,B,+N X,N,=b,X,B,=,B,-1,b,-,B,-1,N,X,N,Z=,(C,B,C,N,),(X,B,X,N,),T,=,C,B,X,B,+,C,N,X,N,Z=,C,B,B,-1,b,+ (,C,N,-,C,B,B,-1,N,),X,N,最优解的判别,:,若,x,(0),=(b,1,/, b,2,/, .,b,m,/, 0.,0,0,),为对应基,B,的一个基可行解,并对于一切,j=m+1,n,且有,j,0,(,最优性条件,).,则,x,(0),为最优解,无穷多最优解判别,:,若,x,(0),=(b,1,/, b,2,/, .,b,n,/, 0.,0,0,),为对应基,B,的一个基本可行解,并对于一切,j=m+1,n,有,j,0,而且又存在非基变量的检验数,m+k,=0,，则线性规划问题有多重解,.,无界解判别,:,无最优解判別,:,若,x,(0),=(b,1,/, b,2,/, .,b,n,/, 0.,0,0,),为对应基,B,的一个基可行解,至少有一个,m+k,0,对于,I=1,2,.m,均有,a,/,I,m+k, 0,则线性规划问题无最优解,.,唯一最优解判别,无可行解判别,3.4,基变换,从原可行基中换一个列向量（当然要保持线性独立），得到一个新的可行基，称之为,基变换,。,换入变量的确定,从直观上一般选择,j,0,中的最大者（可以任选或按最小足码选），即,max(,j,0)=,k,所对应的,x,k,为换入变量。,换出变量的确定,=,min(,b,i,/,a,ik,|,a,ik,0)=,b,l,/,a,lk,这时,x,l,为换出变量。按照最小比值确定,值，称为,最小比值规则,。,3.5,迭代（旋转运算）,确定,x,k,为换入变量、,x,l,为换出变量后，以,a,lk,为主元素进行迭代（即用高斯消元法或称为旋转运算），把,p,k,变换为单位向量（其中第,l,个分量为,0,）。,例,7,4,单纯形法的计算步骤,4.1,单纯形表,c,j,C,1,c,2.,c,m,c,m+1,c,m+2,.,c,n,b,C,B,x,B,x,1,x,2,x,m,x,m+1,x,m+2.,x,n,C,1,x,1,C,2,x,2,c,m,x,m,1 0 .0,a,1,m+1,a,1,m+2,a,1, n,0 1 0,a,2,m+1,a,2,m+2,a,2, n,. . . .,0 0 1,a,m,m+1,a,m,m+2,a,m ,n,b,1,b,2,.,b,m,C,j,-z,j,0 0 0,C,m+1,-,c,i,a,i,m+1,C,n,-,c,i,a,i,n,-,c,i,b,i,4.2,单纯,形法的计算步骤,1.,找出一个初始基本可行基，建立单纯形表,2.,检验各非基变量,x,的检验数,j,=,c,j,-,c,i,a,ij,，,对最大化问题，若,j,0,，,j=m+1,，,.n,(,对最小化问题，若,j,0,，,j=m+1,，,.n),，,则得到最优解，停止计算。否则，转入下一步,.,3.,对最大化问题，在,j,0 (,对最小化问题，,j,0 ),，,j=m+1,，,.n,中， 若有一个,k,对应的,x,k,的系数列向量,P,k,0,，,则问题无最优解，停止计算。否则，转入下一步,.,4.,根据,max(,j,0 )=,k,(,对最小化问题， 按,min (,j,0 )=,k,),，,确定,x,k,为 入基变量，按最小比值判断法计算,=,min(,b,i,/,a,ik,|,a,ik,0)=,b,l,/,a,lk,确定,x,l,为 出基变量。转下一步。,i1,m,单纯,形法的计算步骤（续）,5.,以,a,lk,为主元素进行迭代运算。,a,1k,0,a,2k,0,P,K,= . .,a,lk,1,. .,a,nk,0,同时将,X,B,列中,x,l,的换为,x,k,，,得到新的单纯形表。重复第,25,步,走到终止。,第,l,行,5,单纯形法的进一步讨论,5.1,人工变量法：人为地构造一个单位矩阵来充当初始可行基，再通过单纯形迭代逐步地用矩阵,A,的列向量取代这个人造基或证明原问题无最优解。,大,M,法：在人工变量相应的一个绝对值很大,-M(M0,，,对于极小化问题用,+M),，,这样只要基变量中还存在人工变量,目标函数就不可能实现极值。,例,8,两阶段法,例,9,5.2,退化,5.3,检验数的几种表现形式,5.4,单纯形法小结,5.1,人工变量法,人为地构造一个单位矩阵来充当初始可行基，再通过单纯形迭代将它们逐个地从基变量中替换出来。若经过基的变换，基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有,C,j,-z,j, 0,，,而在其中还有某个非零人工变量，这表示无可行解。,大,M,法,两阶段法,大,M,法,基本思想,:,假定人工变量在基变量中的价值系数为一个绝对值很大的,-M (M0,对于极小化问题用,+M),这样只要基变量中还存在人工变量,目标函数就不可能实现极值,.,基本步骤,:,1.,建立,LP,问题,2. LP SLP,3. SLP MSLP,4.,单纯形迭代,.,min z=-3x,1,+x,2,+x,3,s.t,x,1,-2x,2,+x,3,11,-4x,1,+x,2,+2x,3,3,-2x,1,+x,3,=1,x,j,0(j=1,2,3),例,8:,用大,M,法求解线性规划问题,例,8,（解）,解,:,标准化,: x,1,-2x,2,+x,3,+ x,4,=11,-4x,1,+x,2,+2x,3,-,x,5,=,3 (SLP,问题,),-2x,1,+x,3,=1,x,j,0(j=1,2,3,4,5),化成,MSLP,问题,:,min z=-3x,1,+x,2,+x,3,+My,1,+My,2,x,1,-2x,2,+x,3,+ x,4,=11,-4x,1,+x,2,+2x,3,-,x,5,+ y,1,=,3,-2x,1,+x,3,+y,2,=1,x,j,0(j=1,2,3,4,5),y,1,y,2,0,单纯形迭代,:,c,j,-3 1 1 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,0,M,M,X,4,y,1,y,2,1 -2 1 1 0 0 0,-4 1 2 0 -1 1 0,-2 0,1,0 0 0 1,11,3,1,j,-3+6M 1-M,1-3M,0 M 0 0,-4M,例,8,（解）,c,j,-3 1 1 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,0,M,1,X,4,y,1,x,3,3 -2 0 1 0 0,0,1,0 0 -1 1,-2 0 1 0 0 0,10,1,1,j,-1,1-M,0 0 M 0,-M-1,例,8,（解）,c,j,-3 1 1 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,0,1,1,X,4,x,2,x,3,3,0 0 1 -2,0 1 0 0 -1,-2 0 1 0 0,12,1,1,j,-1,0 0 0 1 0 0,-2,例,8,（解）,X,*,=(4,1,9,0,0),T,Z,min,=-2,cj,-3 1 1 0 0 M M,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,-3,1,1,X,1,x,2,x,3,1 0 0 1/3 -2/3,0 1 0 0 -1,0 0 1 2/3 -4/3,4,1,9,j,0 0 0 1/3,1/3,0 0,2,例,8,（解,）,兩阶段法,基本思想,:,它把,LP,问题分两阶段来处理人工变量,.,第一阶段,:,建立,ASLP,问题并求解以判断原问题是否存在最优解,. ASLP,问题的目标函数取所有人工变量之和,并对目标函数取极小值,.,第二阶段,:,利用第一阶段的最终单纯形表,计算,SLP,关于已知基的目标函数和检验数,直接构成,SLP,的初始单纯形表,进行求解,.,基本步骤,:,1.,建立,LP,问题,2. LP SLP,3. SLP ASLP,4.,单纯形迭代求解,ASLP,问题的最优可行基,.,若基本变量组中含有取值大于零的人工变量,则,SLP,问题无可行解,.,5.,单纯形迭代求解,SLP,问题,例,9,用两阶段法求解下列线性规划问题,min z=-3 x,1,+x,2,+x,3,S.T.,x,1,-2x,2,+ x,3,11,-4x,1,+x,2,+2x,3,3,-2x,1,+x,3,=1,x,j,0(j=1,2,3),例,9(,解,),解：,LP ASLP,问题,min w=,y,1,+y,2,x,1,-2x,2,+x,3,+ x,4,=11,-4x,1,+x,2,+2x,3,-,x,5,+ y,1,=,3,-2x,1,+x,3,+y,2,=1,x,j,0(j=1,2,3.5),y,1,y,2,0,思考：,目标函数设为,min w=,3,y,1,+,4,y,2,行,不行？,c,j,0 0 0 0 0 1 1,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,0,1,1,X,4,y,1,y,2,1 -2 1 1 0 0 0,-4 1 2 0 -1 1 0,-2 0,1,0 0 0 1,11,3,1,j,6 -1,-3,0 1 0 0,-4,例,9(,解,),例,9(,解,),cj,0 0 0 0 0 1 1,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,0,1,0,X,4,y,1,x,3,3 -2 0 1 0 0 -1,0,1,0 0 -1 1 -2,-2 0 1 0 0 0 1,10,1,-1,j,0,-1,0 0 1 0 2,1,在最优表中,基变量已无人工变量,可进行第二阶段,.,cj,0 0 0 0 0 1 1,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,y,1,y,2,0,0,0,X,4,x,2,x,3,3 0 0 1 -2 2 -5,0 1 0 0 -1 1 -2,-2 0 1 0 0 0 1,12,1,1,j,0 0 0 0 0 1 1,0,例,9(,解,),例,9(,解,),cj,-3 1 1 0 0,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,0,1,1,X,4,x,2,x,3,3,0 0 1 -2,0 1 0 0 -1,-2 0 1 0 0,12,1,1,j,-1,0 0 0 1,0,所有检验数,大于或等于零,得最优表,. X,*,=(4,1,9,0,0),T,Z,min,=-2,cj,0 0 0 0 0,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,-3,1,1,X,1,x,2,x,3,1 0 0 1/3 -2/3,0 1 0 0 -1,0 0 1 2/3 -4/3,4,1,9,j,0 0 0 1/3 1/3,2,例,9(,解,),小结,是 否 否,是,唯一最,优解,LP,问题,引人松弛变量,人工,变量,列出单纯形表,非基,变量,检验数,j,0,对任,一,j,0,有,a,ij,0,令,k,=max,j,X,k,为,入基变量,对,所有,a,ik,0,计算,min(,i,),=min(b,i,/ a,ik,),=,l,X,l,为出基变量,换基,迭代,1.X,k,替代,X,l,2.,对主元行,3.,对主元列,4.,对其它行,列变换,无最优解,无,可行解,基,变量含有,非零人工变量,非基,变量检,验数为零,多重最优解,打印,结果,结束,6,应用举例,一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型：,（,1,）要求解问题的,目标函数,能用数值指标来反映，且为,线性函数,；,（,2,）存在着,多种方案,；,（,3,）要求达到的目标是在一定,约束条件,下实现的，这些约束条件可用,线性等式或不等式,来描述。,例,10,例,10,合理利用线材问题。现要做,100,套钢架，每套用长为,2.9m,，,2.1m,和,1.5m,的元钢各一根。已知原料长,7.4m,，,问应如何下料，使用的原材料最省。,例,10,（解）,解：采用套裁方案，可取方案为：,方案,下料数,长度,I,II,III,IV,V,2.9,2.1,1.5,1,0,3,2,1,2,2,1,2,1,3,合计,料头,7.4,0,7.3,0.1,7.2,0.2,7.1,0.3,6.6,0.8,例,10,（解）,为了得到,100,套钢架，需要混合使用各种下料方案。设第,i,种方案下料的原材料根数为,x,i,，（,i,1,，,2,，,3,，,4,，,5,）,得数学模型为：,min z=0 x,1,+0.1x,2,+0.2x,3,+0.3x,4,+0.8x,5,x,1,+,2x,2,+ x,4,100,2x,3,+ 2x,4,+x,5,100,3x,1,+,x,2,+2,x,3,+3x,5,100,x,i,0(i=1,2,3,4,5),加入人工变量用单纯形法计算可得到结果。最优方案为,I,方案,下料,30,根，,II,方案,下料,10,根，,IV,方案,下料,50,根。,例13,例,13,连续投资问题（课本,P42,）,例,13,（解）,解：,(1),确定变量,：以,x,iA,，,x,i,B,，,x,i,C,，,x,i,D,（,i,1,，,2,，,3,，,4,，,5,）,分别表示第,i,年年初给项目,A,B,C,D,的投资额。它们都是待定的未知变量。,（,2,）,投资额应等于手中拥有的资金额,。,（,3,）目标函数,问题是要求在第五年末该部门手中拥有的资金额达到最大，这个目标函数可表示为：,Maxz,1.15,x,iA,+1.40,x,iB,+1.25,x,iC,+1.06,x,iD,（,4,）,数学模型,（,5,）用单纯形法计算结果。,例,13,（解）,A,B,C,D,1,2,3,4,5,习题,P44,第,1,题（,1,）（,3,）或（,2,）（,4,）,第,2,题（,1,）,P45,第,4,题,(1),或（,2,）,第,6,题,(1),或（,2,）或（,3,）或（,4,）,P46,第,7,题,作业,P45,：,1.3,（,1,）、,1.4,（,2,）,P45,：,1.6,（,2,）,P46,：,1.7,、,1.9,