Browse Prior Art Database

Parametric Processing for Transportation Problems

IP.com Disclosure Number: IPCOM000073401D
Original Publication Date: 1970-Dec-01
Included in the Prior Art Database: 2005-Feb-22
Document File: 5 page(s) / 139K

Publishing Venue

IBM

Related People

Horowitz, HM: AUTHOR

Abstract

Parametric processing for transportation problems allows for any combination of input parameters to be modified and produces new solutions in minimum computer processing time relative to the original problem processing time.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 43% of the total text.

Page 1 of 5

Parametric Processing for Transportation Problems

Parametric processing for transportation problems allows for any combination of input parameters to be modified and produces new solutions in minimum computer processing time relative to the original problem processing time.

Once a solution to a transportation problem is obtained, it is often advantageous to vary some input vector element(s) and/or cost matrix element(s) to reflect any desired modifications to the original problem. This procedure has proven very effective as a method of incorporating newly obtained input data and to assist in ascertaining answers to "What if..." type questions concerning the problem being evaluated. One approach to accomplishing this would be to change the desired inputs and completely rerun the problem. This procedure would require computer processing times that would most likely approximate the original problem. It is well known that in Linear Programming formulations, parametric processing is accomplished by using an original solution as an excellent starting point for subsequent optimization. Using this technique, only a very small fraction of the original computer processing time is usually consumed to obtain the modified solution. This is also the case in the Transportation Problem where the basic solution can be salvaged as the starting point for further processing.

There are three major input parameters to a transportation problem matrix, the row entries (a(i) which represent the number of items available at source i, column entries (b(i)), which represent the requirements of items at terminal j, and costs (C(ij)). Parametric changes to these inputs are given in the form of Delta a(i), Delta b(j) and Delta c(ij).

Mathematically, the parametric transportation problem can be stated as:

(Image Omitted)

The parametric processor takes an original basic solution and inserts the required modifications in such a way as to preserve feasibility and the triangular properties of the basis.

The parametric processor is best described as a series of four major steps which verify and reflect the modifications of the a(i) and b(i) vectors into the original basic solution (x(ij)).

Step I is the resolution of any inconsistencies in the magnitudes of Delta a(i) or Delta b(j). The following relationships must exist prior to continuing with subsequent steps:

(Image Omitted)

Step II converts all negative delta a(i) into a corresponding positive delta b(j) and all negative delta b(j) into corresponding positive delta a(i) in order to simplify subsequent processing. This step is accomplished by first locating a negative Delta a(i) and then decreasing the activity level of any basic variable situated in

1

Page 2 of 5

the effected row. This activity level decrease is accounted for by increasing the corresponding delta b(j). This procedure is then repeated searching for negative Delta b(j) decreasing the appropriate basic variable activity levels and increasing the co...