Browse Prior Art Database

REVIEW OF COMPUTATIONAL METHODS

IP.com Disclosure Number: IPCOM000128831D
Original Publication Date: 1956-Jul-25
Included in the Prior Art Database: 2005-Sep-19
Document File: 6 page(s) / 98K

Publishing Venue

Software Patent Institute

Related People

Jacobs, Walter: AUTHOR [+3]

Abstract

An abstract of various computing procedures which have been proposed for the linear programming problem.

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

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

REVIEW OF COMPUTATIONAL METHODS 1

Walter Jacobs, U.S. Air Force July 25, 1956

SUMMARY

An abstract of various computing procedures which have been proposed for the linear programming problem.

REVIEW OF COMPUTATIONAL METHODS [ title ]

Walter Jacobs, U.S. Air Force

1. SUMMARY OF METHODS

a. Problems in simplex form.
(i) Koopmans' method.
(ii) Multiplex method.
b. Problems in inequalities form.
(i) Elimination.
(ii) Relaxation--projection.

Other types of relaxation, acceleration.
c. Problems in game form.
(i) Fictitious play. von Neumann's method.

2. THE SIMPLEX FORM

a. Standard form: Maximize (clxl + c2x2 +...+ cnxn) subject to
(2.1) ailxl + ai2x2+ ... + ainxn+ xn+1 = bi (i = 1, 2, ...,m)
(2.2)xk ≥ 0 (k = 1,2,..,, n + m).

The geometrical representation considers x : (x1x2 xn)

1 Prepared for The RAND Corporation Short Course in Computational Aspects of Linear Programming, Sept. 4-13, 1956.

Rand Corporation Page 1 Jul 25, 1956

Page 2 of 6

REVIEW OF COMPUTATIONAL METHODS

as a point in Euclidean n-space. The inequalities xk ≥ 0form half spaces, whose intersection is a convex point set GG consisting of all points x satisfying (2.1), (2.2). The point c : (clc2 ... cn), viewed from the origin, determines the objective direction; the optimal solution is the point or points of GG whose components in the objective direction are maximal. The hyperplanes xk = 0 contain the faces of GG; they can be written explicitly as
(2.3) xk = bk0 + bk1x1 + bk2x2 + ... + bknxn = 0. (k=1 ..., n+m) where bk0 = 0, bkj = δkj, = (k = 1, 2, ...,n) bk0 = bk-n, bkj = ak-n,j, (k = n+1, n+2, ..., n + m).

Koopmans' method (ref. 3)2. The t-th iteration commences with an interior point xt ε GG. Move in the objective direction c until a bounding plane xkt = 0 is reached; call this point yt. In the two- dimensional plane normal to xkt = 0 and parallel to c, move in a direction interior to GG and orthogonal to c until a new bounding plane is reached; call this new point &bar{y};t. Take xt+1 as the point midway between yt and &bar{y};t. Repeat. Analytically,
(2.4) ytj = xtj + λtcj (j =1, 2,..., n)

where λtis a maximum subject to yt ε GG. Thus there in at least one value of k, say kt, such that [ Equation omitted ] Write
(2.5) [ Equation omitted ]

with µt a maximum subject to &bar{y};t ε GG. Commence a new iteration with
(2.6) xt+1j = 1/2 (ytj + &bar{y};tj) (j = 1, 2,..., n).

c. The multiplex method of R. Frisch (ref. 5).3 This method starts like Koopmans' with an interior point x0 of GG. From x0 move in the direction c until a bounding plane xk1 = 0 is reached:
(2.7) [ Equation omitted ]

where λ0 and all subsequent λt are maximal subject to the corresponding xt+l ε GG. From xl, staying in the hyperplane xk1 = 0, move as close to the direction c as possible [ Equation omitted ] where θ11 is determined so that (2.9) [ Equation omitted ] This move will reach a second bounding plane xk2 = 0.

In general a...