Total unimodularity and the transportation problem: a generalization

Well-known sufficiency conditions for total unimodularity are relaxed to include more general classes of matrices, whose determinants are related to Fibonacci sequences. It is then shown that in order to study determinants of submatrices of the two-commodity transportation problem, one should study precisely these generalized unimodular matrices. (Note that all submatrices of an ordinary transportation problem are unimodular.) This result enables us to establish determinantal values for submatrices of two-commodity transportation problems (in terms of the number of disjoint capacitated routes) and to identify a totally unimodular class of two-commodity transportation problems.