0
$\begingroup$

I know there are a number of ways to use a simplex tableau in linear programming to find the minimum value for an equation given constraints, including transposing the simplex tableau etc. etc. However, my teacher specifically mentioned that he would like us to minimise equations by multiplying the objective by -1 and turning any 'greater than' inequalities into 'less than' inequalities by multiplying by -1. This makes sense to me mathematically, however my resulting simplex tableau (before pivoting) has negative values in the constraint column (which is not allowed) and only positive values in the objective row (which suggests the optimum solution has been reached). What do I do to actually find the optimal solution? I know this isn't very well explained and I've probably got something wrong here but help would be much appreciated.

$\endgroup$
0
$\begingroup$

You'll need the "two phase" version of the simplex method for this. During the first phase applied, one (if needed) does operations whose goal is to make the entries of the constraint column all non-negative. There are rules in this case for where to pivot, and typically while doing phase one some negative entries will wind up in the objective row.

Once phase one is done, you have a usual simplex problem with non-negative constraints which is then solved. That's called by some the "phase two" part of the simplex algorithm.

I don't have a link handy but try something like "two phase simplex algorithm" to look it up.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.