The Transportation Paradox Revisited

Sverre Storøy (sverre.storoyii.uib.no)

Abstract: The transportation paradox is related to the classical transportation problem. For certain instances of this problem an increase in the amount of goods to be transported may lead to a decrease in the optimal total transportation cost. Even though the paradox has been known since the early days of linear programming, it has got very little attention in the literature and in teaching, and it seems to be almost unknown to the majority of the LP-prcatitioners. We consider the result of a recent paper which presents necessary and sufficient conditions for a transportation cost matrix to be immune against the paradox. These conditions are rather restrictive, supporting the results reported from simulations that the paradox may occur quite frequently. We also consider some postoptimal conditions for when the paradox may occur. A simple procedure for modifying an existing model to exploit the paradox is given and illustrated by examples.

Keywords: transportation problem; transportation paradox; linear programming; duality

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Department of informatics, University of Bergen, P.O.Box 7803, N-5020 Bergen, NORWAY August, 2007

Download: [PDF]

Entry Submitted: 08/31/2007
Entry Accepted: 09/01/2007
Entry Last Modified: 09/03/2007

Modify/Update this entry