Solutions

CO 602/CM 740: Fundamentals of Optimization
Problem Set 7
H. Wolkowicz
Fall 2014.
Handed out: Wednesday 2014-Oct-15.
Due: Wednesday 2014-Oct-22 in class before lecture starts.
1
Network Flow and Spanning Tree
1.1
The flow balance constraint is given by
X
X
fij −
fji = bi ∀i = 1, 2, · · · , n.
j∈o(i)
j∈I(i)
The value of: arc 15, f15 = 3; Arc 43, f43 = 0; Arc 37, f37 − f43 = 0 =⇒ f37 = 0; Arc 56, f56 − f15 =
0 =⇒ f56 = 3; Arc 62, −f62 = −1 =⇒ f62 = 1; Arc 68, f68 + f62 − f56 = 0 =⇒ f68 = 2; Arc 79,
f79 − f37 = 0 =⇒ f79 = 0; Arc 89, f89 − f68 = 0 =⇒ f89 = 2.
Since the tree flows corresponding to the basic solution are nonnegative, it is a basic feasible solution.
1.2
Let yi for i = 1, 2, · · · , n be dual variables. The reduced cos to arc (i, j) is given by
c¯ij = cij − yi + yj .
The basic variables are f15 , f3,7 , f43 , f56 , f62 , f68 , f79 , f89 . Since c¯ij = 0 for all (i, j) corresponding to the basic
variables (or edges in the network), we get
0 = c89 − y8 + y9 =⇒ y8 = 2; 0 = c79 − y7 + y9 =⇒ y8 = 3; 0 = c68 − y6 + y8 =⇒ y6 = 4; 0 =
c37 − y3 + y7 =⇒ y3 = 4; 0 = c43 − y4 + y3 =⇒ y4 = 7; 0 = c62 − y6 + y2 =⇒ y2 = 3; 0 = c56 − y5 + y6 =⇒
y5 = 5; 0 = c15 − y1 + y5 =⇒ y1 = 7.
For the nonbasic variables, c¯ij is calculated as
c¯14 = 1; c¯46 = 1; c¯52 = 2; c¯67 = 1; c¯28 = 0. So,
c¯
=
1
c¯14
0
c¯15
0
c¯28
0
c¯37
0
c¯43
1
c¯46
2
c¯52
0
c¯56
0
c¯62
1
c¯67
0
c¯68
0
c¯79
0
c¯79
1.3
Since the reduced costs of nonbasic variables are all nonnegative, the basic solution is optimal.
1
1.4
NO. A nondegenerate solution requires strictly positive flow on all arcs in some spanning tree. In particular,
a positive flow must be on at least one of (4, 3) or (3, 7). By examining the graph, it is easy to see that
positive flow on (4, 3) or (3, 7) is possible if flow goes along the following path
p1 = (1, 4), (4, 3), (3, 7), (7, 9).
The cost of this flow is 8. However, the path p2 = (1, 5), (5, 6), (6, 8), ((8, 9)) from node 1 to node 9 has a
cost of only 7. Hence any solution with flow on p1 is not optimal. It follows that both (4, 3) and (3, 7) will
have 0 flow in any optimal solution, and any basic solution must use one of those edges. Therefore, there is
no nondegenerate optimal BFS.
1.5
Consider the solution found in part 2: y¯=(7 3 4 7 5 4 3 2 0)t , and obtain b = (3 -1 0 0 0 0 0 0 -2)t . Then
bt y¯ = 18. Note that, the cost of tree solution from part 1 is 2(3)+1(3)+1(1)+2(2)+2(2)=18.
1.6
In calculating the reduced cost of nonbasic variables, only the reduced cost of arcs (1, 4) and (5, 2) involve
the arc cost c56 . If the arc cost c56 is to be increased by maintaining optimality, then we need to maintain
the nonnegative reduced cost for arcs (1, 4) and (5, 2). That is,
c¯52 = c52 − c62 − c56 = 4 − 1 − c56 ≥ 0 =⇒ c56 ≤ 3
c¯14 = c14 + c43 + c37 + c79 − c89 − c68 − c56 − c−5 = 1 + 3 + 1 + 3 − 2 − 2 − c56 − 2 ≥ 0 =⇒ c56 ≤ 2
So, since c56 is already equal to 1, it can be increased by at most 1 to have the same optimal BFS.
1.7
If we increase the supply at node 1 and demand at node 9 by small positive amount δ, the new optimal cost
will be
cN = 2(3 + δ) + 1(3 + δ) + 1(1) + 2(2 + δ) + 2(2 + δ) = 18 + 7δ
Hence, the change in cost is 7δ.
1.8
This digraph has no directed cycle, the problem will never be unbounded.
2
Assignment Problem
2.1
For each student i and university j, we denote the student-university pair i, j by the arc (i, j). The flow on
(i, j), which is interpreted as student i being assigned to university j, is defined as fij = 1, if student i is
assigned to university j, and 0 otherwise. Let cij denote the value student i assigned for the preference of
university j. Then the network flow problem is given as
2
max
x
s.t.
n X
n
X
cij fij
i=1 j=1
n
X
fij = 1, ∀j = 1, 2 · · · , n,
i=1
n
X
(1)
fij = 1, ∀i = 1, 2 · · · , n,
j=1
fij ≥ 0.
2.2
For a connected digraph, the rank of the incidence matrix is equal to the number of nodes minus 1. Since
the digraph is connected and there are 40 nodes, the rank of the incidence matrix is 39.
2.3
2.4
In a balanced transportation problem there are two sets of nodes, the source nodes (warehouse) and the
sink nodes (the dealers). The number of items available at each warehouse (source node) and the number of
items demanded at each dealer ( sink node) can be greater or equal to 1. In order to transform the balanced
transportation problem into assignment problem, we split each source node and each sink nodes such that
the nodes have exactly one item. So, each source node i represents one item and has bi = 1, and each sink
node j represents one item and has bj = −1. Since the transportation problem is balanced, we have equal
number of source node and sink node in the transformed system. Each of these new nodes will have an arc
to a sink node, with the same cost as the arcs from the original node. Therefore, the problem is transformed
into assignment problem.
3
Maximum Flow Problem
3.1
Consider the following graph, where the name of the nodes represents the first letter of the cities and the
numbers on the arc represent the capacities equal to the number of seats available in the route. We connect
S and T by an arc with cost equal to -1 and capacity equala to ∞. We consider the cost of the rest of arcs
as 0. Therefore, maximizing the number of travellers from S to T is given by
max
fT S
s.t.
Af = 0,
x
(2)
0 ≤ fij ≤ uij ∀i, j,

1
−1

0
where A is the incidence matrix A=
0

0
0
1
0
−1
0
0
0
0
1
0
−1
0
0
0
1
0
0
−1
0
3.2
3
0
0
1
−1
0
0
0
0
0
1
0
−1
0
0
0
0
1
−1

−1
0

0

0

0
1

Download Report