Operations Management MBA 2024-25 PDF
Document Details
ICFAI Business School Hyderabad
2024
IBS
Dr. Hasanuzzaman
Tags
Related
- Lecture 21 Optimization Problems PDF
- Computer Aided Design for Transportation (CDT521S) Lecture 1 PDF
- Basic Elements of Transportation Planning PDF
- Computer Based Optimization Techniques Exam 2023-2024 PDF
- Note 23 Oct 2024 PDF
- Problem-Solving Exercise: Addressing Social Determinants in Healthcare Scenarios PDF
Summary
This document is an Operations Management MBA past paper from the ICFAI Business School for the Academic Year 2024-25. The paper covers the transportation problem, including its assumptions, important definitions, and examples for different scenarios.
Full Transcript
Operations Management MBA Academic Year 2024-25 Dr. Hasanuzzaman Assistant Professor Operations & Information Technology ICFAI Business School Hyderabad Transportation Transportation Scenario 1 Transportation Scenario 2 ...
Operations Management MBA Academic Year 2024-25 Dr. Hasanuzzaman Assistant Professor Operations & Information Technology ICFAI Business School Hyderabad Transportation Transportation Scenario 1 Transportation Scenario 2 Transportation D1 b 𝐶𝑖𝑗 1 a S1 Demand Center 1 Supply Center D2 b 2 a S2 2 D3 b 3 ai Si 𝑥𝑖𝑗 Dj bj Minimize (Cost and / or Time) Z= σ𝑖 =𝑚,𝑗=𝑛 𝑥𝑖𝑗 𝐶𝑖𝑗 Supply Constraint, σ𝑖=𝑚 𝑥𝑖𝑗 = 𝑎𝑖 Demand Constraint, σ𝑗=𝑛 𝑥𝑖𝑗 = 𝑏𝑗 𝑎𝑖 > 0 𝑏𝑗 > 0 Transportation ▪ The objective is to determine the number of units of an item (commodity or product) that should be shipped from an origin (limited quantity of goods or services available at each origin) to a destination in order to satisfy the required quantity of goods or services at each destination centre at the minimum transportation cost and/or time that can maximize the profit. Supply D1 D2 D3 D4 (Availability) S1 19 30 50 10 7 S2 70 30 40 60 9 S3 40 8 70 20 18 Demand 5 8 7 14 34 (Requirement) Transportation – Assumption ▪ The total quantity of the item available at different sources is equal to the total requirement at different destinations ▪ Item can be transported conveniently from all sources to destinations ▪ The unit transportation cost of the item from all sources to destinations is certainly and precisely known ▪ The transportation cost on a given route is directly proportional to the number of units shipped on that route ▪ The objective is to minimize total transportation costs for the organization as a whole and not for individual supply and distribution centres. Transportation Supply D1 D2 D3 D4 (Availability) 19 30 50 10 7 2 S1 5 2 0 70 30 40 60 9 S2 3 6 3 0 40 8 70 20 18 S3 4 14 14 0 Demand 5 8 7 14 (Requirement) 0 6 0 34 4 0 0 Transportation Problem – Important Definitions When the total supply is equal to the total demand, the problem is called – A balanced transportation problem, otherwise it is called an unbalanced transportation problem. – The unbalanced transportation problem can be made balanced by adding a dummy supply centre (row) or a dummy demand centre (column) as the need arises. Cells in the transportation table having positive allocation, i.e., 𝑥𝑖𝑗 > 0 are called occupied cells, otherwise are known as non-occupied (or empty) cells Transportation Problem – Important Definitions Feasible Solution: Any set of non-negative allocations (𝑥𝑖𝑗 > 0) which satisfies the row and column sum (rim requirement) is called a feasible solution. Basic Feasible Solution: A feasible solution is called a basic feasible solution if the number of non-negative allocations is equal to 𝑚 + 𝑛 − 1, where m is the number of rows and n the number of columns in a transportation table. Non-degenerate Basic Feasible Solution: Any feasible solution to a transportation problem containing m origins and n destinations is said to be non- degenerate, if it contains 𝑚 + 𝑛 − 1 occupied cells and each allocation is in independent positions. Degenerate Basic Feasible Solution: If a basic feasible solution contains less than 𝑚 + 𝑛 − 1 non-negative allocations, it is said to be degenerate. Optimal Solution: Optimal solution is a feasible solution (not necessarily basic) which minimizes the total cost Transportation Problem – Algorithm Step 1: Formulate the problem and arrange the data in the matrix form – Here the objective function is the total transportation cost and the constraints are the supply and demand available at each source and destination, respectively. Step 2: Obtain an initial basic feasible solution – North-West Corner Method – Least cost Method – Vogel’s Approximation (or penalty) Method The initial solution obtained by any of the three methods must satisfy the following conditions: 1. The solution must be feasible, i.e. it must satisfy all the supply and demand constraints (also called rim conditions). 2. The number of positive allocations must be equal to m + n – 1 Step 3:Test the initial solution for optimality. – The stepping stone and the Modified Distribution (MODI) method Step 4: Updating the solution Transportation - Example ▪ A company has three production facilities S1, S2 and S3 with production capacity of 7, 9 and 18 units (in 100s) per week of a product, respectively. These units are to be shipped to four warehouses D1, D2, D3 and D4 with requirement of 5, 8, 7 and 14 units (in 100s) per week, respectively. The transportation costs (in rupees) per unit between factories to warehouses are given in the table below. Supply D1 D2 D3 D4 (Availability) S1 19 30 50 10 7 S2 70 30 40 60 9 S3 40 8 70 20 18 Demand 5 8 7 14 34 (Requirement) ▪ Formulate this transportation problem as an LP model to minimize the total transportation cost. Initial Basic Solution - NCWM Supply D1 D2 D3 D4 (Availability) 19 30 50 10 7 2 S1 5 2 0 Is it a basic feasible solution ? 70 30 40 60 9 Satisfies Demand-Supply 3 Constraint S2 6 3 0 Non-negativity condition Independent Allocation 40 8 70 20 18 – m (3) + n (4) – 1 = 6 S3 4 14 14 0 Demand 5 8 7 14 0 6 0 34 (Requirement) 4 0 0 Total cost = 5 × 19 + 2 × 30 + 6 × 30 + 3 × 40 + 4 × 70 + 14 × 20 = Rs 1,015 Initial Basic Solution - LCM Supply D1 D2 D3 D4 (Availability) 19 30 50 10 7 S1 7 Is it a basic feasible solution ? Satisfies Demand-Supply 70 30 40 60 9 Constraint S2 2 7 Non-negativity condition Independent Allocation 40 8 70 20 18 – m (3) + n (4) – 1 = 6 S3 2 8 7 Demand 5 8 7 14 (Requirement) 34 Total cost = 7 × 10 + 2 × 70 + 7 × 40 + 3 × 40 + 8 × 8 + 7 × 20 = Rs 814 Initial Basic Solution - VAM ▪ A company has three production facilities S1, S2 and S3 with production capacity of 7, 9 and 18 units (in 100s) per week of a product, respectively. These units are to be shipped to four warehouses D1, D2, D3 and D4 with requirement of 5, 8, 7 and 14 units (in 100s) per week, respectively. The transportation costs (in rupees) per unit between factories to warehouses are given in the table below. Supply D1 D2 D3 D4 (Availability) 19 30 50 10 7 S1 70 30 40 60 9 S2 40 8 70 20 18 S3 Demand 5 8 7 14 (Requirement) 34 Initial Basic Solution - VAM ▪ Step 1: Calculate the penalties for each row (column) by taking the difference between the smallest and next smallest unit transportation cost in the same row (column). This difference indicates the penalty or extra cost that has to be paid if one fails to allocate to the cell with the minimum unit transportation cost. Supply Row D1 D2 D3 D4 (Availability) Difference (penalty) 19 30 50 10 7 19-10=9 S1 70 30 40 60 9 40-30=10 S2 40 8 70 20 18 20-8=12 S3 Demand 5 8 7 14 34 (Requirement) Initial Basic Solution - VAM ▪ Step 2: Select the row or column with the largest penalty and allocate as much as possible in the cell that has the least cost in the selected row or column and satisfies the rim conditions. If there is a tie in the values of penalties, it can be broken by selecting the cell where the maximum allocation can be made. Supply Row D1 D2 D3 D4 (Availability) Difference (penalty) 19 30 50 10 7 19-10=9 S1 70 30 40 60 9 40-30=10 S2 40 8 70 20 18 20-8=12 S3 Demand 5 8 7 14 34 (Requirement) Penalty 40-19=21 30-8=22 50-40=10 20-10=10 Initial Basic Solution - VAM ▪ Step 3: Adjust the supply and demand and cross out the satisfied row or column. If a row and a column are satisfied simultaneously, only one of them is crossed out and the remaining row (column) is assigned a zero supply (demand). Any row or column with zero supply or demand should not be used in computing future penalties. Supply Row D1 D2 D3 D4 (Availability) Difference (penalty) 19 30 50 10 7 19-10=9 S1 70 30 40 60 9 40-30=10 S2 40 8 70 20 18 20-8=12 S3 Demand 5 8 7 14 34 (Requirement) Penalty 40-19=21 30-8=22 50-40=10 20-10=10 Initial Basic Solution – VAM -Final ▪ Final Allocation Supply P1 P2 P3 P4 D1 D2 D3 D4 (Availability) S1 19 5 30 50 10 2 7 9 9 40 40 S2 70 30 40 7 60 2 9 10 20 20 20 S3 40 8 8 70 20 10 18 12 20 50 - Demand 5 8 7 14 34 (Requirement) Is it a basic feasible solution ? P1 40-19=21 30-8=22 50-40=10 20-10=10 Satisfies Demand-Supply P2 21 - 10 10 Constraint P3 - - 10 10 Non-negativity condition P4 - - 10 50 Independent Allocation – m (3) + n (4) – 1 = 6 Total cost = 5 × 19 + 2 × 10 + 7 × 40 + 2 × 60 + 8 × 8 + 10 × 20 = Rs 779 NWCM vs. LCM vs. VAM NWCM does not consider cost of transportation. LCM considers the transportation cost VAM is preferred over NWCM and LCM as allocation is made on the basis of opportunity / penalty cost that would have been incurred if the allocation in certain cells with minimum unit transportation cost were missed NWCM LCM VAM Total cost 1015 814 779 Test for Optimality The test of optimality begins by calculating an opportunity cost associated with each unoccupied cell. An unoccupied cell with the largest negative opportunity cost is selected to include in the new set of transportation routes (allocations). – This value indicates the per unit cost reduction that can be achieved by making appropriate allocation in the unoccupied cell. This cell is also known as an incoming cell (or variable). The outgoing cell (or variable) from the current solution is the occupied cell (basic variable) where allocation will become zero as allocation is made in the unoccupied cell with the largest negative opportunity cost. Methods – Modified-distribution Method (MODI) or u-v method or method of multipliers – Stepping Stone Method Test for Optimality – MODI Method MODI method begins by calculating opportunity cost associated with each unoccupied cell. An unoccupied cell with the largest negative opportunity cost is selected to include in the new set of transportation routes (allocations). This value indicates the per unit cost reduction that can be achieved by raising the shipment allocation in the unoccupied cell from its present level of zero. An efficient technique called the modified-distribution (MODI) method (also called u-v method or method of multipliers), which helps in comparing the relative advantage of alternative allocations for all the unoccupied cells. Test for Optimality – MODI Method Step 1: For a given basic feasible solution if we assign numbers (also called dual variables or multipliers) 𝑢𝑖 and 𝑣𝑗 with row i (i = 1, 2,..., m) and column j ( j = 1, 2,..., n) of the transportation table, respectively. Supply 𝑢𝑖 D1 D2 D3 D4 19 30 50 10 7 𝑢1 S1 5 2 70 30 40 60 9 𝑢2 S2 7 2 40 8 70 20 18 𝑢3 S3 8 10 Demand 5 8 7 14 34 Total cost = 5 × 19 + 2 × 10 + 7 × 40 + 2 × 60 + 8 × 8 + 10 × 20 = Rs 𝑣𝑗 𝑣1 𝑣2 𝑣3 𝑣4 779 Test for Optimality – MODI Method Step 2: To start with, any one of uis or vjs is assigned the value zero. It is better to assign zero to a particular ui or vj where there are maximum number of allocations in a row or column respectively, as this will reduce the considerably arithmetic work. The 𝑢𝑖 and 𝑣𝑗 must satisfy the equation 𝑢𝑖 + 𝑣𝑗 = 𝑐𝑖𝑗 , for each occupied cell (i, j). Supply 𝑢𝑖 D1 D2 D3 D4 19 30 50 10 7 𝑢1 = 10 S1 5 2 70 30 40 60 9 𝑢2 = 60 S2 7 2 40 8 70 20 18 𝑢3 = 20 S3 8 10 Demand 5 8 7 14 34 𝑣𝑗 𝑣1 = 9 𝑣2 = −12 𝑣3 = −20 𝑣4 = 0 Test for Optimality – MODI Method Step 3: Once the values of 𝑢𝑖 and 𝑣𝑗 have been determined, evaluation in terms of opportunity cost of each unoccupied cell (called non-basic variable or unused route) is done by using the equation: 𝑑𝑟𝑠 = 𝑐𝑟𝑠 – (𝑢𝑟 + 𝑣𝑠) , for each unoccupied cell (r, s) Supply 𝑢𝑖 D1 D2 D3 D4 19 30 50 10 7 𝑢1 = 10 S1 5 +32 +60 2 70 30 40 60 9 𝑢2 = 60 S2 +1 -18 7 2 40 8 70 20 18 𝑢3 = 20 S3 +11 8 +70 10 Demand 5 8 7 14 34 𝑣𝑗 𝑣1 = 9 𝑣2 = −12 𝑣3 = −20 𝑣4 = 0 Test for Optimality – MODI Method Step 4: ▪ If 𝑑𝑖𝑗 > 0, then the current basic feasible solution is optimal. ▪ If 𝑑𝑖𝑗 = 0, then the current basic feasible solution will remain unaffected but an alternative solution exists. ▪ If 𝑑𝑖𝑗 < 0 for one or more unoccupied cell, then an improved solution can be obtained by entering unoccupied cell (i, j) in the basis. An unoccupied cell having the largest negative value of 𝑑𝑖𝑗 is chosen for entering into the solution mix (new transportation schedule). Supply 𝑢𝑖 D1 D2 D3 D4 19 30 50 10 7 𝑢1 = 10 S1 5 +32 +60 2 70 30 40 60 9 𝑢2 = 60 S2 +1 -18 7 2 40 8 70 20 18 𝑢3 = 20 S3 +11 8 +70 10 Demand 5 8 7 14 34 𝑣𝑗 𝑣1 = 9 𝑣2 = −12 𝑣3 = −20 𝑣4 = 0 Test for Optimality – MODI Method ▪ Step 5: Construct a closed-path (or loop) for the unoccupied cell with largest negative opportunity cost. Start the closed path with the selected unoccupied cell and mark a plus sign (+) in this cell. Trace a path along the rows (or columns) to an occupied cell, mark the corner with a minus sign (–) and continue down the column (or row) to an occupied cell. Then mark the corner with plus sign (+) and minus sign (–) alternatively. Close the path back to the selected unoccupied cell Supply 𝑢𝑖 D1 D2 D3 D4 19 30 50 10 7 𝑢1 = 10 S1 5 +32 +60 2 70 30 + 40 60 - 9 𝑢2 = 60 S2 +1 -18 7 2 40 8 - 70 20 + 18 𝑢3 = 20 S3 +11 8 +70 10 Demand 5 8 7 14 34 𝑣𝑗 𝑣1 = 9 𝑣2 = −12 𝑣3 = −20 𝑣4 = 0 Test for Optimality – MODI Method ▪ Step 6: Select the smallest quantity amongst the cells marked with minus sign on the corners of closed loop. Allocate this value to the selected unoccupied cell and add it to other occupied cells marked with plus signs. Now subtract this from the occupied cells marked with minus signs. Further test the revised solution for optimality. The procedure terminates when all 𝑑𝑖𝑗 > 0 for unoccupied cells. Supply 𝑢𝑖 D1 D2 D3 D4 19 30 50 10 7 𝑢1 = 10 S1 5 +32 +60 2 70 30 + 40 60 - 9 𝑢2 = 60 S2 +1 2 -18 7 40 8 - 70 20 + 18 𝑢3 = 20 S3 +11 6 +70 12 Demand 5 8 7 14 34 𝑣𝑗 𝑣1 = 9 𝑣2 = −12 𝑣3 = −20 𝑣4 = 0 Test for Optimality – MODI Method ▪ Step 6: Select the smallest quantity amongst the cells marked with minus sign on the corners of closed loop. Allocate this value to the selected unoccupied cell and add it to other occupied cells marked with plus signs. Now subtract this from the occupied cells marked with minus signs. Further test the revised solution for optimality. The procedure terminates when all 𝑑𝑖𝑗 > 0 for unoccupied cells. Supply 𝑢𝑖 D1 D2 D3 D4 19 30 50 10 7 𝑢1 = 0 S1 5 +32 +42 2 70 30 40 60 9 𝑢2 = 32 S2 +19 2 7 +14 40 8 70 20 18 𝑢3 = 10 S3 +11 6 +52 12 Demand 5 8 7 14 34 Total cost = 5 × 19 + 2 × 10 + 7 × 40 + 2 × 30 + 6 × 8 + 12 × 20 = Rs 𝑣𝑗 𝑣1 = 19 𝑣2 = −2 𝑣3 = 8 𝑣4 = 10 743 Transportation – Practice ▪ Compute basic feasible solution and find out the optimal solution P Q R S Supply A 6 3 5 4 22 B 5 9 2 7 15 C 5 7 8 6 8 Demand 7 12 17 9 45 Transportation Problem – Special Case ▪ CASE 1. UNBALANCED PROBLEM: ▪ When quantity demanded is larger than supply D1 D2 D3 D4 SUPPLY S1 3 5 6 7 11 S2 2 5 6 8 5 S3 3 5 7 9 4 DEMAND 5 7 8 3 20/23 D1 D2 D3 D4 SUPPLY S1 3 5 6 7 11 S2 2 5 6 8 5 S3 3 5 7 9 4 S excess 0 0 0 0 3 DEMAND 5 7 8 3 23/23 Transportation Problem – Special Case ▪ CASE 1. UNBALANCED PROBLEM: ▪ When quantity demanded is fewer than supply D1 D2 D3 D4 SUPPLY S1 3 5 6 7 11 S2 2 5 6 8 12 S3 3 5 7 9 4 DEMAND 5 7 8 3 27/23 D1 D2 D3 D4 Dexcess SUPPLY S1 3 5 6 7 0 11 S2 2 5 6 8 0 12 S3 3 5 7 9 0 4 DEMAND 5 7 8 3 4 27/27 Transportation Problem – Special Case ▪ CASE 2. DEGENERACY IN INITIAL SOLUTION : To resolve degeneracy at the initial solution, we proceed by allocating a very small quantity close to zero to one or more (if needed) unoccupied cells so as to get 𝑚 + 𝑛 – 1 number of occupied cells. This amount is denoted by a Greek letter 𝜖 (epsilon) or Δ (delta). The quantity Δ is considered to be so small that if it is transferred to an occupied cell it does not change the quantity of allocation. That is, 𝑥𝑖𝑗 + Δ = 𝑥𝑖𝑗 − Δ = 𝑥𝑖𝑗 Δ + Δ = Δ; Δ − Δ = 0 0 + Δ = Δ; 𝑘 × Δ = Δ It is also obvious then that Δ does not affect the total transportation cost of the allocation. Hence, the quantity Δ is used to evaluate unoccupied cells and to reduce the number of improvement cycles necessary to reach an optimal solution. Once the purpose is over, Δ can be removed from the transportation table Transportation Problem – Special Case ▪ CASE 2. DEGENERACY IN INITIAL SOLUTION : Example A manufacturer wants to ship 22 loads of his product as shown below. The matrix gives the kilometres from sources of supply to the destinations. D1 D2 D3 D4 D5 Supply S1 5 8 6 6 3 8 S2 4 7 7 6 5 5 S3 8 4 6 6 4 9 Demand 4 4 5 4 8 The shipping cost is Rs 10 per load per km. What shipping schedule should be used in order to minimize the total transportation cost? Transportation Problem – Special Case ▪ CASE 3. DEGENERACY IN SUBSEQUENT ITERATION: To resolve degeneracy, which occurs during optimality test, the quantity may be allocated to one or more cells that have recently been unoccupied, to have m + n – 1 number of occupied cells in the new solution. Example: Goods have to be transported from sources S1, S2 and S3 to destinations D1, D2 and D3. The transportation cost per unit, capacities of the sources, and the requirements of the destinations are given in the following table. D1 D2 D3 Supply S1 8 5 6 120 S2 15 10 12 80 S3 3 9 10 80 Demand 150 80 50 Determine a transportation schedule so that cost is minimized Transportation Problem – Special Case ▪ CASE 3. Alternative Solution: If an unoccupied cell in an optimal solution has an opportunity cost of zero, an alternative optimal solution can be formed with another set of allocations, without increasing the total transportation cost Example: Goods have to be transported from sources W, X and Y to destinations A, B and C. The transportation cost per unit, capacities of the sources, and the requirements of the destinations are given in the following table. A B C SUPPLY W 4 8 8 76 X 16 24 16 82 Y 8 16 24 77 DEMAND 72 102 41 20 Determine a transportation schedule so that cost is minimized Thank You