Linear programming question: Solve this using the two phase method

[fiksx]

Homework Statement

(P)
minimize: $$z=x_1+x_2$$
subject to :
$$
x_1+2x_2 >= 4 $$( equation 1)
$$2x_1+x_2>=6$$ (equation 2)
$$-x_1+x_2<=1$$ (equation 3)
$$x_1>=0 ,x_2>=0 $$


I'm trying to solve this using two phase method, please review my answer.


**2.) For the problem (P), use
the nonnegative variable $$x_3$$ for inequality constraint 1 and the nonnegative variable $$x_4$$ for inequality constraint 2 and the nonnegative variable $$x_5$$ for inequality 3 then Show the equation standard form of the problem (P).**

answer: standart form
min $$u=x1+x2$$ or $$u=-x1-x2$$ (?)


subject to <br>
$$x_1+2x_2-x_3=4 $$
$$2x_1+x_2- x_4=6 $$
$$-x_1+x_2+ x_5=1$$


**(3) Find all feasible basis
solutions of the equation standard form of the problem (P) obtained in (2).**

answer:im not sure how to find the feasible basis(?)

\begin{bmatrix}
1 & 2 & -1 & 0 & 0 \\
2 & 1 & 0 & -1 & 0 \\
-1 & 1 & 0 & 0 & 1 \\
\\
\end{bmatrix}

am I right?

**(4) from the standard form
matrix that obtain in number 2, Consider the artificial variable (the problem of the first phase) when applying the two-step method, introduced artificial variable $$v_1$$ and $$v_2$$. find dictionary for base variable $$v_1,v_2,v_5$$**

answer: dictionary
we input v1 and v2 as artificial variable
min $$u=v_1+v_2$$
subject to
$$x_1+2x_2-x_3+v_1=4 $$
$$2x_1+x_2- x_4+v_2=6$$
$$-x_1+x_2+ x_5=1 $$

reason is because if non basic variable are all 0 then the basis variable will produce a feasible solution (4,6,1)

**5) From problem 4, show the
optimal dictionary**

answer:
min
$$u=10-3x_1-3x_2-x_3-x_4 $$
$$v_1=4-x_1-2x_2-x_3 $$
$$v_2=6-2x_1-x_2-x_4$$
$$x_5=1+x_1-x_2 $$

here I need to find the optimal solution that produces z =0 ? until artificial variable =0?

am i right??

**6. Use the feasible basis
solution obtained from the optimal dictionary in (5), find the first dictionary from the standard matrix form (P) and optimal solution
of the problem (P),**

answer:
is this the two phase ? and solve this using tableau?
how to know if the answer is optimize or not?

to optimize number 4, we need to make sure all artificial variables are 0(?)

I'm confused, I have read about this but i cant seem understand

Relevant Equations

Linear programming , matrices,simplex method

Simplex method

 

[Ray Vickson]

Simplex method

First: in this Forum, LaTeX needs # # (no space) at the start and at the end of each in-line equation, and needs
$ $ (no space) at the start and the end of each "displayed" equation.

So, your problem is
$$\begin{array}{clc}
\min&x_1+x_2 &\\
&x_1 + x_2 - x_3 &=4\\
&2x_1 - x_2 - x_4 &=6\\
& -x_1 + x_2 + x_5 &=1 \\
&x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array}$$

If you really do want to use the two-phase method, you need to introduce artificial variables in the first two constraints (in order to have terms like +x on the left, so you can get an initial feasible solution. However, we want to see if a feasible solution is available in which all the artificial variables equal zero. So, the question is:
given
$$\begin{array}{lc}
x_1+x_2-x_3+a_1 &=4\\
2x_1 - x_2 - x_4 + a_2 &=6\\
-x_1 + x_2 + x_5 &=1\\
x_1,x_2,x_3,x_4,x_5, a_1, a_2 &\geq 0
\end{array}$$
can we find a solution in which $a_1 = 0$ and $a_2 = 0?$ Clearly, if we find a solution with $a_1 = a_2 = 0$ we will have found a feasible solution to the original problem. On the other hand, if every feasible solution of the "artificial" problem involves $a_1 > 0$ or $a_2 > 0$ that would mean that the original problem does not have any feasible solutions (in other words, is an infeasible problem).

The standard Phase-I problem is to find a feasible solution of the artificial problem with all artificial variables equal to zero, or else to show this is not possible. This is done simply by minimizing $a_1 + a_2$. So the phase-I problem is
$$\begin{array}{clc}
\min & a_1 + a_2 \\
\text{s.t.}&x_1+x_2-x_3+a_1 &=4\\
&2x_1 - x_2 - x_4 + a_2 &=6\\
&-x_1 + x_2 + x_5 &=1\\
&x_1, x_2, x_3, x_4, x_5, a_1, a_2 &\geq 0
\end{array} $$

An initial feasible solution to this problem is $a_1 = 4, a_2 = 6, x_5 = 1.$ In order to proceed towards minimizing $Z_1 = a_1 + a_2$ we need to eliminate the current basic variables $a_1, a_2$ from the objective. We have
$$Z_1 = a_1 + a_2 =(4-x_1-x_2+x_3) +(6-2x_1+x_2 + x_4) \\
= 10 -3 x_1+x_3+x_4$$

Now proceed as usual to minimize $-3 x_1 + x_3 + x_4$ in the artificial problem,

 

[FactChecker]

Just a note:
The original problem with so many equalities may not have a solution at all. Adding the artificial variables directly may not help since the Simplex algorithm will want those variables to be non-negative, which may not be possible. The only sure method is to get an easy initial solution for the Simplex algorithm is to add two non-negative artificial variables, $+a_1-a_2$ to the first equation and two more for the second equation.

CORRECTION EDIT: Somehow, I didn't get up to the top of post #1 to see that the original equations are not strict equalities. This post was appropriate for the modified equations at the end of post #1.

 

[fiksx]

First of all i would like to thank for the answer. But i was still confuse of how to find executable basis for
min $$u=x1+x2$$ or $$u=-x1-x2$$ (?)
although it can be seen from the picture that the executable basis is the extreme point of feasible region

this is the correct answer but I am still confuse:

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

**(4) from the standard form
matrix that obtain in number 2, Consider the artificial variable (the problem of the first phase) when applying the two-step method, introduced artificial variable $v_1$ and $v_2$. find dictionary for base variable $v_1,v_2,v_5$**
the correct answer is

min u=v1+v2

v1,v2 is artificial variable

subject to

$$x1+2x2+x3+v1=4$$

$$2x1+x2+x4+v2=6$$

$$-x1+x2+x5=1$$
here I am not sure why x3 and x4 is positive ??

and change to dictionary form when v1, v2, and x5 is basis

$$u=10-3x_1-3x_2-x_3-x_4 $$

$$v_1=4-x_1-2x_2-x_3 $$

$$v_2=6-2x_1-x_2-x_4$$

$$x_5=1+x_1-x_2 $$

**5) From problem 4, show the
optimal dictionary**to find optimal dictionary:

we have to see the negative variable in u to minimize it?

suppose x1 , so we find ratio of x1 in v1 = 4, x1 in v2 =3 , x1 in x5= 1

so take 1 in order to minimize it at most

here I am confuse why 1?

correct answer is

$$x1=8/3-x3/3+2/3x4+2/3v1+2/3v2$$
$$x2=2/3+2/3v3+x4/3-v1/2-1/3v2$$
$$1-x1+x2$$

**6. Use the feasible basis
solution obtained from the optimal dictionary in (5), find the first dictionary from the standard matrix form (P) and optimal solution
of the problem (P),**

correct answer is
$$z=10/3+1/3x3+1/3x4$$
$$x1=8/3-1/3x3+2/3x4$$
$$x2=2/3+2/3x3-1/3x4$$
$$x5=1-x3+x4$$

this maybe correct or not but WHY??

 

[FactChecker]

In my opinion, you are not adding enough artificial variables. The Simplex algorithm I am familiar with requires non-negative variable values. By adding two non-negative artificial variables ($+a_1-a_2$) to the first equation, two more ($+a_3-a_4$), to the second equation, and two ($+a_5-a_6$) to the third, you can guarantee that an initial feasible solution can be found with all variables non-negative.

 

[Ray Vickson]

In my opinion, you are not adding enough artificial variables. The Simplex algorithm I am familiar with requires non-negative variable values. By adding two non-negative artificial variables ($+a_1-a_2$) to the first equation, two more ($+a_3-a_4$), to the second equation, and two ($+a_5-a_6$) to the third, you can guarantee that an initial feasible solution can be found with all variables non-negative.

No, this is definitely not the case. Consider the two linear systems:
$$\begin{array}{lc}
x_1 + x_2 - x_3 &=4\\
2x_1 - x_2 - x_4 &=6\\
-x_1 + x_2 + x_5 &=1 \\
x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(1)
$$
and
$$
\begin{array}{lc}
x_1+x_2-x_3+a_1 &=4\\
2x_1 - x_2 - x_4 + a_2 &=6\\
-x_1 + x_2 + x_5 &=1\\
x_1,x_2,x_3,x_4,x_5, a_1, a_2 &\geq 0
\end{array}\hspace{3em}(2)
$$

(1) Clearly, if (1) has a feasible solution (that is, a solution with all $x_j \geq 0$) then (2) also has a feasible solution with $a_1 = a_2 = 0.$
(2) if (2) has a feasible solution with $a_1+a_2 = 0$ (that is, with both $a_1 = 0$ and $a_2 = 0$), then (1) has a feasible solution (obtained by just ignoring the variables $a_1, a_2$).
(3) If every solution of (2) has $a_1 >$ or $a_2 > 0$, then it is impossible to have a feasible solution of (1). Thus, minimizing $a_1 + a_2$ subject to all the contraints in (2) will decide the issue once and for all---either we get a feasible solution to the original problem (from which we start the rest---Phase II--- of the simplex method) or else we conclude 100% accurately that the original problem has no feasible solutions.

There is no reason for any "extra" artificial variables, and for over 60 years that is how simplex implementations have worked. To be honest, though, modern implementations (especially professional-industrial-scale versions) do not use artificial variables at all---they are regarded as old-fashioned, textbook-level methods. Furthermore, they enlarge the problem unnecessarily, since we can get along without them just by tweaking the logic of the simplex method (although in a way that beginners may find confusing and a bit counter-intuitive).

Here is how a modern implementation might proceed for the following problem:

$$\begin{array}{clc}
\min&x_1+x_2 &\\
&x_1 + x_2 - x_3 &=4\\
&2x_1 - x_2 - x_4 &=6\\
& -x_1 + x_2 + x_5 &=1 \\
&x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(LP1) $$Start with a basic solution, possibly infeasible:
$$ x_3 = -4, x_4 = -6, x_5 = 1 \hspace{3em} (S1)$$
Since we have $x_3, x_4 < 0,$ let us regard as a temporary objective that of increasing $x_3$, so we temporarily have $\max x_3$ subject to the constraints in (LP1). Since
$$x_3 = -4 +x_1+x_2 \hspace{3em}(1a)$$
increasing either $x_1$ or $x_2$ will increase $x_3$. We also have
$$x_4 = -6 + 2x_1 -x_2 \hspace{3em}(2a)$$
and
$$x_5 = 1 + x_1 - x_2 \hspace{3em} (3a)$$
If we increase $x_1$ from 0 to 3, $x_3$ increases from -4 to -1 and $x_4$ increases from -6 t0 0 and $x_5$ increases from 1 to 4; Clearly, if we increase $x_1$ up to 4, $x_3$ will reach 0, $x_4$ will increase to 2 and $x_5$ will increase to 5. This is a basic feasible solution to (LP1)! So, we have basic variables $x_1 = 4, x_4 = 2$ and $x_5 = 5.$

Now we can return to the original problem (LP1) and start the simplex method with the above basic feasible solution.

 

[FactChecker]

I should have said that the addition of proper artificial variables make an initial solution trivial to find, regardless of whether the original problem turns out to have a solution. This is critically important to the practical use of the algorithm.

PS. I realized that if the original equations are multiplied through so that the constant side is non-negative, then only one artificial variable needs to be added per equation. The original example is already like that.

 

[fiksx]

No, this is definitely not the case. Consider the two linear systems:
$$\begin{array}{lc}
x_1 + x_2 - x_3 &=4\\
2x_1 - x_2 - x_4 &=6\\
-x_1 + x_2 + x_5 &=1 \\
x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(1)
$$
and
$$
\begin{array}{lc}
x_1+x_2-x_3+a_1 &=4\\
2x_1 - x_2 - x_4 + a_2 &=6\\
-x_1 + x_2 + x_5 &=1\\
x_1,x_2,x_3,x_4,x_5, a_1, a_2 &\geq 0
\end{array}\hspace{3em}(2)
$$

(1) Clearly, if (1) has a feasible solution (that is, a solution with all $x_j \geq 0$) then (2) also has a feasible solution with $a_1 = a_2 = 0.$
(2) if (2) has a feasible solution with $a_1+a_2 = 0$ (that is, with both $a_1 = 0$ and $a_2 = 0$), then (1) has a feasible solution (obtained by just ignoring the variables $a_1, a_2$).
(3) If every solution of (2) has $a_1 >$ or $a_2 > 0$, then it is impossible to have a feasible solution of (1). Thus, minimizing $a_1 + a_2$ subject to all the contraints in (2) will decide the issue once and for all---either we get a feasible solution to the original problem (from which we start the rest---Phase II--- of the simplex method) or else we conclude 100% accurately that the original problem has no feasible solutions.

There is no reason for any "extra" artificial variables, and for over 60 years that is how simplex implementations have worked. To be honest, though, modern implementations (especially professional-industrial-scale versions) do not use artificial variables at all---they are regarded as old-fashioned, textbook-level methods. Furthermore, they enlarge the problem unnecessarily, since we can get along without them just by tweaking the logic of the simplex method (although in a way that beginners may find confusing and a bit counter-intuitive).

Here is how a modern implementation might proceed for the following problem:

$$\begin{array}{clc}
\min&x_1+x_2 &\\
&x_1 + x_2 - x_3 &=4\\
&2x_1 - x_2 - x_4 &=6\\
& -x_1 + x_2 + x_5 &=1 \\
&x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(LP1) $$Start with a basic solution, possibly infeasible:
$$ x_3 = -4, x_4 = -6, x_5 = 1 \hspace{3em} (S1)$$
Since we have $x_3, x_4 < 0,$ let us regard as a temporary objective that of increasing $x_3$, so we temporarily have $\max x_3$ subject to the constraints in (LP1). Since
$$x_3 = -4 +x_1+x_2 \hspace{3em}(1a)$$
increasing either $x_1$ or $x_2$ will increase $x_3$. We also have
$$x_4 = -6 + 2x_1 -x_2 \hspace{3em}(2a)$$
and
$$x_5 = 1 + x_1 - x_2 \hspace{3em} (3a)$$
If we increase $x_1$ from 0 to 3, $x_3$ increases from -4 to -1 and $x_4$ increases from -6 t0 0 and $x_5$ increases from 1 to 4; Clearly, if we increase $x_1$ up to 4, $x_3$ will reach 0, $x_4$ will increase to 2 and $x_5$ will increase to 5. This is a basic feasible solution to (LP1)! So, we have basic variables $x_1 = 4, x_4 = 2$ and $x_5 = 5.$

Now we can return to the original problem (LP1) and start the simplex method with the above basic feasible solution.

thankyou for answering
i really want to ask
$$x1+x2−x3+a1=4$$
$$2x1−x2−x4+a2=6$$
$$−x1+x2+x5=1$$
$$x1,x2,x3,x4,x5,a1,a2≥0$$

by making a1 +a2=0
if i pick v1,v2,x5 as basic variable
then dictionary will be
$$u=10−3x1−3x2−x4$$

$$v1=4−x1−2x2−x3$$

$$v2=6−2x1−x2−x4$$

$$x5=1+x1−x2$$
am i right?

 

[Ray Vickson]

thankyou for answering
i really want to ask
$$x1+x2−x3+a1=4$$
$$2x1−x2−x4+a2=6$$
$$−x1+x2+x5=1$$
$$x1,x2,x3,x4,x5,a1,a2≥0$$

by making a1 +a2=0
if i pick v1,v2,x5 as basic variable
then dictionary will be
$$u=10−3x1−3x2−x4$$

$$v1=4−x1−2x2−x3$$

$$v2=6−2x1−x2−x4$$

$$x5=1+x1−x2$$
am i right?

There were no $u, v_1, v_2$ in your original system, so where did they come from? Also, what happened to $a_1, a_2$? It is true that after you have found a basic solution with variables $a_1, a_2=0$ non-basic, you can then drop $a_1, a_2$ from all subsequent equations, etc. However, until you have done that, just failing to write them would be considered as sloppy and might result in reduced marks. You need to show that you understand what you are doing at each step, and you need to be careful.

Finally, if you have a system of several equations, you can put them in an "array", so they come out looking good. For example, here are your final three equations put into an array:
$$\begin{array}{l}
u=10−3x_1−3x_2−x_4 \\
v_1=4−x_1−2x_2−x_3 \\
v_2 = 6 - 2x_1 - x_2 - x_4 \\
x_5=1+x_1−x_2
\end{array}$$
Just right-click on the image to see the TeX commands used.

I cannot possibly tell if these are correct, because I don't know what are $u, v_1, v_2.$

 

[fiksx]

There were no $u, v_1, v_2$ in your original system, so where did they come from? Also, what happened to $a_1, a_2$? It is true that after you have found a basic solution with variables $a_1, a_2=0$ non-basic, you can then drop $a_1, a_2$ from all subsequent equations, etc. However, until you have done that, just failing to write them would be considered as sloppy and might result in reduced marks. You need to show that you understand what you are doing at each step, and you need to be careful.

Finally, if you have a system of several equations, you can put them in an "array", so they come out looking good. For example, here are your final three equations put into an array:
$$\begin{array}{l}
u=10−3x_1−3x_2−x_4 \\
v_1=4−x_1−2x_2−x_3 \\
v_2 = 6 - 2x_1 - x_2 - x_4 \\
x_5=1+x_1−x_2
\end{array}$$
Just right-click on the image to see the TeX commands used.

I cannot possibly tell if these are correct, because I don't know what are $u, v_1, v_2.$

thankyou this is actually a step by step questions about simplex method that change dictionary or the basis until find the feasible dictionary(?)

\begin{array}{lc}
x_1 + x_2 - x_3 &=4\\
2x_1 - x_2 - x_4 &=6\\
-x_1 + x_2 + x_5 &=1 \\
x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(1)

the questions are to Find all feasible basis solutions of the equation standard form of the problem (P)
and find the feasible dictionary

Consider the artificial variable (the problem of the first phase) when applying the two-step method, introduced artificial variable v1 and v2. find dictionary for base variable v1,v2,v5

theequation will become:

min u=v1+v2
\begin{array}{lc}
x_1 + x_2 - x_3 +v1&=4\\
2x_1 - x_2 - x_4 +v2&=6\\
-x_1 + x_2 + x_5 &=1 \\
x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(1)

the dictionary will be:
by subsitute v1 and v2 to the u
we get

min u=v1+v2
\begin{array}{l}
u=10−3x_1−3x_2+x_4+x_5\\
v_1=4−x_1−2x_2+x_4 \\
v_2 = 6 - 2x_1 - x_2 +x_5 \\
x_5=1+x_1−x_2
\end{array}

but my question is how to know which variable will be depart and enter ?
which variable should i find the ratio?
i know that either x1 or x2?

 

[Ray Vickson]

thankyou this is actually a step by step questions about simplex method that change dictionary or the basis until find the feasible dictionary(?)

\begin{array}{lc}
x_1 + x_2 - x_3 &=4\\
2x_1 - x_2 - x_4 &=6\\
-x_1 + x_2 + x_5 &=1 \\
x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(1)

the questions are to Find all feasible basis solutions of the equation standard form of the problem (P)
and find the feasible dictionary

Consider the artificial variable (the problem of the first phase) when applying the two-step method, introduced artificial variable v1 and v2. find dictionary for base variable v1,v2,v5

theequation will become:

min u=v1+v2
\begin{array}{lc}
x_1 + x_2 - x_3 +v1&=4\\
2x_1 - x_2 - x_4 +v2&=6\\
-x_1 + x_2 + x_5 &=1 \\
x_1, x_2, x_3, x_4, x_5 &\geq 0
\end{array} \hspace{3em}(1)

the dictionary will be:
by subsitute v1 and v2 to the u
we get

min u=v1+v2
\begin{array}{l}
u=10−3x_1−3x_2+x_4+x_5\\
v_1=4−x_1−2x_2+x_4 \\
v_2 = 6 - 2x_1 - x_2 +x_5 \\
x_5=1+x_1−x_2
\end{array}

but my question is how to know which variable will be depart and enter ?
which variable should i find the ratio?
i know that either x1 or x2?

So, in the current dictionary you have $u = 10- 3x_1 - 3x_2 + x_4 + x_5$, and you want to minimize $u$. Currently, when you have all the non-basic variables $x_1 = x_2 = x_4 = x_5 = 0$ you have $u=10.$ Is that really the minimum possible value of $u$? If you increase some non-basic variable up from 0, can you make $u$ smaller? It looks like the answer is YES: by increasing either $x_1$ or $x_2$ you can reduce $u$, so doing that is a logical next step. You can pick either $x_1$ or $x_2$ to increase---just pick one and do it.

 

[fiksx]

So, in the current dictionary you have $u = 10- 3x_1 - 3x_2 + x_4 + x_5$, and you want to minimize $u$. Currently, when you have all the non-basic variables $x_1 = x_2 = x_4 = x_5 = 0$ you have $u=10.$ Is that really the minimum possible value of $u$? If you increase some non-basic variable up from 0, can you make $u$ smaller? It looks like the answer is YES: by increasing either $x_1$ or $x_2$ you can reduce $u$, so doing that is a logical next step. You can pick either $x_1$ or $x_2$ to increase---just pick one and do it.

Thankyou if i choose x1 then i need to find the smallest ratio in order to make the equation still bigger then zero(?)
In v1 ,x1 ratio is 4
In v2,x1 ratio is 3
In x5,x1 ratio is 1
I used to choose x1 but the right answer is v2 , why ?
and to find feasible basis for this questions , it is said that basis are the point of visible region (?) am i right?

 

[Ray Vickson]

Thankyou if i choose x1 then i need to find the smallest ratio in order to make the equation still bigger then zero(?)
In v1 ,x1 ratio is 4
In v2,x1 ratio is 3
In x5,x1 ratio is 1
I used to choose x1 but the right answer is v2 , why ?
and to find feasible basis for this questions , it is said that basis are the point of visible region (?) am i right?

You will get nowhere using the above, because you do not have a valid dictionary. Your last equation has $x_5$ on the left of the "=" sign, but the same $x_5$ appears on the right-hand-side of the first and third equations. Remember, in a "dictionary" one group of variables are on the left of the "=" signs and the remaining variables are all on the right of "="; you cannot mix them up the way you have done.

Anyway, I have done all I can for you; the rest is up to you. You must be careful, and check each step you perform. You must avoid trying to invent your own personal version of the simplex method in which you do steps that are not among those described in all explanations of simplex. Instead of constantly asking "what should I do next" (which is just about the worst way of learning anything) you should just go ahead boldly and do what the simplex method tells you to do----it is all written down in great detail in many places.

 

[fiksx]

You will get nowhere using the above, because you do not have a valid dictionary. Your last equation has $x_5$ on the left of the "=" sign, but the same $x_5$ appears on the right-hand-side of the first and third equations. Remember, in a "dictionary" one group of variables are on the left of the "=" signs and the remaining variables are all on the right of "="; you cannot mix them up the way you have done.

Anyway, I have done all I can for you; the rest is up to you. You must be careful, and check each step you perform. You must avoid trying to invent your own personal version of the simplex method in which you do steps that are not among those described in all explanations of simplex. Instead of constantly asking "what should I do next" (which is just about the worst way of learning anything) you should just go ahead boldly and do what the simplex method tells you to do----it is all written down in great detail in many places.

sorry i wrote wrong variable
this is the right one
\begin{array}{l}
u=10−3x_1−3x_2+x_4+x_3\\
v_1=4−x_1−2x_2+x_3 \\
v_2 = 6 - 2x_1 - x_2 +x_4 \\
x_5=1+x_1−x_2
\end{array}

what i understand here is u is 10 and basic variable is, v1=3, v2=4, x5=6
we can minimize objective function by decrease $$x_1$$
if i choose x1, in v1 $$ 4-x1 \geq 0$$ ratio is 4
in v2, $$6-2x_1 \geq 0$$ ratio 3
in $$x_5$$,$$x_1+1 \geq 0$$ ratio 1
so in order the basis variable still positive, if i increase $$x_1$$ at most 3 will reduce u to 1
but if i choose $$x_5$$ will reduce u to 7

my question is why we are not consider $$x_5$$ as departing variable??
please clear my confusion in this part, because if i choose wrong pivot the entire solutions is wrong
thankyou so much!

 

[hmla]

the best simplex method calculator - linprog.com