一种改进的单纯形最优化方法  

A New Improved Optimal Method of Simplex Algorithm

作　　者：董兵[1] 梁俊[1] 

机构地区：[1]中国民航飞行学院计算机学院,四川广汉618307

出　　处：《重庆师范大学学报（自然科学版）》2010年第4期9-11,共3页Journal of Chongqing Normal University:Natural Science

基　　金：中国民航飞行学院自然科学基金项目(No.J2008-76)

摘　　要：对求极小化线性规划问题maxZ=CX,AX=b,X≥0,通过添加人工变量,可直接获得问题的基解,若求得问题的基解不是原问题的可行解,也不是对偶问题的可行解的情况下,本文给出了求解该类规划问题初始可行解的一般方法。迭代过程如下:令((bp)/(aps))=minp∈P,itn∈T{((bp)/(apt))},若((br)/(ars))≤((bp)/(aps)),则以ars为主元,若((br)/(ars))≥((bp)/(aps)),则以aps为主元,对单纯形表进行初等行变换,可获得问题的可行解或最优解。与大M法和两阶段法相比,该算法计算量大大减少。最后给出了具体实例。Considering the linear program for minimal solution with standard style ： max Z = CX,AX = b, by adding artificial variables, the directly based solution can be obtained. If the problem doesn＇ t have either feasible or dual feasible base solution, a new common method is obtained in the paper. Iterative process as following as： Let bp/aps=min p∈P,t∈T{bp/apt},Ifbr/ars≤bp/apsPlaces ars as the main element,if br/ars≥bp/aps, places aps as the main element. Row transformation the simplex table elementary, a feasible solution of the problem or the optimal solution are obtained. Through the analysis and comparison with a big-M method, two-phase method, the results show that it is a simple effective and feasible method. Two examples are given.

关 键 词：线性规划 单纯形法 典式 

分 类 号：O221.1[理学—运筹学与控制论]