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

GATE 2024 · PI · Q.23MCQ · 1 markLinear programming, transportation and network models

Which of proportionality, additivity, integrality and certainty is NOT an assumption of a linear programme?

Which of the following is NOT an assumption of a linear programming problem?
  1. (A)Proportionality
  2. (B)Additivity
  3. (C)Integrality
  4. (D)Certainty

Answer: (C) Official key: C

  1. 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.
  2. 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.

Where this shows up in industry

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.

GATE 2024 · PI · Q.42MCQ · 2 marksLinear programming, transportation and network models

Maximise 6x1 + 5x2 with three resource limits, optimum (9, 4): which resources have non-zero shadow price?

Consider the following linear programming problem with two decision variables and . There are three constraints involving resources R1, R2 and R3 as indicated.

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)?

  1. (A)R1, R2 and R3
  2. (B)R1 and R2
  3. (C)R2 and R3
  4. (D)R1 only

Answer: (C) Official key: C

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Where this shows up in industry

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.

GATE 2025 · PI · Q.27MCQ · 1 markLinear programming, transportation and network models

Starting simplex table for maximise z = 6x1 + 4x2 with slacks S1 to S4: the leaving variable

The starting simplex table of a linear programming problem is given below, where , , and are the slack variables. The objective of the problem is

Maximize

The leaving variable among the basic variables is

BasicSolution
63100036
21010040
300102
0300013
  1. (A)
  2. (B)
  3. (C)
  4. (D)

Answer: (A) Official key: A

  1. 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).
  2. 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.
  3. Column of : has 6, giving . has 2, giving . has (skipped). has 0 (skipped).
  4. 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.

Where this shows up in industry

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.

GATE 2025 · PI · Q.59NAT · 2 marksLinear programming, transportation and network models

Vogel's method: total cost of the initial transportation solution for 3 plants and 3 centres

Three plants P1, P2 and P3 produce 6, 1 and 9 thousand liters of fruit juice, respectively. The produced fruit juice is transported to three distribution centers D1, D2 and D3 with requirement of 7, 5 and 4 thousand liters of juice, respectively. The transportation cost (in hundreds of Rupees) from each plant to each distribution center is given in the table. The total transportation cost (in hundreds of Rupees) in initial basic feasible solution using Vogel’s approximation method is ________. (Answer in integer)
D1D2D3Supply
P123116
P21061
P358159
Demand754

Answer: 97 (hundreds of INR), that is INR 9,700 Official key: 95 to 99

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Only column D3 remains, needing 3: P1-D3 takes 1 (cost 11) and P3-D3 takes 2 (cost 15).
  6. 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.

Where this shows up in industry

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.

GATE 2026 · PI · Q.14MCQ · 1 markLinear programming, transportation and network models

Linear programme: choose all constraints that give the shaded feasible region in the figure

Which ONE of the following options represents correctly ALL the constraints resulting in the feasible region for the given linear programming problem as shown in the figure?
Note: Figure not to scale
Graph in the x1, x2 plane (axes marked 0 to 4, figure not to scale). The shaded feasible region has corners at (0,2), (1,0), (4,3) and (0,3). Its upper edge is the horizontal line x2 = 3, its lower right edge is the line through (1,0) and (4,3), and its lower left edge is the line through (0,2) and (1,0)123412340x2x1(4,3)feasible region
  1. (A)
  2. (B)
  3. (C)
  4. (D)

Answer: (B) Official key: B

  1. 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.
  2. Top edge: the horizontal line through with the region below it, so . This rules out (A), which says , and (C), which uses .
  3. 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 .
  4. 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.
  5. 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.

Where this shows up in industry

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.

GATE 2026 · PI · Q.22MCQ · 1 markLinear programming, transportation and network models

Weighted graph: shortest distance d from A to E, number p of paths of that length, value of d/p

In the given weighted graph, the weights represent distance between the corresponding vertices. The shortest distance between vertex A and vertex E is . The number of paths with distance is .
The value of is ______.
Weighted graph with six vertices A to F. Edge distances: A to B 2, A to C 1, B to C 1, B to D 5, B to E 4, D to E 3, C to F 2, E to F 321154323ABCDEF
  1. (A)5
  2. (B)3
  3. (C)2
  4. (D)8

Answer: (C) Official key: C

  1. 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.
  2. 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: .
  3. 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 .
  4. 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.

Where this shows up in industry

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.

GATE 2026 · PI · Q.58NAT · 2 marksLinear programming, transportation and network models

Oil allocation from two plants to two markets: optimal objective value of the intern's LP formulation

A company must allocate oil produced from their two plants to meet all the demands of two markets. The cost per litre of allocation from plant to market is denoted by . The market demand , plant production capacity and values are given in the table.
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

  1. 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.
  2. Nothing in the constraints forces any oil to be sent. Setting every satisfies all of them (, , ), and it gives .
  3. Because every cost is positive, for any feasible plan, so cannot be beaten. The optimal value is 0.
  4. 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.

Where this shows up in industry

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.

From GATE prep to a production, planning or manufacturing career

Talk to a counsellor.

Talk to a career counsellor

Free 20-minute call. We'll map the right course to where you want to work.

By submitting you agree to our Terms and Privacy Policy.

Talk to a career counsellor

Talk to a career counsellor

Free 20-minute call. We'll map the right course to where you want to work.

By submitting you agree to our Terms and Privacy Policy.