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

How will you add styles to a document, Question 1 How will you add styles ...

Question 1 How will you add styles to a document? Question2 How will you view XML in different ways? Question 3 Explain various file handling mechanism available in PERL

Capital gain calculator, This assignment is divided into two parts. The goa...

This assignment is divided into two parts. The goal is to write a Java program that calculates capital gain on a stock market, see Lab 7. When a share of common stock of some co

I need engineer with good knowledge of assembly x86 language, I need an eff...

I need an efficient and fast reverse engineer with good knowledge of assembly x86 language, strong reverse engineering skills, IDA Pro (Hex-Rays) to Linux game routine, C, C++ prog

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

Prims algorithm for minimum spanning tree, Implement the Prim's algorithm w...

Implement the Prim's algorithm with array data structure as described in slide 12 of the file 04mst.ppt. Your program should have a runtime complexity of O(n2) and should be as eff

Write a shell script to find the maximum of three numbers, W.A.S.S to find ...

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

Develop a diagram to model functionality, Develop (i) a context diagram, an...

Develop (i) a context diagram, and (ii) a use case diagram to model the following functionalities of an online brokerage house. eBroker is a discount online broker. An account h

Pros and cons of Assembly language, What are the main pros and cons of asse...

What are the main pros and cons of assembly programming language?

Write a program to list the intermediate films sandwiched, We want a progra...

We want a program, a logic, we can list the intermediate films sandwiched between the 2 tapes (from - to) that indicates the user. example: From to

Opening and closing the document object on web page, Although the Document ...

Although the Document object's write()and writeln() methods are part of the DOM, they cannot be used to change content after a Web page has been rendered. You can write code that e

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