10.1.002_Linear_Programming_Code_for_the_IBM_1620_with_Card_Input_and_Output 10.1.002 Linear Programming Code For The IBM 1620 With Card Input And Output
10.1.002_Linear_Programming_Code_for_the_IBM_1620_with_Card_Input_and_Output 10.1.002_Linear_Programming_Code_for_the_IBM_1620_with_Card_Input_and_Output
User Manual: 10.1.002_Linear_Programming_Code_for_the_IBM_1620_with_Card_Input_and_Output
Open the PDF directly: View PDF 
.
Page Count: 156
| Download | |
| Open PDF In Browser | View PDF |
~
W
1620 GENERAL PROGRAM LIBRARY
Linear Programming Code for the
IBM 1620 with Card Input and Outpu t
10.I
_
~
*Jt********* ~\*
+I. *********~$
~iJ ***********
*************
*************
*************
*************
*************
./t~~)*********9*
•
o
o
o
\.
I'
,
I
"
,. ,mtettftrihttti±fri"tit""w."Yt !"d,rittriHHrtIt'"hh#t*riIWtn
n""U"'U'KTflT"""j"j
fHttti!H&tit
ap"
i
,'to!'""
•
Linear Programming Code for the IBM 1620
with Card Input and Output
o
R. Dietz
IBM Corporation
Queens, New York
Modifications or revisions to this program, as they occur,
will be announced in the appropriate Catalog of Programs
for the IBM Data Processing Systems. If such announcement indicates a change to the program decks or tapes, a
complete new program, if needed, should be requested
from the Program Distribution Center.
~-"---""."""""''''''''''''''''-''''-'''"'''''''''.~'''.'
...................... ,,,. -............ ..........
-~
~~-~--------
•
o
o
C'·
,
I
Aclmo1.Jledgement
This ~rogram is a modification of one for the basic
1620 with naper tape input and output written by
C. R. Nichols, m~f, Inglewood, california. The only
changes made were those necessary to enable his
}1Uch. of the
information in the writeup is taken directly from
hi S v-lri teup •
program to be used \..,.1 th a card 1620.
o
0';"
I"~
TABLE OF CONTENTS
I.
II.
Program description
1
A.
Machine requirements
1
B.
Error stops
2
4
4
The program
A.
-operating instructions
TO lo-ad in! tia1 data
To solve a.ndobtain output
4
5
5
5
Data preparation
6
Natrix data
6
co s t -cha.nge s
8
TO effect cost changes
TO effect
B.
requi~ement
Requirement
c.
D.
changes
ch~nges
9
Interpretation otresults
9
cost or requirement changes
9
Dual or simp1exalgor1thms
9
Final basis output
10
Final non';;'basis output
10
Ilfatrix punehout
11
FUnctions'o-:r individual sub-p,rograms
11
Data 1oad,rou:t:lne
11
cost change routine
11
Requirement 'change r:outine
11
,Shadow
o
pri.c~c,alc'U.l.ato~
o
11
o
'""·"KI"
IW&fd+ri b9.bi' "MtiNM;+H&IJt r In
"If!
'Jj
Dunl algorithm
11
Sl:mplex algorithm
12
Final basis output
12
Non-bnsis output
12
t-fatrix punch routino
12
E.
Use of storage
12
F.
Makeup of program decks
13
G.
stora.ge of matrix in memory
Jl~
C:
III.
sample problem
A.
Matrix
15
B.
Hatrix in storage
15
c.
Input
15
D.
0
IV.
v.
0
lS
1.
Fixed point
15
2.
Floating point
15
output
16
1.
Final matrix punched
16
2.
TYPewriter output
16
l\Tethod of loading program
16
Flow charts
17
A.
Genera.l flow cha.rt
17
B.
Data. loader
19
c.
cost changer
22
D.
Requirement changer
24
E.
shadovl price calculator
27
F.
DUa.l algorithm
31
G.
Simplex algorithm
35
H.
Final basis output
39
~~------~----"-.-""'------'--'---'-".""'"''''''''''
VI.
I.
Fix subroutine
41
J.
Non-basis output
K.
Matrix punch routine
A.
Data loadex-'
43
45
46
46
B.
cost ,ohanger
~.8
c.
Requirement changer
D.
solution deck
49
51
Listing of program decks
C
o
o
±W"W"·'¥fW'· *W·Mii"··w·'Ifi*r- ¥%b
T
I±iflndd·· .. ithT
r,
iij'ifiU¥
I
t
T..
o
PROG RA lVl DESCRIPTION
This program solves linear progra..rmning problems Hith
output of detailed results. That is, given coefficients ai1, cost coefficients OJ, and requirements
bi' dete~ine Xj such that
~
9.1 jXj • bi
,d th Xj
~0
..J
and
~ cjXj
=
ma.ximum
J
computations are performed by the DUal Algorithm until
a feasible solution is obtained. Control 1s then given
to the simplex Algorithm for optimization. cost changes
and requirement changes can be made after loading
origina.l matrix or after solving origina.l ma.trix.
A.
requirements
~nchine
1.
Basic 1620 'toJ'ith card input and output.
2.
size storage can be used. The larger the
storage, the larger the problem that can be
solved. The size of the problem is restricted
by the follo'Vring relationship:
o
~ny
(m
+ 2)
(n
+ 3)
L memorl - 3920
-
-10-
where:m is the number of restrictions
n is the number of non-basis indenendent
varia.ble s
----
-
memory is 20,000, 40,000, or 60,000
3.
o
Source language:
actual ma.chine language
td th program.
subroutines:
floating point subroutines supplied
No other subrou·t;ines needed.
5.
Input media:
card reader and console
6.
output media:
7.
RUnning time: The precise time required per
iteration depends on the size and density of
the matrix. As an approximation, e. problem
loll th 30 equations and 40 non-basis variables
requires about 20 seconds per iteration.
8.
Decimal accuracy: All computations arc perro~ned
in 2-and-8 floating point form. lYIatrix input
can be a1 ther fixed point or floa'i:iing point.
typewriter~
card punch and console typewriter.
• • • , .",."' , "", .'''':''' .... , ...... , ....
~_'''''- ....... ~J'" ..... ,., ....... ''-"'-' ............. ' - . - ' '... -
... "" ........
'~ ....... ~,.:., "".,..."".".......,"," "
.. " , "
,"
,.,,~~,',
'"
.. " ...
~"'''"'''''.
-2B.
!nOr stopa
1.
All stopa MaY be recogn1zedby displaying
IR-l in MAR. MAR will contain the address
ot the halt instruction plus 12 •.
.
Halt instl'.·
Reason
F1oat.1ng point overflol-l
Floating point attempted d1vision
by zero
Loader - ready for next code
cost changer- Change entered tor
a non-existent identification
number
Cost c~o.nger - ready for next code
RHS changer - change enterod for
a nO'n-existent .identification
number
RHS changer - ready tor next code
DU.a.l algorithm - inconsistent matrix
Simplex algorithm - unbounded solution
f.1atrix ,pWlch - ready for next code
01126
01288
00012
02458
00012
0,3110
00012
02531.~
02654
02838
2.
o
Error procedure
a.
cost.
cha.nger(02~.58).
Erroneous 1dentiflc'at1on
number is the last one typed.
It data are being entered through the type,.
l.f!'i tel',
Type
depres s RESET and INSERT.
.
.
49 02126.·
Depress RELEASE and START.
corrected or new change data may now be
entered no~alli.
If data are being entered from caI'ds, the
erroneous datum may be ignored by following
the same steps as above (tor ent,..,. through
type~rr1 te r ) •
It it 1s des1re:d, to entorthe change cOrr8'ctl,.
through the t'Y'Pewr1ter, the following stepa
MUS t be to.l<:en:
set console sw1tcb two on.
Decre a's RESET and Il'lSERT •
4902126.
'me
DenressRELEASE and START.
Enter COrlt'8ct datum t~ou.gh type,writer
(compl.ete with record mark).
'DeprelsRELEASE and START.
~"'hen
typewrl tel' isagaln se,le"cte4, depress
RESET.
sateonsole sl-11tch two ott.
o
-3Depro s s
INSEn';1.~
. :'~~~ .~..,~:~\ SE, and START.
PJ:'ocesning 1·,Til~. '~!.'
ccnt:Lnue normally,
rea.d:lng data from cards.
'i
RHS Changer (03110):
Erroneous identification
number is the last one typed.
If d!.lta. a.rc bcinB entered through the type'tJ'ri ter, de~)ress R.BSET and INSERT.
Type 1.t9 02126.
Depress REL&\SE and STAPT.
Corrected or ne't-l change data may no,., be
antered norma.lly.
If de. teo are be ing entered from cards, the
erroneous da.ta ma.y be ignored by fol1oN'ing
the same steps e.s above (for entry through
tynowr1 te r ) •
If it is desired to cnter the change correctly
through the typeV1ri ter, the follo'tvinrs step s
mus t be tal{en:
set console s"VTi tch three on.
Deuress RESET and INSERT.
~ry~e h9 O?126.
Denre s s HEI..EASE anti START.
o
Enter correct identification ntunbor
(4
digits
plus record mark) through typewriter.
Depre ss RELEASE and START.
Enter requirement change (including record
mark) through type'Hriter.
Gepress RELEASE and START.
typewriter is again selected, depress
RESET.
;)et console sHitch three off.
~1hen
1)e'..,ress INSERT, RELEASE, and START.
Processing Hill nOl'1 continue normally, reading
data from cards.
c.
Dual algorithm (02534): TO obtain solution
existing at the time of discovery of inconsistency:
RUn out cards from reader.
Replace cards in reader hopper starting with
Final Basis cutput program.
Depress READER SirART.
Depress RESET and INSERT.
TYPe
49
00024.
Denress RELEASE and START.
d.
o
simplex Al~orithm (02654): To obtain solution
existing at the time of discovery of unbounded
solution:
-4Denress RESET and INSERT.
TYPe 1.1.9 00024.
Depress RELF..!ASE and St.rART.
e.
OVerflow-underflow: Overflow causes a
stop at 01126 or 01288. Underflol-l causes
the result to be set to zero, and pro.cessinp; continues. Either condition indicates
either rnachine malfunction or unreasonable
data.
t.
II.
A.
Any other error:
Restart problem.
unrecoverable.
THE PROG-PA}1:
Operation Instruotions
1.
set type\Olri ter margins at 12 and 92; tabs at
21.1-, 36, 48, 60, and 69.
2.
It is important to note that no mOl")e than one
instruction at a time may be inserted at e:ny
time after the initiation of the Loader routine.
3. To load initial
a.
data:
Ready the LOADER deck in the card reader
(including matrix input data).
R.'R.~DER
i
-
Depress
START.
b.
Depreos RESET and INSERT.
c.
Type 16 00010 00000.
d.
Depress REIPASE and START.
rfl,1.1s initiates memory clear' routine.
e.
After at least one seoond, depres:s INSTANT
STOP, RESET, and INSERT.
r.
Type 36 03826 00,00
g.
Depress RELEASE and
h.
o
49 03826
S~RT.
Prog:raaln deok loads, data are loaded, and a
halt at looation 00012 is exeouted. Operation may nO\v prooeed to the COST CHANGER,
RHS CHANGER, or SOLUTIO~T programs.
o
-5-
o
4.
TO effect cost changes:
n.
Ready the COST CHANGER deck in the card
reader (including data change cards if
changes will be made from cards). Depress
READER START.
5.
b.
set console s\J'i toh two off if' cost changes
will be entered from carn-reader; switch
two on if data will be entered through the
typewriter.
c.
~epress
d.
If data arc entered through the typewriter,
RELEASE and START must be depress·ed after
each entry. (Don't forget the record mark
to terminate each entry.)
e.
After all data are entered a halt at location
00012 is executed. Operation may nOvI proceed
'(;0 the RHS CHANGER or SOLUTION programs.
To effect requirement changes:
a.
o
START.
Ready the RES CHANGER deck in the card
reader (including data change cards if
changes Hill be made from cards). Depress
READER START.
set console switch three off if reauirement
changes will be entered
card reader;
switoh three on if data will be entered
through the typewriter.
from
c.
Depress START.
d.
If data are entered through the typewriter,
RELEASE and STAR~ must be depressed after
the entry of eaoh identification and each
change. (Don't forget the record mark
to terminate each entry.)
e.
After all data are entered a halt at location
00012 is executed. Operation may now proceed
to the C03 r CHANGER or SOLUTION programs.
1
6.
o
To solve and obtain output:
a.
Rea.dy SOLVER deck in the card rea.der.
Depress READER START.
b.
set console awl tch one on t~o type i tara tions,
off to omit iteration typeout.
-6c.
set console switch .four on to obtain 'Duric-hout of final matrix, orf~o suppress punching.
B.
o
-
d.
Depress START.
e.
After all output is complete, a halt at
location 02838 will be executed. Operation
may now proceed to the LOADER, COST CHANGER,
or RHS CHANGER programs.
Data Preparation
1.
The first card to be entered is a case identification
card. A five digit alphabetic idefiIrr1catlon
1s punched in columns 1 through 5. columns 6
through 80 are blank.
2.
The second card specifies the size of the problem
being entered. It is punched as follows: -
-
..
Information
..........
o (zero
card columns
with a minus sign)
1
number of equations (3 digits)
2 - 4
Q (zero)
o (zero with a minus sign)
number of non-basis variables (3 dig.) 7 - 9
10
o (zero)
input oode
11
a.- 1 for row-column, fixed point
input
b. 0 for a complete floating point
matrix
g
columns 12 through 80 are blank.
The matrix ean be entered in one of two forms;:
floating point (the entire matrix is entered,~:
oolumn by column, exaotly as it is to be stoNd,
including zero entries) or :fixed point (entries
oan be in any order, aacompanied by the1.r respective row-oolumn designations, and zero elements need not be entered).
For floating point entry, eight elements are
punched on each card, with a minus sign over
the first position of eaoh ten position field,
and a minus sign over the last lJositlonof
negative fields (units position). '!9;l.ereare ten
positions per field, with the first two positions
specifying plaoement of the deoimal point <$0
designates a decimal point to the lett of the
-------
-~--
o
IIPP'
J
*WHlf'
-7-
;.~
o
first non-zero digit; 51 designates one nonzero digit to the left of the decimal; 49 designates thnt the first non-zero digit is in the
hundredths position, etc.) and the last eight
digi ts (vIi th no leading zeroes) giving the
element itself. A zero element is specified
by ten zeroes, with a minus sign over tho first.
The elements must be punched in column order,
starting with the first basis cost. See the
matrix layout included with this writeup to
know hO'tfT the elements are stored In the matrix.
:5.
Fixed point matrix elements are entered four
to a card.
types of cards are necessary
THO
fOl')
matrix
elements:
a.
RO'ti-colu1'nn cards designate where the elements
1,)'i11 be stored in the rna trix. .Rov-I-column
designations are punched in colu.lnns 1-6"L.
21-26, t~1-46, and 61-66 in tho form RRHGCC
(8. minus sign accompanies the first digit
of each rOH and column designation). The
collLYfln de signa tion specifies collu11l1 number
considering only non-basis vectors. The
requirement x.ariables have only a rOll designation, and 000 should be entered for their
coltunn.
b.
r1atrix element cards contain fixed-point
entries including optional leading sign,
up to eight numeric digits, and mandatory
decj.mal point. Each entry must be terminated
by a record mark (0-2-8 punch). The four
elements are punched begimling in colurnns
1, 21, hl, and 61 for each card.
o
Elements may be entered in any order, but corresponding row-column designations and matrix
entries must be in the same nositions of successive cards (roH-column ca.rd preceding).
!
Loading of zero elelJlents
-..
..
.
-
. -
1~
optional
....
~
•
If any card contains fewer than four elements,
the first blank field (column 21, !~l, or 61)
of the rOlv-column card must be punched with a
o
record mark (0-2-8 punch).
-
n· ".
-8~
Description
Row-column
matrix element of the ith row
and jth non-basis vector
..
I
element in the ith row of
the requirement vector
6.
o
, .... A..-,
xxx(ioo
Fixed point cost entries are also four per card,
but the row-column designation is on the same
card as the cost.
Entries consist of a six digit row-column designation followed by a ten digit ID/cost, vlhere
the ID is a four digit numerical designation
to identify theoost variable, and cost is a
six digit fixed point entry wi'th the decimal
after the third digit.
~
°i
ROvl-co1wnn
Description
cost per unit of basis
variable for row 1
cost per unit of jth
non-basis vector
.:rD
I
r~-"
0:.:. 'So r
~~
xxx()OIXxxmxxxx
. .,;
ru
cQ$;-
~~~
oolXxxxxxxxxxxxx
Negative cost is signified by a minus sign over
the units position of the cost field.
If any card contains rewer than four elements,
the first blank field (column 21, 41, or 61)
of that card must be punched with a record mark
(0-2-8 punch).
The last data entry for fixed point mode illu.at
be 000 to terminate the loading operation. This
can be ptUlohed in columns 1-3 of a nel.J' card,
or in 21-23, t,.1-43, or 61-63 or the last rowcolumn or cost entry card.
8.
Entry of cost changes:
Data for the COST CHANGER routine oan be entered
either from cards or from the typewriter. If
entered from cards, one entry is punched in
each card, in oolumns 1-10. The entry cObsists
of the four digitID and six digit cost figure,
'tli th a minus sign over the first dig'it of ,the . ~.
cost (columnS) and over the last digit of negative
costs (column 10). pol1owing the last cost
change card mttst be a cflrd punched with four zeroes
(columns I-L,.) to terminate the operation.
o
-9-
c
If antered from the typewriter, the format is
the same as from cards: fOUl" digi t ID and six
digi t cost figure 1.v1 th flag over the firs t digi t
of all cost figures, and over tho units position
of negative costs. The last entry must be four
moroGs to terminate the operation.
9.
Entry of requirement cha.nges:
~ere are two entries for each requirement ohange:
the identification and the change in the value
of that requirement element. note that the
now requirement element is not entered, but
rather the difference between the old and new
requiremen.t elements. If changes are entered
from cards, the identifioation and ohange are
entered on separate cards, one per card.
The identification is entered first, and consists of the ID associated with the cost element
.for that roVI. Thus, to change bi • b3, use the
ID associated with ci = 01. No flags or record
marks are needed in entoring the ID either
from cards or typewriter. It is punched in
colunms l-LI. of card entries, vlith 5-80 blank.
o
After entering the In, its associated requirement
chanec is entered (by typewriter or on a separate
card). The entry starts in colmnn 1, if a
card is being used, and oonsists of optional
leading sign, up to eight n~~eric digits, and
mandatory decimal point. It must be terminated
by a record mark, whether it is entered from
cards or from the typewriterc
The last entry must be four zeroes to terminate
the operation.
C.
Interpretation of Results
Cost changes or requirement changes are typed
if the input is from cards. If input is through
the typewriter, the input operation itself
produces a log of the changes made.
2.
o
DUal Algorithm and Simplex Algorithm:
Results of iterations are typed only i£ console
switch one is on. If it is desired to monitor
the course of the solution onlh occasionally,
this may be done by setting switch one on and
off periodioally.· The following points should
be borne in mind:
-10-
a.
b.
Page headings for iteration output are
typed only if switch one is on at the beginning of the solution.
The iteration count is reset tvhen the dual
algorithm is .finished and control passes
to the simplex algorithm.
The 1nfor--llation which may be typed includes
the iteration count, the current value of the
profit function (floating point), the last
variable to leave the basis, and the variable
which entered the basis.
3~
Final Basis Output:
The final value of the profit function is given
in floating point.
For each final basis variable, the £ollowing
information is supplied (in rixed point):
4.
a.
Ident1ricatio~/cost
'b.
Activity.
c.
The limits of the cost coerricient over
lvhich the current solution is optimal.
d.
The variables which limit the range of the
cost coefficient and will enter the basis
if a limit is exceeded.
coefficient.
Final Non-Basis Output:
For each non-basis va.riable, tho follo't-ling
information is given (in fixed point):
a.
Identification/cost coefficient.
b.
Shadow price - the penalty to the total
system if a unit of tIlls variable is forced
into the final solution.
c.
The limits of activity over which the shadow
price applies.
d.
The va~iables which limit the range of
applicability of the shadow prioe. The
upper limiting variable is the one which
would. leave the basis if -the ~i.ssociated
non-bq.sis variable were fo~oed into the
solution.
o
ii'rtJ"lWirHH±i+wit," 'ffli:i'&tIi&+iietLtiwHri,/"ttl "' 1"""2 ""UIIT"I!"
ff"TH
,nwilt'"' ,
-11-
j.
D.
A puncbout of the complote final matrix is optional under control of console svTi tch four.
The cn.rds punched also contain. all necessary
supnlementary information and are in a i'ormat
which is suitable for direct re-londi~~ by
the LeADER routine.
FUnctions of Individual sub-programs
1.
'I'he data. load routine reads and stores parameters
for the p!loblem. It then proceeds to load and
store the matrix in the proper format. In the
case of' fixed point input, storage locations
are computed from the row/column designa.tions,
and the input elements are converted to floating
point nota.tion as they are read and stored.
2.
The cost change routine reads ID/cost elements,
searches tho matrix for a corresponding identification number, and stores the new cost
coefficient in the proper locG.tion.
3.
The requirement change routine rea.ds variable
identification nwnbers and changes for the
associated requirement element. The change is
converted to floating point notations, the
matrix is searched for the identification nuniber, and tho requirement vector is updated.
Lt.•
The shadoH price calculator converts all cost
coefficients to floating point notation and
evaluates Zj-Cj for each non-basis variable.
o
~le dual algorithm computes a feasible solution
for the problem. Its operation may be monitored
allovJ'ing the typing of tho value of the functional
and the identifications of the variables that
enter into and are removed from the basis. It
should be noted in this regard that the objectives
of feasibility and optimality may not be compatible at this point, and therefore the functional
may actually decrease from one iteration to the
next 'Hhile the dual algori tbm is in control.
o
During the reduction of the matrix of coefficients
a test is made to detennine whether the resulting
quantity has a magnitude less than an amount
called "essential zero." Any element falling
into this category is set to zero in order to
avoid computation with numbers which are actually
not sisn1ficant. "Essential zero" has been set
to 10-. Its value (the corresponding floating
~oint exponent) is located in memory addresses
II.
'-123141~ and 3145 and may be changed if desired.
this change is made, it is important to note
that the high order digit must carry a flag.
6.
If
0
.
·,
,
The simplex algori tbm starts N'1 th any feasible
solution and computes the optimal feasible solution. Its operation may be monitored by allowing iteration typeout as in the ease of the dual.
algorithm.
The discussion of' essential zero as applied to
the dual algorithm in 5. above 1s equally valid
for the simplex algorithm. In this case the test
value is located in memory addresses 3264. and
326,5.
In the case of a tie in the quotient used as the
criterion for choosing the variable to leave the
basis on any iteration, the choice is resolved
by using the largest denominator as a secondary
criterion.
7. The basis output routine searches out and com-
putes the information described in section c.
above. Floating point quantities (with the exception of the funct5.onal) are converted to
fixed point before being typed.
8.
The non-basis output routine searohes out and
computes the 1n.fonnation described in section
c. above. Floating point quantities are converted
to fixed point before being typed.
9:.
The matrix punch routine resets the permanent
instructions in lOvl memory to allow re-initiation
of the input or ohange phases. Problem parameters
and the final matrix are punched into paper tape
if called ror by the setting of oonsole switch
fou!'.
E.
Use or storage
Memory locations from 00012 through 03919 are used
by the program.
Nemory from 0,3920 up to the required location is used for the matrix and its manipulation. Locations 00000 through 00011 are available for the insertion of one instruction at a time
through the typewriter. A halt instruction :tnposi~
t.ion 00012 ensures that only this ona instruct'ion
will be exeouted.
00012-0004?
oOOlL8" 00 058
00060-00064
load routine
case identification
S address
()
1'"][
tvart" ,..wuwtLb'iWiri"
'kO """r-"Rb" ""lU"i!!U
-13ooo65-no069
Oo070-ooo71~
00075-00079
00080-00099
00100-004°0
oOil. 0 2 -020 64·
variable
03758-03917
03920F.
1'1
and 2
N
M
product area
arithmetic tables
floating point subroutines
programs
input area (record mark in 03918)
matrix
Program Decks
1.
LOADER
3 nre-load cards.
Arithmetic tables.
?lonting point routines.
Data load routine.
!JT.atrix data to be entered.
2.
COST CPillNGER
2 nre-load cards.
Arl thrnetic tables.
Floating point routines.
Cost changer routine.
cost change data (if entered from cards).
o
3•
RHS C:IA jyrG ER
2 pre-load cards.
Arithmetic tables.
ploating point l~outines.
Requirement change routine.
Requirement change data (if entered from cards~
SOLUTION
2 pre-load cards.
o
Sh'adoH price calculation routine.
page headings.
2 pre-load cards.
Dual e.lgol"Ji t;hl11 routine.
2 pre-load cards.
Simplex algorithm.
2 pre-load cards.
Final basis output routine.
2 pre-load cards.
Fix and print routine.
Page hea.dj.ngs.
2 pre-load cards.
Non-basis output routine.
pa.ge headings.
2 Pre-load cards.
Natrix punch routine.
-14G.
storage of matrix in'memory
()
The matrix is stored in column sequence and uses
memory from 3920 upward to the' extent required by
the problem size. rrhe following diagram indicate,s
the manner in which matrix elements are stored:
39'20
S+lO(2m+3 )
S
;
F\ln'ctional
S410(2m+4>
S,+10 (m.,3)
s+10(2m+5}
,\tlorlcing
column
bi"
aij:
r
l
S+lo[+1J
Ino ~easing
i
~920+,'·
tJ;:O(m+l)
S-tlOm
S"10(2m+2)
"
S+10(.3m+4)
Sf-10[(nt 2 ) tn ~2)-2J
S is computed for each problem and 1s equal to 3920
All addresses are field addresses.
.. lO(m-t3).
c
'YB ...
'[ .... rr'
-
Wild'
-15-
01
III.
A.
SAHPLE PROBLEM
Matrix
Be.sis variables
"01
9992
1
0
Non-basis va.riables
0001
0002
Requirement
vector
variable
9902
ID
6
1
2
1
1
-1
-1
-10
1
1
0
-4
cost
I
B.
¥Atrix in stora.ge
'0000000000 0001001000 ~002001000 9902000000
o
'0000000000 ~OOOOOOOOO ~OOOOOOOOO 0000000000
~901000000 ;"160000000 5110000000 5120000000 '0000000000
9992010000 ;'.l.4000000?J ;110000000 5110000000 5110000000
c.
2 X3
Dlput
1.
Fixed point
IIOO",0000301
001001
'0"02'0"01
1.t
1.*
00 2lrO 0
~Ol 0~901000000
~O~03~902000000
~0~01~001001000
.1.
002i03
~4~~
!)o 2t5'O 2
1.+
'.
~0~02~002001000
(5'00
2.
Floating point
2 X 3
OO~000300
.B.~Q~Qn0..oQR9920 1 oooooo.o.oo.a.oooooooonOOOOQbI J 60000non~J 1 _·-&ES.
t
'-_
/,\
~D ID~C~~
I FROM CARD
'---.....,./
'1~~-~/~~!~1
I
J
TIP F~~M
.~IL ..
e "
:d
t~~~·
o
-2)-
COST CHArDER
Page 2
c
1 • i 1
1C
=K-l
SET
ADDRESS
OF
2
62
.0
,..---10.....-...1,"",2
j • j 1
K : K-l
STORE
NEW
COST
)
g. 1
o
m
lUIS CHAIIlER
page 1
_.
1.2.,
/
READ
NEXT
CODE
2286
READ
\
b
o.
FROM
CARD
S~DOW
10
PRICE
TYPE
b
SET'
SIGN
r.1INUS
SET
EXP =
$0
o
tfr!!ii¥rirtYflW··'U . ·· n W
1·]""1
PH""lf!M '" .. ·')"f!!"ft"n-""",,, tr·lm
RHS CHANGER
Page 2
SET
i • 1
o
.' ,2862
~-....'
,,"_
~
r SET9~
; PROPER
, SIGlT
SET k-m
;1 =
SET 1-1
®
mrs
CHANGER
page 3
112
SET kan
SET j=l
Pg. 1
_---....,/..086
=
j
j+1
k .. k-l
Pg. 1
o
-27-
SHADOW PRICE CALC.
page 1
o
___'""'\O
SET
ORK AR
_~
TO ZERO
o
SAVE k
o
r .
-28-
SHlDOW P RICE CALC,.
page 2
f!f Ulf'" PVW "!tt8'irllliWlibltt!!lWit",u
"j"
"r
PU" ',nf""i "qWiN,Q
-29-
SHADOW PRICE CALC
page
3
•
C"'·:
,"",
-------~
g. 2
0,
,',
o
,-,--'~"""".-~.-.-"""-"--.-"'-.~"
.. ,,- ..,,.""""'."".,.'""',",...,,,.,,""
""."""'"""'"'''-.~~-
-30-'
SHADOW PRICE
Page
4
CALC~,
o
_ ...........f-=L.'~2
j = j+1,
x • %-1
I-------..:I>~~,'
,2,,752
UPg.3
TYPE
HEADINGS
71
__ .__. QOD:&l~ "
t
"
DUAL .
AWORITHM
o
·
Iii
-t
i'
-.31DUAL AIDORITHM
Page 1
,
2=.::;1:::0=:::IIII:-
\SET°bm1n
• 0
SET x • •
~T
1 • 0
o
I.
"
SIMPLEX
AIGORITHM
o
j • j+1
,
..
'.'''--.'.''-''''''''''''''~."''-~
-'-.''.-'-"~-'-'.'-'-''-'---'''''''---'''-'~''.-'-'-''''''''''''.''''''''''''
. """,,,,,,",.,,..
,"~".,,~,
....
-~~
DUAL AIGORITBM
Page 2
TBmaz·R
VE arj ADDR.
()
(INCONSIS'l"ENT
MATRIX)
CALC.
1/8.rk
o
.. '''fI"srr!f!l5v<' . ~
or't'fl"tlll"i
DUAL AUlORITHM
page
1 • 1+1
x
%-1
=
SET j.iO]
SET ylltl
o
~--
. \arj~~rj/arkl
I.
j
'1
o
= 3+1
= ,.-1
3
-34-
DUAL A.WORITHM
page 4
o
1•
x
~~~~--------~
Og·l,
...
1-1
= %-1
SIMPLEX AlGORI'IIHM
-3$-
0
Page 1
1
o
.,r'"
.....",
( 2542 ).-..~-.---.-~.--...p,j
\,
/
..... ~...
.
~
.. '
r-~JZ4·1
L--COiE I
I
t
BASIS
OUTPUT
o
-36-
SIMPLiXA~Oli~HM
:page- '2
o
G~
~'42 )g.
-'
1
6 4
HALT)
(UnBOUNDED)
CALC • .
l/ark
SET
ark- ·. 0
o
._--
---~--'.~----.~--~--.-
..-
l,t¥1¥W!i!"T"f"rKr"'H
fir'n"""
'MFfflfn'T"]W!I!!!'P"
SIMPLEX AWORITHM
-37-
page
o
. ~.
....................
SET &1k
• 0
1
x
= 1+1
= x-1
SET
ark • 1
0
SET j-O
SET y=n
j
"1
o
=
=
j+1
,.-1
/
3
-38..
SIMPLEXAIDORITHM
page
4
o
1 = 1+1
x • x-1
g. 1
rIYPE:
ITERATION,
F't.nTCTIOUAL,
m/OOSTk
ID/COSTr
o
Pg. 1
WC"'BHf,rr"3"[""'
HwdH 'J%"'H'U"Pf!t"WiIi"WU
-39-
FINAL BASIS OUTPUT
Page 1
o
.
o
FID.LBlSIS, OD'.TPU'l'
, ... 2
'TYPE ID/C!
V33~~
CALC. &: TYPE
OWER LIMIT
c- (LOWER)
CALC •. & TIP
o
tIPPER LIMIT
'. C-(UPPER)
_---+_~o
1
= 1-1
x :: x-l
READ
NEXT
CODE
,
+
NON-BASIS
OUTPUT
o
" WTT"![l!!"'MtJ
'IX SUBROtJTDE
paS. 1
o
o
o
'PIX SUBKQU'1'DI
Page :2
o
o
o
·W'nuflr ...
NOB-BASIS OUTPUT
Pase 1
o
UPPER-CO
If LOWlll--
am
1-1
SET XIIJIl
o
o
.. .._..._
.. ,.___._.__ . . ._ . . . .". . _". _.__._......................".
~
~_
-1t4-
""."'.",,."","~."."_,
.
w.~~_
.____ ._ _ _ __
NON-BASISOUTPtJ'T
Page 2
'fiPE
OWER m
TYPE
LOWER
LIMIT
TYPE
UPPER
o
3 • 3+1
"1 • "1-1
e 'z.:
410
0'1
g. 1
rJn2 I
4
! BEEr
CODE
I
I
I
I
,
I
MATRIX
PUNCH
o
------------~-
--
~----
-45-
o
o
( HA~~:)
t
REA~l
l _;;i,\ .
r--
;;r
o
LOADER
/
I
I
7
'~
RHS
CHANGER
COST
CHANGER
MATRIX PUNCH
page 1
o
o
o
PRE-LOAD"
CARDS.
o
360383800500
15039180000Z4903826
~1.00.Ql.a~§a749.QJB.26-
ARITHMETIC:
TABLES
: F'LOATIm
POINT
ROUTINES
.. _ .. _... _......~--- ~.-... ~.--- ...' --.... 48000000969636~3826e63'e~4 ..e3e~e'3100100038584903826 000000000000102030400020406080003060902100408021610050015102
'- .:l!'Q.Q I. 9_Q93.f35~49Q;3e..z9. OOo.OZl.B14200.7041 J 2 8 200Bo-ol4.22300909172fi30000000000S06076BEfge
: 3100220038584903826 012141618151811242720242822363520353045403632484455324946536
~.~_LQ.Q.?~QQ~~;>.~~~.o.~.~?..Q_.o..~.~~.t465464;; 75445..36271 dO 1 £: '~4567891 234567agg234§e78~O.Jd4 §67890JI(
3100340038584903826 4567890~KL567890~KLM67890JKLMN7890JKLMN0890JKLMNOP90~KLMNOPQ
. 31004020385849Q3826 16005360053849004340J60053600558260'197000002601) '209 4451601
3100462038584903826 1 24 000001101124000014600494014004901128004692601176000002601
3100522038584903826 187018274900000022011860117649005700260118601176150084700001
~058203~584903826 16008 57 01187260i0920118922011780118947Q070201100260117601197 .'
3100642036584903826 260119701186260118601176210)09201189260117801189320117800000 .'
3100702038584903826'-1501-19800000140 11780000Q470 1 09401300440077401197320119800000 "1.
3160762038584~Q..382·e?_ 3~Ql 1970000021008570117844008220118633011 8600000150084700002' ':/1
3100822038584903826 15011780000015011890000Q210119800000250109301198330119800000
31 00882038584903826 430.-9.~860 1 18943010340 1 19046009660120031 Q119001191250 119800557...
3100942038584903826 120109200001460089401300260119701826490110602601 1980J 1 973301
31 0 1 0020~~.~~4~0~~..?t?) ?QQ.9QQ.9 Ll 0 1 O~gQ.Q.QQ !.~.~Q_Ug§..o 1400 1501 1890M.ODJJJU_198000054300
3101062038584903826 986011894401094010933201197000002601189010922600000011974900
3101122038?84903826 000048260115100469260051700000490050600000000000000000000000
3101182039004903826
*
'
OOOOOOOOOOOOOOOOOZ
31 0 1200038584903~2~__!....~q95360 1256150 1 ?53000_Q.~!' 6<;>1.112000993201 19000000490045804301
3101260038584903826 2760119Q490096604301290011~482201189011682S0132501176330117
3101320038584903826 600000150116800000160 1347'OOOOQ 11 0134700001 ~1760 1176430 139
: -310 i 380038584903826 401 -168490 1350016'014410 1 e31~50 14280 116911 014410 *0023011 75000
3101440038584903826 002601477014411201477000042601166000002201166000933201162 no O
3101500038584903826 002301176011652601186019372201186000963201178000002301186011
310! 56003_~_~~~0~~g.Q..~~~~J)_Q...Q82Q.Q.O_Q.Q t~QQQ8J_QQ.Q.{bl2.J..o00900 1186260 1 18600090230 J 18601 1
3101620038584903826 652100095000951201347000014701622012002601186000944401694013
3101680038584903826 25320118600Q0023011~6Q11971101189000N025010930009926OJ092011
3101740038584903826 892601198000924601774013004900966047008820140049011260000000
31 0.1800038.584903826 ...Q.9JlQ..000000QOOOOOOOOOQOOOOOQOJ20692R080J74077PS66J60 12604'05,14
3101860038584903826 8~49N490~38013M759~29099MI64~21267L674j14332L266~08147K922jO
~J_q 1230 I 19
3102040038934903826
*
7011762101189011684901718
'------n-u I 9Boo38Sszr9U3820---g(JqYOOY660 430 2'OTUOTT 6949009560 320 I
~
..-
... -
COST~ ;'.i~: ,,'
, OHAWOER
, RbUTINE
.,......
I.
.
~id21i40385B4Y03B26
48000000000046021 10002003603838005002503848h0400490219403400
3102174038584903826 000001023603838001003203838000001403841000004600012012004602
j
1 02234038584903826
2OO0020034oootrn00TtJ23803838(~''-(rnjU26022050oh
192602308000541102
3102294038584903826 3080000424000000384146024600120011023080(,)OJn1202205000J04702
"'"3T'02 354cr:msS4'9038"20" -3'0'"20 [20026022 0 50lnj7zr26UZZro~ti2 30 82 102404000 692q>OO 0 0 003841 4602 ":'\
3102414038584903826 480012002102404000691202205000J04702398012004826025100230849
~ Cf~474O':m'7l5lp:m3S20~"
3102516038744902126
.
--~·-··'--'·-------·1F··---U2492b26025
•
,snoo
3101440038584903826 0026Q1477014411201477000042601166000002201166000933201162000
:-"310'150 0038584963"826-~oTrr60 11 652601 rS-6QT'7:3722'oTTBooooQ032Q1 17800000230119661 i
3101560038584903826 8633000820n00015000810000J21ci0090011862601186000902301i86011
j-3f0162 {,)03S'S84953826-6-S21o-0095 00095 f2-Crr:r47 0000 r4,-cff'62"2nT2nrf2'6n 11 86000944401694013
, 3101680038584903826 253201186000002301186011971101189000N025010Q3000992601092011
3101740038594903825--892601 198000924601 I 740i'"300490d966d4 rotJ882t1 1400490 I i 260000000
3101800038584903826 00000000oooMo,n(')00000('lno()()()onJ90692R080J74077P568,,)601280405,,)4
- - :..
.I:0>
100240411 c)251 00000626000000384 f
'*26025460251nl,2025460000~33000000000049021~60
Q
o
til
~
a
~
!'i
ttJ
=
PRE-LOAD
·360383'8('-0500
CARDS·
'AiiITHMi'ilc~
'fAB~ .... J
.FLOATING
POIBT
RoUTINES
.! ?Q;39_!~~)0~Q?4~q~~~~_._. _
.
31nnl~00385849n3826
--w--- _.
_
____
.' _ .. __ ._ .... __ . ___ ....
....
-." - - - -
0000nnnnnn~~ln2n3040nn2n406n8non30609021nn4n80~1610050015102
31 OQJJ~90~85849038_~.~ ___o.060~] §.l~?OO}.9'!! 1128~q9_~Q§1.~~230Q~081 72~~00000005060708090
31·00220038584903826 0121416181518112427202428223635203~3045403632484455324946536
3100280038584903826 04846S4627544536271801234567891234567890234567890J3~567890JK
~ 3100340038584903826 4567890JKL567890JKCM67~90JKLMN7890JKLMN0890JKLMNOP90JKLMNOPQ '
3100402038584903826 160053600538490043401600536a05582601i97c~non260111200 4 451601
._. "3100462038584903826 124000001-1-0 1-124i)oooi 466(i494 I"' 14-00-490iI28004692601176000n02601
3100522038584903826 1870182749000000220118601176490057002601186~1.176150084700001
,:-·3160-582038584903826 160085701 187260 iO·9.2 o·i-IB9-i20i-1-78 0 1189470070201100260117601197
L.~J OQ~42038584903826 260119701 1862601 18601 1 76.? 1 0 1 0920 1189260117801189320117800000..
3100702038584903826 15011980000014011780000Q470109401300440077401197320119800000
.. _.~.l.QO.?62P?_~58490~~~.~_._~~91__ ~700Q002}gC?857~.!_.!..!~44.~08220 1 1 ~6330 118.600000150084700002
~ 3100822038584903826 150117800000150118900000210119800000250109301198330119800000
3100882038584903826 430098601189430103401190460096601200310119001191250119800557
;- -310094203·8584903826 1201 0920'000146008-9401360-260·11'970182649011 0602601198011973301
. 3101002038584903826 1900000011010920b0014601126014001S01189000001101198000054300
I 3101062038584903826 986011894401094010933201197000002601189010922600000011974900·
\ _~...! 0 1122Q3_~~~4903~26. Q..QQ.Q~~~60.!~} gQ.~?_~~60051 7QQ.CI_O().~?.9..Q_~Q_?n0.0nn~"('ono()ooooonnnoot")
3101182039004903826
*
,
*
OOOOOOOOOOOOQOOOOZ
• 310 1200038?849Q3826 1 6005360 1._?56_!_~01 7530_9_002 }_~q_l 1 1200099320 1 19n"0000490045804~O 1
3101260038584903826 27601190490n966()43Q12900116948220118901168250132501176330117
310132n038584903826 60000015011680000016013470000011013470oon1210117601176430139
3101380038584903826 4011684901350016014410183725014280116911014410 *002301175000
3101440038584903826 00260147?0144112014770000~2601166000002201166000933201162000 '
. 3101500038584903826 002301176011652601186019372201186000963201178000002301 186011
3101560038584903826 8633000820000015000810000J210009001l862601186000902301186011
31016200-38584903826 6521000950009-512013470000147016220 120Ci260 1 18600094440 1694~ 1 3
3101680038584903826 253201186000002301186011971101189000N02501Q93000992601092011
3101740038594903826 892601198000924601774013004900966047008820140049011260000000
310 t 80('038584903826 OOOOci0~C?~!!.rH"()_~_noo on onnooono ~J.9()6~.~~~0_::!_?4() 77P568..J60 1280405J4
31~lB60038584903826 8249N490J38013M759J29099M164J21267L674J14332L266..J08147K922JO
~ 1..2..t 9.~_og~~.~_~~.~2.3~~.?_.~?~.?~?~OJO~0000000 1 ~().~~?~_!9_7-.2~ ~g~_?5~~O_.25_940~.~?~~2Q?~£!_6 . o.074_C9.~;tg4.4..80gQ481602455000M 12602520026474902) 50MqO?6683?0392
310.26540.38584903826 0000.00 4 902466026026590007426027100.00.6421027100006926000000.18
.. ~~.()_2?~.!4-.03~~E349o.38g~ _?~?'§Q~a.7.l..o..?_7l..O.2.Q0284702710 110284'1000 101602799039402602253000
. 310.2774038584903826 792603920018262103920.000004602884012001600469028472601197039·
3102834038584903826 ~~9...a..L9380aoo.0160a46902BB3160044500000490042?ot>099Jl0?7g9ggg
-310289403858490.3826 ~OI1028470o.O~01202253000j04702776012001102847000K02102871000
~ 31 0295403~58490_382~ _Q.9J 202~5...2.Q..Q.Q~046027520 130..0..370356300500250358300400340000000 1
~3103014038584903826 0. 2 390 3 5630010039000 4 90010034000000010234000.0000102160.26590.00
, 31 03074038584903826 04370356~Q!?00250 3583004Q04]~~Q 1003903563001003400000001
~ 03134-038734902114
'0812026590000147030760120034000000010249000.24
c_
PAGE' .
~INGS
.
...:.~:-._
• .1-__ _ _
PRE-LOAD
CARDk_-_
; DUAL
AWO~ITHM
ROUTINE
o
!
CASE ..___._ _ __
ITER NO
FUNCTIONAL
VAR.OUT
VAR IN
I
\1\
....I
----------------------_._-----------
... -360.38380.050.0 - - - - - - - - - - - - - - - - - - .--15039180000Z4903826
310211403~84903826 26000230-1826260.3 44 00007926021850006421021850.00691102185000~o.
31 021 7403i~584903826 2 4 00.02300000470222201 1 Qo.2602221 o.218526Q00230o..QQQ~3440000~0
----31022-340385·84·9-03826 '4702 i'620 i 200440062400o-i3260C;-023022051603560o.0000260341600074
3102294038584903826 26023720222126024130o.0642'1Q241300069210237200069260242502372
--"31'0235403858490.3826 2-10241300069-2400000018264.,6"
860130016004690.2425260119700000
, 310.24140.38584903826 490 12000000...Q£~
990
23 7
4
310.247403858490.3826 2603560024131203416000J04702330o.1200140356o.oo.o.o.o.47025460.1200
31·025340.38584903826
48N
11 00o.000026026840352426027080356026~44.n.ru1O.7926Q2.66503524
t-_·_·
- . - . - - - - . - - _ . - - - - - - . -..
- ... -.---... ---..
"'-"--'
.--.
3102594038584903826 16026960393026027800352426027010356016004690266526011970.2545
310265403858490.3826 490 1200000002603740000992~.000QOO I a.?§2603~~1l0_0QQ_~QQQ.o_ODo 1826
-"'310271""40-:38584903826--1 1-02696C)0'O-JO i'I--0270-1 OOOJdl10270800o.~0 1203440QOOJ0460269o.o 1300
3102774038584903826 26000000254526028570222126028640222126034160.0074160046902857
'-~T02834038584903826 2601197037 4 0 49 01938000002600000000992102857000692102864000.69
3102a9403~584903826 120341 qOOO~046028,??O.1300 160298403930260302.500064210302500069
o
o
CIl
o
t.
.
i
.
a
t-3
H
o
sz:
o
:·PRE-LOAb- -.
CARDS
SII-1PLEX .
ALGORITm·i
ROUTI:\!E
o
o
- . 31029-540j'6584903826 160309703930260344000'07922039300 182646032180 1200260308502-221
.._. 3.~.?~0~. ~~:3~?84~038~~ 60_3121 000002603416000]4~§q314003 t?..LL?9~t~_Q. Q..Q.~Q?J..60Q~§9~_~.ll.9L_
· 3103074038584903826 260119700000490193803930160046903133160Q445Q0000490Q40200099 -.
__ .=!J 9.:}_L~~_93a584903826 1400000000M34 7Q35980 1 300;> 1 03~L~..50QQ6921 Q31 L!_n.o...QQ.9..~21-~21 OQQ69
3103194038584903826 1203416000J 46Q3062013001102984QOOJ011Q3Q9700QJOI103025000JQ
.
3103254038584903826 1203440000J 46n29780130026033730222126n3361n35601203361nonJO
.
-., :fl-6""33'1'40385S-4903826 260336803361'220337'3000692'60'3380033732600023t:"0000260000000-00~
_.. ?!.Q_~~_?_~.O.~8584903~2~ 26000000002311 O~631 00n014.7021 1400 1.003~!:nn('\nnQ...t_023803?290!'....!.20_._
3103434038584903826 340000000108260357703373260354103361260350~00064210350500069
3103494039584903826 260391700000380390800100340000000108260391700000380390900100
--"3fo'S554cij8584903826 3400000001 08260391700000380390800 1-00490211402603616031212600
310361403<:1004902114
*
.. 000018264903158000
-·-3'60-38'3800500..----··------------·-1503918000QZ4903826
- ....
- .• -....
.......- - ............ --.
---'.'
..•.
. _ - - - _....
_-.,
...
_-
.
-
3102114038584903826 250366803747260002301826260354800074260219700064210219700069
~ . ~! 0 2 ~.?~J~?~~~~903~~~21.~~_1~.!£o..0_692_~Q.Q.9...E.30qQ.90.4 70223401 100260223302197260002300000
_~_l.022J~.5.8!i9Q3a26
•
I
2102197000691203548000 '04 7 021860 1200440002.~2~0002.J035;22
3102294038584903826 160348100000260363200079260238002233260243302233260242100064
'__~J
Q.23.;;~JL~e.5843l60Z~.?O_O_389932019.~7{),00004402276.0 1957430P?~0Q7.!ij3IAQ:l,,- :;
3 i 022480'38'5~~'?93_~2_6___ 7?~QPQQQ__~9Q22JH3Q4~Q 195.10.0000250 38 9 9 0075.3..1--1. 022&70000111 Oa.a4 39 i
310230&038584903826 000111022820000211022500000212022190000147022200120044024160
, 31023680385849038.2.6._1956330 195600 0 00.330-195700000 16G22-1-~20340eee6601 ee
;- 31024-280-3-8584903826 39038990010042140391 7000K04 702478012003200760000002100760007
31 0248803~~e~9.Q_;3J3.ZfLLO_4_7..02.52ZQ.1.3.OO.l.603.9.17-OO-00049021-4-s.o1Q(}391+GOOK04 9021 CbS-r-
.-'--,~~
After entering the ID, its associated requirement
change is entered (by typewriter or on a separate
card). The entry starts in column 1, if a
card is being used, and consists of optional
leading sign, up to eight numeric digits, and
mandatory decimal point. It must be terminated
by a record mark, whether it is entered from
cards or from the typewriter.
oOlXxxi'xxxxxxxxx
Negative cost is signified by a minus sign over
the units position of the cost field.
If any card contains fewer than four elements,
the first blank field (column 21, 41, or 61)
of that card must be punched with a record mark
(0-2-8 punch).
7.
The_last data entry for fixed point mode must
be 000 to terminate the loading operation. This
can be punched in columns 1-3 of a new card,
or in 21-23, 41-43, or 61-63 or the last rowcolumn or cost entry card.
8 •. Entry of
requirement changes:
The identification is entered first, and consists or the ID associated with the cost element
for that row. Thus, to change bi • b3, use the
ID associated with ci = c~. No flags or ~cord
marks are needed in entering the ID either
from cards or typewriter. It is punched in
columns 1-4 or card entries, .-li th 5-80 blank •
Row-column
Description
or
There are two entries for each requirement change:
the identification and the C~St in the value
of that requirement element. _0 e that the
new requirement element is not entered, but
rather the difrerence between the old and new
requirement elements. If changes are entered
from cards, the identification and change are
entered on separate cards, one per card.
Fixed point cost entries are also four per card,
but the row-column designation is on the same
card as the cost.
~
Entry
The last entry must be four zeroes to terminate
the operation.
!.
Interpretation of Results
1.
cost changes or requirement changes are typed
if the input is from cards. If input is through
the typewriter, the input operation itsel~
produces a log of the changes made.
2.
DUal Algorithm and simplex Algorithm:
co~t c~nges:
Data for the COST CHANGER routine can be entered
either from cards or from the typewriter. If
entered from cards, one entry is punched in
each card, in columns 1-10. The entry consists
of the four digit ID and six digit cost figure,
with a minus sign over the first digit of 'the ,
cost (column 5) and over the last digit of negative
costs (column 10). Fbllow1ng the last cost
change card must be a cn.rd punched with four zeroes
(columns 1-4.) to terminate the operation.
Results of iterations are typed only ir console
switch one is on. If it is desired to monitor
the course of the solution onlh occasionally,
this may be done by setting switch one on and
off periodically. The following points should
be borne in mind:
-10a.
b.
-11-
5.
Page headings for iteration output are
typed only if switch one is on at the beginning of the solution.
The iteration count is reset when the du~l
algorithm is finished and control passes
to the simplex algorithm.
D.
~e information which may be typed includes
the iteration count, the current value of the
profit function (floating point), the last
variable to leave the basis, and the variable
which entered the basis.
3.
For each final basis variable, the following
information is supplied (in fixed point):
4.
a.
Identification/cost coefficient.
b.
Activity.
c.
The limits of the cost coefficient over
which the current solution is optimal.
d.
The variable s which limi t the range of the
cost coefficient and will enter the basis
if a limit is exceeded.
Final Non-Basis output:
For each non-basis variable, the following
information is given (in fixed point):
()
FUnctions of Individual sub-programs
1.
~e data load routine reads and stores parameters
for the problem. It then proceeds to load and
store the matrix in the proper format. In the
case of fixed point input, storage locations
are computed from the rOW/COlumn designations,
and the input elements are converted to floating
point notation as they are read and store_d.
2.
The cost change routine reads ID/cost elements,
searches the matrix for a corresponding identification number, and stores the new cost
coefficient in the proper location.
3.
~e requirement change routine reads variable
identification numbers and changes for the
associated requirement element. The change is
converted to floating point notations, the
matrix is searched for the identification n~
ber, and the requirement vector is updated.
4.
The shadow price calculator converts all cost
coefficients to floating point notation and
evaluates Zj-Cj for each non-basis variable.
~.
The dual algorithm computes a feasible solution
for the problem. Its operation may be monitored
allowing the typing of the value of the functional
and the identifications of the variables that
enter into and are removed from the basis. It
should be note~ in this regard that the objectives
of feasibility and optimality may not be compatible at this point, and therefore the functional
may actually decrease from one iteration to the
next while the dual algorithm is in control.
Final Basis output:
The final value of the profit function is given
in floating point.
a.
Identification/cost coefficient.
b.
Shadow price - the penalty to the total
system if a unit of this variable is forced
into the final solution.
c.
~e limits of activity over which the shadow
price applies.
d.
The variables which limit the range of
applicability of the shadow price. The
upper limiting variable is the one which
would leave the basis if the associated
non-b~sis variable were forced into the
solution.
A punchout of the complete final matrix is optional under control of console switch four.
The cards punched also contain all necessary
supplementary information and are in a format
which is suitable for direct re-loading by
the LOADER routine'.
DUring the reduction of the matrix of coefficients
a test is made to determine whether the resulting
quantity has a magnitude less than an amount
callAd "essential zero." Any element falling
into this category is set to zero in order to
avoid computation with numbers which are actually
not sisntficant. "Essential zero" has been set
to 10-. Its value (the corresponding floating
pOint exponent) is located in memory addresses
0
0"
o
o
o
-123144 and 3145 and may be changed if desired.
th1s change is made, it is 1mportant to note
that the high order digit must carry a flag.
6.
-13It
00065-00069 M and 2
00070-000'74 N
00075-00079 M
00080-00099 product area
00100-00400 arithmetic tables
00402-02064 floating point subroutines
variable
programs
03758-03917 input area (record mark in 03918)
matrix
03920-
The simplex algorithm starts with any feasible
solution and computes the optimal feasible solution. Its operation may be monitored by allowing iteration typeout as in the case of the dual
algorithm.
~ discussion of essential zero as applied to
the dual algorithm in 5. above is equally valid
for the simplex algorithm. In th1s case the test
value is located in memory addresses 3264 and
3265.
F.
Program Decks
1.
3 pre-load cards.
Arithmetic tables.
~oating point routines.
Data load routine.
~Atrix data to be entered.
In the case of a tie in the quotient used as the
criterion for choosing the variable to leave the
basis on any iteration, the choice is resolved
by using the largest denominator as a secondarJ
criterion.
7.
The basis output routine searches out and computes the information described in section C.
above. Floating point quantities (with the exception of the functional) are converted to
fixed point before being typed.
8.
The non-basis output routine searches out and
computes the information described in section
e. above. Floating point quantities are converted
to fixed point before being typed.
9.
E~
The matrix punch routine resets the permanent
instructions in low memory to allow re-initiation
of the input or change phases. Problem parameters
and the final matrix are punched into paper tape
if called for by the setting of console switch
four.
Use of storage
Memory locations from 00012 through 03919 are used
by the program. Memory from 03920 up to the required location is used for the matrix and its manipulation. Locations 00000 through 00011 are available for the insertion of one instruction at a time
through the typewriter. A halt instruction in posi~
tion 00012 ensures that only this one instruction '
will be executed.
00012-0004?
00ou.8-00058
00060-00064
load routine
case identification
S address
LOADER
2.
COST CF...ANJER
2 Dre-load cards.
Arithmetic tables.
Floating point routines.
Cost changer routine.
cost change data (if entered from cards).
3.
RHS
CRANGER
2 pre-load cards.
Arithmetic tables.
Floating point routines.
Requirement change routine.
Requirement change data (if entered from
4.
SOLUTION
2 pre-load cards.
Shadol-1 price calculation routine.
Page headings.
2 pre-load cards.
DUal algorithm routine.
2 pre-load cards.
Simplex algorithm.
2 pre-load cards.
Final basis output routine.
2 pre-load cards.
Fix and print routine.
Page headings.
2 pre-load cards.
Non-basis output routine.
Page headings.
2 Pre-load cards.
Natrix punch routine.
cards~
-15-
-14SAHPLE PROBLEM
III.
G.
storage of matrix in memory
A.
The matrix is stored in column sequence and uses
memory from 3920 upward to the extent required by
the problem size. The following diagram indicates
the manner in which matrix elements are stored:
Matrix
Basis variables
'901
S..10(2m+3)
3920
S
_.
S+10(2m+4)
S+10 [r-<3~----r-
RHS CHAN&
SHADOW PRICE
-.-
I
CRAInER
-19-
-18-
GENERAL FLOW
DA!l'A LOADER
Pagel.
Page 2
N~"-"
_90
~~vW-19'-....
-"/
~O
.~~~vl
t__::IXI
........
LOAtER
~
r
........
~
RHS CHANGER
o
3
o
o
o
o
--20.
-21DATA LOADER
Page 2
DATA LOAJ)ER
Page
NO/~
SET '-I
L~T_~=9
e-
3
-22-
-23-
COST CHAItJER
COST CHANGER
Page 1
Page 2
·
8
1..-1<9------1(,
2126
@:.
C
g. 1
o
o
o
RBS ClWllER
page 1
/
cof'!
CHANGER
o
o
o
-zs-
®
RHS CHANGER
Page Z
\
sJoow
PRICE
~
rn(J
00
:J:~
:2-0
®
OC
,-{
O~
~~
\J
~
-<
.-.-~
mrs
-27CHANGER
page
SHADOW PRICE CALC.
page 1
3
)c
1.
1
o
o
o
o
o
o
-28-
SHADOW PRICE CALC.
-29-
SHADOW PRICE CALC.
page
page 2
G?l_-
'_m
.
3
,
I
g. 2
-31-30-
DUAL AIGORITHM
Page 1
SHADOW PRICE CALC.
Page
4-
~-= i·n i
NO)
~(;;~
I
Pg. 3
'12,1~
~bm1n·t>~
~/ 2198 ~/
~t-;;-1
\=
I
bi
~
1
~_ft~;~
Ix • x-l I
~~OO
~
'
~~_~I~~
,-,......
I
,/~234
NO
/;
x•
'~,
0
$
I
t
DUAL
ALGORITHM
SIMPLEX
ALGORITHM
~
o
o
o
o
-32-
o
DUAL AWORITHM
page 3
DUAL ALGORITHM
Page 2
.~
.
.
1( ....
r--~
i ar j-arj/ark
I
-34-
DUAL AffiORITHM
Page
4
~ii
INQ\.
.
. '~
j!.l.
rEn
'::>
=
j+l..
'1j = '1-1
~
-:
2258
NO
\...J
O'??">--fNO)'"
S.'1
-/
...-.,~.
I
t
BASIS
OUTPU!
1
.
e
E: ITERATION,
CTIONAL,
'/COS'1'k
~/COS!r
2114 -""'<3~-------'
g. 1
o
o
o
o
o
SIMPLEX AWOIlITHM
page
e
o
-37-
SIMPLEX AWORITID1
Page 3
-38-
SIMPLEX
-39-
AlGORITHM
Page
4
FINAL BASIS OUTPUT
Page 1
~_oc>
'ET
,ET UPPER
LOWER =
ET j = 1
ET ,. = n
_ _ _• _ _
~
00,'
.
• . ___ r _ _
;-----..-J
®-
TYPE: ITERATION,
FUNCTIONAL,
ID/coSTJc
ID/COSTr
.
i32918
~~.,
~7'-~:~?
p
Pg. 1
o
o
o
o
o
~o-
-41-
FINAL BASIS OUTPUT
Page 2
~
~E
V1~~a
AOIfIVITY\
:L:
ICALC~--&-mEI
lO-
LOWER LIMIT .
(toWER)
!
-.-t~
1
I
t
NON-BASIS
OUTPUT
FIX SUBROUTINE
page 1
-42~
-43-
FIX SUBROUTINE
NON-BASIS OUTPUT
Page 1
Page 2
ISET UPPER- 00
SET LOWER=SET 1=1
1
.~~220
SET
,FrAG 0
'~,?
232
~_D'~GI~
e:
~~~
SET
','
t
I
'28.8.'
-_.. ·.\-·....
,1 = ~~ .
:---.- -'---~~
..
,
= x-1
r--~~~.
~:i~I~
-1
~
~,~2 C'.'\
~--./uP.PER?'~
M
. 10@f
,.
TO OUTPUT I
pIG_~) __
,...-/.
,
..
, j
i
o't'>--eJ
G>'
"',.-
I
'8
~~4
i
f2348
~~,~.
~fb~~
"--'---'-®_~j:O? -~
TURl2~~
j+1 \
'j •
,--'-"
~~r...
'
...
m.DIGIT
OUT.PU.T.
j ,'.
x
(_.,\
~,-O!,~~,~'
x=m
. /'/ V
'.......,,-
__~6
'~006
tN()\~r IPWER~
~ l~.V
';"'---../
rj~~
!>Ie:::::'!
I
1SE'l' x-5
I~
I
o
o
o
o
o
o
-1¥t--
-45-
NON-BASIS OUTPUT
MATRIX PUNCH
pagel
Page 2
C;::o;O
I~AI
'g. 1
I
I
I
t
MATRIX
PUliOH
/
~
LOADER
I
,
I
+
~
RES
CHANGER
COS'!'
CHANGER
PRE-LOAD"
36038380()500
15039180000Z4903826
CARDS
ARITHtvlETIC
TABLES
3100012038874903826
3100100038584903826
310016003d584903826
310022003d5B4Y03826
31002B003d~b4~038~6
3 1 0034003 e 5 e 4903826
3100402038584903826
3100462038584903826
3100522038584903826
310058203eS84903826
*
4800000000003603826005004903826
000000000000102030400020406080003060902100408021610050015102
0060218142007041128 2 0080614223009081726300000000005060708090
0121416181S1Hl12427202428223635203S3045 4 036324844SS324946536
04b46~4627~44~36271d012J4~b7eY1234~67bYO~34567eYOJ34567890JK
4::j6 7 8 yo JK L 567890 J KL 1"'6 7890 J KL TI/I(\J 7890 J i< L MNO 8 9 0 Ji<' L ,VlN UP 9 O")K L MNOPQ
16005360053849004340160053600~5826011970000n2601112004451601
124000001101124000014600494014004901128004692601176000002601
187018274900000022011860117649005700260118601176150084700001
16008~70118726010Y2011bY220117801189470070201100260117601197
310064203~584903826
2601197011862601186011762101092011892601178n1189320117800000
3100702038584903826 15011980000014n11780nnOG47010940130Q44nn774n119732nl19Bnnnon
3100762038584903826 3~011970000021008S701178440082201186330118600cn015C0847orC02
3100822038584903826 1~011780000015011890000021011980000025nln93n11983301198noooo
31008820385d4903826 4~OOY86011894301034011904600966012003101190nl1S1250119800557
3100942038584903826 1201092000n146008940130026011970182649nl106n26Qll980Jl973301
3101002038584903826 1900000011010920000146011260140015011890000nl101198000054300
3101062038584903826 986011894401094010933201197000002601189010922600000011974900
3101122038584903826 00004826011510n4692b00517000004gno506ononn00000000000Q000000
3101182039004903826
OOOOOOOOOOOOOOOOOZ
3101200038584903826 160053601256150175300002160111200099320119000000490045804301
3101260038584903826 276011904900966043012Y001169482201189011682~0132501176330117
3101320038584903826 600000150116800000160134700000110134700001210117601176430139
3101380038584903826 40116849013500160144101837?-5014280116911n14410 *00230117~OOO
3101440038584903826 002601477014411201477000042601166000002201166000933201162000
3101500038584903826 002301176011652601186019372201186000963201178000002301186011
3101560038584903826 8633000820000C15000810000J2100090011862601186000902301186011
3101620038584903826 652100095000951201347000014701622012002601186000944401694013
3101680038584903826 253201186000002301186011971101189000N02501093000992601092011
3101740038584903826 892601198000924601774013004900966047008820140049011260000000
3101800038584903826 000000000onOOOOOQOOQOOOOOQQoJ90692R080J74077P568J60128 0405J4
3101860038584903826 a~49N490J38013M759J29099M164J21267L674J14332L266J08147K922JO
31019200385a4903826 2597K630J000000000160053601970150175300003490122404301990011
3101980038584903826 9049009660430201001169490096603201169000n01201168000Nl230119
310204003(:)934..9,0 382 9
70117621 nl189011684901718
*
o
0'
I
*
*
o
•
-t:""
o
~
~
t:-t
~
t;1
t:t:i
~
o
o
o
.--,.-
--
3102114038584903826 4800000000003 7 0375900500250376900400310004803758360383800500
.~.t02J !403_~~84903826 _21 0219(,0~~~JtQ0006403_95Q26QnD79.038A211 0384200QK02600Q6903842 _ ...
3102234038584903826 260007403847430232603848210228800064360383800500310000103838
3102294038584903826 110228800000470227000900490001203603643005001403645000004603
3102354038584903826 174012002303648000692100099000693300099000002100098036452100
3102414038584903826 098000633303646000003200095000002603160000994402490036482602
3102474038584903826 125036584903154044025100364549024700490341800bo01403759000PO
3102534038584903826 4602646013001403759000K0460262601200430264603759330260500000.
3102594038584903826 320376000000310375803760490265803202605000004902594033026050
3102654038584903826 00001602117000N016027120375916Q27000376032000000000014000000
3102714038584903826 0003460277 4 0120011027120000211027000000211021170000149026940
3102774038584903826
260282102700260281602712120281600001310000000000430292603759
- - .-- - - '.
3102834038584903826 3103758037601202117000014502822037594Q033n200000000000000000
31028940385A49038?6 000000000C0000n00000000000000nOOI602657n~0~916n2985037591603
-
3io~~540385R49b3826
.
00002118160300~037594502994000004903062025nnOOOOOOOOll029850
_..
.. 31 Q3-56.oo.3.8974903826
2503723004004902126
I
-
3103014038584903826 000211030000000111030050000212026570n00149029740260310403000
3i03074038~84903826 120265700001460313001200150000000000110310460001490307404403
3103134038584903826 154026053202125000002600000021254903302026032520006412032520
-. :3 f03'i94038-584903826 00J92jb06690007~3200095000002io00990006921000990006932000000 ,
3103254038704903826
00001103252000J01200999000J047032460120049000!20
...... -...
--".
_ 3.lQ..3.3.02..o3.65 8 490.3.826 .31037580379831..03.79803&383.1038380387831 038780391831 0364303663·3103362038584903826 450339403643160251603418490232601602516034~44902338000003103
7580350031 03B3Bo.3500370375900.50032()3758000004902~2{)---..
.. 3J.03.422D36.66_4903826
3103500038584903826
~-.-.,-
.!:
-.J
*
-------------------*~
~
t-3
~
t'"
~
d
tJ:j
::0
~~-
36038380050n
15039180000Z4903826
31nnlnnn3~5849n3826
onnnnnn00n~nln2~3n4n~n2n4n6~8nnn3n609n21n~4n802161nn5on15102
310016no~8~84qn38?6
on6n218142nn7n411282nn806142230n90~17263nnnnnOnonn50607n809n
310022nn385849n3826 ()121416181:j 181 12427~()~~423c2j6.j5F()3'::)3n4~j4n36324844:::;5324946536
3100280038584903826 0484654627544S36271bal~34~61891234~6·'A90234~67B90J34567890JK
310034~b38~R4q038?6 4~67890JKLs678g0JKLM67b90JKLM~7890JKLMN089nJ~LMNOP90JKLMNOPQ
16nn~36nn:::;3849n04~401600536n0~~826nl1q7~nnnn26nl112n04451601
31Qn4n2 n 38584903826
3100462038584903826
3100522038584903826
j)00582038584903826
3100642038584903826
31b0702038584903826
3100762038584903826
310()822D385849n3p.26
31nnRA2038584gn382A
FLOATING
POIlfr
ROUTINES
310~942n385d49n3826
124000001101124000n1460Q4Y4n140049011280n46Q26n1176000002601
187018274900000022011B6011764900570026~1186~117615G084700001
160085701187260109201189220117801189470070201100260117601197
260119701186260118601176210109201189260117801189320117800000
150119800onn14n11780000Q4701C04013804400774~1197320119800600
3301 197000()()21 n08570 1 1 784400822G 1 1 B6~=-1n 1 18~-"()()OC~C-! 15("'(':84 7n0nn2
1:-5011 780nn n n IS!") 1 1 B90()()on21 Q 1 19Bi'(\r"'(H)?C:::n 1 nq~", 1 1 (jd.33n 11 q8 n nn!)f)
4~n09860118Y4301034011Y0460nqb6012n031011~0nl1~1~~011Q80n557
1201092cnn"'146nn894013nn26011~7018~64Qnlln0n2Snl1S8nll973301
31 n 1 n~.2n38~84 :--:)139?6 1 ~Jn"nC'l0~(' 1 1'" 1 092r'!oon 146 r '11 26,'"' I /... rn 1 ~)n 1 ! .qqn:-'nl"· . . . 1 1 t"'.1.19~~.1}nnn~430n
310106?038S84~03A26
9860118944nl094010g332Cl197noon026CllA901nq?26n000~nI1g74~n0
3101 1220385R4Gn3R?S
31011R2039004903826
00nn48?6nl131nn46926nn5170D0cn4Y~n506nnnn~~nrr0n~nn0nnnn~nnn
*
*
OOOOOOOlH)OOOC()()OOZ
1600536012S6150175300n021601112G009932011900COn0490045804301
. 310126003d584903826 276011904900966043012YOOl1694822011B901168250132501176330117
31012n003ci584~03826
3101320036~d4~03b26
ico
I
6000001~01168000001b013470000011013470nn0121nl17601176430139
31013S003cl58490j826 4Ul16d4901350015014410183725014280116911n1441Q *002301 17500n
310144Q038584Q03826 0026Q14770144112014(7000042601166000na22nI1660n093~20116200n
31015n0038~84903826 0023011760116526011d601Y3722011H60009h3201178000002301186011
3101560038~R49n382A
8633nnn82n~0.0nlS0~n81n000J2100.n900.11862601186000S02301186011
31r162 n n385R49n3A?A 652100.n9snn n 951201347nOnnI47 n 1622n12nn?6nl1
.
A6 n
n09444nl6940.13
310168n0385849038262532011860nn0023011H601197110118900ONn2~nl0q30nCq926nln92011
310174n038584 0 n3R?6 89260119800n92460177401300490096604700832n140049011260noonan
31nI8rnn385R49n38?~
noon()nnnnn~r0nn0000n0nnnnnonJ9n692RQ8nJ74n77p~68~6012804n5J4
310186003b584903826 8~49N490J38013M759J290Y9M164J21267L674J14332L266J08147K922JO
3101920038584903826 2597K630JOOOOOOOOQ16n05360197n1501753nnnn349Q122 4 04301990nl1
3101980038584903826 90490096604302010011694900966032011690nonOl?01168000Nl230119
310204003B934~03826
70117621allcl901168490171d
*
31n21140~S84903A26480n00000000460Z1700020036038380D50025n3848n04004902194IT3¢OO-·
FLOATlOO
POlIiT
3102174038584903826 00000I02360383800100320383800nOOI403841n~nn~46noo120120~4602
3102234038584903826 2660020034n0000001n23803838~010n260220Snnn7926r2308nno641102
3102?94038584903826 3080000424nnOOnQ38414602460n12n011n23nHn~nJn12n22050nnJn47n2
3102354038584903826 302012C026022050007426024040236821024n40n06924C0000038414602
3102414038584903826 480012n021n2404nOObY12n2205~OOJ047n23980120n482602510n230849
0249202602510024041102S10nOD06260000003847
3102474038764g03R26
ROUTINES
*
310251603~744002126
o
*260254602~lnl.202546000n533nnoon0000049021260
o
o
Q
o
CIl
1-:3
(")
~
~
Q
t.rJ
::0
o
o
-- _.-.........
.......
-
...
~
o
.
. 360383800500
.._.!_?0.~21~g~)g_Q.?4?Q.3f3~?_. __....... _--- .. _._' ... _'..
,
... ,_"
.. ,
,,___ ,_
__ . _.. ,_'._,._
I 3100100038584903826 ooooonnnnn~~102n304nnn2n406n8nnn3n609n21n~4n80~161n05n015102
I 31 00_lQ.00385_~.19.92.8~,§ __Q,Q?Q?~ ~l_~?Q.Q!Q_~ 1 12.82000Q6142,23009081 ?2,63Q00no9Qo_99~060?n~Q..~Q_
I 3100220038584903826 0121416181S1811242720242822363S203~304~40363248445~324946536
I
!-
3100280038584903826
04846S4627544536271801234567891234567890234567890J34567890JK
. ----.----.. -----~"-. ---.-.. _....._._--..... _...... _-........ , _..._._._-,.._. ',","'._."" - -..-- "'''--'''' ..... "'---.-.'--"----:-----:-~~
; . '·'3 1 00340038584903826 4567890 JK L 5 6 7890 J KL iV16 7890 J KL MN 7890 J KL IVI N 0 890 JK L r"iN 0 P9 0 J KL MNO PQ
. PLOA..rING
POINT
.'
RQtIT~!J~.
,,,,"'" ,.
~.!.QQ40_2_9_~_E35.~~5~S?,=?,?~~_.J._~.Q_Q.536qo5.3E3.~9(')04340 !.60?53~0055H26Q 1197(j('lnn02601 1120044~.~~g_~
3100462038534903826 124000001101124000014600494n14(')04901128nn4602601176000on2601
1 §?g} 82749000000.220 11 ~60 ~ 1 7649005?00260 1186n 1 1 76150084 7q0.o,O.~_ .
;I 3100582038584903826 16Q0857011A726010920118922011780118947n07(')2nl100260117601197
'
: 3100642038584903826 26011970118626011860117621010920118926Q1178n1189320117800000
....3-iOo7o2038S-g'49·03826-1-s-oi-i 98000'ooi4n 1 17800n-6Q47-6~i 09'40 130044nn774n i'19'i3'20 i 19-806000
. 3100762038584903826 330119700000210085701178440082201186330118600000150084700n02
t"'3100S'22"038584903826 . 150"117800000 i 501 1890000021 0~1 i 98000002501093(") 1198330 119800000
~ 3100882038584903826 430098601189430103401190460096601200310119001191250119800557
r-3100942-038~584-963826 12-01'0920000146008940130026011970 182649n 11 06()260 1198011973301
:....2lQ.Lr~Q.?.Q;?_~_~~~_~93~_?,§"_!2,OOQ9,Q_0 1 ~.':}9.~2099.0_.~':"?9l-~~?.Q.~ 400 150 11 R9.0()()OO ~ 1 ql 1980000S430'q
t
3101062038584903826 9d6011894401094010933201197a000026011A901092260000(;OI1974900,
:~--.----".---.....
3101122038584903826
00004826011510n46926nn51700non49n()5060~nn0nnnn0nn0nnnnnnn()n~
".
.
_"
; 3101182039004903826
*
* nnooooooooooonoooz
~_~,!"2.J?,Qs:.Q~f3584903826 160n53?012561501 75_~10no02160 1 1 120n09932n 119nnoon04900458n430 1
3101260n38584903826 2760119049nn966()43()12900116948220118q011682~nI32501176330117
3 1 0 1 32 Q..O 3 §.58:t.90 3 ~_?,§__§ 0 OQ n..9..~~5,~ l,l.~t;3 9_0.9.2.9 L? ~~ 1,_~~.! n 9~0 0 1 ~..('I, 1 347 \' ('I n n ~ 2 I, C' ~ . !.7? 0 1 17.9_'!.,'} 0 l.}.~_
3101380038584903826 401 1·.a490 1350'0 160 1441 01837250142801 1691101441 0 *0023011 75000
3101440038584903826 002601477014411201477000042601166000002201166000933201162000
3101500038584903826 002301 1 760'i-i652'601 1860193722"01186"00096320' 11 786000023'0 i i 860-113101560038584903826 863300082000001500081nOOOJ210009001~8626011R6000902301186011
3101620038584903826-6521000950669512013"4.7060"614701622012002601 i 86000944401"6-94-013', 3101680038584903826 253201186000002301186011971101189000N02501003000992601092011
:1101740038584903826 892601'19800092460 t-77401300490096604700-882-oT4'Ob490 1 i-2600-00~
3101800038584903826 oooocinnoonnnnnnoobnonnonnnOoJ9n692R08n~74n77p~68J6012804n~J4
, 31 0 1860038584903826--8249N490j38613'M759~i2-90<;i9-MT64-j,2'1267L674JI4332L266J0814 71< 922JQ
3101920038584903826 2597K630J000000000160n536019701501753 0 no03490122404301990011
-31-0 (980038584903826-'-9'0"4'90096'604'3"020100 i i69490-0966032"6 1'16900000 1 ?'O 1168000N 12301 19"3102040038934903826
*
7011762101189011684901718
i:_,.~..~().95~~.Q_~8~t.?_~0~S.?6
-
'
,
~
.....0
•
..
~
~
H
ffi
lilz
t-3
Q
$1
~
t;rj
t:O
---:-~~
REQUlREME~
CHANGE
~-3~r)2T140385R"4 9 n 3826-'480 nnn 00 n 6", n34 nOn 0 ~ ('\ (') ('\ 1 0246021 820 n300.-36-r;-j4 '1 n n05 nn 25034 n4nn 4 n n"
31021740385R4Qn382A 49n?194036n340nnOl0032034n000n0014034n3n0nnn46nno12012nn4702
3"1022340385849n3826 274(,)0300340000nOO 1 n8370375900 1 0049023340:j8n340nc;O 1 0037n3759n
3102294038584903826
05004100000000003400n00001083903759001n032n375dooon014n3759n
,--..
--_.
3102354038584903826 00P04602470013Q01403759000Kn46024500120043n24700375933024810
3102414038584903826 0000320376000000310~7580376n4902482032o2481noon0490241803302
il02474038584903826 481000001602117boON01602536n375916025240376n320376000b001403
310253403858490382~
7~9C0003460259R0120Gl1025J6nOo02110252400n~211021170GO014902
"31025Q4038584903826 518n26n2645n25242602640n2~3612026400nn0131n~758n37604302702n
31026540385849038?A 375q~ln3759n376012n2117nnn0145n2646037~9490~126n16n22n5nnn09
3102714038584903826 16027610375916027760211b1602781037~945n277nn37~9490283802502
31027740385R49n3R?6 118n37S911a2761000021102776nOOOll1027R10nn0?120220~0nonl~902
3102R34038584903A?6 750026028800277612022050n0014602906012n015n?118000(IOl102880n
"~102894038584903826 000149028500440293002481320212500000260220500079260297200064
"t3"102954038584"903826 1 1029720000424000000340346031 120120 ell n29 72no OJO 1202205nnnJn
3103014038~84903826 470?9660120026022050no74260j0680297221n3n68n0069240000003403
:.31-0307463"858-4-9038-26 ""-46031920 12nO 1202205000J04-?036sno 1200482603"171029722103171000 '
3103134038584903826 691103171onri061600469031831600445000004900422021254902126026
~-31"03T9-4038584903826 032750j'0681103275006a626Q33Ci0006421 03311 non69260220500079 i 6
ROUTINE
I
\J1.;
o
•
:- 3 f03254(,)3858490382·ft"o04"690~:r2"87260-1 r97"0000'0.490 1938t5212516C;04690~323160044S(\000()4q
3103314038584903826 00422000991103?75000~nll03311nOCJn12n22n500n~04603~52() 13004Q
3Io3374b39124902126
021260
E2
.g
H
~
to;?
tij
Z
1-3
Q
it!...,..1
a
l7j
~
c
o
o
~.
o
,0
PRE-LOAD
CARDS
o
360383800500
15039180000Z4903826
~1_0?>~ 14Q;3e~849938~6 1602472039402602173000642602253000791102173000J0260391800000
3102174038584903826 320391300000220391801822470223001200260392001826490246601603
_.~~_Q2_2~~038584903826 912000N33303913000001602337Q39131602429018181602436039192503
3102294038584903826 910039183303918000002503919004004302394000001102337000011203
._.~ 1 023540~8584903826 912000011102429000011202436000014902326026024170233731039130
3102414038584903826 0000260392001818330391900000440246603910320~9200000026000000
.~I.o.~4749.~E3584903826 3920110247200QJ01202253000J047021500120026024720006421024720
3102534038584903826 00692102472000691102173000J026021610006926024890006926022530
00741602448026481602455000M12602520026474902150M902668320392
3102594038584903826
-'.
3102654038584903826 000000490246602602659000742602710000642102710000692600000018
3102714038584903826 26~602871027102602847027101102847000J01602799039402602253000
3102774038584903826 79260392001826210392000000460288 4 012001600469028472601197039
.~~Q28~4Q38584903826 2049019380000016004690288316004450000049004220n0991102799000
3102894038584903826 JOII02847000J01202253000J04702776012001102847000K02102871000
310295403b584903826 691202659000J0460275Z013003 7 03563005002503583004003400000001
3103014038584903826 023903563001003900049001003400000001023400000001021602659000
310~074038584993826 043703563005002503583004004703136001003903563001003400000001
081202659000014703076012003 4 00000001024900024
3103134038734902114
.__ .~A$~~. .....
-
I
\.J\
I-'
•
ITER NO
. FU~~T I ONAL.
VAR OUT
VAR IN
. PRE":LOAD
.~1\!ID~. __
. DUAL
.
<.
360383800500
15039180000Z4903826
-." j i 021 i403~584903826
Aroo~ITm1
ROUTINE
....
310217403e584903826
3102234038584903826
3102294038584903826
-- -_. '3102354038584903826
----~-.
~_~!.Q~4_1 ~Q3§?8_~9.0_~J3?6
2600023018262603~4000079260218500064210218500069110218 5000JO
2400023000004702222011Q0260222102185260002300000120344OOOOJO
470216201200440002400023260002302205160356000000260341600074
2602372q?22126024130006~21Q241300069210237200069260242502372
21024130006924000000182646QF48601300160046902425260119700000
490, 2QOQ.Qonn2.4QOO 9~OOQ434 70~,±a.60 t1 OQ26000230009 9 260352 4 02.3.222603560024131203416000J0470233001200140356000000470254601200
48NI100000002602684035242602708035602603 44 000079260266503524.
160269603930260278003524260270103560160046902665260119702545
4901200000002603740000992600000018262603Q3000000260000001826.
1102696000JOII02701000Jd1102708000J0120344nOOOJ04602690013bo
2600000025452602857022212602864022212603416000741 t200469Q285_7
3102474038584903826
3102534038584903826
3102594038584903826
3102654038584903826
3102714038584903826
3102774038584903826
~16~~j4b3~584903~~6 26bl1~703740490193H00000260000000099210285700069210286400069
310289403~~B4903826
1~03416000~04602~2?01300160298403930260302500064210302500069
til
o
88
H
o
~
~-~
i
. .
PRE-LOAD· .CARDS
SD·!PLEX
AWORITHrvI
ROUTI:0JE
3162954038584903826 160309703930260344000079220393001826460321801200260308502221
3103014038584903826 160312100000260341600074260314003121120314000008160046903997
3103074Q385849038~6 2601197000004901938039301600469031331600 4 4500000490040200099
3103134038584903826 1400000000M347035980130021030850006921031 4 000069210312100069.
3103194038584903826 1203416000J 4603062013001102984QOOJOI1030 97 nOOJOI103025000JO
3103254038584903826 1203440000J 46029780130026033730222126n3361n356Q1 2 03361000JO
3103314038584903826 2603368033612203373000692603380033732600023n0000260000Onoo00
3103374038584903826 26000ooob02311Q363100n0147021140010034n n nnnnQln23803629nnl00
3103434038584903826 340000000108260357703373260354103361260350~00064210350500069
3103494038584903826 2603917000003803908001003 4 0000000108260391 7 0000Q380390800100
3103554038584903826 34000aO~0108~60391j000003803~0800100490211402603616031212600
310361403Y004902114
000018264Y03158000
360383800500
15039180000Z4903826
3102114038584903826 250366803747260002301826260354800074260219700064210219700069
3102174q.38584903826 21 021970006924C:0023000004702234:91 1.00g~Q22}30~ 1.?7?6.000?300000
~J022J4036584903826 2102J97000691203548000J04702186012004400024Q0023260002303522
3102294038584903826 160348100000260363200079260238002233260243302233260242100064
3102354038584903826 210242100069490254202400000018264702518011001600469024332601
3102414038584903826 197000004901200000002400099000234602518011004602586012002602
31024740385R4903826 4930238026037460000026000230009926034BI024211203632000 J04602
3102534038584903826 630012001102380000jOl102421000J01102433000J04902374026026090
*
*
f\)
I
3102~9403~584903826
23802403~460000047024700130049025180140348100000470266601200
3102654038584903826
310271.4038584903826
3102774038584903826
.31D2834038584903826
3102894038584903826
3102954038584903826
3103014038584903826
_.3103074038584903826
3103134038584903826
3103194038584903826
3103254038584903826
48NII0000000260280402493260282802233260363200079260278502493
16028160393026029000249326028210223316004690 2 785260119702665.
490120000000260392000099260000001826260393000000260000001826
1102816000JOII02821000JOI102828000J01203632nOOJ046Q281001300
260000002665260297703481260298403481260354800074160046902977
2601 1970392n4901938000002600000000992102977no0692 1 0298 40006Q
120354800aJ04602942013001603104039 3 026o3145n00642 1 0314500069
160321 7039302603632000J9220~9300 1 '~",,4603338n 1200260320503481
3~0331403d584903826
1203548000J04603182013001103104000~01103217000~01103145000~O
H
3103374038584903826
.31034340.:)658490.382.6_.
3103494038584903826
3103554038584903826
3103614038584903826
1203632000J04603098013002603469022331203469000J0260347603469
2203481 0006.92603,48.a034Bl26QOG2.300000260000()o0000260000nooo23
1103667000014702126QOI003400000001023803665001003 4 0000000108
!2!
160324100000260354800074260~260032411203260n0008160046903217
260119700000490193803930160-0409032531aa0445n000049004020ooqq
1400000000M3470370601300210320500069210326000069210324100069
260368503481260364903469260361300064210~61300069260374600000
3803737001003400000001082603746000003803737()0100 34 0000oonln8
260374600000380373700100490212602603724032412600000018264903
3103734039044902114
*
278QOOOOOOOOOZ
310~~740~8584903826
'~
I
\Jl..
*
o
o
(J)
o
t-t
~
8
o
o
. PRE-LOAD
CARDS
FINAL
BASIS
OUTPUT
ROUTDlE
o
o
36Q383800500
;-15039180000Z4903826
3102562038584903826
310262203B584903826
310268203~S84903826
3102742038584903826
360382600500490382603400100001022602653000642102653000693703
7S900500390375900100260391700000340001000108L803908001003400
000001023400000001021603533000063703759005003903759001001203
533000014702714012003400000001022603321000641103321000~02603
:~!Q?8020~~5a49Q382~ 369026531103369000~02603013033692103013000792603001030131103
310286203B584903826
3102922038584903826
3102982038584903826
3103042038584903826
3103102038584903826
3103162038584 9 03826
3103222038584903826
3103282038584903826
3103342038584903826
3103402038584903826
3103462038584903826
3103522Q38584903826
3103582038584903826
3103642038584903826
3103702038904902562
360383800500
15039180000Z4903826
001000J02602965030131102965000K02603545000792600750026662600
7 4 00259316007250000016007150000016030440nOOn2603097029652603
109029651603085000001603157000002603213030132603533000742200
000037064603214012001600469030972601197000004901200000004403
166nonn024nnn99n07504703214nl100260075nonnGQ26n0730n00on4903
2140240009900740460321 4 013002600740000Q926007200000021030440
006921030850006921030970006921031090006921031570006921032130
00691203533000J047030380120n2603918000n034n~ocnOOln238n3909n
0100320195500000270194800000260-9180071434000000010635039150
01002603429033212600760000003.~0755000n044034860076033007600
0000320352100000 4 9034980330352100000260076900760150077ooonoo
330195500000320074000000270194800740260391800724340000000108
3803915001 0 033007500000033019550000027n1948007501102965000JO
1103321000Jnl103369000~012035l~5000J04702q06nI200490002400000
*
000007 n 7n7070037Q707Q70nnOZn
•
\J1.
\.J.J
I
310~948038584903826 3201956000003103898037074402008019473301947000001603917nooKn
PAGE
HEADINGS
3102008038584903826
3102068038584903826
:- 310212803$584903826
310218803cl584903826
310224803bS84Y03826
3102308038584903826
3102368038584903826
3102428038584903826
3102488038584903826
3102548039044903826
2503919004004902582
FUf'(JCTIONALZ
VAR/<:OST
Z
ACTIVITY
Z
LIM VAR
Z
LOWER L l,iVl Z
LIM VAR
Z
UPPER L IIVl
Z
2600760037061401939000N44702064011001600757R9999490214801201
939000M74702136013001602135019402102135019~9150193qOOOOD2100
760019474402442019551602219000041602287007531602282038991602
243007~31602250038993201957000004402276019574302264007~31603
7~9000004902288033019570000025038990075311022870000111022430
000111022820000211022500000212022190D00147n22200120044024160
195633019560000033019570000016022190000549023120340000000108
390389900100421403917000K04702478012003200760000002100760007
7047025220130016039170000049Q214801603917nonK049021487070707
003707Q7070000
*
*
(/1
o
t-f
c::
...:;
H
o
!2!
PAGE
HEADINGS
PRE-LOAD
, CARDS
; MATRIX
. PUNCH
ROUTINE
360383800?00
15039180000Z4903826
3102562038584903826 3 4 0001000102L4001000010216032530000637n3759n0500390375900100
310262203ti584903826 1~03253000014702~9801200340000000102260321700064210321700069
31026~2038584903826 2103217000692603265032171203217000J02602861n3217110286 1000KO
3102742038584903826 260289702861220289700069260290902897220290900069260322400074
31~28Q?0~~584903826 2600750025852600740Q2574160071500000160072500000160294ononoo
3102862038584903826 260299302861260300502861160298100000160305~00000260310902909
3102922038584903826 260325300079220000003438460311001200160046902993260119700000
3102982038584903826 4901200000004 4 03062000002400099007 4 0 4 70311001100260074000099
3103042038584903826 260072000000490311002400099007504603110013002600750000992600
3103102038584903826 730000001102940000JOI102981non~nl1029930nOJnl1030050on JoI103
3103162038584903826 053000JOI103109000J01203253000J047029340120n26Q3918000003400
3103222038584903826 0000010238039090010032019550000027019480000026n3918007143400
3103282038584903826 0000010838n391~001002701948007402603918007243400000001083803
3103342038584903826 91500100270194800750210286100069210321700069210326~OOO691203
3103402038814902562
*
224000J047028n2 n 12nn49C002400noooooon
VAR/COST
Z
SHAD PRICE Z
LIM VAR
Z
LOWER LIM
Z
LIM VAR
Z
UPPER LIM
Z
360383800500
15039180000Z4903826
3102562038584903826 470282600400310356303401310356200048150357300000390356300400
3102622038584903826 310356303481260356700079260357200074150357300000380356300400
3102682038584903826 260278400064110278400001230006900073320009500000210009900069
3102742038584903826 21000980007821000990278426028130009938000nnn0400110278400000
3102802038584903826 140278400000470277801300410000000J00488888R88888.49000240000Z
::.,.~,1 pj 4 0 J 0 3§ ~84 9 03826 - - - - -- - - - - - - - - - - - - - - - - - - - - - - --- - -.:.. - - -- -- -- - -- - -- - -- - -- --- --31~3461038584903826 -------------------------------------~----------------------
·~i03521038784903826
250356100~002503723004004902562
c
*
------------------~~~--~~---------------
o
c
,
\J1..
r--
~
CJl
o
81-3
H
o
~
o
o
o
c
COMPUTER
TECHNOLOGY
'II
I
II'""
"
c)
o
o
L ...
o
Feb.1,19f>5
1620 Correction
0101
10.1.006
, "Linear Programming Code for the card 1620 with Punched card
Option for Final. Output"
An error in the subject program was reported to the 1620 Users Group
and subsequently to us. The enclosed changes should eliminate the
error.
The Right Hand Side Changer Program (cards numbered 200 - 260) should
be modified to eliminate a stray flag bit left in memory position 03513.
The following changes should be made.
1.
Card #229 of the RHS changer program. Change cols. 1 -7 from
4800000 to 4903484.
2.
Card #259 of the RHS changer program. Change from col. 33 on to
contain:
33035l~00000480000000000+00000~l0345203508000259
o
,"
~
3.
Card #260 of the RHS changer program. Change cols. 1 - 13 to
490212600000+ and 63. - 80 to
010350803520000260
- ...
--
--
4.
Add Card #261 to the RHS changer program. Cord cols. and contents
as follows
Col 1 - 69 - all-zeros
Cols 70 - 80 - 02114000261
5.
Appendix A, Section D3 should read:
uRHS changer itself loads and a stop at 03501 is
executed ...
A complete corrected RHS Changer deck has been distributed since
o
Feb.2,1965
..
..
,.----.~
"
"~.-
_.
- ".--.--~
.......
"'.'""-~"
..... --
o
0
'1.',
1/
o
o
o
1.620 Correction
hb.1,1965
0101
10.1.006
File No. 10.1
"Linear PrOsra-1Dg Code tor the card l.62o with Plmcbed carel
Option for 1'1nal. OutPlt~'
UNEAR PROGRAMMING CODE
FOR THE CARD 1620
WITH PUNCHED CARD OPTION
FOR FINAL OUTPUT
An error in the subject program was reported to the 1620 Users Group
and subsequently to us. The enclosed changes should el1minate the
error.
The Right Hand Side Changer Program (cards numbered 200 - 260) should
be modified to eliminate a stray flag bit left in memory position 03513.
The following changes should be made.
1.
Card *229 of the RHS changer program. Change cols. 1 - 7 from
4800000 to 4903484.
2.
Card *259 of the RHS changer program. Change from col. 33 on to
contain:
330351~00000480000000000+00000~10345203508~00259
3.
Card +260 of the RHS changer program. Change colli. 1 - 13 to
490212600000+ and 63 - 80 to
010350803520000260
4.
Add Card *261 to the RHS changer progr~. c.rd cola. and CODtenta
as follows
Col 1 - 69 - all zeros
Cols 70 - 80 - 02114000261
5.
Appendix A, Section D3 should read:
.. RHS changer itself loads and a stop at.Q1§jll is
executed. II
,
Lou DaviS and Art Nickel
IBM
401 Grand Avenue
Oakland, California
A complete corrected RHS Changer deck bas bee ct1atr1buted as.noe
Feb.2,1965
1
,..
1620
10. 1. 006
PROGRAM ABSTRACT
DECK KEY
Title:
--
1.
Data Loader - 000-053
2.
Cost Changer - 100-107
3.
RHS Changer - 200- 260
4.
Solution Deck - 300-916 (not continuous)
Linear Programming Code for the Card 1620 with Punched Card
Option for Final Output
Subject Calssification:
A.
Floatirig Point Subroutine
300-328
B.
Shadow Price
400-423
C.
Dual
500-526
D.
Simplex
600-628
E.
Final Basis
700-720
F.
Fix and Print
750-768
G.
Non Basis
800-821
Authors:
---
Lou Davis and Art Nickel
IBM
401 Grand Avenue
Oakland 1 0, California
Direct Inquiries to:
Purpose:
10.1. 006
Lou Davis or Art Nickel
IBM
401 Grand Avenue
Oakland I 0, California
TEmplebar 4-7070
Solution of linear programming problems with output of
detailed results. Given coefficients ai j, cost coefficients
c j ' and requirements b i , determine Xj such that
~ ai )Xj
J
H.
5.
Matrix Punch
900-916
Z'o
and
~CjXj
The deck mentioned in Section I. on· Page lO
= maximum.
J
Mathematical Method:
Computations are performed by the Dual Algorithm
until a feasible solution is oiDtained. Control is
then given to the Simplex Algorithm for optimization.
Many, many things go on before this stage is reached
and after. It is quite important to read the instructions for order of program input (Appendix A) and data
input carefully.
a.
Accuracy: All computations are performed in 2and -8 floating point arithmetic.
b.
Derivation-Reference: Some (Nichols') notation
and techniques were derived from the writeup of
the "Linear Programming Code for the Augmented
650" by O.R. Petry. Reference is also made to
C. R. Nichols' writeup for the 1620 paper tape
input/output version.
4
3.
o
= b i with Xj
o
c~
y
o
o
o
Restrictions, Range:
a.
Requires a 1622 Card Read-Punch Unit. This
program was rewritten for a 20K machine. Certain
changes in the prograjTI deck are necessary to
enable it to run on a 40K or 60K machine. These
changes are indicated in Appendix E. The size
of the problem which can be handled is restricted
by the following relationship:
(m+2) (n+3)
COMMENTS
This program and its documentaUon were written by an IBM
employee. It was developed for a specific purpose and submitted
for general distribution to interested parties in the hope that it
might prove helpful to other members of the data processing
community. The program and its documentation are essentially
in the author's original form. IBM serves as the distribution
agency in supplying this program. Questions concerning the
use of the program should be directed to the author.' s atte;:;.iion.
For certain probleIns it has been found that the value for "essential
zero" located in memory positions 3144 and 3145 may need to be
increased to .ome value greater than the 10-8 value to whi:::h it is
set in the prolram..
~memory - 3920
10
where m is the number of restrictions,
n is the number of non-baSis independent
variables, and memory is 20K, 40K, or 60K.
b.
Data must be prepared in the format specified in
Appendix B.
c.
Output may be either on the typewriter or on cards.
The optional final matrix punchout is on cards.
(See Addendum No.1 to program writeup).
Storage. Requirements:
Any size memory - see Restrictions.
Equipment Spec1fltations:
BaSic 1620 with Card input and output.
Source Language:
The original tape program and the modification
for card input and output have been coded in
1620 SPS.
Program Execution Time:
The precise time required per iteration depends
on the size and density of the matrix. As an
approximation, a problem with 30 equations and
40 non-basis variables requires about 20 seconds
per iteration.
Check Out Status:
(b
This program has been widely and successfully
. used in the field for some time now on many problems of different sizes and descriptions.
j
1620 LINEAR PROGRAMMING CODE FOR CARD lliPUT/OUTPUT
Nichols, Nickel and Davis
TABLE OF CONTENTS
Addendums to 1620 Linear Programming Code - File Number 10.1.006
I.
General Information
L
IT. Appendix A
- Operator Information
m.
- Input Format
Appendix B
N. Appendix C
V.
Addendum No.
To avoid an overflow condition and certain loading inefficiency when using
the Data loader program, make the following change in the program deck
and listings for the Data loader:
Object Program
- Output
- Card Output of Final Basis
and Non-Basis
VI. Appendix D
- Sample Problem
VII. Appendix E
- Storage layout and listings
VITI. Addendum No.
- Punched Final Output
IX. Addendums
- Overflow Negative Data and
Conversion of "Punch Option"
Deck for 40 K or 60 K.
Card No.
location
mm....
IL
32
01946
4902022
4902090
Symbolic Lisling (Data loader)
I
~
location
From
I2-
TSTRC + 12
01946
B Fill .
B Signst
The subject "overflow" causes no apparent error but only slows down
the execution of the program. If the above change is made, data cards
~ not contain record marks.
n.
m.
A second item that it would be well to note is the following:
When using negative (minus) data values, the minus sign (11 punch)
imustbe in the first and only first column of the ten ~JO) column field
alloVled for the number. That is, column 9, 29, 49 and/or 69.
If this is not followed, the value will be treated as positive.
To convert the "final output - punch option" deck for use on a 40K or 60K
1620, the following cards and columns should be changed in the manner
prescribed in the program writeup:
!/
o
o
()
o
o
o
1620 Linear Programming Code for Card Input/Output
-2-
Nichols, Nickel and Davis
Addendum No. 1 to Program
Card Number
Columns
700
3 and 51
3, 15, and 39
?:l and 39
701
702
712
718
47
800
39 and 51
1.
Reference: Item 3. "Restrictions"
23
912
15
I
part c.
The Final Basis and Non-Basis Output may be punched on cards
rather than typed by replacing caris numbered 700 through 916 c f
the solution deck with a different card deck bearing the same first
and last number (700 and 916) e:nd approximately the same numbers
in between. (These cards are the 'last section in the deck. )
43
814
write-~lp
These columns contain ones (l's) as the first digit of 19xxx: addresses
and should be changed to threes (3's) or fives (5's) for the 40K or 60K
machine.
II. Reference: Appendix C - Output
Items 2 and 3
2.1and3.1
Final Basis and Non-Basis Output using "Punch Deck" for cards
700 - 916. The final value of the profit function is typeq in
floating pOint form as before.
The same information is punched as is given with the typed output.
The card format is as follows:
Card Columns
1 -
2
3 - 10
Code.11 - Final BaSis
22 - Non-Basis
Zeros
11 - 20
Identification/Cost Coeffic: ent
21 - 24
Zeros
25 - 32
Activity - Final Basis
or Shadow Price - Non- Bash'
o-
33
Record Mark
34
Zero
3S - 38
Limiting variable
2 - 8 punch
10
9
39 - 40
41 - 48
1.
Zeros
Lower Limit on Cost - Final Basis
or Lower Limit on Activity - Non-Basis
Identification:
a.
1620 Linear Programing Code for card input/output.
b.
This program is an amended version ot C. R. Nichols' 1620
Linear Programing Code for paper tape input/output.
49
Record Mark
50
Zero
a-
2 - 8 punch
unchanged tor this edition.
51 - 54
Limiting variable
55 - 56
Zeros
Upper Limit on Cost - Final Basis
or Upper Limit on Activity - Non-Basis
65
Record Mark
66 - 80
Zeros
a-
This version edited by Art Nickel
and Lou Divis.
c.
57 - 64
Most of
his original program and much ot his writeup have been retained
2.
IBM Branch Office, OIikland, California.
Purpose:
Solution ot linear progra8l1ng problems with output of
detailed results.
2 - 8 punch
Given coetticients ai,j' cost coetticients Cj, and re-
quirements bi, determine x j such that
~ ai,jxj= bi vith Xj ~ 0
J
and
:2.Notes:
1. The card output is numeric so there are no decimal paints
or minus signs.
3.
c jX j
::<
qxillUl10
Restrictions:
a.
2. Negative numbers are denoted by a flag (II punch) over the
low order digit 1. e., card columns 48 or 64.
Requires a 1622 Card Read-Punch Unit.
tor a 201< _chine.
This program vas revritten
Certain changea in the program deck are necesMry
to enable it to run on a 401< or 601< _chine.
3. The Activity I Shadow Price and Limits are 8 digit numbers,
and the decimal paint is assumed in the middle -- that is, 4
positions from the right or left, so (xxxx. xxxx).
dicated in Appendix t;.
(11...2)(n"'3)~
where
II
n 11 the nWllber ot
?!J/
10- 3'o
hYl4./ly
~£
ch4111(J
-1-.,
.. 1..
'1/. l
1-
:l.h
to accept changes.
~
~
-1,
11
-
- l.'h,.
~
;
'-
_=~.1
::
lfM~
= ,
'1
-tYc.
+-
y?
1 ...
""
=10
.,,.
ttL'>' 0
:. 10
f.
-1.
'"
40,
i- "f~
- lC,
,¥,~o
- ¥-y
"'7
+~
~"¥~
---y~
311.
+ '1...
t ?Jh
,.
---~~
+l'"
+-
It the output phase 111 inter-
rupted hef'ore its cOlipletion, hovever, the computer is not conditioned
tV$'"
1, -1...
-1, -l1/..,
~o
It ahould he noted that changes -:I' he initiated under the procedures
ghen in Appendix A either i_diately atter loading s matrix or at
+- 3"fa.. -~l
1-,
~12-
:5kMPI.-~
C.,IKIS.
CASE TESTl
ITER NO
FUNCTIONAL
VAR OUT
VAR IN
n01
~42003998n
I)o0599999§
I)o0200200~
n02
~144000001f
n00699999§
1)0010010011
FUNCT IONAl
~1440000011
VAR/COST
ACTIVITY
~ ,J,.• ~~,+ .pj,~.1
der( .. d,Yl~
...."....
....... .
~.
~
LIM VAR
lOWER lIM
:l",.fc-.k
LIM VAR
CII\
:5tnse..
I.
UPPER LIM
n00200200~
1.6000
11004
3.0000-
'0003
.5000-
nOO 100 10ob'
1.2000
'0003
4.0001-
'0004
.6667-
n007oo0000
6.4000
1)003
.4285-
nD04
.1666
D008000000
3.2000
Do04
.5000-
1)006
2"99.4975
n009oooo00
2.4000
nD04
.2500-
D003
1.0000
VAR/COST
SHAO PRICE LIM VAR
lOWER LIM
L1MVAR
UPPER lIM
1)o0699999§
999.7990
1)009
3.0000-
DOOl
2.0000
n00599999§
999.3989
1)007
4.5714-
D002
4.0000
11003000000
.6000
1)002
4.0000-
Do07
4.5714
D004000000
.2000
1)001
2.0000-
11009
3.0000
0
D-3
o
00,,9
1.
0004
-I.!>
0000
0001001000
0002002000
0000
o
D-'-I
APPEND IX E
S'TCRA;;E LAYOUT AND LISTINGS
I.
STORAGE USElh
;!emory locatio')s froll' 00048 thr""gh 3747 are usod by th~ progral1.
Ic~d
Loc:ti",n~
rcuti'le,
used for the ... ,t.-ix ,,~d its "'8nirul~tkn,
d'i~gra~.~
i .... ,jic~te-5
t..,~
.
The )otriy. is stor"d in colu'lln sequence
TI.,"'ner in 'u!'"'tjc'" !"'I?"trix
3760
37'50+ 101 ... 1)
PRCffiM~
ORDER
uses memory from 03749 upward.
ID/Cj
S+ 101 I n+l) (m+2)..a)
S+IOI (n+I)(III+2),
5+ 101m+~)
$+ 101 2m+5)
S+IOI 1"+1)1111+2)+ I)
fG,'
-
~
9
~
s+ ,em s. 101 2m+2)
Incre~sing
S.1013... 4)
S Is com;:uted for e"ch ?rotlem and Is e'lual to 03760 + 10( ... 31.
2.
,no
stcred:
S+1012111+4)
!i
~::
~re-
Functional
c
8
'"c
elern~nt~
S+ 1012111+3)
S
o
19840-19963 are used fvr .. pre-gram
,',Iemory fl"Oll1 3749 up to the required location lor 19839) Is
is. ')V'fiCV"r, f'05sible tJ ",. 000JJ-:'''0047 for inserting).
The following
Loc~tiuns
",,,(,4, 1S;965-0M44 are used fur a c'r-:1 in,'ut .re~ for data, he'1ings, and program input l i t
J
"10«,., "~".,,
S+IO( ("+2)(m+2)-2)
All addresses are fTeld address...
I Card nunbers are In col umns 78-80 of progralll decks)
••
DATA LOADER
000-053
b.
COST CHANtER
100_101
C.
RHS CH~'IGER
£-1
o
d.
300-916 (Not continuous)
SOLlmON
I I) Floating Point Subroutt,nes
300-328
(2) ShadoW Price
400-423
1:,\) Dual
500.526
I~)
Simplex
600-628
1.5), FInal Basis
700.720
(6) Fix nnd fri nt
750.768
17·) Non 3 asls
600-821
(8)
tt'."trlx Punch
900-916
00.80 Ifstlngs, wIth remarks, of the '!lachine l","gu3g~ pr9gr:m decks follow.
,.
the
conden~ed
output.
Columns
1-60
61
62
63-64
65-69
70-74
75
76-77
78-60
Con t~"lts
Instructions or const .. nts
• (record nark) if full 60 columns are us~d. Oth~r wise the record mark is at end
of the d~t~ being punch.,d.
1
~, Loader' Code
"'ddr~ss of wher., ttli! first character on th., c?rd Is to be plilced in memory.
Addr.,ss of wh,rQ th. last charecter wi II f~ II in 'I1""..ory
Flag
t40t used
C"rd s.,quence numb<>rs
This listing was mad., on .407 !>CCL'unting !.Iachin.,.
.Iph"betlcal characters in the J-R range.
bit recalcitrant.)
4.
These c,rds are in a format similar to
Spec if I ca II y s
Sinc., the 407 does not hav., flags, flagged dIgIts wi II appear as
A flagged zero wi II appeer as a
-
(',inus) or a zero.
IThe 407 was a
A record mark prints out as a Z.
o
In order to allow this program to run on a machine with great.,r than 20K memory, certain changes hav., to be made.
dIgIt In the attached lIst that is marked with an
a
J
(flag:Jed one).
fl~gged 5) for 6()<.
This
*
must be chan9"d.
I lor flagged Il must be changed to a
In each C 021I4t
1:688
,tee e,e8.'8ae ••~ •••••••• O' ••
1&1
19:'11
uuee
o
o
---0 ._-
o
IUi,ul1nl
e;e.eteU.8681888'9.eUf1e-e.uerUU·e~UlneUUdnn .......
86}4 U'88.U1YU'8eeOOelee&fb8'1'UneeUUUUlnUl'.... " ..I4H ..
1ft" 3!i!e,S '845 4e36jhh4~S'hhn,lii§4446S~Un"n.n""""II"W!"
o
-
0
00079
/IIOP
..
0
03476 49 19840 00000
02114
.-~~---.--
0
'"
.-
J3", ?f!. __ ____
o
26999 9S98f6 _318
02114
o
e8eeee!ee!68el14ee!14~5e660eOeel14'8eel~e6eee
o
o
o
DORG 02114Z
02114 47 02834 00400
START
BNC4 OUTZ
TR
SLUSH.48Z
TFM
SLUSH+14.0.27Z
02150 11 02144 -0005
AM
010+6.5Z
o
02162 14 02144 -3024
CM
010+6.SLUSH+164Z
o
02174 47 02138 01200
i:lNE
OIDZ
o
02186
WACD SLUSH+IZ
02126 31 02860 00048
02138 16 -2874 -0000
DID
·0
02198 25 00079 00400
TD
02210 31 02860 00076
TR
SLUSH.M-3Z
02222 25 00074 00400
TO
N.400Z
02234 31 02864 00071
TR
SLUSH+4.N-3Z
02246 15 02868 00000
TDM
SLUSH+8.0Z
o
o
o
o
o
o
02258 25 02863 02858
TO
SLUSH+3.GLUGZ
o
02270 25 02867 02858
TO
SLUSH+7.GLUGZ
TD
SLUSH+9.GLUG.2Z
CM
YOU+6.SLUSH+76Z
02330 16 02939 0-000
TFM
SLUSH+79.0.8Z
02342 33 02936 OOUOO
CF
SLUSH+76Z
~9
02861 00400
02282 25 -2869 02858
YOU
02294 11 02288 -0001
M.400Z
YOU+6.1Z
02306 14 02288 -2936
o
o
02318 47 02282 01200
o
02354 38 02860 00400
WW'"(l
SLUSHl
02366 32 02936 JUOOO
SF
SLUSH+76Z
02378 26 02629 00064
TF
GOOD+ll.SADDRZ
02390 11 02629 -0001
AM
(';00D+l1.12
02402 26 02593 02629
TF
NICKEL+l1.GOOD+l1l
02414 23 00069 00073
02426 32 00095
o
o
MAND2.N-ll
GOuao
5F
95Z
99.MAND2Z
02438 21 00099 00069
o
o
02450 21 00098 vvJ78
A
98.M-ll
o
02462 21 00099 02629
A
99.GOOO+l1Z
o
02474 26 82492 00099
TF
KNOW+6.99Z
o
TD
* .400Z
02498 26 02569 00099
TF
ART+ll.99Z
02510 15 00C79 OUUCO
TO'"
M.Ol
02522 15 00074 OOUJO
TOM
N.Ol
o
THAT
AM
SLUSH+79.1.8Z
o
AM
NICKEL+l1.70Z
ART
eM
NICKEL+l1.*l
02486 25
~2486
00400
02534 11 02939 0-001
02546 11
02~93
KNOW
-0070
02558 14 02593 -2558
BNL
YESZ
HOLO.*.2Z
o
TF
DOES+6.NICKEL+l1l
o
o
02582 25 -2859 02582
NICKEL TO
02594 26 02612 02593
02606 25 02606 0)400
OUE.S
TO
* .400Z
02618 31 02860 02618
GOOD
TR
SLUSH.*Z
o
.--~-------------.-
0
02630 H. 02936 00000
CF
02642 31 02160 00400
WHCD SLUSHZ
02654 32 02936 00000
SF
-.-----._---_
.. --
WO~K+6."ICKfL+11Z
TF
...... -._-- ......
TO
*.HOLoZ
02690 26 02629 02593
WORK
TF
GOOO+11.NICKEL+11Z
o
02702 49 02534 00000
B
THATZ
RIGHTZ
o
o
02678 25 02671 02859
........... ---.
................
02714 46 02774 01200
YES
BE
02726 25 -2860 02858
THATS
TO
SLUSH.GLUG.2Z
027311 11 02732 -0001
AM
THATS+6.1Z
02750 14 02732 -2930
CM
THATS+6.SLUSH+70Z
................
OUT
H
B
19840Z
00019
M
OS
.79Z
00014
N
OS
.74Z
00064
SADDR
OS
,64Z
o
o
o
o
o
o
o
o
o
o
o
o
o
o
028511
GLlIG
ONP
lZ
o
•• ___ • • • • • • • 4
• • • ___
•
__ • • • • •
02762 47 02726 01200
BNE
THATSZ
RIGHT
TF
KI 000+ 11.GOOD+ lIZ
KlooO
TR
SLUSH.*Z
TO
SLUSH+ 71 .400Z
02810 33 02936 00000
CF
C;lI'~H+ 761
02822 38 02860 00400
WHCo SLUSHZ
_._-----_ .. _--
02774 26 02797 02629
········ __ ····r .. ·· ...
02786 31 02860 02786
.. - .. _---_._-
02798 25 02931 00400
"0 ••••• _
--._-.------
•• ____ • • • • • • • • • _
02834 48 00000 00000
02846 49 19840 00000
'C)
o
o
o
o
SLUSH+76Z
02666 26 02614 0-2593
.'6\
..~ ...
SLUSH+16Z
o
00069
MA,.02
OS
02859
HOLD
DC
02860 41 00000 00000
SLUSH
-----
.-:!.~~.~~~~~85'i10
1.0Z
Z
o
o
0602859021600
NOP
o
o
DEND
L688 8808
IUluuelue
.. -.- .. _- .. _- ..... .
36881 1188858 8 !!I 08 8 1 Tl!88588~.~~.~~.~~."~.~8.~!!I!lI' le88·;~~~~8II~8eU!!le8 .................... ~ ..... .
\
'10i!
'~9~!!I8~ft8~8
U~h!!IIU~
. .~i8~!!I86'"U"'"11tef!88~~~·Hl~~~P-N~·~~~.~~~.~~"'*.~~.~~
~'8,,"'
['~1f)fI<1I60&f'l[~t+t~~~'~['etet!'~~~~=""""""'" .
'0"11 281!808 061"
!['"OJ~8~!~6'68600800001183T080J661[1.16181'1811f.['f6[41f
0
... - ...... _---_ .......... - .... _- ............ .
iU!!6 )5£8!!15 -II 5
.. 8] 6.!!I[ ~I.~~.! ~.~!.~ ~~65.]~6 '8 •.~ ~.~~.l ~~~.~~.~~.~ ~.~~.~ ~.[ ,.].,~.~ ~.[ ~~~-~~.. 0···· -...... .
. ''''II! H%T8 9@;j!!l ,,~e !.~ '_8;J':4 56T8J6d'(L '6'8) OdIl!LP48T8 "d'.LlII." J 8dll!tflfl~~ ~~~~~~. -~- _........ .
....
_----_._--_._---------
o
I-tf
1114r~IX
NON
PUNCH
BASIS
DO/PtlT - Z
I
I
Mil rRI){
PUNcH
\
I
I
I
LO/tOEt
I
CO~T
71
o
,,
,
72
RHS
·CHANfJEf(
C.HII~lt
~
'Y
o
o
o
o
NON
PIX
BI/SIS
OurPIJ'T -/
@
7~
5U8KOtlTIN£ -
@)
7~
Z
FIIVIIL
FIX
SU6~OllrINE
ElI.t~'j:
our fliT
-
Z
Dr PIX,I1I(G
AiG is
"OF
i,..t F/t.IJ
locfl-l.ilJII-
flDftt,°l&.j
'to be
81lSJ5
-/
f()
c.D1t IIct'teJ
a ... J
wi: 'j fed.
C12 Ie
{r,r&
L Dwe .... Lim ,'t
:- C -(LOWER)
i
C12k ( T,fe.
Ufft. ~ L i",,'t
;: C - (UfPtt)
i
I
I
NON
8I1SI.S
OtJrPIJT
@
@)
1~
7{
~
Cj
o
o
o
o
Ffllll1L
B/?SrS
OtlTFtlr - /
@)
71
(b
:JIIIIPLEX
e
-4
78
SIll{ PI.. eX -.3
SImPLEX -
e
4
r~
pl·vat
t< ' p:lllt
W.
(lV
K'·"l (AI"",,.,
8D
!1
~
o,." ..
~DW
c,I"".,.,
~
-~I
o
o
o
o
SIlJtPL EX - /
DUll/. - 4
T!Jfl!.
'ltLyat iDA.
F'lIid,iJllt#
1P/CDSt /C
IO/e.Dst r
I
I
8RS:1S
O/Jrl'IJ"f
K ~ f;lI~t
C()JtJ.~1I-
C3~
9
gz-.
{)tl/lL - 3
2
Pt/r1L-c
q:
r ':
f,'lIdt
J(:
f,'f/ot colVIIt/l.
WOt"K,'lfj Cool""."..
w.:
8'
~
YOW
81
~O
o
o
o
o
DtllIL -/
SHIlPOI1/
PRICE -
I
I
SImPLEX
I
I
I
()UI1L
8{
8~
4
SHI1POW
PRICE - 3
SJlllfJ6w
PRICE -
CD
c.
\~,
81
o
®
c
,,.,
@
o
o
o
o
S IiIlOt)w
PRICE -/
f~ 1-/5
C H/lt1lGER -.3
8'
~
{(II S
RI-/S
CHJ1NGER -I
c IIIlIIIG E R - z,
t?~
£11
o
o
o
o
o
ctJsr
c IIIIAlGE~
o
COST
-
CHIIIIBER -/
e.
GO
/
/
I
/
RHS
C HIINBEf.
"
\
\
\
sHlivoW
f«lct
q1
LtJ/liJER-3
LCJI/PER-Z
q{
o
'I'
Q
c
o
o
LOJ1f)ER-/
ReaJ '"
Col/! s:: W+l0{l",3i
5-to .. e S
s't"o .... "..
S
/
I
COST
ClllINGEt
,,
,
I
./
./
I
SHAPOw
I
f'f ICE
({HS
C I/JING/!R
1?
0,
A,
U
o
COMPU1ER
TECHNOlOG'l
I
i
THE riig~~fftl~ifmaIIMrrER '
1 026 2035 1
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.3 Linearized : No XMP Toolkit : Adobe XMP Core 4.2.1-c043 52.372728, 2009/01/18-15:56:37 Create Date : 2014:03:06 11:12-08:00 Modify Date : 2014:03:06 10:47:21-08:00 Metadata Date : 2014:03:06 10:47:21-08:00 Producer : Adobe Acrobat 9.55 Paper Capture Plug-in Format : application/pdf Document ID : uuid:1a4ae8f3-0af1-574e-a50e-a1b050036c8d Instance ID : uuid:b6355aae-42cb-6f4a-8139-729909a3060e Page Layout : SinglePage Page Mode : UseNone Page Count : 156EXIF Metadata provided by EXIF.tools