Name:

Number:

ISE$222$

Final Exam, Fall $2023$

Closed book, closed notes,

Duration: $110$ minutes

Question $1(20$ Points$)$

Telephone calls from New York $($node $1)$ to Los Angeles $($node $6)$ are transported as follows: The call is first sent to either Chicago $($node $2)$ or Memphis $($node $3),$ then routed through Denver $($node $4)$ or Dallas $($node $5),$ and finally sent to Los Angeles. In the graph on the right, the number of phone lines joining each city pair $(i,j)$ is indicated on the arc connecting cities i and $j.$ The objective is to determine the maximum number of calls that can be sent from New York to Los Angeles at any given time.

a$)$ Which network problem covered in class can be used to solve the problem above? $(2$ points$)$

b$)$ Formulate an LP that can be used to determine the maximum number of calls that can be sent from New York to Los Angeles at any given time. $(18$ points$)$

Use the decision variables provided below in your formulation: $x_{ij}$: number of calls sent from node $i$ to node $j,$ where $i,$jin$\{1,2,3,4,5,6\}$

Objective function:

Constraints: