1
$\begingroup$

I had an issue understanding wich matrix enters the bases in a linear programing exercise done during a lecture : the variable that entered the basis is one which has negative coefficient in $\hat c$ in the case of a $\max$ problem.

$$ \begin{cases} \begin{aligned} \max \ & 2x_1&+ 3x_2\\ &3x_1&+5x_2&\le 15\\ &4x_1&+x_2&\le 8\\ &x_1&+x_2&\ge 1\\ \forall i, x_i \end{aligned} \end{cases} $$

was transformed with slack variables into :

$$ \begin{cases} \begin{aligned} \max \ & 2x_1&+ 3x_2\\ &3x_1&+5x_2&+x_3&&&= 15\\ &4x_1&+x_2&&+x_4&&= 8\\ &x_1&+x_2&&&+x_5&= 1\\ \forall i, x_i \end{aligned} \end{cases} $$

I think there is a mistake in the last line, shouldn't it be : $-x_1-x_2+x_5= 1$? Because it leads me to an absurdity about which variable enters the matrix when doing revised simplex method:

\begin{align*} \hat{c} &= c -\Pi A\\ &=\begin{pmatrix} 2 & 3 & 0 & 0 & 0 \end{pmatrix}-\begin{pmatrix} 0 & 0 & 2 \end{pmatrix}\begin{pmatrix} 3& 5 & 1 & 0 & 0\\ 4 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\\ \hat{c}&=\begin{pmatrix} 0 & 1 & 0 & 0 & -2 \end{pmatrix} \end{align*}

Then it was said that $x_5$ enters the matrix. Yet, its coefficient is negative in $\hat c$.

$\endgroup$
1
$\begingroup$

The last line of the formulation in standard form is wrong. It should read $x_1+x_2-x_5 = 1$ ($x_5$ is subtracted as an excess variable).

Indeed $x_5$ enters the basis since the coefficient is negative and it is a $\max$ problem. No contradiction there.

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