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

Describe the hypermedia and hypertext, Question: (a) How does HTML all...

Question: (a) How does HTML allow you to: (i) turn an image into a clickable hyperlink? Include code to switch off the default border (ii) convert the above hyperlink i

Simple corba program, You are working in charge of a group of programmers a...

You are working in charge of a group of programmers at a software company. Your task is to assess and research CORBA and to produce a report to be given to the programmers detailin

Create procedures for accessing the root, (a)  Create procedures for access...

(a)  Create procedures for accessing the root, left subtree and right subtree, and also mutators for changing the root, left subtree and right subtree of an avl argument. (b) Wr

Windows card space, Windows Card Space Windows Card Space (codenamed Info C...

Windows Card Space Windows Card Space (codenamed Info Card), is Windows now-canceled customer application for the Identification Met system. Card Place is an instance of a class of

Java exception handling, Expertsmind brings you unique solution in java as...

Expertsmind brings you unique solution in java assignments Exception Handling An exception is an issue that appears during the performance of an application. An exception

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

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

Lalr parser - xml table output, LALR Parser: Rule Table - Contains de...

LALR Parser: Rule Table - Contains definitions of production rules within the grammar. Attributes: Count - Number of production rules in the table Child items:

Prolog assignment, I have constantly been emailing to get the task i had pa...

I have constantly been emailing to get the task i had paid for to be done correctly but no replies from anyone. Not even one acknowledging my emails. Been phoning all the way from

Jsp project, Eclipse Jsp Project. I am making a a project on my website and...

Eclipse Jsp Project. I am making a a project on my website and i was making a help support page on which the user can submit their question and the question is saved to a text file

Calculate the sum of negative elements of specified column, Write a program...

Write a program that will generate 25 DWORD values in the range from +/-50 representing a two dimensional array of size 5 x 5. It should then display the array as a table (5 x 5) b

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