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

Ws-addressing, WS-Addressing, WS-Reliable Texting and WS-Security WCF tools... WS-Addressing, WS-Reliable Texting and WS-Security WCF tools many innovative Web solutions (WS) expectations such as WS-Addressing, WS-Reliable Texting and WS-Security. With the di

Create application for a book store, You need to create a simple applicatio... You need to create a simple application for the Note Plus book Store. The interface for the application is shown below:   REQUIRED: 1)  Create all necessary contro

Java.., create a program that can determine the number of students that are... create a program that can determine the number of students that are doing their final year for a particular program (e.g. BCOM Information Systems), calculate the required credits

Matlab, want to do an image-mean. but image is and mean is so an error ... want to do an image-mean. but image is and mean is so an error showing Error using ==> minus Number of array dimensions must match for binary array op. wat to do?

How do you find the complexity of an algorithm, How do you get the complexi... How do you get the complexity of an algorithm? What is the relation b/w the time & space complexities of an algorithm? Justify your answer with an example.

Looping, You are required to develop a program that calculates the charges ... You are required to develop a program that calculates the charges for DVD rentals, where current release cost RM3.50 and all others cost RM2.50. If a customer rents several DVDs, e

Write a program to draw the truck , Write a program to draw the truck follo... Write a program to draw the truck following figure. The program should buttons to provide When the truck runs left wheels must rotate in the correct direction. Rotating whe

Flowchart and Pseudocode using Control Breaks, Shemrock Inc. is a brake pad... Shemrock Inc. is a brake pad manufacturing company. This company uses raw materials, such as carbon powder, iron, ash, and resin. It wants to develop an inventory management system

Develop a socket program in unix, Develop a socket program in UNIX/Linux th... Develop a socket program in UNIX/Linux that uses (i) TCP as the transport protocol and  (ii) UDP as the transport protocol for transferring  a short message between a client and  s

Create xpath expressions and xslt templates, Consider the following schema ... Consider the following schema (DTD) and sample instance document: name    ID      #REQUIRED spouse  IDREF   #IMPLIED job     CDATA   #IMPLIED > ]>