Question

Chicken feed is transported by trucks from three silos to tour farms. Some of the silos cannot ship directly to some farms. The capacities of the other routes are limited by the number of trucks available and the number of trips that can be made daily. The following table shows the daily amounts of supply at the silos and demand at the farms (in thousands of pounds) and the capacities of the routes. Page: 3 of 3 Farm 1 Farm 2 Farm 3 Farm4 Capacity (x1.000 pounds) 30 5 O40 0 0 590 100 40 30 40 20 Silo 1 Silo 2 Silo 3 Demand (x1,000 pounds)200060 20 20 200 We would like to find a transportation scheme that satisfies the most demand uioo an appropriate network flow model (a) [1 point] What kind of network flow model is this? Note: Your answers should not be transportation or transshipment (b) [4 points] Draw the network graph showing all necessary parameters and their values, and explain what they are. (c) [10 points] Formulate the corresponding network flow model

Answer 1

(a)

Total demand = 200+10+60+20 = 290 (x1000 pounds)

Total supply = 20+20+200 = 240 (x1000 pounds)

Total demand is greater than supply.

Objective is to satisfy the most demand.

Therefore, this can be formulated as a Maximal network flow model

---------------

(b) The network graph is following:

100 200 10 40 200 3 60 200 200 40 4 90 40 Farms Slios

Number on each arc shows the capacity (maximum flow) along that arc. Objective is to find the maximal flow from source node 1 to destination node 9

Nodes 2,3,4 represent the three silos and nodes 5,6,7,8 represent the four farms.

----------------

(c) Network flow model is following:

Let Xij = flow from node i to node j

Max X12+X13+X14

s.t.

X12-X25-X26-X27-X28=0

X13-X35-X36-X37-X38=0

X14-X45X46-X47-X48=0

X25+X35+X45-X59=0

X26+X36+X46-X69=0

X27+X37+X47-X79=0

X28+X38+X48-X89=0

X12<=20

X13<=20

X14<=200

X25<=30

X26<=5

X27<=0

X28<=40

X35<=0

X36<=0

X37<=5

X38<=90

X45<=100

X46<=40

X47<=30

X48<=40

X59<=200

X69<=10

X79<=60

X89<=20

Xij >= 0