GATE Mathematics Linear Programming Syllabus

Linear Programming syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Linear Programming in GATE Mathematics, not a summary of it.

1. 1

   Linear programming models

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

2. 2

   Convex sets

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

3. 3

   Extreme points

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

4. 4

   Basic feasible solution

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

5. 5

   Graphical method

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

6. 6

   Simplex method

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

7. 7

   Two phase methods

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

8. 8

   Revised simplex method

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

9. 9

   Infeasible and unbounded linear programming models

   overview

   Examined as a single unit within Linear Programming — no further topic split in the official outline.

10. 10

    Alternate optima

    overview

    Examined as a single unit within Linear Programming — no further topic split in the official outline.

11. 11

    Duality theory

    overview

    Examined as a single unit within Linear Programming — no further topic split in the official outline.

12. 12

    Weak duality and strong duality

    overview

    Examined as a single unit within Linear Programming — no further topic split in the official outline.

13. 13

    Balanced and unbalanced transportation problems

    overview

    Examined as a single unit within Linear Programming — no further topic split in the official outline.

14. 14

    Initial basic feasible solution of balanced transportation problems

    3 topics

    • Least cost method
    • North-west corner rule
    • Vogel’s approximation method
15. 15

    Optimal solution

    overview

    Examined as a single unit within Linear Programming — no further topic split in the official outline.

16. 16

    Modified distribution method

    overview

    Examined as a single unit within Linear Programming — no further topic split in the official outline.

17. 17

    Solving assignment problems

    1 topic

    • Hungarian method

Linear Programming flashcards for GATE Mathematics

22 of 51 cards from the Linear Programming deck — real questions with worked answers.

1. What is a transportation problem in linear programming?

   A special LP problem of distributing a homogeneous commodity from several sources (origins/supply points) to several destinations (demand points) at minimum total transportation cost, subject to supply and demand constraints.

2. State the standard mathematical formulation of a transportation problem.

   Minimize $Z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}\,x_{ij}$ subject to $\sum_{j=1}^{n} x_{ij} = a_i$ (supply), $\sum_{i=1}^{m} x_{ij} = b_j$ (demand), and $x_{ij} \geq 0$, where $c_{ij}$ is the unit cost and $x_{ij}$ the amount shipped from source $i$ to destination $j$.

3. What condition makes a transportation problem 'balanced'?

   Total supply equals total demand: $\sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j$. Only then does a feasible solution exist for the equality-constrained form.

4. How do you convert an unbalanced transportation problem into a balanced one?

   Introduce a dummy source (if demand exceeds supply) or a dummy destination (if supply exceeds demand) with the required slack quantity, and assign zero transportation costs to all its cells.

5. For an $m \times n$ balanced transportation problem, how many basic (allocated) cells must a non-degenerate basic feasible solution have?

   Exactly $m + n - 1$ basic cells (allocations).

6. What is degeneracy in a transportation problem?

   Degeneracy occurs when the number of occupied (basic) cells is fewer than $m + n - 1$. It is resolved by allocating an infinitesimal quantity $\epsilon$ (epsilon) to an independent empty cell to restore the required count.

7. Name the three classical methods used to find an Initial Basic Feasible Solution (IBFS) of a transportation problem.

   North-West Corner Rule, Least Cost (Matrix Minima) Method, and Vogel's Approximation Method (VAM).

8. Describe the North-West Corner Rule procedure.

   Start at the top-left (north-west) cell. Allocate the maximum possible $x_{ij} = \min(a_i, b_j)$. Cross out the exhausted row or column, adjust the remaining supply/demand, and move to the next north-west cell (right if a column remains, down if a row remains). Repeat until all supply and demand are met.

9. On what basis does the North-West Corner Rule make allocations?

   Purely on cell position (top-left corner), completely ignoring the transportation costs $c_{ij}$.

10. What is the main advantage and main disadvantage of the North-West Corner Rule?

    Advantage: it is the simplest and fastest method to apply. Disadvantage: since it ignores costs, the resulting initial solution is usually far from optimal, requiring more optimization iterations.

11. Describe the Least Cost (Matrix Minima) Method procedure.

    Identify the cell with the smallest unit cost $c_{ij}$ in the whole matrix. Allocate $\min(a_i, b_j)$ there, cross out the satisfied row/column, and repeat by selecting the next least-cost cell among remaining cells until supply and demand are exhausted.

12. In the Least Cost Method, how is a tie between two cells having the same minimum cost broken?

    Choose the cell that allows the largest possible allocation (i.e., where $\min(a_i, b_j)$ is greatest); if still tied, the choice is arbitrary.

13. How does the Least Cost Method's initial solution generally compare to the North-West Corner Rule's?

    The Least Cost Method usually gives a lower initial cost (closer to optimal) than the North-West Corner Rule because it accounts for the unit costs while allocating.

14. What does the abbreviation VAM stand for, and what is its purpose?

    VAM stands for Vogel's Approximation Method, used to obtain an Initial Basic Feasible Solution for a transportation problem that is usually very close to (or equal to) the optimum.

15. In Vogel's Approximation Method, how is the 'penalty' for each row and column computed?

    The penalty equals the difference between the two smallest unit costs in that row (or column): $\text{penalty} = c_{\text{2nd smallest}} - c_{\text{smallest}}$. It represents the extra cost incurred if the cheapest route is not used.

16. Outline the full step-by-step procedure of Vogel's Approximation Method.

    1) Compute each row and column penalty (difference of the two least costs). 2) Select the row/column with the largest penalty. 3) In that line, allocate $\min(a_i, b_j)$ to its lowest-cost cell. 4) Cross out the exhausted row/column and recompute penalties. 5) Repeat until all allocations are complete.

17. Why is the penalty given priority in Vogel's Approximation Method?

    A high penalty means that avoiding the cheapest cell in that row/column would be very costly, so allocating there first minimizes the risk of being forced into an expensive route later, yielding a near-optimal initial solution.

18. Rank the three IBFS methods by typical quality of the initial solution (closeness to optimum).

    Vogel's Approximation Method (best) > Least Cost Method (intermediate) > North-West Corner Rule (worst). VAM trades extra computation for a much better starting solution.

19. Which IBFS method requires the most computational effort per iteration, and why?

    Vogel's Approximation Method, because at every step it must recompute the two-smallest-cost penalties for all remaining rows and columns before allocating.

20. After obtaining an IBFS, which method is used to test and improve it toward the optimal transportation solution?

    The optimality is tested and improved using the MODI (Modified Distribution) method, also called the $u$-$v$ method, or alternatively the Stepping Stone method.

21. In the MODI method, how are the dual variables $u_i$ and $v_j$ determined?

    For every basic (occupied) cell, set $u_i + v_j = c_{ij}$. Assign one variable (usually $u_1 = 0$) and solve the system for the rest.

22. In the MODI method, what is the optimality criterion for empty (non-basic) cells?

    Compute $d_{ij} = c_{ij} - (u_i + v_j)$ for each empty cell. The current solution is optimal if all $d_{ij} \geq 0$. A negative value indicates improvement is possible by bringing that cell into the basis.

See more Linear Programming flashcards →

Planning Linear Programming for GATE Mathematics

Linear Programming (GATE Mathematics) FAQ