基本解,可行解,基本可行解的区别

对于线性规划
min f(x) (I)
Ax>=b (II)
x>=0 (III)
设A的秩为r,x长度为n
基本解x中至少有n-r个分量为0,同时Ax=b.
可行解是满足(II)及(III)的x.
基本可行解既是基本解也是可行解.

O

可行域是一个凸集，目标函数Z取不同值时，在图上可以得到一族以Z为参数的平行线。也就是等值线。当Z由小变大时，在图上可以看到，当等值线平移到距离原点最远且仍与可行域有一交点时，那个交点便是使Z值取最大值的可行解，因而它是最优解。有时候最优解要在所有的角顶解中解出，所以基本解是在顶点也就是角顶解开始的。最优解也是角顶解中的一个。