Browse Prior Art Database

THE CENTRAL MATHEMATICAL PROBLEM

IP.com Disclosure Number: IPCOM000128830D
Original Publication Date: 1956-Jul-09
Included in the Prior Art Database: 2005-Sep-19
Document File: 8 page(s) / 41K

Publishing Venue

Software Patent Institute

Related People

Dantzig, G.B.: AUTHOR [+3]

Abstract

I. The L. P. Model Stated in Algebraic Terms.....1 Symbols are introduced to distinguish various activities items, the assumed constant flows and costs (or profits) per unit level of activity, the activity levels and the quantities of demand or availability of various items. The central problem is then stated in standard algebraic form. II. Equivalent Systems.....4 It is shown that the problem of minimizing a linear form where the unknowns satisfy a system of equations in non-negative variables is equivalent to one where the variables satisfy a system of linear inequalities. III. Properties of Solutions and the Simplex Method.....8 It is stated without proof that an optimizing solution belongs to a class of feasible solutions that ";involve"; no more variables than equations. The simplex method is illustrated by showing for this class a way of testing the optimality of a solution and constructing a sequence of improved feasible solutions. IV. Existence of Solutions, Uniqueness.....11 V. Problems.....17

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

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE CENTRAL MATHEMATICAL PROBLEM

G. B. Dantzig

P-892

July 9, 1956

The RAND Corporation 1700 MAIN ST., SANTA MONlCA, CALIFORNIA

SUMMARY

I. The L. P. Model Stated in Algebraic Terms.....1
Symbols are introduced to distinguish various activities items, the assumed constant flows and costs (or profits) per unit level of activity, the activity levels and the quantities of demand or availability of various items. The central problem is then stated in standard algebraic form.

II. Equivalent Systems.....4
It is shown that the problem of minimizing a linear form where the unknowns satisfy a system of equations in non-negative variables is equivalent to one where the variables satisfy a system of linear inequalities.

III. Properties of Solutions and the Simplex Method.....8
It is stated without proof that an optimizing solution belongs to a class of feasible solutions that "involve" no more variables than equations. The simplex method is illustrated by showing for this class a way of testing the optimality of a solution and constructing a sequence of improved feasible solutions.

IV. Existence of Solutions, Uniqueness.....11

V. Problems.....17

THE CENTRAL MATHEMATICAL PROBLEM

G. B. Dantzig

I. Algebraic Statement of the L. P. Model

The minimization of a linear form subject to linear inequality restraints has been called the central mathematical problem of linear programming. The standard form for such problems,

Rand Corporation Page 1 Jul 09, 1956

Page 2 of 8

THE CENTRAL MATHEMATICAL PROBLEM

because it arises naturally in many applications, is finding a solution of a system of linear equations in non-negative variables which minimizes a linear form. We shall see in a moment why this particular form was chosen as standard. At the same time we shall formalize in mathematical terms our remarks regarding linear programming models.

Standard Form: If the subscript j = 1, 2, ..., n denotes the j-th type of activity and xj its quantity (or activity level), then usually xj ≥ 0. If, for example, xj represents the quantity of a stockpile allocated for the j-th use, it does not, as a rule, make sense to allocate a negative quantity. In certain cases, however, one may wish to interpret a negative quantity as meaning taking stock from the j-th use. Here some care must be exercised; for example, there may be costs, such as transportation charges, which are positive regardless of the direction of flow of the stock. One must also be careful not to overdraw the stock of the using activity. For these reasons it is better in formulating models to distinguish two activities, each with a non-negative range, for their respective xj, rather than to try incorporating them into a single range. The interdependencies between various activities arise because all practical programming problems are circumscribed by commodity limitations of one kind or another. The limited commodity may be raw materials, manp...