220
Appendix A. Computer
Program Listing and
Instructions
IF (FLOW(A) .GE. HI(Α) .OR. (FLOW(A) .GE. LO(A) .AND. C .GT. 0)) G
J
55
10 TO 120
J
56
c«*«* LABELING PROCESS THROUGH A FORWARD ARC
NA(JA) s 1(A)
J
57
NB(JA) = A
J
58
GO TO 110
J
59
ο····
ARC FLOW CANNOT BE DECREASEO WITHOUT ORIVING IT (MORE) OUT OF KILTER
100
IF (FLOW(A) .LE. LOCA) .OR. (FLOW(A) .LE. HI(A) ·AND. C .LT. 0)) G
J
60
10 TO 120
J
61
LABELING PROCESS THROUGH A REVERSE ARC
IA = 1(A)
J
62
NA(IA) = -J(A)
J
63
NB(IA) = -A
J
64
110
LAB = 1
J
65
NODE LABELED, TEST FOR BREAKTHRU
J
66
IF (NA(SNK) .NF. 0) GO TO 150
J
67
120
CONTINUE
J
68
0···· NO dREAKTHRU
J
69
IF (LAB .NE. 0) GO TO 90
J
70
c«*»» DETERMINE CHANGE TO PI VECTOR
J
71
DEL = INF
J
72
DO 130 A s 1· ARCS
J
73
ΙΑ = I(A)$JA = J(A)
J
74
IF ((NA(IA) .EO. 0 .AND. NA(JA) .EQ. 0) .OR. (NA(IA) ·ΝΕ· 0 .AND.
J
75
1NA(JA) .NE. 0)) GO TO 130
J
76
C = COST(A)*PI(IA)-PI(JA)
J
77
IF (NA(JA) .EO. 0 .AND. FLOW(A) .LT. HI(A)) DEL = MINO(DEL* C)
J
78
IF (NA(JA) .NE. 0 .AND. FLOW(A) .GT. LO(A)) DEL = MINO(DEL· -C)
J
79
130
CONTINUE
J
80
IF (DEL ·ΕΟ· INF .AND. (FLOW(AOK) .FO. HI(AOK) .OR. FLOW(AOK) # EO.
J
81
1 LO(AOK))) DEL = ABS(COK)
J
82
c«*«» EXIT. NO FEASIBLE FLOW PATTERN
J
83
IF (DEL .EQ. INF) GO TO 210
J
84
c«««« CHANGE PI VECTOR BY COMPUTED DEL
J
85
DO 140 Ν a 1, NODES
J
86
140
IF (NA(N) .EQ. 0) PI(N) * PI(N)*DEL
J
87
FIND ANOTHER OUT-OF-KILTER ARC
J
88
GO TO 20
J
89
c»«*« BREAKTHRU* COMPUTE INCREMENTAL FLOW
J
90
ISO
EPS = INF
J
91
NI = SRC
J
92
160
NJ = IABS(NA(NI))
J
93
A = IABS(NB(NI>)
J
94
C = C0ST(A)*PI(NI)-PI(NJ)
J
95
IF (NB(NI) .LT. 0) GO TO 170
J
96
IF (C .GT. 0 .AND. FLOW(A) .LT. LO(A)) EPS = MIN0(EPS, LO(A)-FLOW(
J
97
1A) )
J
98
IF (C .LE. 0 .AND. FLOW(A) .LT. HI(A)) EPS = MlN0(EPS* HI(A)-FLOW(
J
99
1A) )
J 100
GO TO 180
J 101
170
IF (C .LT. 0 .AND. FLOW(A) .GT. HI(A)) EPS = MlN0(EPS* FLOW(A)-HI(
J 102
1A) )
J 103
IF (C .GE. 0 .AND. FLOW(A) .GT. LO(A)) EPS = MIN0(EPS, FLOW(A)-LO(
J 104
1A) )
J 105
180
Nl = NJ
J 106
IF (NI .NE. SRC) GO TO 160
J 107
c««*« CHANGE FLOW VECTOR BY COMPUTED EPS
J 10ft
190
NJ = IABS(NA(NI))
J 109
A = IABS(NB(NI))
J no
FLOW(A) = FLOW(A)•ISIGNiEPSt NB(NI))
J 111
NI = NJ
J 112
IF (NI .NE. SRC) GO TO 190
J 113