可行解按字面意义就可以理解,可行的解。什么是可行?符合所有约束条件就可行,否则不可行。
基本解和基本可行解,这两个玩意可以认为是为了求解
线性规划问题而发明的概念。线性规划不画图应该怎么求解呢?答案是按多元一次方程组来求。
我们知道线性规划都可以转化为标准型(具体转化方法就不赘述了),而标准型写成矩阵形式是下面这样的:
X是一个
列向量,其元素的个数就是题目中未知变量的个数,假如有n个。
目标方程Z其实是各个未知变量按权(就是乘以价值系数)求和的结果。
AX=b是资源约束条件,假如有m个约束条件,那AX=b就有m个方程。为了求X中各未知量的值,我们只要能求解这个方程组就可以了。初中应该学过,多元一次方程组用
高斯消去法,有唯一解的条件是未知量的个数刚好等于方程组的个数(n=m),可在线性规划问题中往往是n>m的。
这种情况怎么做呢?很简单,想办法让n=m,这就用到了基B的概念。一般
运筹学教材的描述是“B是A的m×n阶非奇异子矩阵”。
线性代数学得好的肯定已经明白了,没学好的呢?那就要看如果绕开“非奇异子矩阵”的概念,应该怎么理解。其实就是把A分成n个列向量,从中任意取出了m个,当然这m个列向量必须是线性无关的,就是说不能有哪一个可以用剩下的m-1个表示出来,要不相对于少取了一个。这m个列向量就是一个基B,也叫作基矩阵。从A中刨去B,剩下的n-m个列向量组成的矩阵就是非基N,或者叫非基矩阵。基B对应的变量 [公式] 叫作基变量,非基N对应的变量[公式]叫作非基变量。第一个约束条件也就写成了:
这时我们只要把 [公式] 中变量都设为0,上式就变成了: [公式] ,这是m个线性无关的m元一次方程组成的方程组,消元法就可以求出[公式]来。连带上[公式],得出的 [公式] 就是上述约束条件的解,当然也是原约束条件AX=b的一个解,这个解就是一个基本解。