3.2. The Capital Budgeting Problem (Problem
II)
79
Matrix 6:
Fig. 3.6 The solution tree after branching sequence 2.
The row and column reduction of matrix 5 reduces the value of the elements
of column 4 by 7, thereby giving a bound for arc (1, 3) = 300 + 7 = 307
and the new matrix 6; see Fig. 3.6.
(e)
THIRD BRANCHING SEQUENCE
In matrix 6 there are two elements that could be considered for the
third branching sequence. Table 3.3 gives the value of 0*/ for each of the
elements.
The bound for arc (2, 4) is calculated by removing row 2 and column 4
from matrix 6 to give the element (4, 1), which is equal to zero. Thus the
bound for arc (2, 4) = 307 + 0 = 307. Also the bound for arc (4, 1) =
307 + 0 = 307. Thus we have a feasible solution to the traveling salesman
problem, namely the sequence (3, 2), (1, 3), (2, 4), (4, 1), or rearranging,
(1, 3), (3, 2), (2, 4), (4, 1). The length of the route is 307 mi; Fig. 3.7
shows the solution tree.
Table 3.3
Calculation of 0 for the Zero Elements of Matrix 6
Element (ij)
of matrix 6
θα
(2, 4)
00
00
00
(4, 1)
00
00
00