Jsun Yui Wong
Abstract:
The first example is to find the shortest distance between P15 and P01:
So path {P15}-{P14}, {P14}-{P10}, {P10}-{P06}, {P06}-{P04}, {P04}-{P01} is an optimal route of shortest distance of 16+3+2+10+9=40.
Using the same procedure as the last three papers, this paper easily solves two dynamic programming networks. The immediately following dynamic programming problem is from Sathyapriva, Swathy,Srivarshini, and Bhavatarini [6, pp. 344-346]. It is essential that one takes a good look of the network (picture) on p. 344 of Sathyapriva et al. [6, p. 344].
stage 1 stage 2 stage3 stage 4 stage 5
{A} {E} {H} {K}
{B}
{X} {C} {F} {I} {L} {Y]
Input output
{D} {G} {J} {M}
Above is a simplified version of their network [6, p. 48] and is for illustration only. Some small changes shown below have been added to the original picture, Sathyapriva et al. [6, p. 344], where much more data is given there than given below; please take a good look]. P01, P02, P03, …, P15 are described in line 351 through line 497. P05, for example, stands for the shortest distance from P05 to the destination point, P15.
stage 1 stage 2 stage3 stage 4 stage 5
15+50 10+40 20+20 20+0
P11 P08 P05 P02
{A} {E} {H} {K}
10+21
P12
{B}
16+24 3+21 2+19 10+9 15+0 0
P15 P13 P09 P06 P03 P01
{X} {C} {F} {I} {L} {Y]
Input output
3+21 2+19 10+9 9+0
P14 P10 P07 P04
{D} {G} {J} {M}
To solve the problem above, the following computer program uses the Principle of Optimality of Dynamic Programming, which is “If a particular node is on the optimal route, then the shortest path from that node to the end is also on the optimal route, “ Anderson, Sweeney, and Williams [1, p. 821].
0 REM DEFDBL A-Z
1 REM DEFINT I, J, K
2 DIM B(99), N(99), A(2002), G(128), J44(222), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J(99), AA(99), HR(32), HHR(32), LHS(44), PLHS(44), LB(22), UB(22), PX(44), PN(22), NN(22)
85 FOR JJJJ = -32000 TO 32000
88 RANDOMIZE JJJJ
351 P01 = 0
355 P02 = 20 + 0
358 P03 = 15 + 0
362 P04 = 9 + 0
369 P05 = 20 + 20
373 P06 = 10 + 9
375 P07 = 10 + 9
389 P08 = 10 + 40
397 P09 = 2 + 19
430 P10 = 2 + 19
432 P11 = 15 + 50
434 P12 = 10 + 21
475 P13 = 3 + 21
489 P14 = 3 + 21
497 P15 = 16 + 24
2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, P10, P11, P12, P13, P14, P15, JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with qbv1000-win [9], and the complete output through JJJJ=-31998 is as follows:
0 20 15 9 40
19 19 50 21 21
65 31 24 24 40
-32000
0 20 15 9 40
19 19 50 21 21
65 31 24 24 40
-31999
0 20 15 9 40
19 19 50 21 21
65 31 24 24 40
-31998
So path {P15}-{P14}, {P14}-{P10}, {P10}-{P06}, {P06}-{P04}, {P04}-{P01} is an optimal route of shortest distance of 16+3+2+10+9=40.
The wall-clock time (NOT cpu time) for producing the output above was 2 seconds (or 1 second) when one counts from “Starting program…”.
Example Two
Abstract:
The second example is to find the shortest distance between P12 and P01:
So path {S}-{B}, {B}-{D}, {D}-{H}, {H}-{P} is an optimal route of shortest distance of 2+5+1+4=12.
The following dynamic programming network is from Ullmann [6, pp. 48-49]. It is essential that one takes a good look of the network (picture) on p. 48 of Ullmann [7, p. 48, Figure 5-3].
{A} {D} {H}
{S} {B} {E} {I} {P}
{C} {F} {J}
{G}
Above is a simplified version of Figure 5.3 of Ullmann [7, p. 48] and is for illustration only. Some small changes shown below have been added to the original Figure 5.3, Ullmann [7, p. 48], where much more data is given there than given here; please take a good look]. P01, P02, P03, …, P12 are described in line 351 through line 434. P05, for example, stands for the shortest distance from P05 to the destination point, P01.
START STAGES FINISH
a b c
1+6 1+4 4+0
P09 P05 P02
{A} {D} {H}
2+10 5+5 2+2 2+0 0
P12 P10 P06 P03 P01
{S} {B} {E} {I} {P}
3+4
2+7 5+2 4+0
P11 P07 P04
{C} {F} {J}
2+4
P08
{G}
The following computer program also uses the Principle of Optimality of Dynamic Programming, which is “If a particular node is on the optimal route, then the shortest path from that node to the end is also on the optimal route, “ Anderson, Sweeney, and Williams [1, p. 821].
0 REM DEFDBL A-Z
1 REM DEFINT I, J, K
2 DIM B(99), N(99), A(2002), G(128), J44(222), H(99), L(99), U(99), X(2002), D(111), P(111), PS(33), J(99), AA(99), HR(32), HHR(32), LHS(44), PLHS(44), LB(22), UB(22), PX(44), PN(22), NN(22)
85 FOR JJJJ = -32000 TO 32000
88 RANDOMIZE JJJJ
351 P01 = 0
355 P02 = 4 + 0
358 P03 = 2 + 0
362 P04 = 4 + 0
369 P05 = 1 + 4
373 P06 = 2 + 2
378 IF RND < .5 THEN P07 = 3 + 4 ELSE P07 = 5 + 2
389 P08 = 2 + 4
397 P09 = 1 + 6
430 P10 = 5 + 5
432 P11 = 2 + 7
434 P12 = 2 + 10
2000 PRINT P01, P02, P03, P04, P05, P06, P07, P08, P09, P10, P11, P12, JJJJ
2222 NEXT JJJJ
This BASIC computer program was run with qbv1000-win [9], and the complete output through JJJJ=-31998 is as follows:
0 4 2 4 5
4 7 6 7 10
9 12 -32000
0 4 2 4 5
4 7 6 7 10
9 12 -31999
0 4 2 4 5
4 7 6 7 10
9 12 -31998
So path {S}-{B}, {B}-{D}, {D}-{H}, {H}-{P} is an optimal route of shortest distance of 2+5+1+4=12.
The wall-clock time (NOT cpu time) for producing the output above was 2 seconds (or 1 second) when one counts from “Starting program…”. The computer system used for the two examples above is the same as that used by the preceding paper.
Acknowledgement
I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.
I would like to acknowledge the help of H. Wong for the two pictures shown above.
References
[1] D.R. Anderson, D. J. Sweeney, I. A. Williams, An introduction to management science: quantitative approaches to decision science, ninth edition, South-Western College Publishing, 2000.
[2] J. G. Ecker, M. Kupferschmid, Introduction to operations research, John Wiley and Sons, Inc., 1988.
[3] F. S. Hillier, G. J. Lieberman, Introduction to operations research, sixth edition, McGraw Hill, Inc.
[4] Paul A. Jensen, Microsolve/Operations Research, Holden-Day, Oakland, California.
[5] Katta G. Murty, Operations research, Prentice –Hall, Inc., 1995.
[6] S. Sathyapriva, S. Swathi, S. Srivarshini, P, Bhavatarini, Dynamic programming in stage coach problem and cargo loading problem, International Journal of Scientific Research in Science and Technology(www.ijsrst.com), January-February-2019: 342-348.
[7] John E. Ullmann, Theory and Problems of Quantitative Methods in Management, SCHAUM’S OUTLINE SERIES IN BUSINESS, McGRAW-HILL BOOK COMPANY, Inc. 1976.
[8] Harvey Wagner, Principles of operations research, second edition, Prentice –Hall, Inc., 1975.
[9] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.
Comments