带自由变量的线性规划问题的直接解法——单纯形法

一般,在运筹学中带自由变量的线性规划问题只有传统的变量替换法。即令自由变量x_i=x′_i-x″_i(其中x′_i≥0,x″_i≥0),把带自由变量的线性规划问题转换为一般线性规划标准型后求解。这样经变量替换后,增加了变量个数,从而增加了问题的计算量和难度。本文提出一种不需要变量替换而直接用单纯形法求解的新方法。文中首先给出了此类问题的可行解定义,指出与一般线性规划问题类似,此类问题也有基,基础解、基础可行解、基础最优解等慨念。于是有对应的单纯形表。然后通过3个定理论证了单纯形解法的正确性及具体的解法。