Which statements are true?

the feasible region of every linear programme is convex

if a linear programme in standard form has an optimal solution, some extreme point of its feasible region is optimal

every basic feasible solution is an extreme point of the feasible region

the feasible region of every linear programme is convex

if a linear programme in standard form has an optimal solution, some extreme point of its feasible region is optimal

the set {(x, y) : x² + y² = 1} is convex

every basic feasible solution is an extreme point of the feasible region

An optimal simplex tableau has a non-basic variable whose reduced cost is zero. This indicates

alternate optimal solutions (if the pivot is non-degenerate)

that the tableau is not optimal

Which statements about the two-phase and Big-M methods are true?

Phase I minimises the sum of the artificial variables

if the optimal value of Phase I is positive, the original problem is infeasible

the Big-M and two-phase methods are two ways of handling artificial variables

Phase I minimises the sum of the artificial variables

if the optimal value of Phase I is positive, the original problem is infeasible

Phase I is needed only when the problem is unbounded

the Big-M and two-phase methods are two ways of handling artificial variables

For a primal max cᵀx, Ax ≤ b, x ≥ 0 and its dual min bᵀy, Aᵀy ≥ c, y ≥ 0, which statements are true?

cᵀx ≤ bᵀy for every primal-feasible x and dual-feasible y

if the primal is unbounded, the dual is infeasible

at optimality, a primal constraint that is not tight has dual value zero

cᵀx ≤ bᵀy for every primal-feasible x and dual-feasible y

if the primal is unbounded, the dual is infeasible

if the primal is infeasible, the dual must be unbounded

at optimality, a primal constraint that is not tight has dual value zero

The dual of min 3x₁ + 2x₂ subject to x₁ + x₂ ≥ 4, x₁ + 3x₂ ≥ 6, x₁, x₂ ≥ 0 is

max 4y₁ + 6y₂ subject to y₁ + y₂ ≤ 3, y₁ + 3y₂ ≤ 2, y₁, y₂ ≥ 0

max 3y₁ + 2y₂ subject to y₁ + y₂ ≤ 4, y₁ + 3y₂ ≤ 6, y₁, y₂ ≥ 0

min 4y₁ + 6y₂ subject to y₁ + y₂ ≥ 3, y₁ + 3y₂ ≥ 2, y₁, y₂ ≥ 0

max 4y₁ + 6y₂ subject to y₁ + 3y₂ ≤ 3, y₁ + y₂ ≤ 2, y₁, y₂ ≥ 0

Which statements about transportation problems are true?

a balanced transportation problem always has a feasible solution

an unbalanced problem is balanced by adding a dummy source or destination with zero unit costs

for minimisation, a BFS is optimal when cᵢⱼ − uᵢ − vⱼ ≥ 0 for every non-basic cell

a balanced transportation problem always has a feasible solution

an unbalanced problem is balanced by adding a dummy source or destination with zero unit costs

Vogel’s approximation method always gives an optimal solution

for minimisation, a BFS is optimal when cᵢⱼ − uᵢ − vⱼ ≥ 0 for every non-basic cell

Linear Programming: Simplex, Duality, Transportation and Assignment

Linear Programming is Section 11 of the GATE Mathematics (MA) paper, the last, and the most algorithmic. It begins with geometry — the feasible region of a linear programme is a convex polyhedral set, and if an optimum exists it is attained at an extreme point, which is exactly a basic feasible solution — and the simplex method is that fact turned into an algorithm that walks from one extreme point to a better neighbour. The chapter follows the syllabus: models, convex sets and extreme points; basic feasible solutions and the graphical method; the simplex, two-phase and revised simplex methods with the signs of infeasible and unbounded problems and of alternate optima; duality with the weak and strong duality theorems and complementary slackness; balanced and unbalanced transportation problems with the north-west corner, least cost and Vogel initial solutions and the modified distribution (MODI) test; and the assignment problem with the Hungarian method. Every numerical answer here was checked against a brute-force search.

1. Models, convex sets and extreme points

A linear programme optimises a linear objective cᵀx over a set defined by linear constraints; every LP can be written in standard form max cᵀx subject to Ax = b, x ≥ 0 by adding slack (≤) or surplus (≥) variables and splitting free variables. A set S is convex if it contains every segment between its points; intersections of half-spaces are convex, so every feasible region is convex (a circle x² + y² = 1 is not). An extreme point of S is one that is not a strict convex combination of two other points of S.

Fundamental theorem. If the feasible region of an LP in standard form is non-empty it has an extreme point, and if the LP has an optimal solution then some extreme point is optimal. The extreme points are exactly the basic feasible solutions (BFS): choose m linearly independent columns of the m × n matrix A (a basis B), set the other n − m variables to 0, solve Bx_B = b, and require x_B ≥ 0. There are at most C(n, m) basic solutions; a BFS with some basic variable equal to 0 is degenerate.

Graphical method. max z = 3x + 5y subject to x ≤ 4, 2y ≤ 12, 3x + 2y ≤ 18, x, y ≥ 0: the vertices are (0, 0), (4, 0), (4, 3), (2, 6), (0, 6), with z = 0, 12, 27, 36, 30, so the optimum is z = 36 at (2, 6). Sliding the objective line 3x + 5y = k outward reaches (2, 6) last.

2. The simplex, two-phase and revised simplex methods

For max cᵀx, Ax = b, x ≥ 0 with a BFS and basis B, the reduced cost of a non-basic xⱼ is c̄ⱼ = cⱼ − c_BᵀB⁻¹aⱼ. If every c̄ⱼ ≤ 0 the BFS is optimal. Otherwise bring in a variable with c̄ⱼ > 0 and use the minimum ratio test min{(B⁻¹b)ᵢ/(B⁻¹aⱼ)ᵢ : (B⁻¹aⱼ)ᵢ > 0} to choose the leaving variable; the objective does not decrease, and increases strictly unless the step is degenerate.

Reading the final tableau
Signal	Conclusion
an entering column with no positive entry	the LP is unbounded: the variable can grow without limit
at optimality, a non-basic variable with reduced cost 0	alternate optima: pivoting it in gives another optimal BFS, and the segment between is optimal
Phase I ends with a positive sum of artificial variables	the LP is infeasible
a basic variable equal to 0	degeneracy; cycling is possible in principle and prevented by Bland’s rule

Two-phase method. When no obvious starting BFS exists (≥ or = constraints), add artificial variables; Phase I minimises their sum. A minimum of 0 gives a BFS of the original problem, from which Phase II optimises the true objective; a positive minimum proves infeasibility. The Big-M method does the same in one phase by penalising artificials with a large M in the objective.
Revised simplex. Carry only B⁻¹ (or a factorisation of B): compute the simplex multipliers πᵀ = c_BᵀB⁻¹, price out c̄ⱼ = cⱼ − πᵀaⱼ, generate only the entering column B⁻¹aⱼ, and update B⁻¹ by one elementary matrix. It does the same pivots with far less work when n ≫ m.

3. Duality

The dual of the primal max cᵀx, Ax ≤ b, x ≥ 0 is min bᵀy, Aᵀy ≥ c, y ≥ 0: one dual variable per primal constraint, the right-hand sides and costs exchange roles, and the dual of the dual is the primal. For a min primal with ≥ constraints the dual is a max with ≤ constraints; an equality constraint gives a free dual variable.

Weak duality: for any primal-feasible x and dual-feasible y, cᵀx ≤ bᵀy. So a primal that is unbounded has an infeasible dual, and equal objective values certify that both are optimal.
Strong duality: if either problem has a finite optimum, so does the other and the optimal values are equal. Both can be infeasible (e.g. max x₁ with x₁ − x₂ ≤ −1, −x₁ + x₂ ≤ −1).
Complementary slackness: feasible x, y are optimal iff yᵢ(b − Ax)ᵢ = 0 for every i and xⱼ(Aᵀy − c)ⱼ = 0 for every j: a slack constraint has a zero dual price, and a positive variable has a tight dual constraint.

🧠 Dual prices from the optimal vertex

max 2x + 3y with x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0 is optimal at (3, 1) with z = 9. Both variables are positive, so both dual constraints are tight: u + v = 2 and u + 3v = 3, giving v = 1/2, u = 3/2. Check strong duality: 4u + 6v = 6 + 3 = 9. The dual value u = 1.5 is the rate at which z grows per unit increase of the first right-hand side (the shadow price).

4. Transportation problems

Ship from m sources with supplies aᵢ to n destinations with demands bⱼ at unit costs cᵢⱼ, minimising Σcᵢⱼxᵢⱼ. The problem is balanced if Σaᵢ = Σbⱼ, and then it is always feasible; an unbalanced problem is balanced by a dummy source or destination with zero costs. One of the m + n equality constraints is redundant, so a BFS has m + n − 1 basic cells; fewer positive allocations mean a degenerate BFS, handled by placing an ε allocation.

A worked problem: supplies 30, 40; demands 20, 30, 20; costs row 1 (2, 3, 1), row 2 (5, 4, 8)
Method	Allocation	Cost
north-west corner	x₁₁ = 20, x₁₂ = 10, x₂₂ = 20, x₂₃ = 20	40 + 30 + 80 + 160 = 310
least cost	x₁₃ = 20, x₁₁ = 10, x₂₂ = 30, x₂₁ = 10	20 + 20 + 120 + 50 = 210
MODI check of the least-cost BFS	u₁ = 0, v₁ = 2, v₃ = 1, u₂ = 3, v₂ = 1; Δ₁₂ = 3 − 0 − 1 = 2, Δ₂₃ = 8 − 3 − 1 = 4	all Δ ≥ 0: optimal, 210

Vogel’s approximation method computes for each row and column the difference between its two smallest costs (the penalty of not using the cheapest cell), allocates as much as possible to the cheapest cell of the line with the largest penalty, and repeats; it usually starts closer to the optimum than the other two but is not guaranteed optimal. MODI (u–v) method: for the basic cells solve uᵢ + vⱼ = cᵢⱼ with one uᵢ = 0; the BFS is optimal (for minimisation) iff Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ ≥ 0 for every non-basic cell; otherwise enter the most negative Δ around a closed loop.

5. The assignment problem and the Hungarian method

Assign n workers to n jobs, one each, minimising total cost: a transportation problem with all supplies and demands 1, hence highly degenerate (n positive allocations against 2n − 1 basic cells). There are n! feasible assignments. The Hungarian method: subtract each row minimum, then each column minimum; cover all zeros with the fewest lines; if n lines are needed an optimal assignment exists among the zeros; otherwise subtract the smallest uncovered entry from all uncovered entries, add it at intersections, and repeat. Subtracting a constant from a row or column changes every assignment’s cost by the same amount, which is why the method is correct. A maximisation problem is converted by subtracting every entry from the largest.

Example. Costs [[10, 3, 8], [7, 5, 4], [6, 9, 2]]. Row reduction gives [[7, 0, 5], [3, 1, 0], [4, 7, 0]]; column reduction (column minima 3, 0, 0) gives [[4, 0, 5], [0, 1, 0], [1, 7, 0]], whose zeros (1, 2), (2, 1), (3, 3) form an assignment. Its cost is 3 + 7 + 2 = 12, and the total reduction 3 + 4 + 2 + 3 = 12 confirms optimality.

Key takeaways

Feasible regions are convex; an optimum, if it exists, is attained at an extreme point, and extreme points are the basic feasible solutions (at most C(n, m) of them).
Simplex: optimal when no reduced cost can improve; unbounded when the entering column has no positive entry; alternate optima when a non-basic reduced cost is 0; Phase I > 0 means infeasible.
Weak duality cᵀx ≤ bᵀy; strong duality gives equal optima; complementary slackness links slack constraints to zero dual prices.
Balanced transportation has m + n − 1 basic cells; NW corner, least cost and Vogel give starting solutions and MODI tests Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ ≥ 0.
Assignment is degenerate transportation with n! feasible solutions; the Hungarian method reduces rows and columns and covers zeros with n lines.

Practice questions (16)

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.

The maximum value of z = 3x + 5y subject to x ≤ 4, 2y ≤ 12, 3x + 2y ≤ 18, x ≥ 0, y ≥ 0 is ____.
Numerical answer — type the value.
Show answer
Answer: 36
The vertices are (0, 0), (4, 0), (4, 3), (2, 6) and (0, 6), where z = 0, 12, 27, 36, 30. The optimum 36 is at (2, 6), where y = 6 and 3x + 2y = 18 are tight. (4, 3) is the trap: it looks like a corner of all three constraints but gives only 27.
A system Ax = b has 2 equations in 4 unknowns with A of rank 2. The maximum possible number of basic solutions is ____.
Numerical answer — type the value.
Show answer
Answer: 6
A basic solution chooses 2 of the 4 columns as the basis and sets the other 2 variables to 0; there are C(4, 2) = 6 choices, each giving at most one basic solution (none if the two columns are dependent). Not all need be feasible.
Which statements are true?
1. the feasible region of every linear programme is convex
2. if a linear programme in standard form has an optimal solution, some extreme point of its feasible region is optimal
3. the set {(x, y) : x² + y² = 1} is convex
4. every basic feasible solution is an extreme point of the feasible region
Show answer
Answer: A — the feasible region of every linear programme is convex; B — if a linear programme in standard form has an optimal solution, some extreme point of its feasible region is optimal; D — every basic feasible solution is an extreme point of the feasible region
(1) An intersection of half-spaces and hyperplanes is convex. (2) is the fundamental theorem of LP. (4) BFS and extreme points coincide in standard form. (3) is false: (1, 0) and (−1, 0) are on the circle but their midpoint (0, 0) is not.
In a simplex iteration for a maximisation problem, the entering variable’s column has no positive entry. Then the problem
1. is unbounded
2. is infeasible
3. has alternate optima
4. is degenerate
Show answer
Answer: A — is unbounded
With no positive entry, the ratio test has no candidate: increasing the entering variable never drives a basic variable negative, so it can grow without limit while the objective, whose reduced cost is positive, grows too. Infeasibility is signalled by Phase I, alternate optima by zero reduced costs at the optimum.
An optimal simplex tableau has a non-basic variable whose reduced cost is zero. This indicates
1. alternate optimal solutions (if the pivot is non-degenerate)
2. an unbounded problem
3. an infeasible problem
4. that the tableau is not optimal
Show answer
Answer: A — alternate optimal solutions (if the pivot is non-degenerate)
Pivoting that variable in changes the objective by (reduced cost) × (step) = 0, so it reaches a different BFS with the same optimal value, and every point of the segment between them is optimal. If the ratio-test step is 0 the BFS stays the same, which is the degenerate exception.
Which statements about the two-phase and Big-M methods are true?
1. Phase I minimises the sum of the artificial variables
2. if the optimal value of Phase I is positive, the original problem is infeasible
3. Phase I is needed only when the problem is unbounded
4. the Big-M and two-phase methods are two ways of handling artificial variables
Show answer
Answer: A — Phase I minimises the sum of the artificial variables; B — if the optimal value of Phase I is positive, the original problem is infeasible; D — the Big-M and two-phase methods are two ways of handling artificial variables
(1) is the definition of Phase I. (2) A feasible x of the original problem would give Phase I value 0, so a positive minimum rules it out. (4) Big-M penalises artificials in one objective; two-phase separates the penalty into its own phase. (3) is false: Phase I is about finding a starting BFS, needed for ≥ or = constraints regardless of boundedness.
The maximum of 2x + 3y subject to x + y ≤ 4, x + 3y ≤ 6, x ≥ 0, y ≥ 0 is ____.
Numerical answer — type the value.
Show answer
Answer: 9
Vertices: (0, 0) → 0, (4, 0) → 8, (0, 2) → 6, and the intersection of x + y = 4 and x + 3y = 6, i.e. y = 1, x = 3 → 9. The maximum is 9 at (3, 1).
For the LP max 2x + 3y subject to x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0, the optimal value of the dual variable associated with the constraint x + y ≤ 4 is ____.
Numerical answer — type the value.
Show answer
Answer: 1.5
The primal optimum is (3, 1), with both x, y > 0, so by complementary slackness both dual constraints are tight: u + v = 2 and u + 3v = 3. Hence v = 1/2 and u = 3/2. Check: dual objective 4u + 6v = 6 + 3 = 9 equals the primal optimum.
For a primal max cᵀx, Ax ≤ b, x ≥ 0 and its dual min bᵀy, Aᵀy ≥ c, y ≥ 0, which statements are true?
1. cᵀx ≤ bᵀy for every primal-feasible x and dual-feasible y
2. if the primal is unbounded, the dual is infeasible
3. if the primal is infeasible, the dual must be unbounded
4. at optimality, a primal constraint that is not tight has dual value zero
Show answer
Answer: A — cᵀx ≤ bᵀy for every primal-feasible x and dual-feasible y; B — if the primal is unbounded, the dual is infeasible; D — at optimality, a primal constraint that is not tight has dual value zero
(1) cᵀx ≤ (Aᵀy)ᵀx = yᵀAx ≤ yᵀb, using x, y ≥ 0. (2) Any dual-feasible y would bound the primal. (4) is complementary slackness. (3) is false: both problems can be infeasible, e.g. max x₁ subject to x₁ − x₂ ≤ −1 and −x₁ + x₂ ≤ −1.
The dual of min 3x₁ + 2x₂ subject to x₁ + x₂ ≥ 4, x₁ + 3x₂ ≥ 6, x₁, x₂ ≥ 0 is
1. max 4y₁ + 6y₂ subject to y₁ + y₂ ≤ 3, y₁ + 3y₂ ≤ 2, y₁, y₂ ≥ 0
2. max 3y₁ + 2y₂ subject to y₁ + y₂ ≤ 4, y₁ + 3y₂ ≤ 6, y₁, y₂ ≥ 0
3. min 4y₁ + 6y₂ subject to y₁ + y₂ ≥ 3, y₁ + 3y₂ ≥ 2, y₁, y₂ ≥ 0
4. max 4y₁ + 6y₂ subject to y₁ + 3y₂ ≤ 3, y₁ + y₂ ≤ 2, y₁, y₂ ≥ 0
Show answer
Answer: A — max 4y₁ + 6y₂ subject to y₁ + y₂ ≤ 3, y₁ + 3y₂ ≤ 2, y₁, y₂ ≥ 0
A min with ≥ constraints and x ≥ 0 has dual max bᵀy, Aᵀy ≤ c, y ≥ 0. Here b = (4, 6), c = (3, 2) and A = [[1, 1], [1, 3]], so Aᵀ = [[1, 1], [1, 3]] as well, giving y₁ + y₂ ≤ 3 (column of x₁) and y₁ + 3y₂ ≤ 2 (column of x₂). The last option transposes the wrong way.
The number of basic variables in a basic feasible solution of a balanced transportation problem with 3 sources and 4 destinations is ____.
Numerical answer — type the value.
Show answer
Answer: 6
There are 3 + 4 = 7 equality constraints, but their sum over sources equals their sum over destinations, so one is redundant and the rank is m + n − 1 = 6. A BFS with fewer than 6 positive allocations is degenerate.
Supplies are 30 and 40, demands 20, 30 and 20, and the unit costs are (2, 3, 1) from source 1 and (5, 4, 8) from source 2. The total cost of the north-west corner initial solution is ____.
Numerical answer — type the value.
Show answer
Answer: 310
Start at cell (1, 1): x₁₁ = min(30, 20) = 20; column 1 done, move right: x₁₂ = 10 exhausts source 1; move down: x₂₂ = 20 completes column 2; x₂₃ = 20. Cost 20·2 + 10·3 + 20·4 + 20·8 = 40 + 30 + 80 + 160 = 310. The method ignores costs, which is why it is usually poor.
For the same data (supplies 30, 40; demands 20, 30, 20; costs (2, 3, 1) and (5, 4, 8)), the minimum total transportation cost is ____.
Numerical answer — type the value.
Show answer
Answer: 210
Least cost gives x₁₃ = 20, x₁₁ = 10, x₂₂ = 30, x₂₁ = 10, cost 20 + 20 + 120 + 50 = 210. MODI: u₁ = 0 gives v₁ = 2, v₃ = 1; then u₂ = 3 and v₂ = 1. Non-basic Δ₁₂ = 3 − 0 − 1 = 2 and Δ₂₃ = 8 − 3 − 1 = 4 are non-negative, so 210 is optimal (a full search agrees).
Which statements about transportation problems are true?
1. a balanced transportation problem always has a feasible solution
2. an unbalanced problem is balanced by adding a dummy source or destination with zero unit costs
3. Vogel’s approximation method always gives an optimal solution
4. for minimisation, a BFS is optimal when cᵢⱼ − uᵢ − vⱼ ≥ 0 for every non-basic cell
Show answer
Answer: A — a balanced transportation problem always has a feasible solution; B — an unbalanced problem is balanced by adding a dummy source or destination with zero unit costs; D — for minimisation, a BFS is optimal when cᵢⱼ − uᵢ − vⱼ ≥ 0 for every non-basic cell
(1) xᵢⱼ = aᵢbⱼ/Σa is feasible. (2) The dummy absorbs the excess at no cost. (4) cᵢⱼ − uᵢ − vⱼ are the reduced costs, with (uᵢ, vⱼ) the dual variables. (3) is false: Vogel is a heuristic for a good starting BFS, and it can miss the optimum.
Three jobs are assigned to three workers, one each, with cost matrix rows (10, 3, 8), (7, 5, 4), (6, 9, 2). The minimum total cost is ____.
Numerical answer — type the value.
Show answer
Answer: 12
Row minima 3, 4, 2 give [[7, 0, 5], [3, 1, 0], [4, 7, 0]]; column minima 3, 0, 0 give [[4, 0, 5], [0, 1, 0], [1, 7, 0]]. Zeros at (1, 2), (2, 1), (3, 3) form an assignment: 3 + 7 + 2 = 12, equal to the total subtracted, so it is optimal. The other five permutations cost 13, 17, 19, 23, 24.
The number of feasible solutions of an n × n assignment problem is
1. n!
2. n²
3. 2ⁿ
4. 2n − 1
Show answer
Answer: A — n!
A feasible assignment gives each worker a distinct job, i.e. a permutation of n jobs, and there are n! permutations. 2n − 1 is the number of basic cells when the problem is viewed as a transportation problem, of which only n are positive, so every BFS is degenerate.