1
$\begingroup$

I have a linear program with the following tableaux:

\begin{array}{crrrrrr|l} & x_1 & x_2 & s_1 & s_2 & s_3 & P & rhs \\ \hline & 67& 126& 52& 36& -7& 0& 988\\ & -24& -46& -19& -14& 3& 0& -358 \\ & -9& -17& -7& -5& 1& 0& -133\\ \hline & -40 & -30 & 0 & 0 & 0 & 1 & 0 \\ \hline \end{array}

where I want to maximize $P$. I want to apply the simplex method starting from the initial solution $(x_1,x_2,s_1,s_2,s_3)=(8,0,8,1,0)$, but I'm confused about how to pivot when nearly all elements of the matrix are nonzero.

$\endgroup$
2
$\begingroup$

You have to make $x_1$, $s_1$, and $s_2$ basic first. To achieve this you can execute a sequence of pivots such that the matrix corresponding to these columns is the identity matrix $I$. This is the same process used in Gaussian elimination to produce a reduced row echelon form. After that continue with Phase II of the Simplex method.

$\endgroup$
  • $\begingroup$ That makes sense. Thank you! $\endgroup$ – user3433489 May 23 at 18:52

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.