This program implements the Simplex Method for linear programming optimization, capable of handling both maximization and minimization problems with less-than-or-equal-to, greater-than-or-equal-to, and equality constraints. It uses a Big-M method (with M=10000 as the penalty coefficient) to handle artificial variables for ≥ and = constraints. The tableau is stored in a two-dimensional array A(M,N) alongside vectors B, C, D, E, F, X, and Z, with the problem parameters supplied via READ/DATA statements at lines 2100–2120. The program prints the full simplex tableau at each iteration, detects degeneracy, multiple optimal solutions, and infeasibility, and displays the final basis variable values upon convergence.
Program Analysis
Program Structure
The program is organized into several logical phases, executed sequentially from line 1 onward:
- Lines 1–18: Documentation display — prints a variable glossary with a
PAUSE 340before clearing. - Lines 19–95: Problem setup — reads optimization direction and problem dimensions from
DATA. - Lines 100–190: Echoes problem dimensions and allocates all arrays.
- Lines 210–560: Variable identification — assigns indices to decision variables, slack variables, surplus variables, and artificial variables, printing a mapping table.
- Lines 570–860: Data entry — reads objective function coefficients, right-hand-side values, and constraint matrix coefficients from
DATA; constructs the initial identity sub-matrix and sets surplus variable coefficients to −1. - Lines 860–990: Initializes the simplex iteration: computes
D(I)(objective coefficients of basic variables),Z(J),E(J)=Z(J)−C(J), andOB. - Lines 1030–1280: Tableau display — prints the current basis, the A matrix in pages of 8 columns, and the Z−C row at each iteration.
- Lines 1290–1340: Pivot column selection — finds the most positive
E(J). - Lines 1340–1710: Optimality and special-case checks — detects optimality, multiple optimal solutions, and degeneracy; prints the final solution.
- Lines 1740–1990: Pivot row selection and basis update — minimum-ratio test, row operations, and basis bookkeeping; loops back to line 920.
- Lines 2100–2120: Embedded
DATA— a 3-constraint, 3-decision-variable example problem.
Array Allocation
| Array | Size | Purpose |
|---|---|---|
B(M) | M | Right-hand-side values |
C(N) | N | Objective function coefficients (negated for maximization) |
D(N) | N | Objective coefficients of current basic variables |
Z(N) | N | Reduced cost numerator Z(J) |
E(N) | N | Z(J)−C(J) reduced costs |
X(N) | N | Variable index map (original numbering) |
F(M) | M | Current basis variable indices |
A(M,N) | M×N | Simplex tableau constraint matrix |
The Sample Problem (DATA Lines)
Line 2100 supplies MN=3, NS=3, NB=1, NE=0: three decision variables, three ≤ constraints, one ≥ constraint, and no equality constraints, giving M=7 total constraints and N=11 total variables. Line 2110 provides objective function coefficients (250, 190, 175) followed by RHS values (7, 80, 70, 20). Line 2120 provides the 4×3 constraint matrix.
Key BASIC Idioms and Techniques
- Maximize/minimize switch:
PT=1for MAX,PT=-1for MIN; objective coefficients are stored asC(I) = C(I)*PT*(-1), converting both cases to an internal minimization problem. - Big-M penalty: Artificial variables receive
C(J)=10000(line 540), a fixed large-M value rather than a symbolic infinity. This penalizes any basis containing artificial variables and drives them out during optimization. - Identity matrix seeding: Lines 670–720 construct a unit sub-matrix for the initial basis (covering slack and artificial variables) using an
IF I<>Jbranch rather than two nestedFORloops. - Tableau paging: Lines 1090–1260 page through the N columns in blocks of 8 (
N1toN2) for display, since the full tableau may be too wide to show at once. - Rounding for display:
INT(100*A(I,J)+0.5)/100rounds printed values to two decimal places without a dedicated rounding function. - Multiple optimal solution detection: Lines 1420–1490 scan non-basic decision variables; if any has a zero reduced cost (
E(K)=0) it flags multiple optima. - Degeneracy detection: Line 1540 checks whether any basic variable has a zero value in the optimal solution and prints a degenerate solution warning.
- Infeasibility detection: Lines 1810–1830 check whether the minimum-ratio test finds no valid pivot row (
IM=0), indicating an unbounded or infeasible problem.
Notable Anomalies and Bugs
- Line 70/80 logic error: Line 70 correctly checks for neither “MAX” nor “MIN”, but line 80 tests
C$="MI"(two characters) instead ofC$="MIN". This means “MIN” will never match line 80, soPTwill always be set to 1 (maximize), making minimization inoperative. - Line 95 placed after line 90:
READ MN,NS,NB,NEappears at line 95 but is only reached ifC$<>"MIN"(the MAX branch falls through from line 90). If the MIN branch is taken viaGO TO 100, the READ is bypassed and the variables remain undefined. - Array sizing with N=M+MN+NB: The formula correctly accounts for decision variables, slack variables (NS embedded in M), surplus variables (NB), and artificial variables (NB+NE embedded in M), though the relationship is non-obvious.
- Line 1100 condition: The check
IF N2<>N THEN GO TO 1120is intended to capN2atNwhen the last page is shorter than 8 columns, but the assignmentLET N2=Non line 1110 is only reached whenN2=N, meaning it has no effect. The cap should instead testIF N2>N. - Line 1690 typo: “MINIMUN” is printed instead of “MINIMUM”.
- Hardcoded pivot direction: The simplex selects the entering variable as the most positive reduced cost (line 1310–1320), which is the standard maximization pivot rule applied to the internally negated objective — correct but worth noting.
Content
Image Gallery
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,0Note: Type-in program listings on this website use ZMAKEBAS notation for graphics characters.