Consider the following linear program:

(LP #1) Minimize 4x1 + 5x2 − 3x3 + 4x4 + x5 + 2x6 + 9x7 + 3x8

subject to x1 + x2 + x3 = 1

x4 = x1 + x5

x2 = x5 + x6 + x7

x8 = x4 + x6

x3 + x7 + x8 = 1

x1 ≤ 1

x2 ≤ 1

x3 ≤ 1

x4 ≤ 1

x5 ≤ 1

x6 ≤ 1

x7 ≤ 1

x8 ≤ 1

x1, x2, x3, x4, x5, x6, x7, x8 ≥ 0.

4 Part A: Show that this linear program is equivalent to a min-cost flow problem. Be sure to specify all aspects of the min-cost flow problem (exogenous flows, arc costs, arc flow upper bounds, and arc flow lower bounds).

Part B: Make a rigorous argument that your min-cost flow problem from Part A is equivalent to a shortest path problem. Be sure to specify all aspects of the shortest path problem (start and destination nodes, arc costs).

Part C: Solve your from Part B using an algorithm.