# Solution for Transportation Problems | My Assignment Tutor

1Sherri [email protected] on Chapter 7, Operations Research: Applications & Algorithms, 4th edition, by Wayne L. WinstonCopyright © 2004 Brooks/Cole, a division of Thomson Learning, Inc.Finding Basic FeasibleSolution for TransportationProblems2IntroductionIn contrast to other Linear Programming problems, a balancedTP with 𝑚𝑚 supply points and 𝑛𝑛 demand points is easier tosolve, even though it has 𝑚𝑚 + 𝑛𝑛 constraints.The reason is, if a set of decision variables (𝑥𝑥𝑖𝑖𝑖𝑖’s) satisfy all butone constraint, the decision variable values will satisfy that lastconstraint automatically.3Basic feasible solutionsThere are three basic methods to find a basic feasiblesolution for a balanced transportation problem:1. North-West Corner2. Minimum Cost (also called Least Cost)3. Vogel’s41. North-West Corneri. Begin in the upper left corner of the tableau and set 𝑥𝑥11 aslarge as possible (the minimum of 𝑠𝑠1 and 𝑑𝑑1).ii. Amend the total amount of supply/demand remaining andcross off the row/column where the remaining amount is zero.iii. Move to the upper left corner of the tableau that is notcrossed off and repeat the steps above for 𝑥𝑥𝑖𝑖𝑖𝑖 as appropriateuntil you reach the bottom right corner.Basic feasible solutions5North-West Corner example.5 6 23 5 2 3 3 26 2X 5 2 3Basic feasible solutionsi. Set 𝑥𝑥11 = 3ii. Cross offcolumn 1as demandis met.6 32 X6 2X 3 2 3 323 X32X X 2 3Basic feasible solutionsiii. Move to 𝑥𝑥12i. Set 𝑥𝑥12 = 2ii. Cross off row 1 assupply is exhausted.iii. Move to 𝑥𝑥22i. Set 𝑥𝑥12 = 3ii. Cross off column2 demand is met.7 3232 X12X X X 3 32321 XX2X X X 2Basic feasible solutionsiii. Move to 𝑥𝑥23i. Set 𝑥𝑥23 = 2ii. Cross off column3 demand is met.iii. Move to 𝑥𝑥24i. Set 𝑥𝑥24 = 1ii. Row 2 is complete,supply is exhausted.8We have a bfs: 𝑥𝑥11 = 3, 𝑥𝑥12 = 2, 𝑥𝑥22 = 3, 𝑥𝑥23 = 2, 𝑥𝑥24 = 1, 𝑥𝑥34 = 2 323212 XXXX X X XBasic feasible solutionsThe Northwest Corner method is easy and gives a quick bfs,however does not utilise shipping costs. Thus, it can yield asolution with a high total cost.iii. Move to 𝑥𝑥34 and set to 2. End92. Minimum CostThis method uses shipping costs to find a bfs and will generallygive a lower cost than the North-West corner method.To start, find the decision variable 𝑥𝑥𝑖𝑖𝑖𝑖 with the lowest cost.i. Assign its largest possible value (minimum of 𝑠𝑠𝑖𝑖 and 𝑑𝑑𝑖𝑖 ).ii. Amend the total amount of supply/demand remaining andcross off the row/column where the remaining amount is zero.iii. From the remaining uncrossed decision variables, find thelowest cost and repeat i., ii., iii. until all cells are crossed off.Basic feasible solutions10Minimum Cost exampleStart by selecting the cell with minimum cost. 235621353846 5101512 8 4 6Basic feasible solutions11 2356218353846 12 X 4 65 215i. Assign its largest possible value, 8ii. Amend the total amount of remaining supply from s2 and cross off col 2.Basic feasible solutions12 23562218353846 5 X1510 X 4 6iii. Lowest cost = 𝑥𝑥21i. Set 𝑥𝑥21 = 2ii. Cross off row 2 as supply exhausted, amend column 1 to 10Basic feasible solutions13 253562218353846 X X155 X 4 6iii. Lowest remaining cost is 𝑥𝑥11i. Set 𝑥𝑥11 = 5ii. Amend column 1 to 5 and cross off row 1 as supply exhausted.Basic feasible solutions14 2535622183535846 X X10X X 4 6i. Set 𝑥𝑥31 = 5ii. Cross off column 1 and amend row 3 to 10.iii. Lowest remaining cost is 𝑥𝑥31Basic feasible solutions15 25356221835358446 X X 6X X X 6Basic feasible solutionsiii. Lowest remaining cost is 𝑥𝑥32i. Set 𝑥𝑥32 = 4ii. Cross off column 3 and amend row 3 to 6.16Assign 6 to last cell.The bfs is: 𝑥𝑥11 = 5, 𝑥𝑥21 = 2, 𝑥𝑥22 = 8, 𝑥𝑥31 = 5, 𝑥𝑥33 = 4, 𝑥𝑥34 = 6 253562218353584466 X X XX X X XBasic feasible solutions3. Vogel’s methodi. Compute a penalty for each row and column. This is thedifference between the two smallest shipping costs in the r/c.ii. Find the row/column with the largest penalty and find thebasic variable which has the smallest shipping cost in that r/c.iii. Assign the highest possible value to that variable, then crossout the r/c and amend values as in the previous methods.Return to first step and repeat until tableau complete.17Basic feasible solutions18Vogel’s method examplei. Compute the penalties.Supply Row Penalty 678158078 DemandColumn Penalty 15-6=9 80-7=73 78-8=707-6=178-15=6315 5 51015Basic feasible solutions19Supply Row Penalty 6758158078 DemandColumn Penalty 15-6=9 _ 78-8=708-6=278-15=6315 X 5515Basic feasible solutions ii.Find the row/column with the largest penalty and find the basic variablewhich has the smallest shipping cost in that r/c. iii. Assign the highest possible value to that variable, then cross-out the r/cand amend values. Return to first step: i. Calculate penalties20Supply Row Penalty 67585158078 DemandColumn Penalty 15-6=9 _ __ _15 X X015Basic feasible solutions ii.Find the row/column with the largest penalty and find the basic variablewhich has the smallest shipping cost in that r/c. iii. Assign the highest possible value to that variable, then cross-out ther/c and amend values. Return to first step: i. Calculate penalties21Supply Row Penalty 607585158078 DemandColumn Penalty _ _ __ _15 X XX15Basic feasible solutions ii.Find the row/column with the largest penalty and find the basic variablewhich has the smallest shipping cost in that r/c. iii. Assign the highest possible value to that variable, then cross-out ther/c and amend values.22The bfs found is: 𝑥𝑥11 = 0, 𝑥𝑥12 = 5, 𝑥𝑥13 = 5, 𝑎𝑎𝑛𝑛𝑑𝑑 𝑥𝑥21 = 15Supply Row Penalty 60758515158078 DemandColumn Penalty _ _ __ _X X XX XBasic feasible solutions23QuestionFind a basic feasible solution using the Northwest CornerMethod, Minimum Cost Method and Vogel’s Method 3148510208123607101153030451510 24AnswerFind basic feasible solution using Northwest Corner Method 310148510202084012360710511515103030451510 COST = 96525AnswerFind basic feasible solution using Minimum Cost Method 310148510205845123106071510115153030451510 COST = 640AnswerFind basic feasible solution using Vogel’s Method 310148510205845123106071510115153030451510 COST = 640END OF LECTURE

QUALITY: 100% ORIGINAL PAPER – NO PLAGIARISM – CUSTOM PAPER