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.