×

Ill-conditional networks for network flow problems. (Chinese. English summary) Zbl 1438.90287

Summary: In a transportation system, due to the unsuitable distribution of supplies and demands, the network flow problem would cause a strange phenomenon: for an optimal transportation scheme, even the supplies and demands are increasing, more amounts of goods are transported, the transportation cost decreases instead. This unusual situation reflects the unbalanced and lopsided structure of the system, which twists the optimal scheme. This kind of structures may be called “ill-conditional”. In the case of transportation problem without capacity constraints, this strange phenomenon is called “the transportation paradox”, which has been discussed in the literature. In this paper, we investigate more ill-conditional structures in general network flow models and present corresponding recognition algorithms. This study will eventually lead to the area of the network improvement.

MSC:

90C27 Combinatorial optimization
90B10 Deterministic network models in operations research
90B06 Transportation, logistics and supply chain management
Full Text: DOI