线性规划(基本概念)课件.ppt

作业与思考 作业： 习题1: 1 思考： 习题1：19,20 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当S的值增加时，目标函数同约束条件：4x1+3x2 ? 120 重合，Q2与Q3之间都是最优解。 Q1（25，0） Q2（15，20） Q3（0，40） 解的讨论： 无界解： 例：max S=x1+x2 s.t. -2x1+x2 ? 20 x1-x2 ? 5 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。 x1-x2 = 5 -2x1+x2 = 20 解的讨论： 无可行解： 例：max S=2x1+3x2 s.t. x1+2x2 ? 8 x1 ? 4 x2 ? 3 x1+2x2 ? 9 x1,x2 ? 0 该问题可行域为空集，即无可行解，也不存在最优解。 解的情况： 有可行解 ⊙有唯一最优解 ⊙有无穷最优解 ⊙无最优解 无可行解 线性规划问题解的概念 线性规划标准型的矩阵形式： Max S = CX （1-9） s.t. AX=b （1-10） X ? 0 （1-11） a11 a12 …. a1n b1 A= a21 a22 …. a2n b = b2 …………………………… ………… am1 am2 …. amn bm c1 x1 0 c2 x2 0 CT= X= 0= …… …… ….. cn xn 0 解、可行解、最优解 ⊙满足约束条件（1-10）的X，称为 线性规划问题的解。 ⊙满足约束条件（1-10）与（1-11） 的X，称为线性规划的问题可行解。 ⊙满足目标函数（1-9）的可行解X， 称为线性规划的问题最优解。 基、基向量、基变量 ⊙设r(A)=m,并且B是A的m 阶非奇异的子矩阵（det(B)?0),则称矩阵B为线性规划问题的一个基。 ⊙矩阵B=（P1，P2….Pm) ，其列向量Pj称为对应基B的基向量。 ⊙与基向量 Pj 相对应的变量xj就称为基变量，其余的就称为非基变量。 基础解.基础可行解.可行基 ⊙对于某一特定的基B，非基变量取0值的解，称为基础解。 ⊙满足非负约束条件的基础解，称为基础可行解。 ⊙与基础可行解对应的基，称为可行基。 例1.4： max S = 2x1 + 3x2 （1-12） s.t. -2x1 + 3x2 ? 6 （1-13-1） 3x1 - 2x2 ? 6 （1-13-2） x1 + x2 ? 4 （1-13-3） x1, x2 ? 0