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
My programming class uses Virtual Logic (not virtual studio) to learn how to program algorithms but we don''t get any assistance form the instructor so I am at a loss as to how I a

How to make game in pascal language

can you provide some assignments for JSP learning

Write a function named prob2.m which creates and returns an N×N identity matrix. An identity matrix is a square matrix with values of one on the main diagonal and zeros in all off-

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

Define a higher order version of the insertion sort algortihm. That is define functions insertBy :: Ord b => (a->b) -> a -> [a] -> [a] inssortBy :: Ord b => (a->b) -> [a] ->

You are to Use ASCII operations to design an IA-32 assembly language program which will do addition and subtraction on positive integers of any length represented in characters. T

Many applications require entering a number from a button and then the device counts that number down.  If it is a 2 digit number it can be stored in a single register.  If it is l

Design an object definition named Pet, which should have the following fields: name: The name field holds the name of a Pet type: The type field holds the type of anima

W.A.S.S to find the maximum of three numbers Program # W.A.S.S to find the maximum of three numbers echo "Enter three No.:" read no1 read no2 read no3 if test $no1 -gt $n