Simplex Method and Unrestricted Variables

1.8k Views Asked by At

I was hoping someone here could explain this issue: say you are working with a set of linear equations in standard form ($a_1 x_1 + a_2 x_2 + a_3 x_3 + \ldots + a_n x_n= c$ where $c$ is the constant), and for all $k$, $x_k$ is unrestricted - meaning that it could be positive or negative (each variable is over the Rationals $\mathbb{Q}$).

Simplex-based algorithms with pivoting rules like Robert Bland's finite method usually only work with positive variables, so we need to fix this. The traditional solution has been to replace $x_k$ with $\delta_{(x,k,+)} - \delta_{(x,k,-)}$, where $\delta_{(x,k,+)}$ represents the positive component of $x$, and the other the negative component. Each $\delta$ is strictly positive, thus allowing us to solve with it.

The implementation I've looked at makes a summation of all the error variables as the objective function - this is intuitive if you're trying to minimize the change in the basic-feasible solution. For instance, if you use the dual simplex method to minimize the error variables over their constraint set, then you're basically trying to bring the unrestricted variables closer to 0 in the objective function, which is actually minimizing the changes needed to be made in the constraint set (which, if you recall what a basic-feasible solution is - we ignore the objective function's value).

My question is this - would the primal simplex method (maximization) have a similar effect? I first thought that it would try to change the unrestricted variables, but then I realized that maximizing them would still cause the net-worth of the unrestricted variable to hit 0 (because a large amount minus itself is still 0).

By turning the unrestricted variables into two error variables, the objective function then has this strange $\sum^n_{k=1} {\big(\delta_{(x,k,+)} + \delta_{(x,k,-)}\big)} = 0$ behavior - I'm now not sure what the effect of maximization or minimization would have on the unrestricted scenario - we would maximize or minimize both variables by the same amount, where the value of $x$ is the difference of the two.

My guess is that primal simplex "puts values where the should be", while dual simplex "moves them as little as possible".