MATH 251 ACTIVITY 1: - Saint Mary's College



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 S1 capacity 60 units cost $700 per unit

From F1 to D capacity 50 units, cost $300 per unit

From F2 to D capacity 50 units cost $400 per unit

From F2 to S2 capacity 50 units cost $900 per unit

From D to S1 capacity 50 units cost $400 per unit

From D to S2 capacity 50 units cost $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 a a 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 S1 60 units

From F1 to D 20 units

From F2 to D 20 units

From F2 to S2 50 units

From D to S1 nothing

From D to S2 40 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 name supply demand

F1 80 0

F2 70 0

D 0 0 [Note that D neither creates nor uses the product]

S1 0 60

S2 0 90

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:

From To Cost Capacity

F1 S1 700 60

F1 D 300 50

F2 D 400 50

F2 S2 900 50

D S1 400 50

D S2 400 50

Once these are entered, we call the solver (which has the relationships entered) and click solve. The result:

NODE INPUT |  |ARC INPUT |  |SOLUTION |TOTAL COST= |116000 | |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 cost Shipping capacity

To Warehouse 1 Warehouse 2 Warehouse 1 Warehouse 2 Output

Plant 1 $425 $560 125 150 200

Plant 2 $510 $600 175 200 300

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 cost Shipping capacity

To RO1 RO2 RO3 RO1 RO2 RO3

Warehouse 1 $470 $505 $490 100 150 100

Warehouse 2 $390 $410 $440 125 150 75

Demand 150 200 150

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]]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download