# What are the lawful operations in the simplex method?

Having the following:

\begin{equation*} \begin{cases} \max& 3 x_1 & + 2x_2 & +4x_3\\ &x_1 &+ x_2 &+ 2 x_3 &\le 4\\ &2x_1 & &+3 x_3 &\le7\\ &2 x_1 &+ x_2 &+x_3 &\le 7\\ &\forall i,x_i\ge 0 \end{cases} \end{equation*} resulting, after one iteration, in the following Simplex programm: $$\begin{array}{llllll} x_3= \frac{5}{3}& -\frac{2}{3}X_1 & & & &-\frac{1}{3}X_5\\ x_4= \frac{2}{3}& +\frac{1}{3} X_1& -X_2& &\\ x_6= 2& & -X_2 & & &+X_5 \\ \hline z= \frac{20}{3} &+\frac{1}{3}X_1 & + 2X_2 & & & -\frac{4}{5}X_5 \end{array}$$

Can $X_1$ enter the basis and $X_4$ exit it?

We would have:

$$X_1=-2 + 3 X_2 + 3 X_4 -2 X_5$$

Having such a $-2$ leaves me perplex, shouldn't any $X_i$ be positive?

Thus what are the conditions to have an operation be lawful in the Simplex method?

• Select a column such that the coefficient of $X_i$ in the $Z = a_1 x_1 ... a_k X_k$ row is MOST negative. From there you can only select rows such that the corresponding $X_i$ has a positive coefficient (namely the positive coefficient that satisfies minimum ratio). – frogeyedpeas Feb 20 '16 at 23:58
• @ Marine1 : I suggest you to think to the simplex algorithm as a gradient descent on the vertices of the admissible convex polytope. each vertex is fully determined by what you call "some basis variables", and the rule for jumping from one vertex $a$ to an other $b$ is that $a$ and $b$ are connected by an outer edge (in term of "basis variables" only one $X_i$ goes out and only one goes in) and that the new vertex $b$ is the one, among the vertices directly connected to $a$, yielding the lower value for the objective function to be minimized – reuns Feb 21 '16 at 1:22
• @frogeyedpeas Okay, so should it be $X_4$? because of the coefficient is the most negative? But it was the $X_i$ that just went out... – ThePassenger Feb 21 '16 at 11:12
• @frogeyedpeas According to my teacher, it should be $X_2$ that goes in... – ThePassenger Feb 21 '16 at 11:32
• I think it is $X_2$ because it is a case of maximizing, isn't it? $X_2$ has the greatest coefficient. – ThePassenger Feb 21 '16 at 11:38