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
How do you print triangles using for loops and if statements

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

In this assignment, you will design a program to perform the following task: Calculate the total price to purchase all the components required to build a state-of-the-art gaming c

PLEASE HELP ME ORACLE PROGRAMING TRIGGER

1.  A function that produces the Collatz sequence and counts the number of terms. 2.  A main function that calculates interesting values about the Collatz sequence. 1.The Col

Explain the applet Element ? Applets are embedded in web pages by using the and tags. The APPLET element is same to the IMG element. Like IMG APPLET references a source fil

Hi, Can any of you, tell me how to use Included Applications?

basic steps involved in spreadsheet developement

Problem 1 Explain the Booch Methodology 2 Why does every interaction diagram need a written description? Explain 3 Explain the five core workflows of the Unified Process

I need to write code to compute matrix multiplication without using built in function.