'********************************************************* '* SIMPLEX METHOD * '* -------------- * '* * '* LIST OF MAIN VARIABLES: * '* * '* R1\$: MAXIMIZE = Y, MINIMIZE = N * '* NV: NUMBER OF VARIABLES OF ECONOMIC FUNCTION * '* (TO MAXIMIZE OR MINIMIZE). * '* NC: NUMBER OF CONSTRAINTS * '* TS: SIMPLEX TABLE OF SIZE NC+1 x NV+1 * '* R1: =1 TO MAXIMIZE, =-1 TO MINIMIZE * '* R2: AUXILIARY VARIABLE FOR INPUTS * '* NOPTIMAL BOOLEAN IF FALSE, CONTINUE ITERATIONS * '* XMAX: STORES GREATER COEFFICIENT OF ECONOMIC * '* FUNCTION. * '* RAP STORES SMALLEST RATIO > 0 * '* V: AUXILIARY VARIABLE * '* P1,P2: LINE, COLUMN INDEX OF PIVOT * '* XERR: BOOLEAN IF TRUE, NO SOLUTION. * '* ----------------------------------------------------- * '* PROBLEM DESCRIPTION: * '* A builder of houses can make 3 kinds of them with * '* various profits: 15000\$, 17000\$ and 20000\$. * '* Each kind must respect following conditions: * '* 1) for supply reasons, the number of houses of kind 2 * '* built each month must not exceed the number of * '* kind 3 by more than two. * '* 2) for staff reasons, the buider can make each month * '* up to 5, 5 and 3, respectively of kinds 1, 2 and 3.* '* 3) for organisation reasons, the builder can make up * '* to 8 houses monthly of kinds 1,2 and 3, respecti- * '* vely in the proportions of 3, 2 and 1. * '* The builder, having these data, wants to maximize his * '* monthly profit by knowing the number oh houses of * '* each kind to build monthly. * '* ----------------------------------------------------- * '* SAMPLE RUN: * '* (Maximize 15 X1 + 17 X2 + 20 X3 with conditions: * '* X2 - X3 <= 2 * '* 3 X1 + 3 X2 + 5 X3 <= 15 * '* 3 X1 + 2 X2 + X3 <= 8 ) * '* * '* LINEAR PROGRAMMING * '* * '* MAXIMIZE ? Y * '* * '* NUMBER OF VARIABLES OF ECONOMIC FUNCTION ? 3 * '* * '* NUMBER OF CONSTRAINTS ? 3 * '* * '* INPUT COEFFICIENTS OF ECONOMIC FUNCTION: * '* #1 ? 15 * '* #2 ? 17 * '* #3 ? 20 * '* Right hand side ? 0 * '* * '* CONSTRAINT #1: * '* #1 ? 0 * '* #2 ? 1 * '* #3 ? -1 * '* Right hand side ? 2 * '* * '* CONSTRAINT #2: * '* #1 ? 3 * '* #2 ? 3 * '* #3 ? 5 * '* Right hand side ? 15 * '* * '* CONSTRAINT #3: * '* #1 ? 3 * '* #2 ? 2 * '* #3 ? 1 * '* Right hand side ? 8 * '* * '* RESULTS: * '* VARIABLE #1 : .3333334 * '* VARIABLE #2 : 3 * '* VARIABLE #3 : 1 * '* * '* ECONOMIC FUNCTION: 76 * '* * '* (Building monthly 1/3, 3 and 1 house(s) of kinds 1,2, * '* 3, the builder can make a monthly profit of 76000\$). * '* ----------------------------------------------------- * '* REFERENCE: * '* Modèles pratiques de décision Tome 2, By Jean-Pierre * '* Blanger, PSI Editions, France, 1982. * '********************************************************* OPTION BASE 0 DEFINT I-N 'PROGRAM SIMPLEX CLS GOSUB 2000 'INPUTS GOSUB 3000 'SIMPLEX METHOD GOSUB 7000 'PRINT OUTPUTS END 'OF MAIN 2000 'INPUTS PRINT PRINT " LINEAR PROGRAMMING" PRINT INPUT " MAXIMIZE "; R1\$ PRINT INPUT " NUMBER OF VARIABLES OF ECONOMIC FUNCTION "; NV PRINT INPUT " NUMBER OF CONSTRAINTS "; NC PRINT IF LEFT\$(R1\$, 1) = "Y" THEN R1 = 1 ELSE R1 = -1 END IF DIM TS(NC + 1, NV + 1) PRINT " INPUT COEFFICIENTS OF ECONOMIC FUNCTION:" FOR J = 1 TO NV PRINT " #"; J; : INPUT R2 TS(1, J + 1) = R2 * R1 NEXT J INPUT " Right hand side "; R2 TS(1, 1) = R2 * R1 FOR I = 1 TO NC PRINT PRINT " CONSTRAINT #"; I FOR J = 1 TO NV PRINT " #"; J; : INPUT R2 TS(I + 1, J + 1) = -R2 NEXT J INPUT " Right hand side "; TS(I + 1, 1) NEXT I PRINT PRINT " RESULTS:" PRINT FOR J = 1 TO NV: TS(0, J + 1) = J: NEXT J FOR I = NV + 1 TO NV + NC: TS(I - NV + 1, 0) = I: NEXT I RETURN 3000 'SIMPLEX METHOD 3010 GOSUB 4000 'SEARCH PIVOT GOSUB 5000 'USE SIMPLEX FORMULA GOSUB 6000 'OPTIMIZE IF NOPTIMAL = 1 THEN GOTO 3010 RETURN 4000 'PIVOT XMAX = 0 FOR J = 2 TO NV + 1 IF TS(1, J) > 0 AND TS(1, J) > XMAX THEN XMAX = TS(1, J) P2 = J END IF NEXT J RAP = 999999 FOR I = 2 TO NC + 1 IF TS(I, P2) >= 0 THEN GOTO 4100 V = ABS(TS(I, 1) / TS(I, P2)) IF V < RAP THEN RAP = V P1 = I END IF 4100 NEXT I V = TS(0, P2): TS(0, P2) = TS(P1, 0): TS(P1, 0) = V RETURN 5000 'SIMPLEX FORMULA FOR I = 1 TO NC + 1 IF I = P1 THEN GOTO 5070 FOR J = 1 TO NV + 1 IF J = P2 THEN GOTO 5060 TS(I, J) = TS(I, J) - TS(P1, J) * TS(I, P2) / TS(P1, P2) 5060 NEXT J 5070 NEXT I TS(P1, P2) = 1 / TS(P1, P2) FOR J = 1 TO NV + 1 IF J = P2 THEN GOTO 5120 TS(P1, J) = TS(P1, J) * ABS(TS(P1, P2)) 5120 NEXT J FOR I = 1 TO NC + 1 IF I = P1 THEN GOTO 5160 TS(I, P2) = TS(I, P2) * TS(P1, P2) 5160 NEXT I RETURN 6000 'OPTIMIZE FOR I = 2 TO NC + 1 IF TS(I, 1) < 0 THEN XERR = 1 NEXT I NOPTIMAL = 0 IF XERR = 1 THEN RETURN FOR J = 2 TO NV + 1 IF TS(1, J) > 0 THEN NOPTIMAL = 1 NEXT J RETURN 7000 'PRINT OUTPUTS IF XERR = 0 THEN GOTO 7030 PRINT " NO SOLUTION.": GOTO 7100 7030 FOR I = 1 TO NV FOR J = 2 TO NC + 1 IF TS(J, 0) <> I THEN GOTO 7070 PRINT " VARIABLE #"; I; ": "; TS(J, 1) 7070 NEXT J NEXT I PRINT PRINT " ECONOMIC FUNCTION: "; TS(1, 1) 7100 PRINT : PRINT RETURN 'end of file simplex.bas