几何直观 Polytope(多胞体)：LP的可行区域，即满足所有约束的点集 Vertex/,Corner(顶点)：可行区域中n个超平面相交的点 每个约束定义一个半平面(halfspace) 目标函数定义了一个方向： 找到该方向上最“远”的顶点（可能不唯一） 事实1：LP的可行区域总是凸的(convex) 事实2：P一定存在一个最优解在顶点上 Source:Wikipedia CCO 凸集(convex set):Hx,y∈S,t∈[0,1]，tx+(1-t)y∈S 14几何直观 14 Source: Wikipedia CC0 Polytope (多胞体): LP的可行区域，即满足所有约束的点集 Vertex/Corner (顶点): 可行区域中n个超平面相交的点 每个约束定义一个半平面 (halfspace) 目标函数定义了一个方向： 找到该方向上最“远”的顶点（可能不唯一） 事实1: LP的可行区域总是凸的 (convex) 事实2: LP一定存在一个最优解在顶点上 凸集 (convex set): ∀�, � ∈ �, ∀� ∈ 0,1 ,�� + 1 − � � ∈ �