Determining All Nondegenerate Shadow Prices for the Transportation Problem

Shadow prices derived from the optimal dual solution of a transportation problem give the rate at which the optimal cost changes when a warehouse capacity or market requirement is changed ceteris paribus. One of the limitations in interpreting shadow prices for managerial use is that they may be degenerate, i.e., their interpretation may be valid only over a zero range of the parameter to be varied. This paper provides an efficient procedure for computing all nondegenerate (or “real”) shadow prices. The method involves breaking the optimal basis tree into subtrees by dropping basic variables which are at their bounds, defining a measure of distance between the subtrees and solving a shortest path problem between all pairs of subtrees.