4

I'm trying to solve this problem but need some help getting started. The problem asks to find all the basic feasible solutions of the following system:

$$ \begin{aligned} -4x_2+x_3 &= 6\\ 2x_1-2x_2-x_4 &= 1\\ x_1, x_2, x_3, x_4 &\geq 0 \end{aligned} $$

How might one go about solving this problem? Thanks!

Rodrigo de Azevedo
  • 1
Matthew James
  • 41
  • 1
    There are four variables and two constraints, so $\binom 42$ choices of basis. All that remains is to determine which are feasible. – Math1000 Apr 15 '16 at 23:06
  • 1
    Thanks for the hint. Unfortunately, this area is completely new to me and I'm no closer to understanding 'how' I could actually solve this problem. What steps do I need to take to determine the basic solutions, and then what criteria makes it a basic feasible solution? – Matthew James Apr 15 '16 at 23:24
  • x[1,4] does not have a solution. So the answer is just x[1,3] Also, can someone tell me this: In this case the rank of A and augmented matrix [A,b] is 2 which is less than the number of unknowns which is 4. So the system should have infinite basic solutions right? – Vinayak Narwade Jul 29 '18 at 15:43

1 Answers1

1

Given the constraints of a model, $$-4x_2 + x_3 = 6$$ $$2x_1-2x_2-x_4=1$$ $$x_1, x_2, x_3, x_4 \ge 0$$

Let's put it in standard form:

$$-4x_2 + x_3 +a_1= 6$$ $$2x_1-2x_2-x_4 + a_2=1$$ $$x_1, x_2, x_3, x_4, a_1, a_2\ge 0$$

To start, let's put these values into a tableau as such: enter image description here

From here, notice that the $x_3$ column is like the columns of the basic, artificial variables, and as such, we can swap $a_1$ and $x_3$ to achieve a new tableau as shown here: enter image description here

In addition, we can divide the second row by 2 to make $x_1$ a basic variable. By doing all of this, we should find two more tableaus as depicted below,

enter image description here enter image description here

The last tableau will be the only feasible solution we are able to reach with these constraints, as modifying the $x_2$ and $x_4$ columns to make them basic variables will turn the RHS negative, which will then invalidate the $x_4\ge0$ and $x_2\ge0$ constraints and make the solution infeasible.

Since we can only have a max of two basic variables with the two constraints we have, and the coefficients of $x_2$ and $x_4$ are all negative, there will exist no combination of points that will allow $x_2$ and $x_4$ to become basic variables in the constraints. Thus, there is only one possible solution.

  • 1
    Only the last of these is a basic feasible solution for the problem. In the others, since the artificial slack variables are nonzero, the point $(x_1, x_2, x_3, x_4)$ does not satisfy the constraints we're given. – Misha Lavrov Oct 03 '22 at 06:07
  • Ah yes, nice catch, then there would exist only one feasible solution. Thank you!!! –  Oct 03 '22 at 06:23