Write the dual of the max flow problem, Programming Languages

1. Write the dual of the above max-?ow problem.

2. Solve both problems with AMPL, and for each print the values of the vari- ables and the values of the dual variables (if a problem has a constraint c1, its dual value can be displayed with the command "display c1.dual;"). Verify that the numbers correspond between primal and dual, and that the optimal solution of the primal and the dual is in accordance with duality.

3. Show the minimum cut that results from solving the dual problems.

4. Consider replacing the objective function in the max cut problem with max xs1+xs2 which gives an equivalent formulation of the max-?ow prob- lem. How does the dual formulation change? Explain why it is equivalent to the ?rst dual problem.

max x2t + x3t

xs1 = x12 + x13

xs2 + x12 = x2t

x13 = x3t

0 ≤ xs1 ≤ 2

0 ≤ xs2 ≤ 3

0 ≤ x12 ≤ 3

0 ≤ x13 ≤ 4

0 ≤ x2t ≤ 2

0 ≤ x3t ≤ 1

1574_Write the Dual of the Max Flow Problem.png

 

 

Posted Date: 3/25/2013 2:29:08 AM | Location : United States







Related Discussions:- Write the dual of the max flow problem, Assignment Help, Ask Question on Write the dual of the max flow problem, Get Answer, Expert's Help, Write the dual of the max flow problem Discussions

Write discussion on Write the dual of the max flow problem
Your posts are moderated
Related Questions
Write a program to handle a book collection. The data on each book might be title, author, publication date, book number and  cataloging details. Allow for adding or deleting books

We want a program that will allow us to print a "grade list" of the students in a class. The program should loop, asking for a name, midterm score, and final score. It should th

1. Write the dual of the above max-?ow problem. 2. Solve both problems with AMPL, and for each print the values of the vari- ables and the values of the dual variables (if a p

how to get horizontal motion vectors field with quiver ?

Write a program to show ten buttons with five possible colors: red, green, orange, yellow, blue. When the user clicks on a button, its color must advance to the next color, or go b

I need to finish my game project within two weeks using XNA. Would you guys can help me to finish it? Thank you

Write a Prolog predicate has_duplicates(L) that is true if list L contains duplicated elements (that is at least 2 copies of an element). For instance: ?- has_duplicates([a,e,b,

How to i write a car rental program in jgrasp

Develop a socket program in UNIX/Linux that uses (i) TCP as the transport protocol and  (ii) UDP as the transport protocol for transferring  a short message between a client and  s

3d Interpolation using matlab from x,y, and z coordinates in a csv file and reading them after that interpolating them..