Samacheer Kalvi Class 12 Business Maths Solutions Chapter 10 Operations Research Exercise 10.1

Tamilnadu Samacheer Kalvi 12th Business Maths Solutions Chapter 10 Operations Research Ex 10.1

 

Question 1. What is transportation problem?
Answer: A transportation problem aims to find the best way to move goods from different starting points (origins) to various ending points (destinations). The main goal is to figure out how much to send from each origin to each destination so that the total cost of transportation is as low as possible. This helps companies save money on shipping. It's a key part of logistics planning for businesses.
In simple words: A transportation problem helps decide how to ship items from factories to stores at the lowest cost.

🎯 Exam Tip: Transportation problems always involve minimizing cost, which is crucial for efficient supply chain management.

 

Question 2. Write mathematical form of transportation problem.
Answer: Let's say there are \( m \) starting points (origins) and \( n \) ending points (destinations). The supply at each origin \( i \) is \( a_i \), and the demand at each destination \( j \) is \( b_j \). The cost to move one unit of an item from origin \( i \) to destination \( j \) is \( C_{ij} \), which is known for every possible path. The quantity transported from origin \( i \) to destination \( j \) is \( X_{ij} \). The goal is to find the values of \( X_{ij} \) for all routes (i,j) to make the total transportation cost as small as possible. We also need to make sure that the supply limits at the origins and the demand needs at the destinations are met. This is a common method for optimizing resource allocation. The transportation problem can be described in the following table format:

Now, the linear programming model that shows this transportation problem is:
Objective function is: Minimize \( Z = \sum_{i=1}^{m} \sum_{j=1}^{n} C_{ij} X_{ij} \)
Subject to these rules:
\( \sum_{j=1}^{n} X_{ij} = a_i, i = 1, 2 ....... m \) (This ensures all supply from each origin is used or accounted for)
\( \sum_{i=1}^{m} X_{ij} = b_j, j = 1, 2 ....... n \) (This ensures all demand at each destination is met)
\( X_{ij} \ge 0 \) for all i, j (This means you cannot transport a negative amount of goods).
In simple words: We want to find the smallest cost to move things. We use a formula that adds up the cost for each path, and we must meet all supply and demand without moving negative items.

🎯 Exam Tip: Remember that \( X_{ij} \) must always be non-negative, as you cannot transport a negative quantity of goods.

 

Question 3. What is feasible solution and non degenerate solution in transportation problem?
Answer:
Feasible Solution: A feasible solution for a transportation problem is a collection of non-negative values for \( X_{ij} \). These values, where \( i \) goes from 1 to \( m \) and \( j \) goes from 1 to \( n \), must meet all the given supply and demand conditions. It simply means a possible way to transport goods that follows all the rules. It shows that the problem has at least one valid way to move goods.
Non-degenerate Basic Feasible Solution: If a basic feasible solution to a transportation problem has exactly \( m + n - 1 \) allocations, and all these allocations are in independent positions, then it is called a non-degenerate basic feasible solution. Here, \( m \) stands for the number of rows (origins) and \( n \) stands for the number of columns (destinations) in the transportation problem. This specific number of allocations helps in finding unique solutions.
In simple words: A feasible solution is any way to ship goods that meets all rules. A non-degenerate solution is a special type of feasible solution that has a certain number of assigned shipping paths.

🎯 Exam Tip: The \( m + n - 1 \) rule for non-degenerate solutions is a critical condition for many transportation problem algorithms like MODI method.

 

Question 4. What do you mean by balanced transportation problem?
Answer: A transportation problem is called a balanced transportation problem if the total amount of goods available from all origins (total supply) is exactly equal to the total amount of goods needed at all destinations (total demand). This condition, expressed as \( \Sigma a_i = \Sigma b_j \), is essential because it means that all available goods can be shipped and all demands can be met without any leftover supply or unmet demand. This makes the problem easier to solve. If they are not equal, it's called an unbalanced problem, which needs a dummy origin or destination.
In simple words: A transportation problem is balanced if the total supply exactly matches the total demand.

🎯 Exam Tip: Always check if a transportation problem is balanced (\( \Sigma a_i = \Sigma b_j \)) before solving, as unbalanced problems require an extra step to add a dummy row or column.

 

Question 5. Find an intial basic feasible solution of the following problem using north west corner rule.
Answer:
The initial transportation table is given below:

First, we check if the problem is balanced. Total supply is \( 19 + 37 + 34 = 90 \). Total demand is \( 16 + 18 + 31 + 25 = 90 \). Since total supply equals total demand, the problem is balanced. This means we can find an initial basic feasible solution. We will use the North West Corner rule to find the initial solution. This rule starts allocating from the top-left corner of the table. 1. **Allocate to (O\( _1 \), D\( _1 \)):** The cell in the North-West corner is (O\( _1 \), D\( _1 \)). We allocate the minimum of the supply for O\( _1 \) (19) and the demand for D\( _1 \) (16). \( X_{11} = \min(19, 16) = 16 \). Demand for D\( _1 \) is met (16-16 = 0). Supply for O\( _1 \) reduces (19-16 = 3). The D\( _1 \) column is now fulfilled.
2. **Allocate to (O\( _1 \), D\( _2 \)):** The next North-West corner cell in the reduced table is (O\( _1 \), D\( _2 \)). We allocate the minimum of the remaining supply for O\( _1 \) (3) and the demand for D\( _2 \) (18). \( X_{12} = \min(3, 18) = 3 \). Supply for O\( _1 \) is met (3-3 = 0). Demand for D\( _2 \) reduces (18-3 = 15). The O\( _1 \) row is now fulfilled.
3. **Allocate to (O\( _2 \), D\( _2 \)):** The next North-West corner cell is (O\( _2 \), D\( _2 \)). We allocate the minimum of the remaining supply for O\( _2 \) (37) and the remaining demand for D\( _2 \) (15). \( X_{22} = \min(37, 15) = 15 \). Demand for D\( _2 \) is met (15-15 = 0). Supply for O\( _2 \) reduces (37-15 = 22). The D\( _2 \) column is now fulfilled.
4. **Allocate to (O\( _2 \), D\( _3 \)):** The next North-West corner cell is (O\( _2 \), D\( _3 \)). We allocate the minimum of the remaining supply for O\( _2 \) (22) and the demand for D\( _3 \) (31). \( X_{23} = \min(22, 31) = 22 \). Supply for O\( _2 \) is met (22-22 = 0). Demand for D\( _3 \) reduces (31-22 = 9). The O\( _2 \) row is now fulfilled.
5. **Allocate to (O\( _3 \), D\( _3 \)):** The next North-West corner cell is (O\( _3 \), D\( _3 \)). We allocate the minimum of the remaining supply for O\( _3 \) (34) and the remaining demand for D\( _3 \) (9). \( X_{33} = \min(34, 9) = 9 \). Demand for D\( _3 \) is met (9-9 = 0). Supply for O\( _3 \) reduces (34-9 = 25). The D\( _3 \) column is now fulfilled.
6. **Allocate to (O\( _3 \), D\( _4 \)):** The only remaining cell is (O\( _3 \), D\( _4 \)). We allocate the minimum of the remaining supply for O\( _3 \) (25) and the remaining demand for D\( _4 \) (25). \( X_{34} = \min(25, 25) = 25 \). Both supply and demand are met (25-25 = 0 for both). The problem is now solved.
The final allocations are:
Transportation Schedule:
O\( _1 \)\( \rightarrow \) D\( _1 \) (16 units)
O\( _1 \)\( \rightarrow \) D\( _2 \) (3 units)
O\( _2 \)\( \rightarrow \) D\( _2 \) (15 units)
O\( _2 \)\( \rightarrow \) D\( _3 \) (22 units)
O\( _3 \)\( \rightarrow \) D\( _3 \) (9 units)
O\( _3 \)\( \rightarrow \) D\( _4 \) (25 units)
Total transportation cost \( = (16 \times 5) + (3 \times 3) + (15 \times 7) + (22 \times 9) + (9 \times 7) + (25 \times 5) \)
\( = 80 + 9 + 105 + 198 + 63 + 125 \)
\( = 580 \)
In simple words: We used the North West Corner rule to fill the table from top-left, making sure not to exceed supply or demand. We calculated the total cost by multiplying the allocated units by their costs.

🎯 Exam Tip: When applying the North West Corner rule, remember to always fulfill either the row's supply or the column's demand completely before moving to the next cell.

 

Question 6. Determine an intial basic feasible solution of the following transportation problem by north west corner method.
Answer:
The initial transportation table is given below:

First, we check if the problem is balanced. Total capacity (supply) is \( 30 + 40 + 50 = 120 \). Total demand is \( 35 + 28 + 32 + 25 = 120 \). Since total capacity equals total demand, the problem is balanced. We can now find an initial basic feasible solution using the North West Corner rule. 1. **Allocate to (Chennai, Bangalore):** The cell in the North-West corner is (Chennai, Bangalore). We allocate the minimum of Chennai's capacity (30) and Bangalore's demand (35). \( X_{11} = \min(30, 35) = 30 \). Chennai's capacity is met (30-30 = 0). Bangalore's demand reduces (35-30 = 5). The Chennai row is now fulfilled.
2. **Allocate to (Madurai, Bangalore):** The next North-West corner cell is (Madurai, Bangalore). We allocate the minimum of Madurai's capacity (40) and Bangalore's remaining demand (5). \( X_{21} = \min(40, 5) = 5 \). Bangalore's demand is met (5-5 = 0). Madurai's capacity reduces (40-5 = 35). The Bangalore column is now fulfilled.
3. **Allocate to (Madurai, Nasik):** The next North-West corner cell is (Madurai, Nasik). We allocate the minimum of Madurai's remaining capacity (35) and Nasik's demand (28). \( X_{22} = \min(35, 28) = 28 \). Nasik's demand is met (28-28 = 0). Madurai's capacity reduces (35-28 = 7). The Nasik column is now fulfilled.
4. **Allocate to (Madurai, Bhopal):** The next North-West corner cell is (Madurai, Bhopal). We allocate the minimum of Madurai's remaining capacity (7) and Bhopal's demand (32). \( X_{23} = \min(7, 32) = 7 \). Madurai's capacity is met (7-7 = 0). Bhopal's demand reduces (32-7 = 25). The Madurai row is now fulfilled.
5. **Allocate to (Trichy, Bhopal):** The next North-West corner cell is (Trichy, Bhopal). We allocate the minimum of Trichy's capacity (50) and Bhopal's remaining demand (25). \( X_{33} = \min(50, 25) = 25 \). Bhopal's demand is met (25-25 = 0). Trichy's capacity reduces (50-25 = 25). The Bhopal column is now fulfilled.
6. **Allocate to (Trichy, Delhi):** The only remaining cell is (Trichy, Delhi). We allocate the minimum of Trichy's remaining capacity (25) and Delhi's demand (25). \( X_{34} = \min(25, 25) = 25 \). Both capacity and demand are met (25-25 = 0 for both). The problem is now solved.
The final allocations are:
Transportation Schedule:
Chennai \( \rightarrow \) Bangalore (30 units)
Madurai \( \rightarrow \) Bangalore (5 units)
Madurai \( \rightarrow \) Nasik (28 units)
Madurai \( \rightarrow \) Bhopal (7 units)
Trichy \( \rightarrow \) Bhopal (25 units)
Trichy \( \rightarrow \) Delhi (25 units)
Total transportation cost \( = (30 \times 6) + (5 \times 5) + (28 \times 11) + (7 \times 9) + (25 \times 7) + (25 \times 13) \)
\( = 180 + 25 + 308 + 63 + 175 + 325 \)
\( = 1076 \)
In simple words: We systematically filled the transport table from the top-left, matching supply and demand at each step, and then added up the costs for all successful shipments.

🎯 Exam Tip: Ensure that all row capacities and column demands are fully satisfied at the end of the North West Corner allocation process, with no remaining supply or demand.

 

Question 7. Obtain an initial basic feasible solution to the following transportation problem
Answer:
The initial transportation table is given below:

First, we check if the problem is balanced. Total supply is \( 25 + 35 + 40 = 100 \). Total demand is \( 30 + 25 + 45 = 100 \). Since total supply equals total demand, the problem is balanced. We will use the Least Cost Method to find the initial solution. This method prioritizes cells with the lowest transportation cost. 1. **Allocate to (O\( _2 \), D\( _3 \)):** The least cost in the table is 4, which corresponds to the cell (O\( _2 \), D\( _3 \)). We allocate the minimum of O\( _2 \)'s supply (35) and D\( _3 \)'s demand (45). Allocate \( \min(35, 45) = 35 \) units to (O\( _2 \), D\( _3 \)). O\( _2 \)'s supply is met (35-35 = 0). D\( _3 \)'s demand reduces (45-35 = 10). The O\( _2 \) row is now fulfilled.
2. **Allocate to (O\( _1 \), D\( _3 \)):** The least cost in the remaining table is 5, which corresponds to the cell (O\( _1 \), D\( _3 \)). We allocate the minimum of O\( _1 \)'s supply (25) and D\( _3 \)'s remaining demand (10). Allocate \( \min(25, 10) = 10 \) units to (O\( _1 \), D\( _3 \)). D\( _3 \)'s demand is met (10-10 = 0). O\( _1 \)'s supply reduces (25-10 = 15). The D\( _3 \) column is now fulfilled.
3. **Allocate to (O\( _3 \), D\( _2 \)):** The least cost in the remaining table is 6, which corresponds to the cell (O\( _3 \), D\( _2 \)). We allocate the minimum of O\( _3 \)'s supply (40) and D\( _2 \)'s demand (25). Allocate \( \min(40, 25) = 25 \) units to (O\( _3 \), D\( _2 \)). D\( _2 \)'s demand is met (25-25 = 0). O\( _3 \)'s supply reduces (40-25 = 15). The D\( _2 \) column is now fulfilled.
4. **Allocate to (O\( _3 \), D\( _1 \)):** The least cost in the remaining table is 7, which corresponds to the cell (O\( _3 \), D\( _1 \)). We allocate the minimum of O\( _3 \)'s remaining supply (15) and D\( _1 \)'s demand (30). Allocate \( \min(15, 30) = 15 \) units to (O\( _3 \), D\( _1 \)). O\( _3 \)'s supply is met (15-15 = 0). D\( _1 \)'s demand reduces (30-15 = 15). The O\( _3 \) row is now fulfilled.
5. **Allocate to (O\( _1 \), D\( _1 \)):** The only remaining cell is (O\( _1 \), D\( _1 \)). We allocate the minimum of O\( _1 \)'s remaining supply (15) and D\( _1 \)'s remaining demand (15). Allocate \( \min(15, 15) = 15 \) units to (O\( _1 \), D\( _1 \)). Both supply and demand are met (15-15 = 0 for both). The problem is now solved.
The final allocations are:
Transportation Schedule:
O\( _1 \)\( \rightarrow \) D\( _1 \) (15 units)
O\( _1 \)\( \rightarrow \) D\( _3 \) (10 units)
O\( _2 \)\( \rightarrow \) D\( _3 \) (35 units)
O\( _3 \)\( \rightarrow \) D\( _1 \) (15 units)
O\( _3 \)\( \rightarrow \) D\( _2 \) (25 units)
Total transportation cost \( = (15 \times 9) + (10 \times 5) + (35 \times 4) + (15 \times 7) + (25 \times 6) \)
\( = 135 + 50 + 140 + 105 + 150 \)
\( = 580 \)
In simple words: We used the Least Cost Method by choosing the cheapest routes first and filling them as much as possible. Then we calculated the total cost from these allocations.

🎯 Exam Tip: The Least Cost Method often leads to a lower initial cost compared to the North West Corner rule because it considers costs from the very beginning.

 

Question 8. Explain vogel's approximation method by obtaining initial feasible solution of the following transportation problem.
Answer:
The initial transportation table is given below:

First, we check if the problem is balanced. Total supply \( \Sigma a_i = 6 + 1 + 10 = 17 \). Total demand \( \Sigma b_j = 7 + 5 + 3 + 2 = 17 \). Since total supply equals total demand, the problem is balanced. This means a feasible solution exists. Vogel's Approximation Method (VAM) tries to reduce the penalty cost by making good initial allocations. It works by finding the difference between the two smallest costs in each row and column (called the penalty). The cell in the row/column with the largest penalty is then chosen for allocation. 1. **Calculate Penalties:** Find the difference between the two smallest costs for each row and column.
2. **First Allocation:** The largest difference (penalty) is 6, which belongs to column D\( _4 \). In this column, the least cost is 1 (cell O\( _2 \), D\( _4 \)). We allocate \( \min(\text{supply for O\( _2 \)}, \text{demand for D\( _4 \)})\) which is \( \min(1, 2) = 1 \) unit to (O\( _2 \), D\( _4 \)). O\( _2 \)'s supply is met (1-1 = 0). D\( _4 \)'s demand reduces (2-1 = 1). The O\( _2 \) row is now fulfilled, so we remove it from further penalty calculations.
3. **Second Allocation:** The largest penalty is now 5 (column D\( _3 \)). The least cost in D\( _3 \) is 11 (cell O\( _1 \), D\( _3 \)). No, wait. I need to re-calculate penalties after the allocation and row/column removal. The table shown after the first allocation should be a *reduced* table, and then penalties re-calculated. The OCR image shows the new penalties in the next table. Let's follow that. Reduced table after first allocation (O\( _2 \) row removed):
The largest penalty is 5, which corresponds to column D\( _2 \). In D\( _2 \), the least cost is 3 (cell O\( _1 \), D\( _2 \)). We allocate \( \min(\text{supply for O\( _1 \)}, \text{demand for D\( _2 \)})\) which is \( \min(6, 5) = 5 \) units to (O\( _1 \), D\( _2 \)). D\( _2 \)'s demand is met (5-5 = 0). O\( _1 \)'s supply reduces (6-5 = 1). The D\( _2 \) column is now fulfilled.
4. **Third Allocation:** Now, the reduced table is:
The largest penalty is 8, which corresponds to column D\( _3 \). In D\( _3 \), the least cost is 11 (cell O\( _1 \), D\( _3 \)). No, wait. The problem statement in the image has a different set of penalties leading to a different path. Let's re-calculate penalties carefully from the last reduced table. **Recalculate Penalties based on the reduced table (D2 column removed):**
There are two largest penalties of 8. Let's choose the column D\( _3 \). In D\( _3 \), the least cost is 11 (cell O\( _1 \), D\( _3 \)). We allocate \( \min(\text{supply for O\( _1 \)}, \text{demand for D\( _3 \)})\) which is \( \min(1, 3) = 1 \) unit to (O\( _1 \), D\( _3 \)). O\( _1 \)'s supply is met (1-1 = 0). D\( _3 \)'s demand reduces (3-1 = 2). The O\( _1 \) row is now fulfilled.
5. **Fourth Allocation:** Now, the reduced table is:
The largest penalty is 8, which corresponds to column D\( _4 \). In D\( _4 \), the least cost is 9 (cell O\( _3 \), D\( _4 \)). We allocate \( \min(\text{supply for O\( _3 \)}, \text{demand for D\( _4 \)})\) which is \( \min(10, 1) = 1 \) unit to (O\( _3 \), D\( _4 \)). D\( _4 \)'s demand is met (1-1 = 0). O\( _3 \)'s supply reduces (10-1 = 9). The D\( _4 \) column is now fulfilled.
6. **Fifth Allocation:** Now, the reduced table is:
The largest penalty is 10, which corresponds to row O\( _3 \) (or column D\( _1 \)). Let's pick row O\( _3 \). In O\( _3 \), the least cost is 5 (cell O\( _3 \), D\( _1 \)). We allocate \( \min(\text{supply for O\( _3 \)}, \text{demand for D\( _1 \)})\) which is \( \min(9, 7) = 7 \) units to (O\( _3 \), D\( _1 \)). D\( _1 \)'s demand is met (7-7 = 0). O\( _3 \)'s supply reduces (9-7 = 2). The D\( _1 \) column is now fulfilled.
7. **Sixth Allocation:** Now, the reduced table is:
Only one cell remains: (O\( _3 \), D\( _3 \)). We allocate \( \min(\text{supply for O\( _3 \)}, \text{demand for D\( _3 \)})\) which is \( \min(2, 2) = 2 \) units to (O\( _3 \), D\( _3 \)). Both supply and demand are met (2-2 = 0 for both). The problem is now solved. The final allocations are:
Transportation Schedule:
O\( _1 \)\( \rightarrow \) D\( _2 \) (5 units)
O\( _1 \)\( \rightarrow \) D\( _3 \) (1 unit)
O\( _2 \)\( \rightarrow \) D\( _4 \) (1 unit)
O\( _3 \)\( \rightarrow \) D\( _1 \) (7 units)
O\( _3 \)\( \rightarrow \) D\( _3 \) (2 units)
O\( _3 \)\( \rightarrow \) D\( _4 \) (1 unit)
Total transportation cost \( = (5 \times 3) + (1 \times 11) + (1 \times 1) + (7 \times 5) + (2 \times 15) + (1 \times 9) \)
\( = 15 + 11 + 1 + 35 + 30 + 9 \)
\( = 101 \)
In simple words: VAM works by calculating "penalty costs" (the difference between the two lowest costs) for each row and column. We pick the highest penalty and allocate to the cheapest cell in that row or column, repeating until all supply and demand are met. This method often gives a better starting solution than the North West Corner or Least Cost methods.

🎯 Exam Tip: VAM is known for providing an initial basic feasible solution that is often very close to the optimal solution, making it more efficient than other methods in terms of solution quality.

 

Question 8. Explain vogel's approximation method by obtaining initial feasible solution of the following transportation problem.

Answer: First, we check if the total supply is equal to the total demand. Here, total supply \( \sum a_i = 6 + 1 + 10 = 17 \) and total demand \( \sum b_j = 7 + 5 + 3 + 2 = 17 \). Since total supply equals total demand, the problem is balanced. This means we can find a feasible solution for the transportation problem. We use the Vogel's Approximation Method by finding the "penalty" for each row and column. The penalty is the difference between the two smallest costs in that row or column.

Now, we find the largest penalty, which is 6, corresponding to column \(D_4\). In this column, the smallest cost is 1 (for cell \(O_2, D_4\)). We allocate the minimum of supply and demand for this cell: \(x_{24} = \text{min}(1, 2) = 1\) unit. This uses up the supply from \(O_2\) and reduces the demand for \(D_4\) to 1. The transportation table is then reduced.

The largest penalty is now 5, which is in column \(D_2\). The smallest cost in \(D_2\) is 3 (for cell \(O_1, D_2\)). We allocate \(x_{12} = \text{min}(6, 5) = 5\) units. This exhausts demand for \(D_2\) and reduces supply from \(O_1\) to 1. The table is further reduced.

The largest penalty is 4, in row \(O_1\). The least cost in row \(O_1\) is 2 (for cell \(O_1, D_1\)). We allocate \(x_{11} = \text{min}(1, 7) = 1\) unit. This uses up the remaining supply from \(O_1\) and reduces demand for \(D_1\) to 6. The table is reduced again.

The largest penalty is 4 for row \(O_3\). The least cost in row \(O_3\) is 5 (for cell \(O_3, D_1\)). We allocate \(x_{31} = \text{min}(10, 6) = 6\) units. This exhausts demand for \(D_1\) and reduces supply from \(O_3\) to 4. The table is further reduced.

The largest difference is 6, corresponding to row \(O_3\). The least cost is 9 (for cell \(O_3, D_4\)). We allocate \(x_{34} = \text{min}(4, 1) = 1\) unit. This uses up demand for \(D_4\) and reduces supply from \(O_3\) to 3. The table is further reduced.

The remaining allocation is for \(O_3, D_3\). We allocate \(x_{33} = \text{min}(3, 3) = 3\) units. This satisfies both the remaining supply and demand. The problem is now fully allocated.

The final transportation schedule is:
\(O_1 \rightarrow D_1\)
\(O_1 \rightarrow D_2\)
\(O_2 \rightarrow D_4\)
\(O_3 \rightarrow D_1\)
\(O_3 \rightarrow D_3\)
\(O_3 \rightarrow D_4\)

The total transportation cost is calculated by multiplying the allocated units by their respective costs and summing them up:
Cost \( = (1 \times 2) + (5 \times 3) + (1 \times 1) + (6 \times 5) + (3 \times 15) + (1 \times 9) \)
Cost \( = 2 + 15 + 1 + 30 + 45 + 9 \)
Cost \( = 102 \)
In simple words: We find the cheapest way to send items from their starting places to their end locations. We keep making smart choices to reduce costs until all items are sent. The goal is to get the lowest possible total shipping cost.

🎯 Exam Tip: Remember that Vogel's Approximation Method (VAM) aims to find a good initial basic feasible solution by minimizing penalties, which often leads to a solution closer to the optimal one compared to other methods.

 

Question 9. Consider the following transportation problem.

Determine initial basic feasible solution by VAM
Answer: First, let's check if the total supply equals the total demand. Total availability \( \sum a_i = 30 + 50 + 20 = 100 \). Total requirement \( \sum b_j = 30 + 40 + 20 + 10 = 100 \). Since total supply matches total demand, the problem is balanced. This means we can find an initial basic feasible solution. We will use Vogel's Approximation Method by calculating the difference (penalty) between the two smallest costs in each row and column.

The largest difference is 3, which is for column \(D_2\). In this column, the least cost is 2 (for cell \(O_3, D_2\)). We allocate the minimum of availability and requirement for this cell: \(x_{32} = \text{min}(20, 40) = 20\) units. This exhausts the availability from \(O_3\) and reduces the requirement for \(D_2\) to 20. The transportation table is reduced.

The largest difference is 4, in column \(D_3\). The least cost in column \(D_3\) is 3 (for cell \(O_1, D_3\)). We allocate \(x_{13} = \text{min}(30, 20) = 20\) units. This exhausts the requirement for \(D_3\) and reduces the availability from \(O_1\) to 10. The table is further reduced.

The largest difference is 3, corresponding to column \(D_2\). In this column, the least cost is 5 (for cell \(O_2, D_2\)). We allocate \(x_{22} = \text{min}(50, 20) = 20\) units. This exhausts the requirement for \(D_2\) and reduces the availability from \(O_2\) to 30. The table is further reduced.

The largest difference is 2, corresponding to column \(D_4\). In this column, the least cost is 4 (for cell \(O_2, D_4\)). We allocate \(x_{24} = \text{min}(30, 10) = 10\) units. This exhausts the requirement for \(D_4\) and reduces the availability from \(O_2\) to 20. The table is further reduced.

We now allocate the remaining units. For cell \(O_1, D_1\), we allocate \(x_{11} = \text{min}(10, 30) = 10\) units. This exhausts the availability from \(O_1\) and reduces the requirement for \(D_1\) to 20. For cell \(O_2, D_1\), we allocate \(x_{21} = \text{min}(20, 20) = 20\) units. This satisfies both the remaining availability and requirement. The problem is now fully allocated.

The final allocations are:
\(x_{11} = 10\)
\(x_{13} = 20\)
\(x_{21} = 20\)
\(x_{22} = 20\)
\(x_{24} = 10\)
\(x_{32} = 20\)

The transportation schedule is:
\(O_1 \rightarrow D_1\)
\(O_1 \rightarrow D_3\)
\(O_2 \rightarrow D_1\)
\(O_2 \rightarrow D_2\)
\(O_2 \rightarrow D_4\)
\(O_3 \rightarrow D_2\)

The total transportation cost is:
Cost \( = (10 \times 5) + (20 \times 3) + (20 \times 4) + (20 \times 5) + (10 \times 4) + (20 \times 2) \)
Cost \( = 50 + 60 + 80 + 100 + 40 + 40 \)
Cost \( = 370 \)
In simple words: This method helps us find the cheapest way to send goods from factories to shops. We first look at the most costly problems (highest penalties) and fix them first to save more money. This helps us get a good starting plan for shipping.

🎯 Exam Tip: Always double-check that all supply and demand requirements are met in your final allocation and that the number of allocated cells is \(m+n-1\) for a non-degenerate solution.

 

Question 10. Determine basic feasible solution to the following transportation problem using North west Corner rule.

Answer: First, we verify if the total supply equals the total demand. Total supply \( = 4 + 8 + 9 = 21 \). Total demand \( = 3 + 3 + 4 + 5 + 6 = 21 \). Since total supply equals total demand, the problem is balanced. This allows us to find an initial basic feasible solution using the North West Corner rule. We start allocating units from the top-left cell of the table.

**Step 1: Cell (P, A)**
Allocate \(x_{11} = \text{min}(\text{supply at P}=4, \text{demand at A}=3) = 3\) units.
Supply at P becomes \(4-3=1\). Demand at A becomes \(3-3=0\).
The reduced transportation table (column A exhausted) is:

**Step 2: Cell (P, B)**
Allocate \(x_{12} = \text{min}(\text{supply at P}=1, \text{demand at B}=3) = 1\) unit.
Supply at P becomes \(1-1=0\). Demand at B becomes \(3-1=2\).
The reduced transportation table (row P exhausted) is:

**Step 3: Cell (Q, B)**
Allocate \(x_{22} = \text{min}(\text{supply at Q}=8, \text{demand at B}=2) = 2\) units.
Supply at Q becomes \(8-2=6\). Demand at B becomes \(2-2=0\).
The reduced transportation table (column B exhausted) is:

**Step 4: Cell (Q, C)**
Allocate \(x_{23} = \text{min}(\text{supply at Q}=6, \text{demand at C}=4) = 4\) units.
Supply at Q becomes \(6-4=2\). Demand at C becomes \(4-4=0\).
The reduced transportation table (column C exhausted) is:

**Step 5: Cell (Q, D)**
Allocate \(x_{24} = \text{min}(\text{supply at Q}=2, \text{demand at D}=5) = 2\) units.
Supply at Q becomes \(2-2=0\). Demand at D becomes \(5-2=3\).
The reduced transportation table (row Q exhausted) is:

**Step 6: Cell (R, D)**
Allocate \(x_{34} = \text{min}(\text{supply at R}=9, \text{demand at D}=3) = 3\) units.
Supply at R becomes \(9-3=6\). Demand at D becomes \(3-3=0\).
The reduced transportation table (column D exhausted) is:

**Step 7: Cell (R, E)**
Allocate \(x_{35} = \text{min}(\text{supply at R}=6, \text{demand at E}=6) = 6\) units.
Supply at R becomes \(6-6=0\). Demand at E becomes \(6-6=0\). The problem is now fully allocated.

The transportation schedule is:
P \( \rightarrow \) A
P \( \rightarrow \) B
Q \( \rightarrow \) B
Q \( \rightarrow \) C
Q \( \rightarrow \) D
R \( \rightarrow \) D
R \( \rightarrow \) E

The total transportation cost is:
Cost \( = (3 \times 2) + (1 \times 11) + (2 \times 4) + (4 \times 7) + (2 \times 2) + (3 \times 8) + (6 \times 12) \)
Cost \( = 6 + 11 + 8 + 28 + 4 + 24 + 72 \)
Cost \( = 153 \)
In simple words: The North West Corner rule is a straightforward way to start solving transportation problems. You begin allocating items from the top-left cell of the table, making sure to use up as much supply or demand as possible at each step, moving only right or down. This method helps get a first solution quickly.

🎯 Exam Tip: The North West Corner Rule is simple but doesn't consider costs. It's usually the first step to find a basic feasible solution, which then needs further optimization methods (like MODI or Stepping Stone) to get the best possible (optimal) cost.

 

Question 11. Find the initial basic feasible solution of the following transportation problem: Using
(i) North West corner rule
(ii) Least Cost method
(iii) Vogel's approximation method

Answer: First, we check if the problem is balanced by comparing total supply and total demand. Total supply \( = 10 + 10 + 10 = 30 \). Total demand \( = 7 + 12 + 11 = 30 \). Since total supply equals total demand, the problem is balanced and a feasible solution exists. We will now find the initial basic feasible solution using the three specified methods:

(i) North West Corner Rule:
We start allocating from the top-left cell (A, I).

**Step 1: Cell (A, I)**
Allocate \(x_{AI} = \text{min}(\text{supply at A}=7, \text{demand at I}=10) = 7\) units.
Supply at A becomes \(7-7=0\). Demand at I becomes \(10-7=3\).
The reduced table (row A exhausted) is:

**Step 2: Cell (B, I)**
Allocate \(x_{BI} = \text{min}(\text{supply at B}=12, \text{demand at I}=3) = 3\) units.
Supply at B becomes \(12-3=9\). Demand at I becomes \(3-3=0\).
The reduced table (column I exhausted) is:

**Step 3: Cell (B, II)**
Allocate \(x_{BII} = \text{min}(\text{supply at B}=9, \text{demand at II}=10) = 9\) units.
Supply at B becomes \(9-9=0\). Demand at II becomes \(10-9=1\).
The reduced table (row B exhausted) is:

**Step 4: Cell (C, II)**
Allocate \(x_{CII} = \text{min}(\text{supply at C}=11, \text{demand at II}=1) = 1\) unit.
Supply at C becomes \(11-1=10\). Demand at II becomes \(1-1=0\).
The reduced table (column II exhausted) is:

**Step 5: Cell (C, III)**
Allocate \(x_{CIII} = \text{min}(\text{supply at C}=10, \text{demand at III}=10) = 10\) units.
Supply at C becomes \(10-10=0\). Demand at III becomes \(10-10=0\). All supplies and demands are satisfied. This completes the North West Corner solution.

The transportation schedule is:
A \( \rightarrow \) I
B \( \rightarrow \) I
B \( \rightarrow \) II
C \( \rightarrow \) II
C \( \rightarrow \) III

The total transportation cost is:
Cost \( = (7 \times 1) + (3 \times 0) + (9 \times 4) + (1 \times 1) + (10 \times 5) \)
Cost \( = 7 + 0 + 36 + 1 + 50 \)
Cost \( = 94 \)
In simple words: This method starts by filling the top-left box of the table. We keep filling cells as much as possible, then move to the right or down, until everything is shipped. It's a quick way to get an initial plan.

🎯 Exam Tip: When using the North West Corner Rule, remember to prioritize exhausting either the row supply or column demand at each step before moving to the next cell. Always start at the extreme top-left.

(ii) Least Cost Method:
We start allocating from the cell with the minimum cost. Here, the least cost is 0, in cell (B, I).

**Step 1: Cell (B, I)**
Allocate \(x_{BI} = \text{min}(\text{supply at B}=12, \text{demand at I}=10) = 10\) units.
Supply at B becomes \(12-10=2\). Demand at I becomes \(10-10=0\).
The reduced table (column I exhausted) is:

**Step 2: Cell (C, II)**
The least cost in the reduced table is 1 (for cell (C, II)). Allocate \(x_{CII} = \text{min}(\text{supply at C}=11, \text{demand at II}=10) = 10\) units.
Supply at C becomes \(11-10=1\). Demand at II becomes \(10-10=0\).
The reduced table (column II exhausted) is:

**Step 3: Cell (B, III)**
The least cost in the reduced table is 2 (for cell (B, III)). Allocate \(x_{BIII} = \text{min}(\text{supply at B}=2, \text{demand at III}=10) = 2\) units.
Supply at B becomes \(2-2=0\). Demand at III becomes \(10-2=8\).
The reduced table (row B exhausted) is:

**Step 4: Cell (C, III)**
The least cost is 5 (for cell (C, III)). Allocate \(x_{CIII} = \text{min}(\text{supply at C}=1, \text{demand at III}=8) = 1\) unit.
Supply at C becomes \(1-1=0\). Demand at III becomes \(8-1=7\).
The reduced table (row C exhausted) is:

**Step 5: Cell (A, III)**
Allocate \(x_{AIII} = \text{min}(\text{supply at A}=7, \text{demand at III}=7) = 7\) units. Both supply and demand are satisfied. The problem is now fully allocated.

The transportation schedule is:
A \( \rightarrow \) III
B \( \rightarrow \) I
B \( \rightarrow \) III
C \( \rightarrow \) II
C \( \rightarrow \) III

The total transportation cost is:
Cost \( = (7 \times 6) + (10 \times 0) + (2 \times 2) + (10 \times 1) + (1 \times 5) \)
Cost \( = 42 + 0 + 4 + 10 + 5 \)
Cost \( = 61 \)
In simple words: The Least Cost Method focuses on choosing the cheapest routes first. We find the cell with the lowest cost, allocate as much as possible, and then move to the next lowest cost cell until all items are shipped. This helps find a good initial plan that tries to keep costs down from the start.

🎯 Exam Tip: The Least Cost Method generally provides a better initial basic feasible solution than the North West Corner Rule because it considers the actual costs of transportation in its allocation strategy.

(iii) Vogel's Approximation Method:
We calculate the penalty for each row and column, which is the difference between the two smallest costs. We choose the row or column with the largest penalty and then allocate units to the cell with the minimum cost in that chosen row or column.

**Step 1: First Allocation**
The largest penalty is 3, corresponding to column III. In column III, the least cost is 2 (for cell (B, III)). Allocate \(x_{BIII} = \text{min}(\text{supply at B}=12, \text{demand at III}=10) = 10\) units.
Supply at B becomes \(12-10=2\). Demand at III becomes \(10-10=0\).
The reduced table (column III exhausted) is:

**Step 2: Second Allocation**
The largest penalty is 4, corresponding to row B. In row B, the least cost is 0 (for cell (B, I)). Allocate \(x_{BI} = \text{min}(\text{supply at B}=2, \text{demand at I}=10) = 2\) units.
Supply at B becomes \(2-2=0\). Demand at I becomes \(10-2=8\).
The reduced table (row B exhausted) is:

**Step 3: Third Allocation**
The largest penalty is 2, corresponding to column I and row C. Let's pick row C. In row C, the least cost is 1 (for cell (C, II)). Allocate \(x_{CII} = \text{min}(\text{supply at C}=11, \text{demand at II}=10) = 10\) units.
Supply at C becomes \(11-10=1\). Demand at II becomes \(10-10=0\).
The reduced table (column II exhausted) is:

**Step 4: Fourth Allocation**
The remaining penalty is 2, corresponding to column I. In column I, the least cost is 1 (for cell (A, I)). Allocate \(x_{AI} = \text{min}(\text{supply at A}=7, \text{demand at I}=8) = 7\) units.
Supply at A becomes \(7-7=0\). Demand at I becomes \(8-7=1\).
The reduced table (row A exhausted) is:

**Step 5: Fifth Allocation**
The remaining cell is (C, I). Allocate \(x_{CI} = \text{min}(\text{supply at C}=1, \text{demand at I}=1) = 1\) unit.
Supply at C becomes \(1-1=0\). Demand at I becomes \(1-1=0\). All supplies and demands are satisfied. This completes the Vogel's Approximation Method solution.

The transportation schedule is:
A \( \rightarrow \) I
B \( \rightarrow \) I
B \( \rightarrow \) III
C \( \rightarrow \) I
C \( \rightarrow \) II

The total transportation cost is:
Cost \( = (7 \times 1) + (2 \times 0) + (10 \times 2) + (1 \times 3) + (10 \times 1) \)
Cost \( = 7 + 0 + 20 + 3 + 10 \)
Cost \( = 40 \)
In simple words: This method is usually the best for finding a starting solution because it considers the cost differences (penalties). By focusing on the biggest penalties, it tries to avoid making expensive choices, which often leads to a solution that is very close to the best possible (optimal) cost.

🎯 Exam Tip: VAM is often preferred over North West Corner and Least Cost methods for finding initial feasible solutions because it accounts for potential "regrets" (penalties), resulting in a solution that is typically closer to the optimal one.

 

Question 11. Find the initial basic feasible solution of the following transportation problem:

Using
(i) North West corner rule
(ii) Least Cost method
(iii) Vogel's approximation method
Answer:

(i) North West corner rule:
First, we check that the total supply ( \( 7 + 12 + 11 = 30 \) ) equals the total demand ( \( 10 + 10 + 10 = 30 \) ), confirming it is a balanced transportation problem. Now we can find an initial basic feasible solution. The Northwest Corner Method starts allocations from the top-left cell of the table.

Allocate \( x_{A1} = \min(7, 10) = 7 \) units to cell (A, I). Row A capacity is exhausted.

The reduced transportation table is:

Allocate \( x_{BI} = \min(3, 12) = 3 \) units to cell (B, I). Column I demand is exhausted.

The reduced transportation table is:

Allocate \( x_{BII} = \min(9, 10) = 9 \) units to cell (B, II). Row B capacity is exhausted.

The reduced transportation table is:

Allocate \( x_{CII} = \min(11, 1) = 1 \) unit to cell (C, II). Column II demand is exhausted.

The reduced transportation table is:

Allocate \( x_{CIII} = \min(10, 10) = 10 \) units to cell (C, III). All capacities and demands are exhausted.

The final allocations are:

Transportation schedule:
\( O_1 \rightarrow D_1; O_1 \rightarrow D_2; O_2 \rightarrow D_2; O_3 \rightarrow D_3; O_3 \rightarrow D_2 \)
Total transportation cost:
\( = (7 \times 1) + (3 \times 0) + (9 \times 4) + (1 \times 1) + (10 \times 5) \)
\( = 7 + 0 + 36 + 1 + 50 \)
\( = 94 \)

(ii) Least cost method:
This method prioritizes allocating units to the cells with the lowest transportation costs first, irrespective of their position. We confirm the problem is balanced as total supply equals total demand (both 30). Then we proceed with allocations.

The least cost is 0, corresponding to cell (B, I). Allocate \( \min(12, 10) = 10 \) units to this cell. Column I demand is exhausted.

The reduced transportation table is:

The next least cost is 1, corresponding to cell (C, II). Allocate \( \min(11, 10) = 10 \) units to this cell. Column II demand is exhausted.

The reduced transportation table is:

The next least cost is 2, corresponding to cell (B, III). Allocate \( \min(2, 10) = 2 \) units to this cell. Row B capacity is exhausted.
The next least cost is 5, corresponding to cell (C, III). Allocate \( \min(1, 8) = 1 \) unit to this cell. Row C capacity is exhausted.
The next least cost is 6, corresponding to cell (A, III). Allocate \( \min(7, 7) = 7 \) units to this cell. Row A capacity and column III demand are exhausted.

Thus, we have the following allocations:

Transportation schedule:
\( A \rightarrow III; B \rightarrow I; B \rightarrow III; C \rightarrow II; C \rightarrow III \)
Total transportation cost:
\( = (7 \times 6) + (10 \times 0) + (2 \times 2) + (10 \times 1) + (1 \times 5) \)
\( = 42 + 0 + 4 + 10 + 5 \)
\( = 61 \)

(iii) Vogel's approximation method:
This method involves calculating penalties (differences between the two smallest costs in each row and column) and making allocations to the cell corresponding to the largest penalty. This helps in finding a good initial basic feasible solution. The problem is balanced, with total supply and demand both being 30.

First, calculate the penalties for each row and column (difference between the two smallest costs).

The largest penalty is 3 (from column III). The least cost in this column is 2 (cell B, III). Allocate \( x_{BIII} = \min(12, 10) = 10 \) units. Column III demand is exhausted.

The table for Second Allocation:

The largest penalty is 4 (from row B). The least cost in this row is 0 (cell B, I). Allocate \( x_{BI} = \min(2, 10) = 2 \) units. Row B capacity is exhausted.

The table for Third Allocation:

The largest penalty is 2 (from column I). The least cost in this column is 1 (cell A, I). Allocate \( x_{AI} = \min(7, 8) = 7 \) units. Row A capacity is exhausted.

The table for Fourth Allocation:

Remaining supply for C is 11, remaining demand for I is 1. Allocate \( x_{CI} = \min(11, 1) = 1 \) unit. Column I demand is exhausted.

The table for Fifth Allocation:

Remaining supply for C is 10, remaining demand for II is 10. Allocate \( x_{CII} = \min(10, 10) = 10 \) units. All capacities and demands are exhausted.

Thus, we have the following allocations:

Transportation schedule:
\( A \rightarrow I; B \rightarrow I; B \rightarrow III; C \rightarrow I; C \rightarrow II \)
Total transportation cost:
\( = (7 \times 1) + (2 \times 0) + (10 \times 2) + (1 \times 3) + (10 \times 1) \)
\( = 7 + 0 + 20 + 3 + 10 \)
\( = 40 \)
In simple words: This question asks us to find the best way to move goods from factories to stores using three different methods. Each method gives a different starting plan and a different total cost. The goal is to find a good starting solution that keeps the total transport cost as low as possible.

🎯 Exam Tip: When using different methods like Northwest Corner, Least Cost, or Vogel's Approximation, always clearly label each part of your solution to avoid confusion. Also, double-check that your total supply equals total demand before starting any allocations.

 

Question 12. Obtain an initial basic feasible solution to the following transportation problem by north west corner method.

Answer:

First, let's check if the problem is balanced by comparing total available supply and total required demand.

Total available supply \( = 250 + 300 + 400 = 950 \)
Total required demand \( = 200 + 225 + 275 + 250 = 950 \)

Since total supply equals total demand, the problem is balanced, and we can find an initial basic feasible solution. We will use the North West Corner method, starting allocations from the top-left cell.

From the table, we choose cell (A, D). Allocate \( x_{AD} = \min(250, 200) = 200 \) units. Column D demand is exhausted.

The reduced transportation table is:

Next, choose cell (A, E). Allocate \( x_{AE} = \min(50, 225) = 50 \) units. Row A capacity is exhausted.

The reduced transportation table is:

Now, choose cell (B, E). Allocate \( x_{BE} = \min(300, 175) = 175 \) units. Column E demand is exhausted.

The reduced transportation table is:

Next, choose cell (B, F). Allocate \( x_{BF} = \min(125, 275) = 125 \) units. Row B capacity is exhausted.

The reduced transportation table is:

Next, choose cell (C, F). Allocate \( x_{CF} = \min(400, 150) = 150 \) units. Column F demand is exhausted.

The reduced transportation table is:

Finally, choose cell (C, G). Allocate \( x_{CG} = \min(250, 250) = 250 \) units. All capacities and demands are exhausted.

Thus, we have the following allocations:

Transportation schedule:
\( A \rightarrow D; A \rightarrow E; B \rightarrow E; B \rightarrow F; C \rightarrow F; C \rightarrow G \)
Total Transportation cost:
\( = (200 \times 11) + (50 \times 13) + (175 \times 18) + (125 \times 14) + (150 \times 13) + (250 \times 10) \)
\( = 2200 + 650 + 3150 + 1750 + 1950 + 2500 \)
\( = 12,200 \)
In simple words: We found the first possible way to transport all goods from factories to cities by always picking the top-left available box in the table. This method ensures that all factories send out their goods and all cities get what they need, while trying to keep the overall cost as low as possible.

🎯 Exam Tip: Remember to always check if the total supply matches the total demand first. If they don't match, the problem is unbalanced, and you would need to add a dummy row or column to balance it before proceeding with the North West Corner Method.