Trailing-Edge
-
PDP-10 Archives
-
decuslib20-01
-
decus/20-0020/linpro.tuk
There are 2 other files named linpro.tuk in the archive. Click here to see a list.
10' NAME--LINPRO
15'
20' DESCRIPTION--LINEAR PROGRAMMING-2 PHASE
25'
30' SOURCE--REVISED 12/23/68 BY D. DOWNES
35'
40' INSTRUCTIONS--INSTRUCTIONS FOR THE USE OF THIS PROGRAM ARE
41' IN THE LIBRARY PROGRAM DESCRB***
45'
50' THIS PROGRAM WAS WRITTEN FOR STUDENT USE AT AMOS TUCK SCHOOL
51' OF HANOVER, N.H., WHICH DOES NOT ASSUME RESPONSIBILITY FOR
52' ITS ACCURACY.
55'
60' * * * * * * * * * * * MAIN PROGRAM * * * * * * * * * * * * * *
65'
80 GO TO 20000
90 LET Q=.01
100 DIM A(50,100)
101 PRINT"IF MAX, THEN TYPE:'1'; IF MIN, TYPE:'-1'";
102 INPUT Z
103 LET Z=-Z
110 PRINT"TYPE: NUMBER OF CONSTRAINTS, VARIABLES";
120 INPUT M,N
140 PRINT"TYPE: LESS THANS, EQUALITIES, GREATER THANS";
150 INPUT L,E,G
160 IF L+E+G=M THEN 190
170 PRINT" INPUT DATA NOT CONSISTENT."
180 STOP
190 LET B=M+N+G+1
200 LET W=M
210 IF B*(W+1) < 5000 THEN 240
220 PRINT" PROBLEM TOO LARGE"
230 STOP
240 IF B>100 THEN 259
250 IF W+1 < 50 THEN 310
259
260 PRINT" CHANGE DIM STATEMENT (100) FOR A"W+1"BY"B"MATRIX"
265 PRINT" THEN DELETE LINES 260,265,270"
270 STOP
280' INITIALIZATION
310 LET M=M-1
320 LET H=1
330 FOR I=0 TO W+1
340 FOR J=1 TO B
350 LET A(I,J)=0
360 NEXT J
370 NEXT I
400' READ DATA
410 FOR I=0 TO M
420 FOR J=1 TO N
430 READ A(I,J)
440 NEXT J
450 NEXT I
460 FOR I=0 TO M
470 READ A(I,B)
480 NEXT I
490 FOR J=1 TO N
500 READ A(W,J)
510 LET A(W,J)=Z*A(W,J)
520 NEXT J
540' SET UP TABLEAU, SLACKS, ETC.
560 FOR K=1 TO M+1
570 LET A(K-1,N+G+K)=1
580 LET A(K-1,0)=K+N+G
590 NEXT K
600 IF G<>0 THEN 620
610 IF E=0 THEN 770
611 GO TO 650
620 FOR K=L+E+1 TO M+1
630 LET A(K-1,K+N-L-E)=-1
640 NEXT K
650 LET W=W+1
660 LET Q=0
670 FOR J=1 TO N+G
680 LET S=0
690 FOR I=M-G-E+1 TO M
700 LET S=S+A(I,J)
710 NEXT I
720 LET A(W,J)=-S
730 IF A(W,J)>Q THEN 760
740 LET Q=A(W,J)
750 LET C=J
760 NEXT J
761 LET S=0
762 FOR J=M-G-E+1 TO M
763 LET S=S+A(J,B)
764 NEXT J
765 LET A(W,B)=-S
770 PRINT
775 PRINT
780 PRINT" YOUR VARIABLES"H"THROUGH"N
790 IF G=0 THEN 810
800 PRINT" SURPLUS VARIABLES"N+1"THROUGH"N+G
810 IF L=0 THEN 830
820 PRINT" SLACK VARIABLES"N+G+1"THROUGH"N+G+L
830 IF G+E=0 THEN 850
840 PRINT" ARTIFICIAL VARIABLES"N+G+L+1"THROUGH"B-1
850
860 GOSUB 2000
870' TRANSFORM MATRIX
880 PRINT
890 PRINT
895 IF Q=.01 THEN 1230
900 IF Q=0 THEN 1330
910 GO TO 1400
920 LET H=H+1
930 LET Q=1E38
940 LET R=-1
950 FOR I=0 TO M
960 IF A(I,C)<=0 THEN 1000
970 IF A(I,B)/A(I,C)>Q THEN 1000
980 LET Q=A(I,B)/A(I,C)
990 LET R=I
1000 NEXT I
1010 IF R>=-.5 THEN 1050
1020 PRINT" SOLUTION UNBOUNDED"
1030 GOSUB 2000
1040 STOP
1050 LET P=A(R,C)
1060 LET A(R,0)=C
1070 FOR J=1 TO B
1080 LET A(R,J)=A(R,J)/P
1090 NEXT J
1100 FOR I=0 TO W
1110 IF I=R THEN 1180
1120 FOR J=1 TO B
1130 IF J=C THEN 1170
1140 LET A(I,J)=A(I,J)-A(R,J)*A(I,C)
1150 IF ABS(A(I,J))>1E-5 THEN 1170
1160 LET A(I,J)=0
1170 NEXT J
1180 NEXT I
1190 FOR I=0 TO W
1200 LET A(I,C)=0
1210 NEXT I
1220 LET A(R,C)=1
1230 LET Q=0
1240 FOR J=1 TO N+G+L
1250 IF A(W,J)>Q THEN 1280
1260 LET Q=A(W,J)
1270 LET C=J
1280 NEXT J
1290 GO TO 900
1300' CHANGE TO PHASE TWO
1330 IF W=M+1 THEN 1360
1340 LET W=W-1
1350 IF A(W+1,B)<1E-6 THEN 1353
1351 PRINT" NO FEASIBLE SOLUTION"
1352 STOP
1353 FOR I=0 TO M
1354 IF A(I,0)<=N+G+L THEN 1358
1355 FOR J=1 TO B
1356 LET A(I,J)=0
1357 NEXT J
1358 NEXT I
1359 GO TO 1230
1360 PRINT"ANSWERS:"
1400 IF Q=0 THEN 1420
1410 PRINT" BASIS BEFORE ITERATION"H
1420 PRINT" VARIABLE","VALUE"
1430 FOR I=0 TO M
1440 IF A(I,0)=0 THEN 1460
1450 PRINT A(I,0),A(I,B)
1460 NEXT I
1470 IF Q<>0 THEN 920
1480 PRINT"DUAL VARIABLES:"
1510 PRINT" COLUMN","VALUE"
1520 FOR J=N+1 TO B-G-1
1530 PRINT J,A(W,J)
1540 NEXT J
1543 PRINT"OBJECTIVE FUNCTION VALUE =";-Z*A(W,B)
1545 PRINT"IN"H-1"ITERATIONS"
1550 GOSUB 2000
1610 GO TO 99999
1620' SUBROUTINE TO PRINT THE ENTIRE TABLEAU
2000 PRINT"TABLEAU AFTER"H-1"ITERATIONS"
2030 FOR I=0 TO W
2040 FOR J=1 TO B
2050 IF B>5 THEN 2080
2060 PRINT A(I,J),
2070 GO TO 2090
2080 PRINT A(I,J);
2090 NEXT J
2100 PRINT
2110 PRINT
2120 NEXT I
2130 RETURN
10000 DATA 4E36
20000 READ G9
30000 IF G9=4E36 THEN 60000
40000 RESTORE
50000 GO TO 90
60000 PRINT" LIST THE FILE 'DESCRB***' FOR INSTRUCTIONS"
99999 END