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

Leave a Reply

Your email address will not be published. Required fields are marked *