Journal of Applied Mathematics and Decision Sciences
Volume 2 (1998), Issue 1, Pages 65-104
Managing cost uncertainties in transportation and assignment problems
Business Center, University of Baltimore, 1402 N. Charles Street, Baltimore 21201-5779, MD, USA
Copyright © 1998 V. Adlakha and H. Arsham. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
In a fast changing global market, a manager is concerned with cost uncertainties
of the cost matrix in transportation problems (TP) and assignment problems (AP).A time lag
between the development and application of the model could cause cost parameters to assume
different values when an optimal assignment is implemented.
The manager might wish to determine the responsiveness of the current optimal solution to such uncertainties.
A desirable tool is
to construct a perturbation set (PS) of cost coeffcients which ensures the stability of an optimal
solution under such uncertainties.
The widely-used methods of solving the TP and AP are the stepping-stone (SS) method and the
Hungarian method, respectively. Both methods fail to provide direct information to construct the
needed PS. An added difficulty is that these problems might be highly pivotal degenerate.
Therefore, the sensitivity results obtained via the available linear programming (LP) software might be
We propose a unified pivotal solution algorithm for both TP and AP.
The algorithm is free of pivotal degeneracy, which may cause cycling, and does not require any extra variables such as slack, surplus, or artificial variables used in dual and primal simplex. The algorithm permits higher-order assignment problems and side-constraints. Computational results comparing the proposed
algorithm to the closely-related pivotal solution algorithm, the simplex, via the widely-used pack-age Lindo, are provided. The proposed algorithm has the advantage of being computationally
practical, being easy to understand, and providing useful information for managers. The results
empower the manager to assess and monitor various types of cost uncertainties encountered in
real-life situations. Some illustrative numerical examples are also presented.