Consider the following linear program: Min 2X_13 + 4X_34 + 2X_24 + 3 X_32 - 2x_2

Question

Consider the following linear program: Min 2X_13 + 4X_34 + 2X_24 + 3 X_32 - 2x_21 subject to X_32 - x_21 = 2 X_24 + X_21 - X_32 = 1 X_32 + X_34 - X_13 = 0 X_24 + X_34 = 3 X_21 lessthanorequalto 1 X_24 lessthanorequalto 3 X_13 lessthanorequalto 2 X_32 lessthanorequalto 2 X_34 lessthanorequalto 1 X_13, X_24, X_32, X_21, X_34 greaterthanorequalto 0 a) By drawing the appropriate network, show that this linear program can be interpreted as representing the objective and flow constraints for a min-cost flow mode a) b) Use the min-cost augmenting flow algorithm to solve your model from part (a). You may omit the details of your shortest path calculations, but otherwise show all work.

Explanation / Answer

variable new name value X12 x 2 X34 y 1 X24 z 2 X32 q 1 X21 w 0 equation becomes p = 2x + 4y + 2z + 3q -2w Optimal Solution: p = 15; x = 2, y = 1, z = 2, q = 1, w = 0 Table #1 ========================================================== x      y      z      q      w      s1     s2     s3     s4     s5     s6     s7     s8     s9     s10    s11    s12    s13    p              ========================================================== 1      0      0      0      -1     1      0      0      0      0      0      0      0      0      0      0      0      0      0      2       0      0      1      -1     1      0      1      0      0      0      0      0      0      0      0      0      0      0      0      1       -1     1      0      1      0      0      0      1      0      0      0      0      0      0      0      0      0      0      0      0       0      1      1      0      0      0      0      0      1      0      0      0      0      0      0      0      0      0      0      3       0      0      0      0      1      0      0      0      0      1      0      0      0      0      0      0      0      0      0      1       0      0      1      0      0      0      0      0      0      0      1      0      0      0      0      0      0      0      0      3       1      0      0      0      0      0      0      0      0      0      0      1      0      0      0      0      0      0      0      2       0      0      0      1      0      0      0      0      0      0      0      0      1      0      0      0      0      0      0      2       0      1      0      0      0      0      0      0      0      0      0      0      0      1      0      0      0      0      0      1       1      0      0      0      -1     0      0      0      0      0      0      0      0      0      -1     0      0      0      0      2       0      0      1      -1     1      0      0      0      0      0      0      0      0      0      0      -1     0      0      0      1       -1     1      0      1      0      0      0      0      0      0      0      0      0      0      0      0      -1     0      0      0       0      1      1      0      0      0      0      0      0      0      0      0      0      0      0      0      0      -1     0      3       -2     -4     -2     -3     2      0      0      0      0      0      0      0      0      0      0      0      0      0      1      0       Table #2 ========================================================== x      y      z      q      w      s1     s2     s3     s4     s5     s6     s7     s8     s9     s10    s11    s12    s13    p              ========================================================== 0      0      0      0      0      1      0      0      0      0      0      0      0      0      1      0      0      0      0      0       0      0      1      -1     1      0      1      0      0      0      0      0      0      0      0      0      0      0      0      1       0      1      0      1      -1     0      0      1      0      0      0      0      0      0      -1     0      0      0      0      2       0      1      1      0      0      0      0      0      1      0      0      0      0      0      0      0      0      0      0      3       0      0      0      0      1      0      0      0      0      1      0      0      0      0      0      0      0      0      0      1       0      0      1      0      0      0      0      0      0      0      1      0      0      0      0      0      0      0      0      3       0      0      0      0      1      0      0      0      0      0      0      1      0      0      1      0      0      0      0      0       0      0      0      1      0      0      0      0      0      0      0      0      1      0      0      0      0      0      0      2       0      1      0      0      0      0      0      0      0      0      0      0      0      1      0      0      0      0      0      1       1      0      0      0      -1     0      0      0      0      0      0      0      0      0      -1     0      0      0      0      2       0      0      1      -1     1      0      0      0      0      0      0      0      0      0      0      -1     0      0      0      1       0      1      0      1      -1     0      0      0      0      0      0      0      0      0      -1     0      -1     0      0      2       0      1      1      0      0      0      0      0      0      0      0      0      0      0      0      0      0      -1     0      3       0      -4     -2     -3     0      0      0      0      0      0      0      0      0      0      -2     0      0      0      1      4       Table #3 ========================================================== x      y      z      q      w      s1     s2     s3     s4     s5     s6     s7     s8     s9     s10    s11    s12    s13    p              ========================================================== 0      0      0      0      0      1      0      0      0      0      0      0      0      0      1      0      0      0      0      0       0      0      0      0      0      0      1      0      0      0      0      0      0      0      0      1      0      0      0      0       0      1      0      1      -1     0      0      1      0      0      0      0      0      0      -1     0      0      0      0      2       0      1      0      1      -1     0      0      0      1      0      0      0      0      0      0      1      0      0      0      2       0      0      0      0      1      0      0      0      0      1      0      0      0      0      0      0      0      0      0      1       0      0      0      1      -1     0      0      0      0      0      1      0      0      0      0      1      0      0      0      2       0      0      0      0      1      0      0      0      0      0      0      1      0      0      1      0      0      0      0      0       0      0      0      1      0      0      0      0      0      0      0      0      1      0      0      0      0      0      0      2       0      1      0      0      0      0      0      0      0      0      0      0      0      1      0      0      0      0      0      1       1      0      0      0      -1     0      0      0      0      0      0      0      0      0      -1     0      0      0      0      2       0      0      1      -1     1      0      0      0      0      0      0      0      0      0      0      -1     0      0      0      1       0      1      0      1      -1     0      0      0      0      0      0      0      0      0      -1     0      -1     0      0      2       0      1      0      1      -1     0      0      0      0      0      0      0      0      0      0      1      0      -1     0      2       0      -4     0      -5     2      0      0      0      0      0      0      0      0      0      -2     -2     0      0      1      6

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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