Télécharger perm22.eso

Retour à la liste

Numérotation des lignes :

  1. C PERM22 SOURCE BP208322 16/06/27 21:16:22 8990
  2. C ******* SAMPLE CALLING PROGRAM FOR SUBROUTINE APC *******
  3. C *** (MIN-COST ASSIGNMENT PROBLEM) ***
  4. C *** ***
  5. C *** THE PROGRAM IS BASED ON THE PAPER ***
  6. C *** G. CARPANETO, S. MARTELLO, P. TOTH "ALGORITHMS ***
  7. C *** AND CODES FOR THE ASSIGNMENT PROBLEM", ***
  8. C *** ANNALS OF OPERATIONS RESEARCH 7, 1988. ***
  9. C *** ***
  10. C *** ALL THE SUBROUTINES ARE WRITTEN IN AMERICAN ***
  11. C *** STANDARD FORTRAN AND ARE ACCEPTED BY THE ***
  12. C *** PFORT VERIFIER. ***
  13. C *** ***
  14. C *** QUESTIONS AND COMMENTS SHOULD BE DIRECTED TO ***
  15. C *** SILVANO MARTELLO AND PAOLO TOTH ***
  16. C *** D.E.I.S., UNIVERSITA' DI BOLOGNA, ***
  17. C *** VIALE RISORGIMENTO 2, ***
  18. C *** 40136, BOLOGNA, ITALY. ***
  19. C ************************************************************
  20. C
  21.  
  22. SUBROUTINE PERM22(N,A,F,Z)
  23. C
  24. C SOLUTION OF THE LINEAR MIN-SUM ASSIGNMENT PROBLEM.
  25. C
  26. C HUNGARIAN METHOD. COMPLEXITY O(N**3).
  27. C
  28. C
  29. C MEANING OF THE INPUT PARAMETERS:
  30. C N = NUMBER OF ROWS AND COLUMNS OF THE COST MATRIX.
  31. C A(I,J) = COST OF THE ASSIGNMENT OF ROW I TO COLUMN J .
  32. C ON RETURN, THE INPUT PARAMETERS ARE UNCHANGED.
  33. C
  34. C MEANING OF THE OUTPUT PARAMETERS:
  35. C F(I) = COLUMN ASSIGNED TO ROW I .
  36. C Z = COST OF THE OPTIMAL ASSIGNMENT =
  37. C = A(1,F(1)) + A(2,F(2)) + ... + A(N,F(N)) .
  38. C
  39. C ALL THE PARAMETERS ARE INTEGERS.
  40. C VECTOR F MUST BE DIMENSIONED AT LEAST AT N , MATRIX A
  41. C AT LEAST AT (N,N) . AS CURRENTLY DIMENSIONED, THE SIZE
  42. C LIMITATION IS N .LE. 260 . IN ALL THE SUBROUTINES, THE
  43. C INTERNAL VARIABLES WHICH ARE PRESENTLY DIMENSIONED AT
  44. C 260 MUST BE DIMENSIONED AT LEAST AT N .
  45. C
  46. C THE ONLY MACHINE-DEPENDENT CONSTANT USED IS INF (DEFINED
  47. C BY THE FIRST EXECUTABLE STATEMENT OF THIS SUBROUTINE). INF
  48. C MUST BE SET TO A VERY LARGE INTEGER VALUE.
  49. C
  50. C THE CODE IS BASED ON THE HUNGARIAN METHOD AS DESCRIBED BY
  51. C LAWLER (COMBINATORIAL OPTIMIZATION : NETWORKS AND
  52. C MATROIDS, HOLT, RINEHART AND WINSTON, NEW YORK, 1976).
  53. C THE ALGORITHMIC PASCAL-LIKE DESCRIPTION OF THE CODE IS
  54. C GIVEN IN G.CARPANETO, S.MARTELLO AND P.TOTH, ALGORITHMS AND
  55. C CODES FOR THE ASSIGNMENT PROBLEM, ANNALS OF OPERATIONS
  56. C RESEARCH 7, 1988.
  57. C
  58. C SUBROUTINE APC DETERMINES THE INITIAL DUAL AND PARTIAL
  59. C PRIMAL SOLUTIONS AND THEN SEARCHES FOR AUGMENTING PATHS
  60. C UNTIL ALL ROWS AND COLUMNS ARE ASSIGNED.
  61. C
  62. C MEANING OF THE MAIN INTERNAL VARIABLES:
  63. C FB(J) = ROW ASSIGNED TO COLUMN J .
  64. C M = NUMBER OF INITIAL ASSIGNMENTS.
  65. C U(I) = DUAL VARIABLE ASSOCIATED WITH ROW I .
  66. C V(J) = DUAL VARIABLE ASSOCIATED WITH COLUMN J .
  67. C
  68. C APC NEEDS THE FOLLOWING SUBROUTINES: INCR
  69. C INIT
  70. C PATH
  71. C
  72. C ALL THE SUBROUTINES ARE WRITTEN IN AMERICAN NATIONAL
  73. C STANDARD FORTRAN AND ARE ACCEPTED BY THE PFORT VERIFIER.
  74. C
  75. C
  76. C THIS WORK WAS SUPPORTED BY C.N.R. , ITALY.
  77. C
  78. IMPLICIT INTEGER(I-N)
  79. IMPLICIT REAL*8(A-H,O-Z)
  80.  
  81. INTEGER A(N,N),F(N),Z
  82. INTEGER U(N),V(N),FB(N),RC(N),P(N)
  83.  
  84. INF = 10**9
  85.  
  86. c=======================================================================
  87. C SEARCH FOR THE INITIAL DUAL AND PARTIAL PRIMAL SOLUTIONS.
  88. c=======================================================================
  89. c CALL INIT(N,A,F,M,INF,U,V,FB,P)
  90. CALL PERM23(N,A,F,M,INF,U,V,FB)
  91.  
  92. IF ( M .EQ. N ) GO TO 2
  93.  
  94.  
  95. c=======================================================================
  96. C SOLUTION OF THE REDUCED PROBLEM.
  97. c=======================================================================
  98. DO 1 I=1,N
  99.  
  100. IF ( F(I) .GT. 0 ) GO TO 1
  101.  
  102. C DETERMINATION OF AN AUGMENTING PATH STARTING FROM ROW I .
  103. c CALL PATH(N,A,I,F,INF,J,U,V,FB,RC)
  104. CALL PERM24(N,A,I,F,INF,J,U,V,FB,RC)
  105.  
  106. C ASSIGNMENT OF ROW I AND COLUMN J .
  107. c CALL INCR(N,F,J,U,V,FB,RC)
  108. CALL PERM25(N,F,J,FB,RC)
  109.  
  110. 1 CONTINUE
  111.  
  112. c=======================================================================
  113. C COMPUTATION OF THE SOLUTION COST Z .
  114. c=======================================================================
  115. 2 Z = 0
  116. DO 3 K=1,N
  117. Z = Z + U(K) + V(K)
  118. 3 CONTINUE
  119.  
  120. RETURN
  121. END
  122.  
  123.  
  124. c c=======================================================================
  125. c SUBROUTINE INCR(N,F,J,U,V,FB,RC)
  126. c C
  127. c C ASSIGNMENT OF COLUMN J .
  128. c C
  129. c INTEGER F(N)
  130. c INTEGER U(N),V(N),FB(N),RC(N)
  131. c 1 I = RC(J)
  132. c FB(J) = I
  133. c JJ = F(I)
  134. c F(I) = J
  135. c J = JJ
  136. c IF ( J .GT. 0 ) GO TO 1
  137. c RETURN
  138. c END
  139.  
  140. c c=======================================================================
  141. c SUBROUTINE INIT(N,A,F,M,INF,U,V,FB,P)
  142. c C
  143. c C SEARCH FOR THE INITIAL DUAL AND PARTIAL PRIMAL SOLUTIONS.
  144. c C
  145. c C P(I) = FIRST UNSCANNED COLUMN OF ROW I .
  146. c C
  147. c INTEGER A(N,N),F(N)
  148. c INTEGER U(N),V(N),FB(N),P(N),R
  149. c C PHASE 1 .
  150. c M = 0
  151. c DO 10 K=1,N
  152. c F(K) = 0
  153. c FB(K) = 0
  154. c 10 CONTINUE
  155. c C SCANNING OF THE COLUMNS ( INITIALIZATION OF V(J) ).
  156. c DO 40 J=1,N
  157. c MIN = INF
  158. c DO 30 I=1,N
  159. c IA = A(I,J)
  160. c IF ( IA .GT. MIN ) GO TO 30
  161. c IF ( IA .LT. MIN ) GO TO 20
  162. c IF ( F(I) .NE. 0 ) GO TO 30
  163. c 20 MIN = IA
  164. c R = I
  165. c 30 CONTINUE
  166. c V(J) = MIN
  167. c IF ( F(R) .NE. 0 ) GO TO 40
  168. c C ASSIGNMENT OF COLUMN J TO ROW R .
  169. c M = M + 1
  170. c FB(J) = R
  171. c F(R) = J
  172. c U(R) = 0
  173. c P(R) = J + 1
  174. c 40 CONTINUE
  175. c C PHASE 2 .
  176. c C SCANNING OF THE UNASSIGNED ROWS ( UPDATING OF U(I) ).
  177. c DO 110 I=1,N
  178. c IF ( F(I) .NE. 0 ) GO TO 110
  179. c MIN = INF
  180. c DO 60 K=1,N
  181. c IA = A(I,K) - V(K)
  182. c IF ( IA .GT. MIN ) GO TO 60
  183. c IF ( IA .LT. MIN ) GO TO 50
  184. c IF ( FB(K) .NE. 0 ) GO TO 60
  185. c IF ( FB(J) .EQ. 0 ) GO TO 60
  186. c 50 MIN = IA
  187. c J = K
  188. c 60 CONTINUE
  189. c U(I) = MIN
  190. c JMIN = J
  191. c IF ( FB(J) .EQ. 0 ) GO TO 100
  192. c DO 80 J=JMIN,N
  193. c IF ( A(I,J) - V(J) .GT. MIN ) GO TO 80
  194. c R = FB(J)
  195. c KK = P(R)
  196. c IF ( KK .GT. N ) GO TO 80
  197. c DO 70 K=KK,N
  198. c IF ( FB(K) .GT. 0 ) GO TO 70
  199. c IF ( A(R,K) - U(R) - V(K) .EQ. 0 ) GO TO 90
  200. c 70 CONTINUE
  201. c P(R) = N + 1
  202. c 80 CONTINUE
  203. c GO TO 110
  204. c C REASSIGNMENT OF ROW R AND COLUMN K .
  205. c 90 F(R) = K
  206. c FB(K) = R
  207. c P(R) = K + 1
  208. c C ASSIGNMENT OF COLUMN J TO ROW I .
  209. c 100 M = M + 1
  210. c F(I) = J
  211. c FB(J)= I
  212. c P(I) = J + 1
  213. c 110 CONTINUE
  214. c RETURN
  215. c END
  216.  
  217. c c=======================================================================
  218. c SUBROUTINE PATH(N,A,II,F,INF,JJ,U,V,FB,RC)
  219. c C
  220. c C DETERMINATION OF AN AUGMENTING PATH STARTING FROM
  221. c C UNASSIGNED ROW II AND TERMINATING AT UNASSIGNED COLUMN
  222. c C JJ , WITH UPDATING OF DUAL VARIABLES U(I) AND V(J) .
  223. c C
  224. c C MEANING OF THE MAIN INTERNAL VARIABLES:
  225. c C LR(L) = L-TH LABELLED ROW ( L=1,NLR ).
  226. c C PI(J) = MIN ( A(I,J) - U(I) - V(J) , SUCH THAT ROW I IS
  227. c C LABELLED AND NOT EQUAL TO FB(J) ).
  228. c C RC(J) = ROW PRECEDING COLUMN J IN THE CURRENT
  229. c C ALTERNATING PATH.
  230. c C UC(L) = L-TH UNLABELLED COLUMN ( L=1,NUC ).
  231. c C
  232. c INTEGER A(N,N),F(N),Z
  233. c INTEGER PI(N),LR(N),UC(N)
  234. c INTEGER U(N),V(N),FB(N),RC(N),R
  235. c C INITIALIZATION.
  236. c LR(1) = II
  237. c DO 10 K=1,N
  238. c PI(K) = A(II,K) - U(II) - V(K)
  239. c RC(K) = II
  240. c UC(K) = K
  241. c 10 CONTINUE
  242. c NUC = N
  243. c NLR = 1
  244. c GO TO 40
  245. c C SCANNING OF THE LABELLED ROWS.
  246. c 20 R = LR(NLR)
  247. c DO 30 L=1,NUC
  248. c J = UC(L)
  249. c IA = A(R,J) - U(R) - V(J)
  250. c IF ( IA .GE. PI(J) ) GO TO 30
  251. c PI(J) = IA
  252. c RC(J) = R
  253. c 30 CONTINUE
  254. c C SEARCH FOR A ZERO ELEMENT IN AN UNLABELLED COLUMN.
  255. c 40 DO 50 L=1,NUC
  256. c J = UC(L)
  257. c IF ( PI(J) .EQ. 0 ) GO TO 100
  258. c 50 CONTINUE
  259. c C UPDATING OF THE DUAL VARIABLES U(I) AND V(J) .
  260. c MIN = INF
  261. c DO 60 L=1,NUC
  262. c J = UC(L)
  263. c IF ( MIN .GT. PI(J) ) MIN = PI(J)
  264. c 60 CONTINUE
  265. c DO 70 L=1,NLR
  266. c R = LR(L)
  267. c U(R) = U(R) + MIN
  268. c 70 CONTINUE
  269. c DO 90 J=1,N
  270. c IF ( PI(J) .EQ. 0 ) GO TO 80
  271. c PI(J) = PI(J) - MIN
  272. c GO TO 90
  273. c 80 V(J) = V(J) - MIN
  274. c 90 CONTINUE
  275. c GO TO 40
  276. c 100 IF ( FB(J) .EQ. 0 ) GO TO 110
  277. c C LABELLING OF ROW FB(J) AND REMOVAL OF THE LABEL OF
  278. c C COLUMN J .
  279. c NLR = NLR + 1
  280. c LR(NLR) = FB(J)
  281. c UC(L) = UC(NUC)
  282. c NUC = NUC - 1
  283. c GO TO 20
  284. c C DETERMINATION OF THE UNASSIGNED COLUMN J .
  285. c 110 JJ = J
  286. c RETURN
  287. c END
  288. c
  289.  
  290.  

© Cast3M 2003 - Tous droits réservés.
Mentions légales