Optimal Solutions (TP) - Part 2

Duration: 12 min

This video lesson is available to enrolled students.

Enroll to watch — Coal India Management Trainee (CS) Recruitment 2026

AI Summary

An AI-generated summary of this video lecture.

This video is a lecture on solving a transportation problem in linear programming, specifically using the Vogel's Approximation Method (VAM). The instructor begins by presenting a transportation table with supply and demand values for four sources (Pada, Indore, Ranchi, Pune) and four destinations (Kolkata, Delhi, Mumbai, Chennai). He first reviews the North West Corner method, calculating a total cost of 189,200. He then introduces VAM as a more efficient method to find a better initial basic feasible solution. The instructor demonstrates the VAM process step-by-step: he calculates the penalty for each row and column by finding the difference between the two smallest costs, identifies the row or column with the highest penalty, and allocates as much as possible to the cell with the lowest cost in that row or column. He repeats this process, updating the table and penalties, until all supply and demand are satisfied. The final solution obtained using VAM has a total cost of 140,920, which is significantly lower than the initial solution, illustrating the method's effectiveness.

Chapters

  1. 0:00 – 2:00 00:00-02:00

    The video opens with a whiteboard displaying a transportation problem titled "Linear Programming Problem" and "Stealing Stone Problem". The instructor, a man in a checkered shirt, stands to the right of the board. He presents a 4x4 transportation table with supply values (200, 160, 160, 90) for sources Pada, Indore, Ranchi, and Pune, and demand values (180, 120, 150, 90) for destinations Kolkata, Delhi, Mumbai, and Chennai. The cost matrix is filled with numbers like 16, 20, 12, etc. The instructor begins by explaining the problem and then calculates the total supply (610) and total demand (540), noting the imbalance. He then proceeds to solve the problem using the North West Corner method, writing the formula for the minimum cost: 180x15 + 20x20 + 100x12 + 60x15 + 90x14 + 40x8 + 100x16 + 10x140 + 10x140. He calculates the total cost as 189,200, which is written as "min (189,200)" on the board.

  2. 2:00 – 5:00 02:00-05:00

    The instructor introduces the Vogel's Approximation Method (VAM) as a better approach. He begins by drawing a new, empty 4x4 table on the right side of the whiteboard. He then explains the first step of VAM: calculating the penalty for each row and column. The penalty is the difference between the two smallest costs in that row or column. He calculates the penalties for the first row (Kolkata): 20-16=4, for the second row (Delhi): 12-8=4, for the third row (Mumbai): 18-8=10, and for the fourth row (Chennai): 16-9=7. He then calculates the penalties for the columns: Kolkata (16-14=2), Delhi (20-8=12), Mumbai (12-8=4), and Chennai (16-9=7). He identifies the highest penalty, which is 12 in the Delhi column, and allocates the maximum possible amount to the cell with the lowest cost in that column, which is Indore to Delhi (cost 8). He allocates 120 units, satisfying the Delhi demand, and crosses out the Delhi column.

  3. 5:00 – 10:00 05:00-10:00

    The instructor continues the VAM process. After the first allocation, he recalculates the penalties for the remaining rows and columns. The new penalties are: Pada (16-12=4), Indore (20-16=4), Ranchi (18-16=2), Pune (24-16=8). For the columns: Kolkata (16-14=2), Mumbai (12-12=0), Chennai (16-9=7). The highest penalty is now 8 in the Pune row. He allocates the maximum possible amount to the lowest cost cell in this row, which is Pune to Chennai (cost 9). He allocates 90 units, satisfying the Chennai supply, and crosses out the Pune row. He then recalculates the penalties again. The new penalties are: Pada (16-12=4), Indore (20-16=4), Ranchi (18-16=2). For the columns: Kolkata (16-14=2), Mumbai (12-12=0), Chennai (16-16=0). The highest penalty is 4, which occurs in both Pada and Indore rows. He chooses the Pada row and allocates to the lowest cost cell, Pada to Kolkata (cost 16). He allocates 180 units, satisfying the Kolkata demand, and crosses out the Kolkata column.

  4. 10:00 – 12:28 10:00-12:28

    The instructor completes the VAM solution. With Kolkata and Pune eliminated, he recalculates the penalties. The remaining cells are Indore to Mumbai (20), Ranchi to Mumbai (18), and Ranchi to Chennai (16). The penalties are: Indore (20-16=4), Ranchi (18-16=2). The highest penalty is 4 in the Indore row. He allocates to the lowest cost cell in this row, which is Indore to Mumbai (cost 20). He allocates 160 units, satisfying the Indore supply, and crosses out the Indore row. The only remaining cell is Ranchi to Mumbai (cost 18). He allocates the remaining 150 units to this cell, satisfying the Mumbai demand. The final solution is written as: Pada-Kolkata (180), Indore-Delhi (120), Indore-Mumbai (160), Ranchi-Mumbai (150), Ranchi-Chennai (90). He then calculates the total cost: 180x16 + 120x8 + 160x20 + 150x18 + 90x9 = 2880 + 960 + 3200 + 2700 + 810 = 140,920. He writes "VAM = 140,920" and "C. Method = 6600" on the board, concluding the demonstration.

The video provides a comprehensive, step-by-step demonstration of solving a transportation problem in linear programming. It begins by establishing the problem's parameters and calculating an initial solution using the North West Corner method, which yields a total cost of 189,200. The core of the lecture is the application of the Vogel's Approximation Method (VAM), a more sophisticated heuristic. The instructor meticulously walks through each iteration of VAM, emphasizing the calculation of penalties (the difference between the two smallest costs in a row or column) to prioritize allocations. By always selecting the row or column with the highest penalty and allocating to the cell with the lowest cost, VAM produces a significantly better initial solution with a total cost of 140,920. The video effectively contrasts the two methods, highlighting VAM's superiority in finding a near-optimal starting point for further optimization.