MATH 251 ACTIVITY 5:Setup and Excel solution of Minimum –cost Flow Network Models
WHY:Minimum-cost flow networks allow a solution for the transshipment problem and other extensions of the transportation problem. Networks generally allow us to create good models of multiple interconnections among a finite set of objects/people/projects/locations, and are an important addition to the modeler’s toolkit.
LEARNING OBJECTIVES:
1.Work as a team, using the team roles.
2. Learn how to set up & optimize network models for transshipment problems
3.Further develop skill in modeling.
CRITERIA:
1.Success in completing the exercises.
2.Success in working as a team
RESOURCES:
1.Your class notes on network models (10/3)
2.The NETWORK.xls template from Lawrence & Pasternak (available on the Blackboard site)
3.Your text section 4.3 (and p. 236) and the example given below
4.Microsoft Excel, running on the campus computer network
5.45 minutes
PLAN:
1.Select roles, if you have not already done so, and decide how you will carry out steps 2 and 3
2.Read through the model and work through the exercises given here - be sure everyone understands all results. Hand in your solutions and email me the Excel workbook (as an attachment).[send a copy to each member of the team, also to use for added work].
3.Assess the team's work and roles performances and prepare the Reflector's and Recorder's reports including team grade.
MODEL:
We saw (on Tuesday) the set-up of a transshipment model as a capacitated network model.:
There are two factories which produce a product: F1 has production capacity 80 units, F2 has capacity 70 units.
There are two Stores at which the product is sold – S1 has a demand for 60 units, S2 has a demand for 90 units
There is a Distribution center D which can receive product from the factories and send it on to the stores. Product is not stored, created, or sold at the distribution center – it must send out exactly the same amount it receives.
The following transportation links are available for moving the product:
From F1 to S1capacity 60 unitscost $700 per unit
From F1 to D capacity 50 units,cost $300 per unit
From F2 to Dcapacity 50 unitscost $400 per unit
From F2 to S2capacity 50 units cost $900 per unit
From D to S1capacity 50 unitscost $400 per unit
From D to S2capacity 50 unitscost $400 per unit
Our goal is to ship the production to the stores to meet the demand at minimum cost. This problem is balanced, if it were not, we would need aa dummy demand node or a dummy supply node or– with $0 cost on links to (or from) the dummy.
Our network model looks like :
One feasible solution is :
From F1 to S160 units
From F1 to D20 units
From F2 to D20 units
From F2 to S250 units
From D to S1nothing
From D to S240 units
Cost is $117,000
To seek the minimum-cost solution, we turn to L&P’s Excel template for Transshipment in the NETWORK.xls workbook (see p. 236 in the text)
To use this, we need to organize our data a bit differently.
First we need a list of nodes, each with supply (available) and demand (desired)
Our situation:
Node namesupplydemand
F180 0
F2 70 0
D00 [Note that D neither creates nor uses the product]
S1060
S2090
The template will number these nodes (in this case from 1 to 5)
Then we need a list of arcs, for each we must indicate which node it comes from and which node it goes to, the unit cost for the arc, and the capacity of the node – the program requires that we use the numbers supplied by the template in describing the nodes.
Our arc data:
FromTo CostCapacity
F1S170060
F1D30050
F2D40050
F2S290050
DS140050
DS240050
Once these are entered, we call the solver (which has the relationships entered) and click solve. The result:
NODE NAME / NODE # / SUPPLY / DEMAND / FROM / TO / COST / CAPACITY / FROM / TO / FLOW
SLACK / 100
F1 / 1 / 80 / 1 / 4 / 700 / 60 / 1 / 4 / 60
F2 / 2 / 70 / 1 / 3 / 300 / 50 / 1 / 3 / 20
D / 3 / 2 / 3 / 400 / 50 / 2 / 3 / 30
S2 / 4 / 60 / 2 / 5 / 900 / 50 / 2 / 5 / 40
S3 / 5 / 90 / 3 / 4 / 400 / 50 / 3 / 4
3 / 5 / 400 / 50 / 3 / 5 / 50
So we know that the least-cost shipping plan is :
F1 sends 60 units directly to S1 and 20 units to D
F1 sends 40 units directly to S2 and 30 units to D
D sends 50 units to S2
This problem was balanced, so the question of a dummy supply or destination never came up. As long as total supply is as large as total deman the spreadsheet model will work properly; if the total supply is less than the total demand, a dummy supply must be added to make up the shortage – and must have 0-cost links to all the intermediate and demand nodes.
If there are no capacities on the arcas (the capacity is unlimited in each arc) the spreadsheet model needs a large capacity for each arc – using the total supply or anything larger will work.
EXERCISE:
The Makonsel Company both produces goods and sells them at retail outlets. After production, the goods are stored in the company’s two warehouses until they are needed by the retail outlets. Trucks are iused to transport the goods from the two plants to the warehouses and from the warehouses to the three retail outlets. The following table shows each plant’s monthly output , the shipping costs per truckload sent to each warehouse, and the maximum amount (in truckloads) that it can ship per month to each warehouse.
Unit shipping costShipping capacity
ToWarehouse 1Warehouse 2Warehouse 1Warehouse 2Output
Plant 1$425$560125150200
Plant 2$510$600175200300
For each (RO) the next table shows its monthly demand (truckloads), its shipping cost per truckload from each warehouse, and the maximum amount (in truckloads) that can be shipped per month from each warehouse.
Unit shipping costShipping capacity
ToRO1RO2RO3RO1RO2RO3
Warehouse 1$470$505$490100150100
Warehouse 2$390$410$44012515075
Demand150200150
The company wants a distribution plan to minimize total shipping cost.
a.) Draw a network model of the problem – show demands, capacities, costs.
b.) Solve using the “Transshipment” sheet in the NETWORKS.xls workbook available via blackboard (and on the CD that came with your text). Write out the solution (amount shipped in each link)
c.) The demand at Retail Outlet 1 has increased from 150 units per month to 200 units per month. Now what is the best shipping plan to meet as much of the demand as possible and at lowest cost? Which retail outlet (or outlets) have unmet demand? [You need to add a dummy source to represent the unmet demand ]
NOTE: You can duplicate the Excel page in the workbook and then add data entries – you do not need to re-enter the rest of the model. You no not need to draw the new network (though you may).
CRITICAL THINKING QUESTIONS:(answer individually in your journal)
1.What would have to be changed if we had profits, or some kind of benefits, on the links, rather than costs?
2.How do you suppose we might adjust the model if the intermediate nodes had limits (capacities) on the intermediate nodes?
SKILL EXERCISES:(This is the assignment due next class) Be sure you give the solutions in words, and answer all questions. Text p. 239 (Ch 4) #3 (set capacities for links ata 8500 – or above), 12 (this is a repeat to see how straight transportation problem works in this setting) 17 (set all transportation costs at $1 per unit – really interested in whether there is a feasible solution) 49bc, 50a [These are on the CD that comes with the text [PDF files> additional problems > addprobsch04.pdf] - capacities in links are not limited, so set all above the number of cars]]