11
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

17
$\begingroup$

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 the the primal steps remains within the polygon, while the dual steps starts 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.

enter image description here

$\endgroup$
5
  • $\begingroup$ Thank you for the answer. Do we need to explicitly find the dual to follow the dual simplex method? My confusion is : - The simplex method is applied on the dual formulation without explicitly finding the dual. How is that done? $\endgroup$
    – MathMan
    Commented Apr 21, 2022 at 15:20
  • 3
    $\begingroup$ @MathMan, Please be aware that, the dual simplex method is different from the dual theory. Primal/dual simplex is the method to solve a linear program, while the dual theory talks about the relation between the primal problem and its corresponding dual. $\endgroup$
    – A.Omidi
    Commented Apr 21, 2022 at 15:30
  • 1
    $\begingroup$ @MathMan No, you do not need to formulate the dual problem. The dual simplex method works on the same tableau that the primal simplex uses (when executed by hand) or with the same matrices that primal simplex uses (if done on a computer). It just changes the pivot selection rules. Instead of the reduced costs deciding who enters the basis and the adjusted RHS deciding who leaves, the RHS decides who enters and the reduced cost vector decides who leaves. $\endgroup$
    – prubin
    Commented Apr 21, 2022 at 20:20
  • $\begingroup$ @prubin Many thanks. Could you please explain how are the pivot selection rules obtained? Thanks $\endgroup$
    – MathMan
    Commented Apr 23, 2022 at 0:34
  • $\begingroup$ @MathMan Assume a minimization problem in standard form. Your basis is superoptimal (all reduced costs nonnegative) but infeasible (at least one negative basic variable). Select a row containing a negative basic variable and a legal pivot column such that pivoting will make the RHS of that row nonnegative (fixing the negative basis variable) while preserving superoptimality (keeping all reduced costs nonnegative). So primal simplex pivots out a negative reduced cost while keeping the RHS nonnegative, and dual simplex pivots out a negative RHS keeping the reduced costs nonnegative. $\endgroup$
    – prubin
    Commented Apr 23, 2022 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.