GATE Production and Industrial Engineering (PI): Operations Research and Operations Management (linear programming, transportation, queuing, forecasting, EOQ and inventory, scheduling, CPM and PERT, break-even and NPV), previous-year questions solved
Every operations research and operations management question from the GATE Production and Industrial Engineering papers of 2024, 2025 and 2026, solved: linear programming and the simplex table, transportation and shortest-path problems, Markovian queues, forecasting and aggregate planning, EOQ and quantity discounts, job sequencing, CPM and PERT networks, and break-even, depreciation and NPV. Each answer matches the official key and was recomputed by code with the numbers printed in the paper, by a second method where one exists.
Questions from official GATE PI papers (IISc Bengaluru 2024, IIT Roorkee 2025, IIT Guwahati 2026); solutions by Skill-Lync. · Updated 19 Nov 2026 · 7 of 26 questions on this page
Which of proportionality, additivity, integrality and certainty is NOT an assumption of a linear programme?
- (A)Proportionality
- (B)Additivity
- (C)Integrality
- (D)Certainty
Answer: (C) Official key: C
- A linear programme rests on four assumptions. Proportionality: the contribution of a variable to the objective and to each constraint is a constant times its level, so doubling an activity doubles its effect. Additivity: the total effect of several activities is the sum of their separate effects, with no interaction terms. Divisibility: variables may take any non-negative real value, including fractions. Certainty: every coefficient and right-hand side is a known, fixed number.
- Integrality is the opposite of divisibility. Forcing variables to be whole numbers turns the problem into an integer programme, which needs branch and bound or cutting planes. So (C) is not an assumption of linear programming, and it is the answer.
Check: the simplex method happily returns fractions. For example, maximise subject to , , has the optimum at a fractional vertex. Proportionality and additivity held in 200 random tests of a linear row, and changing the right-hand side from 3 to 4 changed the optimum, which is why the numbers must be certain.
Planners in refineries, steel plants and food factories build blend and product-mix linear programmes on exactly these assumptions, and check them before trusting the answer. When a plant must run whole batches, trucks or shifts, the same model is reformulated as an integer programme, which is much slower to solve.
Maximise 6x1 + 5x2 with three resource limits, optimum (9, 4): which resources have non-zero shadow price?
Maximize
Subject to
(R1)
(R2)
(R3)
The optimal solution of the problem is: and .
For which one of the following options, the shadow price of the resource(s) will have non-zero value(s)?
- (A)R1, R2 and R3
- (B)R1 and R2
- (C)R2 and R3
- (D)R1 only
Answer: (C) Official key: C
- The shadow price of a resource is the gain in per extra unit of that resource. By complementary slackness, a resource that is not fully used at the optimum has shadow price zero, and a resource that is fully used (a binding constraint) can have a non-zero price.
- At : R1 uses , so there is a slack of 2 units and the shadow price of R1 is 0. R2 uses , binding. R3 uses , binding.
- Prices of the two binding resources from the dual: and (both variables are positive, so both dual constraints are tight). Subtracting, and . Both are non-zero.
- Check of optimality: dual objective equals primal . So the non-zero shadow prices are those of R2 and R3: option (C).
Check: we enumerated every vertex of the feasible region with exact fractions and confirmed the optimum with , then raised each right-hand side by 0.1 and re-solved. rose by 0, 0.1 and 0.4, i.e. shadow prices 0, 1 and 4 for R1, R2 and R3. Trap: assuming every constraint has a price because every constraint appears in the model.
In a product-mix model for a factory, the shadow price of a machine-hour or raw-material limit tells the manager how much profit an extra unit of that resource would earn, so it sets the most worth paying for overtime or an extra supply. A resource with slack, like R1 here, has a price of zero and buying more of it is wasted money.
Starting simplex table for maximise z = 6x1 + 4x2 with slacks S1 to S4: the leaving variable
Maximize
The leaving variable among the basic variables is
| Basic | Solution | ||||||
|---|---|---|---|---|---|---|---|
| 6 | 3 | 1 | 0 | 0 | 0 | 36 | |
| 2 | 1 | 0 | 1 | 0 | 0 | 40 | |
| 3 | 0 | 0 | 1 | 0 | 2 | ||
| 0 | 3 | 0 | 0 | 0 | 1 | 3 |
- (A)
- (B)
- (C)
- (D)
Answer: (A) Official key: A
- Simplex rule 1, the entering variable: in a maximisation, bring in the non-basic variable with the largest positive objective coefficient. Here , so (coefficient 6) enters, not (coefficient 4).
- Simplex rule 2, the leaving variable: take the minimum ratio test, solution value divided by the entering column entry, using only rows where that entry is strictly positive. A zero or negative entry puts no limit on how far can grow, so the row is skipped.
- Column of : has 6, giving . has 2, giving . has (skipped). has 0 (skipped).
- The minimum ratio is 6, in the row, so leaves. Option (A).
Check by pivoting: with entering in the row, and the other basic values become , , , all non-negative, so the new basic solution is feasible. Pivoting on the row instead would set and drive to , which is infeasible. Trap: choosing the smallest ratio including negative entries, or letting enter (then the ratios are , , and , and would leave, option C). We ran the ratio test and the pivot with exact fractions for every candidate row: only the pivot stays feasible.
The simplex method is what sits under production-mix and blending planners: each pivot adds one product to the plan and removes the resource that runs out first. Reading the minimum ratio tells a planner which machine, material or labour limit becomes the binding one as output of a new product grows.
Vogel's method: total cost of the initial transportation solution for 3 plants and 3 centres
| D1 | D2 | D3 | Supply | |
|---|---|---|---|---|
| P1 | 2 | 3 | 11 | 6 |
| P2 | 1 | 0 | 6 | 1 |
| P3 | 5 | 8 | 15 | 9 |
| Demand | 7 | 5 | 4 |
Answer: 97 (hundreds of INR), that is INR 9,700 Official key: 95 to 99
- Vogel's approximation method: for every row and column, the penalty is the gap between its two cheapest costs. Allocate as much as possible to the cheapest cell of the line with the largest penalty, cross off the exhausted line, and repeat. Supply (16) equals demand (16), so no dummy is needed.
- Round 1 penalties. Rows: P1 , P2 , P3 . Columns: D1 , D2 , D3 . The largest is 5 (column D3); its cheapest cell is P2-D3 (cost 6). Allocate . Plant P2 is used up.
- Round 2 (P2 removed). Rows: P1 , P3 . Columns: D1 , D2 , D3 . The largest is 5 (column D2); the cheapest cell is P1-D2 (cost 3). Allocate . Column D2 is satisfied; P1 has 1 left.
- Round 3 (D2 removed). Rows: P1 , P3 . Columns: D1 , D3 . The largest is 10 (row P3); the cheapest cell is P3-D1 (cost 5). Allocate . Column D1 is satisfied; P3 has 2 left.
- Only column D3 remains, needing 3: P1-D3 takes 1 (cost 11) and P3-D3 takes 2 (cost 15).
- Total cost 97 hundred INR, that is INR 9,700.
Check: we coded the method with the penalty rule above and no penalty ties arose, giving the allocation (P1-D2: 5, P1-D3: 1, P2-D3: 1, P3-D1: 7, P3-D3: 2) at cost 97. Enumerating every integer allocation, the true minimum cost is also 97, so here Vogel's start is already optimal. Trap: the north-west corner rule gives a dearer start (7 × 2 starts at P1-D1), and stopping a round too early or mixing the supply and demand totals changes the answer.
Vogel's method is the quick starting solution for distribution problems such as moving product from plants to depots, and it usually lands at or very near the optimum, so the later improvement steps are short. Logistics planners use the same logic when allocating supply from several sources to several demand points at the lowest freight cost.
Linear programme: choose all constraints that give the shaded feasible region in the figure
Note: Figure not to scale
- (A)
- (B)
- (C)
- (D)
Answer: (B) Official key: B
- Method: write the equation of each boundary line from two points on it, then test one point inside the shaded region to find which side the inequality points to.
- Top edge: the horizontal line through with the region below it, so . This rules out (A), which says , and (C), which uses .
- Right edge: the line through and has slope 1 and equation . The shaded region lies to the left and above it. Test : , so the constraint is .
- Lower left edge: the line through and has intercepts 2 and 1, so , that is . The region lies above it. Test : , so the constraint is . Option (A) has , which is a different line, and (D) has , which would cut the region down to a sliver near the origin.
- With and (the left and bottom of the first quadrant) the constraints are , , . Option (B).
Check: the corners of option (B) are , , and , found by solving every pair of boundary lines exactly (in fractions) and keeping only the feasible intersections. These are the four corners of the figure. We also compared each option with the drawn region on a grid of 525 test points spaced 0.25 apart: only (B) matches the figure at every point.
Turning a sketch of a feasible region into constraints is the reverse of formulating a production plan: each boundary line is a limit such as machine hours, material supply or a minimum order. Planners check a formulation this way, by plotting it and asking whether the corners are the plans they expect.
Weighted graph: shortest distance d from A to E, number p of paths of that length, value of d/p
The value of is ______.
- (A)5
- (B)3
- (C)2
- (D)8
Answer: (C) Official key: C
- Method: Dijkstra's algorithm gives the shortest distance by settling the nearest vertex each time. Start with A at 0. Settle C at 1 (edge A to C). Then B is 2 either directly or as through C. Next F is . E is reached from B at or from F at , and D is . So distance units.
- Now count every route of length exactly 6 that does not revisit a vertex. A to B to E: . A to C to B to E: . A to C to F to E: .
- Other simple routes are longer: A to B to D to E is , A to C to B to D to E is , and A to B to C to F to E is . So .
- 2. Option (C).
Trap: stopping at the first shortest path found (, giving , which is not even an option), or counting the route A to B to E but missing the two routes that pass through C. We ran Dijkstra and a depth-first enumeration of all 6 simple paths from A to E: the minimum is 6 and exactly 3 paths (A to B to E, A to C to B to E, A to C to F to E) reach it.
Shortest-path calculations choose delivery routes, plant-layout material-handling paths and network routing. Several routes tying for the shortest distance is common in real road networks, and planners then pick between them on road quality, tolls or congestion.
Oil allocation from two plants to two markets: optimal objective value of the intern's LP formulation
| Market 1 () | Market 2 () | Capacity in litres | |
|---|---|---|---|
| Plant 1 () | |||
| Plant 2 () | |||
| Demand in litres |
The company hired an intern to formulate an optimization model to decide on the quantity () to be allocated from plant to market and the formulation is given below:
Minimize
Subject to
The optimal value of the objective function of the linear programming problem formulated by the intern is ______ (in integer).
Answer: 0 Official key: 0 to 0
- Read the model exactly as written, not as the story intends. The objective is a minimisation of a cost with all . The constraints say the litres leaving a plant are at most its capacity, and the litres arriving at a market are at most its demand. Both are upper limits.
- Nothing in the constraints forces any oil to be sent. Setting every satisfies all of them (, , ), and it gives .
- Because every cost is positive, for any feasible plan, so cannot be beaten. The optimal value is 0.
- The error is in the intern's formulation: to meet all the demands, the market constraints must be equalities, .
Trap: solving the transportation problem the story describes. With the demands forced to be met (300 and 400 litres, total 700, against capacity 1100 litres) the cheapest plan sends all 600 litres of plant 2 and 100 litres from plant 1 to market 2 (the extra 100 litres cost 100 INR per litre more than plant 2), a cost of INR. That is not what the written model asks. We enumerated all basic solutions of both versions in exact fractions: the written model gives 0, and the forced-demand version gives 127000.
A model that lets the solver choose to ship nothing is a common slip in supply-chain optimisation: cost-minimising models need equality or lower-bound constraints on demand, or a penalty for unmet demand. Planners test a new formulation on a tiny case first, as this one would have shown a zero-cost plan at once.