Linear Optimization By Simplex Method

Source Code

    1 REM "LIN OPT SI"
    2 REM LINEAR OPTIMIZATION BY SIMPLEX METHOD
    4 PRINT " VARIABLES:": PRINT 
    5 PRINT "M    TOTAL NO OF CONSTRAINTS"
    6 PRINT "MN   NUMBER OF DECISION VAR-line     2100"
    7 PRINT "N    TOTAL NO OF VAR"
    8 PRINT "NB   NO OF >= CONSTRAINTS-line       2100"
    9 PRINT "NE   NO OF = CONSTRAINTS-line        2100"
   10 PRINT "NS   NO OF <= CONSTRAINTS-line       2100"
   11 PRINT "      OB ECONOMIC FUNCTION"
   12 PRINT "X(I)  VECTOR IDENTIFYING VAR"
   13 PRINT "Z(I)  COEFF OF MARG PROFITS"
   14 PRINT "A(I,J) MATRIX OF TECH COEFF"
   15 PRINT "B(I)  VECTOR OFVAL OF RT HND-line     2120"
   16 REM       SIDE OF CONSTR
   17 PRINT "C(I)  COEFF OF OBJ FUNCT-line         2110"
   18 PAUSE 340: CLS : PRINT 
   19 PRINT "LINEAR PROGRAMMING"
   40 PRINT "--------------": PRINT : PRINT : PRINT 
   50 PRINT "ECONOMIC FUNCTION: "
   60 INPUT "MAXIMIZE OR MINIMIZE (MAX/MIN)? ";C$
   70 IF C$<>"MAX" AND C$<>"MIN" THEN GO TO 60
   80 IF C$="MI" THEN LET PT= -1: GO TO 100
   90 LET PT=1
   95 READ MN,NS,NB,NE
  100 PRINT "NO OF DECISION VAR? ";MN
  110 PRINT : PRINT 
  120 PRINT "NO OF CONSTRAINTS"
  130 PRINT "(EXCLUDING NONNEG CONSTRAINTS):"
  140 PRINT "LESS THAN OR EQUAL TO?    ";NS
  150 PRINT "GREATER THAN OR EQUAL TO? ";NB
  160 PRINT "EQUAL?                      ";NE
  170 LET M=NS+NB+NE: REM M=TOTAL CONSTRAINTS
  180 LET N=M+MN+NB: REM N=TOTAL VARIABLES
  190 DIM B(M): DIM C(N): DIM D(N): DIM Z(N): DIM E(N): DIM X(N): DIM F(N): DIM A(M,N)
  200 REM 
  210 REM  IDENTIFICATION OF DEC VAR
  220 REM  SLACK VAR, AND ARTIFIC VAR
  230 PRINT : PRINT 
  240 PRINT "DEFINITION OF VAR INDICES:": PRINT 
  250 LET K=1: FOR J=M+1 TO M+MN
  260 PRINT "DECISION VARIABLE ";K;
  270 LET X(J)=K
  280 PRINT " = X(";X(J);")"
  290 LET K=K+1: NEXT J: PRINT 
  300 IF NS<=0 THEN GO TO 390
  310 PRINT "SLACK VAR(S) OF "
  320 PRINT "LESS-THAN-OR-EQUAL-TO CONSTRAINTS:"
  330 LET K=MN+1: FOR J=1 TO NS
  340 PRINT "CONSTRAINT ";J;
  350 LET X(J)=K
  360 PRINT " =X(";X(J);")"
  370 LET K=K+1: NEXT J: PRINT 
  380 FOR I=1 TO N: LET C(I)=0: NEXT I
  390 IF NB=0 THEN GO TO 470
  400 PRINT "SLACK VAR(S) OF"
  405 REM 2ND PAGE
  410 PRINT "GREATER-THAN-OR-EQUAL-TO CONTRAINTS"
  415 PRINT "(SURPLUS VARIABLES):"
  420 LET K=M+MN+1: FOR J=M+MN+1 TO N
  430 PRINT "CONSTRAINT ";J+NS-M-MN;
  440 LET X(J)=K
  450 PRINT " = X(";X(J);")"
  460 LET K=K+1: NEXT J: PRINT 
  470 IF NB=0 AND NE=0 THEN GO TO 560
  480 PRINT "ARTIFICIAL VARIABLES FOR THE"
  490 PRINT "GREATER-THAN-OR-EQUAL-TO AND"
  495 PRINT "EQUALITY CONSTRAINTS:"
  500 LET K=MN+NS+1: FOR J=NS+1 TO M
  510 PRINT "CONSTRAINT ";J;
  520 LET X(J)=K
  530 PRINT " = X(";X(J);")"
  540 LET C(J)=10000
  550 LET K=K+1: NEXT J: PRINT 
  560 FOR I=1 TO M: LET F(I)=X(I): NEXT I
  570 PRINT "COEFFICICIENTS OF THE OBJECT FUNCTION:"
  580 FOR I=M+1 TO M+MN
  600 READ C(I)
  605 PRINT "COEFF OF DECISION VARIABLE ";C(I)
  610 LET C(I)=C(I)*PT*( -1)
  620 NEXT I: PRINT 
  630 FOR I=1 TO M
  640 PRINT "VALUE OF THE RIGHT SIDE"
  642 READ B(I)
  645 PRINT "  OF CONSTRAINT ";I;"      ?";B(I)
  655 NEXT I
  660 REM   CONSTRUCT THE UNIT MATRIX
  670 FOR I=1 TO M: FOR J=1 TO N
  680 IF I<>J THEN GO TO 710
  690 LET A(I,J)=1
  700 GO TO 720
  710 LET A(I,J)=0
  720 NEXT J: NEXT I
  730 PRINT 
  740 PRINT "CONSTRAINT COEFFICIENTS:"
  750 FOR I=1 TO M
  760 PRINT "COEFFICIENT OF CONSTRAINT #";I
  770 FOR J=M+1 TO M+MN
  772 READ A(I,J)
  780 PRINT "--DECISION VARIABLE ";(J - M);"  ";A(I,J)
  800 NEXT J: NEXT I
  810 IF NB=0 THEN GO TO 870
  820 REM  INTRO THE COEFF OF SURPLUS VAR
  830 FOR I=1 TO NB
  840 LET A(NS+I,M+MN+I)= -1
  850 NEXT I
  860 REM  SIMPLEX ALGORITHIM
  870 FOR I=1 TO M: FOR J=1 TO N
  880 IF F(I)<>X(J) THEN GO TO 900
  890 LET D(I)=C(J)
  900 NEXT J: NEXT I
  910 LET IT=0
  920 FOR J=1 TO N
  930 LET Z(J)=0
  940 FOR I=1 TO M
  950 LET Z(J)=Z(J)+D(I)*A(I,J)
  960 NEXT I
  970 LET E(J)=Z(J)-C(J)
  980 NEXT J
  990 LET OB=0
 1000 FOR I=1 TO M
 1010 LET OB=OB+D(I)*B(I)
 1020 NEXT I
 1030 PRINT : PRINT 
 1040 PRINT "ITERATION #";IT
 1050 PRINT "------------"
 1060 PRINT "BASIC VARIABLES       VALUE"
 1070 FOR I=1 TO M
 1080 PRINT TAB ( 6);"X(";F(I);")";TAB ( 22);B(I): NEXT I
 1090 PRINT : LET N1=1: LET N2=8
 1100 IF N2<>N THEN GO TO 1120
 1110 LET N2=N
 1120 PRINT "VARIABLES OF THE SIMPLEX TABLEAU"
 1130 FOR I=N1 TO N2
 1140 PRINT "X(";X(I);"),";
 1145 NEXT I
 1150 PRINT : PRINT 
 1160 PRINT "MATRIX OF COEFFICIENTS A(I,J):"
 1170 FOR I=1 TO M: LET K=0: FOR J=N1 TO N2
 1180 PRINT TAB ( 4*K+1);INT (100*A(I,J)+.5)/100;: LET K=K+1
 1190 NEXT J: PRINT : NEXT I: PRINT 
 1200 PRINT "MARGINAL PROFIT COEFF Z(J)-C(J);"
 1210 LET K=0: FOR I=N1 TO N2
 1220 PRINT INT (100*E(I)+.5)/100;" ";
 1230 NEXT I: PRINT 
 1240 IF N2>=N THEN GO TO 1270
 1250 LET N1=N1+8: LET N2=N2+8
 1260 GO TO 1100
 1270 PRINT : PRINT "ECONOMIC FUNCTION Z= ";OB: PRINT 
 1280 PRINT : INPUT "CONTINUE? ";C$
 1290 LET IT=IT+1: LET CM=E(1): LET JM=1
 1300 FOR J=2 TO N
 1310 IF E(J)<=CM THEN GO TO 1330
 1320 LET CM=E(J): LET JM=J
 1330 NEXT J
 1340 IF CM>0 THEN GO TO 1740
 1350 LET M3=M+MN: LET MO=M+1
 1360 IF M=NS THEN GO TO 1420
 1370 FOR I=1 TO M
 1380 LET M4=NS+1
 1390 FOR J=M4 TO M
 1400 IF F(I)=X(J) THEN GO TO 1720
 1410 NEXT J: NEXT I
 1420 FOR K=MO TO M3
 1430 FOR I=1 TO M
 1440 IF X(K)=X(I) THEN GO TO 1470
 1450 NEXT I
 1460 IF E(K)=0 THEN GO TO 1490
 1470 NEXT K
 1480 GO TO 1500
 1490 PRINT "***SEVERAL OPT SOLN POSSIBLE***"
 1500 PRINT : PRINT : PRINT 
 1510 PRINT "***OPTIMAL SOLUTION FOUND***"
 1520 PRINT "***AFTER ";IT;" ITERATIONS   ***"
 1530 FOR I=1 TO M
 1540 IF B(I)<>0 THEN GO TO 1570
 1550 PRINT : PRINT " *** DEGENERATE SOLUTION ***"
 1560 GO TO 1580
 1570 NEXT I
 1580 PRINT 
 1590 PRINT "-------------------------------"
 1600 PRINT " DECISION VARIABLE    VALUE"
 1620 FOR I=1 TO M
 1630 PRINT TAB ( 8);"X(";X(I);")";TAB ( 16);"=";TAB ( 25);B(I)
 1640 NEXT I
 1650 PRINT "NOTE: ": PRINT "ALL VARIABLES NOT SHOWN "
 1660 PRINT "IN THIS TABLE HAVE VALUES OF ZERO"
 1680 IF PT=1 THEN PRINT TAB ( 5);"MAXIMUM    Z = ";ABS (OB)
 1690 IF PT=-1 THEN PRINT TAB ( 5);"MINIMUN    Z = ";ABS (OB)
 1700 PRINT "-------------------------------"
 1710 STOP 
 1740 LET XM=1.0E25: LET IM=0
 1750 FOR I=1 TO M
 1760 IF A(I,JM)<=0 THEN GO TO 1800
 1770 LET XX=B(I)/A(I,JM)
 1780 IF XX>=XM THEN GO TO 1800
 1790 LET XM=XX: LET IM=I
 1800 NEXT I
 1810 IF IM>0 THEN GO TO 1840
 1820 PRINT " *** SOLUTION IMPOSSIBLE ***"
 1830 STOP 
 1840 LET XX=A(IM,JM)
 1850 LET B(IM)=B(IM)/XX
 1860 FOR J=1 TO N
 1870 LET A(IM,J)=A(IM,J)/XX
 1880 NEXT J
 1890 FOR I=1 TO M
 1900 IF I=IM THEN GO TO 1960
 1910 LET XX=A(I,JM)
 1920 LET B(I)=B(I)-XX*B(IM)
 1930 FOR J=1 TO N
 1940 LET A(I,J)=A(I,J)-XX*A(IM,J)
 1950 NEXT J
 1960 NEXT I
 1970 LET D(IM)=C(JM)
 1980 LET F(IM)=X(JM)
 1990 GO TO 920
 2100 DATA 3,3,1,0
 2110 DATA 250,190,175,7,80,70,20
 2120 DATA 1,0,0,0,1.5,1,2,1,.5,0,1,0