Mathematical Description of NPSC

The NETFLOW Procedure

Mathematical Description of NPSC

If a network programming problem with side constraints has n nodes, a arcs, g nonarc variables, and k side constraints, then the formal statement of the problem solved by PROC NETFLOW is

: min {c^T x + d^T z}
subject to: F x = b
: $H x + Q z \geq, =, \leq r$
: $l \leq x \leq u$
: $m \leq z \leq v$

where

c is the a x 1 objective function coefficient of arc variables vector (the cost vector)

x is the a x 1 arc variable value vector (the flow vector)

d is the g x 1 objective function coefficient of nonarc variables vector

z is the g x 1 nonarc variable value vector

F is the n x a node-arc incidence matrix of the network, where

F_i,j = -1: if arc j is directed toward node i
F_i,j = 1: if arc j is directed from node i
F_i,j = 0: otherwise

b is the n x 1 node supply/demand vector, where

b_i = s: if node i has supply capability of s units of flow
b_i = -d: if node i has demand d of units of flow
b_i = 0: if node i is a transshipment node

H is the k x a side constraint coefficient matrix for arc variables, where H_i,j is the coefficient of arc j in the ith side constraint

Q is the k x g side constraint coefficient matrix for nonarc variables, where Q_i,j is the coefficient of nonarc j in the ith side constraint

r is the k x 1 side constraint right-hand-side vector

l is the a x 1 arc lower flow bound vector

u is the a x 1 arc capacity vector

m is the g x 1 nonarc variable value lower bound vector

v is the g x 1 nonarc variable value upper bound vector

Chapter Contents
Previous
Next
Top