Questions about simplex algorithm

Question

I'm trying to understand how simplex algorithm works, and here are my questions:

1. Why we choose the entering variable as that with the most negative entry in the last row? My understanding is that this can increase the optimal value by the largest amount. Is this correct?

2. After determining the entering variable, why we calculate the θ-ratio just using the column corresponding to the entering variable?

3. After calculating the θ-ratio, why we ignore the negative value when deciding the exiting variable? Is this because the variable with negative θ-ratio will always increase no matter how we move? But then why we cannot set it as non-basic?

4. Do we choose the least positive θ-ratio in order to ensure all the variables are still non-negative?

5. I am taught that the simplex process can be translated as finding θ and d such that x'=x+θd where x is the current solution, x' is the new one, d is the moving direction, θ is the step size. But how this θ could equal to the θ-ratio and how d is related with anything in the tableau (the entries in the last row maybe?)?

I'm totally confused about the relation between x'=x+θd and the tableau calculation, could anyone just explain the logic behind the calculation (using the step size and direction approach) and how this can be shown on the diagram?

Answer 1

I'm assuming you're doing "Phase 2" of the simplex method, so your current tableau gives you a basic feasible solution.

1. The short answer is that "we" don't necessarily do that. Entering variables should have negative entries in the objective row. The magnitude of that entry gives you the rate of increase in the objective per unit of change in the entering variable, keeping the other nonbasic variables at $0$. But different candidates for entering variable could increase by different amounts. Taking the most negative entry is one strategy that works, but it is not the only one, and I don't think it's really used in practice outside of undergraduate linear programming courses.
2. and
3. and
4. These ratios tell you what change in the entering variable, while keeping the other nonbasic variables at $0$, would make each basic variable $0$. You're increase the entering variable, but you're not allowed to have a basic variable become negative, so you have to stop the first time one hits $0$. This happens when the entering variable hits the lowest nonnegative ratio.
5. The tableau corresponds to a system of linear equations telling you how the values of the basic variables depend on the nonbasic variables (in any solution). The basic solution $x$ for the tableau is the one where the nonbasic variables are all $0$. If you take the entering variable at $\theta$ instead of $0$, you get $x' = x + \theta d$, where the $d$ entry for the entering variable is $1$, for the other nonbasic variables $0$, and for the basic variables it's $-$ the corresponding entry in the entering column of the tableau for that basic variable. In particular, you get $x'_i = 0$ when $\theta = x_i/d_i$, which is that ratio you calculate.

Answer 2

To 1: Yes, this is correct. The variable that has the most negative entry in the objective row will increase the optimal value by the largest amount. An example might make things more intuitive. Suppose at a particular iteration of the simplex method, your objective function is $z=2x_1+x_2$ or $z-2x_1-x_2=0$. The coefficients that would appear in your objective row would be -2 for $x_1$ and -1 for $x_2$. Increasing $x_1$ by 1 unit would increase z by 2, whereas increasing $x_2$ by one unit would increase z by only 1. So you can increase the optimal value the most by choosing the new entering variable to be the one with the most negative coefficient in the last row.

To 2, 3, and 4: To apply the minimum ratio test, you pick out every coefficient in the pivot column(column that contains your new entering basic variable) that is strictly positive, and divide the right hand side by this coefficient. Identify the row with the smallest ratio. The basic variable in that row becomes the leaving basic variable. The intuition behind this is that your basic variables must remain positive, so you were correct in that respect. The row that has the smallest ratio contains the basic variable that will become zero the fastest as you increase the value of the entering basic variable. Since this basic variable CANNOT become negative, it is this variable that becomes the leaving basic variable. You can ignore variables with negative ratios because since it has a negative coefficient increasing the value of the entering basic variable actually increases the value of said variable, instead of decreasing it, so you do not run the risk of that variable becoming negative.

To 5: Intuitively, think of $\theta$ as the step size that you can increase x while staying within the feasible region. In the simplex method, you are really moving along a boundary that consists of connected line segments, each corresponding to a different (linear) constraint. Think of delta as the amount that you can move along a particular line segment, before you hit one of the connecting joints and moving any further along that line segment would take you out of the feasible region of the problem. So x is the point you start at, d is the direction you are moving in, and $\theta$ is the amount you move before you hit another constraint.

Hope this was helpful.