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

determine if dna sequence is periodic or not, A string s is said to be per...

A string s is said to be periodic with a period α, if s is α k for some k > 2. (Note that α k is the string formed by concatenating k times.) A DNA sequence s is called a tande

Python , Return a new picture with each pixel''s color values made up of 80...

Return a new picture with each pixel''s color values made up of 80% of the color values of the corresponding pixel in the first picture and 20% of the color values of the

Program to find the largest value in an array, 1. Write out a detailed plan...

1. Write out a detailed plan for a program to find the largest value in an array that is smaller than a ceiling C. For example, suppose the array has the values {4, 14, 11, 100, 6}

Php / mysql issues, Im having problems with my php / mysql code. I am tryin...

Im having problems with my php / mysql code. I am trying to make it so it looks for an asset Number and if it is in the shop if the asset is in the database but is not in the shop

Irenecereno, Using the concept of structures, write a program to assign pas...

Using the concept of structures, write a program to assign passenger seats in an airplane. Assume a small airplane with seats numbered as follows: 1 A B C D 2 A B C D 3 A

Software problem program, On December 27, 2011, Seymour Gravel, at the urgi...

On December 27, 2011, Seymour Gravel, at the urging of his wife, Mary Walford, has brought you his preliminary figures for his business. Seymour carries on a business writing and e

Depth estimation from a single view camera, i doing a project about depth e...

i doing a project about depth estimation, i have done some research, and i used the block matching algorithm to get the motion vectors from the image sequences, i now have the prob

Script shell to display lines of a file in reverse order, Normal 0 ...

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

Artificial intelligence, Describe briefly how you might program a computer ...

Describe briefly how you might program a computer to exhibit fear or sorrow.

Algorithm and data structure, Man, i''m having quite a problem with this ex...

Man, i''m having quite a problem with this exercise. Even googled for Roman multiply table concept. I just don''t get it. Multiply two numbers given in Roman figures. For instan

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