向量和子空间投影定理〔.ppt

第 二 章;2.0、预备知识;2.0、预备知识（续）;2.0、预备知识（续）;2.0、预备知识（续）;2.0、预备知识（续）;2.0、预备知识（续）;2.0、预备知识（续）;2.0、预备知识（续）;2.1 数学规划模型的一般形式 min f(x) --------目标函数 s.t. x?S --------约束集合，可行集 其中，S ? Rn，f :S ? R，x?S称（f S )的可行解 最优解: x*?S，满足f (x*)≤ f (x), ? x?S。则称 x*为(f S)的全局最优解(最优解), 记 g.opt.(global optimum),简记 opt. 最优值: x*为(f S)的最优解, 则称 f * = f (x*) 为 (f S)的最优值(最优目标函数值);2.1 数学规划模型的一般形式（续）;2.1 数学规划模型的一般形式（续）;2.2 凸集、凸函数和凸规划;2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.2 凸集、凸函数和凸规划(续);2.3 多面体、极点、极方向;2.3 多面体、极点、极方向;2.3 多面体、极点、极方向;2.3 多面体、极点、极方向;考虑多面体 S = { x?Rn?Ax = b , x≥0 }，其中 3 2 1 0 0 65 A = 2 1 0 1 0 b = 40 0 3 0 0 1 75 即 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 ≥ 0 ; 3 2 1 0 0 A = [ P1 , P2 , P3 , P4 , P5 ] = 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个3×3的子矩阵： B1=[p1 ，p2 ，p3] B2=[p1 ，p2 ，p4] B3=[p1 ，p2 ，p5] B4=[p1 ，p3 ，p4] B5=[p1 ，p3 ，p5] B6=[p1 ，p4 ，p5] B7=[p2 ，p3 ，p4] B8=[p2 ，p3 ，p5] B9=[p2 ，p4 ，p5] B10=[p3 ，p4 ，p5]? ; 其中?B4?= 0，因而B4不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有9个可构成极点、极方向的子矩阵，我们称之为基。 对于基B3=[p1 ，p2 ，p5]，令x3 = 0， x4 = 0，在等式约束中令x3 = 0，x4 = 0，解线性方程组： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，对应的极点： x = (x1，x2，x3，x4，x5 )T = (15，10，0，0，45 )T; 类似可得到极点 x(2) = (5, 25, 0, 5, 0 )T （对应B2） x(7) = (20, 0, 5, 0, 75 )T （对应B5） x(8) = (0, 25, 15, 15, 0 )T （对应B7） x(9) = (0, 0, 65, 40, 75 )T （对应B10） 而 x(3)= (0, 32.5, 0, 7.5, -22.5 )T（对应B9） x(4)= (65/3, 0, 0, -10/3, 75 )T （