1
$\begingroup$

If I am trying to solve a minimization problem without converting it to a maximization problem how do I decide which variable to pivot ?

I think it involves looking at the ratio of that variable with the RHS but unsure if I should choose the variable. Is the one with the smallest ratio or the largest.

Here is the problem that I have:

Minimize:

$x_1+x_2-4x_3$

Subject to:

$$ \begin{align} x_1+x_2+2x_3+x_4=9\\ x_1+x_2-x_3+x_5=2\\ -x_1+x_2+x_3+x_6=4\\ x_1,x_2,x_3,x_4,x_5,x_6 \geq 0\\ \end{align}$$

In this case I know the 4 needs to be pivoted to made negative but not sure if I need to use the $x_4,x_5,x_6$ as the first pivot.

$\endgroup$
2
$\begingroup$

Minimising $x_1+x_2-4x_3$ is equivalent to maximising it's additive inverse, so we can simply copy the coefficients in the original problem to the last row of the inital simplex tableau:

\begin{array}{r|rrrrrr|rr} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \text{RHS} & \text{ratio}\\ \hline x_4 & 1 & 1 & 2 & 1 & 0 & 0 & 9 & 9/2 \\ x_5 & 1 & 1 & -1 & 0 & 1 & 0 & 2 & - \\ x_6 & -1 & 1 & 1^* & 0 & 0 & 1 & 4 & 4\\ \hline & 1 & 1 & -4 & 0 & 0 & 0 & 0 \end{array}

Choose the most negative number at the $z$-row (-4 in this case.), just like what we do for a standard simplex maximisation problem.

Then pick the least nonnegative number at the "ratio" column. (You may consult my other post on choosing the leaving variable for further explanation.)

\begin{array}{r|rrrrrr|rr} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \text{RHS} & \text{ratio}\\ \hline x_4 & 3^* & -1 & 0 & 1 & 0 & -2 & 1 & 1/3\\ x_5 & 0 & 2 & 0 & 0 & 1 & 1 & 6 & - \\ x_3 & -1 & 1 & 1 & 0 & 0 & 1 & 4 & - \\ \hline & -3 & 5 & 0 & 0 & 0 & 4 & 16 \end{array}

\begin{array}{r|rrrrrr|r} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \text{RHS} \\ \hline x_1 & 1 & -1/3 & 0 & 1/3 & 0 & -2/3 & 1/3 \\ x_5 & 0 & 2 & 0 & 0 & 1 & 1 & 6 \\ x_3 & 0 & 2/3 & 1 & 1/3 & 0 & 1/3 & 13/3 \\ \hline & 0 & 4 & 0 & 1 & 0 & 2 & 17 \end{array}

Hence our optimal solution is $(x_1,x_2,x_3,x_4,x_5,x_6) = (1/3, 0, 13/3, 0 ,6, 0)$ with optimal value -17.

$\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.