Question

Consider the following linear program: Minimize z = 3x12 + 2x13 + 5x14 + 2x41 + x23 + 2x24 + 642 + 4x34 + 4x43. subject to: s 8, x12 x23 -x24 + x42 Х34-Х13-Х23-Х43 s 4, x14 +x34 +x24 x42 x42 - x43 25, all xiy 20. a) Show that this is a network problem, stating it in general minimum-cost flow form. Draw the associated network and give an interpretation to the flow in this network.

Answer 1

a) Network problem can be formulated in general minimum-cost flow form as below:

Min $\sum$cij*Xij, where cij is the cost per unit to go from i to j, and Xij is the flow quantity from node i to j

s.t.

$\sum$Xij - $\sum$Xki <= Si , for each i, where j is the set of inflow nodes terminating at i and k is the set of outflow nodes originating from j and Si is the net supply capacity at node i

$\sum$Xij - $\sum$Xki >= Di , for each i, where j is the set of inflow nodes terminating at i and k is the set of outflow nodes originating from j and Di is the net demand at node i

all Xij >= 0

The given linear program is the same form.

Associated network for the given model is following:

4 2 2 6 4 4