1
$\begingroup$

I have the following LP problem:

$$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x & \le 3\\ & & x & \ge 3\\ & & -x + 2y & \le -1\\ & & x, y & \ge 0 \end{aligned} \end{equation*}$$

I know this that the 2 first constraints are equivalent to $x = 3$, but I got some kind of theorotical question... If I add slack variables, I get the following:

$$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x + s_1 & = 3\\ & & -x + s_2 & = -3\\ & & -x + 2y + s_3 & = -1\\ & & x, y, s_1, s_2, s_3 & \ge 0 \end{aligned} \end{equation*}$$

Which gives me the following augmented matrix: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 3\\ 0 & -1 & 0 & 0 & 1 & 0 & -3\\ 0 & -1 & 2 & 0 & 0 & 1 & -1\\ \hline 1 & -2 & -3 & 0 & 0 & 0 & 0 \end{bmatrix}

From there, I have the following situation (which causes me some troubles... ):

  1. There are no positive values in the objective row, so I should get the optimal solution.
  2. The optimal solution includes only slack variables ($x=y=0$), but $s_2$ and $s_3$ are negative, actually this is not a feasible solution!

Here's my « question »: What should I do when facing this case?

As far as I know, I have a unfeasible solution if, when I pick a pivot column, I got only negative coefficients on it. Since I cannot pick one here, I don't know what to do...

$\endgroup$
2
  • $\begingroup$ Should the third row be 0 -1 2 0 0 1 -1? $\endgroup$ Commented Jul 20, 2015 at 13:31
  • $\begingroup$ @user3313320 Yes it should, edited, but the problem remains ;) $\endgroup$ Commented Jul 20, 2015 at 13:32

2 Answers 2

Reset to default
2
$\begingroup$

I assume the variables are implicitly non-negative.

You initial basis is not primal feasible nor dual feasible. You need a 2 step simplex algorithm to get a feasible initial basis. See for example section 2 of http://math.jacobs-university.de/oliver/teaching/iub/spring2007/cps102/handouts/linear-programming.pdf

$\endgroup$
2
  • $\begingroup$ If I understood your link, once I got my second set of equations (with the slack variable), my choice of the basic variables is wrong (because it yields a non-feasible solution), so I should add artificial variables (like in the part 2 of your PDF)? $\endgroup$ Commented Jul 20, 2015 at 14:35
  • $\begingroup$ @holt: yes. That the general way to do it. In some particular cases, you can make shortcuts by applying dual steps or informed guessing :) $\endgroup$ Commented Jul 20, 2015 at 14:38
0
$\begingroup$

First of all you can combine the first two constraints to one constraint.

$\texttt{first and second constraint}$

$x\leq 3 $

$x\geq 3$

Combining the two constraints:

$x=3$

$\Rightarrow x^*=3$

Therefore the objective function is

$\texttt{min} \ \ z = 2\cdot 3+3y=6+3y$

$\texttt{third constraint}$

$-3 + 2y \leq -1 \quad \quad |+3$

$2y\leq 2$

$y\leq 1$

Since the objective function has to be minimized and the coefficient of the y variable is positive, y has to be as small as possible. Therfore $y^*=0$, because $y\geq 0$.

And $z^*=6+0=6$

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, but I am not looking to the solution to this problem which is kind of trivial, I want to know what is wrong with my simplex algorithm (since it should yield the same $z^*$ value but it doesn't, even with the 2 initials constraints). $\endgroup$ Commented Jul 20, 2015 at 14:38
  • $\begingroup$ First of all the RHS has to be positive. Therefore you have to multiply the second and the third constraint by -1. The (in-)equality signs are turning around. $\endgroup$ Commented Jul 20, 2015 at 14:40

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.