Question

An objective function \(Z\) of primal variables (\(x_1\) and \(x_2\)) is described below:
\[ \begin{gathered} \text{Minimize } Z = 0.07x_1 + 0.05x_2 \\ \text{subject to} \\ 0.1x_1 \ge 0.4 \\ 0.1x_2 \ge 0.6 \\ 0.1x_1 + 0.2x_2 \ge 2.0 \\ 0.2x_1 + 0.1x_2 \ge 1.8 \\ x_1, x_2 \ge 0 \end{gathered} \]
\(W\) is the objective function of the dual of \(Z\). \(k_1\), \(k_2\), \(k_3\), and \(k_4\) represent the corresponding dual variables. Which one of the following options represents the correct form of \(W\)?

• A. \[ \begin{gathered} \text{Maximize } W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4 \\ \text{subject to} \\ 0.1k_1 + 0.1k_3 + 0.2k_4 \le 0.07 \\ 0.1k_2 + 0.2k_3 + 0.1k_4 \le 0.05 \\ k_1, k_2, k_3, k_4 \ge 0 \end{gathered} \]
• B. \[ \begin{gathered} \text{Maximize } W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4 \\ \text{subject to} \\ 0.1k_1 + 0.1k_2 + 0.2k_4 \le 0.07 \\ 0.1k_2 + 0.2k_3 + 0.1k_4 \le 0.05 \\ k_1, k_2, k_3, k_4 \ge 0 \end{gathered} \]
• C. \[ \begin{gathered} \text{Maximize } W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4 \\ \text{subject to} \\ 0.1k_1 + 0.1k_2 + 0.2k_4 \le 0.05 \\ 0.1k_1 + 0.2k_3 + 0.1k_4 \le 0.07 \\ k_1, k_2, k_3, k_4 \ge 0 \end{gathered} \]
• D. \[ \begin{gathered} \text{Maximize } W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4 \\ \text{subject to} \\ 0.1k_1 + 0.1k_3 + 0.2k_4 \le 0.05 \\ 0.1k_2 + 0.2k_3 + 0.1k_4 \le 0.07 \\ k_1, k_2, k_3, k_4 \ge 0 \end{gathered} \]

Hint:

Build the dual by transposing the constraint coefficient matrix, one dual constraint per primal variable.

Answer 1

The Correct Option is A

Step 1: Write the primal in matrix form.
Collect the constraint coefficients into a matrix $A$, with $x_1$ and $x_2$ as columns and the four constraints as rows: $$A = \begin{pmatrix} 0.1 & 0 \\ 0 & 0.1 \\ 0.1 & 0.2 \\ 0.2 & 0.1 \end{pmatrix}$$ The right hand side vector is $b = (0.4, 0.6, 2.0, 1.8)$ and the cost vector is $c = (0.07, 0.05)$.

Step 2: Recall the dual recipe for a min problem with greater-or-equal constraints.
For minimizing $c^Tx$ subject to $Ax \ge b$, $x \ge 0$, the dual is maximizing $b^Tk$ subject to $A^Tk \le c$, $k \ge 0$, where $A^T$ is $A$ with rows and columns swapped.

Step 3: Transpose the matrix.
$$A^T = \begin{pmatrix} 0.1 & 0 & 0.1 & 0.2 \\ 0 & 0.1 & 0.2 & 0.1 \end{pmatrix}$$ Each row of $A^T$ now becomes one dual constraint, read against $c$.

Step 4: Write out the dual constraints from $A^Tk \le c$.
Row 1 of $A^T$ times $k$ gives $0.1k_1 + 0k_2 + 0.1k_3 + 0.2k_4 \le 0.07$, and row 2 gives $0k_1 + 0.1k_2 + 0.2k_3 + 0.1k_4 \le 0.05$. Dropping the zero terms leaves $0.1k_1+0.1k_3+0.2k_4 \le 0.07$ and $0.1k_2+0.2k_3+0.1k_4 \le 0.05$, together with $W = 0.4k_1+0.6k_2+2.0k_3+1.8k_4$ to maximize.

Final Answer:
This transpose calculation lines up exactly with option (A), so that is the correct dual. \[ \boxed{\text{Option A}} \]