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

Unix, 1. Write a shell script to locate executable files. This script takes...

1. Write a shell script to locate executable files. This script takes a list of file names from the command line and determines which would be executed had these names been given a

Russian peasant, This is Python program I am stuck Modify the Russian peas...

This is Python program I am stuck Modify the Russian peasant multiplication mod n function from class to perform "Russian peasant exponentiation" instead. You can assume that you

Write the html code to bind this xml data, Question: (a) (i) Describe w...

Question: (a) (i) Describe what an XML Data Island is and outline the restrictions of using a Data Island. (ii) The following XML file book.xml is used to keep track of a l

Code a simulation of image compression , Your task will be to code a simula...

Your task will be to code a simulation of image compression based on the approximate low rank structure of the set of image patches. You will write functions .code = my block compr

Multi-targeting .net structure, Support for Multi-Targeting The multi-targe...

Support for Multi-Targeting The multi-targeting function of Vision Facilities allows you specify the particular edition or account of the .NET Structure that is required for your p

Create a directory, The ?rst task in the project is to develop a sane syste...

The ?rst task in the project is to develop a sane system to store change logs and versions of ?les. The simplest approach is to create a "dot" directory in the location of the ?le

Shell script to print left traingle, Normal 0 false false f...

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

Program to create multithreaded calculator, Multithreaded Calculator I...

Multithreaded Calculator In this Lab, you will be implementing a simple multithreaded calculator. Our calculator will accept expressions as infix notation text strings consist

Design and implement schemasusing xml schema, You are to build a Schema in ...

You are to build a Schema in XML Schema Language that will be used to support the development of the new central course information management system and other supporting applicati

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