Chapter 6 Network Flow Programming Methods 高等作業研究

高等作業研究
高等作業研究(一)
Chapter 6
Network Flow Programming Methods
Chapter 6 Network Flow Programming Methods
高等作業研究
TRANSPORTATION PROBLEM(TP)
The problem is to find the optimal
distribution plan for shipments from
sources to destinations that minimizes
the total transportation cost.
Chapter 6 Network Flow Programming Methods
高等作業研究
TP
Chapter 6 Network Flow Programming Methods
高等作業研究
• feasibility property—
 s = d
i i
j
j
• All instances of the traditional TP can be modified so
that this requirement is satisfied by simply adding
either a dummy source with index m + 1 if demand
exceeds supply, or a dummy destination with index n
+ 1 if supply exceeds demand. Letting Δ be the
excess, we set sm+1 = in the first case and d n+1 = in
the second case. In addition, the corresponding cost
coefficients are set equal to zero—i.e., either c m 1, j =
0 for all j or c i,n 1 = 0 for all i
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
LP Formulation
m
 c x
• Minimize
s.t.
i 1 j1
n
x
j1
i 1
ij
ij
ij
 si
,i=1,2,…,m
(1)
ij
 dj
,j=1,2,…,n
(2)
m
x
n
x ij  0
,i=1,2,…,m; j=1,2,…,n
Chapter 6 Network Flow Programming Methods
高等作業研究
Transportation Simplex Method
• The m + n equations are linearly
dependent.
• The primal problem has n + m constraints,
one of which is redundant. A basic
solution for this problem is determined by
a selection of n + m - 1 independent
variables.
• Figure 6.3 shows a basic solution.
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
Chapter 6 Network Flow Programming Methods
高等作業研究
• The cells in the tableau are said to be
dependent and do not form a basis if it is
possible to trace a closed path through them.
• Figure 6.4 depicts a collection of dependent
cells marked by x and the closed path that
connects them.
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Dual LP Formulation
• Let ui be the dual variable corresponding to Equ. (1)
• Let vj be the dual variable corresponding to Equ. (2).
• Max
m
s u  d v
i 1
s.t.
n
i
i
j1
j
u i  v j  c ij
j
, i = 1,..., m and j = 1,..., n
Note: ui and vj are unrestricted in sign for all i, j
Chapter 6 Network Flow Programming Methods
高等作業研究
• Let wij=cij-ui-vj for all i, j
• The complementary slackness property states
that for every basic primal variable the
corresponding dual constraint must be satisfied
as an equality— u i  v j  c ij or w ij  0 for
every basic variable xij.
Chapter 6 Network Flow Programming Methods
高等作業研究
• Because of the redundant primal constraint,
one of the dual variables can be arbitrarily set
equal to zero, and the others can be determined
by solving the resulting equations.
• By construction, we ensure that the primal
solution is feasible. If all the dual constraints
are satisfied for the dual solution, both the
primal and dual solutions are optimal. The
condition for dual feasibility is
u i  v j  c ij or w ij  0 for all nonbasic cells
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Initial Basic Feasible Solution
• Northwest Corner Rule: The initial solution in Figure
6.3 was obtained by using this rule.
• Vogel's Method :For each uncrossed row, compute
the difference between the smallest cost and the
second-smallest cost. Do the same for all uncrossed
columns. Select the row or column with the largest
difference. The rule is to choose the uncrossed cell in
the selected row or column with the smallest cost.
Chapter 6 Network Flow Programming Methods
高等作業研究
Vogel’s Method
Chapter 6 Network Flow Programming Methods
高等作業研究
Russell's Method
• For each uncrossed row and column, we first
find the following.
u i = value of the largest uncrossed cost, in row i
v = value of the largest uncrossed cost, in column j
Then, for each uncrossed cell we compute
j
 ij  c ij - u i - v j
The rule is to choose the uncrossed cell with
the most negative value of  ij (smallest value)
Chapter 6 Network Flow Programming Methods
高等作業研究
Russell’s Method
Chapter 6 Network Flow Programming Methods
高等作業研究
Assignment Problem (AP)
• A special case of the TP arises when all the
sources have one unit of supply and all the
destinations have one unit of demand.
• For the model to be balanced, the number of
sources must equal the number of destinations.
Call this number n. Common applications
include assigning n workers to n tasks or
assigning n jobs to n machines.
Chapter 6 Network Flow Programming Methods
高等作業研究
• The same procedures used to solve the transportation
problem can be used to solve the assignment problem.
• Based on its special structure, however, several
highly efficient algorithms have been devised for the
AP. For example, the Hungarian Method.
• In practice, large-scale transportation and assignment
problems are generally solved with network simplex
codes.
Chapter 6 Network Flow Programming Methods
高等作業研究
SHORTEST PATH PROBLEM
• The problem is one of finding a collection of
arcs that constitutes the shortest path on a
directed network of m nodes and n arcs from a
specified node s, called the source, to a second
specified node t, called the destination or sink .
• It is always possible to convert a (partially)
undirected network into a directed one by
replacing each undirected edge e(i, j) of length
L(i, j) with two directed arcs (i, j) and (j, i), each
of length L(i, j).
Chapter 6 Network Flow Programming Methods
高等作業研究
SHORTEST PATH PROBLEM
A closely related problem is to find the set of
shortest paths from the source node to all other
nodes in the network. This shortest path tree
problem is solved with very little additional
difficulty.
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Dijkstra's Algorithm
• Assume that all arc lengths are nonnegative.
• The algorithm uses a set S, called the "set of solved
nodes." This set includes the nodes for which the
shortest path has already been determined at the
current point in the algorithm.
• The nodes in the unsolved set S are those that are not
in S.
• While iterating, the algorithm assigns the numbers  i
to each node in the network, where  i is the length of
the shortest path to node i from the source node s
through the members of S.
Chapter 6 Network Flow Programming Methods
高等作業研究
Dijkstra's Algorithm
• Note that the  i values are equivalent to the
dual variables associated with the LP
formulation of the problem.
• At the end of the algorithm,  i is the length
of the shortest path to node i.
Chapter 6 Network Flow Programming Methods
高等作業研究
Initially, let S = s
Algorithm
,
s  0
Repeat until S is the set of all nodes:
Find an arc k(i,j) that passes from a solved node to an
unsolved node such that:
k(i,j) = argmin{  i  c k : k (i , j )  A, i   S, j  S }
Add node j and arc k(i, j) to the tree. Add node j to the solved set
S. Let  j =  i  c k ,where k=k(i,j)
Note: The algorithm requires m - 1 iterations. The algorithm
works because of the assumption of nonnegative arc lengths.
Chapter 6 Network Flow Programming Methods
高等作業研究
• This algorithm is easily adapted to graphs with undirected
edges, where each edge has nonnegative length.
• In the iterative step, we replace the arc set A with the edge
set £ and replace the word "arc" with the work "edge."
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
Figure 6.13 shows the intermediate situation with five nodes assigned
to the tree, S = {1, 3, 4, 6, 2} with arcs (2, 3, 6, 7}
Chapter 6 Network Flow Programming Methods
高等作業研究
Tabular Implementation
Chapter 6 Network Flow Programming Methods
高等作業研究
Primal Simplex Algorithm
• The primal simplex algorithm can also be used to
solve the shortest path tree problem but is not limited
to the case of all nonnegative arc lengths.
• It requires, however, that there exist no directed
cycles with negative total length. When such a cycle
is present, the algorithm terminates with the selected
arcs identifying the cycle. This means that the
associated LP has an unbounded solution.
Chapter 6 Network Flow Programming Methods
高等作業研究
Algorithm
Chapter 6 Network Flow Programming Methods
高等作業研究
• We use the example problem in Figure 6.11 to illustrate the
computations but assume that arc 4(2, 7) has length -10 rather than 10.
Arcs shown in Figure 6.12 form the initial basis .
• With c 4 = -10, we compute for arc 4
d 4  c 4   2 -  7  -10  12 - 18  -16
• Because d 4 is negative, we select arc 4 to enter the basis. According
to Step 2c, the arc that currently enters node 7, arc 11, must leave the
basis. Change the basis and obtain the new spanning tree shown in
Figure 6.14.
• If we allow arc 15 to enter the basis, arc 20 must leave, This leads to
the solution in Figure 6.15, which is optimal.
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
(-10)
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
MAXIMUM FLOW PROBLEM
• Consider a directed network with m nodes and n arcs in
which the only relevant parameter is the upper bound on
arc flow, called arc capacity.
• The problem is to find the maximum flow that can be sent
through the network from some specified node s, called
the source, to a second specified node t, called the sink.
Chapter 6 Network Flow Programming Methods
高等作業研究
MAXIMUM FLOW PROBLEM
• A cut is a set of arcs whose removal will interrupt all
paths from the source to the sink. The capacity of a cut is
the sum of the arc capacities of the set. The minimal cut is
the cut with the smallest capacity.
• Given a solution to the maximum flow problem, one can
always find at least one minimal cut, as illustrated in
Figure 6.17. The minimal cut is a set of arcs that limit the
value of the maximum flow.
• Not coincidentally, the example shows that the total
capacity of the arcs in the minimal cut equals the value of
the maximum flow (this result is called the max-flow mincut theorem)
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Flow Augmenting Algorithm
• The algorithm begins with a feasible set of arc flows
obtaining some value for the flow out of the source
and into the sink.
• A search is then made in the network for a set of
connected arcs from source to sink whose remaining
capacity is positive. This is called a flow augmenting
path.
• Flow is increased along that path as much as
possible.
• The process continues until no such path can be
found, at which time the algorithm terminates.
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
• Figure 6.18 Initial flow with V0  0
Chapter 6 Network Flow Programming Methods
高等作業研究
• For the initial solution, there are several flow augmenting paths.
We choose the path = (1,4,8)
0
0
0
Chapter 6 Network Flow Programming Methods
高等作業研究
0
0
0
0
Chapter 6 Network Flow Programming Methods
高等作業研究
0
0
0
0
0
Chapter 6 Network Flow Programming Methods
高等作業研究
Identify the minimal cut
• To find the minimal cut, we identify a set of nodes,
call it S, such that one or more paths exist from the
source node to the nodes in S on which additional
flow can be delivered.
• The source node is necessarily in S. The set of arcs
leaving S comprises the minimal cut.
• For example, starting at node A, we can reach only
node C through an arc that has additional capacity .
Chapter 6 Network Flow Programming Methods
高等作業研究
• Thus, we have the node set S = {A, C) to
which additional flow could be advanced. The
remaining nodes define the set = {B, D, E, F}.
The minimal cut consists of all the arcs that
pass from S to arcs in the set ={ 1, 5, 6} in the
example.
• The flows in the arcs on the minimal cut are at
their respective arc capacities.
Chapter 6 Network Flow Programming Methods
高等作業研究
Finding Flow Augmenting Paths
• In the example problem, flow augmenting paths
were discovered by observation. For larger
networks and for computer implementation, a more
formal procedure is required.
• The algorithm described below is a search
procedure that begins at s and labels all nodes to
which a flow augmenting path from s can be found.
• When node t is labeled, we have a break-through,
and the required flow augmenting path to t has been
discovered.
Chapter 6 Network Flow Programming Methods
高等作業研究
Finding Flow Augmenting Paths
• When the algorithm begins, all nodes are
unlabeled except s. We "check" a labeled
node after all avenues for finding paths
from the node have been explored.
• Initially, all nodes are unchecked.
Chapter 6 Network Flow Programming Methods
高等作業研究
Labeling Algorithm
Chapter 6 Network Flow Programming Methods
高等作業研究
Labeling Algorithm
• If the algorithm terminates with t labeled, the flow
augmenting path is found by tracing the path
backward from t and constructing P from the
labels encountered.
• If the algorithm terminates with t unlabeled, no
flow augmenting path exists. We illustrate the
former case with the situation depicted in Figure
6.20.
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
• Node C is the first to be labeled and checked,
followed by nodes E, B, D, and F. The resultant node
labels and checks are shown adjacent to the nodes in
Figure 6.22. An "x" indicates that a node is checked.
• When node F is labeled, the flow augmenting path is
complete. The label on node F indicates that the last arc on
the path is 7. Node D is the origin of this arc, so we find
the next arc on the path from the label on node D. The
process continues until the path P = (2, 6, -4, 3, 7) is
discovered.
Chapter 6 Network Flow Programming Methods
高等作業研究
PURE MINIMUM-COST FLOW
PROBLEM
• The problem is to determine the minimumcost plan for sending flow through the
network to satisfy supply and demand
requirements. Arc flows must be nonnegative
and no greater than the arc capacities, they
must satisfy conservation of flow at the nodes.
• It is assumed that all arc lower bounds on
flow are zero and all arc gains are unity.
Chapter 6 Network Flow Programming Methods
高等作業研究
PURE MINIMUM-COST FLOW
PROBLEM
Formulation
– The decision variables are
x k = flow through arc k(i, j) from node i to node j
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Also, let
Chapter 6 Network Flow Programming Methods
高等作業研究
0≦xk≦uk, k=1,…,n
Chapter 6 Network Flow Programming Methods
高等作業研究
– It is always possible to transform such a lower bound to zero by
introducing the variable

x k  x k - lk
– and substituting xˆ  l for XK throughout the model. The upper
k
k
bound must also be changed to

u k  u k - lk
Chapter 6 Network Flow Programming Methods
高等作業研究
• we will now allow for arcs that are incident to a
single node only, as shown in Figure 6.24. Arcs 6,7,
and 8 represent variable external flows at nodes 3, 2,
and 1, respectively
• we introduce an additional node into the network
called the slack node. Arcs representing the variable
external flows originate or terminate at the slack node,
as shown in Figure 6.25. Now all arcs again have
both origin and terminal nodes. Generally, the index
m is assigned to the slack node.
Chapter 6 Network Flow Programming Methods
高等作業研究
• Feasibility property
– Necessary condition for a pure NFP problem to
have a feasible solution
m
b
i 1
i
0
– The feasibility property will hold if we designate
the external flow of the slack node to be
m -1
b m  - b i
i 1
– This is shown in Figure 6.25, where m = 5.
Chapter 6 Network Flow Programming Methods
高等作業研究
Figure 6.24 Model with variable external flow
Chapter 6 Network Flow Programming Methods
高等作業研究
Figure 6.25 Model with a slack node (node 5)
Chapter 6 Network Flow Programming Methods
高等作業研究
• Integrality Property
– In all the network examples worked out earlier,
we saw that the solutions were always integral.
This was not a coincidence but a direct
consequence of the structure of the A matrix.
Chapter 6 Network Flow Programming Methods
高等作業研究
• Definition 1:
– A square integer matrix B is called unimodular if the
absolute value of its determinant equals 1—i.e.,
if | det B| = 1. An integer m x n matrix A is totally
unimodular if every square submatrix has determinant
+1, -1, 0 (or, equivalently, if every nonsingular square
submatrix is unimodular).
– From linear algebra we know that if B is nonsingular,
then B -1 = B  /det B, where B  is the adjoint of B and
is similarly an integer matrix.
(If B+ is an integer matrix and |det B|=1, then B-1 is an
integer matrix.)
Chapter 6 Network Flow Programming Methods
高等作業研究
• Theorem 1:
– If A is totally unimodular, every basic solution
( x B , x N ) = ( B-1b,0 ) is integer valued.
• Integrality property:
– For the pure NFP problem, when all supply and demand
values and all upper bounds on arc flows are integer
valued, all basic solutions are integral .
Chapter 6 Network Flow Programming Methods
高等作業研究
• Vector Notation
Chapter 6 Network Flow Programming Methods
高等作業研究
Basic Solutions
• Basis Tree
– Because the network model contains m - 1 independent
conservation-of-flow constraints and the variables are
the arc flows, a basis is determined by selecting m - 1
independent arcs. These arcs are identified by the arc
indices of the basic variables. Call the corresponding
set nB .
– To illustrate, let nB= (2, 4, 7, 8} for the network shown
in Figure 6.25. Drawing only the selected arcs forms
the subnetwork shown in Figure 6.26. Node 5 is
defined as the root node of the tree.
Chapter 6 Network Flow Programming Methods
高等作業研究
Figure 6.26 Basis tree for= (2,4,7,8}
Chapter 6 Network Flow Programming Methods
高等作業研究
• Nonbasic Arcs
– The arcs not selected as basic are, by definition, the
nonbasic arcs.
– In the bounded variable simplex method of general LP,
each nonbasic variable takes the value 0 (lower bound)
or the value of its upper bound in the definition of a
basic solution.
Chapter 6 Network Flow Programming Methods
高等作業研究
• In a basic solution, each nonbasic arc k has its
flow at 0 or u k , the upper bound. We let n 0
denote the set of nonbasic arcs with 0 flow, and
we let n 1 , denote the set of arcs with upper
bound flow. To represent a specific case
graphically, we add the members of n 1 to the
basis tree as dotted lines.
• To illustrate, Figure 6.27 shows the basis tree
representing n B ={2,4,7,8}, n 1 ={5}, and n 0
={1,3,6}.
Chapter 6 Network Flow Programming Methods
高等作業研究
• Figure 6.27 Basis tree with a nonbasic arc with flow at its
bound
Chapter 6 Network Flow Programming Methods
高等作業研究
• Primal Basic Solution
– Given a selection of basic arcs and an assignment of
nonbasic arcs to either n 0 or n 1 , there is a unique
assignment of flows to the basic arcs that satisfies the
conservation-of-flow requirement at the nodes.
– To solve for the basic arc flows, we must first adjust the
external flows in the network to account for nonbasic
arcs at their upper bounds.
Chapter 6 Network Flow Programming Methods
高等作業研究
• the network in Figure 6.25, the external flow
vector is b  (2, 1, 0,  5, 2)T
• Arc 5 is in the set n 1 , so we adjust the external
flows at both ends of the
arc: b3  b3  u 5，b4  b4  u5 . Since u 5 = 3, the
adjusted external flows are b  (2,1,-3,-2,2) T
Chapter 6 Network Flow Programming Methods
高等作業研究
• Given the adjusted external flows,
there is a unique assignment of flows
to the basic arcs that satisfies
conservation of flow at the nodes. The
solution for the basis in Figure 6.27 is
shown in Figure 6.28.
Chapter 6 Network Flow Programming Methods
高等作業研究
• This is a primal basic feasible solution (BFS)
Chapter 6 Network Flow Programming Methods
高等作業研究
• Figure 6.27 Basis tree with a nonbasic arc with flow at its
bound
Chapter 6 Network Flow Programming Methods
高等作業研究
Figure 6.28 Solution for the basic flows
[-2]
Chapter 6 Network Flow Programming Methods
高等作業研究
• Dual Basic Solution
– There is a dual variable for each node i,denoted by  i
and interpreted as the cost of bringing one unit of flow
to node i from the slack node. Given a basis tree, the
dual values are assigned using the requirement of
complementary slackness. For every basic arc k(i,j)
c k   i - j =0
– Because one of the conservation-of-flow constraints in
the LP model is redundant, one of the dual variables can
have an arbitrary value. We choose to set the dual value
for the slack variable, node 5 in the example, equal to
zero.
Chapter 6 Network Flow Programming Methods
高等作業研究
– The values are computed in the following order
5  0, 1  5  11  11, 3  1  16  27
 2   5  10  10, 4   2  18  28
– There are several different orders that can be followed in this
computation, but they all must start at the slack node and work
outward
Chapter 6 Network Flow Programming Methods
高等作業研究
• Simplified Computation of Primal Solutions
– Observe again the example basis in Figure 6.30, and note
that there is a directed path from node 5 to every other node
in the tree. This is called a directed spanning tree rooted at
node 5.
Chapter 6 Network Flow Programming Methods
高等作業研究
• The process starts at nodes at the extremes of
the tree (the nodes incident to only one arc are
called the leaves of the tree). We assign flows
to the arcs incident to the leaves and work
backward through the tree toward the root.
• The order in which arc flows are assigned is
not unique, but for a given basis tree and set n,
there is a unique solution for the basic flows.
For our example, we find two leaves of the tree
in Figure 6.30—nodes 3 and 4 .
Chapter 6 Network Flow Programming Methods
高等作業研究
– We assign the flows to arcs 2 and 4 such that
x 2  -b3  -(-3)  3, x 4  -b4  -(-2)  2
– Now the flows for arcs 7 and 8 can be assigned
x 7  -b2  x 4  -(1)  2  1, x8  -b1  x 2  -(2)  3  1
– The arcs selected for the basis in Figure 6.30 naturally form
a directed spanning tree. Other selections may not. For
instance, consider the basis consisting of arcs 2, 3, 5, and 6
as shown in Figure 6.31 where
n B = {2, 3, 5, 6}
n1 = {4, 7}
n 0 = {1, 8}
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
• Although the subnetwork defines a tree, it does not form
a directed spanning tree. To put the network into the
desired form, the direction of some of the arcs must be
reversed, as shown in Figure 6.32.
Chapter 6 Network Flow Programming Methods
高等作業研究
– The reversed arcs, called mirror arcs, play a major role
in the minimum-cost flow algorithm. We call an arc
with a positive index (k) a. forward arc, and one with a
negative index (-k) a mirror arc. A forward arc has the
direction and parameters given in the problem
statement.
– The parameters of the mirror arc are derived from those
of the forward arc as follows:
l -k  -uk , u -k  -lk , c -k  -ck
– Similarly, for the flow variable, we set
x -k  -x k
Chapter 6 Network Flow Programming Methods
高等作業研究
– It is always possible to construct a directed spanning
tree by replacing some forward arcs with mirror arcs.
– The basic flows for the tree in Figure 6.32 are easily
obtained by following the tree backward from its leaves.
The flows in the forward arcs are found by negating the
flows in the mirror arcs.
Chapter 6 Network Flow Programming Methods
高等作業研究
– For the original basis n B = (2, 3, 5, 6}, the directed tree
uses n B = (-2, -3, 5, -6}. Now, working backward from
the leaves yields x B = (-2, 0, 1, -1). To find the
equivalent flow in the forward (original) arcs, we
negate the flow in the mirror arcs, yielding x B =
(2,0,1,1) , which, along with x1 = (4,3), satisfies the
conservation-of-flow constraints for the network in
Figure 6.31.
Chapter 6 Network Flow Programming Methods
高等作業研究
– Data associated with the solution in Figure 6.32 are as
follows
Chapter 6 Network Flow Programming Methods
高等作業研究
• Simplified Computation of Dual Solutions
– The directed spanning tree can also be used to compute the
dual variables, but here we start at the root and work
outward toward the leaves.
– We begin by setting  5 = 0. When the dual variable for a
node on one end of a basic arc is known, the value for the
node on the other end can be computed using the
complementary slackness condition:
for every basic arc k(i, j)
Chapter 6 Network Flow Programming Methods
高等作業研究
– we compute the values of
1
and  2 as follows.
 1   5  c8  0  11  11,  2   7  c 8  0  10  10
– Now the values of
3
and  4 can be calculated
 3   1  c 2  11  16  27,  4   2  c 4  10  18  28
Chapter 6 Network Flow Programming Methods
高等作業研究
Figure 6.33 Directed spanning tree used to compute the dual solution
Chapter 6 Network Flow Programming Methods
高等作業研究
– When the basic arcs do not naturally define a spanning
tree, mirror arcs are used to construct one. For n B = {2,
3, 5, 6}, we replace arcs 2, 3, and 6 with mirror arcs.
The relation c -k  -ck provides the unit costs for the
mirror arcs.
– The spanning tree and the computed dual variables are
shown in Figure 6.34
Chapter 6 Network Flow Programming Methods
高等作業研究
Figure 6.34
– Figure 6.34 Solution for the dual variables for
= (-2, -3,5, -6}
Chapter 6 Network Flow Programming Methods
高等作業研究
Optimality Conditions
Chapter 6 Network Flow Programming Methods
高等作業研究
Example
• For the primal and dual solutions illustrated in Figures 6.28
and 6.29, respectively, we see that x satisfies both parts of
condition 1. Condition 2a is satisfied for the basic
variables x B  (x 2 , x 4 , x 7 , x 8 )  (3,2,1,1) , so the solution is
optimal if condition 2b or condition 2c is satisfied for each
nonbasic arc. For the nonbasic arcs with flows at the lower
bound, n 0 = {1, 3,6} and dual solution π=  1 ,  2 ,  3 ,  4 ,  5 
=(11,10, 27, 28,0), we get the following reduced costs
Chapter 6 Network Flow Programming Methods
高等作業研究
– the nonbasic arcs with flows at their upper bound,
={5}, the reduced cost is
n1
– Thus, the solution is not optimal, because arcs 3 and 5
violate the optimality conditions. In fact, these two arcs are
candidates to enter the basis.
Chapter 6 Network Flow Programming Methods
高等作業研究
Chapter 6 Network Flow Programming Methods
高等作業研究
Since primal feasibility and complementary slackness are satisfied,
this is the optimal solution.
Chapter 6 Network Flow Programming Methods

Download Report