A residential moving company needs to move a family from city $1$ to city $12$ in the following figure where the numbers on the arcs represents the driving distance in miles between cities. $45918037062142043023345440813654343554152405575152901076842311712312$ Network flow model for the moving company problem a$)$ Formulate an LP model to find the shortest path from city $1$ to city $12$ for this problem. b$)$ Create a spreadsheet model for this problem and solve it using Solver. What is the optimal solution? c$)$ Suppose the moving company gets paid by the mile and, as a result, wants to determine the longest path from city $1$ to city $12.$ What is the optimal solution? d$)$ Now suppose travel is permissible in either direction between cities $6$ and $9.$ Describe the optimal solution to this problem.