Are all the basic feasible solutions accepted?

[evinda]

Hello! (Wave)The following linear programming problem is given:

$$\max{(x_1-x_2)} \\ x_1+x_2 \leq 4 \\ 2x_1-x_2 \geq 2 \\ x_1, x_2 \geq 0$$

Write it in its canonical form and find its vertices.

I have tried the following:

The linear programming problem can be written in its canonical form as follows:

$$\max{(x_1-x_2)} \\ x_1+x_2+x_3=4 \\ 2x_1-x_2-x_4=2 \\ x_1, x_2, x_3, x_4 \geq 0$$

$A=\begin{bmatrix}
1 &1 & 1 & 0\\
2 & -1 & 0 &-1
\end{bmatrix}$

$r(A)=2$, $P_1=\begin{bmatrix}
1\\
2
\end{bmatrix}, P_2=\begin{bmatrix}
1\\
-1
\end{bmatrix}, P_3= \begin{bmatrix}
1\\
0
\end{bmatrix}, P_4=\begin{bmatrix}
0\\
-1
\end{bmatrix}$

and the problem can be written equivalently as follows:

$$\max{ (x_1-x_2) } \\ P_1 x_1+ P_2 x_2+ P_3 x_3+ P_4 x_4= \begin{bmatrix}
4\\
2
\end{bmatrix} \\ x_j \geq 0, j=1,2,3,4$$From the equations we get that $0 \leq x_1 \leq 4, 0 \leq x_2 \leq 4, 0 \leq x_3 \leq 4, 0 \leq x_4 \leq 8$ and thus the set of feasible solutions is bounded.

• $P_1, P_2$ are linearly independent.
  
  We solve the system $P_1 x_1+P_2 x_2= \begin{bmatrix}
  4\\
  2
  \end{bmatrix}$ and we get $x_1=x_2=2$.
  
  $(2,2,0,0) $ -> basic feasible solution
  
• $P_1, P_3$ are linearly independent.
  
  We solve the system $P_1 x_1+P_3 x_3= \begin{bmatrix}
  4\\
  2
  \end{bmatrix}$ and we get $x_2=x_3=2$.
  
  $(2,0,2,0) $ -> basic feasible solution
• $P_1, P_4$ are linearly independent.
  
  We solve the system $P_1 x_1+P_4 x_4= \begin{bmatrix}
  4\\
  2
  \end{bmatrix}$ and we get $x_1=4, x_4=6$.
  
  $(4,0,0,6) $ -> basic feasible solution
• $P_2, P_3$ are linearly independent.
  
  We solve the system $P_2 x_2+P_3 x_3= \begin{bmatrix}
  4\\
  2
  \end{bmatrix}$ and we get $x_1=-2, x_3=3$, which does not give a basic faesible solution.
  
• $P_2, P_4$ are linearly independent.
  
  We solve the system $P_2 x_2+P_4 x_4= \begin{bmatrix}
  4\\
  2
  \end{bmatrix}$ and we get $x_2=4, x_4=-6$, which does not give a basic faesible solution.
  
• $P_3, P_4$ are linearly independent.
  
  We solve the system $P_3 x_3+P_4 x_4= \begin{bmatrix}
  4\\
  2
  \end{bmatrix}$ and we get $x_3=4, x_4=-2$, which does not give a basic faesible solution.

Is the above right? Or can't we accept for example $(2,0,2,0)$ as a basic feasible solution since $x_3$ doesn't appear at the function that we want to maximize? (Thinking)

 

[I like Serena]

Is the above right? Or can't we accept for example $(2,0,2,0)$ as a basic feasible solution since $x_3$ doesn't appear at the function that we want to maximize? (Thinking)

Hey evinda! (Smile)

All is well.
It it normal that not all variables appear in the objective function. (Mmm)

 

[evinda]

Hey evinda! (Smile)

All is well.
It it normal that not all variables appear in the objective function. (Mmm)

So the maximum of the objective function is $4$ and is achieved for the basic feasible solution $(4,0,0,6)$, right? (Thinking)

 

[I like Serena]

So the maximum of the objective function is $4$ and is achieved for the basic feasible solution $(4,0,0,6)$, right? (Thinking)

Right! (Nod)

 

[evinda]

Right! (Nod)

Nice... Thank you! (Smirk)