'********************************************************** '* DANTZIG'S MODEL * '* * '* LIST OF MAIN VARIABLES: * '* * '* NR : TOTAL NUMBER OF MARKS * '* V(NR,NR) : PATH VALUES * '* XL(NR) : USED FOR WEIGHTING OF EACH PATH * '* IE(NR*2) : SET OF ADOPTED MARKS * '* V : PATH VALUE * '* IR : NUMBER OF MARKS COMING FROM A SAME MARK * '* RA : INDEX OF AN ARRIVAL MARK * '* R\$ : = "YES" ON OPTIMAL ROUTE * '* XM1,XM2 : USED TO SEEK MINIMUM, MAXIMUM PATH * '* IASSO : ARRIVAL MARK ASSOCIATED WITH SET IE * '* ------------------------------------------------------ * '* PROBLEM DESCRIPTION: * '* A mountaineer wants to climb up a stiff face. He has * '* preliminarily estimated that he can follow different * '* paths from 0 (bottom) to 8 (summit) with different * '* lengths: * '* Path 1: 0 - 1 - 4 - 7 - 8 * '* Path 2: 0 - 3 - 5 - 8 * '* Path 3: 0 - 2 - 6 - 5 - 8 * '* Path 3a: 0 - 2 - 6 - 7 - 8 * '* Path 4: 0 - 1 - 2 - 4 - 7 - 8 * '* Path 4a: 0 - 1 - 2 - 4 - 6 - 7 - 8 * '* The mountaineer wants to know the maximum length rope * '* to take, knowing the following distance matrix * '* (meters): * '* START/ARR/DIST START/ARR/DIST START/ARR/DIST * '* 0 1 5 0 2 11 0 3 10 * '* 1 2 4 1 4 6 * '* 2 4 5 2 6 9 * '* 3 5 2 4 7 5 * '* 5 6 4 5 8 15 * '* 6 7 6 7 8 8 * '* ------------------------------------------------------ * '* SAMPLE RUN: * '* * '* DO YOU WANT THE MINIMUM PATH ? NO * '* * '* NUMBER OF MARKS ? 9 * '* * '* NUMBER OF ARCS FROM MARK #0 ? 3 * '* ARRIVAL MARK, VALUE ? 1,5 * '* ARRIVAL MARK, VALUE ? 2,11 * '* ARRIVAL MARK, VALUE ? 3,10 * '* * '* NUMBER OF ARCS FROM MARK #1 ? 2 * '* ARRIVAL MARK, VALUE ? 2,4 * '* ARRIVAL MARK, VALUE ? 4,6 * '* * '* NUMBER OF ARCS FROM MARK #2 ? 2 * '* ARRIVAL MARK, VALUE ? 4,5 * '* ARRIVAL MARK, VALUE ? 6,9 * '* * '* NUMBER OF ARCS FROM MARK #3 ? 1 * '* ARRIVAL MARK, VALUE ? 5,2 * '* * '* NUMBER OF ARCS FROM MARK #4 ? 1 * '* ARRIVAL MARK, VALUE ? 7,5 * '* * '* NUMBER OF ARCS FROM MARK #5 ? 2 * '* ARRIVAL MARK, VALUE ? 6,4 * '* ARRIVAL MARK, VALUE ? 8,15 * '* * '* NUMBER OF ARCS FROM MARK #6 ? 1 * '* ARRIVAL MARK, VALUE ? 7,6 * '* * '* NUMBER OF ARCS FROM MARK #7 ? 1 * '* ARRIVAL MARK, VALUE ? 8,8 * '* * '* RESULTS: * '* * '* THE MAXIMUM VALUE PATH IS: * '* * '* <- 0 - 2 - 6 - 7 - 8 -> * '* * '* PATH VALUE = 34 * '* * '* ------------------------------------------------------ * '* REFERENCE: * '* Modèles pratiques de décision Tome 2, By Jean-Pierre * '* Blanger, PSI Editions, France, 1982. * '********************************************************** 'PROGRAM DANTZIG OPTION BASE 0 DEFINT I-N CLS GOSUB 2000 'INPUT DATA GOSUB 3000 'DANTZIG MODEL GOSUB 4000 'EDIT OPTIMAL PATH END 2000 'INPUT DATA PRINT INPUT " DO YOU WANT THE MINIMUM PATH ? ", R\$ R\$ = MID\$(R\$, 1, 1) PRINT INPUT " NUMBER OF MARKS ? ", NR PRINT DIM V(NR, NR), XL(NR), IE(NR * 2) FOR I = 0 TO NR - 2 PRINT " NUMBER OF ARCS FROM MARK #"; I; " ? "; INPUT "", IR FOR J = 1 TO IR INPUT " ARRIVAL MARK, VALUE ? "; RA, V V(I, RA) = V NEXT J PRINT NEXT I PRINT PRINT " RESULTS" PRINT IF R\$ = "O" OR R\$ = "o" THEN PRINT " THE MINIMUM VALUE PATH IS:" ELSE PRINT " THE MAXIMUM VALUE PATH IS:" END IF PRINT RETURN 3000 'DANTZIG XL(0) = 0 K = 1: IE(K) = 0 3030 IF R\$ = "N" THEN XM1 = -999999: XM2 = -999999 ELSE XM1 = 999999: XM2 = 999999 END IF FOR IO = 1 TO K FOR ID = 1 TO NR IF R\$ = "N" THEN IF V(IE(IO), ID) < XM1 OR V(IE(IO), ID) = 0 THEN GOTO 3170 ELSE IF V(IE(IO), ID) > XM1 OR V(IE(IO), ID) = 0 THEN GOTO 3170 END IF FOR J = 1 TO K IF IE(J) = ID THEN F = 1: J = K NEXT J IF F = 1 THEN F = 0: GOTO 3170 XM1 = V(IE(IO), ID): IASSO = ID 3170 NEXT ID V = XL(IE(IO)) + XM1 IF R\$ = "N" THEN IF V > XM2 THEN XM2 = V: IE(K + 1) = IASSO ELSE IF V < XM2 THEN XM2 = V: IE(K + 1) = IASSO END IF NEXT IO XL(IE(K + 1)) = XM2 K = K + 1: IF IE(K) <> NR - 1 THEN GOTO 3030 RETURN 4000 'EDIT OPTIMAL PATH IO = IE(1): ID = IE(2): K = 1: XL = 0 PRINT " <- 0 -"; 4030 IF V(IO, ID) <> 0 THEN XL = XL + V(IO, ID) PRINT ID; "-"; : IO = ID: K = K + 1: ID = IE(K) GOTO 4050 END IF K = K + 1: ID = IE(K) 4050 IF ID <> NR - 1 THEN GOTO 4030 XL = XL + V(IO, ID) PRINT ID; " ->" PRINT PRINT " PATH VALUE = "; XL PRINT RETURN 'end of file dantzig.bas