Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Last revision Both sides next revision
cs-312:hw20.5 [2015/03/06 12:37]
ringger
cs-312:hw20.5 [2015/03/06 16:40]
ringger [Question 2]
Line 12: Line 12:
 === Question 2 === === Question 2 ===
 Linear Programming and the Maximum Flow Problem: ​ Consider the directed graph $G=(E,​V)$. ​ Without loss of generality, let $s$ be the source vertex and $t$ be the sink vertex in $V$. For each edge $(u,v)\in E$, let $c_{uv}$ denote the capacity of that edge. Now, formulate the '''​general'''​ maximum flow problem (not a specific instance) as a linear programming problem as follows: Linear Programming and the Maximum Flow Problem: ​ Consider the directed graph $G=(E,​V)$. ​ Without loss of generality, let $s$ be the source vertex and $t$ be the sink vertex in $V$. For each edge $(u,v)\in E$, let $c_{uv}$ denote the capacity of that edge. Now, formulate the '''​general'''​ maximum flow problem (not a specific instance) as a linear programming problem as follows:
-(a) First, define the variables. +(a) First, define the variables. 
-(b) Second, use those variables to formulate all of the necessary elements of a linear program in algebraic terms, and make sure that your formulation is in standard form up to step #1.+(b) Second, use those variables to formulate all of the necessary elements ​(i.e., objective function and constraints) ​of a linear program in algebraic terms.
  
cs-312/hw20.5.txt · Last modified: 2015/03/07 17:52 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0