Dismiss
Prior Art Database (priorart.ip.com) will be unavailable on Saturday, November 1 from 9:00 - 10:00 AM EST due to maintenance updates. We apologize for any inconveniences.
Dismiss
Pantros applications will be unavailable from Thursday, October 30, 2014 at 9:00 PM EST through Friday, October 31, 2014 at 5:00 AM EST, due to maintenance. We apologize for any inconveniences.

Browse Prior Art Database

Select date range below to browse

HITCHCOCK TRANSPORTATION PROBLEM

IP.com Disclosure Number: IPCOM000128834D
Publication Date: 1956-Jul-09

Publishing Venue

Software Patent Institute

Related People

Fulkerson, D.R.: AUTHOR [+3]

Abstract

An exposition of the simplex computation for transportation type problems.


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...