1.2 Duality Theory

1.2.1 Primal-Dual Table

The primal-dual table for linear programming (Table 6.2 ) also helps to highlight the correspondence between the two problems. It shows all the linear programming parameters (the \(a_{i j}, b_{i}\) and \(c_{j}\)) and how they are used to construct the two problems. All the headings for the primal problem are horizontal, whereas the headings for the dual problem are read by turning the book sideways. For the primal problem, each column (except the right-side column) gives the coefficients of a single variable in the respective constraints and then in the objective function, whereas each row (except the bottom one) gives the parameters for a single contraint. For the dual problem, each row (except the right-side row) gives the coefficients of a single variable in the respective constraints and then in the objective function, whereas each column (except the rightmost one) gives the parameters for a single constraint. In addition, the right-side column gives the right-hand sides for the primal problem and the objective function coefficients for the dual problem, whereas the bottom row gives the objective function coefficients for the primal problem and the right-hand sides for the dual problem.

Primal-Dual Table

Figure 1.1: Primal-Dual Table

Consequently, we now have the following general relationships between the primal and dual problems:
1. The parameters for a (functional) constraint in either problem are the coefficients of a variable in the other problem.
2. The coefficients in the objective function of either problem are the right-hand sides for the other problem.

1.2.2 SOB Rules

Primal-Dual Table

Figure 1.2: Primal-Dual Table

1.2.3 Primal-Dual Relationships

Definition 1.1 (Complementary optimal solutions property) At the final iteration, the simplex method simultaneously identifies an optimal solution \(\mathbf{x}^{*}\) for the primal problem and a complementary optimal solution \(\mathbf{y}^{*}\) for the dual problem (found in row 0, the coefficients of the slack variables, where \[ \mathbf{c x}^{*}=\mathbf{y}^{* \mathbf{b}} \] The \(y_{i}^{*}\) are the shadow prices for the primal problem.

The primal-dual relationships under all these possibilities can be summarized as: (Hillier 2012)

Theorem 1.1 (Duality) The following are the only possible relationships between the primal and dual problems.

  1. If one problem has feasible solutions and a bounded objective function (and so has an optimal solution), then so does the other problem, so both the weak and strong duality properties are applicable.
  2. If one problem has feasible solutions and an unbounded objective function (and so no optimal solution), then the other problem has no feasible solutions.
  3. If one problem has no feasible solutions, then the other problem has either no feasible solutions or an unbounded objective function.

1.2.4 Complementary Slackness

Assume that \(x\) is a feasible solution to the primal problem and \(y\) is a feasible solution to the dual problem. Then, a necessary and sufficient condition for \(x\) and \(y\) being optimal are: \[ \begin{align} & \sum_{j=1}^{n} a_{i j} x_{j}=b_{i} \text { or } y_{i}=0 \quad \forall i=1 \ldots m \\ & \sum_{i=1}^{m} a_{i j} y_{i}=c_{j} \text { or } x_{j}=0 \quad \forall j=1 \ldots n \end{align} \]

References

Hillier, Frederick S. 2012. Introduction to Operations Research. Tata McGraw-Hill Education.