Télécharger perm12.eso

Retour à la liste

Numérotation des lignes :

  1. C PERM12 SOURCE BP208322 16/06/27 21:16:19 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 PERM12(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 XINF (DEFINED
  47. C BY THE FIRST EXECUTABLE STATEMENT OF THIS SUBROUTINE). XINF
  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. -INC CCREEL
  81. REAL*8 A(N,N),U(N),V(N),Z
  82. INTEGER F(N)
  83. INTEGER FB(N),RC(N),P(N)
  84.  
  85. XINF = XSGRAN
  86.  
  87. c=======================================================================
  88. C SEARCH FOR THE INITIAL DUAL AND PARTIAL PRIMAL SOLUTIONS.
  89. c=======================================================================
  90. c CALL INIT(N,A,F,M,XINF,U,V,FB,P)
  91. CALL PERM13(N,A,F,M,XINF,U,V,FB)
  92.  
  93. IF ( M .EQ. N ) GO TO 2
  94.  
  95.  
  96. c=======================================================================
  97. C SOLUTION OF THE REDUCED PROBLEM.
  98. c=======================================================================
  99. DO 1 I=1,N
  100.  
  101. IF ( F(I) .GT. 0 ) GO TO 1
  102.  
  103. C DETERMINATION OF AN AUGMENTING PATH STARTING FROM ROW I .
  104. c CALL PATH(N,A,I,F,XINF,J,U,V,FB,RC)
  105. CALL PERM14(N,A,I,F,XINF,J,U,V,FB,RC)
  106.  
  107. C ASSIGNMENT OF ROW I AND COLUMN J .
  108. c CALL INCR(N,F,J,U,V,FB,RC)
  109. CALL PERM15(N,F,J,FB,RC)
  110.  
  111. 1 CONTINUE
  112.  
  113. c=======================================================================
  114. C COMPUTATION OF THE SOLUTION COST Z .
  115. c=======================================================================
  116. 2 Z = 0
  117. DO 3 K=1,N
  118. Z = Z + U(K) + V(K)
  119. 3 CONTINUE
  120.  
  121. RETURN
  122. END
  123.  
  124.  
  125. c c=======================================================================
  126. c SUBROUTINE INCR(N,F,J,U,V,FB,RC)
  127. c C
  128. c C ASSIGNMENT OF COLUMN J .
  129. c C
  130. c INTEGER F(N)
  131. c INTEGER U(N),V(N),FB(N),RC(N)
  132. c 1 I = RC(J)
  133. c FB(J) = I
  134. c JJ = F(I)
  135. c F(I) = J
  136. c J = JJ
  137. c IF ( J .GT. 0 ) GO TO 1
  138. c RETURN
  139. c END
  140.  
  141. c c=======================================================================
  142. c SUBROUTINE INIT(N,A,F,M,XINF,U,V,FB,P)
  143. c C
  144. c C SEARCH FOR THE INITIAL DUAL AND PARTIAL PRIMAL SOLUTIONS.
  145. c C
  146. c C P(I) = FIRST UNSCANNED COLUMN OF ROW I .
  147. c C
  148. c INTEGER A(N,N),F(N)
  149. c INTEGER U(N),V(N),FB(N),P(N),R
  150. c C PHASE 1 .
  151. c M = 0
  152. c DO 10 K=1,N
  153. c F(K) = 0
  154. c FB(K) = 0
  155. c 10 CONTINUE
  156. c C SCANNING OF THE COLUMNS ( INITIALIZATION OF V(J) ).
  157. c DO 40 J=1,N
  158. c MIN = XINF
  159. c DO 30 I=1,N
  160. c IA = A(I,J)
  161. c IF ( IA .GT. MIN ) GO TO 30
  162. c IF ( IA .LT. MIN ) GO TO 20
  163. c IF ( F(I) .NE. 0 ) GO TO 30
  164. c 20 MIN = IA
  165. c R = I
  166. c 30 CONTINUE
  167. c V(J) = MIN
  168. c IF ( F(R) .NE. 0 ) GO TO 40
  169. c C ASSIGNMENT OF COLUMN J TO ROW R .
  170. c M = M + 1
  171. c FB(J) = R
  172. c F(R) = J
  173. c U(R) = 0
  174. c P(R) = J + 1
  175. c 40 CONTINUE
  176. c C PHASE 2 .
  177. c C SCANNING OF THE UNASSIGNED ROWS ( UPDATING OF U(I) ).
  178. c DO 110 I=1,N
  179. c IF ( F(I) .NE. 0 ) GO TO 110
  180. c MIN = XINF
  181. c DO 60 K=1,N
  182. c IA = A(I,K) - V(K)
  183. c IF ( IA .GT. MIN ) GO TO 60
  184. c IF ( IA .LT. MIN ) GO TO 50
  185. c IF ( FB(K) .NE. 0 ) GO TO 60
  186. c IF ( FB(J) .EQ. 0 ) GO TO 60
  187. c 50 MIN = IA
  188. c J = K
  189. c 60 CONTINUE
  190. c U(I) = MIN
  191. c JMIN = J
  192. c IF ( FB(J) .EQ. 0 ) GO TO 100
  193. c DO 80 J=JMIN,N
  194. c IF ( A(I,J) - V(J) .GT. MIN ) GO TO 80
  195. c R = FB(J)
  196. c KK = P(R)
  197. c IF ( KK .GT. N ) GO TO 80
  198. c DO 70 K=KK,N
  199. c IF ( FB(K) .GT. 0 ) GO TO 70
  200. c IF ( A(R,K) - U(R) - V(K) .EQ. 0 ) GO TO 90
  201. c 70 CONTINUE
  202. c P(R) = N + 1
  203. c 80 CONTINUE
  204. c GO TO 110
  205. c C REASSIGNMENT OF ROW R AND COLUMN K .
  206. c 90 F(R) = K
  207. c FB(K) = R
  208. c P(R) = K + 1
  209. c C ASSIGNMENT OF COLUMN J TO ROW I .
  210. c 100 M = M + 1
  211. c F(I) = J
  212. c FB(J)= I
  213. c P(I) = J + 1
  214. c 110 CONTINUE
  215. c RETURN
  216. c END
  217.  
  218. c c=======================================================================
  219. c SUBROUTINE PATH(N,A,II,F,XINF,JJ,U,V,FB,RC)
  220. c C
  221. c C DETERMINATION OF AN AUGMENTING PATH STARTING FROM
  222. c C UNASSIGNED ROW II AND TERMINATING AT UNASSIGNED COLUMN
  223. c C JJ , WITH UPDATING OF DUAL VARIABLES U(I) AND V(J) .
  224. c C
  225. c C MEANING OF THE MAIN INTERNAL VARIABLES:
  226. c C LR(L) = L-TH LABELLED ROW ( L=1,NLR ).
  227. c C PI(J) = MIN ( A(I,J) - U(I) - V(J) , SUCH THAT ROW I IS
  228. c C LABELLED AND NOT EQUAL TO FB(J) ).
  229. c C RC(J) = ROW PRECEDING COLUMN J IN THE CURRENT
  230. c C ALTERNATING PATH.
  231. c C UC(L) = L-TH UNLABELLED COLUMN ( L=1,NUC ).
  232. c C
  233. c INTEGER A(N,N),F(N),Z
  234. c INTEGER PI(N),LR(N),UC(N)
  235. c INTEGER U(N),V(N),FB(N),RC(N),R
  236. c C INITIALIZATION.
  237. c LR(1) = II
  238. c DO 10 K=1,N
  239. c PI(K) = A(II,K) - U(II) - V(K)
  240. c RC(K) = II
  241. c UC(K) = K
  242. c 10 CONTINUE
  243. c NUC = N
  244. c NLR = 1
  245. c GO TO 40
  246. c C SCANNING OF THE LABELLED ROWS.
  247. c 20 R = LR(NLR)
  248. c DO 30 L=1,NUC
  249. c J = UC(L)
  250. c IA = A(R,J) - U(R) - V(J)
  251. c IF ( IA .GE. PI(J) ) GO TO 30
  252. c PI(J) = IA
  253. c RC(J) = R
  254. c 30 CONTINUE
  255. c C SEARCH FOR A ZERO ELEMENT IN AN UNLABELLED COLUMN.
  256. c 40 DO 50 L=1,NUC
  257. c J = UC(L)
  258. c IF ( PI(J) .EQ. 0 ) GO TO 100
  259. c 50 CONTINUE
  260. c C UPDATING OF THE DUAL VARIABLES U(I) AND V(J) .
  261. c MIN = XINF
  262. c DO 60 L=1,NUC
  263. c J = UC(L)
  264. c IF ( MIN .GT. PI(J) ) MIN = PI(J)
  265. c 60 CONTINUE
  266. c DO 70 L=1,NLR
  267. c R = LR(L)
  268. c U(R) = U(R) + MIN
  269. c 70 CONTINUE
  270. c DO 90 J=1,N
  271. c IF ( PI(J) .EQ. 0 ) GO TO 80
  272. c PI(J) = PI(J) - MIN
  273. c GO TO 90
  274. c 80 V(J) = V(J) - MIN
  275. c 90 CONTINUE
  276. c GO TO 40
  277. c 100 IF ( FB(J) .EQ. 0 ) GO TO 110
  278. c C LABELLING OF ROW FB(J) AND REMOVAL OF THE LABEL OF
  279. c C COLUMN J .
  280. c NLR = NLR + 1
  281. c LR(NLR) = FB(J)
  282. c UC(L) = UC(NUC)
  283. c NUC = NUC - 1
  284. c GO TO 20
  285. c C DETERMINATION OF THE UNASSIGNED COLUMN J .
  286. c 110 JJ = J
  287. c RETURN
  288. c END
  289. c
  290.  
  291.  

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