1
$\begingroup$

Why the requirement that variables must be non-negative isn't written in the corresponding tableau? Isn't this kind of constraint equivalent to others? For instance consider some LP with 2 variables $x_1 \geq 0, x_2 \geq 0$. I expect, that I can add two extra rows at the end of the tableau: $\left[\begin{array}{ccc|c}... &1& 0& 0\end{array}\right]$ and $\left[\begin{array}{ccc|c}... &0& 1& 0\end{array}\right]$. The reason that caused this question is that I obtain optimal value of LP with negative entries, but it must not by the condition of the exercise and I can't find another solution by the simplex method, only by selection, which isn't convenient.

UPD: I clarify a bit my problem. Firstly I mention, that I learn linear algebra and I encountered simplex method in context with linear algebra's methods, so my method of solving problem may differ a little bit from common. I have an optimization problem:

$\begin{array}{ll} \min & x_1+2x_2-x_3\\ s.t. & x_2-x_3\le 3\\ &2x_1+2x_2-x_3=1\\ &x_1+2x_2+2x_3\le3\\ & x_1,x_2,x_3\ge0 \end{array}$

I have put my problem into standard form (changed "=" constraint by two equivalent "<=" constraints and replaced minimize problem with maximize by multiplying objective function by -1):

$\begin{array}{ll} \max & -x_1-2x_2 +x_3\\ s.t.& x_2 -x_3 \le 3\\ & 2x_1+2x_2 -x_3 \le 1\\ & -2x_1-2x_2 +x_3 \le -1\\ & x_1+2x_2+2x_3 \le 3\\ & x_1, x_2, x_3 \ge 0\end{array}$

Then, as I don't have starting feasible solution (0,0,0), I transform my problem:

  1. $\max -x_1-2x_2+x_3 \rightarrow \max -y$
  2. I subtract "y" from each constraint that have negative right-side.

$$ \begin{array}{ll} \max & -y\\ s.t.&x_2 -x_3 \le 3\\ &2x_1+2x_2 -x_3 \le 1\\ &-2x_1-2x_2 +x_3 -y \le -1\\ &x_1+2x_2+2x_3 \le 3\\ &x_1, x_2, x_3, y \ge 0 \end{array} $$

This program have obvious feasible solution (0,0,0,1). By pivoting on column of corresponding tableau I have found another solution (1,0,1,0) that gives me optimal value of "-y" equals 0, so I know that initial LP is feasible and at least have solution (1,0,1) (this answer is correct, but isn't supposed to be by the explanation from textbook).

Then I can pivot on columns of tableau corresponding initial LP.

\begin{array}{c|cccc|ccc|c} 1 & 0 & 0 & 0 & 0 & 1 & 2 & -1 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 3 \\ 0 & 0 & 1 & 0 & 0 & 2 & 2 & -1 & 1 \\ 0 & 0 & 0 & 1 & 0 & -2 & -2 & 1 & -1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 3 \\ \end{array}

\begin{array}{c|cccc|ccc|c} 1 & 0 & 0 & 0 & -1 & 0 & 0 & -3 & -3 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 3 \\ 0 & 0 & 1 & 0 & -2 & 0 & -2 & -5 & -5 \\ 0 & 0 & 0 & 1 & 2 & 0 & 2 & 5 & 5 \\ 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 3 \\ \end{array}

\begin{array}{c|cccc|ccc|c} 1 & 0 & 0 & 0 & -1 & 0 & 0 & -3 & -3 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 3 \\ 0 & 0 & -1/5 & 0 & 2/5 & 0 & 2/5 & 1 & 1 \\ 0 & 0 & 0 & 1/5 & 2/5 & 0 & 2/5 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 2 & 2 & 3 \\ \end{array}

\begin{array}{c|cccc|ccc|c} 1 & 0 & -3/5 & 0 & 1/5 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & -1/5 & 0 & 2/5 & 0 & 7/5 & 0 & 4 \\ 0 & 0 & -1/5 & 0 & 2/5 & 0 & 2/5 & 1 & 1 \\ 0 & 0 & 1/5 & 1/5 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2/5 & 0 & 1/5 & 1 & 6/5 & 0 & 1 \\ \end{array}

From here you can see that (-17/7, 20/7, -1/7) is solution (optimal value -24/7), but contains negative entries. Correct answer written in textbook is (1,0,1) with optimal value 0. I suspect, that I have add $x_1,x_2,x_3 \ge 0$ constraints to tableau. Any help would be appreciated.

$\endgroup$
8
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$ Commented Nov 12, 2023 at 0:02
  • $\begingroup$ Can you explicit your problem and the steps you made? Did you use slack variables? You are not supposed to get negative variables with the revised simplex. $\endgroup$ Commented Nov 12, 2023 at 9:48
  • $\begingroup$ @caduk I have clarified my question. $\endgroup$ Commented Nov 12, 2023 at 11:04
  • 1
    $\begingroup$ If you want, you can use just $-y$ as an objective function, but you still need to update the original objective function when pivoting or recompute it in the new basis once you find a feasible solution. $\endgroup$ Commented Nov 12, 2023 at 15:21
  • 1
    $\begingroup$ The tableau depends on a choice of basis, which, unless degeneracy, is uniquely determined by the current vertex of the polyhedra where we are. Variables are split between non basic variables (that are zeros) and basic variables. This dichotomy depends on the vertex where we are. The constraints and the objective function are at each step expressed as a linear expression of the non-basic variables. When we pivot, a non-basic variable become a basic variable and a basic variable become a non-basic variable so we have to pivot to re-express constraints in term of the new non-basic variables. $\endgroup$ Commented Nov 12, 2023 at 22:14

1 Answer 1

Reset to default
0
$\begingroup$

Given the original problem, $$ \begin{array}{ll} \min & x_1+2x_2-x_3\\ s.t. & x_2-x_3\le 3\\ &2x_1+2x_2-x_3=1\\ &x_1+2x_2+2x_3\le3\\ & x_1,x_2,x_3\ge0 \end{array} $$

The standard form, using Big-M, becomes, $$ \begin{array}{ll} \min & x_1+2x_2-x_3+Ma_1\\ s.t. & x_2-x_3+s_1= 3\\ &2x_1+2x_2-x_3+a_2=1\\ &x_1+2x_2+2x_3+s_3=3\\ & x_1,x_2,x_3,s_1,s_3,a_1\ge0 \end{array} $$

Recall that the standard form problem aims to convert $$ \begin{array}{ll} \max & c^Tx\\ s.t. & Ax\le b\\ & x\ge0 \end{array} $$

into $$ \begin{array}{ll} \max & c^Tx\\ s.t. & Ax= b\\ & x\ge0 \end{array} $$

This can be done by adding slack variables $s_n$ to $\le$ constraints and excess variables $-s_n$ to $\ge$ constraints. Additionally, the right-hand-side $b$ must be non-negative. The problem with your formulation is that you have $-1$ on the right-hand side, which isn't allowed for the simplex method to operate.

For the given model, the initial simplex tableau becomes:

$$ \begin{array}{|c|c|c|c|} \hline BV &z &x_1&x_2&x_3&s_1&s_3&a_2&RHS\\\hline z&1&-1&-2&1&0&0&-M&0\\\hline s_1 & 0 & 0 & 1&-1&1&0&0&3\\ ? & 0 & 2&2&-1&0&0&1&1\\ s_3&0&1&2&2&0&1&0&3\\\hline \end{array} $$

Solving for the missing row yields,

$$ \begin{array}{|c|c|c|c|} \hline BV & z &x_1&x_2&x_3&s_1&s_3&a_2&RHS\\\hline z & 1 &-1+2M & -2+2M& 1-M & 0 & 0 & 0 & M\\\hline s_1 & 0 & 0 & 1 & -1 & 1 & 0 & 0 & 3\\ a_2 & 0 & 2 & 2 & -1 & 0 & 0 & 1 & 1\\ s_3 & 0 & 1 & 2 & 2 & 0 & 1 & 0 & 3 \\\hline \end{array} $$

Pivoting the $x_1$ column with the $a_2$ row yields,

$$ \begin{array}{|c|c|c|c|} \hline BV & z &x_1&x_2&x_3&s_1&s_3&a_2&RHS\\\hline z & 1 & 0 & -1 & \frac{1}{2} & 0 & 0 & \frac{1}{2}-M & \frac{1}{2}\\\hline s_1 & 0 & 0 & 1 & -1 & 1 & 0 & 0 & 3\\ x_1 & 0 & 1 & 1 & -\frac{1}{2} & 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ s_3 & 0 & 0 & 1 & \frac{5}{2} & 0 & 1 &-\frac{1}{2} & \frac{5}{2} \\\hline \end{array} $$

Pivoting the $x_3$ column with the $s_3$ row yields,

$$ \begin{array}{|c|c|c|c|} \hline BV & z &x_1&x_2&x_3&s_1&s_3&a_2&RHS\\\hline z & 1 & 0 & -\frac{6}{5} & 0 & 0 & 0 & -M & 0\\\hline s_1 & 0 & 0 & \frac{7}{5} & 0 & 1 & \frac{2}{5} & -\frac{1}{5} & 4 \\ x_1 & 0 & 1 & \frac{6}{5} & 0 & 0 & \frac{1}{5} & \frac{3}{10} & 1\\ x_3 & 0 & 0 & \frac{2}{5} & 1 & 0 & \frac{2}{5} &-\frac{1}{5} & 1 \\\hline \end{array} $$

Which brings us to our optimal solution of $(x^*_1,x^*_2,x^*_3)=(1,0,1)$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.