教案_线性规划.PPTVIP

page() * * 1．4 线性规划问题解的概念(从标准型式引入) i =1，2，…，m xj ? 0 j =1，2，…，n max z =CX （1.4） AX = b （1.5） X ? 0 （1.6） ? 可行解 满足约束条件(1.5)、(1.6)的解 X=( x1，x2，···，xn)T； ? 最优解 使目标函数（1.4）达到最大值的可行解； ? 基 A中的m× m 阶非奇异矩阵B ； （意味着A的秩为m，|B | ≠ 0，B 的各列线性无关） ? 基 A中的m × m 阶非奇异子矩阵B ； （意味着A的秩为m，|B | ≠ 0，B 的各列线性无关） · 基向量 B中的列向量； · 基变量 B中的列向量对应的变量； · 非基变量 非B中的列向量对应的变量； 例如，若A的前m列线性无关，则 a11 … a12 … a1m a21 … a22 … a2m … … am1 … am2 …amm =( P1，P2，…，Pm ) B = 是个基。 P1，P2，…，Pm是基向量； x1，x2，…，xm 是基变量； xm+1，…，xn 是非基变量； 若Am×n，mn，则至多有 个基，每个基有m个基变量，n- m 个非基变量。 · 基解 对应每一个基B,令所有非基变量为零，由 (1.5) 约束方程组求得的解X ； 约束方程组(1.5)中，有m 个方程n 个变量，mn，有无穷多解，若前m个系数向量线性无关，令xm+1=…=xn =0，则可求出XB =( x1，x2，…，xm)T，则X=( x1，x2，…，xm，0，…，0)T就是一个基解。 至多有 个基解，基解的非零分量至多m个，非零分量个数小于m 的基解为退化解。 ? 基可行解 满足非负条件(1.6)的基解； 同样至多有 个基可行解，基可行解至多有m个正分量。 · 可行基 对应于基可行解的基； · 基最优解 使目标函数达到最大值的基可行解。 ： 上述解的概念中基解和基可行解最为重要，各种解的关系粗略地可用下图表示： 非可行解 可行解 基解 基 可 行 解 最优解 如例1，max z = 2x1 + 3x2 s.t. x1 + 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 +x5 =12 x1，x2，x3，x4，x5 ?0 以(P3、P4、P5)作为基，令x1 = x2 =0，得到 X=(0，0，8，16，12)T为一个基可行解，对应图中O点； 2 x2 = 8 x4 =16 4 x2 +x5 =12 以(P1、P2、P5)为基，令x3 = x4 =0，可得X=(4，2，0，0，4)T是基最优解，对应图中Q2点。 x1 x2 O 4 Q2(4,2) Q1 Q3 Q4 3 A 以(P2、P4、P5)作为基，令x1 = x3 =0，由 得X=(0，4，0，16，-4)T是个基解，不是基可行解，对应图中A点； §2 线性规划问题的几何意义 本节重点： 凸组合的概念 凸集的概念 线性规划基本定理 2．1 基本概念 ? 凸组合 设 ，若存在 ，0 ? ? 1 ，且 ，使 则称X 为 的凸组合。 X1 X2 X 2 1 二维空间 两点连线上的任何一点都是这两点的凸组合 (a) (b) (c) (d) (e) 凸集 (a) (b) (c) (d) (e) 图中红粗线和红点是顶点。 结论： 线性规划问题的可行域是凸集（凸多面体），有有限多个顶点。顶点对应基可行解。当可行域有界时，必有顶点达到目标函数最优值。 * * * * * *