Write the dual of the max flow problem, Programming Languages

Assignment Help:

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

 

 


Related Discussions:- Write the dual of the max flow problem

Differentiate between high level and low level languages, The languages use...

The languages used in the module are of a type known as high-level languages. There is another set of languages known as low-level languages. (a) Differentiate between high-leve

Virtual Logic and Arrays, My programming class uses Virtual Logic (not virt...

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

Need help to convert a site to nationbuilder, Need help to convert a site t...

Need help to convert a site to NationBuilder This project is to transfer the site- (podiotools.com) which is by now responsive HTML and is currently setup in Adobe Business Cata

Program to produce the given output , Given a file named maze1.txt whose co...

Given a file named maze1.txt whose contents is 1 0 2 2 1 2 3 0 3 2 2 1 2 0 2 2 3 0 1 1 3 1 0 0 2 0 3 0 0 1 2 0 3 2 2 0 1 2 3 2 1 0 0 1 1 0 0 0 your program when run as a.out

Enter no of hours days months years contains pattern , Normal 0 ...

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

Decision table, If it is a weekday and it is not a holiday, then you go to ...

If it is a weekday and it is not a holiday, then you go to work. However, if it is a weekday and it is a holiday, then what you do depends on the weather. If it is raining, you pla

What is hiding a method? explain, Question 1 Explain the three traits of O...

Question 1 Explain the three traits of Object Oriented Programming Question 2 Write a note on (a) Assignment Operators                             b) Bitwise Operators.

OOPs Concepts. Explain Object-oriented programming, OOPS Concepts Object-or...

OOPS Concepts Object-oriented programming (OOP) is a computer science term used to characterize a programming language that began development in the 1960’s. The term ‘object-orient

Statistical parametric mapping, A large offshore accommodation barge is to ...

A large offshore accommodation barge is to be converted into a floating luxury hotel.  It will be connected to a single point mooring buoy (SPM) in a beautiful inland loch where th

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd