Question

求下列线性规划（LP）问题的可行解、基本解、基本可行解？





Answer 1

满足约束条件和非负条件的决策变量的一组取值.使目标函数达到最优值的可行解.设AX=b是含n个决策变量、m个约束条件的LP的约束方程组,B是LP问题的一个基,若令不与B的列相应的n-m个分量（非基变量）都等于零,所得的方程组的解称为方程组AX=b关于基B的基本解,简称为LP的基本解.基本可行解（对应的基为可行基）：满足非负条件的基本解.基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行解.定理1线性规划的可行解集是一个凸集.定理2若一个线性规划有可行解,则它必有基可行解.定理3设线性规划的可行解集为D,则D的顶点（极点）就是线性规划的基可行解.定理4若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.即：最有解一定可以在D的顶点（极点）上达到.定理5若线性规划存在两个相异的基可行解和为最优解,则以为端点的线段上的一切点,也都是线性规划的最优解.