[教育]01线性规划3.ppt

3 1 0 3 1 0 1 基 基向量 非基向量 基变量 非基变量 基本解 （P1 P2) P1 P2 P3 P4 X1, X2 X3,X4 (11/7,2/7,0,0)T （P1 P3) P1 P3 P2 P4 X1, X3 X2,X4 (5/3,0,2/3,0)T （P1 P4) P1 P4 P2 P3 X1, X4 X2,X3 (2 , 0 , 0 ,-1)T （P2 P3 ) P2 P3 P1 P4 …… (0 ,5 ,-11 ,0)T （P2 P4) …… (0 ,4/3 ,0 ,11/3)T （P3 P4) P3 P4 P1 P2 X3, X4 X1,X2 (0 ,0 ,4 , 5 )T X=(11/7 , 2/7 ,0 ,0)T满足非负条件，既是基本解又是可行解，称为基本可行解，对应的基为可行基 （即满足非负条件的基本解为基本可行解，基本可行解非零分量都是正分量，其个数小于或等于m） X=(2 , 0 , 0, -1)T不满足非负条件，是基本解不是可行解 （P1 P2 P3 P4 ） 该模型约束方程 2X1+ 3 X2 + X3 =4 ① 3X1 + X2 + X4=5 ② 系数矩阵A= 基的个数=C42=6 上例：Max z=3X1+ X2 2X1+ 3 X2 ≤4 ① 3X1 + X2 ≤5 ② X1， X2 ≧0 ③ 基本解X(X1, X2 X3, X4 )T A：(11/7,2/7,0,0)T B：(5/3,0,2/3,0)T C：(2 , 0 , 0 ,-1)T D：(0 ,5 ,-11 ,0)T E：(0 ,4/3 ,0 ,11/3)T F：( 0 ,0 ,4 , 5 )T 基本可行解A、B、E、F 最优解A、B 线性规划问题解的几何意义 ⑴ 0 1 2 3 1 2 x2 x1 ⑵ A B C D F E 可行解：满足约束条件 ①②③的解为线性规划问题的可行解(可行域内各点） 基本解：图中各约束线之间，约束线(或延长线)与坐标轴之间的交点A、B、C、D、E、F都是基本解 基本可行解:可行域的各顶点A、B、E、F 一、基本概念 1.凸集：给定一个点集K（n为欧氏空间）在集合内任取两点，如果连线上的点也在集合内，则K为凸集。 即点集K,集合内任意两点X（1）∈K,X（2）∈K，若X（1）、X（2）连线上的点X=αX（1）+(1-α)X（2）∈K(0≤α≤1 ),则K为凸集。 ﹒ ﹒ X（1） X（2） X ﹒ ﹒ ﹒ ﹒ X（1） X（2） X 凸集 非凸集 非凸集 线性规划问题的几何意义 2.凸组合：设X（1）、X（2） …… X（k）为n维空间K个点，若存在一组数?1 ?2…… ?k且0≤?i≤1，∑?i=1 使X=?1X（1）+?2X（2）+…… +?k X（k）,则称X为X（1）、X（2）、……X（k）的凸组合。 3.极点：设K为凸集,有点X∈K,若X不能用K内不同两点X(1)、X(2)线性组合表示为X= ? X（1）+（1- ? ）X（2） （0＜? ＜1）， 即X不在 X（1） 、 X（2）连线上，则X为极点(顶点)。 ﹒ ﹒ X（1） X 凸集 二、解的性质 定理1：若线性规划问题存在可行域，则其可行域为凸集。 证明：设LP问题可行域为D，D={X∣AX=b，X≥0} D内任意取两点X（1）∈D，X（2）∈D， 则X（1）、X（2）必然满足约束条件，即 A X（1）=b ， X（1） ≥0