MHB Basic feasible solution definition and example

[evinda]

Hello! (Wave)

Basic feasible solution

$$\max (c_1 x_1+ \dots + c_n x_n) \\ Ax=b, x=(x_1, \dots , x_n) , b=(b_1, \dots, b_m) \\ x_i \geq 0, i=1, \dots, n , b_j \geq 0, j=1,\dots, m \\ \\ A=\begin{pmatrix}
a_{11} & a_{12} & \dots & a_{1n} \\
a_{21} & a_{22} & \dots & a_{2n} \\
\dots & & & & \\
\dots & & & & \\
a_{m1} & a_{m2} &\dots &a_{mn}
\end{pmatrix} \\ \\ P_1=\begin{bmatrix}
a_{11}\\
\dots\\
\dots\\
a_{m1}\\

\end{bmatrix}, \dots, P_n=\begin{bmatrix}
a_{1n}\\
\dots\\
\dots\\
a_{mn}\\

\end{bmatrix}$$

Then the equation $Ax=b$ can be equivalently written as $P_1 x_1+ \dots+ P_n x_n= \overline{b}, \overline{b}=\begin{bmatrix}
b_1\\
\dots\\
\dots\\
b_m\\
\end{bmatrix}$(at most $m$ lineraly independent columns)Definition:

If $x \in F \subset \mathbb{R}^n, x=(x_1, \dots, x_n)$ and the non-zero coordinates of $x$ correspond to linearly independent columns of the matrix $A$ then $x$ is called basic feasible solution.
For example if $x=(x_1, x_2, \dots, x_{m-1},0,0,0, \dots, 0) \in F$ and the columns that correspond to the non-zero coordinates, i.e. $P_1, \dots, P_{n-1}$ are linearly independent then $x$ is a basic feasible solution.Could you explain me the definition of the basic feasible solution and also the example? (Thinking)

 

[evinda]

I think that I understood the definition.
Then there is the following remark:

If $r(A)=m<n$, if $x$ is a basic feasible solution then $x$ has at most $m$ non-zero coordinates.

Does this hold because if $x$ has for example $m+1$ non-zero coordinates then $P_{m+1}$ will be linearly dependent with $P_i$ for some $i=1, \dots, m$ ?
Why is it possible that $x$ has less than $m$ non-zero coordinates? (Thinking)

 

[I like Serena]

Could you explain me the definition of the basic feasible solution and also the example? (Thinking)

I think that I understood the definition.
Then there is the following remark:

If $r(A)=m<n$, if $x$ is a basic feasible solution then $x$ has at most $m$ non-zero coordinates.

Does this hold because if $x$ has for example $m+1$ non-zero coordinates then $P_{m+1}$ will be linearly dependent with $P_i$ for some $i=1, \dots, m$ ?
Why is it possible that $x$ has less than $m$ non-zero coordinates? (Thinking)

Hi evinda! (Smile)

Suppose we look at the following linear programming problem:
$$\begin{array}{ll}x &\le 2 \\ 2x+3y&\le 6\end{array}$$
[desmos="-1,4,-1,3"]0\le x\le \left\{0\le y\le \frac{2}{3}:2,\frac{2}{3}\le y\le 2:3-\frac{3}{2}y\right\};(0,0),(1,0),(2,0),(2,\frac{2}{3}),(1,1);[/desmos]

We can bring it in canonical form as:
$$\begin{array}{rrrrrrrrr}
x &&&+&c &&&=& 2 \\ 2x&+&3y&&&+&d&=&6
\end{array}$$

I have marked the points $(0,0),(1,0),(2,0),(2,\frac{2}{3}),(1,1)$.
Can you tell if they are basic feasible solutions? (Wondering)

 

[evinda]

Hi evinda! (Smile)

Suppose we look at the following linear programming problem:
$$\begin{array}{ll}x &\le 2 \\ 2x+3y&\le 6\end{array}$$We can bring it in canonical form as:
$$\begin{array}{rrrrrrrrr}
x &&&+&c &&&=& 2 \\ 2x&+&3y&&&+&d&=&6
\end{array}$$

I have marked the points $(0,0),(1,0),(2,0),(2,\frac{2}{3}),(1,1)$.
Can you tell if they are basic feasible solutions? (Wondering)

So if we are given these points do we look at the matrix $A$ of the linear programming problem when it is not in its canonical form? (Thinking)

If we have this linear programming problem, we have: $A=\begin{bmatrix}
1 & 0 & 1 & 0\\
2 & 3 & 0 & 1
\end{bmatrix}$ and then $r(A)=2<4$.

$P_1=\begin{bmatrix}
1\\
2
\end{bmatrix}, P_2=\begin{bmatrix}
0\\
3
\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 $P_1 x+ P_2 y+ P_3 c+ P_4 d= \begin{bmatrix}
2\\
6
\end{bmatrix}$.

$x \leq 2 \\ y \leq 2 \\ c \leq 2 \\ d \leq 6$
so the set of feasible solutions is bounded.

Then we look at the $6$ possible 2-linaerly independent columns.

• $P_1, P_2$ are linearly independent:
  
  $P_1 x+P_2 y= \begin{bmatrix}
  2\\
  6
  \end{bmatrix} \Rightarrow x=2, y=\frac{2}{3}$
  
• $P_1, P_3$ are linearly independent:
  
  $P_1 x+P_3 c= \begin{bmatrix}
  2\\
  6
  \end{bmatrix} \Rightarrow x=3, c=-1$ -> we reject it.
  
• $P_1, P_4$ are linearly independent:
  
  $P_1 x+P_4 d= \begin{bmatrix}
  2\\
  6
  \end{bmatrix} \Rightarrow x=2, d=2$
  
• $P_3, P_4$ are linearly independent:
  
  $P_3 x+P_4 d= \begin{bmatrix}
  2\\
  6
  \end{bmatrix} \Rightarrow c=2, d=6$
  
• $P_2, P_3$ are linearly independent:
  
  $P_2 y+P_3 c= \begin{bmatrix}
  2\\
  6
  \end{bmatrix} \Rightarrow c=2, y=2$
  
• $P_2, P_4$ are not linearly independent.
  

Is it right so far? Do we set in each of the above cases the other variables that are not used equal to $0$ ? (Thinking)

 

[I like Serena]

So if we are given these points do we look at the matrix $A$ of the linear programming problem when it is not in its canonical form? (Thinking)

What do you mean?

Is it right so far? Do we set in each of the above cases the other variables that are not used equal to $0$ ? (Thinking)

Yes and yes. (Nod)

Note that we have 4 lines: $x=0, y=0, x=2, 2x+3y=6$.
You have found the intersections of each pair of lines, each of which corresponds to a possible basic feasible solution.

However, $x=0$ and $x=2$ do not intersect, which corresponds to the fact that the corresponding $P_i$ are linearly dependent (the lines are parallel).
And $y=0$ and $2x+3y=6$ do intersect, but their intersection $(3,0)$ is outside of the feasible region.

So the basic feasible solutions are exactly the corner points of the feasible region. (Mmm)