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
This is the programming language of the Web. It is mainly used for validating forms. JavaScript & Java can be associated to each other. There exist several other differences betwee

Object-oriented languages Languages that support OOP features can be classified into the following two categories: 1.    Object-based programming languages, and 2.      O

find value of nCr using function

Real Distinct and 1 Double Eigenvalue with 1 Eigenvector From the real eigenvalue/vector pair, l 1 and ?h 1 , we find one solution, e l1 t ?h 1 By our work in the 2x

CSCI 3380 Project 1 For Mano’s Computer design, we have the following flowchart for fetch and decode phases: Please write the code to simulate the computer to

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

Please write a program declaring a variable x as the type int, and use the scanf function to input an integer to initialize the value of x. Then, your program will print the follow

You are to write a program which will answer a pair of questions for squares, triangles, circles and ellipses. A square is defined by its lower left corner (SLLx,SLLy), and the len

Term project (you should code a function), demonstrate it to the class and a very breief report (one or two pages) describing what you did. You determine your project (could be imp

One of the main strengths of the Perl programming language are its powerful text manipulation features. In this assignment, you will put them to use for writing a Perl program that