ÐÏࡱá>þÿ þÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿRoot Entryÿÿÿÿÿÿÿÿ*0_šîÏ»òÀð^Ç#ë€ïÅ € Contentsÿÿÿÿÿÿÿÿÿÿÿÿ€ ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿþÿÿÿýÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿþÿÿÿþÿÿÿ  ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿRoot Entryÿÿÿÿÿÿÿÿ*0_šîÏ»òÀð^ Ù÷€ïÅ€ Contentsÿÿÿÿÿÿÿÿÿÿÿÿ€ ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿþÿÿÿýÿÿÿþÿÿÿ ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿþÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ  !"#$%&'()*+,-þÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿì‹{\rtf1\ansi\ansicpg1252\deff0\deflang1033{\fonttbl{\f0\fnil\fcharset0 Courier New;}} {\colortbl ;\red0\green0\blue255;\red0\green0\blue0;\red0\green175\blue0;} \viewkind4\uc1\pard\cf1\f0\fs20 MODEL\cf2 : \par \cf1 SETS\cf2 : \par \cf3 ! Dynamic programming illustration (see Anderson, \par Sweeney & Williams, An Intro to Mgt Science, \par 6th Ed.). We have a network of 10 cities. We \par want to find the length of the shortest route \par from city 1 to city 10.;\cf2 \par \cf3 ! Here is our primitive set of ten cities, where \par F( i) represents the shortest path distance \par from city i to the last city;\cf2 \par CITIES /1..10/: F, CONPATH; \par \cf3 ! The derived set ROADS lists the roads that \par exist between the cities (note: not all city \par pairs are directly linked by a road, and roads \par are assumed to be one way.);\cf2 \par ROADS( CITIES, CITIES)/ \par 1,2 1,3 1,4 \par 2,5 2,6 2,7 \par 3,5 3,6 3,7 \par 4,5 4,6 \par 5,8 5,9 \par 6,8 6,9 \par 7,8 7,9 \par 8,10 9,10/: D, RONPATH; \par \cf3 ! D( i, j) is the distance from city i to j;\cf2 \par \cf1 ENDSETS\cf2 \par \cf1 DATA\cf2 : \par \cf3 ! Here are the distances that correspond to the \par above links;\cf2 \par D = \par 1 5 2 \par 13 12 11 \par 6 10 4 \par 12 14 \par 3 9 \par 6 5 \par 8 10 \par 5 2; \par \cf1 ENDDATA\cf2 \par \cf3 ! If ou are already in last city, then the cost to \par travel to it is 0;\cf2 \par F( \cf1 @SIZE\cf2 ( CITIES)) = 0; \par \cf3 ! The following is the classic dynamic programming \par recursion. In words, the shortest distance from \par City i to last city is the minimum over all \par cities j reachable from i of the sum of the \par distance from i to j plus the minimal distance \par from j to last city;\cf2 \par \cf1 @FOR\cf2 ( CITIES( i)| i #LT# \cf1 @SIZE\cf2 ( CITIES): \par F( i) = \cf1 @MIN\cf2 ( ROADS( i, j): D( i, j) + F( j)); \par ); \par \cf3 ! Set CONPATH( j) > 0 if city j is on any critical path, \par i.e., if going to j from some i on the critical path, \par still allows us to get to last city in optimal time;\cf2 \par CONPATH( 1) = 1; \par \cf1 @FOR\cf2 ( CITIES( j)| j #GT# 1: \par CONPATH( j) = \cf1 @MAX\cf2 ( ROADS( i,j): CONPATH( i)*((F(I)-F( j) #EQ# D(i,j)))); \par ); \par \cf3 ! Set RONPATH(i,  !"#$%&'()*+,-þÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿj) = 1 if arc i,j is on any critical path, \par i.e., both i and j are on path and (i,j) is shortest path \par from i to j. Note, we do not assume distances satisfy \par triangle inequality;\cf2 \par \cf1 @FOR\cf2 ( ROADS(i,j): RONPATH(I,J) = \par \cf1 @SMIN\cf2 ( CONPATH(i), CONPATH(j))*((F(i)-F( j)) #EQ# D(i,j)); \par ); \par \cf1 END\cf2 \par } ì‹{\rtf1\ansi\ansicpg1252\deff0\deflang1033{\fonttbl{\f0\fnil\fcharset0 Courier New;}} {\colortbl ;\red0\green0\blue255;\red0\green0\blue0;\red0\green175\blue0;} \viewkind4\uc1\pard\cf1\f0\fs20 MODEL\cf2 : \par \cf1 SETS\cf2 : \par \cf3 ! Dynamic programming illustration (see Anderson, \par Sweeney & Williams, An Intro to Mgt Science, \par 6th Ed.). We have a network of 10 cities. We \par want to find the length of the shortest route \par from city 1 to city 10.;\cf2 \par \cf3 ! Here is our primitive set of ten cities, where \par F( i) represents the shortest path distance \par from city i to the last city;\cf2 \par CITIES /1..10/: F, CONPATH; \par \cf3 ! The derived set ROADS lists the roads that \par exist between the cities (note: not all city \par pairs are directly linked by a road, and roads \par are assumed to be one way.);\cf2 \par ROADS( CITIES, CITIES)/ \par 1,2 1,3 1,4 \par 2,5 2,6 2,7 \par 3,5 3,6 3,7 \par 4,5 4,6 \par 5,8 5,9 \par 6,8 6,9 \par 7,8 7,9 \par 8,10 9,10/: D, RONPATH; \par \cf3 ! D( i, j) is the distance from city i to j;\cf2 \par \cf1 ENDSETS\cf2 \par \cf1 DATA\cf2 : \par \cf3 ! Here are the distances that correspond to the \par above links;\cf2 \par D = \par 1 5 2 \par 13 12 11 \par 6 10 4 \par 12 14 \par 3 9 \par 6 5 \par 8 10 \par 5 2; \par \cf1 ENDDATA\cf2 \par \cf3 ! If ou are already in last city, then the cost to \par travel to it is 0;\cf2 \par F( \cf1 @SIZE\cf2 ( CITIES)) = 0; \par \cf3 ! The following is the classic dynamic programming \par recursion. In words, the shortest distance from \par City i to last city is the minimum over all \par cities j reachable from i of the sum of the \par distance from i to j plus the minimal distance \par from j to last city;\cf2 \par \cf1 @FOR\cf2 ( CITIES( i)| i #LT# \cf1 @SIZE\cf2 ( CITIES): \par F( i) = \cf1 @MIN\cf2 ( ROADS( i, j): D( i, j) + F( j)); \par ); \par \cf3 ! Set CONPATH( j) > 0 if city j is on any critical path, \par i.e., if going to j from some i on the critical path, \par still allows us to get to last city in optimal time;\cf2 \par CONPATH( 1) = 1; \par \cf1 @FOR\cf2 ( CITIES( j)| j #GT# 1: \par CONPATH( j) = \cf1 @MAX\cf2 ( ROADS( i,j): CONPATH( i)*((F(I)-F( j) #EQ# D(i,j)))); \par ); \par \cf3 ! Set RONPATH(i,j) = 1 if arc i,j is on any critical path, \par i.e., both i and j are on path and (i,j) is shortest path \par from i to j. Note, we do not assume distances satisfy \par triangle inequality;\cf2 \par \cf1 @FOR\cf2 ( ROADS(i,j): RONPATH(I,J) = \par \cf1 @SMIN\cf2 ( CONPATH(i), CONPATH(j))*((F(i)-F( j)) #EQ# D(i,j)); \par ); \par \cf1 END\cf2 \par }