# Solving a linear optimisation problem with simplex method

\begin{align*} \max 3x_1+x_2\\ x_1 - x_2 \leq -1\\ -x_1 - x_2 \leq -3 \\ 2x_1 + x_2 \leq 4\\ x_1, x_2 \geq 0\\ \\ \\ \\ \\ x_3 = -1 - x_1 + x_2\\ x_4 = -3 + x_1 + x_2\\ x_5 = 4 - 2x_1 - x_2\\ z = 3x_1 + x_2\\ \\ \text{we add:}\,x_0\\ \\ \\ \\ x_3 = -1 +x_0 + x_2\\ x_4 = -3 +x_0+x_1+x_2\\ x_5 = 4 + x_0 - 2 x_1 - x_2\\ z = 3x_1 + x_2\\ w = -x_0\\ \text{enters}\,x_0, \quad \text{exits:}\,x_4\\ \end{align*} \begin{align*} \text{My question is why does}\;x_4\;\text{exit, if}\;x_3\;\text{limits the equation more? Shouldn't}\;x_3\;\text{exit?}\\ \end{align*}

This isn't the way the simplex algorithm is usually presented, but it is certainly equivalent to the usual presentation. I'm going to use the standard terminology (pivots, phase I, basic feasible solution); if wherever you got this from doesn't use this, feel free to ask about it in comments.

This isn't a regular pivot step; this is a pivot step that is preparing for phase I of the simplex algorithm, in which we are trying to find a basic feasible solution of the original problem. In phase I, we don't use z so I will drop it. We had

\begin{align} & \max w \\ x_3 &= -1 +x_0 + x_2\\ x_4 &= -3 +x_0+x_1+x_2\\ x_5 &= 4 + x_0 - 2 x_1 - x_2\\ w &= -x_0\\ &\text{enters}\,x_0, \quad \text{exits:}\,x_4.\\ \end{align}

Let's figure out what the next step is.

\begin{align} & \max w \\ x_3 &= 2 - x_1 + x_4 \\ x_0 &= 3 - x_1 - x_2 + x_4 \\ x_5 &= 7 - 3x_1 - 2x_2 + x_4 \\ w &= -x_0.\\ \end{align}

Now, if we set all the variables not in the basis to $$0$$, we get $$x_3 = 2$$, $$x_0=3$$, $$x_5 = 7$$, and they're all positive, so we can apply a standard pivot.

If instead, we had taken $$x_3$$ out, we would have: \begin{align} & \max w \\ x_0 &= 1 - x_2 + x_3 \\ x_4 &= -2 + x_1 + x_3 \\ x_5 &= 5 - 2x_1 - 2x_2 +x_3 \\ w &= -x_0, \end{align}

but this gives $$x_4 = -2$$, which means we can't apply a standard pivot.

• My question is when we look it here: \begin{align} & \max w \\ x_3 &= -1 +x_0 + x_2\\ x_4 &= -3 +x_0+x_1+x_2\\ x_5 &= 4 + x_0 - 2 x_1 - x_2\\ w &= -x_0\\ &\text{enters}\,x_0, \quad \text{exits:}\,x_4.\\ \end{align} In school what we usually have done to know which one exits is to do the following: $0\leq -1+x_0$ from this we get: $1\leq x_0$ So on the left side of the inequality is a lower number than if we done: $3\leq x_0$ when $x_4$ exits. It always was like that, but it's also true that there wasn't $x_0$, there were only other variables. – Bili Debili Jun 6 '20 at 17:40
• Do you know how to choose the variable, based on what. Is it different in this phase as it's usually without the $x_0$. The variable for exit I mean. Because in my book the special rules only suggest that $x_0$ enters, but doesn't tell me how to choose an exit variable. – Bili Debili Jun 6 '20 at 17:47
• It's not different in the entire phase; it's just different in the first step of this phase, and that's because you have negative terms ($x_4 = -3 + \ldots$). You want to make them all positive in the first pivot, and for this you choose whichever has the most negative constant term ($-3 < -1$, so you choose $x_4$). This is assuming that all the $x_0$ coefficients are $1$. Once you've gotten rid of these negative terms you proceed as usual. – Peter Shor Jun 6 '20 at 18:44
• Peter, just curious. In your Ph.D. thesis, www-math.mit.edu/~shor/thesis/introduction.pdf , your signature is dated September 1984, but the "submission" date appears to be September 1985. Is the 1984 a typo, or was there a one year delay between your signing and the formal submission? – Mark L. Stone Jun 7 '20 at 1:18
• The 1984 is a typo. I suspect I got the template from a graduate student who had graduated the previous year, and I forgot to change it. – Peter Shor Jun 7 '20 at 1:34

For min z I got 5 where x1=1, x2=2, and x5=2

I forgot what the relationship between min and max are when finding solution to LP... I know the question wants to max z but the first constraint is tricky because it wants a negative number

• x1=0, x2=4, x5=0, actually gives you a lower value of z. – Peter Shor Jun 6 '20 at 17:12
• But that doesnt satisfy the first two constraints... – swordlordswamplord Jun 6 '20 at 17:13
• So for instance, lets say entering varaible is x2.. after applying test ratio it is bound to row 1 where x2 = 1 – swordlordswamplord Jun 6 '20 at 17:15
• Doesn't x1=0, x2=4, x3=3, x4=1, x5=0, satisfies all the constraints? – Peter Shor Jun 6 '20 at 17:17
• o crap ur right – swordlordswamplord Jun 6 '20 at 17:19