A Revised Method for Determining all Extreme Points to Span a Convex Polytope Under Linear Inequalities

Abstract

線性不等式Σnj=1aijxj≦bi，i=1，2，3，……，m及xj≧0，j=1，2，3，……，n，求其可行基解(feasiblebasic solution)或非負數解(non-negative solution)，此線性不等式可構成一幾何圖形－－凸多面體 (convex polytope)而其可行基解必在凸多面體頂點上(vertex)或極點(extreme point)上，當變數超過三個即n大於3時無幾何圖形解，本文應用基集合(basicset)及非基集合(non-basic set)內元素(element)對換而根據單純法(Simplex method)計算出全部可行基解而得到所有極點以構成一凸多面體表示其幾何圖形解。