Network flows and linear programming 2

Definitions

Network: A network consists of two types of objects: nodes and arcs. The nodes are connected by arcs. Arcs are assumed to be directed.

i.e.

Network Flow Problems: A problem of minimizing the “transportation” cost of moving materials through a network from supply to demand.Total demand must equal to total supply.

i.e.

The network problem can be written as follow:

   maximize c^Tx
   subject to Ax = -b
            x ≥ 0

Network Flows and Linear Programming

Example:

   Xad = a 
   Xbc = b
   Xbe = c
   Xcd = d
   Xde = e
   z = cost

   Minimize z = 108a + 81b +38c + 42d + 70e subject to
   a >= 2
   a <= 2
   -b + c >= -6
   -b + c <= -6
   b + d >= 10
   b + d <= 10
   -a - d + e >= -4
   -a - d + e <= -4
   -c - e >= -2
   -c - e <= -2
   a,b,c,d,e >= 0

   solution : z = 216

Real Life Problem:

There are 3 water suppliers: a, b, c in the district that provide the water for two neighbourhoods: A and B. Neighbourhood A needs 175 tons water per day and B needs 200 tons water per day. Supplier a can provide at most 140 tons per day, supplier b can provide at most 80 tons per day and suppiler c can provide at most 155 tons per day. The distance from a to B is 1050 meters, a to b is 360 meters, b to A is 310 meters, c to b is 880 meters,c to A is 500 meters and c to B is 600 meters. The cost of sending water from supplier to neighbourhood is $1 per ton. What is the minimum cost of this network?

   xaB = a
   xcB = b
   xcb = c
   xab = d
   xbA = e
   xcA = f

   Minimize p = 1050a+600b+500f+880c+360d+310e
   a + b >= 140
   a + b >= 175
   b + c + f >= 155
   e - d - c >= 80
   e + f >= 200
   a,b,c,d,e,f >=0

   solution: z = 167000