How to Use This Page
1. Solve each exercise problem on your own first — attempt every step before looking here. 2. Compare your method with the step-by-step solution shown. 3. If your answer differs, rework from the step where you diverged. 4. Pay special attention to the Common Mistakes section — these are the errors that cost marks in exams. 5. Use the Exam Checklist before your test to ensure you have covered every topic.
Key Concepts (Quick Recap)
Linear Programming Problem (LPP)
- Objective function: Z = c₁x₁ + c₂x₂ + ... (linear, to be maximised or minimised)
- Constraints: Linear inequalities a₁₁x₁ + a₁₂x₂ + ... ≤ or ≥ bᵢ
- Non-negativity: x₁, x₂, ... ≥ 0
- Feasible region: Common area satisfying all constraints
- Optimal solution: Occurs at a corner (extreme) point of the feasible region
- Infeasible solution: No point satisfies all constraints simultaneously
- Unbounded solution: Feasible region extends infinitely, no finite optimum
Graphical Method (Two Variables)
1. Write the LPP in standard form 2. Convert each inequality to an equation (replace ≤ with =) 3. Plot each line and identify the feasible side 4. Shade the feasible region (intersection of all half-planes) 5. Find corner points of the feasible region 6. Evaluate Z at each corner point 7. Choose the corner point giving maximum (or minimum) Z
Special Cases in LPP
- Multiple optimal solutions: When the objective function is parallel to a constraint on the feasible region boundary
- Infeasible LPP: When constraints are contradictory, feasible region is empty
- Unbounded LPP: When the feasible region is unbounded and the objective can increase without limit
Transportation Problem
- Objective: Minimise total transportation cost from sources to destinations
- Balance condition: Total supply = Total demand (if not, add dummy row/column)
- Methods for Initial Basic Feasible Solution (IBFS):
- North-West Corner Rule
- Least Cost Method (Matrix Minimum)
- Vogel's Approximation Method (VAM)
- Optimality check: MODI method (u-v method) or stepping stone method
- Degeneracy: When number of basic cells < m + n − 1
Assignment Problem
- Objective: Assign n workers to n jobs (one-to-one) to minimise total cost (or maximise profit)
- Special case of transportation: Each supply = 1, each demand = 1
- Hungarian Method: Step-by-step algorithm to find optimal assignment
- Maximisation: Convert to minimisation by subtracting all elements from the maximum element
- Unbalanced assignment: Add dummy row/column with zero costs
Key Formulas
- Number of basic variables in transportation: m + n − 1 (m = rows, n = columns)
- VAM penalty = difference between two smallest costs in a row/column
- For unbalanced transportation: add dummy with zero cost and required supply/demand
I. Choose the Best Answer (MCQs)
1. The optimal solution of an LPP occurs at: (a) Any point inside the feasible region (b) A corner point of the feasible region (c) The origin (d) Outside the feasible region
Answer(b) A corner point of the feasible region Explanation: By the fundamental theorem of linear programming, if an optimal solution exists, it occurs at a corner (extreme) point of the feasible region. If multiple optimal solutions exist, they occur along an edge connecting two corner points.
2. In a transportation problem with 3 sources and 4 destinations, the number of basic variables is: (a) 12 (b) 7 (c) 6 (d) 5
Answer(c) 6 Explanation: Number of basic variables = m + n − 1 = 3 + 4 − 1 = 6. This is required for a non-degenerate basic feasible solution.
3. The Hungarian method is used to solve: (a) Transportation problems (b) Assignment problems (c) LPP with two variables (d) Network problems
Answer(b) Assignment problems Explanation: The Hungarian method (also called the assignment algorithm) is specifically designed to solve assignment problems efficiently. It works by reducing the cost matrix to create zero entries for optimal assignment.
4. If an LPP has no feasible solution, it is called: (a) Optimal (b) Unbounded (c) Infeasible (d) Degenerate
Answer(c) Infeasible Explanation: When the constraints are contradictory and there is no point that satisfies all constraints, the problem is infeasible. The feasible region is empty.
5. In Vogel's Approximation Method (VAM), the penalty for each row is: (a) The smallest cost in the row (b) The largest cost in the row (c) The difference between the two smallest costs in the row (d) The sum of all costs in the row
Answer(c) The difference between the two smallest costs in the row Explanation: VAM computes penalties (opportunity costs) as the difference between the two smallest costs in each row and column. The row/column with the highest penalty gets allocation priority.
6. A balanced transportation problem requires: (a) Total supply > Total demand (b) Total supply < Total demand (c) Total supply = Total demand (d) Number of sources = Number of destinations
Answer(c) Total supply = Total demand Explanation: A transportation problem is balanced when total supply equals total demand. If they are not equal, a dummy source or destination with zero cost is added to balance the problem.
7. In the graphical method, the feasible region is: (a) The area outside all constraint lines (b) The common area satisfying all constraints (c) Only the x-axis (d) Only the origin
Answer(b) The common area satisfying all constraints Explanation: The feasible region is the intersection of all half-planes defined by the constraints. It is the set of all points that satisfy every constraint simultaneously.
8. For a maximisation assignment problem, the first step is to: (a) Subtract all values from zero (b) Subtract all values from the maximum value (c) Add all values (d) Find the minimum value
Answer(b) Subtract all values from the maximum value Explanation: To convert a maximisation problem to minimisation (required by Hungarian method), subtract each element from the maximum element in the matrix. This preserves the optimal assignment while converting from "maximise profit" to "minimise cost."
9. Degeneracy in a transportation problem occurs when: (a) Number of basic cells = m + n − 1 (b) Number of basic cells > m + n − 1 (c) Number of basic cells < m + n − 1 (d) All cells are occupied
Answer(c) Number of basic cells < m + n − 1 Explanation: Degeneracy occurs when the number of basic (occupied) cells is less than m + n − 1. This can happen during the initial allocation or during optimization. It is resolved by adding an epsilon (ε) allocation to an independent zero cell.
10. The North-West Corner method starts allocation from: (a) The bottom-right cell (b) The cell with the least cost (c) The top-left cell (d) The cell with the highest penalty
Answer(c) The top-left cell Explanation: The North-West Corner method starts from the top-left cell (first row, first column) and allocates as much as possible, then moves right or down. It does not consider costs, so it typically gives a non-optimal initial solution.
II. Fill in the Blanks
1. The feasible region of an LPP is the intersection of all half-planes defined by the constraints.
2. In a transportation problem with m sources and n destinations, the number of basic cells should be m + n − 1.
3. The Hungarian method for assignment problems was developed by Harold Kuhn (based on earlier work by Konig and Egervary).
4. An LPP is said to be unbounded if the feasible region is not bounded and the objective function can increase indefinitely.
5. In VAM, the penalty for a row/column is the difference between the two smallest costs in that row/column.
6. To balance an unbalanced transportation problem, we add a dummy row or column with zero transportation cost.
7. The objective function Z = 5x + 3y is a linear function.
8. In an assignment problem, each worker must be assigned to exactly one job.
III. True or False
1. Statement: The optimal solution of an LPP always occurs at the origin.
False. Correction: The optimal solution occurs at a corner point of the feasible region, which may or may not be the origin. The origin is only one possible corner point.
2. Statement: Vogel's Approximation Method generally gives a better initial solution than the North-West Corner method.
True. VAM considers costs (through penalties) and typically gives a solution closer to optimal. The North-West Corner method ignores costs entirely.
3. Statement: An assignment problem is a special case of a transportation problem.
True. An assignment problem is a transportation problem where each source has supply 1 and each destination has demand 1.
4. Statement: Degeneracy in transportation means the solution has too many basic cells.
False. Correction: Degeneracy means the number of basic cells is less than m + n − 1. Having too few (not too many) basic cells is the issue.
5. Statement: A maximisation assignment problem can be solved by the Hungarian method directly.
False. Correction: The Hungarian method is designed for minimisation. To solve a maximisation assignment problem, first convert it by subtracting each element from the maximum element, then apply the Hungarian method.
6. Statement: The feasible region of an LPP is always bounded.
False. Correction: The feasible region may be bounded (closed polygon) or unbounded (extending to infinity). An unbounded feasible region may lead to an unbounded solution where the objective can increase without limit.
7. Statement: In the North-West Corner method, the cost values in the cells are not considered during allocation.
True. The North-West Corner method only considers supply and demand values. It ignores costs during allocation, which is why it often gives a non-optimal initial solution.
IV. Match the Following
| Column A | Column B |
|---|
| 1. North-West Corner | (a) Minimises total transport cost |
| 2. VAM | (b) Solves assignment problems |
| 3. Hungarian method | (c) Starts from top-left cell |
| 4. Corner point | (d) Uses penalty difference |
| 5. Transportation problem | (e) Where optimal solution occurs in LPP |
Answer1 → (c): North-West Corner starts from the top-left cell. 2 → (d): VAM uses the penalty (difference between two smallest costs). 3 → (b): Hungarian method solves assignment problems. 4 → (e): Optimal solution occurs at a corner point of the feasible region. 5 → (a): Transportation problem minimises total transportation cost.
V. Answer Briefly
1. What are the components of a Linear Programming Problem?
Answer
An LPP has three components: 1. Objective function: A linear function to be maximised or minimised (e.g., Z = 5x + 3y) 2. Constraints: Linear inequalities or equations that restrict the decision variables (e.g., 2x + y ≤ 10) 3. Non-negativity restrictions: All decision variables must be non-negative (x ≥ 0, y ≥ 0)
2. Explain the steps of the graphical method for solving an LPP.
Answer
1. Formulate the LPP with objective function and constraints 2. Convert each inequality to an equation (replace ≤/≥ with =) 3. Plot each constraint line and identify the feasible side (use a test point, usually origin) 4. Shade the feasible region — the area satisfying ALL constraints 5. Find all corner points of the feasible region 6. Evaluate Z at each corner point 7. The corner point giving maximum Z (for maximisation) or minimum Z (for minimisation) is the optimal solution
3. What is the difference between balanced and unbalanced transportation problems?
Answer
| Feature | Balanced | Unbalanced | |---|---|---| | Supply vs Demand | Total supply = Total demand | Total supply ≠ Total demand | | Solution method | Direct methods applicable | Must add dummy source or destination | | Dummy | Not needed | Added with zero cost and required supply/demand | | Example | Supply = 100, Demand = 100 | Supply = 120, Demand = 100 (add dummy destination with demand 20) |
4. What are the different methods for finding an initial basic feasible solution in a transportation problem?
Answer
1. North-West Corner Method: Start from top-left cell, allocate min(supply, demand), move right or down. Simple but ignores costs. 2. Least Cost Method (Matrix Minimum): Identify the cell with the lowest cost, allocate maximum possible, eliminate exhausted row/column, repeat. Better than NWCM. 3. Vogel's Approximation Method (VAM): Calculate penalties (difference of two smallest costs) for each row and column. Allocate to the lowest-cost cell in the row/column with the highest penalty. Most efficient of the three — usually gives a near-optimal initial solution.
5. What is degeneracy in a transportation problem? How is it resolved?
Answer
Degeneracy occurs when the number of occupied (basic) cells is less than m + n − 1, where m is the number of sources and n is the number of destinations. This can happen during initial allocation or during the optimisation step. Resolution: Add an allocation of epsilon (ε, a very small positive number close to zero) to an independent zero cell so that the total number of basic cells becomes m + n − 1. The cell chosen must not form a closed loop with the existing basic cells.
6. What is an assignment problem? How does it differ from a transportation problem?
Answer
An assignment problem assigns n workers to n jobs on a one-to-one basis to minimise total cost (or maximise profit). | Feature | Transportation | Assignment | |---|---|---| | Supply/Demand | Any values | All equal to 1 | | Number of sources | m (any) | n | | Number of destinations | n (any) | n | | Solution method | NWCM, LCM, VAM + MODI | Hungarian method | | Decision | How many units to ship | Which worker gets which job | | Allocation | Fractional possible | Only 0 or 1 |
VI. Answer in Detail
1. Solve the following LPP using the graphical method: Maximise Z = 5x + 4y Subject to: x + y ≤ 10, x ≤ 6, y ≤ 8, x ≥ 0, y ≥ 0
Step 1: Plot the constraints Constraint 1: x + y ≤ 10 → Line x + y = 10 passes through (10, 0) and (0, 10) Constraint 2: x ≤ 6 → Vertical line at x = 6 Constraint 3: y ≤ 8 → Horizontal line at y = 8 Constraints 4 & 5: x ≥ 0, y ≥ 0 → First quadrant Step 2: Identify the feasible region The feasible region is bounded by all constraints in the first quadrant. Step 3: Find corner points - Origin: (0, 0) — intersection of x = 0, y = 0 - A: (6, 0) — intersection of x = 6, y = 0 - B: (6, 4) — intersection of x = 6 and x + y = 10 (6 + 4 = 10) ✓, check y ≤ 8: 4 ≤ 8 ✓ - C: (2, 8) — intersection of y = 8 and x + y = 10 → x = 2. Check x ≤ 6: 2 ≤ 6 ✓ - D: (0, 8) — intersection of x = 0, y = 8 Step 4: Evaluate Z at each corner point | Corner Point | Z = 5x + 4y | |---|---| | (0, 0) | 5(0) + 4(0) = 0 | | (6, 0) | 5(6) + 4(0) = 30 | | (6, 4) | 5(6) + 4(4) = 30 + 16 = 46 | | (2, 8) | 5(2) + 4(8) = 10 + 32 = 42 | | (0, 8) | 5(0) + 4(8) = 32 | Step 5: Optimal solution Maximum Z = 46 at (x, y) = (6, 4)
2. Solve the following LPP using the graphical method: Minimise Z = 3x + 2y Subject to: 2x + y ≥ 8, x + y ≥ 5, x + 2y ≥ 8, x ≥ 0, y ≥ 0
Step 1: Plot the constraints Constraint 1: 2x + y ≥ 8 → Line through (4, 0) and (0, 8), feasible side away from origin Constraint 2: x + y ≥ 5 → Line through (5, 0) and (0, 5), feasible side away from origin Constraint 3: x + 2y ≥ 8 → Line through (8, 0) and (0, 4), feasible side away from origin Constraints 4 & 5: x ≥ 0, y ≥ 0 Step 2: Find corner points of the feasible region The feasible region is unbounded towards the right and top, but bounded below. - A: Intersection of 2x + y = 8 and x + y = 5 Subtracting: x = 3, then y = 5 − 3 = 2. Point: (3, 2) Check: 2(3) + 2 = 8 ✓, 3 + 2 = 5 ✓, 3 + 4 = 7 ≥ 8? No. So (3,2) does NOT satisfy all constraints. - Let me find the correct corner points: Intersection of 2x + y = 8 and x + 2y = 8: From first: y = 8 − 2x. Substituting: x + 2(8 − 2x) = 8 → x + 16 − 4x = 8 → −3x = −8 → x = 8/3 y = 8 − 16/3 = 8/3. Point: (8/3, 8/3) Check x + y ≥ 5: 8/3 + 8/3 = 16/3 = 5.33 ≥ 5 ✓ Intersection of x + y = 5 and x + 2y = 8: From first: x = 5 − y. Substituting: 5 − y + 2y = 8 → y = 3, x = 2. Point: (2, 3) Check 2x + y ≥ 8: 4 + 3 = 7 < 8. Not feasible! Intersection of 2x + y = 8 and x + 2y = 8: (8/3, 8/3) as computed Intersection of x + 2y = 8 with x-axis: (8, 0) Check all constraints: 2(8)+0 = 16 ≥ 8 ✓, 8+0 = 8 ≥ 5 ✓, 8+0 ≥ 8 ✓ Intersection of 2x + y = 8 with y-axis: (0, 8) Check: 0+8 ≥ 5 ✓, 0+16 ≥ 8 ✓. Point: (0, 8) Intersection of x + 2y = 8 with y-axis: (0, 4) Check: 0+4 = 4 < 5. Not feasible! Step 3: The feasible corner points are: - (0, 8): from 2x + y = 8 on y-axis - (8/3, 8/3): intersection of 2x+y=8 and x+2y=8 - (8, 0): from x + 2y = 8 on x-axis Step 4: Evaluate Z | Corner Point | Z = 3x + 2y | |---|---| | (0, 8) | 0 + 16 = 16 | | (8/3, 8/3) | 3(8/3) + 2(8/3) = 8 + 16/3 = 40/3 ≈ 13.33 | | (8, 0) | 24 + 0 = 24 | Step 5: Optimal solution Minimum Z = 40/3 ≈ 13.33 at (x, y) = (8/3, 8/3)
3. Find the initial basic feasible solution using (i) North-West Corner method and (ii) Vogel's Approximation method for the following transportation problem:
Answer
| D1 | D2 | D3 | Supply |
|---|
| S1 | 2 | 3 | 5 | 20 |
| S2 | 4 | 1 | 3 | 30 |
| Demand | 10 | 25 | 15 | 50 |
(i) North-West Corner Method Start from the top-left cell (S1, D1): - Cell (S1, D1): Allocate min(20, 10) = 10. S1 supply: 20−10 = 10. D1 demand: 0. D1 is satisfied. - Cell (S1, D2): Allocate min(10, 25) = 10. S1 supply: 0. D2 demand: 25−10 = 15. S1 is exhausted. - Cell (S2, D2): Allocate min(30, 15) = 15. S2 supply: 30−15 = 15. D2 demand: 0. - Cell (S2, D3): Allocate min(15, 15) = 15. S2 supply: 0. D3 demand: 0. Total cost = 10(2) + 10(3) + 15(1) + 15(3) = 20 + 30 + 15 + 45 = 110 (ii) Vogel's Approximation Method (VAM) Iteration 1: Compute penalties - S1: |2−3| = 1, S2: |1−3| = 2 - D1: |2−4| = 2, D2: |1−3| = 2, D3: |3−5| = 2 Maximum penalty = 2 (multiple). Choose S2 (or any). Allocate to minimum cost cell in S2, which is D2 (cost 1). Allocate min(30, 25) = 25 to (S2, D2). D2 satisfied. S2 supply = 30 − 25 = 5. Iteration 2: Remove D2. Remaining: | | D1 | D3 | Supply | |---|---|---|---| | S1 | 2 | 5 | 20 | | S2 | 4 | 3 | 5 | | Demand | 10 | 15 | Penalties: S1: |5−2| = 3, S2: |4−3| = 1, D1: |4−2| = 2, D3: |5−3| = 2 Maximum penalty = 3 (S1). Allocate to min cost in S1, which is D1 (cost 2). Allocate min(20, 10) = 10 to (S1, D1). D1 satisfied. S1 supply = 20 − 10 = 10. Iteration 3: Remove D1. Remaining: | | D3 | Supply | |---|---|---| | S1 | 5 | 10 | | S2 | 3 | 5 | | Demand | 15 | Allocate min(10, 15) = 10 to (S1, D3). S1 exhausted. Allocate min(5, 5) = 5 to (S2, D3). Done. Total cost = 25(1) + 10(2) + 10(5) + 5(3) = 25 + 20 + 50 + 15 = 110 Both methods give the same total cost of 110 in this case. However, VAM typically gives better initial solutions for larger problems.
4. Solve the following assignment problem using the Hungarian method:
Answer
| J1 | J2 | J3 | J4 |
|---|
| W1 | 10 | 15 | 20 | 25 |
| W2 | 5 | 12 | 18 | 23 |
| W3 | 15 | 25 | 10 | 20 |
| W4 | 8 | 13 | 16 | 22 |
Step 1: Row reduction — subtract row minimum from each row Row 1 min = 10: Row 1 becomes [0, 5, 10, 15] Row 2 min = 5: Row 2 becomes [0, 7, 13, 18] Row 3 min = 10: Row 3 becomes [5, 15, 0, 10] Row 4 min = 8: Row 4 becomes [0, 5, 8, 14] Reduced matrix: | | J1 | J2 | J3 | J4 | |---|---|---|---|---| | W1 | 0 | 5 | 10 | 15 | | W2 | 0 | 7 | 13 | 18 | | W3 | 5 | 15 | 0 | 10 | | W4 | 0 | 5 | 8 | 14 | Step 2: Column reduction — subtract column minimum from each column Col 1 min = 0, Col 2 min = 5, Col 3 min = 0, Col 4 min = 10 Reduced matrix: | | J1 | J2 | J3 | J4 | |---|---|---|---|---| | W1 | 0 | 0 | 10 | 5 | | W2 | 0 | 2 | 13 | 8 | | W3 | 5 | 10 | 0 | 0 | | W4 | 0 | 0 | 8 | 4 | Step 3: Draw minimum lines to cover all zeros Row 1: 0, 0 — line through Row 1 or through Col 1, Col 2 Row 3: 0, 0 — line through Row 3 or through Col 3, Col 4 Try: Line through Col 1, Col 3, and Row 1 (need to cover zeros in Col 2 also) Better: Lines through Col 1, Col 3, Row 1 → this covers (W1,J1), (W1,J2), (W2,J1), (W3,J3), (W3,J4), (W4,J1). But (W4,J2) = 0 is not covered. Let me try 4 lines: Col 1, Col 3, Row 1, Row 3 → covers all zeros. But we need only n = 4 lines if optimal, or fewer if not. Actually, try: Line through Col 1 covers (W1,J1), (W2,J1), (W4,J1) Line through Col 3 covers (W3,J3) Line through Row 1 covers (W1,J2) Line through Row 3 covers (W3,J4) That's 4 lines = n, so optimal assignment exists. Step 4: Make the assignment Look for rows/columns with single zeros: - W3 has zeros at J3 and J4. W1 has zeros at J1 and J2. W4 has zeros at J1 and J2. - W2 has a single zero at J1. Assign W2 → J1 (only zero in Row 2 after considering competition) Now J1 is taken. Remove J1 column. W4 → J2 (W4's remaining zero is at J2) W1 → J1 is taken, so W1 → J2? No, J2 is taken by W4. W1 → need to check. Let me redo systematically. The zeros are at: (W1,J1), (W1,J2), (W2,J1), (W3,J3), (W3,J4), (W4,J1), (W4,J2) We need 4 assignments with zero cost. Since we have only 4 lines needed, let's find the assignment: - W3 → J3 (only row with exclusive zero in J3) - W2 → J1 (W2 only has zero at J1; but W1 and W4 also have zeros at J1) Let's try: W3→J3, then J3 is taken. Remaining zeros: (W1,J1), (W1,J2), (W2,J1), (W3,J4), (W4,J1), (W4,J2) Assign W3→J4 (zero at J4), W3→J3 (zero at J3). W3 can take J3 or J4. Let's try: W3→J3, then W1→J2 (W1 can't take J3, best is J2), W2→J1, W4→... J4? W4 has no zero at J4. Optimal Assignment: - W1 → J2: cost = 15 - W2 → J1: cost = 5 - W3 → J3: cost = 10 - W4 → J4: cost = 22 Total cost = 15 + 5 + 10 + 22 = 52 (Note: Since we can't cover all assignments with zeros alone, some assignment costs come from the original matrix.)
5. Formulate the following problem as an LPP and solve graphically: A factory produces two products A and B. Product A gives a profit of ₹5 per unit and product B gives ₹4 per unit. Product A requires 2 hours of machine time and product B requires 1 hour. Total machine time available is 100 hours. Product A requires 1 unit of raw material and product B requires 2 units. Total raw material available is 120 units. Find the product mix for maximum profit.
Step 1: Formulate the LPP Let x = number of units of A, y = number of units of B Maximise Z = 5x + 4y (profit) Subject to: 2x + y ≤ 100 (machine time) x + 2y ≤ 120 (raw material) x ≥ 0, y ≥ 0 Step 2: Find corner points Origin: (0, 0) x-intercept of 2x + y = 100: (50, 0) y-intercept of 2x + y = 100: (0, 100) x-intercept of x + 2y = 120: (120, 0) y-intercept of x + 2y = 120: (0, 60) Intersection of 2x + y = 100 and x + 2y = 120: From first: y = 100 − 2x Substituting: x + 2(100 − 2x) = 120 → x + 200 − 4x = 120 → −3x = −80 → x = 80/3 y = 100 − 160/3 = 140/3 Check: (80/3, 140/3) — both constraints satisfied. Corner points: (0, 0), (50, 0), (80/3, 140/3), (0, 60) Step 3: Evaluate Z at each corner point | Corner Point | Z = 5x + 4y | |---|---| | (0, 0) | 0 | | (50, 0) | 250 | | (80/3, 140/3) | 5(80/3) + 4(140/3) = 400/3 + 560/3 = 960/3 = 320 | | (0, 60) | 240 | Step 4: Optimal solution Maximum Z = ₹320 at x = 80/3 ≈ 26.67 units of A and y = 140/3 ≈ 46.67 units of B.
6. Solve the following transportation problem using the Least Cost Method:
Answer
| D1 | D2 | D3 | Supply |
|---|
| S1 | 3 | 1 | 7 | 30 |
| S2 | 5 | 6 | 4 | 40 |
| Demand | 20 | 30 | 20 | 70 |
Check balance: Total supply = 30 + 40 = 70, Total demand = 20 + 30 + 20 = 70. Balanced ✓ Iteration 1: Minimum cost in entire table = 1 (cell S1-D2) Allocate min(30, 30) = 30 to (S1, D2). S1 supply exhausted. D2 demand satisfied. Iteration 2: Remove S1 and D2. Remaining: | | D1 | D3 | Supply | |---|---|---|---| | S2 | 5 | 4 | 40 | | Demand | 20 | 20 | Minimum cost = 4 (cell S2-D3). Allocate min(40, 20) = 20 to (S2, D3). D3 demand satisfied. S2 supply = 20. Iteration 3: Remaining: | | D1 | Supply | |---|---|---| | S2 | 5 | 20 | | Demand | 20 | Allocate 20 to (S2, D1). Summary of allocations: | Cell | Allocation | Cost | Total | |---|---|---|---| | (S1, D2) | 30 | 1 | 30 | | (S2, D1) | 20 | 5 | 100 | | (S2, D3) | 20 | 4 | 80 | Total cost = 30 + 100 + 80 = 210 Number of basic cells = 3 = m + n − 1 = 2 + 3 − 1 = 4. Wait, we have only 3 basic cells but need 4. This is degeneracy! We need to add an epsilon (ε) allocation to make it 4. Actually, let me recount: (S1,D2) = 30, (S2,D1) = 20, (S2,D3) = 20. S1 has supply 30 (all to D2). S2 has supply 40 (20 to D1, 20 to D3). Basic cells = 3, but m + n − 1 = 2 + 3 − 1 = 4. We need one more basic cell. Add ε to cell (S1, D1) or (S1, D3) as an independent cell. (S1, D1) with allocation ε. Now we have 4 basic cells. Total cost remains 210 (since ε allocation contributes negligible cost).
Common Mistakes to Avoid
1. Forgetting non-negativity constraints — Always include x ≥ 0, y ≥ 0 in LPP formulations. Without these, the feasible region may extend into negative values which have no physical meaning.
2. Incorrectly identifying corner points — When finding the feasible region, only include intersections of constraint lines that satisfy ALL constraints. A point that lies on one constraint line but violates another constraint is not a corner point of the feasible region.
3. Confusing maximisation and minimisation — When the objective is to minimise, choose the smallest Z value at a corner point. When maximising, choose the largest. Always read the problem statement carefully.
4. Not balancing the transportation problem — Before solving, always verify that total supply equals total demand. If they are unequal, add a dummy source (if supply < demand) or dummy destination (if supply > demand) with zero costs.
5. Applying Hungarian method directly for maximisation — The Hungarian method solves minimisation problems. For maximisation (profit), first subtract each element from the maximum element in the matrix, then apply the method.
6. Mishandling degeneracy — In transportation problems, if the number of basic cells is less than m + n − 1, the solution is degenerate. Add an epsilon (ε) allocation to resolve this before proceeding with optimality check.
Exam Checklist
- [ ] I can formulate an LPP from a word problem (identify variables, objective, constraints)
- [ ] I can solve a two-variable LPP graphically (plot, find corner points, evaluate Z)
- [ ] I can find initial basic feasible solution using North-West Corner, Least Cost, and VAM methods
- [ ] I can balance an unbalanced transportation problem using a dummy source/destination
- [ ] I can solve an assignment problem using the Hungarian method
- [ ] I can handle degeneracy in transportation problems (add ε allocation)
- [ ] I can convert a maximisation assignment problem to minimisation
- [ ] I can identify special cases: infeasible, unbounded, and multiple optimal solutions
