##### Differences

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

 cs-312:hw20.5 [2015/03/06 16:40]ringger [Question 2] cs-312:hw20.5 [2015/03/07 17:52]ringger [Question 2] Both sides previous revision Previous revision 2015/03/07 17:52 ringger [Question 2] 2015/03/06 16:40 ringger [Question 2] 2015/03/06 12:38 ringger [Question 2] 2015/03/06 12:37 ringger 2014/12/31 16:22 ringger 2014/12/31 16:06 ringger created 2015/03/07 17:52 ringger [Question 2] 2015/03/06 16:40 ringger [Question 2] 2015/03/06 12:38 ringger [Question 2] 2015/03/06 12:37 ringger 2014/12/31 16:22 ringger 2014/12/31 16:06 ringger created 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. ​ (I recommend representing the flows through each edge as your variables.) * (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. * (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.