Browse Prior Art Database

Transportation Problem Extended Optimization Program

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

Publishing Venue

IBM

Related People

Horowitz, HM: AUTHOR

Abstract

This Transportation Problem Extended (TPX) program is based on the Simplex Stepping Stone Method. A general statement of the problem that TPX addresses is the classical "Hitchcock" distribution problem. Assume that m origins with a supply a(i) at each origin and n destinations with a demand b(j) at each destination are given. In addition, a cost c(ij) of shipping a unit from origin i to destination j is also given. The solution matrix x(ij) is computed such that z, the total shipping cost, is minimized when: (Image Omitted)

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

Page 1 of 3

Transportation Problem Extended Optimization Program

This Transportation Problem Extended (TPX) program is based on the Simplex Stepping Stone Method. A general statement of the problem that TPX addresses is the classical "Hitchcock" distribution problem. Assume that m origins with a supply a(i) at each origin and n destinations with a demand b(j) at each destination are given. In addition, a cost c(ij) of shipping a unit from origin i to destination j is also given. The solution matrix x(ij) is computed such that z, the total shipping cost, is minimized when:

(Image Omitted)

In addition to the above relationships, Simplex multipliers are used through processing. The row and column simplex multipliers are represented by u(i) and v(j), respectively.

(Image Omitted)

Where z' is the current objective function and equal to z in (1) when the solution is optimal.

Two main features of the TPX program are loop determination and simplex multiplier updating.

A major limitation of other stepping stone method programs is the indirect trial and error approach that connects the basic elements which constitute a unique loop. These procedures involve extensive bookkeeping in searching row entry/exits and column entries/exits and retracting paths that proved to be not part of the loop. The loop determination path procedure of TPX uses direct pointers to the basic elements in the loop. These pointers are saved in two vectors u'(i) and v'(i) and are derived from the indices used in the simplex multiplier (dual variable) computations.

If the determination of the simplex multipliers, the following relations were used:

(Image Omitted)

To demonstrate exactly how u'(i) and v'(j) are created and then utilized to find a loop, consider the TP example shown in A. TPX Processing requires that a basic variable be created at x(31). By retaining the indices from the simplex multiplier computations, the loop is formed by the addition of x(31).

u'(3) represents the base row which corresponds to the simplex multipl...