单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运 筹 学,主 讲 教 师,向宇,第一章,线性规划与单纯形法,2 线性规划问题的标准型与解的概念,2.1 线性规划的标准型,我们规定线性规划的标准,型,如下：,maxZ=c,1,x,1,+c,2,x,2,+,+c,n,x,n,a,11,x,1,+,a,12,x,2,+,+a,1n,x,n,b,1,a,21,x,1,+,a,22,x,2,+,+a,2n,x,n,b,2,a,m1,x,1,+,a,m2,x,2,+,+a,mn,x,n,b,m,x,1,x,2,x,n,0,通常称,c,j,(j=1,2n),为价值系数，,b,i,（i=1,2,m),为资源系数；,a,ij,为技术系数，或约束系数在模型中它们是常数若记,X,=（,x,1,x,2,x,n,）,T,C,=（,c,1,c,2,c,n,）,b,=（b,1,b,2,b,m,）,T,A,=（,a,ij,）,n,n,=（P,1,P,2,P,n,）,则标准,型亦可记作,maxZ=,CX,AX=b,X,0,或,maxZ=,P,j,x,j,=,b,x,j,0,j=1,2n,任何形式的线性规划都可以化为与其等价的标准形式。
1）如果,目标函数是,minZ=cx,，,则可令,Z=-Z，,将目标函数变为：,maxZ,=-cx,（2）如果某,约束条件为不等式：,a,i1,x,1,+a,i2,x,2,+a,in,x,n,b,i,则在约束条件的左端加一个非负变量,x,n+i,称之为松弛变量，即可变为等式:,a,i1,x,1,+a,i2,x,2,+a,in,x,n,+,x,n+i,=,b,i,如果某,约束条件为不等式：,a,i1,x,1,+a,i2,x,2,+a,in,x,n,b,i,则可在约束条件的左端减一个非负变量,x,n+i,称之为剩余变量 或松弛变量，即可变为等式:,a,i1,x,1,+a,i2,x,2,+a,in,x,n,-,x,n+i,=,b,i,（3）如果,x,j,没有非负限制，则可令,x,j,=x,j,-x,j,其中,x,j,，,x,j,0，,代入目标函数及约束条件即可例3 将线性规划,minZ=3x,1,-x,2,x,1,+x,2,1,X,1,-x,2,-1,x,1,0,化为标准型解：,2.1 线性规划解的概念,我们把决策变量的一组取值称为线性规划问题的一个,解,满足约束条件的解称为,可行解,所有可行解的集合称为,可行域,。
使目标函数达到最优的可行解称为,最优解,在上一节图解法中，我们求得例1问题的最优解是唯一的，,但是线性规划问题的解还可能出现以下几种情况：,（1）无穷多个,最优解若例1的目标函数变为,maxZ=4,x,1,+2x,2,，,就会出现这种情况见图1-1O,X,2,60,50,40,30,20,10,10 20 30 40 50,x,1,4,x,1,+2x,2,=,120,2,x,1,+3x,2,=,100,Q,3,Q,2,Q,1,图1-1,maxZ=4,x,1,+2x,2,Z=6,x,1,+4x,2,（,2）无可行解如果约束中存在相互矛盾的约束条件，则导致可行域是空集，此时问题无可行解3）无有限最优解对下述线性规划问题,maxZ=,x,1,+x,2,-x,1,+x,2,4,x,1,-x,2,2,x,1,x,2,0,用,图解法求解结果见图1-2图1-2,x,2,4,2,2,4,0,x,1,从图中可以看出,可行域无界，在可行域中找不到最大值点，目标函数值可以增大到无穷大，称这种情况为无有限最优解或无界解x,1,-x,2,=2,-,x,1,+x,2,=4,Z=,x,1,+x,2,线性规划基解的概念,记线性规划问题为,maxZ=,CX,（L）,AX=b,X,0,基,：,设,A,是,m,n,阶约束系数矩阵（,m,n,）,秩,A=m,.,A=（,P,1,P,2,P,n,）,则A中一定存在,m,个线性无关的列向量，设为,P,j1,P,j2,P,jm,称可逆矩阵B=（P,j1,P,j2,P,jm,）为线性规划（L）的一个,基,，称B中的列向量对应的变量,x,j1,x,j2,x,jm,为,基变量,，其余变量称为,非基变量,。
基本解,：记基变量为X,B,=（,x,j1,x,j2,x,jm,）,T,，非基变量构成的列向量记为,X,N,，并令,X,N,=0，则有,AX=,P,j,x,j,=B,X,B,=,b,，于是有 X,B,=B,-1,b称X,B,=B,-1,b，X,N,=0为线性规划（L）的一个基本解基（本）可行解,：若基本解中,X,B,=B,-1,b0，,则称该解为基可行解，,这时基,B也称为可行基显然，基可行解的数目基解的数目,例4 求出下面线性规划的所有基本解，并指出哪些是基可行解maxZ=2,x,1,+x,2,3,x,1,+5x,2,15,6x,1,+2x,2,24,x,1,x,2,0,解：标准化得,maxZ=2,x,1,+x,2,3,x,1,+5x,2,+x,3,=,15,6,x,1,+2x,2,+x,4,=,24,x,1,x,2,x,3,x,4,0,系数矩阵,A=,秩A=2,取,B,1,=（,P,1,P,2,）=,同理,取,B,2,=（,P,1,P,3,）,可得,取,B,3,=（,P,1,P,4,）,可得,取,B,4,=（,P,2,P,3,）,可得,同理,取,B,5,=（,P,2,P,4,）,可得,x,2,=3,x,4,=18,x,1,=x,3,=0,是基可行解。
同理,取,B,6,=（,P,3,P,4,）,可得,x,3,=15,x,4,=24,x,1,=x,2,=0,是基可行解。