Sorry for the vague title, wasn't sure quite how to put it.
I'm supposed to implement a two-phase simplex method solver as a part of one course at my faculty. I'm thinking that I either don't understand something or maybe the algorithm statement, as written by our professor, is wrong.
The original problem is given as:
Minimize:
$$c^Tx$$
subject to constraints:
$$Ax = b$$
$$x \geq 0$$
So in phase 1 we're supposed to add artificial variables so that we end up having the basis submatrix. That is written as follows:
We introduce artificial variables $w_1, ….w_m$ and we solve the following problem:
Minimize $w_1 +… + w_m$
subject to constraints
$Ax + Ew = b$
$x, w \geq 0$
And for this we're supposed to use any other (say the regular tableau) simplex method.
However, the thing that seems contradictory here is that in our own statement of the regular simplex method the very first step says the following:
If $c_j \geq 0 \quad (\forall j)$ then STOP, the optimal solution is found.
That is, if all the coefficient of the objective function are positive, we have reached the optimal solution. Since our objective function in this sub-problem we're solving is always the sum of artificial variables, won't this condition always hold and the simplex always immediately stop? Or am I missing something?
Thanks in advance.
Best Answer
The optimality condition is that all reduced costs (under standard conventions, these are the entries in the top row of the simplex table) must be non-negative. The reduced costs are not necessarily the coefficients of the objective function, and in particular they won't be if any variable in the basis has a non-zero coefficient in the objective function, because the reduced costs for the basic variables must be zero for the simplex table to be valid. This is exactly what happens in the first phase of the two phase method: all $w_i$ are in the initial basis and have non-zero coefficients in the objective function.
One way to fix this is to perform some simple row operations on the table to ensure that the reduced costs of the $w_i$ are zero, and thus that the simplex table correctly shows the reduced costs for all non-basic variables.