(a) You have water containers A, B, C, D with respectively a, b, c and d...

Transcribed Image Text:

(a) You have water containers A, B, C, D with respectively a, b, c and d units of water. You need to move water from these containers to canisters 1, 2, 3, 4 where for each i = 1, 2, 3, 4, canister i receives between l and u units of water. Moreover, no water goes from A to 1, no water goes from B to 2, no water goes from C to 3, and no water goes from D to 4. Under these conditions you want to maximize the amount in water received in canisters 1,2,3 minus the amount in canister 4. Formulate this problem as a minimum cost flow problem. HINT: Do not write the Linear Program, describe the digraph, capacities, etc ... (b) You are using a software package that allows you to solve minimum cost flow problems where the lower bounds are all 0 (for every arc e the flow xe is between 0 and some capacity ue). Unfortunately, you have to solve a minimum cost flow problem with lower bounds le 0. Your friend Jake is selling you, for $100, an upgraded software package that can solve minimum cost flow problems with arbitrary lower bounds. Should you take Jake's offer? (a) You have water containers A, B, C, D with respectively a, b, c and d units of water. You need to move water from these containers to canisters 1, 2, 3, 4 where for each i = 1, 2, 3, 4, canister i receives between l and u units of water. Moreover, no water goes from A to 1, no water goes from B to 2, no water goes from C to 3, and no water goes from D to 4. Under these conditions you want to maximize the amount in water received in canisters 1,2,3 minus the amount in canister 4. Formulate this problem as a minimum cost flow problem. HINT: Do not write the Linear Program, describe the digraph, capacities, etc ... (b) You are using a software package that allows you to solve minimum cost flow problems where the lower bounds are all 0 (for every arc e the flow xe is between 0 and some capacity ue). Unfortunately, you have to solve a minimum cost flow problem with lower bounds le 0. Your friend Jake is selling you, for $100, an upgraded software package that can solve minimum cost flow problems with arbitrary lower bounds. Should you take Jake's offer?