Linear Programming - Motivation behind the Dual Simplex Method

Question

I am trying to understand the motivation behind the Dual Simplex Method. However, I have run into some roadblocks while understanding the rationale behind the Dual Simplex Method. This is my current understanding of the Simplex, Primal and Dual problem:

$1$. For a minimization problem, the Simplex Algorithm proceeds with first a basic feasible solution; then it replaces individual basis columns with an external column until $c_j - C_B B^{-1} A_j >0~\forall~j$ where $c_j$ is the $jth$ cost tuple ; $C_B$ is the cost corresponding to the feasible basis $B$ and $A_j$ is the $jth$ column external to $B$.

$2$. If $x_0$ be the primal feasible solution and $y_0$ be the dual feasible solution and both satisfy the complementary slackness conditions, then $x_0$ is the primal optimal solution and $y_0$ is the dual optimal solution.

$3$. If $c^T x_0 = b^T y_0$ where $B$ is the feasible basis, then $x_0$ is the primal optimal solution and $y_0$ forms the dual optimal solution.

Using this, my professor has tried to implement the Dual Simplex Algorithm by first accounting for a tuple of the RHS $:b_r < 0$ and then proceeding ahead.

However, I do not quite understand the need to consider $b_r < 0$ nor the algorithm ahead. Could someone help me build the dual simplex algorithm from here?

Answer 1

The primal simplex starts with a feasible basis, and finds "a better one" while keeping feasibility. On the other hand, the dual simplex starts with an optimal basis (typically infeasible), and finds a feasible one while keeping optimality.

In algebraic terms, the primal simplex maintains the RHS feasible, and iterates until the reduced cost is non-negative (if minimization), while the dual maintains the reduced cost non-negative (if minimization), and iterates until the RHS is positive.

In the figure below, the primal simplex iterations are the full arrows, the dual simplex iterations are the dotted arrows. The green dots are the feasible bases, the orange ones are the infeasible bases. The yellow arrow represents the gradient of the objective function (the best direction). You can see that the primal steps remain within the polygon, while the dual steps start outside of the polygon.

The benefit of using the dual is that sometimes, it is easier to "fix" an infeasible solution close to optimality, as in the figure below, only one step is required.