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
In analytical geometry, a convex polygon can be represented by the Cartesian coordinates of its vertices, x and y. Assume such data of a polygon are stored in a file called "vertic

All programs have to be done in console application. Program 1, 2 and 3 are due on 2/11/12 Program 4, 5, and 6 are due on 2/18/12 Program 7, 8, and 9 are due on 2/25/12 Program 10

Problem: This assignment is about deleting nodes from the binary search tree. You need to use given sequence to construct a binary search tree and then delete some nodes from

1.  Develop HTML code to create a Web page with the red background and title "My First Page" in any other color. 2.  Develop an HTML document with details of your name, telephon

The program presents mainframe contains two button new user, existing user PART ONE: CLICKING ON NEW USER New window appear contains: text field represent username,

Write a Perl program that uses a hash structure. The program should use a larger number of operations (100 or more) on this hash. To do that, use a random number generator to creat

Write a program that will allow the user to input the corners of a triangle. The program will draw small yellow circles for each input point, then draw the triangle and calculate t


Question : (a) Many systems provide support for both user threads and kernel threads, resulting in different multithreading models. What are the two differences between user

How to read datasets in multiple text files in an non interactive program?