摘要
一般,在运筹学中带自由变量的线性规划问题只有传统的变量替换法。即令自由变量x_i=x′_i-x″_i(其中x′_i≥0,x″_i≥0),把带自由变量的线性规划问题转换为一般线性规划标准型后求解。这样经变量替换后,增加了变量个数,从而增加了问题的计算量和难度。本文提出一种不需要变量替换而直接用单纯形法求解的新方法。文中首先给出了此类问题的可行解定义,指出与一般线性规划问题类似,此类问题也有基,基础解、基础可行解、基础最优解等慨念。于是有对应的单纯形表。然后通过3个定理论证了单纯形解法的正确性及具体的解法。
Generally,in operation research there is only one traditinal method of variable trasformation for linear programing with free variable.Given that the free variable x_j=x_j~′-x_j~″,(x_j≥0,x_j~″≥0), the linear programing with free variable will be trasformed into common linear programing,which will be worked out.The method of variable trasformation,however,increases the number of variable, the times of computation and the degree of complexiry.In this paper a new method has been introduced,which does not need the variable trasformation.A direct use of the simplex method may solve the pro- blem.The paper,firstly,presents the definition of feasible solution. and suggest that the linear programing with free variable also has the concept of base,basic solution,basic feasible solution,optimal basic solution,and simplex table as common linear programing does.Secondly simplex method is explained by demonstrating the three principles in the paper,and thus the specific solution is given.
