1-2 线性规划问题
解的概念和性质
一,LP问题的各种解
1,可行解, 满足约束条件和非负条
件的决策变量的一组取值 。
2,最优解,使目标函数达到最优值
的可行解 。
3.（ 见下页 ）
3,基本解, 设 AX=b是含 n个决策变量、
m个约束条件的 LP的约束方程组，
B是 LP问题的一个基，若令不与 B
的列相应的 n-m个分量（非基变量）
都等于零，所得的方程组的解称为
方程组 AX=b关于基 B的基本解,简
称为 LP的基本解 。
B P j x j 0
基 m 个独立向量组成 基向量 对应之决策变量 基变量 剩余 n - m 个变量 非基变量
令非基变量取值为零，计算出基变量取值，两者搭配构成基本解 。
4.基本可行解 （对应的基为可行基）：
满 足非负条件的基本解。
5.基本最优解 （对应的基为最优基）：
使 目标函数达到最优值的基本可行解。
最优解 基本最优解
用画图, 模型制作, 三维动画等方
法清楚地显示其可行解, 基本解, 基本
可行解 。 进一步具体计算出这些解来,
说明它们之间的关系 。
每个小组交 1份报告 。
课后小组讨论 1,研究约束集合
?
?
?
?
?
?
??
???
0,,
132
1
..
321
21
321
xxx
xx
xxx
ts