3.2. The Capital Budgeting Problem (Problem
II)
77
12
3
4
1
2
Matrix 2:
3
4
Fig. 3.4 Starting the solution tree.
merits. Arc (2, 3) or arc (3, 2) has the highest value of 0#, and according
to rule (3) of Section 3.2.2 either arc could be included in the first branching sequence. Arbitrarily, arc (3, 2) was chosen for the first branching
sequence. The bound for excluding arc (3, 2) [denoted by (3, 2)] is
equal to 286 + 14 = 300, a value computed by making the element (3, 2)
equal to infinity and continuing with row and column reduction. To calculate the bound for including arc (3, 2) it is necessary to change matrix 2 as
follows:
1. Element (3, 2) is made equal to infinity to avoid considering it again,
and element (2, 3) is made equal to infinity to avoid the subtour (2-3-2).
2. Elements (3, 1), (3, 4), (1, 2), (4, 2) are made equal to infinity since
we can only arrive at city 2 from city 3 or depart for city 2 from city 3. In
effect, row 3 and column 2 are eliminated from matrix 2, and matrix 3
results.
Table 3.2
Calculation of 0»; for the Zero Elements of Matrix 4
Element
of matrix 4
α»
0/
9u
(1, 3)
0
8
8
(1, 4)
0
7
7
(2, 1)
7
0
7
(4, 1)
8
0
8