10 PRINT "LINEAR PROGRAMMING"
20 PRINT
28 REM - SEE DISCUSSION FOR A DESCRRIPTION OF HOW LINE 30 LIMITS THE
29 REM - NUMBWER OF VARIABLES AND CONSTRAITS
30 DIM A(10,14), B(15)
39 REM - LINES 40 TO 70 INPUT THE SIZE OF THE PROBLEM
40 PRINT "NUMBER OF VARIABLES";
50 INPUT V
60 PRINT "NUMBER OF CONTRAINTS";
70 INPUT C
79 REM - LINES 80 TO 180 INPUT THE CONSTRAINTS
80 PRINT "MATRIX ELEMENTS:"
90 FOR I=2 TO C+1
100 PRINT "CONSTRAINT";I-1
110 FOR J=1 TO V
120 PRINT "  COEFFICIENT";J;
130 INPUT A(I,J)
140 NEXT J
149 REM - FOR A '<' RELATION USE 1; FOR A '>' RELATION USE -1
150 PRINT "  RELATION (1 OR -1)";
160 INPUT A(I,V+1)
170 PRINT "   CONSTANT";
180 INPUT A(I,V+2)
188 REM - INTRODUCE ARTIFICIAL VARIABLES BY MOVING RELATION AND
189 REM - CONSTANTS TO THE END OF THE ROW
190 A(I,C+V+1)=A(I,V+2)
200 A(I,V+2)=0
210 IF I=2 THEN 240
220 A(I,V+I-1)=A(I,V+1)
230 A(I,V+1)=0
240 NEXT I
249 REM - LINES 250 TO 310 INPUT THE OBJECTIVE FUNCTION
250 PRINT
260 PRINT "FUNCTION:"
270 FOR I=1 TO V
280 PRINT "  COEFFICIENT";I;
290 INPUT A(1,I)
300 NEXT I
310 PRINT
320 M=1
330 FOR I=1 TO V
340 B(I)=1
350 NEXT I
358 REM - LINES 360 TO 430 SUM ALL CONSTRAINTS WITH '>' RELATION
359 REM - IN LAST ROW OF A()
360 FOR I=2 TO C+1
370 IF A(I,V+I-1)<>-1 THEN 430
380 B(V+I-1)=1
390 FOR J=1 TO C+V
400 A(C+2,J)=A(C+2,J)-A(I,J)
410 NEXT J
420 M=C+2
430 NEXT I
439 REM - LINES 440 TO 690 FIND THE NEXT PIVOT ELEMENT
440 P=1
450 R=1
460 FOR I=2 TO C+V
470 IF A(M,I)<A(M,P) THEN 490
480 P=I
490 IF A(M,I)>=A(M,R)THEN 510
500 R=I
510 NEXT I
520 IF A(M,R)<0 THEN 570
530 IF M=1 THEN 880
540 IF A(M,P)>.0001 THEN 840
550 M=1
560 GOTO 440
570 P=1
580 FOR I=2 TO C+1
590 IF A(I,R)<=0 THEN 640
600 Z=A(I,C+V+1)/A(I,R)
610 IF P=1 THEN 630
620 IF Z>=A(P,C+V+1)/A(P,R) THEN 640
630 P=I
640 NEXT I
650 IF P=1 THEN 860
660 FOR I=1 TO V+C
670 IF B(I)=1 THEN 690
680 IF A(P,I)=1 THEN 700
690 NEXT I
699 REM - LINES 700 TO 830 PERFORM THE PIVOT OPERATION
700 B(I)=1
710 B(R)=0
720 Z=A(P,R)
730 FOR I=1 TO V+C+1
740 A(P,I)=A(P,I)/Z
750 NEXT I
760 FOR I=1 TO C+2
770 IF I=P THEN 820
780 Z=A(I,R)
790 FOR J=1 TO V+C+1
800 A(I,J)=A(I,J)-Z*A(P,J)
810 NEXT J
820 NEXT I
830 GOTO 440
840 PRINT "INFEASIBLE"
850 GOTO 1030
860 PRINT "UNBOUNDED"
870 GOTO 1030
879 REM - MAKE FINAL CALCULATIONS AND PRINT
880 FOR J=1 TO V
890 IF B(J)=0 THEN 920
900 B(J)=0
910 GOTO 960
920 FOR I=2 TO C+1
930 IF A(I,J)=1 THEN 950
940 NEXT I
950 B(J)=A(I,V+C+1)
960 NEXT J
970 Z=A(1,V+C+1)
980 PRINT
990 PRINT "FUNCTION =";Z*(-1)
1000 FOR I=1 TO V
1010 PRINT "X(";I;")=";B(I)
1020 NEXT I
1030 END
