[Math] Questions about simplex algorithm

linear programmingoptimizationsimplex

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?

Best Answer

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.
Related Question