Given that I have a question of an objective function to minimize or maximize and I have a constraint for the same such that when converting to equation form for using simplex method would require an artificial variable. For example:
$$Max\;Z =\;100\,x_1\,+\,300x_2$$
Subject to
$$x_1\,+\,x_2\,\le80$$
$$6x_1\,+\,10x_2\,\le720$$
$$x_1\ge30,\,x_2\ge20$$
Didn't write non negativity constraint as it would be redundant
Here the last two constraint when written in standard form would have artificial variable hence the starting simplex table would have 4 starting variables.
Assuming we can convert these last two constraints into non negativity constraint by introducing and substituting new variable $X_1=x_1-30\quad$ & $\quad X_2=x_2-20\,$ where $\,X_1\ge0\;$ & $\;X_2\ge0\;$ and subsequently substitute them in the objective function and solve the new equation using simplex.
The new equation I am getting is
$$Max\,Z'=100X_1\,+300X_2\,+3000+6000\,$$
(maximizing only first 2 terms as rest are constant)
Subject to
$$X_1\,+\,X_2\le30$$
$$6X_1\,+\,10X_2\le340$$
$$X_1,X_2\ge0$$
I am getting the answer for both methods using 4 starting variables and using new substitution method which has 2 starting variable, the same. Answer from first method $x_1=30,x_2=50$ and from second method $X_1=0,X_2=20$ which is same when substituted back to $x_2\,\&\,x_1$.
I have tried this method on 2-3 more problems and all had same answers. The main effect of this method is that it reduces number of iterations of simplex method by 1-2.
My question is this method correct or not? If so can you provide a link or proof cause my professor isn't accepting this method without text to back it with.
Best Answer
What you’re effectively doing is called Lower-Bound Substitution. The Simplex method requires an initial Basic Feasible Solution. Normally, the lower bounds of a Linear Model is where all values of $x$ are equal to zero, i.e. $(x_1, x_2, \ldots, x_n)=(0,0,\ldots,0)$, or what is called the origin
By doing lower-bound substitution, it is effectively pre-solving the model to start on the basic feasible extreme point where $(x_1, x_2, \ldots, x_n)=(l_1, l_2, \ldots, l_n)$ where $l_n$ is the lower bound that corresponds to the decision variable $x_n$ that is found in the constraint $x_n \ge l_n$. Graphically, the feasible region of the model looks like so:
The purple dot (at the origin) is where we’d be starting if we used the artificial basis. The green dot is where we’d be starting given then lower-bound substitution method.
Thus, this method is considered a standard method for solving models with non-zero lower-bounds, as like you pointed out, it will reduce the amount of pivots needed to go from the artificial solution to a basic feasible solution (in other words, remove the extra constraints present in the model). The first link above goes into bounded problems on a much deeper level like your professor is wanting