LP的顶点 考虑maxc,x),约束在P={Ax≤b}这个polytope内 1边角corner):如果不存在y≠0使得x+y∈P andx-y∈P,则称点x是一个边角 3基本邂：紧致的约束组成的子矩阵A=是满秩的，i.e.rank(A=)=n 1)→3)：或者说是3)→1) 假设存在rank(A=)<n,i.e,y≠0，A-y=0 考虑x+Ey,x-Ey,注意到 A-(x+cy)=Ax A=(x-Ey)=A-x 取足够小，使得其它的不等式约束不被违反 则有x+ey∈P,x-ey∈P 19 LP的顶点 考虑max �, � ，约束在� ≔ {�� ≤ �}这个polytope内 1.边角(corner): 如果不存在� ≠ 0 使得 � + � ∈ � and � − � ∈ �，则称点�是一个边角 3.基本解: 紧致的约束组成的子矩阵�' 是满秩的, i.e. ���� �' = � 1) ⇒ 3): 或者说是¬3) ⇒ ¬1) 假设存在 ���� �' < �, �. �., ∃� ≠ 0, �'y = 0 考虑� + ��, � − ��，注意到 �' � + �� = �'� �' � − �� = �'� 取�足够小，使得其它的不等式约束不被违反 则有� + �� ∈ �, � − �� ∈ � 19