Linear Programming — JEE MCQs with answers

Answer: A — For each objective compare the largest corner value $M$ with the open half plane $Z > M$. $Z = -2x + y$: corner values $2,\ 4,\ -4,\ -12$, so $M = 4$; every feasible point has $y \le x + 4$ (from $x - y \ge -4$) and $x \ge 0$, so $Z \le -2x + x + 4 = 4 - x \le 4$. The half plane $-2x + y > 4$ has no point in common with the region, and the maximum value is $4$, at $(0, 4)$. $Z = 2x - 3y$: $M = 12$, but the feasible point $(8, 1)$ ($7 \ge -4$, $9 \ge 2$, $6 \le 6$) gives $13$. $Z = -x + 3y$: $M = 12$, but the feasible point $(1, 5)$ ($1 - 5 = -4 \ge -4$, $6 \ge 2$, $1 - 10 = -9 \le 6$) gives $14$. $Z = 3x - 4y$: $M = 18$, but $(8, 1)$ gives $20$. These three have no maximum value.

Answer: D — The tables cost $12 \times 2500 = 30000$ and the chairs $30 \times 500 = 15000$, so he spends Rs 45,000 and $50000 - 45000 = 5000$ is left. The answer is option D. Rs 45,000 is the amount spent, not the amount left; Rs 20,000 is what would be left after paying for the tables alone; Rs 30,000 is the cost of the tables alone.

Answer: B — The points with $3x + 5y \le 15,\ x \ge 0,\ y \ge 0$ form a bounded region, the triangle with corner points $(0, 0)$, $(5, 0)$ and $(0, 3)$. At these corners $x + y$ equals $0$, $5$ and $3$, so its largest value on the triangle is $5$, at $(5, 0)$: option B. Since $5 < 8$, the constraint $x + y \ge 8$ fails at every such point, which is why the problem has no feasible region. Option A takes the corner $(0, 3)$ instead of $(5, 0)$. Option C combines the two intercepts into the point $(5, 3)$, which is not in the triangle because $3(5) + 5(3) = 30 > 15$. Option D assumes the largest value occurs where $x = y$, that is at $\left(\dfrac{15}{8}, \dfrac{15}{8}\right)$.

Answer: C — On p.394 the quotation ends '– G. POLYA' and the portrait is captioned 'L. Kantorovich'. That is option C. G. B. Dantzig and T. C. Koopmans are named only in the Historical Note at the end of the chapter.

Answer: D — The corner points are $(0, 3)$, $(1, 0)$, $(5, 0)$ and $(8, 2)$, where $Z = 6,\ -5,\ -25,\ -36$; so $M = 6$ ($-36$ is the largest only in size, and is in fact the smallest value). The feasible region is unbounded: $(0,\ 3 + t)$ is feasible for every $t \ge 0$. So $M$ is the maximum only if the open half plane $-5x + 2y > 6$ has no point in common with the region. But $(0, 4)$ is feasible ($0 - 12 = -12 \le 10$, $0 + 4 = 4 \ge 3$, $0 \le 8$, coordinates non-negative) and gives $Z = 8 > 6$. Hence $M = 6$, but $Z$ has no maximum value.

Answer: D — The Note calls it 'an efficient method known as the simplex method which is an iterative procedure to solve any linear programming problem in a finite number of steps' (p.405). That is option D. The Note does not restrict the method to the transportation problem, and it says the number of steps is finite.

Answer: A — $Z = 6$ at both corner points $(6, 0)$ and $(0, 3)$, and so at every point of the line segment joining them, which lies on $x + 2y = 6$ (p.401). The point $(2, 3)$ is feasible ($2x + y = 7 \ge 3$, $x + 2y = 8 \ge 6$) but is not on that segment: $Z = 8$ there. This is option A. Option B gives $Z = 4 + 2 = 6$; it lies on the segment joining $(6, 0)$ and $(0, 3)$. Option C gives $Z = 2 + 4 = 6$; it lies on the segment joining $(6, 0)$ and $(0, 3)$. Option D is a corner point, and $Z = 6$ there.

Answer: B — The story ends: he 'wants to know how many tables and chairs he should buy from the available money so as to maximise his total profit' (p.394). That is option B. The quantity to be decided is the number of each item bought, not a selling price, and the aim is the largest total profit, not the smallest cost.

Answer: D — Step 1 is right: $(2, 4)$ lies on $2x + y = 8$ and $x + 2y = 10$, and $(8, 1)$ lies on $x + 2y = 10$ and $x + y = 9$. Step 2 is right: all four points satisfy every constraint, the lines $2x + y = 8$ and $x + y = 9$ meet the $y$-axis at $(0, 8)$ and $(0, 9)$, and the region is a quadrilateral, hence bounded. Step 3 is right: $2 + 16 = 18$, $8 + 4 = 12$, $0 + 36 = 36$, $0 + 32 = 32$. Step 4 picks the largest value, $36$, which is the maximum of $Z$; the minimum asked for is the smallest value, $12$, at $(8, 1)$. So the error is in Step 4. The answer is option D.

Answer: C — Fourteen tables cost $14 \times 2500 = 35000$, leaving Rs 15,000, which buys $15000 \div 500 = 30$ chairs (44 pieces in all, within the 60 he can store). The profit is $14 \times 250 + 30 \times 75 = 3500 + 2250 = 5750$. The answer is option C. Taking 46 chairs, the number that would fill the storage space, gives $3500 + 46 \times 75 = 6950$, but 14 tables and 46 chairs cost Rs 58,000, more than he has. Rs 2250 and Rs 3450 are the profits on the 30 chairs and on the 46 chairs alone, with the tables left out.