Linear Programming Formulation Questions and Answers

Q: The problem of maximizing \(z = x_{1} - x_{2}\) subject to constraints \(x_{1} + x_{2} \le 10\), \(x_{1} \ge 0\), \(x_{2} \ge 0\) and \(x_{2} \le 5\) has

The problem has one solution.The feasible region is the polygon with vertices (0, 0), (10, 0), (5, 5) and (0, 5), bounded by the axes, \(x_{1} + x_{2} \le 10\) and \(x_{2} \le 5\). A linear objective reaches its maximum at a vertex:\[ \begin{aligned} z(0,0) &= 0, \quad z(10,0) = 10 \\ z(5,5) &= 0, \quad z(0,5) = -5 \end{aligned} \]The maximum, z = 10, occurs only at (10, 0). Multiple optima would need the objective's contour lines to lie parallel to an edge through the best vertex; here the edges meeting at (10, 0) are \(x_{2} = 0\) and \(x_{1} + x_{2} = 10\), neither parallel to \(x_{1} - x_{2} = \text{constant}\). The region is bounded and non-empty, so a solution exists, ruling out 'no solution'.

Q: A manufacturing unit produces two products P1 and P2. For each piece of P1 and P2, the table below provides quantities of materials M1, M2, and M3 required, and also the profit earned. The maximum quantity available per day for M1, M2 and M3 is also provided. The maximum possible profit per day is ₹__________.M1M2M3Profit per piece (₹)P1220150P2312100Maximum quantity available per day705040

The maximum profit is ₹4000 per day.Let \(x\) and \(y\) be the daily output of P1 and P2. The linear programme is:\[ \begin{aligned} \max\ Z &= 150x + 100y \\ 2x + 3y &\le 70 \quad (M1) \\ 2x + y &\le 50 \quad (M2) \\ 2y &\le 40 \quad (M3) \end{aligned} \]The optimum lies at a corner of the feasible region. The M1 and M2 lines meet where \(2y = 20\), so \(y = 10\), \(x = 20\), which also satisfies M3. Evaluating the corners:(25, 0), limited by M2: \(Z = 3750\)(20, 10), M1 and M2: \(Z = 3000 + 1000 = 4000\)(5, 20), M1 and M3: \(Z = 750 + 2000 = 2750\)(0, 20): \(Z = 2000\)The maximum is 4000 at 20 pieces of P1 and 10 of P2. 5000 and 6000 would need more material than is available (for example, 6000 needs 40 pieces of P1, using 80 units of M2 against 50), and 3000 is below an achievable corner.

Q: Which one of the options given represents the feasible region of the linear programming model:\(\mathit{Maximize}\ 45X_{1} + 60X_{2}\)\(X_{1} \le 45\)\(X_{2} \le 50\)\(10X_{1} + 10X_{2} \ge 600\)\(25X_{1} + 5X_{2} \le 750\)

The feasible region is Region Q.Simplify the constraints: \(10X_{1} + 10X_{2} \ge 600\) is \(X_{1} + X_{2} \ge 60\), and \(25X_{1} + 5X_{2} \le 750\) is \(5X_{1} + X_{2} \le 150\). A feasible point must liebelow the horizontal line \(X_{2} = 50\);on or above the gently sloping line \(X_{1} + X_{2} = 60\) (intercept 60 on each axis);on or left of the steep line \(5X_{1} + X_{2} = 150\) (intercept 30 on the \(X_{1}\) axis), which already keeps \(X_{1} \le 30 \lt 45\).These meet in a small triangle with corners (10, 50), (20, 50) and (22.5, 37.5), the shaded Region Q.Region P lies below \(X_{1} + X_{2} = 60\), so it breaks the \(\ge 600\) constraint. Region S lies to the right of the steep line, breaking \(25X_{1} + 5X_{2} \le 750\). Region R breaks both.

The problem of maximizing \(z = x_{1} - x_{2}\) subject to constraints \(x_{1} + x_{2} \le 10\), \(x_{1} \ge 0\), \(x_{2} \ge 0\) and \(x_{2} \le 5\) has

A.no solution
B.one solution
C.two solutions
D.more than two solutions

Exam Year(s)

GATE ME - 2018,

Answer: B

The problem has one solution.

The feasible region is the polygon with vertices (0, 0), (10, 0), (5, 5) and (0, 5), bounded by the axes, \(x_{1} + x_{2} \le 10\) and \(x_{2} \le 5\). A linear objective reaches its maximum at a vertex:

\[ \begin{aligned} z(0,0) &= 0, \quad z(10,0) = 10 \\ z(5,5) &= 0, \quad z(0,5) = -5 \end{aligned} \]

The maximum, z = 10, occurs only at (10, 0). Multiple optima would need the objective's contour lines to lie parallel to an edge through the best vertex; here the edges meeting at (10, 0) are \(x_{2} = 0\) and \(x_{1} + x_{2} = 10\), neither parallel to \(x_{1} - x_{2} = \text{constant}\). The region is bounded and non-empty, so a solution exists, ruling out 'no solution'.

Discuss in Forum

A manufacturing unit produces two products P1 and P2. For each piece of P1 and P2, the table below provides quantities of materials M1, M2, and M3 required, and also the profit earned. The maximum quantity available per day for M1, M2 and M3 is also provided. The maximum possible profit per day is ₹__________.

	M1	M2	M3	Profit per piece (₹)
P1	2	2	0	150
P2	3	1	2	100
Maximum quantity available per day	70	50	40

A.5000
B.4000
C.3000
D.6000

Exam Year(s)

GATE ME - 2022,

Answer: B

The maximum profit is ₹4000 per day.

Let \(x\) and \(y\) be the daily output of P1 and P2. The linear programme is:

\[ \begin{aligned} \max\ Z &= 150x + 100y \\ 2x + 3y &\le 70 \quad (M1) \\ 2x + y &\le 50 \quad (M2) \\ 2y &\le 40 \quad (M3) \end{aligned} \]

The optimum lies at a corner of the feasible region. The M1 and M2 lines meet where \(2y = 20\), so \(y = 10\), \(x = 20\), which also satisfies M3. Evaluating the corners:

(25, 0), limited by M2: \(Z = 3750\)
(20, 10), M1 and M2: \(Z = 3000 + 1000 = 4000\)
(5, 20), M1 and M3: \(Z = 750 + 2000 = 2750\)
(0, 20): \(Z = 2000\)

The maximum is 4000 at 20 pieces of P1 and 10 of P2. 5000 and 6000 would need more material than is available (for example, 6000 needs 40 pieces of P1, using 80 units of M2 against 50), and 3000 is below an achievable corner.

Discuss in Forum

Which one of the options given represents the feasible region of the linear programming model:

\(\mathit{Maximize}\ 45X_{1} + 60X_{2}\)
\(X_{1} \le 45\)
\(X_{2} \le 50\)
\(10X_{1} + 10X_{2} \ge 600\)
\(25X_{1} + 5X_{2} \le 750\)

Constraint lines on X1 and X2 axes, not to scale, with four shaded areas labelled Region P, Region Q, Region R and Region S

A.Region P
B.Region Q
C.Region R
D.Region S

Exam Year(s)

GATE ME - 2023,

Answer: B

The feasible region is Region Q.

Simplify the constraints: \(10X_{1} + 10X_{2} \ge 600\) is \(X_{1} + X_{2} \ge 60\), and \(25X_{1} + 5X_{2} \le 750\) is \(5X_{1} + X_{2} \le 150\). A feasible point must lie

below the horizontal line \(X_{2} = 50\);
on or above the gently sloping line \(X_{1} + X_{2} = 60\) (intercept 60 on each axis);
on or left of the steep line \(5X_{1} + X_{2} = 150\) (intercept 30 on the \(X_{1}\) axis), which already keeps \(X_{1} \le 30 \lt 45\).

These meet in a small triangle with corners (10, 50), (20, 50) and (22.5, 37.5), the shaded Region Q.

Region P lies below \(X_{1} + X_{2} = 60\), so it breaks the \(\ge 600\) constraint. Region S lies to the right of the steep line, breaking \(25X_{1} + 5X_{2} \le 750\). Region R breaks both.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Linear Programming Formulation Questions and Answers || Linear Programming Formulation MCQ Questions and Answers || Linear Programming Formulation GK Questions and Answers || Linear Programming Formulation GK MCQ Questions || Linear Programming Formulation Multiple Choice Questions and Answers || Linear Programming Formulation GK || GK on Linear Programming Formulation || Operations Research Questions and Answers || Operations Research MCQ Questions and Answers || Operations Research GK Questions and Answers || GK on Operations Research

Linear Programming Formulation Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications