Skip to main content

Engineering Computer Science Operations Research: Applications and Algorithms

Description: TV picture tubes are produced by a company at three plants. The capacities of each of the plants are 50, 100 and 50 per week, respectively. Three customers are willing to purchase a maximum quantity of 80 tubes, 90 tubes and 100 tubes per week respectively. The profits per tube are indicated in the table below: CUSTOMER 1 CUSTOMER 2 CUSTOMER 3 Plant 1 75 60 69 Plant 2 79 73 68 Plant 3 85 76 70 Since the profits per tube are given, to process further in identifying the optimal solution to the transportation problem, first convert the profits matrix into opportunity loss matrix by subtracting all profit from the maximum profit of the matrix. a. Formulating a balanced transportation problem: The matrix will not be balanced since the total supply is not equal to the total demand. So, add another temporary or dummy plant with a supply of 70 tubes and with zero costs. Then the corresponding matrix is shown below: CUSTOMER 1 CUSTOMER 2 CUSTOMER 3 SUPPLY Plant 1 75 60 69 80 Plant 2 79 73 68 100 Plant 3 85 76 70 50 Plant 4 0 0 0 70 Demand 80 90 100 b. Finding a BFS for the problem using northwest corner method: Step 1: Begin with upper left corner cell (C1, W1) of the transportation table. The supply at that cell is 50 and the demand is 80. Allocate 50 to that cell and cross out row Plant1. Remaining demand amount at Customer1 would be 80 – 50 = 30 . Step2: In the remaining table, choose the upper left corner cell (R2, C1) with supply 100 and demand 30. Allocate 30 to the cell and cross out Customer 1 column. The supply at Plant 2 row would be 100 – 30 = 70 . Step3: In the remaining table, choose the upper left corner cell (R2, C2) with supply 70 and demand 90. Allocate 70 to the cell and cross out row Plant2. The remaining demand at customer 2 would be 90 – 70 = 20 . Step4: In the remaining table, choose the upper left corner cell (R3, C2) with supply 50 and demand 20. Allocate 20 to the cell and cross out Customer 2. The remaining supply at Plant 3 would be 50 – 20 = 30 . Step5: In the remaining table, choose the upper left corner cell (R3, C3) with supply 30 and demand 100. Allocate 30 to the cell and cross out Plant 3. Step6: The only available cell is (R4, C3) with supply 70 and demand 70. Hence, allocate 70 to the cell. As no cells are available, the process of finding BFS is finished. Therefore, the BFS for the given problem is as follows: x 11 =50, x 21 =30, x 22 =70, x 32 =20, x 33 =30, x 43 =70 with z = 50 × 75+30 × 79 + 70 × 73 + 20 × 76 + 30 × 70 + 0 × 70 = 14850 c. Finding an optimal solution for the problem using the transportation simplex: Since the transportation table contains (m+n–1) = 6 basic cells, move to the next step in finding the optimum solution. Here, “m” is the number of rows and “n” is the number of columns. Assume that u 1 = 0 . Also, assume that u i + v j = c i j for all basic variables to find u 1 u 2 ... u m v 1 v 2 ... v n for the current BFS. Obtain the u i ' s and v j ' s for the current BFS. u 1 = 0 u 1 + v 1 = 75 u 2 + v 1 = 79 u 2 + v 2 = 73 u 2 + v 3 = 67 u 3 + v 3 = 70 u 4 + v 3 = 0 By solving the above equations, we get, u 1 = 0 v 1 = 75 u 2 = 4 v 2 = 69 u 3 = 7 v 3 = 63 u 4 = − 63 Now, compute c i j ¯ = u i + v j − c i j for each of the non-basic variable and check whether all c i j ¯ for non-basic variables are positive. If all c i j ¯ of non-basic variables are positive, then the obtained solution is optimum. Observe that x 33 will be the entering variable with the below given value, θ = min ( 50 , 70 , 30 ) = 30 Also, x 21 will be the leaving variable. Continue further in the same way for changing the BFS to reach the optimal solution. The next table will be as shown below: The current solution for the problem is as follows: x 11 =20, x 21 =60, x 22 =40, x 32 =50, x 33 =30, x 43 =70 with z = 20 × 75+60 × 79 + 40 × 73 + 50 × 76 + 30 × 69 + 0 × 70 = 15030 Obtain the u i ' s and v j ' s for the current BFS. u 1 = 0 u 1 + v 1 = 75 u 2 + v 1 = 79 u 2 + v 2 = 73 u 3 + v 2 = 76 u 1 + v 3 = 69 u 4 + v 3 = 0 By solving the above equations, we get, u 1 = 0 v 1 = 75 u 2 = 4 v 2 = 69 u 3 = 7 v 3 = 69 u 4 = − 69 Now, compute c i j ¯ = u i + v j − c i j for each of the non-basic variable and check whether all c i j ¯ for non-basic variables are positive. If all c i j ¯ of non-basic variables are positive, then the obtained solution is optimum. Observe that x 32 will be the entering variable with the below given value, θ = min ( 60 , 50 ) = 50 Also, x 31 will be the leaving variable. The current solution for the problem is as follows: x 11 =20, x 21 =10, x 22 =90, x 31 =50, x 13 =30, x 43 =70 with z = 20 × 75+10 × 79 + 90 × 73 + 50 × 85 + 30 × 69 + 0 × 70 = 15180 Obtain the u i ' s and v j ' s for the current BFS. u 1 = 0 u 1 + v 1 = 75 u 2 + v 1 = 79 u 2 + v 2 = 73 u 3 + v 1 = 85 u 1 + v 3 = 69 u 4 + v 3 = 0 By solving the above equations, we get, u 1 = 0 v 1 = 75 u 2 = 4 v 2 = 69 u 3 = 10 v 3 = 69 u 4 = − 69 For the current BFS, all c i j ¯ ≥ 0 , so an optimal solution is obtained. Thus, the optimal solution to the problem is as follows: x 11 =20, x 21 =10, x 22 =90, x 31 =50, x 13 =30, x 43 =70 The optimal value of the problem is as follows: z = 20 × 75+10 × 79 + 90 × 73 + 50 × 85 + 30 × 69 + 0 × 70 = 15180

Description: TV picture tubes are produced by a company at three plants. The capacities of each of the plants are 50, 100 and 50 per week, respectively. Three customers are willing to purchase a maximum quantity of 80 tubes, 90 tubes and 100 tubes per week respectively. The profits per tube are indicated in the table below: CUSTOMER 1 CUSTOMER 2 CUSTOMER 3 Plant 1 75 60 69 Plant 2 79 73 68 Plant 3 85 76 70 Since the profits per tube are given, to process further in identifying the optimal solution to the transportation problem, first convert the profits matrix into opportunity loss matrix by subtracting all profit from the maximum profit of the matrix. a. Formulating a balanced transportation problem: The matrix will not be balanced since the total supply is not equal to the total demand. So, add another temporary or dummy plant with a supply of 70 tubes and with zero costs. Then the corresponding matrix is shown below: CUSTOMER 1 CUSTOMER 2 CUSTOMER 3 SUPPLY Plant 1 75 60 69 80 Plant 2 79 73 68 100 Plant 3 85 76 70 50 Plant 4 0 0 0 70 Demand 80 90 100 b. Finding a BFS for the problem using northwest corner method: Step 1: Begin with upper left corner cell (C1, W1) of the transportation table. The supply at that cell is 50 and the demand is 80. Allocate 50 to that cell and cross out row Plant1. Remaining demand amount at Customer1 would be 80 – 50 = 30 . Step2: In the remaining table, choose the upper left corner cell (R2, C1) with supply 100 and demand 30. Allocate 30 to the cell and cross out Customer 1 column. The supply at Plant 2 row would be 100 – 30 = 70 . Step3: In the remaining table, choose the upper left corner cell (R2, C2) with supply 70 and demand 90. Allocate 70 to the cell and cross out row Plant2. The remaining demand at customer 2 would be 90 – 70 = 20 . Step4: In the remaining table, choose the upper left corner cell (R3, C2) with supply 50 and demand 20. Allocate 20 to the cell and cross out Customer 2. The remaining supply at Plant 3 would be 50 – 20 = 30 . Step5: In the remaining table, choose the upper left corner cell (R3, C3) with supply 30 and demand 100. Allocate 30 to the cell and cross out Plant 3. Step6: The only available cell is (R4, C3) with supply 70 and demand 70. Hence, allocate 70 to the cell. As no cells are available, the process of finding BFS is finished. Therefore, the BFS for the given problem is as follows: x 11 =50, x 21 =30, x 22 =70, x 32 =20, x 33 =30, x 43 =70 with z = 50 × 75+30 × 79 + 70 × 73 + 20 × 76 + 30 × 70 + 0 × 70 = 14850 c. Finding an optimal solution for the problem using the transportation simplex: Since the transportation table contains (m+n–1) = 6 basic cells, move to the next step in finding the optimum solution. Here, “m” is the number of rows and “n” is the number of columns. Assume that u 1 = 0 . Also, assume that u i + v j = c i j for all basic variables to find u 1 u 2 ... u m v 1 v 2 ... v n for the current BFS. Obtain the u i ' s and v j ' s for the current BFS. u 1 = 0 u 1 + v 1 = 75 u 2 + v 1 = 79 u 2 + v 2 = 73 u 2 + v 3 = 67 u 3 + v 3 = 70 u 4 + v 3 = 0 By solving the above equations, we get, u 1 = 0 v 1 = 75 u 2 = 4 v 2 = 69 u 3 = 7 v 3 = 63 u 4 = − 63 Now, compute c i j ¯ = u i + v j − c i j for each of the non-basic variable and check whether all c i j ¯ for non-basic variables are positive. If all c i j ¯ of non-basic variables are positive, then the obtained solution is optimum. Observe that x 33 will be the entering variable with the below given value, θ = min ( 50 , 70 , 30 ) = 30 Also, x 21 will be the leaving variable. Continue further in the same way for changing the BFS to reach the optimal solution. The next table will be as shown below: The current solution for the problem is as follows: x 11 =20, x 21 =60, x 22 =40, x 32 =50, x 33 =30, x 43 =70 with z = 20 × 75+60 × 79 + 40 × 73 + 50 × 76 + 30 × 69 + 0 × 70 = 15030 Obtain the u i ' s and v j ' s for the current BFS. u 1 = 0 u 1 + v 1 = 75 u 2 + v 1 = 79 u 2 + v 2 = 73 u 3 + v 2 = 76 u 1 + v 3 = 69 u 4 + v 3 = 0 By solving the above equations, we get, u 1 = 0 v 1 = 75 u 2 = 4 v 2 = 69 u 3 = 7 v 3 = 69 u 4 = − 69 Now, compute c i j ¯ = u i + v j − c i j for each of the non-basic variable and check whether all c i j ¯ for non-basic variables are positive. If all c i j ¯ of non-basic variables are positive, then the obtained solution is optimum. Observe that x 32 will be the entering variable with the below given value, θ = min ( 60 , 50 ) = 50 Also, x 31 will be the leaving variable. The current solution for the problem is as follows: x 11 =20, x 21 =10, x 22 =90, x 31 =50, x 13 =30, x 43 =70 with z = 20 × 75+10 × 79 + 90 × 73 + 50 × 85 + 30 × 69 + 0 × 70 = 15180 Obtain the u i ' s and v j ' s for the current BFS. u 1 = 0 u 1 + v 1 = 75 u 2 + v 1 = 79 u 2 + v 2 = 73 u 3 + v 1 = 85 u 1 + v 3 = 69 u 4 + v 3 = 0 By solving the above equations, we get, u 1 = 0 v 1 = 75 u 2 = 4 v 2 = 69 u 3 = 10 v 3 = 69 u 4 = − 69 For the current BFS, all c i j ¯ ≥ 0 , so an optimal solution is obtained. Thus, the optimal solution to the problem is as follows: x 11 =20, x 21 =10, x 22 =90, x 31 =50, x 13 =30, x 43 =70 The optimal value of the problem is as follows: z = 20 × 75+10 × 79 + 90 × 73 + 50 × 85 + 30 × 69 + 0 × 70 = 15180

Operations Research: Applications and Algorithms

Operations Research: Applications and Algorithms

4th Edition

ISBN: 9780357907818

Author: WINSTON

Publisher: Cengage Learning US

See similar textbooks

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Expert Solution & Answer

bartleby

Trending nowThis is a popular solution!

Check out sample textbook solution

Blurred answer

Chapter 7.6, Problem 6P

Chapter 7, Problem 2RP

Students have asked these similar questions

show work

show work on paper

show work on paper

Chapter 7 Solutions

Operations Research: Applications and Algorithms

Ch. 7.1 - Prob. 1P Ch. 7.2 - Prob. 1P Ch. 7.3 - Prob. 1P Ch. 7.5 - Prob. 1P Ch. 7 - Prob. 1RP Ch. 7 - Prob. 5RP Ch. 7 - Prob. 6RP Ch. 7 - Prob. 10RP Ch. 7 - Prob. 14RP Ch. 7 - Prob. 23RP

Knowledge Booster

Background pattern image

Similar questions

SEE MORE QUESTIONS

Recommended textbooks for you

Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage

Text book image

Operations Research : Applications and Algorithms

Computer Science

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Brooks Cole

Text book image

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

SEE MORE TEXTBOOKS