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 x_s1+x_s2 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 x_2t + x_3t

x_s1 = x₁₂ + x₁₃

x_s2 + x₁₂ = x_2t

x₁₃ = x_3t

0 ≤ x_s1 ≤ 2

0 ≤ x_s2 ≤ 3

0 ≤ x₁₂ ≤ 3

0 ≤ x₁₃ ≤ 4

0 ≤ x_2t ≤ 2

0 ≤ x_3t ≤ 1

 

 

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

Ask an Expert

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

Write your message here..

Related Questions

For loops, How do you print triangles using for loops and if statement How do you print triangles using for loops and if statements

Shell script to check a given number is palindrome or not, Normal 0 ... Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

Cmis 102, In this assignment, you will design a program to perform the foll... 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

Oracle , PLEASE HELP ME ORACLE PROGRAMING TRIGGER PLEASE HELP ME ORACLE PROGRAMING TRIGGER

Learning when and how to use a while loop, 1.  A function that produces the... 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, Explain the applet Element ? Applets are em... 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

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

Excel, basic steps involved in spreadsheet developement basic steps involved in spreadsheet developement

Explain the booch methodology, Problem 1 Explain the Booch Methodology ... 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

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