1
$\begingroup$

I want to know what is the relation between network flow min cost problem and max flow problem with simplex method linear programming, such as primal dual and complementary slackness and how can i convert the primal to dual. I'm trying to find on internet,but I can't find one. Please also tell me if there is some source that give some example problem or good book about linear programming network ?

A flow network is a directed graph $G = ( V , E ) $ with a source vertex $s ∈ V$ and a sink vertex $t ∈ V $ where each edge $( u , v ) ∈ E $ has capacity $c ( u , v ) > 0 $, flow $ f(u,v) \ge 0$ and cost $a ( u , v ) $ with most minimum-cost flow algorithms supporting edges with negative costs. The cost of sending this flow along an edge $ (u,v)$ is $f ( u , v ) ⋅ a ( u , v ) $

The problem requires an amount of flow $d$ to be sent from source s s to sink t

The definition of the problem is to minimize the total cost of the flow over all edges:

$ \sum_{(u,v) \in E} a(u,v) \cdot f(u,v) $ with the constraints

Capacity constraints: $f ( u , v ) ≤ c ( u , v ) $

Skew symmetry: $f ( u , v ) = − f ( v , u ) $

Flow conservation: $∑ w ∈ V f ( u , w ) = 0 for all u ≠ s , t $

Required flow: $ \,\sum_{w \in V} f(s,w) = d \text{ and } \sum_{w \in V} f(w,t) = d$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.