Browse Prior Art Database

UPPER BOUNDED VARIABLES IN LINEAR PROGRAMMING

IP.com Disclosure Number: IPCOM000128841D
Original Publication Date: 1956-Aug-10
Included in the Prior Art Database: 2005-Sep-19
Document File: 6 page(s) / 94K

Publishing Venue

Software Patent Institute

Related People

Johnson, S.M.: AUTHOR [+3]

Abstract

When it is necessary to place upper bounds on variables in a linear programming problem, these restraints can be applied without greatly increasing the computational effort. The technique for bounding variables is presented and several applications are discussed.

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.

UPPER BOUNDED VARIABLES IN LINEAR PROGRAMMING

S. M. Johnson

P-921

August 10, 1956

The RAND Corporation 1700 MAIN ST., SANTA MONICA, CALIFORNIA-

SUMMARY

When it is necessary to place upper bounds on variables in a linear programming problem, these restraints can be applied without greatly increasing the computational effort. The technique for bounding variables is presented and several applications are discussed.

UPPER BOUNDED VARIABLES IN LINEAR PROGRAMMING

S. M. Johnson

I. INTRODUCTION

Upper bounds on variables in linear programming are used quite commonly. Their use tends to increase as models become more realistic. Typically, in practice, this would mean that more activities enter the solution since the favored activities are not allowed to carry the whole load.

The following three classes of problems illustrate the use of upper bounds and will be treated in turn.

A. Capacity Restrictions

1. On factory production rates.
2. On traffic links in a transportation problem.
3. In assignment problem (special case of transportation problem).

Rand Corporation Page 1 Aug 10, 1956

Page 2 of 6

UPPER BOUNDED VARIABLES IN LINEAR PROGRAMMING

B. Convex Programming Problems

1. Many examples whore the cost or an activity is a convex function of the level engaged in.
2. Linear programming under uncertainty.

C. Discrete Linear Programming Problems

1. Tanker scheduling problem.
2. The shortest route through a network.

Others of this class where discrete type programming has been partially successful are:
. Flight scheduling problem.
4. Fixed charge problem.
5. Traveling salesman problem.
6. Empty container problem.

2. HANDLING UPPER BOUND RESTRAINTS

The basic device for handling variables with upper bounds will be discussed using a transportation-type problem for illustration.

Consider a system of equations ( [ Equation no. ] 2.1) [ Equation omitted ] where it is desired to obtain values of xj such that the form Σa0jxj is to be minimized (or, what is the same thing, to maximize the variable x0).

The size of the matrix associated with such a linear programming problem may become uncomfortably large when) in addition to (2.1),many (or all) variables of the initial set have upper bounds. Thus, if each variable satisfies 0 ≤ xj ≤ αj, it is customary to add an additional variable, say xj, and a new equation xj +x'j = αj (xj ≥ 0, x'j ≥ 0) to take care of each such restriction. To illustrate by way of example, a linear programming problem of the transportation type involving m destinations and n origins has a matrix involving m + n rows and m * n variables xij associated with m * n possible routes joining origins with destinations. Suppose there is a capacity limitation rij on a route so that, in addition to the original system of equations and linear inequalities, 0 ≤ xij, one must impose m * n additional restraints xij + x'ij = rij (xij, ≥ 0, x'ij ≥ 0)

It is clear now that...