In a linear programming problem with a bounded feasible region, the optimal solution:

Always occurs at a corner (extreme) point of the feasible region

Always occurs strictly in the interior of the feasible region

Occurs at the centroid of the feasible region

Cannot be determined without calculus

Strong duality in linear programming states that:

The primal and dual optimal objective values are equal when both have feasible optimal solutions

The dual problem always has more variables than the primal

Only the primal problem needs to be solved

The dual is feasible only if the primal is infeasible

The dual simplex method is typically applied when a tableau is:

Dual-feasible but primal-infeasible

Primal-feasible but dual-infeasible

Both primal- and dual-infeasible

Already at the optimal solution

Rounding the optimal solution of an integer program's LP relaxation to the nearest integers:

May produce a solution that is infeasible or far from optimal

Always produces the true integer optimum

Is the definition of the branch and bound method

Is only valid for assignment problems

The assignment problem is best described as:

A special (degenerate) case of the transportation problem with all supplies and demands equal to 1

A non-linear optimisation problem

Unrelated to the transportation problem

Solvable only by simplex, never by a dedicated method

In a project network, an activity's total float is:

Latest start minus earliest start (equivalently latest finish minus earliest finish)

Earliest start minus latest start

Always zero for every activity in the network

Which of the following are true of crashing a project to reduce its duration? (More than one option may be correct.)

Only critical-path activities need to be crashed to shorten the project

The critical path can shift to a different chain of activities after a crash

Activities should be crashed in increasing order of cost per unit time saved

Only critical-path activities need to be crashed to shorten the project

The critical path can shift to a different chain of activities after a crash

Crashing is always free of additional cost

Activities should be crashed in increasing order of cost per unit time saved

Optimization — Linear Programming, Integer Programming, Transportation, Assignment and PERT-CPM

Operations research is the one large sub-topic of Unit 1 with no GATE CS equivalent at all — GATE's engineering-mathematics and discrete-mathematics chapters stop well short of it. This chapter covers the whole of it: the linear-programming model and its graphical solution for two variables, the simplex method and duality with the dual simplex method, sensitivity analysis, integer programming, the transportation and assignment models as special-structure LPs solved by their own dedicated methods, and PERT-CPM for project scheduling with critical-path calculation, resource levelling and cost trade-offs.

The LP Model and the Graphical Method

A linear programming problem maximises or minimises a linear objective function c₁x₁ + c₂x₂ + ... subject to linear constraints (equalities or inequalities) and non-negativity xᵢ ≥ 0. For two variables it is solved graphically: plot each constraint as a half-plane, intersect them to get the feasible region (a convex polygon, possibly unbounded), and note that the optimal solution always occurs at a corner (extreme) point of this region — never strictly inside it, because a linear function's value changes monotonically along any straight line, so moving from an interior point towards a boundary in the direction that improves the objective never makes it worse until a corner is reached. Evaluate the objective at every corner and pick the best.

⚠️ An unbounded feasible region does not mean an unbounded optimum

A minimisation problem can have a finite optimum even when the feasible region stretches to infinity, because the objective may still be bounded below on that region (e.g. it keeps increasing as you move away). The optimum is unbounded only when the objective can be improved without limit while staying feasible — check this explicitly rather than inferring it from the region's shape alone.

The Simplex Method, Duality and Sensitivity Analysis

Simplex method: converts inequalities to equalities with slack/surplus variables, starts at a basic feasible solution (often the origin), and moves along edges of the feasible region from corner to corner, each move improving the objective, until no adjacent corner improves it further — that is optimal. The algorithm is a systematic way of doing exactly the corner-checking the graphical method does, but in any number of dimensions.
Duality: every LP (the primal) has an associated dual LP — a maximisation primal pairs with a minimisation dual, the primal's constraint coefficients become the dual's, and the primal's objective coefficients become the dual's constraint right-hand sides and vice versa. The weak duality theorem says the dual's objective value always bounds the primal's (dual minimum ≥ primal maximum at any feasible pair), and strong duality says their optimal values are EQUAL when both problems have a feasible optimal solution.
Dual simplex method: used when a solution is dual-feasible (optimal-looking coefficients) but primal-infeasible (a negative right-hand side) — instead of restarting, it restores primal feasibility while keeping dual feasibility, which is faster than re-solving from scratch after a constraint changes (e.g. in sensitivity analysis or re-optimisation after adding a constraint).
Sensitivity analysis asks how much an objective coefficient or a constraint's right-hand side can change before the optimal basis (which variables are basic) changes — the ranging of a coefficient, and the shadow price of a constraint (how much the optimum improves per unit relaxation of that constraint, which equals the corresponding dual variable's value).

Integer Programming, Transportation and Assignment

Three special LP-family problems
Problem	What is different	Standard method
Integer programming	Some or all variables must be integers; rounding the LP-relaxation's solution is NOT guaranteed feasible or optimal.	Branch and bound (solve the LP relaxation, branch on a fractional variable) or cutting planes.
Transportation problem	Minimise shipping cost from m supply sources to n demand destinations; a balanced problem has total supply = total demand.	North-West Corner or Vogel's Approximation for an initial feasible solution, then MODI (or stepping-stone) to test and improve optimality.
Assignment problem	A special (degenerate) transportation problem: n workers to n jobs, one-to-one, minimising total cost.	Hungarian method — row and column reduction, then cover all zeros with minimum lines and adjust.

🎯 Why rounding an integer program's LP relaxation can fail badly

The LP relaxation (dropping the integrality constraint) gives an upper bound on a maximisation integer program's true optimum, but the relaxed optimum's fractional values, rounded to the nearest integer, need not even be feasible (a rounded solution can violate a constraint the fractional one satisfied exactly), and even when feasible it can be far from optimal. Branch and bound instead systematically explores integer-forcing branches while using the LP bound to prune branches that cannot beat the best integer solution found so far.

PERT-CPM: Critical Path, Resource Levelling and Cost

A project is modelled as an activity network (a directed acyclic graph): nodes are events/milestones and edges are activities with durations (CPM, deterministic) or three time estimates — optimistic, most likely, pessimistic, combined into an expected time by PERT's formula (o + 4m + p)/6. The critical path is the longest path from start to finish; its total length is the minimum possible project duration, and any delay on a critical activity delays the whole project. Every activity has an earliest start/finish (forward pass) and a latest start/finish (backward pass); its total float = latest start − earliest start (equivalently, latest finish − earliest finish) measures how much it can slip without delaying the project. A critical activity has zero total float by definition — floats and criticality are two views of the same computation.

Resource levelling shifts non-critical activities within their float to smooth resource demand over time (e.g. avoiding a workforce peak) without extending the project — it exploits slack that resource-blind scheduling ignores.
Cost consideration (crashing): an activity has a normal duration/cost and a crash (minimum) duration/cost; crashing shortens duration at extra cost per unit time saved, and the project is shortened most cheaply by crashing critical-path activities in increasing order of their cost-per-day-saved, re-checking the critical path after each crash since it can shift to a different chain of activities.

Key takeaways

An LP's optimum always occurs at a corner (extreme point) of the feasible region — evaluate the objective there, never in the interior.
Simplex moves corner to corner improving the objective; strong duality makes the primal and dual optimal values equal when both are feasible; dual simplex restores primal feasibility after a constraint change without restarting.
Rounding an integer program's LP relaxation is not guaranteed feasible or optimal — branch and bound is the sound method.
The transportation problem is solved by an initial-solution method (NW-corner or Vogel's) plus MODI for optimality; the assignment problem is its one-to-one special case, solved by the Hungarian method.
The critical path is the longest start-to-finish path and has zero total float on every activity along it; resource levelling and crashing both exploit float/cost trade-offs without (levelling) or with (crashing) extending the project.

Practice questions (9)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

In a linear programming problem with a bounded feasible region, the optimal solution:
1. Always occurs at a corner (extreme) point of the feasible region
2. Always occurs strictly in the interior of the feasible region
3. Occurs at the centroid of the feasible region
4. Cannot be determined without calculus
Show answer
Answer: A — Always occurs at a corner (extreme) point of the feasible region
A linear objective changes monotonically along any direction, so improving it from an interior point never stops until a boundary corner is reached — this is why simplex only ever needs to check corners.
Strong duality in linear programming states that:
1. The primal and dual optimal objective values are equal when both have feasible optimal solutions
2. The dual problem always has more variables than the primal
3. Only the primal problem needs to be solved
4. The dual is feasible only if the primal is infeasible
Show answer
Answer: A — The primal and dual optimal objective values are equal when both have feasible optimal solutions
Weak duality bounds one by the other at any feasible pair; strong duality tightens this to equality at the optimum, whenever an optimal feasible solution exists for both.
The dual simplex method is typically applied when a tableau is:
1. Dual-feasible but primal-infeasible
2. Primal-feasible but dual-infeasible
3. Both primal- and dual-infeasible
4. Already at the optimal solution
Show answer
Answer: A — Dual-feasible but primal-infeasible
Dual simplex starts from optimal-looking (dual-feasible) coefficients with an infeasible (negative) right-hand side and restores primal feasibility, which is exactly the situation after a constraint's right-hand side is tightened post-optimality.
Rounding the optimal solution of an integer program's LP relaxation to the nearest integers:
1. May produce a solution that is infeasible or far from optimal
2. Always produces the true integer optimum
3. Is the definition of the branch and bound method
4. Is only valid for assignment problems
Show answer
Answer: A — May produce a solution that is infeasible or far from optimal
A rounded fractional solution can violate a constraint that held exactly at the fractional point, and even when it happens to stay feasible it need not be the best integer solution — branch and bound is the method that guarantees optimality.
The assignment problem is best described as:
1. A special (degenerate) case of the transportation problem with all supplies and demands equal to 1
2. A non-linear optimisation problem
3. Unrelated to the transportation problem
4. Solvable only by simplex, never by a dedicated method
Show answer
Answer: A — A special (degenerate) case of the transportation problem with all supplies and demands equal to 1
n workers to n jobs, one-to-one, is a transportation problem where every source supplies exactly 1 and every destination demands exactly 1 — its high degeneracy is exactly why the dedicated Hungarian method is used rather than general transportation methods.
In a project network, an activity's total float is:
1. Latest start minus earliest start (equivalently latest finish minus earliest finish)
2. Earliest start minus latest start
3. Always zero for every activity in the network
4. The activity's own duration
Show answer
Answer: A — Latest start minus earliest start (equivalently latest finish minus earliest finish)
Total float measures how much an activity can slip without delaying the project; a critical activity has zero total float by definition, and non-critical activities have positive float that resource levelling can exploit.
In PERT, the expected duration of an activity with optimistic time o, most likely time m and pessimistic time p is computed as:
1. (o + 4m + p) / 6
2. (o + m + p) / 3
3. (o + p) / 2
4. m alone, ignoring o and p
Show answer
Answer: A — (o + 4m + p) / 6
PERT's weighted average gives the most-likely estimate four times the weight of either extreme, based on treating the activity duration as approximately Beta-distributed.
Which of the following are true of crashing a project to reduce its duration? (More than one option may be correct.)
1. Only critical-path activities need to be crashed to shorten the project
2. The critical path can shift to a different chain of activities after a crash
3. Crashing is always free of additional cost
4. Activities should be crashed in increasing order of cost per unit time saved
Show answer
Answer: A — Only critical-path activities need to be crashed to shorten the project; B — The critical path can shift to a different chain of activities after a crash; D — Activities should be crashed in increasing order of cost per unit time saved
Crashing a non-critical activity does not shorten the project at all, since the critical path's length is unaffected; the critical path itself can shift once a crash removes the previous bottleneck; and crashing always costs extra per unit time saved, which is why the cheapest critical activities are crashed first.
In a balanced transportation problem, if total supply is 100 units spread over sources and total demand is D units spread over destinations, then D must equal _____.
Numerical answer — type the value.
Show answer
Answer: 100
A transportation problem is 'balanced' precisely when total supply equals total demand; an unbalanced problem is first converted to a balanced one by adding a dummy source or destination with zero cost before the standard methods apply.