3 REM GINTLP: LINEAR PROGRAMMING -- VARIABLES RESTRICTED TO VALUES 4 REM OF ONE OR ZERO 8 REM FUNCTION -- SOLVES 0-1 INTEGER LINEAR PROGRAMMING PROBLEMS 9 REM REFERENCE -- 11 REM NONE 15 REM DATA -- COEFFICIENTS FOR PROBLEM (OPTIMAL) 17 REM INPUTS -- COEFFIECIENTS FOR PROGLEM (OPTIMAL) 19 REM FILES -- NONE 21 REM ---------------------------------------------------- 100 DIM A(20,40),B(20),C(40),D(40),S(40),T(40),Y(20),X(40) 170 REM ------------------------------------------------- 190 REM READ THE PROGRAM DATA 200 PRINT 201 PRINT 'NUMBER OF CONSTRAINTS --'; 202 GOSUB 8000 203 M=Z9 205 PRINT'NUMBER OF VARIABLES --'; 206 GOSUB 8000 207 N=Z9 208 PRINT 210 FOR I=1 TO M 212 PRINT'COEFFICIENTS FOR CONSTRAINT ';I 220 FOR J=1 TO N 230 PRINT' VARIABLE ';J;' : '; 231 GOSUB 8000 232 A(I,J)=Z9 240 NEXT J 250 PRINT' RIGHT-HAND SIDE : '; 251 GOSUB 8000 252 B(I)=Z9 253 PRINT 260 Y(I)=-B(I) 270 NEXT I 274 PRINT 275 PRINT'COEFFICIENTS FOR OBJECTIVE FUNTION --' 280 FOR J=1 TO N 290 PRINT ' VARIABLE ';J;' : '; 291 GOSUB 8000 292 C(J)=Z9 300 NEXT J 310 MAT X=ZER(N) 320 MAT S=ZER(N) 330 MAT R=ZER(N) 340 Z9=1.E+38 350 Z=0 360 N1=0 370 REM THIS IS THE END OF THE SET UP PROCEDURE 500 FOR I=1 TO M 510 IF Y(I)>=0 THEN 530 520 GOTO 560 530 NEXT I 540 GOSUB 5000 550 GOTO 500 560 MAT T=ZER(N) 565 T1=0 570 FOR J=1 TO N 580 FOR I=1 TO N1 590 IF ABS(S(I))<>J THEN 610 600 GOTO 690 610 NEXT I 620 IF Z+C(J)>=Z9 THEN 690 630 FOR I=1 TO M 640 IF Y(I)>=0 THEN 680 650 IF A(I,J)<=0 THEN 680 660 T(J)=1 665 T1=1 670 GOTO 690 680 NEXT I 690 NEXT J 700 IF T1<>0 THEN 730 710 GOSUB 6000 720 GOTO 500 730 FOR I=1 TO M 740 IF Y(I)>=0 THEN 840 750 Y1=Y(I) 760 FOR J=1 TO N 770 IF T(J)=0 THEN 800 780 IF A(I,J)<=0 THEN 800 790 Y1=Y1+A(I,J) 800 NEXT J 810 IF Y1>=0 THEN 840 820 GOSUB 6000 830 GOTO 500 840 NEXT I 845 T1=1.E+38 850 FOR J=1 TO N 860 IF T(J)=0 THEN 950 870 Y1=0 880 FOR I=1 TO M 890 IF Y(I)+A(I,J)>=0 THEN 910 900 Y1=Y1+Y(I)+A(I,J) 910 NEXT I 920 IF Y1>=T1 THEN 950 930 T1=Y1 940 J1=J 950 NEXT J 960 N1=N1+1 970 S(N1)=J1 980 Z=Z+C(J1) 990 FOR I=1 TO M 1000 Y(I)=Y(I)+A(I,J1) 1010 NEXT I 1020 GOTO 500 5000 IF Z>=Z9 THEN 5070 5010 Z9=Z 5020 MAT X=ZER(N) 5030 FOR I=1 TO N1 5040 IF S(I)<=0 THEN 5060 5050 X(S(I))=1 5060 NEXT I 5070 GOSUB 6000 5080 RETURN 6000 FOR I=N1 TO 1 STEP -1 6010 IF R(I)=1 THEN 6100 6020 R(I)=1 6030 FOR J=I+1 TO N 6040 R(J)=0 6050 S(J)=0 6060 NEXT J 6070 S(I)=-S(I) 6080 N1=I 6090 GOTO 6130 6100 NEXT I 6110 GOSUB 7000 6120 GOTO 9999 6130 FOR I=1 TO M 6140 Y(I)=-B(I) 6150 FOR I1=1 TO N1 6160 IF S(I1)<=0 THEN 6180 6170 Y(I)=Y(I)+A(I,S(I1)) 6180 NEXT I1 6190 NEXT I 6200 Z=0 6210 FOR I=1 TO N1 6220 IF S(I)<=0 THEN 6240 6230 Z=Z+C(S(I)) 6240 NEXT I 6250 RETURN 7000 PRINT 7010 PRINT 7020 PRINT 7030 IF Z9<1.E+38 THEN 7060 7040 PRINT'THE PROBLEM HAS NO FEASIBLE SOLUTION.' 7050 GOTO 7120 7060 PRINT'ANSWERS:' 7070 PRINT'VARIABLE','VALUE' 7080 FOR J=1 TO N 7090 PRINT J,X(J) 7100 NEXT J 7110 PRINT'MINIMUM VALUE OF THE OBJECTIVE FUNCTION = ';Z9 7115 PRINT 7120 RETURN 8000 REM ---------------------------------------------------- 8005 REM -- SUBROUTINE TO GET NEXT VALE 8020 REM -- INPUT VALUE 8021 INPUT Z9 8022 RETURN 9999 END