MSIS 685: Linear Programming
Lecture 11
Minimal Network Flow Problem
11/24/98
Scriber: Yu Xia
Instructor: Farid Alizadeh
Transportation Problem
Example:
Problem:
, ,
, , ,
:
Solution:
1)Use Northwest corner method to find the initial solution:
:
Dual:
2)Change the base of primal:
Dual:
3)Change the primal base:
This is a degenerate solution
The dual:
4)The primal:
The dual:
5)The primal:
The dual:
6)The primal:
The dual:
7)The primal:
The dual:
8)The primal:
The dual:
9)The primal
The dual:
Conclusion:
Optimal base of the primal:
Minimal Cost Flow Problem
A graph can be represented by. N is the set of nodes, A is the set of arcs.
: Supplying nodes
: Transportation nodes
: Demanding nodes
: Arc
Transshipment Problem:
Definitions:
Walk: ()…
Path: A path is a walk with no vertices visited more than once.
Circuit: A circuit is a walk where
Cycle: A cycle is a circuit, and it is a path if is taken away.
In cycle number of edges equals number of vertices. In path number of edges equals number of vertices minus 1.
Strongly Connected: A directed network G=(N, A) is strongly connected if there exits a path between any pair of nodes.
Weakly Connected: A network is weakly connected if it is connected when treated as an undirected network.
Forest: A forest is a network with no cycles if treated as undirected
Tree: A tree is a weakly connected forest
Degree of Node: Degree of Node (i) is the number of arcs with one end pointing to i.
Indegree of Node: Indegree of Node (i) is the number of arcs with the form (k, i).
Outdegree of Node: Outdegree of Node (i) is the number of arcs with the form (i, k).
Degree of Node (i)= Indegree of Node (i)+ Outdegree of Node (i)
Lemma: A tree with n nodes has n-1 arcs.
Proof:
By induction:
1) The lemma is true for 1-node and 2-node trees.
2) Consider n-node tree:
Claim: Every tree that has more than one node has at least one node of degree 1.
Use contradiction: There is a path P between node 1 and node 2. If the degree of each node of a tree is not less than one, then it is possible to find another path between node 1 and 2, and none of the arcs in this path is identical to any arc in P.
Remove that degree 1 node and the arc, we obtain a tree has n-1 nodes.
Minimal cost flow problem can be presented as
: Incidence Matrix (: the number of nodes, : the number of arcs)
Example:
For any feasible network, the conditionmust be satisfied.
If the rank of the incidence matrix is k, then the graph has m-k parts.
Spanning Tree: T is a spanning tree of , if T=, , and T is a tree.
Lemma: For every (undirected) tree, there is a way to label nodes with 1, 2 … m such that:
a)Node labeled 1 is arbitrary.
b)For each node labeled , there is exactly one edgewhere .
To find the label like this use:
Method 1: breadth-first search.
Example:
1)
2)
3)
Get rid of the first row, the incidence matrix is an upper triangular matrix and no zero in diagonal.
Method 2:
Start from the leaf, and mark it m.
Take it and the associated arc away, and then mark m-1 to the leaf of the new tree.
…
For a minimal cost flow problem, a basic feasible solution corresponds to a spanning tree. One tree differs from another with one arc.