9000 REM ***** ASGNMT ***** BUSINESS PROGRAM
9005 REM ASGNMT *********** VERSION #1 (7/31/69) ***** ASSIGNMENT PROBLEM
9010 REM REVISED JUNE,1972   ANDY ROTH C.C.G.
9011 INPUT"HAVE YOU ENTERED YOUR DATA";Z$:IF Z$="NO"THEN 9080
9015 PRINT "*  ASSIGNMENT PROBLEM  *"
9020 PRINT
9021 GOTO 9120
9025 PRINT "THIS PROGRAM SOLVES THE CLASSIC ASSIGNMENT PROBLEM, AND DETERMINES"
9030 PRINT"THE COST OF IMPLEMENTING THE SOLUTION."
9035 PRINT
9040 REM THIS PROGRAM USES THE GILMORE ALGORITHM DESCRIBED IN THE
9045 REM COMMUNICATIONS OF THE ACM (NOV. 1960, PP. 605-606) TO SOLVE
9050 REM THE CLASSIC ASSIGNNMENT PROBLEM AND COMPUTE A COST FOR THE
9055 REM ASSIGNMENT.
9060 REM
9080 PRINT" DATA SHOULD BE ENTERED STARTING IN LINE 9900:"
9090 PRINT"    1) FIRST ENTER N, THE NUMBER OF MODULES TO BE ASSIGNED."
9095 PRINT"       (IT IS ASSUMED THAT THERE ARE ALSO N LOCATIONS.)"
9105 PRINT"    2) NEXT ENTER E(I,J), THE 'RATING MATRIX'.  E(I,J) IS"
9110 PRINT"       CONSIDERED TO BE (MODULES, LOCATIONS)."
9111 PRINT "NOW ENTER YOUR DATA":GOTO 9999
9112 REM
9114 DIM E(25,25),R(25),X(25),Y(25),M(25),L(25),F(25),G(25)
9115 REM INITIALIZE
9120 READ N
9125 FOR I=1 TO N
9130 FOR J=1 TO N
9135 READ E(I,J)
9140 NEXT J
9145 NEXT I
9150 T=0
9155 FOR I=1 TO N
9160 X1=E(I,1)
9165 FOR J=2 TO N
9170 IF E(I,J) >= X1 THEN 9180
9175 X1=E(I,J)
9180 NEXT J
9185 FOR J=1 TO N
9190 E(I,J)=E(I,J)-X1
9195 NEXT J
9200 T=T+X1
9205 NEXT I
9210 FOR J=1 TO N
9215 X1=E(1,J)
9220 FOR I=2 TO N
9225 IF E(I,J)>= X1 THEN 9235
9230 X1=E(I,J)
9235 NEXT I
9240 FOR I=1 TO N
9245 E(I,J)=E(I,J)-X1
9250 NEXT I
9255 T=T+X1
9260 NEXT J
9265 FOR I=1 TON
9270 X(I),Y(I)=0
9275 NEXT I
9280 FOR I=1 TO N
9285 FOR J=1 TO N
9290 IF E(I,J) <> 0 THEN 9315
9295 IF X(I) <> 0 THEN 9315
9300 IF Y(J) <> 0 THEN 9315
9304 X(I)=J
9310 Y(J)=I
9315 NEXT J
9320 NEXT I
9325 REM SILVER START  START LABELING
9330 F1=N
9335 R1,C1=0
9340 R2=1
9345 FOR I=1 TO N
9350 M(I),L(I)=0
9355 IF X(I) <> 0 THEN 9380
9360 R1=R1+1
9365 R(R1)=I
9370 M(I)=-1
9375 F1=F1-1
9380 NEXT I
9385 IF F1=N THEN 9735
9390 REM LABEL   LABEL AND SCAN
9395 I=R(R2)
9400 R2=R2+1
9405 FOR J=1 TO N
9410 IF E(I,J) <> 0 THEN 9455
9415 IF L(J)<> 0 THEN 9455
9420 L(J)=I
9425 C1=C1+1
9430 F(C1)=J
9435 IF Y(J)=0 THEN 9690
9440 R1=R1+1
9445 R(R1)=Y(J)
9450 M(Y(J))=I
9455 NEXT J
9460 IF R2 <= R1 THEN 9390
9465 REM RENORMALIZE
9470 S1=1
9475 C0=C1
9480 C2=0
9485 FOR J=1 TO N
9490 IF L(J) <> 0 THEN 9505
9495 C2=C2+1
9500 G(C2)=J
9505 NEXT J
9510 X1=E(R(1),G(1))
9515 FOR K=1 TO R1
9520 FOR L1=1 TO C2
9525 IF E(R(K),G(L1))>X1 THEN 9535
9530 X1=E(R(K),G(L1))
9535 NEXT L1
9540 NEXT K
9545 T=T+(R1+C2-N)*X1
9550 FOR I=1 TO N
9555 IF M(I) <> 0 THEN 9580
9560 FOR L1=1 TO C0
9565 E(I,F(L1))=E(I,F(L1))-X1
9570 NEXT L1
9575 GOTO 9655
9580 FOR L1=1 TO C2
9585 E(I,G(L1))=E(I,G(L1))-X1
9590 ON S1 GOTO 9595,9650,9665,9690
9595 IF E(I,G(L1)) <> 0 THEN 9650
9600 IF L(G(L1)) <> 0 THEN 9650
9605 L(G(L1))=I
9610 IF Y(G(L1)) <> 0 THEN 9630
9615 J=G(L1)
9620 S1=2
9625 GOTO 9650
9630 C1=C1+1
9635 F(C1)=G(L1)
9640 R1=R1+1
9645 R(R1)=Y(G(L1))
9650 NEXT L1
9655 NEXT I
9660 ON S1+2 GOTO 9595,9650,9665,9690
9665 IF C0=C1 THEN 9390
9670 FOR I=C0+1 TO C1
9675 M(Y(F(I)))=F(I)
9680 NEXT I
9685 GOTO 9390
9690 REM MARK  MARK NEW COLUMN AND PERMUTE
9695 Y(J),I=L(J)
9700 IF X(I) <> 0 THEN 9715
9705 X(I)=J
9710 GOTO 9330
9715 K=J
9720 J=X(I)
9725 X(I)=K
9730 GOTO 9695
9735 REM  CONTINUE
9740 FOR I=1 TO N
9745 FOR J=1 TO N
9750 E(I,J)=0
9755 NEXT J
9760 NEXT I
9765 FOR K=1 TO N
9770 E(Y(K),X(Y(K)))=1
9775 NEXT K
9780 PRINT "*********************************************************************"
9785 PRINT
9790 PRINT "                         THE ASSIGNMENT IS:"
9795 PRINT
9800 PRINT "MODULE/LOCATION"
9805 PRINT TAB(10);
9810 FOR I=1 TO N-1
9815 PRINT I;
9820 NEXT I
9821 PRINT N
9823 PRINT TAB(8);
9824 FOR I=1 TO N
9825 PRINT "......";
9826 NEXT I
9830 PRINT TAB(8);":"
9835 FOR I=1 TO N
9840 PRINT I;TAB(8);":";TAB(10);
9845 FOR J=1 TO N
9850 PRINT E(I,J);
9855 NEXT J
9860 PRINT
9865 NEXT I
9870 PRINT
9875 PRINT "THE COST OF THIS ASSIGNMENT IS $";T
9880 PRINT
9885 PRINT "*********************************************************************"
9900 DATA 9
9901 DATA 100,90,80,70,60,50,40,30,20
9902 DATA 1,2,3,4,5,6,7,8,9
9903 DATA 10,30,20,40,60,50,80,70,90
9904 DATA 70,69,56,98,56,34,56,12,13
9905 DATA 12,23,34,45,56,6,78,89,90
9906 DATA 12,45,78,98,65,43,32,87,1
9907 DATA 1,2,3,4,5,6,8,9,7
9908 DATA 9,8,7,6,5,4,3,2,1
9909 DATA 100,20,40,69,80,97,5,34,23
9999 END