$(50$ pts$.)$ Each of the subproblems in the following question will be referencing this main Problem Statement Find the route from New York City to San Francisco which takes

the fewest number of days to traverse. That is$,$ find the shortest path between nodes $s$ and $t$

on the graph in Figure $2.$

a Formulate the Problem as an LP$.$ You will be doing a single simplex pivot on this LP later,

so it will be worth writing it out fully $($along with the generic formulation$).$ Note: For this

problem, for the set of edges consider the directed version of the graph like the one in Figure

Therefore, do not consider Subtour elimination constraints in your model formulation.

Figure $3$: A directed version of the graph in Figure $2.$ It only has the edges which are relevant to

this problem.

b Solve this problem in Excel Solver. Report your solution here and submit your implemen$-$

tation as an exoel file. $(25$ pts$.)($Bonus portion$)$

c Solve the problem by hand using Dijkstra Algorithm. Your solution here should agree with

the one you found in Problem $2.$ Mention what method you used and record all your steps.

d Pivot the linear program from part a$)$ into the standard form for the basis that corresponds

to the solution that you found in parts b$)$ and c$).$ Does this standard form support the

optimality of your solution?

Note: This is a pretty large LP and you definitely do not need to do more than one pivot.

Just jump straight to the final basis which you should be able to derive from the optimal

solution you have already found.

mathematical problem. You will be using several methods to solve it$.$

Preface

The Pony Express Starting in early April of $1860,$ The Pony Express was a private

mail service which specialized in transporting letters from the New York all the way to San

Francisco and back. They used a pretty novel staging method to deliver these letters in as few

as ten days! This revolutionized east$-$west coast communication and was somewhat popular

until the first transcontinental telegraph line was completed only $18$ months later.

igure $2$: A rough map of major cities in the US circa $1861$ weighted with the number of days

ight take a group of staged riders to traverse each edge.

You and your computer have been have been transported back in time to September $1861.$

As a fan of the Pony Express, you know that they have been operating at a loss for several

months and that the first transcontinental telegraph line will put them out of business by the

end of next month. Saddened by this knowledge, you set out to change the past by optimizing

the route used by the Pony Express.