MHB Are all the basic feasible solutions accepted?

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The linear programming problem is transformed into its canonical form, allowing for the identification of basic feasible solutions. The feasible solutions include (2,2,0,0), (2,0,2,0), and (4,0,0,6), with the latter yielding the maximum objective value of 4. It is clarified that not all variables need to appear in the objective function for a solution to be considered basic feasible. The discussion confirms the validity of the solutions provided and emphasizes that the maximum is achieved at (4,0,0,6).
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
evinda said:
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)
 
I like Serena said:
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)
 
evinda said:
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)
 
I like Serena said:
Right! (Nod)

Nice... Thank you! (Smirk)
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
32
Views
5K
Replies
6
Views
1K
Replies
4
Views
2K
Replies
6
Views
2K
Replies
1
Views
1K
Replies
4
Views
3K
Replies
12
Views
4K
Back
Top