9000 REM ***** LINPRO ***** BUSINESS PROGRAM
9001 REM LINPRO *********** VERSION #1 (7/31/69) *** LINEAR PROGRAMING
9003 PRINT "* LINEAR PROGRAMMING *"
9108 Q=.01
9112 DIM A(10,20)
9113 I=30
9114 J=50
9115 PRINT
9116 PRINT "IF MAX, TYPE '1'; IF MIN, TYPE '-1'";
9120 INPUT  Z
9123 PRINT
9124 Z=-Z
9128 PRINT "TYPE: NUMBER OF CONSTRAINTS, NUMBER OF VARIABLES";
9132 INPUT M,N
9136 PRINT "TYPE: NO. OF LESS THANS, NO. OF EQUALITIES, NO. OF GREATER THANS";
9140 INPUT L,E,G
9144 IF L+E+G=M THEN 9156
9148 PRINT "INPUT DATA NOT CONSISTENT."
9152 STOP
9156 B=M+N+G+1
9160 W=M+1
9164 IF B*W<1500 THEN 9176
9168 PRINT "PROBLEM TOO LARGE"
9172 STOP
9176 IF B>J THEN 9184
9180 IF W<I THEN 9204
9184 PRINT
9186 R=W+1
9187 C=B+1
9188 PRINT "CHANGE DIM-STATEMENT (9112) TO A "R"BY"C"MATRIX."
9192 PRINT "CHANGE 9113 TO 'LET I=";R;"' AND 9114 TO 'LET J=";B;"'."
9193 PRINT "THEN DELETE LINES 9188,9192,9193, AND 9196."
9196 STOP
9200 REM INITIALIZATION
9204 B=B+1
9208 H=1
9212 FOR I=1 TO W+1
9216 FOR J=2 TO B
9220 A(I,J)=0
9224 NEXT J
9228 NEXT I
9232 FOR I=1 TO M
9234 FOR J=2 TO N+1
9240 READ A(I,J)
9244 NEXT J
9248 NEXT I
9252 FOR I=1 TO M
9256 READ A(I,B)
9260 NEXT I
9264 FOR J=2 TON+1
9269 READ A(W,J)
9272 A(W,J)=Z*A(W,J)
9276 NEXT J
9280 REM SET UP TABLEAU, SLACKS, ETC
9284 FOR K=2 TO M+1
9288 A(K-1,N+G+K)=1
9292 A(K-1,1)=K+N+G-1
9296 NEXT K
9300 IF G <> 0 THEN 9312
9304 IF E=0 THEN 9392
9308 GOTO 9324
9312 FOR K=L+E+2 TO M+1
9316 A(K-1,K+N-L-E)=-1
9320 NEXT K
9324 W=W+1
9328 Q=0
9332 FOR J=2 TO N+G+1
9336 S=0
9340 FOR I=M-G-E+1 TO M
9344 S=S+A(I,J)
9348 NEXT I
9352 A(W,J)=-S
9356 IF A(W,J)>Q THEN 9368
9360 Q=A(W,J)
9364 C=J
9368 NEXT J
9372 S=0
9376 FOR J=M-G-E+1 TO M
9380 S=S+A(J,B)
9384 NEXT J
9388 A(W,B)=-S
9392 PRINT
9396 PRINT "*******************************************************************"
9400 PRINT
9404 PRINT "     YOUR VARIABLES"H"THROUGH"N
9408 IF G=0 THEN 9416
9412 PRINT "     SURPLUS VARIABLES"N+1"THROUGH"N+G
9416 IF L=0 THEN 9424
9420 PRINT"      SLACK VARIABLES"N+G+1"THROUGH"N+G+L
9424 IF G+E=0 THEN 9432
9428 PRINT"      ARTIFICIAL VARIABLES"N+G+L+1"THROUGH"B-2
9436 GOSUB 9744
9440 REM TRANSFORM MATRIX
9444 PRINT
9448 PRINT
9452 IF Q=.01 THEN 9588
9456 IF Q=0 THEN 9620
9460 GOTO 9672
9464 H=H+1
9468 Q=1.E+38
9472 R=0
9476 FOR I=1 TO M
9480 IF A(I,C) <= 0 THEN 9496
9484 IF A(I,B)/A(I,C)>Q THEN 9496
9488 Q=A(I,B)/A(I,C)
9492 R=I
9496 NEXT I
9500 IF R >= .5 THEN 9516
9504 PRINT " SOLUTION UNBOUNDED"
9508 GOSUB 9744
9512 STOP
9516 P=A(R,C)
9520 A(R,1)=C-1
9524 FOR J=2 TO B
9528 A(R,J)=A(R,J)/P
9532 NEXT J
9536 FOR I=1 TO W
9540 IF I=R THEN 9568
9544 FOR J=2 TO B
9548 IF J=C THEN 9564
9552 A(I,J)=A(I,J)-A(R,J)*A(I,C)
9556 IF ABS(A(I,J))>.00001 THEN 9564
9560 A(I,J)=0
9564 NEXT J
9568 NEXT I
9572 FOR I=1 TO W
9576 A(I,C)=0
9580 NEXT I
9584 A(R,C)=1
9588 Q=0
9592 FOR J=2 TO N+G+L+1
9596 IF A(W,J)>Q THEN 9608
9600 Q=A(W,J)
9604 C=J
9608 NEXT J
9612 GOTO 9456
9616 REM CHANGE TO PHASE TWO
9620 IF W=M+1 THEN 9668
9624 W=W-1
9628 IF A(W+1,B)<.000001 THEN 9640
9632 PRINT " NO FEASIBLE SOLUTION"
9636 STOP
9640 FOR I=1 TO M
9644 IF A(I,1) <= N+G+L THEN 9660
9648 FOR J=2 TO B
9652 A(I,J)=0
9656 NEXT J
9660 NEXT I
9664 GOTO 9588
9668 PRINT "ANSWERS:"
9672 IF Q=0 THEN 9680
9676 PRINT " BASIS BEFORE ITERTION"H
9680 PRINT " VARIABLE","VALUE"
9684 FOR I=1 TO M
9688 IF A(I,1)=0 THEN 9696
9692 PRINT A(I,1),A(I,B)
9696 NEXT I
9700 IF Q <> 0THEN 9464
9704PRINT "DUAL VARIABLES:"
9708 PRINT " COLUMN","VALUE"
9712 FOR J=N+1 TO B-G-2
9712 FOR J=N+1 TO B-G-2
9716 PRINT J,A(W,J+1)
9720 NEXT J
9724 PRINT "OBJECTIVE FUNCTION VALUE =";-Z*A(W,B)
9728 PRINT "IN"H-1"ITERATIONS"
9732 GOSUB 9744
9736 GOTO 9999
9740 REM SUBROUTINE TO PRINT THE ENTIRE TABLEAU
9744 PRINT "TABLEAU AFTER"H-1"ITERATIONS"
9748 FOR I=1 TO W
9752 FOR J=2 TO B
9756 IF B>6 THEN 9768
9760 PRINT A(I,J);
9764 GOTO 9772
9768 PRINT A(I,J);
9772 NEXT J
9776 PRINT
9780 PRINT
9784 NEXT I
9788 RETURN
9900 DATA 1,2,3,4
9901 DATA 2,3,4,5
9902 DATA 3,4,5,6
9903 DATA 4,5,6,7
9904 DATA 5,6,7,8
9905 DATA 1,1,1,1
9999 END