In the following figure, if the numbers next to each link in the figure denote the flow capacities. The maximum flow problem to find maximum flow from node to node can be formulated by a linear program as follows:

where the decision variable denotes the flow on the link (,) and the decision variable 0 indicates the maximum flow that can be sent from node to node . Using the duality table in page 1 to find the dual problem of this one. (Hint: for first 6 constraints, please move the right-hand-side decision variables to left-handside before performing the duality).

3 10 10 2 8 6 S t 10 10 2 4 9 max z = Xo s. t. Xo = Xs1 + Xs2 Xs1 = x12 + x13 + X14 Xs2 + x 12 = X24 X13 + X43 = X3t X14 + X24 = X43 + x4t X3tXt = xo Xs1