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

可行解、可行解集（可行域） 最优解、最优值 基、基变量、非基变量 基解、基可行解 设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可表示为 求解线性规划问题 对于LP的一个基B，若B-1b≥0,且λN≤0，则对应于B的基解x(0)便是LP的最优解。 若基可行解x(0)所对应的典式中有某个检验数λr0 ，且相应有bir≤0 ，则LP无最优解。 若基可行解x(0)所对应的典式中有某个检验数λr0 ，且bir中至少有一个大于零，则必存在另一个基可行解，其对应的目标函数值比f(x(0))小。 换基并求出新典式 确定离基变量：min{bi0/bir|bir0}=bs0/bsr， xjs为离基变量，即用pr代替pjs得新基。 确定进基变量：把对应于正检验数的的非 基变量转变为基变量 例题 初始可行基B=(p1, p4 ,p5) 对应典式 单纯形表1 单纯形表2 单纯形表3 最优解x(2)=(9,4,1,0,0) 最优值f(x(2))=1 进行两次单纯形迭代 * * * * * * 线性规划解的概念 1 0 1 1 0 5 x5 0 1 -2 1 0 2 x4 0 0 1 -2 1 2 x1 0 0 -1 1 0 4 f x5 x4 x3 x2 x1 1 -1 3 0 0 3 x5 0 1 -2 1 0 2 x2 0 2 -3 0 1 6 x1 0 -1 1 0 0 2 f x5 x4 x3 x2 x1 1/3 - 1/3 1 0 0 1 x3 2/3 1/3 0 1 0 4 x2 1 1 0 0 1 9 x1 -1/3 -2/3 0 0 0 1 f x5 x4 x3 x2 x1