Path Optimization and Resource Allocation with Dynamic Programming

This assignment demonstrates the application of dynamic programming to solve optimization problems. It includes finding the longest path in a graph using graphical techniques and backward recursion, allocating study time to maximize grade points using the 0/1 Knapsack problem, and determining the shortest path through a network of cities. The solutions detail the steps involved in each dynamic programming approach, including defining recursive formulas, identifying states and decision variables, and constructing optimal paths or resource allocations. The assignment utilizes dynamic programming principles to break down complex problems into smaller subproblems, ensuring efficient and optimal solutions. Desklib offers more solved assignments and study resources for students seeking to enhance their understanding of dynamic programming and related topics.

Dynamic math
Student Name
Institution
Submission Date

1.
a. The task is to use graphical techniques to obtain the longest path from 1 to 10.
Starting from node 10
In one step
9 10
In 2 steps
8 9 10
In 3 steps
5 8 9 10
In 4 steps
3 5 8 9 10
In 5 steps
1 3 5 8 9 10
In conclusion the longest path will be obtained by moving from node 1 to 3 to 5
to 9 and finally to 10. This gives a distance of 20.
b. Backward recursion uses the principle of optimality which states that ” No matter
in what state of stage one may be, in order for a policy to be optimal, one must
proceed from that state and stage in an optimal manner sing the stage
transformation equation” (Kumar).
In this case the recursive formula will be for the elements
4, 6, 2,2, 6
Which is
f ( n ) =an−1+2
The state is the presence situation of the problem in our case node 10. The
decision variable is which action should be taken that is in line with the
optimality principle.
The system works by using the recursive equation to make transformations from
one state to the other.

2. Dynamic programming is a paradigm of algorithm that functions by breaking a
complex situation into sub-problems and stores the outcomes in order to avoid
repetitive computations.
Being that a course can either be picked or not picked in a given day will apply the
0/1 Knapsack problem dynamic programming in designing our solution.
Total weight is 7
The points raised by course allocation using the 0/1 knapsack problem dynamic
programming.
Days 0 1 2 3 4 5 6 7
Course
1 0 3 5 6 7 7 7 7
2 0 5 8 10 11 12 12 12
3 0 5 10 13 15 16 17 17
4 0 6 11 14 17 19 21 21
Total maximum points is obtained as 21.
This value comes from the 4th row hence course 4 will be selected for 3 days which
gives 9 points. We are thereby left with 21−9=12points. Course 3 will be selected
for 1 days having 2 points, course 2 will be selected for 1 day having 5 points. This
gives a remainder of 5 points which are allocated to course 1 for 2 days. In
conclusion, to allocate the study time in way that maximizes the obtained total grade
points, the students need to do the allocation as follows
Course Days Point
4 3 9
3 1 2
2 1 5
1 2 5
With this the student will have maximized the 7 days available for studies.

3. Our objective is t0 make use of dynamic programing to develop a path that starts
and ends at city 1 by going through cities 2,3,4 and 5 just once. To develop our
dynamic programing technique, we first create the graph using the given
information.
This gives
6
10
8 7
4 5 6
9
9
4
Now we can subdivide the problem and design a step by step solution by use of recursion.
First let’s begin at city 1 we need to move to either city 2,3,4 and 5. The shortest path is to go to city
3 with a distance 4.
From city 3 now we need to move to cities 2,4 and 5. Here the shortest path is to go to city 2 with a
distance 6.
Being at city 2 we now need to move to either city 4 or 5, the shortest path is to move to city 4 with
a distance 7. From 4 will only have a single option of moving to city 5 at a distance of 4.
Thereafter we return from 5 to 1 at a distance 9.
In conclusion the shortest path from city 1 to cities 2,3,4 and 5 then back is
4 6 7 4 9
4
1
2
3
4
5
1 3 2 4 5 1

This gives a total distance of 4 +6+7 +4 +9=30
References
Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control. Athena Scientific.
Kumar, N. (n.d.). Dynamic Programming. M5L2.
Meyn, S. (2007). Control Techniques for Complex Networks. Cambridge University Press.