GATE Past Year Questions: Linear Programming | Industrial Engineering - Mechanical Engineering PDF Download

Q1: At the current basic feasible solution (bfs)  the simplex method yields the following form of a linear programming problem in standard form.  
Here the objective function is written as a function of the non-basic variables. If the simplex method moves to the adjacent bfs   that best improves the objective function, which of the following represents the objective function at v₁, assuming that the objective function is written in the same matter as above?  [GATE ME 2024]
(a) z = −4 − 5x₁ + 2x₃
(b) z = −3 + x₅ − 2x₂
(c) z = −4 − 5x₁ − 2x₄
(d) z = −6 − 5x₁ + 2x₃
Ans: (a)
z = -x₁ - 2x₂  ...(A)
x₃ = 2 + 2x₁ - x₂  ...(i)
x₄ = 7 + x₁ - 2x₂  ...(ii)
x₅ = 3 - x  ...(iii)
and x₁, x₂, x₃, x₄, x₅ ≥ 0
From eq. (i):
x₂ = 2 + 2x₁ - x₃
Putting this value in the objective function eq. (A):
z = -x₁ - 2(2 + 2x₁ - x₃)
z = -4 - 5x₁ + 2x₃
From equation (ii):
x₁ = x₄ + 2x₂ − 7
Substitute this value in equation (A):
z = − (x₄ + 2x₂ − 7) − 2x₂
= 7 − 4x₂ − x₄
From equation (iii):
x₁ = 3 − x₅
Substitute this value in equation (A):
z = − (3 − x₅) − 2x₂
= x₅ − 3 − 2x₂
(A) and (B) both are correct but question type is mcq so go for option (A).

Q1: Which one of the options given represents the feasible region of the linear programming model:  [GATE ME 2023]

(a) Region P
(b) Region Q
(c) Region R
(d) Region S
Ans: (b)
x₁ = 45  ... (i)
x₂ = 50  ... (ii)
10x₁ + 10x₂ = 600
or x₁ + x₂ = 60  ... (iii)
25x₁ + 5x₂ = 750
or 5x₁ + x₂ = 150  ... (iv)
By drawing the curve, we get 3 values of x₁ and x₂ as (10, 50), (20, 50), (22.5, 37.5).
So, Zmax = 45x₁ + 60x₂ for (10, 50)
Zmax = 45 × 10 + 60 × 50 = 4450
For (20, 50)
Zmax = 45 × 20 + 50 × 60 = 3900
For (22.5, 37.5)
Zmax = 45 × 22.5 + 60 × 37.5 = 3262.5
So, Zmax = 3900 for (x₁, x₂) = (20, 50)

Q1: A manufacturing unit produces two products P1 and P2. For each piece of P1 an 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 Rs __________.  [GATE ME 2022 SET-2]
(a) 5000
(b) 4000
(c) 3000
(d) 6000
Ans: (b)
Let,
x₁ = Number of units of product P₁
x₂ = Number of units of product P₂
Max, Z = 150x₁ + 100x₂
Subject to:
2x₁ + 3x₂ ≤ 70
2x₁ + 3x₂ ≤ 50
2x₂ ≤ 40
x₁ ≥ 0, x₂ ≥ 0
Point B: Intersection of
2x₁ + 3x₂ ≤ 70
2x₂ ≤ 40
x₂ = 20, x₁ = 5
Point C: Intersection of
2x₁ + 3x₂ ≤ 70
2x₁ + x₂ ≤ 50
By solving 2x₂ = 20
⇒ x₂ = 10, x₁ = 20

Zₘₐₓ = 150x₁ + 100x₂
Z|(A(0,20)) = 150(0) + 100(20) = 2000
Z|(B(5,20)) = 150(5) + 100(20) = 2750
Z|(C(20,10)) = 150(20) + 100(10) = 4000
Z|(D(25,0)) = 150(25) + 100(0) = 3750
⇒ x₁ = 20, x₂ = 10
Zₘₐₓ = 4000

Q2: In a linear programming problem, if a resource is not fully utilized, the shadow price of that resource is  [GATE ME 2022 SET-1]
(a) positive
(b) negative
(c) zero
(d) infinity
Ans: (c)
In a Linear programming problem if a resource is not fully utilized. The shadow price or dual price of the particular resource is zero.

Q1: Two business owners Shveta and Ashok run their businesses in two different states. Each of them, independent of the other, produces two products A and B, sells them at Rs. 2,000 per kg and Rs, 3,000 per kg, respectively, and uses Linear Programming to determine the optimal quantity of A and B to maximize their respective daily revenue. Their constraints are as follows: i) for each business owner, the production process is such that the daily production of A has to be at least as much as B, and the upper limit for production of B is 10 kg per day, and ii) the respective state regulations restrict Shveta?s production of A to less than 20 kg per day and Ashok's production of A to less than 15 kg per day. The demand of both A and B in both the states is very high and everything produced is sold.
The absolute value of the difference in daily (optimal) revenue of Shveta and Ashok is ________ thousand Rupees (round off to 2 decimal places)  [GATE ME 2020 SET-1]
Ans: 9.9 to 10.1
Maximum z = 2000x₁ + 3000x₂
A → x₁ units, x₁ ≥ x₂
B → x₂ units, x₂ ≥ 10
x₂ < 20
x₁ < 15
Shveta’s Profit = Rs. 70,000 at (20, 10)
Ashok’s Profit = Rs. 60,000 at (15, 10)
Difference = Rs. 10,000

Question for GATE Past Year Questions: Linear Programming

Try yourself:After introducing slack variables s and t, the initial basic feasible solution is represented by the table below (basic variables are s = 6 and t = 6, and the objective function value is 0).

After some simplex iterations, the following table is obtained

From this, one can conclude that

[2008]

• A.

  the LP has a unique optimal solution
• B.

  the LP has an optimal solution that is not unique
• C.

  the LP is infeasible
• D.

  the LP is unbounded

Explanation

z = 4x + 6y
3x + 2y ≤ 6
2x + 3y ≤ 6
x, y > 0

Feasible region (O–A–B–C–0) Since, Slope of objective function is equal to the slope of constraint Hence LPP has multiple optimal solution
At B (6/5, 6/5)
Z = 12
At C (0,2)
Z = 12

Report a problem

Cancel Report

View Solution