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

《可行解`可行解集(可行域).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、可行解、可行解集（可行域）最优解、最优值基、基变量、非基变量基解、基可行解线性规划解的概念设B是线性规划的一个基，则A可以表示为A=[B,N]x也可相应地分成其中xB为m维列向量，它的各分量为基变量，与基B的列向量对应；xN为n-m列向量，它的各分量为非基变量，与非基矩阵N的列向量对应。这时约束等式Ax=b可表示为BxB+NxN=b即xB=B-1b-B-1NxN特别，当取xN=0，这时有xB=B-1b=xB(0)。这时目标函数f=cx可表示为对应于B的典式求解线性规划问题对于LP的一个基B，若B-1b≥0,且λN≤0，则对应

2、于B的基解x(0)便是LP的最优解。若基可行解x(0)所对应的典式中有某个检验数λr>0，且相应有bir≤0，则LP无最优解。若基可行解x(0)所对应的典式中有某个检验数λr>0，且bir中至少有一个大于零，则必存在另一个基可行解，其对应的目标函数值比f(x(0))小。换基并求出新典式确定离基变量：min{bi0/bir

3、bir>0}=bs0/bsr，xjs为离基变量，即用pr代替pjs得新基。确定进基变量：把对应于正检验数的的非基变量转变为基变量例题初始可行基B=(p1,p4,p5)对应典式单纯形表1x1x2x3x4x5f

4、401-100x121-2100x4201-210x5501101单纯形表2x1x2x3x4x5f2001-10x1610-320x2201-210x53003-11单纯形表3x1x2x3x4x5f1000-2/3-1/3x1910011x240101/32/3x31001-1/31/3最优解x(2)=(9,4,1,0,0)最优值f(x(2))=1进行两次单纯形迭代