Instructions: Consider the problem and its explanation below. For this problem, implement it in Microsoft

Excel and solve it to optimality. For your peace of mind, the optimal solution is included in this document.

The Maximum Flow Problem: The objective in a maximum flow problem is to determine the maximum

amount of flow $($vehicles$,$ messages, fluid, etc.$)$ that can enter and exit a network system in a given period of time.

In this problem, we therefore attempt to transmit flow through all arcs of the network as efficiently as possible.

The amount of flow is limited due to capacity restrictions on various arcs of the network. For example,

highway types limit vehicle flow in a transportation system. The maximum or upper limit on the flow in an arc

is referred to as the flow capacity of the arc. Even though we do not specify capacities for the nodes, we assume

that the flow out of a node is equal to the flow into a node, for all nodes in the network $($this is different from

shortest path$).$

Consider a simplified version of the north$-$south interstate highway system passing through Cincinnati Ohio.

Arc capacities $($in thousands of vehicles per hour$)$ are denoted by labels for each arc.

The modeling $$trick$$ for this type of problem is the addition of an uncapacitated arc which flows from the exit

node to the start node.

Our goal is to maximize flow over this artificial arc. Maximizing the $$flow$$ from node $7$ to node $1$ is equivalent to

maximizing the number of cars that can get through the north$-$south highway system passing through Cincinnati.

Model:

Let xij $=$ the amount of flow from node i to node j

Then we have:

max x$71(1)$

subject to: $(2)$

x$71=$ x$12+$ x$13+$ x$14(3)$

x$12+$ x$32=$ x$23+$ x$25(4)$

x$13+$ x$23=$ x$32+$ x$34+$ x$35+$ x$36(5)$

x$14+$ x$34=$ x$46(6)$

x$25+$ x$35+$ x$65=$ x$56+$ x$57(7)$

x$36+$ x$46+$ x$56=$ x$65+$ x$67(8)$

x$57+$ x$67=$ x$71(9)$

x$12<=5(10)$

x$13<=6(11)$

x$14<=5(12)$

x$23<=2(13)$

x$25<=3(14)$

x$32<=2(15)$

x$34<=3(16)$

x$35<=3(17)$

x$36<=7(18)$

x$46<=5(19)$

x$56<=1(20)$

x$57<=8(21)$

x$65<=1(22)$

x$67<=7(23)$

$(1)$ is the objective function. Constraints $(2)-(9)$ enforce conservation of flow $($inflow $=$ outflow$)$ at all nodes.

Constraints $(10)-(23)$ enforce capacities on each arc$/$highway$.$ Note that there is no capacity constraint for arc

$7-1.$

Optimal Solution: The optimal solution of this model is as follows. The optimal objective value is identical to

the flow on arc $7-1$ and has a value of $14.$

Arc Value Arc Value

$1-233-63$

$1-364-65$

$1-455-60$

$2-305-77$

$2-536-51$

$3-406-77$

$3-537-114$