USA: +1(669)289-8683 
Sign in
1.
Use decision trees to find a lower bound on the number of comparisons required to sort six items in the worst case.
The decision tree would be a binary tree.
It would contain n! leaves.
Equivalently it has at least 1+lg(n!) levels.
Worst case would be lg(n!).
n! = 6! = 720 = lg(720) = 9.49 = 10 comparisons
Give an algorithm that uses this number of comparisons to sort six items in the worst case.
2.
Use Algorithm 10.2.4 to find a maximal flow in each network.
Algorithm 10.2.4 Finding a Maximal Flow in a Network
This algorithm finds a maximal flow in a network. The capacity of each edge is a nonnegative integer.
Input:
A network with source a, sink z, capacity C, vertices a = v0, . . ., vn = z, and n
Output:
A maximal flow F
max flow(a, z, C, v, n) {
// v’s label is (predecessor(v), val(v))
// start with zero flow
1. for each edge (i, j)
2. Fij = 0
3. while (true) {
// remove all labels
4. for i = 0 to n {
5. predecessor(vi) = null
6. val(vi) = null
7.
}
// label a
8. predecessor(a) = —
9. val(a) = ∞
// U is the set of unexamined, labeled vertices
10. U = {a}
// continue until z is labeled
11. while (val(z) == null) {
12. if (U == Ø) // flow is maximal
13. return F
14. choose v in U
15. U = U −{v}
16. Δ = val(v)
17. for each edge (v, w) with val(w) == null
18. if(Fvw < Cvw) {
19. predecessor(w) = v
20. val(w) = min{Δ, Cvw − Fvw}
21. U = U ∪ {w}
22. }
23. for each edge (w, v) with val(w) == null
24. if(Fwv > 0) {
25. predecessor(w) = v
26. val(w) = min{Δ, Fwv}
27. U = U ∪ {w}
28. }
29. } // end while (val(z) == null) loop
// find path P from a to z on which to revise flow
30. w0 = z
31. k = 0
32. while (wk¬= a) {
33. wk +1 = predecessor(wk)
34. k = k + 1
35. }
36. P = (wk+ 1, wk, . . ., w1, w0)
37. Δ= val(z)
38. for i = 1 to k + 1 {
39. e = (wi, wi −1)
40. if (e is properly oriented in P)
41. Fe = Fe + Δ
42. else
43. Fe = Fe − Δ
44. }
45. } // end while (true) loop
}
3.
Use Algorithm 10.2.4 to find a maximal flow in each network.
4.
Refer to Figure 10.4.1, where we reverse the direction of the edges so that edges are directed from jobs to applicants. Show a maximal matching
5.
Given Example 10.4.4 and Theorem 10.4.5 in the textbook, explain how you would transform the matching problem into a maximal flow problem.
6. Once you complete question 5 use the already known linear program that solves the maximal flow problem. Show all of your work and how you are doing the reduction.
<
b
>Unit 9: Lin
e
a
r Programming, Max Flow, an
d
Mat
c
hing Problems
By
Lawrence Jerome, Online Instructor, Capella University
Unit 9 focuses mostly on Chapter 10 in Johnsonbaugh, matching problems and flow networks. Our u09a1 assignment, Linear Programming, Reduction, and Max Flow Networks, asks you to review the Notes on Linear Programming and Flow Networks on pages 534-535. Unfortunately, that half page of notes is woefully inadequate to introduce you to such a complex subject as linear programming—and the book provides no worked examples as a guide. This tutorial/lecture will attempt to fill the gap.
Linear programming began as Operations Research during World War II as researchers looked for more efficient ways to move and assign men and material in a very large scale war operation. Thus, linear programming seeks to…
1. Maximi
z
e or minimize some composite function of several or many variables
2.
Subject to
a series of constraints involving the variables
3. Leading to an optimal solution of all variables.
While linear programming solves sets or systems of simultaneous linear equations, which you probably encountered in College Algebra, there is one major difference:
1. Systems of linear equations must have the same number of equations as variables
2. Linear programming problems must have more equations than variables.
When there are more equations than variables, an infinite number of solutions are possible (called the feasible region) and the goal of linear programming is to find the best or optimal solution from the infinite set in that feasible region. Fortunately, we have software tools to do all that work for us, so we can concentrate on setting up the problems correctly and interpreting the solution. Let’s look at the linear programming setup for maximizing flow networks presented on pages 534 to 535 in your textbook:
“The problem of finding a maximal flow in a network, G, with source a, sink z, and capacities Cij may be rephrased as follows:
Maximize
Subject to
0 Fij Cij for all i, j
for all j” [1]
The first part, maximize , seems straightforward enough—we’re just maximizing flow in the network. The first constraint, 0 Fij Cij for all i, j, likewise makes sense because we’re just making sure the flows do not exceed the capacity of the network. However, the second constraint, for all j, is not at all clear from the Note until you read Definition 10.1.3 on page 511:
“(b) For each vertex j, which is neither the source or the sink,
(10.1.1)” [2]
The key is that the left hand side of (10.1.1) represents the flow into j and the right hand side represents the flow out of j. This is the key constraint because it maintains the conservation of flow within the network while maximizing the flow within network capacities. Unfortunately, the Linear Programming Note on page 535 fails to mention leaving out the source and sink from this constraint. But a key concept is still missing: how can we represent flows that utilize these equations—and this is the key connection to linear programming that is missing in our textbook.
Look back at our first linear programming restraint:
0 Fij Cij for all i, j
Those capital letters with subscripts represent two-dimensional arrays, or matrices as we’ve been calling them in this class. In other words, a network flow can be represented by a matrix, just as we’ve been representing graphs by adjacency matrices. Note that for our network flow problems, we’ll have two matrices, one for capacity, and the other for the actual flow. Example 10.2.5 on page 520 will serve as a simple example:
Small Network Flow Example 10.2.5, page 520:
2,0
3,0
c
b
4,0
2,0
z
a
4,0
5,0
2,0
e
d
Figure 1: Network Flow Capacities for Example 10.2.5
There are 6 vertices in our network graph, so we need to set up a 6 by 6 square matrix to represent the network capacities:
Capacity Matrix
a
b
c
d
e
z
a
0
3
0
5
0
0
b
0
0
2
0
0
0
c
0
0
0
0
0
4
d
0
0
2
0
2
0
e
0
0
0
0
0
4
z
0
0
0
0
0
0
To set up the linear programming problem in Excel, we need a identical matrix with all zeros to represent the initial flow condition:
Flows
Flow Matrix
Out:
a
b
c
d
e
z
sum:
a
0
0
0
0
0
0
0
b
0
0
0
0
0
0
0
c
0
0
0
0
0
0
0
d
0
0
0
0
0
0
0
e
0
0
0
0
0
0
0
z
0
0
0
0
0
0
0
Flows In:
sum:
0
0
0
0
0
0
maximize:
0
Added to the matrix are the sums of rows and columns, representing the flows in and out of each vertex. Only the middle sums (the tan cells) will be used in the linear programming constraints, leaving the source and sink sums out of the programming mix. Accompanying this Word tutorial is the Excel file in which the actual programming is performed. Here are the instructions for setting up the matrices and Excel Solver which performs the actual linear programming:
To solve max flow problems using linear programming ,,,
Step 1: Set up the Capacity Matrix representing the Flow Network. Sum the rows and columns.
Step 2: Copy the Capacity Matrix below and relabel Flow Matrix. Zero all entries.
Step 3: Set up the function to maximize by summing all cells in the Flow Matrix: cell E24: =SUM(C16:H21)
Step 4: Use Premium Solver Standard LP Simplex engine or Standard Solver set to Assume Linear Model programmed as follows:
Set maximize cell E24 Equal to Max
By Changing Variable Cells C16:H21
Subject to Constraints:
C16:H21 <= C5:H10 (flow <= capacity)
I17:I20 = D22:G22 (flows in = flows out)
Options: Assume Non-Negative
Step 5: Solve
Figure 2 shows the entire linear programming setup in Excel:
Figure 3 shows the actual solution, which is identical to the solution obtained by our textbook after three pages of applying the maximal flow algorithm:
Flows
Flow Matrix
Out:
a
b
c
d
e
z
sum:
a
0
2
0
4
0
0
6
b
0
0
2
0
0
0
2
c
0
0
0
0
0
4
4
d
0
0
2
0
2
0
4
e
0
0
0
0
0
2
2
z
0
0
0
0
0
0
0
Flows In:
sum:
0
2
4
4
2
6
maximize:
18
2,2
3,2
c
b
4,4
2,2
z
a
4,2
5,4
2,2
e
d
Figure 3: Maximal Network Flows for Example 10.2.5
Large Network Flow Example, #12, page 524
The Problem #12 on page 524 is quite large—in fact so large (a 15 by 15 matrix) that it has more variables (225) than Excel Solver can handle (200). However, we can cut down the number of variables by cutting off the first two columns: the first column represents the source and does not enter into calculations; the second column we can artificially set to the same solution as the Solution Manual (a—b = 10, a—f = 5) and run Excel Solver on the remaining 13 columns. The results are shown in Figure 4: the linear programming solution was able to improve on the Solutions Manual solution by quite a bit, resulting in a flow to the sink of 26 compared to the Solutions Manual solution of 22 into the sink.
Figure 4: Comparing Linear Programming Solution with Solution Manual Solution
Matching Problems and Linear Programming
Both the book and our Unit 9 Assignment suggest that matching problems can be solved via linear programming by “reducing” the matching problem to a maximum flow problem, as shown on page 529. However, there is an easier and more straightforward method of solving matching problems not found in any Discrete Math book—Assignment Matrices. Just we used two matrices in the flow problems above (Capacity Matrix and Flow Matrix), we can use two matrices for matching problems:
1. Matching Matrix giving the original matching information
2. Assignment Matrix showing how to assign the matches.
Figure 5 shows how to set up the Applicant-Job matching problem, Example 10.4.1 on pages 528-529:
Matching Applicants and Jobs Using Assignment Matrices and Linear Programming, Example 10.4.1, page 528, 529
Applicant-Job Qualification Matrix:
Jobs:
J1
J2
J3
J4
J5
Applicants
A
0
1
0
0
1
B
0
1
0
0
1
C
1
0
1
1
1
D
0
1
0
0
1
Applicant-Job Assignment Matrix:
Jobs:
J1
J2
J3
J4
J5
sum:
Applicants
A
0
0
0
0
0
0
B
0
0
0
0
0
0
C
0
0
0
0
0
0
D
0
0
0
0
0
0
sum:
0
0
0
0
0
sumproduct target:
0
Figure 5: Matching Problem Setup with Blank Assignment Matrix Ready for
Linear Programming
Here are the instructions for setting up the Example 10.4.1Applicant-Job problem in Excel for linear programming using Excel Solver:
Matching problems can be solved much easier using assignment matrices than as a matching network as in Johnsonbaugh (page 529)…
Step 1: Set up Applicant-Job Qualification Matrix (cells C6:G9).
Step 2: Set up Applicant Job Assignment Matrix (cells C14:G17). Initially set all values to 0 (we haven’t made any assignments yet). Sum the columns and rows (cells H14:H17 and cells C18:G18).
Step 3: Set up the sumproduct target cell E20: =SUMPRODUCT(C14:G17,C6:G9)
Step 4: We could operate Excel Solver on this first Assignment Matrix, but to show the difference from all zero values, I’ve copied the Applicant-Job Assignment Matrix below and redid the sumproduct formula: sumproduct target:, cell E31: =SUMPRODUCT(C25:G28,C6:G9)
Step 5: Go to Data tab and bring up Solver and fill in as shown:
Set Target Cell: E31 Equal to: Max
By Changing Cells: C25:G28
Subject to Constraints:
C25:G28 = binary (assignments are either 0 or 1)
C29:G29 <= 1 (not all jobs can be filled)
H25:H28 <= 1 (not all applicants can get jobs)
Step 6: Solve
Figure 6 shows the entire Excel Solver linear programming and solution:
This assignment matrix methodology can be extended and applied to a wide range of common Discrete Math problems:
· Knapsack problems
· Bottleneck problems
· Independent Set problems
· Matching problems
· Routing problems
· Transportation Time and Cost problems
I have a manuscript, “Generalized Assignment Matrix Methodology in Linear Programming” currently under review by The International Journal for Technology in Mathematics Education, detailing how to set up and solve these diverse Discrete Math problems using assignment matrices, so hopefully this methodology will appear in future Discrete Math textbooks. Be sure to study the Excel file accompanying this Lecture which gives the complete set up and solutions to the problems discussed here.
References
[1] Johnsonbaugh, Richard, Discrete Mathematics, Pearson Prentice-Hall, 2009, pages 534-535.
[2] Johnsonbaugh, Richard, Discrete Mathematics, Pearson Prentice-Hall, 2009, pages 528-529.
[3] Jerome, Lawrence, “Generalized Assignment Matrix Methodology in Linear Programming” currently under review by The International Journal for Technology in Mathematics Education.
