Bubbles Brewery Dual Formulation

The purpose of constructing the dual is to gain insights into the original problem’s structure, such as sensitivity analysis and economic interpretations, and it often provides computational advantages, especially in large-scale optimization. The solutions of the primal and dual problems also satisfy the principle of strong duality, meaning if both problems are feasible, their optimal values are equal.

Bubbles Brewery Primal Formulation

First, we will restate the original, primal Bubbles Brewery optimization model.

Objective function

\( \max 13x_1 + 23x_2 \)

Constraints

corn: \( 5x_1 + 15x_2 \le 480 \)

hops: \( 4x_1 + 4x_2 \le 160 \)

malt: \( 35x_1 + 20x_2 \le 1,190 \)

\(x_1 \ge 0, x_2 \ge 0\)

Standard notation

The optimization problem can be expressed in this form by representing the values as matrices and vectors.

$$
\begin{array}{r r l}
\text{max} & C^T x & \\
\text{s.t.} & Ax & \le b \\
& x & \! \ge 0
\end{array}
$$

For this specific problem, the values for \(C\), \(A\), \(b\), and \(x\) are as follows.

$$C = \begin{bmatrix}13 & 23\end{bmatrix}$$

$$A = \begin{bmatrix}5 & 15 \\ 4 & 4 \\ 35 & 20 \end{bmatrix}$$

$$b = \begin{bmatrix}480 & 160 & 1,190\end{bmatrix}$$

$$x = \begin{bmatrix}x_1 & x_2\end{bmatrix}$$

Bubbles Brewery Dual Formulation

To switch a primal optimization problem to its dual formulation, you must reformulate the problem by associating each primal constraint with a corresponding dual variable. The primal's objective function becomes the dual's constraints, and the primal's constraints become the dual's objective function. For maximization problems, the dual is a minimization problem and vice versa (for linear problems). The coefficients in the primal are reorganized to reflect resource prices or shadow prices in the dual.

Standard notation

$$
\begin{array}{r r l}
\text{min} & b y & \\
\text{s.t.} & A^Ty & \ge C \\
& y & \! \ge 0
\end{array}
$$

Below is the dual formulation for this specific problem:

Objective function

\( \min 480 y_1 + 160 y_2 + 1,190 y_3 \)

Constraints

light beer: \(5y_1 + 4y_2 + 35y_3 \ge 13\)

dark beer: \(15y_1 + 4y_2 + 20y_3 \ge 23\)

\(y_1 \ge 0, y_2 \ge 0, y_3 \ge 0\)

Model Solutions

On the left is the solution file from the original primal Bubbles Brewery optimization model, and on the right is the solution file from the dual problem formulated above. Notice that the bottom half of the left solution matches the top half of the right solution, and vice versa. This demonstrates how the dual solution is derived. For an interpretation of the output values in a business context, refer to the Output JSON article.

If you want to try this yourself, the primal and dual .mps files are attached below for you to download.

{
"objective": {
  "profit": 800
},
"primal": {
  "variables": {
    "decision": {
      "dark_beer": 28,
      "light_beer": 12
    },
    "slack": {
      "corn": 0,
      "hops": 0,
      "malt": 210
    }
  }
},
"dual": {
  "variables": {
    "decision": {
      "corn": 1,
      "hops": 2,
      "malt": 0
    },
    "slack": {
      "dark_beer": 0,
      "light_beer": 0
    }
  }
}
}

{
"objective": {
  "dual_profit": 800
},
"primal": {
  "variables": {
    "decision": {
      "corn": 1,
      "hops": 2,
      "malt": 0
    },
    "slack": {
      "dark_beer": 0,
      "light_beer": 0
    }
  }
},
"dual": {
  "variables": {
    "decision": {
      "dark_beer": 28,
      "light_beer": 12
    },
    "slack": {
      "corn": 0,
      "hops": 0,
      "malt": 210
    }
  }
}
}