The paper deals with the generalized network flow problem (GNFP), which is a minimum cost linear programming problem, where the coefficient matrix contains at most two nonzero entries of opposite sign, in each column. Also lower and upper bounds on the variables are present. First the variant of the simplex algorithm is applied to GNFP, with Dantzig’s pivot rule of selecting the entering variable whose reduced cost is minimum and lexicography to avoid cycling. It is shown that the strongly convergent pivoting rule ofJ. Elam,F. Glover, andD. Klingman [Math. Oper. Res. 4, 39-59 (1979;Zbl 0422.90081)] is equivalent to lexicography in the way that it selects the variable to leave the basis. It is also shown that if a basis B for GNFP is feasible for right hand sides b’ and b” with b’\(\leq b''\) then B is also feasible for all right hand sides b satisfying b’\(\leq b\leq b''\). Next an ordinary network flow problem (i.e. GNFP where all entries of the coefficient matrix are 0, 1, or -1) is considered. It is shown that the maximum number of pivots, when Dantzig’s pivot rule is applied is: \(O(mnu^*\log w^*)\), where: m and n are number of rows and columns of coefficient matrix, respectively, \(u^*\) is the greatest difference between the upper and lower bounds of the individual variables, \(w^*\) is the upper bound on the difference in objective values between any two feasible solutions. The maximum number of possible consecutive degenerate pivots is also given.

Reviewer: W.A.Molisz