Duality - Linear Programming - Mathematics Previous Year Questions

1

2008 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2008

Let a primal linear programming problem admit an optimal solution. Then the corresponding dual problem

A

does not have a feasible solution

B

has a feasible solution but does not have any optimal solution

C

does not have a convex feasible region

D

has an optimal solution

Open complete paper

2

2009 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2009

The dual of the linear programming problem:
Minimize c^Tx subject to Ax ≥ b and x ≥ 0 is

A

Maximize b^Tw subject to A^Tw ≤ c and w ≥ 0

B

Maximize b^Tw subject to A^Tw ≤ c and w ≥ 0

C

Maximize b^Tw subject to A^Tw ≤ c and w is unrestricted

D

Maximize b^Tw subject to A^Tw ≥ c and w is unrestricted

Open complete paper

3

2010 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2010

Which one of the following statements is correct?

A

If a Linear Programming Problem (LPP) is infeasible, then its dual is also infeasible

B

If an LPP is infeasible, then its dual always has unbounded solution

C

If an LPP has unbounded solution, then its dual also has unbounded solution

D

If an LPP has unbounded solution, then its dual is infeasible

Open complete paper

4

2011 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2011

Consider the Primal Linear Programming Problem:
Maximize \( z = c_1x_1 + c_2x_2 + \cdots + c_nx_n \)
subject to
\( a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 \)
\( a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 \)
\( \vdots \)
\( a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m \)
\( x_j \geq 0, j = 1, \ldots, n. \)
The Dual of P is
Minimize \( z' = b_1w_1 + b_2w_2 + \cdots + b_mw_m \)
subject to
\( a_{11}w_1 + a_{21}w_2 + \cdots + a_{m1}w_m \geq c_1 \)
\( a_{12}w_1 + a_{22}w_2 + \cdots + a_{m2}w_m \geq c_2 \)
\( \vdots \)
\( a_{1n}w_1 + a_{2n}w_2 + \cdots + a_{mn}w_m \geq c_n \)
\( w_i \geq 0, i = 1, \ldots, m. \)
Which of the following statements is FALSE?

A

If P has an optimal solution, then D also has an optimal solution

B

The dual of the dual problem is a primal problem

C

If P has an unbounded solution, then D has no feasible solution

D

If P has no feasible solution, then D has a feasible solution

Open complete paper

5

2012 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2012

If \( y_{1} \) and \( y_{2} \) are the dual variables corresponding to the first and second primal constraints, then their values in the optimal solution of the dual problem are, respectively,

A

0 and 6

B

12 and 0

C

6 and 3

D

4 and 4

Open complete paper

6

2014 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2014

Consider the following linear programming problem:

Minimize: \(x_1 + x_2 + 2x_3\)
Subject to
\(x_1 + 2x_2 \geq 4\)
\(x_2 + 7x_3 \leq 5\)
\(x_1 - 3x_2 + 5x_3 = 6\)
\(x_1, x_2 \geq 0\), \(x_3\) is unrestricted

The dual to this problem is:

Maximize: \(4y_1 + 5y_2 + 6y_3\)
Subject to
\(y_1 + y_3 \leq 1\)
\(2y_1 + y_2 - 3y_3 \leq 1\)
\(7y_2 + 5y_3 = 2\)
and further subject to:

A

\(y_1 \geq 0, y_2 \leq 0\) and \(y_3\) is unrestricted

B

\(y_1 \geq 0, y_2 \geq 0\) and \(y_3\) is unrestricted

C

\(y_1 \geq 0, y_3 \leq 0\) and \(y_2\) is unrestricted

D

\(y_2 \geq 0, y_3 \leq 0\) and \(y_1\) is unrestricted

Open complete paper

7

2017 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2017

For a linear programming problem (LPP) and its dual, which one of the following is NOT TRUE?

A

The dual of the dual is primal

B

If the primal LPP has an unbounded objective function, then the dual LPP is infeasible

C

If the primal LPP is infeasible, then the dual LPP must have unbounded objective function

D

If the primal LPP has a finite optimal solution, then the dual LPP also has a finite optimal solution

Open complete paper

8

2018 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2018

For a linear programming problem, which one of the following statements is FALSE?

A

If a constraint is an equality, then the corresponding dual variable is unrestricted in sign

B

Both primal and its dual can be infeasible

C

If primal is unbounded, then its dual is infeasible

D

Even if both primal and dual are feasible, the optimal values of the primal and the dual can differ

Open complete paper

9

2019 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2019

For the linear programming problem (LPP): Maximize \(Z = 2x_1 + 4x_2\) subject to \(-x_1 + 2x_2 \le 4\), \(3x_1 + \beta x_2 \le 6\), \(x_1, x_2 \ge 0\), \(\beta \in \mathbb{R}\), (\(\mathbb{R}\) is the set of all real numbers) consider the following statements: I. The LPP always has a finite optimal value for any \(\beta \ge 0\). II. The dual of the LPP may be infeasible for some \(\beta \ge 0\). III. If for some \(\beta\), the point \((1,2)\) is feasible to the dual of the LPP, then \(Z \le 16\), for any feasible solution \((x_1,x_2)\) of the LPP. IV. If for some \(\beta\), \(x_1\) and \(x_2\) are the basic variables in the optimal table of the LPP with \(x_1 = \frac{1}{2}\), then the optimal value of dual of the LPP is 10. Then which of the above statements are TRUE? (A) I and III only (B) I, III and IV only (C) III and IV only (D) II and IV only

A

I and III only

B

I, III and IV only

C

III and IV only

D

II and IV only

Open complete paper

10

2020 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2020

If \((x_1^*, x_2^*)\) is an optimal solution of the linear programming problem,
minimize \(x_1 + 2x_2\)
subject to
\(4x_1 - x_2 \ge 8\)
\(2x_1 + x_2 \ge 10\)
\(-x_1 + x_2 \le 7\)
\(x_1, x_2 \ge 0\)
and \((\lambda_1^*, \lambda_2^*, \lambda_3^*)\) is an optimal solution of its dual problem, then \(\sum_{i=1}^3 x_i^* + \sum_{j=1}^3 \lambda_j^*\) is equal to __________ (correct up to one decimal place)

Check answer

Open complete paper

11

2020 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2020

Let \(\alpha \in \mathbb{R}\). If \((3,0,0,\beta)\) is an optimal solution of the linear programming problem \[ \text{minimize } x_1 + x_2 + x_3 - \alpha x_4 \] subject to \[ \begin{aligned} 2x_1 - x_2 + x_3 &= 6 \\ -x_1 + x_2 + x_4 &= 3 \\ x_1, x_2, x_3, x_4 &\ge 0 \end{aligned} \] then the maximum value of \(\beta - \alpha\) is ________

Check answer

Open complete paper

12

2020 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2020

If (D1) and (D2) denote the dual problems of the linear programming problems (P1) and (P2), respectively, where \((P1): \text{minimize } x_1 - 2x_2 \text{ subject to } -x_1 + x_2 = 10, x_1, x_2 \geq 0,\) \((P2): \text{minimize } x_1 - 2x_2 \text{ subject to } -x_1 + x_2 = 10, x_1 - x_2 = 10, x_1, x_2 \geq 0,\) then

A

both (D1) and (D2) are infeasible

B

(P2) is infeasible and (D2) is feasible

C

(D1) is infeasible and (D2) is feasible but unbounded

D

(P1) is feasible but unbounded and (D1) is feasible

Open complete paper

13

2021 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2021

Consider the Linear Programming Problem \(P\):
Maximize \(2x_1 + 3x_2\)
subject to
\(2x_1 + x_2 \le 6\), \(-x_1 + x_2 \le 1\), \(x_1 + x_2 \le 3\), \(x_1 \ge 0\) and \(x_2 \ge 0\).
Then the optimal value of the dual of \(P\) is equal to ________.

Check answer

Open complete paper

14

2021 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2021

Consider the Linear Programming Problem $P$:
Maximize $c_1 x_1 + c_2 x_2$
subject to
$a_{11} x_1 + a_{12} x_2 \le b_1$,
$a_{21} x_1 + a_{22} x_2 \le b_2$,
$a_{31} x_1 + a_{32} x_2 \le b_3$,
$x_1 \ge 0$ and $x_2 \ge 0$, where $a_{ij}, b_i$ and $c_j$ are real numbers $(i = 1, 2, 3; j = 1, 2)$.
Let $\begin{bmatrix} p \\ q \end{bmatrix}$ be a feasible solution of $P$ such that $p c_1 + q c_2 = 6$ and let all feasible solutions $\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ of $P$ satisfy $-5 \le c_1 x_1 + c_2 x_2 \le 12$.
Then, which one of the following statements is NOT true?

A

$P$ has an optimal solution

B

The feasible region of $P$ is a bounded set

C

If $\begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix}$ is a feasible solution of the dual of $P$, then $b_1 y_1 + b_2 y_2 + b_3 y_3 \ge 6$

D

The dual of $P$ has at least one feasible solution

Open complete paper

15

2021 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2021

Let \(\bar{x} = \begin{bmatrix} 11/3 \\ 2/3 \\ 0 \end{bmatrix}\) be an optimal solution of the following Linear Programming Problem \(P\):
Maximize \(4x_1 + x_2 - 3x_3\)
subject to
\(2x_1 + 4x_2 + ax_3 \le 10\),
\(x_1 - x_2 + bx_3 \le 3\),
\(2x_1 + 3x_2 + 5x_3 \le 11\),
\(x_1 \ge 0, x_2 \ge 0\) and \(x_3 \ge 0\), where \(a, b\) are real numbers.
If \(\bar{y} = \begin{bmatrix} p \\ q \\ r \end{bmatrix}\) is an optimal solution of the dual of \(P\), then \(p + q + r = \) ________ (round off to two decimal places).

Check answer

Open complete paper

16

2022 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2022

Let \( y = (\alpha, -1)^T \), \( \alpha \in \mathbb{R} \) be a feasible solution for the dual problem of the linear programming problem
Maximize: \( 5x_1 + 12x_2 \)
subject to: \( x_1 + 2x_2 + x_3 \le 10 \)
\( 2x_1 - x_2 + 3x_3 = 8 \)
\( x_1, x_2, x_3 \ge 0 \).
Which of the following statements is TRUE?

A

\(\alpha < 3 \)

B

\(3 \le \alpha < 5.5 \)

C

\(5.5 \le \alpha < 7 \)

D

\(\alpha \ge 7 \)

Open complete paper

17

2022 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2022

Let \(A \in \mathbb{R}^{m \times n}\), \(c \in \mathbb{R}^n\) and \(b \in \mathbb{R}^m\). Consider the linear programming primal problem
Minimize: \(c^T x\)
subject to: \(Ax = b\)
\(x \geq 0\).
Let \(x^0\) and \(y^0\) be feasible solutions of the primal and its dual, respectively. Which of the following statements are TRUE?

A

\(c^T x^0 \geq b^T y^0\)

B

\(c^T x^0 = b^T y^0\)

C

If \(c^T x^0 = b^T y^0\), then \(x^0\) is optimal for the primal

D

If \(c^T x^0 = b^T y^0\), then \(y^0\) is optimal for the dual

Check answer

Open complete paper

18

2025 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2025

Consider the linear programming problem (LPP):
Maximize \(Z = 3x_1 + 5x_2\)
Subject to \(x_1 + x_3 = 4\),
\(2x_2 + x_4 = 12\),
\(3x_1 + 2x_2 + x_5 = 18\),
\(x_1, x_2, x_3, x_4, x_5 \geq 0\).
Given that \(x_B = (x_3, x_2, x_1)^T\) forms the optimal basis of the LPP with basis matrix \(B\) and respective \(B^{-1} = \begin{bmatrix} \alpha & \beta & -\beta \\ 0 & \gamma & 0 \\ 0 & -\beta & \beta \end{bmatrix}\). If \((p, q, r)\) is the optimal solution of the dual of the LPP, then which of the following is/are TRUE?

A

\(\alpha + 3\beta + 2\gamma = 3\)

B

\(\alpha - 3\beta + 4\gamma = 1\)

C

\(p + q + r = \frac{5}{2}\)

D

\(p^2 + q^2 + r^2 = \frac{17}{4}\)

Check answer

Open complete paper

19

2007 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2007

Consider the linear programming problem,
Max. \(z = c_1x_1 + c_2x_2, \; c_1, c_2 > 0,\)
subject to
\(x_1 + x_2 \leq 3\)
\(2x_1 + 3x_2 \leq 4\)
\(x_1, x_2 \geq 0.\)
Then,

A

the primal has an optimal solution but the dual does NOT have an optimal solution

B

both the primal and the dual have optimal solutions

C

the dual has an optimal solution but the primal does NOT have an optimal solution

D

neither the primal nor the dual have optimal solutions

Open complete paper

20

2007 · Mathematics · Linear Programming · Duality

Mathematics (MA) 2007

Consider the linear programming problem \[\begin{aligned} \text{Max. } & z = x_1 + 5x_2 + 3x_3 \\ \text{subject to } & 2x_1 - 3x_2 + 5x_3 \le 3 \\ & 3x_1 + 2x_2 \le 5 \\ & x_1, x_2, x_3 \ge 0. \end{aligned}\] Then the dual of this LP problem

A

has a feasible solution but does NOT have a basic feasible solution

B

has a basic feasible solution

C

has infinite number of feasible solutions

D

has no feasible solution

Open complete paper