The GATE Grind

GATE 2026 ME – Question 46

Operations Research · Linear programming and the simplex method · 2 marks · Multiple choice

An objective function $Z$ of primal variables ($x_1$ and $x_2$) is described below:

Minimize $Z = 0.07\,x_1 + 0.05\,x_2$

subject to $0.1\,x_1 \geq 0.4$, $0.1\,x_2 \geq 0.6$, $0.1\,x_1 + 0.2\,x_2 \geq 2.0$, $0.2\,x_1 + 0.1\,x_2 \geq 1.8$, $x_1, x_2 \geq 0$

$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$?

  1. Maximize $W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4$ subject to $0.1k_1 + 0.1k_3 + 0.2k_4 \leq 0.07$, $0.1k_2 + 0.2k_3 + 0.1k_4 \leq 0.05$, $k_1, k_2, k_3, k_4 \geq 0$
  2. Maximize $W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4$ subject to $0.1k_1 + 0.1k_2 + 0.2k_4 \leq 0.07$, $0.1k_2 + 0.2k_3 + 0.1k_4 \leq 0.05$, $k_1, k_2, k_3, k_4 \geq 0$
  3. Maximize $W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4$ subject to $0.1k_1 + 0.1k_2 + 0.2k_4 \leq 0.05$, $0.1k_1 + 0.2k_3 + 0.1k_4 \leq 0.07$, $k_1, k_2, k_3, k_4 \geq 0$
  4. Maximize $W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4$ subject to $0.1k_1 + 0.1k_3 + 0.2k_4 \leq 0.05$, $0.1k_2 + 0.2k_3 + 0.1k_4 \leq 0.07$, $k_1, k_2, k_3, k_4 \geq 0$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Maximize $W = 0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4$ subject to $0.1k_1 + 0.1k_3 + 0.2k_4 \leq 0.07$, $0.1k_2 + 0.2k_3 + 0.1k_4 \leq 0.05$, $k_1, k_2, k_3, k_4 \geq 0$

Explanation

The dual of a minimization with "$\geq$" constraints is a maximization. The objective uses the right-hand sides, $0.4k_1 + 0.6k_2 + 2.0k_3 + 1.8k_4$. There is one dual constraint for each primal variable, built from the column of that variable, and bounded by its cost. For $x_1$ the column is $(0.1, 0, 0.1, 0.2)$, which gives $0.1k_1 + 0.1k_3 + 0.2k_4 \leq 0.07$. For $x_2$ the column is $(0, 0.1, 0.2, 0.1)$, which gives $0.1k_2 + 0.2k_3 + 0.1k_4 \leq 0.05$.