Name:______

Network Flow optimization

Many poor rural areas have trouble getting clean drinking water. Suppose your company has just drilled a well in location “A” that can produce 10 thousand gallons of safe water per day. You must use trucks to transport allof the water to a distant village “D” via a road network like this:

/ B / <=6
$3 / $10
<=8 / $4
A / <=7 / D
<=15 /
$7 / <=5
$2
C

Each road has a cost per thousand gallons, and a maximum capacity (in thousand gallons). For example, the road from A to B costs $3 per thousand gallons sent that way, and it can’t take more than 8 thousand gallons per day. Our decision variables are the amount of water to send via each road; we will call the variables AB, AC, BC, BD, CD.

Here are some suggested solutions. If there is something wrong with a solution, write a sentence saying what’s wrong, and write a constraint that would prevent it and other similar constraints to prevent other similar problems.

  1. AB=10, AC=0, BC=0, BD=10, CD=0
  1. AB=2, AC=2, BC=0, BD=2, CD=2
  1. AB=6, AC=4, BC=3, BD=6, CD=4
  1. AB=4, AC=6, BC=-2,BD=6, CD=4

Write a formula that is your objective function:

Write the overall LP here, in mathematical formulas

(for example, minimize 3x+2y

s.t. 4x+1y <= 10, etc., keep it in nice columns!)

Now write the numbers and descriptions you need in this Excel-like sheet, or type them directly into Excel if you have it handy.

AB / AC / BC / BD / CD

Follow-up questions:

  1. How would you change your LP if location B needed 2 thousand gallons, and C needed 3 thousand gallons, and D needed 5 thousand gallons?
  1. How would you change your LP to find the minimum-cost route through the network for one thousand gallons?
  1. Suppose your well at “A” improves and can now supply as much water as you might want. How would you change your LP to route water to get as much as possible to D?

AB / AC / BC / BD / CD
8 / 2 / 3 / 5 / 5
capa limits: / 8 / 15 / 7 / 6 / 5
minimize / 3 / 7 / 4 / 10 / 2 / 110
s.t.
flow cons. / 1 / 1 / 0 / 0 / 0 / 10 / = / 10 / A
-1 / 0 / 1 / 1 / 0 / -3.1E-12 / = / 0 / B
0 / -1 / -1 / 0 / 1 / -7.5E-11 / = / 0 / C
0 / 0 / 0 / -1 / -1 / -10 / = / -10 / D
capa / 1 / 0 / 0 / 0 / 0 / 8 / <= / 8 / AB
0 / 1 / 0 / 0 / 0 / 2 / <= / 15 / AC
0 / 0 / 1 / 0 / 0 / 3 / <= / 7 / BC
0 / 0 / 0 / 1 / 0 / 5 / <= / 6 / BD
0 / 0 / 0 / 0 / 1 / 5 / <= / 5 / CD