MHB Basic feasible solution definition and example

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
A basic feasible solution in linear programming is defined as a solution vector where the non-zero coordinates correspond to linearly independent columns of the constraint matrix A. For a feasible solution to be basic, it can have at most m non-zero coordinates, where m is the rank of A. The discussion includes an example of a linear programming problem, illustrating how to identify basic feasible solutions by examining the intersections of constraint lines. It emphasizes that the basic feasible solutions correspond to the corner points of the feasible region defined by the constraints. Understanding these concepts is crucial for solving linear programming problems effectively.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
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)
 
evinda said:
Could you explain me the definition of the basic feasible solution and also the example? (Thinking)

evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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? :confused:

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)
 
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top