Browse Prior Art Database

Post Optimal Transportation Problem Basis Preservation

IP.com Disclosure Number: IPCOM000077710D
Original Publication Date: 1972-Sep-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 4 page(s) / 130K

Publishing Venue

IBM

Related People

Horowitz, HM: AUTHOR

Abstract

Post optimal analysis of Transportation Problem application solutions have significantly enhanced the overall utility of this versatile analytical technique. The preprocessor described eliminates the need for unnecessary introduction of variables into the basis, to accommodate parametric variations to the problem input vectors. By maximizing the utilization of the variable locations already in the basis, the number of new variables required is minimized and the time required for subsequent solution optimization is significantly reduced.

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 54% of the total text.

Page 1 of 4

Post Optimal Transportation Problem Basis Preservation

Post optimal analysis of Transportation Problem application solutions have significantly enhanced the overall utility of this versatile analytical technique. The preprocessor described eliminates the need for unnecessary introduction of variables into the basis, to accommodate parametric variations to the problem input vectors. By maximizing the utilization of the variable locations already in the basis, the number of new variables required is minimized and the time required for subsequent solution optimization is significantly reduced.

Variations to the original problem can be expressed for a(i) in the terms of Delta a(i) for b(j) in terms of Delta b(j) and for c(ij) in terms of Delta c(ij). This parametric variation stated mathematically follows:

(Image Omitted)

The process presently in use to solve this parametric problem takes the basic, original optimal solution and injects all parametric variations (Delta c(ij), Delta a(i) and Delta b(j)), without destroying the triangular properties of the basic. The resulting suboptimal solution is then reoptimized considering the new parameters.

This current procedure is heuristic and follows northwest corner type logic. The resulting feasible and suboptimal solution is not prepared with the prime intent of minimizing the subsequent required optimization time. The incorporation of the preprocessor described is a significant improvement over this heuristic process in accomplishing this advantageous reduction in computer time.

The current four-step heuristic approach are summarized in A (above) as related to the new preprocessor step. The new procedure retains Steps I and II as they currently exist. Step I assures consistency among the Dekta a(i) and Delta b(j) parameters considering the original solution matrix (x(ij)). Step II eliminates negative Delta a(i) and Delta b(j) by adjusting the appropriate x(ij) elements and corresponding input vector elements. A new step is added for the preprocessing of the Delta a(i) and Delta b(j) into an interim solution matrix Delta x(ij) considering a binary c*(ij). This cost matrix relates to the current basis with all c*(ij)=1 except for c*(ij)=0 for elements in the basis.

The solution of this simple transportation problem disposes of the maximum possible parametric flow, using variable locations already in the basis. Where there is element coincidence between Delta x(ij) and x(ij), the two matrices are simply added together and optimality is retained. Where Delta x(ij) > 0 and c*(ij)=1, the basis has to be altered to create a new element in the required location....