Off-campus Eastern Washington University users: To download EWU Only theses, please use the following link to log into our proxy server with your EWU NetID and password.
Non-EWU users: Please talk to your local librarian about requesting this thesis through Interlibrary loan.
Date of Award
Summer 1979
Rights
Access perpetually restricted to EWU users with an active EWU NetID
Document Type
Thesis: EWU Only
Degree Name
Master of Science (MS) in Mathematics
Department
Mathematics
Abstract
The capacitated transshipment problem was originally developed as an extension of the transportation or distribution problem. The transportation problem is a flow network model in which every node is either an origin or a destination. Typically, the origins are production plants and the destinations are consumer markets for some commodity, and a cost is associated with shipping one unit from a given plant to a given market. If some intermediate nodes are introduced, such as warehouses, which are not origins or destinations, the network becomes a transshipment model. Finally, if some or all shipping routes, or arcs in the model, have limits in the amount of flow they may carry, the problem is termed 11 capacitated. 11 Any transshipment problem may be solved with a linear programming (LP) model, where each arc is a variable and each node is a constraint. The Simplex Method, commonly used in LP problems, may be specialized to solve these problems very efficiently by exploiting the inherent special network structure. The key property of networks, essential to the algorithm, is the spanning tree characterization of the basis. The Simplex Method pivots from one basic feasible solution, or spanning tree, to another until optimality is reached. The basis tree provides a unique relationship between the basic variables and the constraints so that the reduced costs may be computed, the pivot procedure completed, and the basis priced out all by simple addition, rather than by matrix operations with the usual tableau. It also provides integer valued basic solutions when supplies, demands and arc bounds are integers.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Banner, Michael C., "SIMNET, a primal Simplex code for networks" (1979). EWU Masters Thesis Collection. 787.
https://dc.ewu.edu/theses/787
