10 REM PROGRAMMED BY D. E. RAMIREZ,MATH DEPT,UVA,CHARLOTTESVILLE,VA 20 REM 11/14/73 25 REM HP CONTRIBUTED LIBRARY, 2/75 30 REM INTRODUCTION TO PROGRAM 40 PRINT "THIS PROGRAM SOLVES LINEAR PROGRAMS AND MATRIX GAMES" 50 PRINT "AND FINDS THE BEST UNIFORM SOLUTION FOR LINEAR EQUATIONS" 60 PRINT "TYPE LP OR MG"; 70 PRINT " OR BS"; 80 DIM W$[2] 90 DIM A[20,20] 100 INPUT W$ 110 IF W$="BS" THEN 4270 120 IF W$="MG" THEN 2570 130 REM TITLE FOR LP 140 PRINT "A PROGRAM TO MAXIMIZE OR MINIMIZE A LINEAR FUNCTION" 150 PRINT "SUBJECT TO LINEAR CONSTRAINTS" 160 PRINT "ENTER MAX OR MIN "; 170 DIM Q$[3] 180 INPUT Q$ 190 IF Q$="MAX" THEN 220 200 Q1=-1 210 GOTO 240 220 Q1=1 230 REM PIVOT QUESTION 240 PRINT "DO YOU WANT TO SEE THE PIVOT STEPS (Y OR N)"; 250 INPUT A$ 260 IF W$="MG" THEN 2600 270 REM INPUT FOR LP 280 PRINT "ENTER NUMBER OF VARIABLES, EQUALITIES (=0) "; 290 INPUT M,E1 300 E2=3 310 M=M+1 320 PRINT "ENTER NUMBER OF INEQUALITIES OF THE FORM >=0,<=0"; 330 INPUT G,L 340 A=G+L 350 N=A+E1+1 360 MAT A=ZER[N,M] 370 PRINT "ENTER THE SIMPLEX TABLEAU ROW BY ROW - GREATER THAN'S FIRST," 380 PRINT "LESS THAN'S NEXT, EQUALITIES NEXT, AND THE LINEAR FUNCTION LAST" 390 MAT INPUT A 400 IF Q1=1 THEN 440 410 FOR J=1 TO M 420 A[N,J]=-A[N,J] 430 NEXT J 440 IF G=0 THEN 500 450 FOR I=1 TO G 460 FOR J=1 TO M 470 A[I,J]=-A[I,J] 480 NEXT J 490 NEXT I 491 PRINT "INITIAL TABLEAU (Y OR N)"; 492 INPUT Y$ 493 IF Y$="N" THEN 530 500 PRINT "IN STANDARD FORM (MAX AND NO GREATER THAN'S) TABLEAU IS" 510 PRINT 520 MAT PRINT A 530 MAT G=ZER[N,M] 540 MAT G=A 550 REM SOLUTION RETRIEVAL VECTORS 560 T=0 570 V5=-1 580 Q=N-1 590 MAT C=ZER[M-1] 600 MAT D=ZER[N-1] 610 DIM T[20],S[20],C[20],D[20] 620 MAT T=ZER[M] 630 MAT S=ZER[N] 640 J2=J3=0 650 N1=N-1 660 FOR A1=1 TO M-1 670 T[A1]=A1 680 NEXT A1 690 FOR A1=1 TO N-1 700 S[A1]=-A1 710 NEXT A1 720 IF W$="MG" THEN 2740 730 REM EQUALITIES IN LP 740 IF E1=0 THEN 1350 750 FOR I=1 TO N-1 760 IF A[I,M] <= 0 THEN 810 770 FOR J=1 TO M-1 780 IF A[I,J]<0 THEN 810 790 NEXT J 800 GOTO 930 810 NEXT I 820 REM PIVOT AT MAXIMUM IN ROW 830 X=J=0 840 FOR U=1 TO M-1 850 IF ABS(A[A+E1,U]) <= X THEN 880 860 X=ABS(A[A+E1,U]) 870 J=U 880 NEXT U 890 IF J=0 THEN 920 900 L=A+E1 910 GOTO 990 920 IF A[A+E1,M]=0 THEN 950 930 PRINT "THE PROGRAM IS INFEASIBLE" 940 END 950 E1=E1-1 960 IF E1#0 THEN 830 970 GOTO 1350 980 REM PIVOT STEP AT L,J 990 P=A[L,J] 1000 A[L,J]=1/P 1010 FOR E=1 TO N 1020 IF E=L THEN 1040 1030 A[E,J]=-A[E,J]/P 1040 NEXT E 1050 FOR E=1 TO N 1060 IF E=L THEN 1140 1070 FOR F=1 TO M 1080 IF F=J THEN 1130 1090 Z=ABS(A[E,F]) MAX ABS(A[E,J]) MAX ABS(A[L,F]) 1100 A[E,F]=A[E,F]+A[E,J]*A[L,F] 1110 IF ABS(A[E,F])>.00001*Z THEN 1130 1120 A[E,F]=0 1130 NEXT F 1140 NEXT E 1150 FOR F=1 TO M 1160 IF F=J THEN 1180 1170 A[L,F]=A[L,F]/P 1180 NEXT F 1190 IF E1<1 THEN 1230 1200 FOR U=1 TO N 1210 A[U,J]=0 1220 NEXT U 1230 IF A$="N" THEN 1260 1240 PRINT "PIVOTING AT";L;",";J;"YIELDS" 1250 MAT PRINT A 1260 X1=T[J] 1270 T[J]=S[L] 1280 S[L]=X1 1290 IF E2 <= 2 THEN 2900 1300 IF E1=0 THEN 1330 1310 E1=E1-1 1320 GOTO 740 1330 Q=(L-1) MIN U 1340 REM STAGE 1 1350 IF T=1 THEN 1750 1360 FOR I=1 TO Q 1370 IF A[I,M] <= 0 THEN 1420 1380 FOR V=1 TO M-1 1390 IF A[I,V]<0 THEN 1420 1400 NEXT V 1410 GOTO 930 1420 NEXT I 1430 FOR U=Q TO 1 STEP -1 1440 IF A[U,M] <= 0 THEN 1720 1450 REM PIVOT COLUMN RANDOMLY CHOSEN 1460 Y=0 1470 FOR V=1 TO M-1 1480 IF A[U,V] >= 0 THEN 1500 1490 Y=Y+1 1500 NEXT V 1510 FOR V=1 TO M-1 1520 IF A[U,V] >= 0 THEN 1550 1530 IF RND(0) <= 1/Y THEN 1560 1540 Y=Y-1 1550 NEXT V 1560 J=V 1570 REM PIVOT COLUMN IS J 1580 L=U 1590 X=-A[U,M]/A[U,J] 1600 FOR I=U+1 TO N-1 1610 IF A[I,J] <= 0 THEN 1700 1620 Y=-A[I,M]/A[I,J] 1630 IF Y>X THEN 1700 1640 IF Y=X THEN 1680 1650 X=Y 1660 L=I 1670 GOTO 1700 1680 IF RND(0)<.5 THEN 1700 1690 L=I 1700 NEXT I 1710 GOTO 990 1720 NEXT U 1730 T=1 1740 REM STAGE 2 1750 Y=0 1760 FOR Z=1 TO M-1 1770 IF A[N,Z] <= 0 THEN 1830 1780 Y=1 1790 FOR I=1 TO N-1 1800 IF A[I,Z]>0 THEN 1830 1810 NEXT I 1820 GOTO 2120 1830 NEXT Z 1840 IF Y=0 THEN 2150 1850 X1=-1 1860 FOR Z=1 TO M-1 1870 IF A[N,Z] <= 0 THEN 2100 1880 X=1.E+38 1890 FOR I=1 TO N-1 1900 IF A[I,Z] <= 0 THEN 2000 1910 Y=-A[I,M]/A[I,Z] 1920 IF Y>X THEN 2000 1930 IF Y=X THEN 1980 1940 L1=I 1950 J1=Z 1960 X=Y 1970 GOTO 2000 1980 IF RND(0)<.5 THEN 2000 1990 L1=I 2000 NEXT I 2010 IF X*A[N,Z]0 THEN 2220 2210 D[-T[U]]=-A[N,U] 2220 NEXT U 2230 IF W$="BS" THEN 4540 2240 IF W$="MG" THEN 2300 2250 IF J2=0 THEN 2270 2260 IF A$="N" THEN 3390 2270 PRINT "THE ";Q$;"IMUM OF THE LINEAR FUNCTION IS ";A[N,M]*Q1 2280 PRINT 2290 GOTO 2320 2300 PRINT "THE VALUE OF THE MATRIX GAME IS ";A[N,M] 2310 PRINT 2320 IF W$="LP" THEN 2350 2330 PRINT "THE OPTIMAL STRATEGY FOR THE ROW PLAYER IS" 2340 GOTO 2360 2350 PRINT "THE SOLUTION OCCURS AT" 2360 PRINT "("; 2370 FOR U=1 TO M-2 2380 PRINT C[U];","; 2390 NEXT U 2400 PRINT C[M-1];")" 2410 PRINT 2420 REM DUAL SOLUTION 2430 IF W$="LP" THEN 2460 2440 PRINT "THE OPTIMAL STRATEGY FOR THE COLUMN PLAYER IS" 2450 GOTO 2470 2460 PRINT "THE DUAL SOLUTION OCCURS AT" 2470 PRINT "("; 2480 FOR U=1 TO N-2 2490 PRINT D[U];","; 2500 NEXT U 2510 PRINT D[N-1];")" 2520 IF W$="MG" THEN 2550 2530 IF J3>0 THEN 3840 2540 GOTO 3180 2550 END 2560 REM TITLE FOR MG 2570 PRINT "A PROGRAM TO SOLVE MATRIX GAMES" 2580 GOTO 240 2590 REM INPUT FOR MG 2600 PRINT "ENTER THE NUMBER OF ROWS,COLUMNS"; 2610 INPUT N1,M1 2620 E1=0 2630 E2=0 2640 DIM G[20,20] 2650 MAT G=ZER[N1,M1] 2660 PRINT "ENTER THE MATRIX ROW BY ROW" 2670 MAT INPUT G 2680 PRINT "MATRIX IS" 2690 MAT PRINT G; 2700 N=M1+1 2710 M=N1+1 2720 GOTO 560 2730 REM CONVERSION TO LP 2740 MAT A=ZER[N,M] 2750 FOR U=1 TO N-1 2760 FOR V=1 TO M-1 2770 A[U,V]=-G[V,U] 2780 NEXT V 2790 NEXT U 2800 FOR U=1 TO N-1 2810 A[U,M]=1 2820 NEXT U 2830 FOR U=1 TO M-1 2840 A[N,U]=-1 2850 NEXT U 2860 IF A$="N" THEN 2890 2870 PRINT "INITIAL TABLEAU IS" 2880 MAT PRINT A 2890 U1=-1 2900 U1=U1+1 2910 L=N-1+U1 2920 J=M-U1 2930 E2=E2+1 2940 IF E2=3 THEN 2970 2950 GOTO 990 2960 REM CONVERSION TO SIMPLEX TABLEAU 2970 FOR U=1 TO N 2980 X=A[U,M] 2990 A[U,M]=A[U,M-1] 3000 A[U,M-1]=X 3010 NEXT U 3020 X=T[M] 3030 T[M]=T[M-1] 3040 T[M-1]=X 3050 FOR U=1 TO M 3060 X=A[N,U] 3070 A[N,U]=-A[N-1,U] 3080 A[N-1,U]=X 3090 NEXT U 3100 X=S[N] 3110 S[N]=S[N-1] 3120 S[N-1]=X 3130 IF A$="N" THEN 3160 3140 PRINT "THE SIMPLEX TABLEAU TO BE SOLVED IS" 3150 MAT PRINT A 3160 GOTO 1350 3170 END 3180 REM GOMORY'S METHOD 3190 PRINT 3200 IF J2>0 THEN 3390 3210 PRINT "DO YOU WANT SOLUTIONS TO BE MORE INTEGRAL (Y OR N)"; 3220 INPUT J$ 3230 PRINT 3240 J2=1 3250 IF J$="N" THEN 3380 3260 PRINT "PROGRAM ASSUMES ALL VARIABLES ARE INTEGER VARIABLES AND ADDS" 3270 PRINT "A CUTTING PLANE ON THE VARIABLE WITH THE LARGEST FRACTIONAL PART." 3280 PRINT 3290 FOR I=1 TO N-1 3300 FOR J=1 TO M 3310 IF G[I,J]=INT(G[I,J]) THEN 3350 3320 PRINT "COEFFICIENTS OF THE CONSTRAINTS MUST BE INTEGERS." 3330 PRINT "RE"; 3340 GOTO 370 3350 NEXT J 3360 NEXT I 3370 GOTO 3390 3380 END 3390 Y=-1 3400 FOR I=1 TO M-1 3410 X=C[I] 3420 IF FNF(X)>.01 AND FNF(X)<.99 THEN 3450 3430 NEXT I 3440 GOTO 3810 3450 FOR I=1 TO N-1 3460 IF S[I]>-N1-.5 THEN 3710 3470 MAT G=ZER[N-1,M] 3480 U1=1 3490 FOR U=1 TO N 3500 IF U=I THEN 3560 3510 FOR V=1 TO M 3520 G[U1,V]=A[U,V] 3530 NEXT V 3540 J[U1]=S[U] 3550 U1=U1+1 3560 NEXT U 3570 D1=S[I] 3580 MAT A=ZER[N-1,M] 3590 MAT A=G 3600 MAT S=J 3610 FOR L=1 TO M-1 3620 IF T[L]>D1 THEN 3640 3630 T[L]=T[L]+1 3640 NEXT L 3650 N=N-1 3660 FOR L=1 TO N-1 3670 IF S[L]>D1 THEN 3690 3680 S[L]=S[L]+1 3690 NEXT L 3700 GOTO 3450 3710 NEXT I 3720 FOR I=1 TO N-1 3730 X=-A[I,M] 3740 IF FNF(X)<.00005*ABS(X) THEN 3790 3750 IF FNF(X)>.995 THEN 3790 3760 IF FNF(X)