.The Network Simplex Method The Min Cost Flow LP: Let network G = (N,A) be given
ID: 372704 • Letter: #
Question
.The Network Simplex Method
The Min Cost Flow LP: Let network G = (N,A) be given, with supplies/ demands bi, i N, costs cij (positive or negative), and capacities uij (possibly ) (i,j) A. Recall the description of the Min Cost Flow Problem: min z(x) = (i,j)A cijxij (NP) jA(i) xij jB(i) xji = bi i N 0 xij uij (i,j) A
Since this is a linear program, it can be solved using the Simplex Method. The Network Simplex Method is a special implementation of the Simplex Method which makes use of the network structure to signicantly streamline the computational eort.
Example:
ij c ij u ,
i b
7
4 1
24
5
6
3
3,$3
2,$1
2,$1
15,$8
5,$2
2
3
4,$4
3
6,$2
1,$1
NetworkLP:
minz=x13+2x21+2x24+8x32+4x35+3x54+x64+2x65 Node1:x13x21=1 Node2:x21+x24x32=2 Node3:x13+x32+x35=3 Node4:x24x54x64=7 Node5:x35+x54x65=3 Node6:x64+x65=4 x132x212x245x325x354x543x641x656
Matrix-Vector Form of (NP)
min cx Nx = b 0 x u where N is the node-arc incidence matrix for G and c, b, and u are the vectors of costs, supplies/demands, and capacities, respectively.
Assumptions:
(A1) G is connected (in the undirected sense) (A2) iN bi = 0 Fact: If the second assumption is not satised, the equality system Nx = b is inconsistent. If it is satised, then at least one row is redundant and can be removed.
It will turn out that the choice of the row to remove is irrelevant, so we will remove the row corresponding to some arbitrary root node s. Let Ns be the resulting matrix.
Spanning Trees
Spanning tree: Set of edges which connects every pair of nodes of G and has no cycles (both in the undirected sense).
Properties of Spanning Trees (from rst assignment):
(a) every spanning tree has exactly n1 arcs; (b) every spanning tree has at least two end nodes (nodes with only one adjacent arc); (c) every pair of nodes in a spanning tree is connected by a unique path; (d) addition of any arc to a spanning tree results in a graph containing exactly one cycle.
Bases for Ns
A basis for Ns is any matrix BT consisting of set T of n1 columns of Ns so that for any choice of bi, i Ns, there is a unique solution to the (n1)×(n1) system () BTx = b (Note that this is equivalent to saying the BT is a nonsingular matrix.) The corresponding variables are called basic variables.
Basis Lemma: Let T be a set of arcs of G, and let BT be the corresponding set of columns of Ns. Then BT is a basis for Ns if and only if T is a spanning tree for G.
Proof of the Basis Lemma
First suppose that T is not a spanning tree. Case 1: Suppose thatT is not connected, that is there is some node t that is not connected to s by a path. Consider the righthand-side b with bt = 1 and bi = 0, i N {s,t}. Then clearly there can be no solution to (). Case 2: Suppose that T contains a cycle W : v0,e1,v1,...,vk1,wk,vk = v0 with ei = (vi1,vi) or (vi,vi1). Now let bi = 0 for all i. For any , consider the solution x having xij = + (i,j) a forward arc of C (i,j) a backward arc of C 0 (i,j) not on C for any this clearly satises (), and so () has more than one solution. In either case, () will not have a unique solution, so that this direction of the lemma is proven.
Computing a Basic Solution
Now suppose that T is a spanning tree. To complete the Basis Lemma, we need to show how to compute unique ow values for x on the arcs of T which will satisfy the ow equations. For any set of ow values xij, (i,j) A, recall the imbalance of i is dened ei = bi jA(i) xij + jB(i) xji
Algorithm Compute-Flows Initialize: Set ei = bi, i A and S = T. while S = do Let i = s be an end node of S, with a = (i,j) or (j,i) the associated unique arc of S adjacent to i.If a = (i,j) assign xij = ei, and if a = (j,i) assign xji = ei. Remove a and i from S and add ei to ej. end while.
Explanation / Answer
Problem 1: (50 points) Given the network shown below, where the labels next to the nodes are the supplies/demand and the labels on the edges are the (costs, capacities). We wish to minimize the cost of this transshipment problem. Find a feasible spanning tree for this problem. Given this spanning tree, use the network simplex algorithm to determine the dual prices for this spanning tree and the associated reduced costs of all non-basic arcs. Is the spanning tree optimal? If not, indicate the entering arc, the leaving arc and how much flow would be increased/decreased on this arc and perform one pivot. If it is optimal, prove that it is by stating the optimality conditions, i.e., show that there are no violating non-basic arcs. a. b. c. 4 $5, 5 $2,4 $6, 3 $4,4 4 S12 b 3, 4 $6, 3 $3,2 $2,3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.