# Python代写 | Optimization theory and applications assessed assignment 3: dynamic programming

本次代写是关于Python相关的一个Assignment

The objective: the objective of this assessed assignment is to devise a software package in Matlab or Python which will be used to solve dynamic programming (DP) problems. These two packages will have input ﬁles which encode the dynamic programming task under consideration and correspondingly two output ﬁles. One output ﬁle will give the individual steps involved in the computation and the second ﬁle will give the solution found.

Deadline: 1:00 PM on Friday 10th December 2021. This is the Friday of the penultimate week of term. This is the ﬁnal assessment for this unit.

The two dynamic programming tasks to consider are worth 10 marks each. They are as follows:

Task 1: write a dynamic programming package to ﬁnd the shortest route through a network. The programme should be initialised to ﬁnd a solution to a problem of the form of Figure 28, where a network is presented with a number of stages and label links indicating the cost of going from one node to another. The task described there is to go from an node A to the line BC. The relevant dynamic programming method to use is described on page 105 of the course notes and is a Bellman or functional equation. The program should be initialised to solve the problem stated on pages 104 and 105 of the course. However it should be generalizable to solve an arbitrary problem of this form with a number of stages between a node A and line BC, of this form. The number of stages should not exceed 6 and there are two choices (up or down) at each node.

Task 2: write a program to solve the capital budgeting problem as stated on page 106 of the course notes with the Bellman or functional equation as stated on page 107 of the notes. The program should be initialised to solve the problem described in Table 5 at the start of section 5.2 (a capital budgeting problem). As for the shortest route through network problem, however, the program should be general and ﬂexible enough to handle capital budgeting problems of up to four stages and four nodes per stage.

The materials will be uploaded to the assessment pages on Blackboard for this course and will have the following components:

(1) The source code for your DP solvers, e.g. network.py and capbud.py.

(2) The input ﬁles, inputnetwork.txt and inputcapbud.txt which will be initialised to the net-work and capital budgeting problems mentioned in the notes in chapter 5. How to present the relevant information to the program is left up to you, but you include text information in

these input ﬁles which gives the relevant information of number of stages, and all other relevant information.

(3) Output ﬁles called lognetwork.txt and logcapbud.txt for the two DP tasks considered. These log ﬁles should present the internal working steps of the two methods.

(4) Two output ﬁles called solutionnetwork.txt and solutioncapbud.txt which gives the solu-tion, with any extra text clearing indicating the nature of the solution.

(5) A readme.txt ﬁle which gives any extra information as to how to run your program, how to alter the input, and interpret the log ﬁle and solution ﬁles, as appropriate.

For this smaller assessed assignment there is no associated research project.

The mark distribution and assessment of the coursework: Both these subprojects have 10 marks each and the marking schedule is similar (the total for this assignment is then 20 marks). In both cases the marks are as follows: 5/10 for the correct solution of the problems mentioned under shortest route through a network and the capital budgeting problem as described in chapter 5, and 5/10 marks each for the ability to handle a more general problem of these types, with a ﬂexible number of stages and nodes per stage. Of the 10 marks assigned to each subproject, 6 marks (3 each) go with correct execution of the program according to the log ﬁle and 4 marks (2 each) for the correct answer.