iS

A Modified General Simplex Method
For Solving Linear Programming Problems

By
BENNETT B. FOSTER

and
RICHARD R. WEYRICK

Station Bulletin 493

Agricultural Experiment Station

University of New Hampshire

Durham, New Hampshire

Table of Contents

Introduction 1

An Example Problem 2

Technique for solution, p, 3

Rules for the pivoting procedure, p. 4

Minimizing Problems and Problems where Zero Production is

not Allowed 7

Summary of Rules for Determining Pivot Row and Pivot Column

and the Pivoting Operation 10

Equality Constraints and No Solution Situations 12

Equality constraint, p. 12
'No solution" situations, p. 12

"T

Computer Program 13

Selected References 13

Appendix A. Fortran II Program with Instructions for Data Cards 15

Appendix B. Derivation of Pivoting Rules and Pivot Row and

Column Selection Rules 19

February 1968

The research project contributing the technique described
'n -liis bulletin is funded through the Mclntire - Stennis
-o.-eracive Forestry Research Act of 1962. The authors
are assistant professors in the Department of Forest
Resources.

Introduction

Most formal explanations and many computer programs for solving
linear programming problems follow the simplex "tableau" method. As
desirable as this method is for enabling the beginning student to see the
"whys" and "hows" of linear programming, it is rather complicated. If
followed in writing an L. P. problem solving program where the origin
(zero production) is not feasible, this method unnecessarily uses up a
sometimes short supply of computer storage space and is vulnerable
to a computer "bug" resulting from an inadequate value "M" for the
slack variable (s) .

This bulletin describes a technique (or algorithm) for solving L. P.
problems that is based on rules derived by simple high school algebra
rather than the intuitive descriptive approach or the more formal math-
ematical approach. It draws on the simple mathematical characteristics
of the derived rules to determine the logical sequences of the problem
solution and also to eliminate the need for artificial variables and high
negative "M" values in problems where zero production is not allowed.

The technique is such that, for a clearer understanding, the ex-
planation will begin with the set-up of a simple problem and proceed
rapidly to the rules of the technique (the algorithm). It is important
to point out that the rules presented herein are specifically oriented to
the method presented for setting up the problem constraints.

The precise point of departure of this technique from those pre-
sented by others (Baumol [1], Heady and Candler [2], Stiefel [3],
Vajda [4, 5] for example) is the placing of the equal sign when the
inequality constraints are changed into equalities.^ This modification in
turn leads to a unique method of handling "greater-than-or-equal-to"
constraints that does not require the use of artificial variables and the
corresponding high negative values.

IS; = EXi ± Ci rather than ZXj ± S; = Ci

1

An Example Problem

Given: the following inequality constraints: ^

2X1 + 3X2 ^ 24
.5X1 4- .25X0 ^ 3
Xi ^5

and objective function:

Z = 3X1 + 2X2 (max.)

The inequality constraints are then changed into equalities by add-
ing or subtracting slack variables.

2X1 + 3X2 + Si = 24

.5X1 + .25X2 + S2 = 3

Xi + Sh = 5

In order to fit these equality constraints into this modified simplex
technique, they are restated in terms of the positive slack variables, and
set up in matrix form.

Si =

52 =

53 =

Si =

52 =

53 =
z =

2X1 — 3X2 + 24
.5X1 — .25X2 + 3

+ 5

Restated
Constraints

Xi
Xi

X2

KPoi

— 2

— 3

24

— .5

— .25

3

— 1

0

5

3

2

0

Constraint
Matrix

The box in the lower right-hand corner of the matrix is the oh-
jective solution. The initial solution is zero because, as the table is read,
there are 24 units of Sj, 3 units of So, and 5 units of S^ in the solution.
In other words, none of the resources have yet been used; therefore,
the objective solution equals zero. However, the first two figures in
the bottom row (objective function) indicate that the objective solu-
tion can be increased by three for each unit of Xj brought into solu-
tion and by 2 for each unit of X2 brought into solution.

1 The other constraints generally assumed in LP problems are that the values
Xi, X2, Si, S2j etc., are non-negative; that is, the solution cannot contain negative
amounts of an activity. These constraints are assumed in the algorithm presented,
and are explicitly stated in the requirements from which the rules are developed
(see p. 22, requirement A).

The Technique for Solution

In the following explanation each figure in the matrix will he called
an "element."

The problem is solved hy attempting to bring Xj and X2 (the ac-
tivities) into solution. The resources (Sj ) will be used to produce the
activities (Xj). This will be done by mathematically exchanging rows
and columns of the matrix, a row and a column at a time, in a series
of matrix-forming processes called "iterations."

The process of exchanging a row and a column is called "pivoting"
and is accomplished by using a set of rules described on page 4 and
derived in Appendix B. The row and column that are exchanged in a
pivoting process are known as "pivot row" and "pivot column," and the
common element is known as the "pivot element." Under no circum-
stance will the bottom row or last column be considered as the pivot row
or pivot column.

Pivot Column. With the exception of the last column, any column
with a positive bottom element can be used as the pivot column,^ as
long as it contains a potential pivot element (see below). -^ The pro-
cedure outlined in this l)ulletin specifies the pivot column as the one
with the largest positive bottom element, but actually the choice is ar-
bitrary. In the example proljlem the pivot column will be the X^
column.

Pivot Row. The appropriate row or "pivot row" is determined by
the resource that is most limiting in the production of the pivot column
activity. This of course excludes the bottom or objective function row.
According to the constraints of the example problem (and also the
matrix table if signs arc ignored), the available supply of S^ (24)
will allow 12 units of X^ to be produced, the available supply of S^
(three) will allow 6 units of X^ to he produced, and the available sup-
ply of S3 (five) will allow 5 units of X^ to be produced. The limiting
resource then is S3, so the S3 row becomes the pivot row. The element
at the intersection of the pivot column and pivot row is the "pivot
element." This determination of the pivot row can be done quickly by
generating what will be called "Q-values." This is done for each poten-
tial pivot row by dividing the resource value (in the last column) by the
element in the pivot column, and registering this quotient in a "Q-
column" to the right of the table. After all Q's have been determined,
the row with the smallest absolute value of Q becomes the pivot row.

1 The algebraic logic of this is also covered in Appendix B.

2 This is also true if the problem is one of minimization, as will be explained
on page 7.

Potential Pivot Element. For reasons explained in Appendix B,
any potential pivot element must he negative and the resource value in
any potential pivot roiv m-ust be positive; therefore, all the Q-values
that are of concern will be negative.^

The pivot column contains the largest bottom positive element and a po-
tential pivot element (negative).
The pivot row generates the smallest absolute value of Q.

Xi

X2

KPo)

Q

—12

Si =

— 2

— 3

24

So =

—.5

—.25

3

— 6

S3 =

— 1*

0

5

— 5

4r- pivot row

z =

3

2

0

t

Pivot

column

*pivot element
(negative)

Figure 1 : Beginning matrix of example problem.

Rules for the Pivoting Procedure

The rules for the pivoting procedure, which are derived in Appen-
dix B, are as follows:

A new matrix is developed by:

Pivoting Rules

PR-1. Changing the old pivot element to its reciprocal
value.

PR-2. Changing the other values in the pivot column
by dividing each by the old pivot element.

PR-3. Changing the other values in the pivot row by
dividing each by the old pivot element and
giving it the opposite sign.

PR-4. Changing all other elements in the matrix by
subtracting from each: the value obtained by
multiplying the element in the same column
and pivot row by the element in the same row
and pivot column, then dividing this product by
the pivot element. ("Rectangle Rule")

1 At this point, we are not concerned with situations in which negative Q-
values cannot be generated. This will be covered later, see bottom of page 12.

This last rule may seem rather complicated, but it will prove simple
if stepped through slowly. It may be thought of in terms of a rectangle.
The elements involved form a perfect rectangle within the matrix. The
element being changed is one corner of the rectangle, the pivot element
is the opposite corner, and the two elements that are to be multiplied
together complete the rectangle. In the example, the Si resource (24)
becomes 24, minus the value of 5 times minus 2 divided by minus 1, or.

24

[(5) (- 2)/(— 1)] = 24 — (+ 10) = 14

Xi

X2 KPo)

S3

X2 KPo)

Si =

— 2

— 3

24

—12

Si =

2

— 3

14

S2 =

—.5

—.25

3

— 6

S2 =

.5

-.25*

.5

S3 =

— 1*

0

5

— 5"^

Xi =
z =

— 1

0

5

z =

3

2

0

— 3

2

15

%

—2

new

pivot

row

Old Matrix

new pivot colamn
New Matrix

It will be noticed that in the new matrix, the headings "Xj" and
"S3" have been switched, which can be visualized by the fact that they
have been "pivoted" on the element in the matrix common to both —
the pivot element.

This new matrix indicates that the objective solution has been in-
creased to 15 by producing five units of Xj. There are 14 units of Si
and .5 units of S2 left over. The positive 2 in the bottom row, however,
indicates that the objective solution can be made even greater. A third
matrix is developed using the X2 column as the pivot column and the
S2 row as the pivot row.

New matrices will continue to be developed as long as there is a
positive element in the bottom row (excepting the objective solution,
of course) . The solution of this example problem comes with the fourth
matrix.

S3 =
X2 =

Xi =

z =

Si

S2

KPo)

—.25

3

2

-.5

2

6

.25

—3

3

—.25

—5

21

Solution

This final matrix presents all the standard information obtainable
from the more common simplex methods; objective solution, activity
levels, amounts of excess resources, shadow prices, and coefficients from
which other information, such as variable prices and resource program-
ming can be calculated:

Activity levels: 6 units of X2

3 units of Xj
Objective solution: 21

Excess resources: 2 units S3 unused

Shadow prices: Si price is .25

S2 price is 5

Minimizing Problems and Problems
Where Zero Production Is Not Allowed

The preceding example was a case where zero production was
allowed under the given constraints, and the objective function was to
be maximized. A common L.P. problem is one where zero production
is not allowed by the constraints and where the objective function is to
be minimized.

Minimizing a positive objective function is nothing more than max-
imizing a negative objective function. If an objective function, Z =
SXj -{- 4X2, is to be minimized, it is the same as maximizing — Z r=
— 8X^ — 4X->. In this case the bottom row of the beginning matrix would
contain:

(X,) (Xo) (KPo))

— Z = *"

indicating that the objective solution could be reduced by the amounts
shown for X^ and X2. Reducing by a negative amount, however, means
adding to or increasing the objective solution, which would defeat the
minimizing objective. This objective solution can be reduced further
only if a positive value appears in the bottom row, which leaves the pre-
viously stated rule (see page 3, Pivot Column) unchanged. The ob-
jective solution will naturally be a negative, but with a simple sign
change the objective solution becomes an acceptable value. For ex-
ample, if — Z = — 85, then Z = 85.

This minimizing case is directly related to the case where zero ac-
tivity »is not allowed. The first case requires the second, for minimizing
a problem where zero activity is allowed leads to the trivial solution of
zero, no activity.

In the example problem, suppose that the second constraint were

changed to:

.5X + .25X2 ^ 3

(greater than, or equal to). In order to make this into an equality a
slack variable must be subtracted from the left hand side of the in-
equality sign: .5X1 -f .25X2 — S2 = 3. When this equality is restated
in terms of the positive slack variable, a negative sign appears in the

last term:

02 ^^^^ .5Xj -|- .25X2 — o.

Xi

X2

KPo)

— 2

-^ 3

24

.5

^5

-3

— 1

0

5

— 3

— 2

0

If this modified problem were now to be minimized, the initial
matrix would be:

Si =

52 =

53 =

-Z =

The bottom row indicates that the problem has been solved because
of the negative numbers, however, the matrix says this is accomplished
by having a negative amount of S2 in solution, which is not an accept-
able situation. The negative three in the last column must be removed.
It is here that this approach differs from the more commonly presented
techniques. Rather than becoming involved with an artificial variable,
its high negative value and additional computer storage space, the nega-
tive last column figure is removed mathematically with the following
rules:

Rules for Removing Negative Resources ^

Neg-1. The row containing the negative number in the last column
becomes the pivot row.

Neg-2. The pivot element must be positive.

Neg-3. The pivot column is chosen arbitrarily if more than one
column satisfies rules Neg-1 and Neg-2.

Neg— 4. If there are two or more negative numbers in the last col-
umn, then the pivot row is the row generating the largest
absolute value of Q.

Once the pivot row and pivot column are determined, the pivoting
rules are followed as before. The first iteration for the above example
is shown here:

Si =

82 =

83 =
-Z =

Xi

X2

KPo)

— 2

— 3

24

.5*

.25

— 3

— 1

0

5

— 3

— 2

0

S2

X2

KPo)

Si =
Xi =

83 =
— z =

4 2
2 —.5
—2 .5*

12
6

—1

6 .5

—18

Old Matrix

New Matrix

^ These rules are derived in Appendix B.

8

In the new matrix the negative three has been eliminated, however, a
negative one has appeared in the S3 row. For the next pivoting process,
the S;} row will therefore become the pivot row, and the X2 column will
become the pivot column since it contains the only positive element
in the S.-? row. The third and final table.

Si =

Xi =

Xo =

z =

S2

S3

KPo)

—12

—4

8

0

-1

5

4

2

2

— 8

—1

—19

indicates that the solution is minimized at 19 ( — Z = — 19, therefore Z
=: 19 I . All negative values in the last column have been eliminated and
the negative nund3ers in the bottom row indicate that no further min-
imizing can be accomplished. If, after eliminating all the last column
negative values, positive numbers exist in the bottom row, the matrix is
further iterated by choosing the pivot column and the pivot row in the
manner described on page 3.

Summary of Rules for Determining Pivot
Rows and Pivot Columns and the
Pivoting Operation

Once the constraints for an L. P. problem are set up in inequality
form, they are made into equalities by adding or subtracting slack vari-
ables. These equality constraints are then restated in terms of the posi-
tive slack variable, and set up in the following matrix form:

X2

KPo)

Si =

82 =

0

To the bottom row of this matrix, the objective function is added. If the
objective function is to be maximized, it takes the form: Z =r X^ -|- X2
. . . X„ . If it is to be minimized, it takes the form: — Z ^ — Xj
— X2 — ... — X n . The objective solution is initially zero.

I. If any negative figures appear in the last column:

Rules for Removing Negative Resources

Neg-1. The row in which the negative figure appears is the pivot
row.

Neg-2. The pivot element must be positive.

Neg-3. The pivot column is arbitrarily chosen.

Neg-4. If there are two or more negative numbers in the- last col-
umn, then, using the arbitrarily chosen pivot column, Q-
values are generated for each row containing a negative
number. The row with the largest absolute value of Q will
be the pivot row (all Q's will be negative since the poten-
tial pivot element must be positive and since only the nega-
tive last row numbers are of concern).

II. Once the pivot row and pivot column are determined, the pivoting
process develops a new matrix by:

10

Pivoting Rules
PR-1. Changing the old pivot element to its reciprocal value.

PR-2. Changing all other elements in the pivot column by divid-
ing them by the old pivot element.

PR-3. Changing all other elements in the pivot row by dividing
them by the old pivol element and giving them the oppo-
site sign.

PR-4. Changing all other elements by subtracting from them the
value derived from the "rectangle rule" (see PR-4, page 4) .

This process of determining the pivot row and column and pivoting
matrix is
last column.

the matrix is continued until all negative values are eliminated from the

III. When this is accomplished, or when the initial matrix does not
contain negative values in the last column, and when positive values are
contained in the bottom row (excepting the solution box), the pivot
row and column for successive pivoting processes are determined as
follows :

Rules for Determining Pivot Columns and Pivot Rows

Pivot Column: The column with the largest positive bottom element
and which contains a negative potential pivot element
becomes the pivot column.

Pivot Row: Q-values are generated for all rows where the potential
pivot element is negative. The smallest absolute value of Q
determines the pivot row (it is obvious that again all
values of Q will be negative) .

Once the pivot row and column have been determined, the pivoting
process continues as previously described (see II, page 10).

This method (III) of determining the pivot row and column, and
the pivoting process (II) are continued until only negative values are
contained in the bottom row. The problem is then solved.

11

Equality Constraints and No Solution

Situations

There are two items that warrant hrief coverage due to their special
handling in the specific technique described herein.

The Equality Constraint

Because this technique does not use artificial varial)les as do the
more conventional methods, it is recommended tliat the equality con-
straint he handled as two opposite inequality constraints, adding and
subtracting slack varialiles wliere indicated. Handled in this manner,
one of the two slack variables will equal zero in tlie final solution.

It is also possible to use one of the unknowns as if it were a slack
variable. In the constraint X^ -f X^ = 100, for example. X, or X^
could be used to absorb the "unused" portion of the 100, thus developing
the constraint: Xj = — X2 + 100.

Now that Xi has been "solved" (in terms of Xo ) , however, it be-
comes necessary to restate all other constraints (that contain X, ), and
the objective function, in terms of X2.

In our example problem, the constraint 2Xi + 8X5 — 24, becomes
2( — Xo -\- 100) -|- 3X2 — 24, and the representative equality becomes:
Sj =r — X2 — 176. The objective function. Z = SX^ -(- 2X0 max.) be-
comes X = 3(— X2 + 100) + 2X2, or Z = — Xo + 300. and the ini-
tial solution is no longer zero but 300.

An equality constraint handled in this manner reduces the number
of constraints by one, and reduces the number of iterations by two, but,
as is quite evident, requires a great deal more time in setting up the
problem.

This increased "set up" time and the increased probability of mak-
ing simple mathematical errors while restating the constraints and ob-
jective function, appear to the authors as justification for handling an
equality constraint in the first described manner. Therefore, unless the
cost of the additional "solving time" is prohibitive, or the additional re-
quired constraint causes the problem to become too unmanageable, it is
recommended that an equality constraint be handled as two opposite
inequality constraints.

The "No Solution" Situation

The two most common "no solution" situations that occur in an
L. P. problem are: (1) when a function is to be maximized, but there
is no upper-limit constraint ("unljounded solution"), and (2) when

12

two or more constraints contradict each other ("mathematical incon-
sistency") .

When either of these situations occur following this technique, defi-
nite and unique events will stop the iteration process. If a maximum
objective is called for when no upper limit is set hy the constraints, the
matrix-iteration process will run into a dead end hy having a positive
value in the l)ottom row. indicating that the solution can he made larger,
and positive values in tlie last column, but there will be no negative
elements to qualify as a pivot element (negative Q-values cannot he gen-
erated I .

If two or more constraints contradict each other, the pivoting pro-
cess will dead-end hecause a negative value will appear in the last col-
umn, but there will be no positive element to qualify as a pivot element
(again, no negative Q-values can he generated).

Thus, tests for "l>oundedness" and mathematical consistency are
built into this technique. In the accompanying computer program (Ap-
pendix A), error messages to this effect are included.

Computer Program

A Fortran II program for this L. P. problem solving technique is
presented in Appendix A.

It is arljitrarily dimensioned for a 14 x 14 matrix which wovild be
the maximum size prol)leni that could be run in a 20,000 unit storage
capacity computer if numerical tables and/or other management rou-
tines have reduced the storage area to approximately 8.000 units.

The output gives the initial matrix, the activities being pivoted and
the objective function for each iteration, the final solution activity
levels, the final objective function (solution) and the shadow prices.

Selected References

(1) Bauniol, William J., Economic Theory and Operations Analysis.
(Englewood Cliffs; Prentice-Hall Inc., 1961).

(2) Heady, Earl O. and Wilfred Candler, Linear Programming Methods.
(Ames: The Iowa State University Press, 1963*.

(3) Stiefel, Eduard L., An Introduction to Numerical Mathematics.
(New York: Academic Press, 1963).

(4) Vajda, S., An Introduction to Linear Programming and the Theory of Games.
(New York: John Wiley & Sons, Inc., 1960).

(5) Vajda, S., Mathematical Programming.

(Reading, Mass.: Addison-Wesley Publishing Company, Inc., 1961).

13

APPENDIX A

Fortran II
Computer Program

COMMENT- THIS PORTION OF THE PROGRAM READS IN
THE PROBLEM DATA AND PRINTS IT OUT IN TABLE FORM,

DIMENSION A(14,14), KR ( 1 4 ) , KG ( 1 4 .'i
30 FORMAT (1615)

40 FORMAT (IH ,39H NO SOLUTION, CONTRADICTING CONSTRAINTS///)
50 FORMAT (IH , 32H NO SOLUTION, INFINITE OBJECTIVE///)
60 FORMAT (IH , I 5 , 7F 1 0 . 4 )
70 FORMAT (IH , 1 OX , 2 I 1 0 , 5X , F 1 0 . 4 )
80 FORMAT ( 1 HO » 5X , 7 I 1 0 )
90 FORMAT ( 8F 1 0 • 4 )

READ 30* M, N

DO 1 I = 1,M
1 READ 90,(A(I,J), J = 1,N)

READ 30, (KR( I ) , I = 1 ,M)

READ 30,(KC(J), J = 1,N)

PRINT 80, (KC(J), J = 1,N)

DO 2 I = 1 ,M

2 PRINT 60, KR ( I ) , ( A ( I , J) , J = 1,N,
MI = M-1

NI = N-1

COMMENT- THE FOLLOWirJG STEPS ASK THE QUESTION,
IS THERE A NEGATIVE VALUE IN THE LAST COLUMN.

3 DC 4 I = 1 , M I

IF ( A( I ,N) ) 5, 4, 4

4 CONTINUE
GO TO 11

COMMENT- IF THE ANSWER IS YES, THE FOLLOWING STEPS
DETERMINE THE APPROPRIATE PIVOT ROW AND COLUMN,

5 0 = 0.

DO 1 0 J = 1 ,NI

DO 9 I = 1 ,MI

IF (A(I,J)) 9, 9, 6

6 IF (A(I,N)) 7, 9, 9

7 IF (Q - A ( I ,N )/A( I , J) ) 9, 9, 8

8 0 = A(I,N)/A(I,J)
KROW = I

KCOL = J

9 CONTINUE

IF (Q) 20, 10, 20
10 CONTINUE
PRINT 40
GO TO 95

COMMENT- IF THE ANSWER IS NO, THE FOLLOWING STEPS
ASK THE QUESTION, IS THERE A POSITIVE VALUE IN
THE BOTTOM ROW,
= 0.

14 J =1 ,NI
(A(M,J)) 14, 14, 12
(QT - ACM, J)) 13, 14, 14
= A (M, J )
KCOL = J

14 CONTINUE

IF (QT) 95, 95, 15

COMMENT- IF THE ANSWER IS NO, THE PROBLEM IS SOLVED
AND THE SOLUTION IS PRINTED OUT,

IF THE ANSWER IS YES, THE FOLLOWING STEPS DETERMINE
THE APPROPRIATE PIVOT ROW AND COLUMN,

15 0= -99999999,
DO 18 I = 1 .MI

IF ( A( I ,KCOL) ) 16, 18, 18

1 1

QT

DO

IF

12

IF

13

QT

16 IF (Q - A( I ,N)/A( I ,KCOL) ) 17, 18, 18

17 O = (A( I ,N)/A( I ,KCOL) )
KROW = I

18 CONTINUE

IF (Q + 99999999,) 20, 19, 20

19 PRINT 50
GO TO 95

COMMENT- ONCE THE APPROPRIATE PIVOT ROW AND COLUMN
ARE DETERMINED THE FOLLOWING STEPS ARE THE
PIVOTING PROCESS. THE OPERATION THEN RETURNS
TO THE FIRST QUESTION (STEP NO. 3).

20 KEEP = KR(KROW)
KR(KROW) = KC(KCOL)
KC(KCOL) = KEEP .
DO 23 11= 1 ,M

IF (II- KROW) 21, 23, 21

21 DO 23 JJ= 1 ,N

IF (JJ- KCOL) 22, 23, 22

22 A(II,JJ) = A(II,JJ) - ( A(KROW, JJ)*A( I I ,KCOL) )/A(KROW,KCOL)

23 CONTINUE

DO 25 11= 1 ,M

IF (II- KROW) 24, 25, 24

24 A( I I, KCOL) = A( I I ,KCOL)/A(KROW,KCOL)

25 CONTINUE

DO 27 JJ= 1 ,N

IF (JJ- KCOL) 26, 27, 26

26 A(KROW,JJ) = (-1 . )*(A(KROW, JJ)/A(KROW,KCOL) )

27 CONTINUE

A(KROW,KCOL) = 1 . /A ( KROW , KCOL )
PRINT 70, KR(KROW) ,KC( KCOL ) , A ( M,N)
GO TO 3

COMMENT- THE FOLLOWING STEPS PRINT OUT THE FINAL

SOLUTION AND END THE OPERATION.

95 DO 96 I = 1 ,M

96 PRINT 60 , KR(I),A(I,N)
DO 97 J = 1 ,NI

97 PRINT 60 , KC(J),A(M,J)
END

Data Cards

The preceding program calls for data cards to be arranged in the
following order; each punched according to the indicated format.

/code nos. or letters for unknowns (Xj, X2, X3, etc.) and the resource Col.
/code nos. or letters for slack variables (8^,82, 83, etc. and Obj. Funct.)

objective function
/etc.

etc.

third row etc.

second row of original table

first row continued (if necessary)

first row of original table

/number of rows

number of columns

18

APPENDIX B

Algorithm Rules
Derivation

Appendix B

Derivation of Pivoting Rules and
Pivot Row and Column Selection Rules

I. Pivoting Rules

The pivoting process is a method of solving simultaneous equations.
By algebraically solving two such equations and following the steps with
the coefficient matrix, rules for the pivoting process are developed.

Given: two general equations, and the corresponding coefficient
matrix :

Si = aXi + bXa + ki
S2 = cXi + dX2 + k2

Si =:
S2 =

a b
c d

ki

k2

The first step is to solve for Xj and S2 (in terms of X2, Si, a, b, c, d,
ki and k2). The column headed "Xj" is the pivot column. The row
headed "Si" is the pivot row. The element at the intersection is the
pivot element.

Solving for Xi :

aXi ^ Si — bX2 — ki

Xi = l/a(Si) — b/a(X2) — ki/a (Equation 1)

Solving for S2 :

S2 = c[l/a(Si) - b/a(X2) - ki/a] + dX2 + kg

S2 - c/a(Si) — c(b/a) (X2) — c(ki/a) + dXs + k2

Combining terms —

S2 = c/a(Si) + [d — c(b/a)] X2 + [k2 — c(ki/a) ] (Equation 2)

Equations (1) and (2) yield the matrix:

Si X2 1

Xi = ■"

S2 =

From this, four rules can be drawn for the pivoting process:

PIVOTING RULES

PR-1. The pivot element (a) becomes its reciprocal value (1/a).

PR-2. The other elements in the pivot column (c) become them-
selves divided by the pivot element (c/a) .

PR-3. The other elements in the pivot row (b and k^ ) become
themselves divided by the pivot element and given the
opposite sign ( — b/a and — kj/a).

PR-4. Each element in the remaining part of the matrix (d and
k2 becomes itself less the quantity derived by multiplying
the element in the same row and in the pivot column by
the element in the same column and in the pivot row, and
dividing this product by the pivot element: d — c(b/a)
and k^ — c(ki/a) .

These rules may be checked by completing the solution, that is,
exchanging S2 and Xo, thus solving for the X's in terms of the S's.

II. Determining Pivot Rows and Pivot Columns

Given: the generalized coefficient matrix:

Xi Xo Xo ... Xq ... Xn l(Po)

s„-=

'pq

Sv =

k.

C^

(Initially
C* = 0)

21

In this generalized matrix, Sp is our eventual pivot row and X q
is our eventual pivot column (i.e. a p, is our eventual pivot element).
There are two requirements on which we will insist:

A. Only solutions that are acceptahle values will be considered

(Xi ^0, X2 ^0, ...X„ ^0, 81^0,82^0 S^^O),

therefore, the C's (last column values) must remain or become

B. During each exchange, C* (the objective solution) must in-
crease (at least not decrease).

IF ALL C'S ARE NON-NEGATIVE

From the above requirements and the pivoting rules (assuming all
C.s are non-negative), three conclusions can be drawn:

1-1. 8ince Cp -^ (becomes) — C,, /pivot (pivoting rule #3),
which must remain ^s:0, we must choose a pivot element
that is negative.

1-2. 8ince C* — » C* — (Cpaq)/pivot (pivoting rule 4^4), which
must be non-decreasing, we must choose a pivot column so
that the quantity (CpEq ) /pivot is — 0, i.e. aq must be posi-
tive.

1-3. Since Ck — > C ^ — (Cpakq ) /pivot (pivoting rule 1^4:) which
must remain :^0, we must choose a pivot row so that C,^^^
(Cj. aikq ) /pivot.

Conclusion 1-3 is automatically satisfied if a^^^ ^^ 0.

However, if there is more than one a jq in the pivot column which
is negative, we will gain by being more cautious.

Suppose a ^ is negative, then Conclusion 1-3 can be written:

Ck /a k,j ^ C p /pivot, or C k /a kq ^Cp/a

pq

If we call C^/an,,| , "Qn," (the kth "characteristic quotient"), then the
gain comes by choosing the pivot row so that Q ], is the largest of the Q's,
for this will prevent any of the positive C's from becoming negative.
Since the Q's in which we are interested are all negative, we can con-
clude that our pivot row is the one which has the smallest absolute
value of Q.

From these three conclusions, three rules can be made for deter-
mining the appropriate pivot row and pivot column for the pivoting
process if all C's are non-negative.

22

Pivot element: The pivot element must be negative.

Pivot column: The bottom element in the pivot column must be
positive.

Pivot row : Among rows with negative a i,, 's, the pivot row is the
row which has the smallest absolute value of (}.

IF SOME C'S ARE NEGATIVE

A linear programming problem that contains greater-than-or-equal-
to constraints will have negative values appearing in the last column
of the initial table. These negative values must become non-negative
(see requirement A, page 22). Given this situation and considering
the pivoting rules, three conclusions can be drawn:

2-1. Since we are only concerned with the negative C's, only rows
with negative C's will be considered for the pivot row.

2-2. Since C ,, — ^ — C ,, /pivot, we must choose a positive pivot
element (i.e. a ,„, > 0).

2-3. If there is only one row that contains a negative C and at
least one positive element in that row, there is no problem
of determining the appropriate pivot row and pivot column
for the pivoting process (the choice of a pivot column is ar-
batrary). However, if there are two or more rows containing
negative C's, we will gain by being cautious.

Suppose that C ^^ is negative and a i^q is positive (see generalized
table page 21) .

Since C I, -^ C ^ — (C ,, a k,, ) /pivot, it would be desirable if
(C|, a kq ) /pivot were ^ C k since this would cause Ck to become
non-negative also. This can be modified to read : C p /pivot — C ,^ /a kq
or Cp/a^^i i^ Ck/akq or even further Qp— Q^. Since again the Q
values we are dealing with are all negative, we can conclude that we
would gain if the pivot row is one which has the largest absolute value
of Q.i

From these three conclusions (2-1, 2-2, and 2-3), four rules can be
made for determining the appropriate pivot row and column for the
pivoting process if some C's are negative.

^ It is possible that a previously non-negative C may become negative during
a pivoting process. This is of no concern, however, since it will eventually be
eliminated in the same manner as the other negative C's.

23

Neg-1. Only rows with negative C's will be eligible for the pivot
row.

Neg-2. The pivot element must be positive.

Neg-3. The pivot row is the row which has the largest absolute
value of Q.

Neg-4. The choice of a pivot column is arbitrary, provided the
first three rules are satisfied.

24