7. (10 points) In the following figure, if the numbers next to each link in the

Question

7. (10 points) In the following figure, if the numbers next to each link in the figure denote the flow capacities. The maximum flow problem to find maximum flow from node 1 to node 6 can be formulated by a linear program as follows: max z=xo X12-X23 + X24 x24-x43 +x46 s.t. x X12 x13 + %24 35 X35- X56 X12 S 6 x13 S 2 x23 3 1 x24 S 3 335 S 7 x43 S 3 X46 3 2 X12, X13, X23-X24, X35, X43, X46, X56 0 where the decision variable xiy denotes the flow on the link (i,j) and the decision variable xo indicates the maximum flow that can be sent from node 1 to node 6. Using the duality table of page 1 to find the dual problem of this one. (Hint: for first 6 constraints, please move the right-hand-side decision variables to left-hand- side before performing the duality). SIE340 Final Exam- Summer I 2017 Page 10 of 12

Explanation / Answer

Rewrite the constraints by moving the decision variables from RHS to LHS

x0 - x12 - x13 = 0

x12 - x23 - x24 = 0

x13 + x23 + x43 - x35 = 0

x24 - x43 - x46 = 0

x35 - x56 = 0

x46 + x56 - 0 = 0

Dual form of the problem is following:

Min w = 0y1 + 0y2 + 0y3 + 0y4 + 0y5 + 0y6 + 6y7 + 2y8 + 1y9 + 3y10 + 7y11 + 3y12 + 2y13 + 7y14

s.t.

y1 - y6 >= 1

-y1 + y2 + y7 >= 0

-y1 + y3 + y8 >= 0

-y2 + y3 + y9 >= 0

-y2 + y4 + y10 >= 0

-y3 + y5 + y11 >= 0

y3 - y4 + y12 >= 0

-y4 + y6 + y13 >= 0

-y5 + y6 + y14 >= 0

All variables unrestricted

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.