Trailing-Edge
-
PDP-10 Archives
-
decuslib20-01
-
decus/20-0020/revsim.tuk
There are 2 other files named revsim.tuk in the archive. Click here to see a list.
1' NAME--REVSIMPX
5'
10' DESCRIPTION--REVISED SIMPLEX LINEAR PROGRAMMING ALGORITHM.
15'
20' SOURCE--REVISED 3/14/68 BY PROF. W. CARLETON
22'
25' INSTRUCTIONS
26REM PROGRAM SHOULD BE USED ACCORDING TO THE FOLLOWING RULES.
27REM YOUR MATRIX OF CONSTRAINTS SHOULD BE SET UP IN THE
28REM FOLLOWING ORDER. FIRST COME CONSTRAINTS WHICH ARE LESS
29REM THAN OR EQUAL, THEN GREATER THAN OR EQUAL TO, AND FINALLY
30REM EQUALITY CONSTRAINTS. NOW CONDENSE YOUR CONSTRAINT MATRIX
31REM BY DROPPING ALL ZERO ELEMENTS. THIS MATRIX SHOULD BE FILLED
32REM OUT WITH ZEROS SO THAT IT HAS THE COLUMN DIMENSION OF THAT
33REM COLUMN WITH THE LARGEST NUMBER OF ELEMENTS. CALL THIS NUMBER
34REM "M". CALL "N" THE NUMBER OF COLUMNS IN THIS MATRIX. IE., THE
35REM NUMBER OF VARIABLES. NOW ENTER THE DATA BEGINNING IN LINE
36REM 6000 AS FOLLOWS: FIRST THE DIMENSIONS OF YOUR COMPACTED
37REM CONSTRAINT MATRIX -- N, M. THIS IS FOLLOWED BY THE ELEMENTS
38REM OF YOUR COMPACTED CONSTRAINT MATRIX ENTERED COLUMN BY
39REM COLUMN IN THE FOLLOWING FORMAT. FIRST THE ROW NUMBER THAT
40REM THAT ELEMENT HAD IN THE ORIGINAL CONSTRAINT MATRIX BEFORE
41REM IT WAS CONDENSED (IF THE ELEMENT IS ZERO DUE TO BEING IN A
42REM SHORT COLUMN THIS NUMBER SHOULD BE ZERO), THEN THE VALUE OF
43REM THE ELEMENT. THIS DATA SHOULD BE FOLLOWED BY THE ELEMENTS
44REM OF YOUR RIGHT HAND SIDE (THE B VECTOR) (DO NOT ELIMINATE
45REM ZEROS FROM THIS VECTOR). FINALLY ENTER THE OBJECTIVE
46REM FUNCTION (IE., THE COSTS OF EACH OF THE N VARIABLES). THE
47REM PROGRAM IS DESIGNED TO MAXIMIZE THIS FUNCTION. IF YOU WANT
48REM TO MINIMIZE IT, NEGATE THE OBJECTIVE FUNCTION. IF YOU
49REM SHOULD HAVE PROBLEMS WITH DIMENSIONING, THE FOLLOWING
50REM CHANGES CAN BE MADE. VARIABLES IN LINE 199 HAVE THE
51REM DIMENSION OF YOUR COMPACTED CONSTRAINT MATRIX (M X N).
52REM VARIABLES IN LINE 200 ARE DIMENSIONED TO THE NUMBER OF
53REM CONSTRAINTS IN YOUR PARTICULAR PROBLEM. VARIABLES IN
54REM LINE 201 ARE DIMENSIONED TO THE TOTAL NUMBER OF VARIABLES;
55REM SLACK + SURPLUS + ARTIFICIAL + DECISION VARIABLES.
56REM IN SOME SITUATIONS YOU MAY WANT TO ASSIGN A NON-ZERO COST
57REM TO A SLACK OR SURPLUS VARIABLE. THIS CAN BE ACCOMPLISHED
58REM BY ADDING LINE STATEMENTS BETWEEN LINES 260 AND 280.
59REM THE OBJECTIVE FUNCTION IS CARRIED IN THE SUBSCRIPTED
60REM VARIABLE F(I) WHERE I IS THE NUMBER OF THE VARIABLE.
61REM IF A COST OF 10 IS TO BE ASSIGNED TO A SLACK VARIABLE
62REM WHICH IS THE 15TH VARIABLE IN THE PROBLEM, ADD THE
63REM FOLLOWING LINE STATEMENT. 261LET F(15) = 10.
64REM GOOD LUCK!...........................................
70'
75' THIS PROGRAM WAS WRITTEN FOR STUDENT USE AT AMOS TUCK SCHOOL
76' OF HANOVER, N.H., WHICH DOES NOT ASSUME RESPONSIBILITY FOR
77' ITS ACCURACY.
80'
85' * * * * * * * * * * * MAIN PROGRAM * * * * * * * * * * * * *
90'
99LETY4$="YES"
100PRINT"ENTER THE NUMBER OF CONSTRAINTS, THE NUMBER OF LESS THAN"
101PRINT"CONSTRAINTS, THE NUMBER OF GREATER THAN CONSTRAINTS, AND"
102PRINT"THE NUMBER OF EQUAL TO CONSTRAINTS";
103INPUTM1,M4,M5,M6
104LETM2=M4+M5
105LETM3=M5+M6
106PRINT
199DIMC(15,50),K(15,50)
200DIM Q(50),A(50,50),D(50),O(50),Z(50),P(50),B(50)
201DIMG(200),T(200),F(200)
202READN,M
203FORJ=1TON
204FORI=1TOM
205READK(I,J),C(I,J)
206NEXTI
207NEXTJ
208FORI=1TOM1
209READB(I)
210NEXTI
211FORI=1TON
212READF(I)
213NEXTI
214FORI=N+1TON+M4
215LETG(I)=1
216NEXTI
217FORI=N+M2+1TON+M2+M3
218LETG(I)=1
219NEXTI
220LETN1=1
225FORI=N+1TON+M2+M3
230IFG(I)=0THEN245
235LETO(N1)=I
240LETN1=N1+1
245NEXTI
250FORI=1TOM3
255LETD(I)=N+M2+I
260NEXTI
280FORI=1TOM4
281LETQ(I)=1
282NEXTI
283FORI=M4+1TOM4+M5
284LETQ(I)=-1
285NEXTI
295FORI=N+M2+1TON+M2+M3
300LETF(I)=-10000000
305NEXTI
306FORJ=1TOM1
307LETZ(J)=-F(O(J))
308NEXTJ
310PRINT"DO YOU WANT THE ENTIRE TABLEAU PRINTED AT EACH ITEREATION";
311INPUTY1$
312PRINT
314PRINT"YOUR VARIABLES ARE "1;" TO ";N
315PRINT"SLACK VARIABLES ARE"N+1;" TO "; N+M4
316PRINT"SURPLUS VARIABLES "N+M4+1;" TO ";N+M4+M5
317PRINT"ARTIFICIAL VARIABLES"N+M4+M5+1;" TO ";N+M2+M3
390PRINT
391PRINT
392PRINT
393PRINT
400GOSUB1115
401GOSUB1000
402GOSUB1235
403GOSUB1410
404GOSUB1000
405GOSUB1235
410IFZ6=0THEN403
465FORJ=1TOM1
470IFO(J)<N+M4+M5+1THEN480
475IFZ(J)>0THEN490
480NEXTJ
485GOTO500
490PRINT"THE PROBLEM IS INFEASIBLE"
495STOP
500PRINT
501PRINT
502LETJ9=1
503IFJ9>M1THEN507
504FORI=J9TOM1
505IFO(I)>N+M4+M5THEN2000
506NEXTI
507LETY4$="NO"
508LETY1$="YES"
509PRINT"FINAL TABLEAU"
510PRINT
511PRINT
512GOSUB1390
513GOSUB1000
514STOP
1000IFY1$="NO"THEN1005
1001PRINT"**********************************************************************"
1002PRINT
1003PRINT
1004PRINT"TABLEAU AFTER ITERATION"N7
1005FORJ=1TON+M2+M3
1006IFJ<N+M2+1THEN1010
1007IFY4$="NO"THEN1075
1010IFG(J)=1THEN1070
1015GOSUB1135
1020LETT(J)=-F(J)
1025FORI=1TOM1
1030LETT(J)=T(J)-P(I)*Z(I)
1035NEXTI
1040IFY1$="NO"THEN1075
1050PRINT
1055PRINT
1056PRINT"COLUMN"J
1057MATPRINTP,
1058PRINT
1059PRINT"DUAL VALUE ="T(J)
1060PRINT"--------- --------- --------- --------- ---------"
1061PRINT
1062GOTO1075
1070LETT(J)=0
1075NEXTJ
1080MATZ=A*B
1081IFY1$="NO"THEN1110
1082PRINT"VARIABLE","VALUE"
1083LETC4=0
1084FORJ=1TOM1
1085PRINTO(J),Z(J)
1086LETC4=C4+F(O(J))*Z(J)
1087NEXTJ
1088PRINT
1089PRINT"THE VALUE OF THE OBJECTIVE FUNCTION IS"C4
1090PRINT"**********************************************************************"
1110RETURN
1115FORI=1TOM1
1120LETA(I,I)=1
1125NEXTI
1130RETURN
1135MATP=ZER(M1)
1140IFJ>NTHEN1195
1145FORI=1TOM1
1150FORJ1=1TOM
1155LETJ2=K(J1,J)
1160IFJ2=0THEN1170
1165LETP(I)=P(I)+A(I,J2)*C(J1,J)
1170NEXTJ1
1175IFABS(P(I))>.00001THEN1185
1180LETP(I)=0
1185NEXTI
1190GOTO1230
1195FORI=1TOM1
1200IFJ>N+M2THEN1215
1205LETP(I)=A(I,J-N)*Q(J-N)
1210GOTO1225
1215LETI1=D(J-N-M2)
1220LETP(I)=A(I,I1)
1225NEXTI
1230RETURN
1235LETZ7=0
1240LETI1=T(1)
1245LETN1=1
1250FORJ=2TON+M2+M3
1255IFT(J)>=I1THEN1270
1260LETI1=T(J)
1265LETN1=J
1270NEXTJ
1275IFI1<=-.0001THEN1295
1280IFZ7=1THEN1335
1285LETZ6=1
1290GOTO1405
1295LETJ=N1
1300GOSUB1135
1305FORI=1TOM1
1310IFP(I)>0THEN1340
1315NEXTI
1320LETT(N1)=0
1325LETZ7=1
1330GOTO1240
1335PRINT"THE PROBLEM IS UNBOUNDED AT ITERATION" N7
1336STOP
1340LETI2=Z(I)/P(I)
1345FORI1=I+1TOM1
1350IFP(I1)<=0THEN1370
1355IFI2<=Z(I1)/P(I1)THEN1370
1360LETI2=Z(I1)/P(I1)
1365LETI=I1
1370NEXTI1
1375LETG(N1)=1
1380LETG(O(I))=0
1385LETO(I)=N1
1390FORJ=1TOM1
1395LETZ(J)=-F(O(J))
1400NEXTJ
1405RETURN
1410FORI1=1TOM1
1415LETA(I,I1)=A(I,I1)/P(I)
1420NEXTI1
1425FORJ=1TOM1
1430IFA(I,J)=0THEN1465
1435FORI1=1TOM1
1440IFI1=ITHEN1460
1445LETA(I1,J)=A(I1,J)-P(I1)*A(I,J)
1450IFABS(A(I1,J))>.00001THEN1460
1455LETA(I1,J)=0
1460NEXTI1
1465NEXTJ
1475LETN7=N7+1
1480RETURN
2000LETJ9=I+1
2005FORJ=1TON+M4+M5
2010GOSUB1135
2015IFP(I)<>0THEN2030
2020NEXTJ
2025GOTO503
2030LETG(J)=1
2035LETG(O(I))=0
2040LETO(I)=J
2045GOSUB1410
2050GOTO503
6000DATA 17,7
6010DATA 1,1,12,.08,13,4,20,1,0,0,0,0,0,0
6020DATA 1,1,9,1,10,1,11,1,12,.08,13,-1,20,1
6030DATA 2,1,12,.1,14,1,20,1,0,0,0,0,0,0
6040DATA 2,1,9,1,10,1,11,1,12,-.1,14,-2,20,1
6050DATA 3,1,12,.04,15,1,20,1,0,0,0,0,0,0
6060DATA 3,1,9,1,10,1,11,1,12,.04,15,-1,20,1
6070DATA 4,1,12,.03,16,1,20,1,0,0,0,0,0,0
6080DATA 4,1,9,1,10,1,11,1,12,.03,16,-3,20,1
6090DATA 5,1,12,.09,17,2,20,1,0,0,0,0,0,0
6100DATA 5,1,9,1,10,1,11,1,12,.09,17,-1,20,1
6110DATA 6,1,12,.02,18,1,20,1,0,0,0,0,0,0
6120DATA 6,1,9,1,10,1,11,1,12,.02,18,-4,20,1
6130DATA 7,1,12,-.05,19,3,20,1,0,0,0,0,0,0
6140DATA 7,1,9,1,10,1,11,1,12,-.05,19,-1,20,1
6150DATA 8,1,20,-1,21,1,0,0,0,0,0,0,0,0
6160DATA 8,1,9,-1,11,.25,20,-1,21,1,0,0,0,0
6170DATA 8,1,20,-1,21,-1,0,0,0,0,0,0,0,0
6180DATA 350,225,170,200,150,250,300,800,250
6190DATA 500,350,25,0,0,0,0,0,0,0,0,0
6200DATA .18,.18,.06,.06,.13,.13,.09,.09,.15,.15
6210DATA .07,.07,.08,.08,0,0,0
9999END