0

Given the following problem:

$$ \max. -3x_1 -2x_2 - \frac{9}{2}$$ $$ \text{s.t.} -x_1 + x_2 \le 0$$ $$ 5x_1 + 3x_2 \le 8$$ $$ x_1,x_2 \ge 0 $$

When we convert the LP into standard form and then write down the simplex tableau we see that the starting solution is already optimal:$$ x_3 ,x_4 \rightarrow \text{basic variables} $$ $$ x_1, x_2 \rightarrow \text{nonbasic variables}$$ Is it possible to transform the original problem so that the starting solution will be another extreme point?

LinAlg
  • 19,822
moli
  • 69
  • There is only one optimal solution $(x_1^,x_2^)=(0,0)$. It cannot be changed by transforming the original problem. It can only be changed if we change the problem. – callculus42 Dec 10 '20 at 11:51
  • @callculus I am not trying to change the optimal solution. I want to change the problem such that we will start from another basis. Not the basis with the variables (x3,x4) – moli Dec 10 '20 at 14:01

1 Answers1

1

Notice that $(1,1,0,0)$ is also a basic feasible solution.

That is we pick the basis using the first tow columns rather than the last two columns, that is $B=\begin{bmatrix} -1 & 1 \\ 5 & 3\end{bmatrix}$.

Rather than $Ax=b$, we have

$$(B^{-1}A )x = (B^{-1}b)$$

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • But the table is optimal when we pick basic variables as x3 and x4 already. Choosing x1 and x2 as basic variables would make us go back to a nonoptimal basic feasible solution than we will come back to a solution where x3 and x4 give optimal value again – moli Dec 12 '20 at 16:44
  • The problem should be modified , the equations should change but the corner points when plugged in objective function should give the same values as the original problem. – moli Dec 12 '20 at 16:46