文档介绍：例如： SLP
就是SLP的可行解。
一 可行解，可行域
定义一：称满足全部约束条件的向量为可行解或可行点或。
第二章 线性规划的基本概念和基本定理
§ 线性规划的基本概念
运筹学—线性规划第2章
定义2：称所有可行解（点）构成的集合为可行集或可行域。也称为可行解集。
例如：上面 SLP 的可行域为R={x | Ax=b, x≥0}
定义3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解。这时线性规划的约束条件不相容。
由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非空集和无界非空集。
二 最优解，无界解
定义4：称使目标函数值达到最优值的可行解为线性规划问题的最优解。
运筹学—线性规划第2章
解：问题的可行域是上图
所示的 无界 凸多边形区
域，在此无界可行域上，
目标函数值无上界，所以这个线性规划问题有无界解。
定义5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解 x 满足 Ax = b， x ≥0，使 cx >M。那么称该线性规划问题有无界解。
由定义可知，无界解的 意思 是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界。那么，有无界解的线性规划问题一定没有最优解。
max
：
运筹学—线性规划第2章
例2. max f=
解：此问题的可行域如上图，是一个无界的 多边形。但极大化目标函数却以1为上界。因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值max f=1在可行域射线 上均可达到。
三. 基、基本可行解
定义6：对于约束条件Ax=b，设A是秩m的mｘn矩阵，用(Pj, j=1 ~n) 表示A的第j列向量。即A=( )。由A的m个列向量构成的m阶方阵 B=( )
若B是非奇异的，即detB‡0，则称B为一个基或称为一个基矩阵。
因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的一个基。
运筹学—线性规划第2章
解：A=
使min f=
满足
例3. 求x1----x5
由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组。
按定义，A中m个列向量，只要是线性无关的就可以构成一个基。
定义7：若变量 对应A中列向量 包含在基B中，则称 为
B 的基变量；若变量 对应A中的列向量 不包含在基B中，
则称 为B中的非基变量。
运筹学—线性规划第2章
定义8 ：设Ax=b, x 0一个基 ，其对应的基变量构成的m维列向量记为 这时若取非基
是线性无关，因此 是一组基。而
不在这个基中，所以x1, x2为非基变量。
的列是线性无关的，即
则
运筹学—线性规划第2章
于是得到方程组Ax=b的一个解： 非基变量
称之为对应于基B的基本解。这个定义也告诉我们怎样找一个基本解）
变量等于0，则 Ax=b BxB=b,得唯一解xB=B-
如：上面例2中， 非基变量 x1=x2==5,x4=-2,x5==(0,0,5,-2,21)是对应于基B的一个基本解，但由于x4=-2<，所以这个基本解不是原问题的可行解。（为什么？）
这是因为，按照定义，基本解中的 n-m个非基变量必须取0值只有m个基变量取值才可能不等于0。但可以取负值。因此基本解不一定满足SLP的非负要求。
定义9：对应于基B的基本解，若基变量取非负值，即xB=B-1b>=0，则称它为满足约束 Ax=b, x>=o的基本可行解。
对应地称B为可行基，因SLP中具有此约束条件。也通常 称为SLP的基本可行解。
运筹学—线性规划第2章
上面我们讲到基本解中