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 x_s1+x_s2 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 x_2t + x_3t

x_s1 = x₁₂ + x₁₃

x_s2 + x₁₂ = x_2t

x₁₃ = x_3t

0 ≤ x_s1 ≤ 2

0 ≤ x_s2 ≤ 3

0 ≤ x₁₂ ≤ 3

0 ≤ x₁₃ ≤ 4

0 ≤ x_2t ≤ 2

0 ≤ x_3t ≤ 1

 

 

Posted Date: 3/25/2013 2:29:08 AM | Location : United States

Ask an Expert

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

Write your message here..

Related Questions

Building an e-store website in xhtml, The last exercise of each assignment ... The last exercise of each assignment will be continuous from assignment to assignment and will have the goal of building an e-store website by the end of the course. For the fir

Board coloring problem description, Board Coloring Problem Description ... Board Coloring Problem Description In this problem you are given a board in which some of the elements are placed as shown in diagram below. Each element represents a color.

Linux Lab Assignments, I have a linux lab class that consist of 1 lab assig... I have a linux lab class that consist of 1 lab assignment per week for 5 weeks. It is an online virtual lab and is fairly easy, I just don''t have the time.

Microprocessor, what is a microprocessor? types of microprocessors? advanta... what is a microprocessor? types of microprocessors? advantages disadvantages

Advantages of asp.net mvc framework, Advantages of asp.net mvc framework ... Advantages of asp.net mvc framework MVC is a conventional style design that many designers are acquainted with. Some kinds of Web programs will advantage from the MVC structur

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

Namererror, how do u define a letter in python "NameError: name ''r'' is n... how do u define a letter in python "NameError: name ''r'' is not defined"

Shell script to generate the series 1+x + x2+ x3+….+xn, Normal 0 ... Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

Algorithm of sort the given array remove the repeated value, Short Arrays: ... Short Arrays: Array = randi(10,1,randi(6,1,1)+4)-5 This command will generate an array which you should be able to evaluate by hand (and also have your code evaluate for te

Python, please decode the following as it is answer for my assisgnment for ... please decode the following as it is answer for my assisgnment for python: Ñò üOLOc  @ s‚ d „ Z d „ Z g Z xY e oQ e ƒ e d ƒ i ƒ Z e d j oI e d