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

Version control system, Version Control is a critical tool in development a...

Version Control is a critical tool in development and production environments that allows a user to make snapshots of working con?gurations or code. In this assignment, you will de

Animals, Let us say we have a list of 10 animal objects called "animals" in...

Let us say we have a list of 10 animal objects called "animals" in Alice. Write the code to move them forward synchronously by 1 meter.

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

CGI mailer Script, i neeed an CGI Script that send mass emails i need this...

i neeed an CGI Script that send mass emails i need this input fields Sender Name: Sender Email: Subject: Message: choose (HTML Or text ) , by default HTML Emails and send bu

Write a program to compute the standard deviation, Write three functions, s...

Write three functions, statistics, average, and sD as follows. The statistics function returns no value and has six parameters: four scores followed by their average and standard d

Assembly Language, need a program of any multiplication algorithm implement...

need a program of any multiplication algorithm implemented in assembly language x86 without using mul command

Shell script to compare that given two files are same or not, Normal 0 ...

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

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 > ]>

Create a reservation system, Villa La Fourche Ltd is a small family busines...

Villa La Fourche Ltd is a small family business situated in the East Coast of Mauritius, more precisely Trou d'eau Douce.   The compound comprises of 6 independent villas, each of

Advantages of java stored procedures, Advantages of java stored procedures ...

Advantages of java stored procedures Transactions Although a saved process contains SQL orders, once collected it will socialize with SQL Hosting server very diversely from

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