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

Write a prolog predicate for a list, Write a Prolog predicate remove_nth(N,...

Write a Prolog predicate remove_nth(N,L1,L2) that is true if list L2 is just list L1 with its Nth element removed. If L1 does not have an Nth element then the predicate should fail

Compare 2 strings, Normal 0 false false false EN-US X...

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

What are relative urls, What are Relative URLS ? When a web browser re...

What are Relative URLS ? When a web browser reads an HTML document, it has a great deal of information about the document. This includes the protocol used to retrieve the docu

Program for connect 4 game on a general board, The classical connect-4 game...

The classical connect-4 game is played on a 67 board, it can in fact be played in any nrRowsnrCols board. In your implementation, the user will specify the number of rows nrRows an

Programs to solve the nonlinear algebraic equations, Introduction Each...

Introduction Each module of the course includes a programming project. However, for Modules 5 and 6 we will do a single project to cover both. The purpose of the programming p

Develop a windows forms application, Develop a Windows Forms Application by...

Develop a Windows Forms Application by creating a new project named "xxxxxxxx" in a new folder named "xxxxxxxxas3" where xxxxxxxx is your student id. You should delete file(s) with

Program to explore page replacement algorithms, Objective: The purpose of ...

Objective: The purpose of this programming project is to explore page replacement algorithms. This can be accomplished by developing a simple simulator that implements various pag

Shell script to check whether user has logged in or not, Normal 0 ...

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

What is multithreaded programming, Question: (i) What is multithreaded...

Question: (i) What is multithreaded programming? Lists the benefits achieved by multithreading your code in a program. (ii) What type of coding should be eliminated when d

Assembly programme , write and compile a simple program in Assembly Languag...

write and compile a simple program in Assembly Language that compute and print student grades for a course.which you can open a file, read from it, and compute the results...using

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