HITCHCOCK TRANSPORTATION PROBLEM

IP.com Prior Art Database Disclosure
IP.com Disclosure Number: IPCOM000128834D
Publication Date: 09-Jul-1956
Find Similar Download

Publishing Venue

Software Patent Institute

Related People

Fulkerson, D.R. - Author [+2] [-2]
Rand Corporation - Owner
B.A. Galler

Abstract

An exposition of the simplex computation for transportation type problems.

Language

English (United States)

Country

United States

Document File

11 pages / 115.7 KB

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

HITCHCOCK TRANSPORTATION PROBLEM

D. R. Fulkerson

P-89O

July 9, 1956

The RAND Corporation 1700 MAIN St., SANTA MONICA, CALIFORNIA

SUMMARY

An exposition of the simplex computation for transportation type problems.

CONTENTS

SUMMARY.....11
Section

1. SIMPLEX METHOD.....6
2. OPTIMAL ASSIGNMENT PROBLEM.....19
3. UPPER BOUNDS ON VARIABLES.....20
4. THE TRANSSHIPMENT PROBLEM.....21
REFERENCES.....26

HITCHCOCK TRANSPORTATION PROBLEM

D. R. Fulkerson

The transportation problem was first formulated by F. L. Hitchcock 1 in 1941; he also gave a computational procedure, much akin to the general simplex method, for solving the problem. Independently, during World War II, T. C. Koopmans arrived at the same problem in connection with his work as a member of the Joint Shipping Board. The problem is thus frequently referred to as the Hitchcock-Koopmans problem.

Mathematically the problem has the form ( [ Equation no. ] 1) [ Equation omitted ]

1 Hitchcock, F. L., "The distribution of a product from several sources to numerous localities," Jour. Math. Phys., vol. 20, 1941.

Rand Corporation Page 1 Jul 09, 1956

Page 2 of 11

HITCHCOCK TRANSPORTATION PROBLEM

subject to the constraints ( [ Equation no. ] 2) [ Equation omitted ] where ai, bj, aij are given. Feasibility is assured by assuming ai ≥ 0, bj ≥ 0, and Σiai = Σjbj. A particular realization of the problem appears if we think of m sources of a commodity, the ith one possessing ai units, and n sinks, the jth one requiring bj units, and interpret aij as the unit transportation cost from source i to sink j. Thus the linear form (1) becomes the total transportation bill, to be minimized subject to fulfilling demands at the sinks from supplies at the sources. This interpretation is a paraphrase of Hitchcock's original statement of the problem.

To give some idea of the diverse applications of the transportation problem, we have compiled the following list (by no means exhaustive) of problems which can be successfully attacked, either directly as transportation problems or by subsequent developments of the theory:
(1) Suppose n men are to be assigned to n jobs, where man i in job j has a "score" aij; (a) find an assignment of men to jobs which maximizes the sum of the scores 2; (b) find an assignment which maximizes the least score 3.
(2) Consider-a network consisting of N points and inter- connecting links. Let ai ≥ 0 denote the supply of a commodity at the ith point, bi ≥ 0 the demand at the point, where aibi ~ 0, and aij ≥ 0 the unit cost of shipping from i to j. Assuming that Σai = Σbi, and that any point can act as a transshipment point, find a minimal cost transportation program 4.
(3) Given a network, let aij denote the length of the link from i to j. Find a chain of minimal length connecting two given points 5.
(4) Suppose B = (bij), i = 1, ..., m, j = 1, ..., n, is a given matrix. By a "walk through B from mn to ln" we wil...

First page image
You are not signed in. If you have an IP.com account, your download price may be lower or waived. Click here if you want to sign-in now.
Loading PayPal...
The full document comprises 11 pages and is available as a PDF document as well as a ZIP archive. The cost is $40.00 USD (depending on your billing address, sales tax may apply); payment may be made directly using your credit card or your PayPal account.

If you've already purchased this document, and wish to download it now you may enter the download access code you received in your original email receipt.