可行解`可行解集(可行域)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,可行解、可行解集（可行域）,最优解、最优值,基、基变量、非基变量,基解、基可行解,线性规划解的概念,设,B,是线性规划的一个基，则,A,可以表示为,A,=,B , N,x,也可相应地分成,其中,x,B,为,m,维列向量，它的各分量为,基变量,，与基,B,的列向量对应；,x,N,为,n-m,列向量，它的各分量为,非基,变量,，与非基矩阵,N,的列向量对应。,这时约束等式,Ax,=,b,可表示为,Bx,B,+,Nx,N,=,b,即,x,B,=,B,-1,b,-,B,-1,Nx,N,特别，当取,x,N,=,0,，,这时有,x,B,=,B,-1,b=x,B,(0),。,这时目标函数,f=cx,可表示为,对应于B的典式,求解线性规划问题,对于,LP,的一个基,B,，若,B,-1,b0,且,N,0,，则对应于,B,的基解,x,(0),便是,LP,的,最优解,。,若基可行解,x,(0),所对应的典式中有某个检验数,r,0,，且相应有,b,ir,0,，则,LP,无最优解,。,若基可行解,x,(0),所对应的典式中有某个检验数,r,0,，且,b,ir,中至少有一个大于零,，则必,存在另一个基可行解，其对应的目标函数值比,f(,x,(0),),小,。,换基并求出新典式,确定离基变量：,minb,i0,/b,ir,|b,ir,0=b,s0,/b,sr,，,x,js,为离基变量，即用p,r,代替p,js,得新基。,确定进基变量：把对应于,正检验数,的的非,基变量转变为基变量,例题,初始可行基,B=(p,1, p,4 ,p,5,),对应,典式,单纯形表1,x,1,x,2,x,3,x,4,x,5,f,4,0,1,-1,0,0,x,1,2,1,-2,1,0,0,x,4,2,0,1,-2,1,0,x,5,5,0,1,1,0,1,单纯形表2,x,1,x,2,x,3,x,4,x,5,f,2,0,0,1,-1,0,x,1,6,1,0,-3,2,0,x,2,2,0,1,-2,1,0,x,5,3,0,0,3,-1,1,单纯形表3,x,1,x,2,x,3,x,4,x,5,f,1,0,0,0,-2/3,-1/3,x,1,9,1,0,0,1,1,x,2,4,0,1,0,1/3,2/3,x,3,1,0,0,1,- 1/3,1/3,最优解x,(2),=(9,4,1,0,0),最优值f(x,(2),)=1,进行两次单纯形迭代,