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