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


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 files which encode the dynamic programming task under consideration and correspondingly two output files. One output file will give the individual steps involved in the computation and the second file 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 final 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 find the shortest route through a network. The programme should be initialised to find 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 flexible 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. and

(2) The input files, 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 files which gives the relevant information of number of stages, and all other relevant information.

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

(4) Two output files 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 file which gives any extra information as to how to run your program, how to alter the input, and interpret the log file and solution files, 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 flexible 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 file and 4 marks (2 each) for the correct answer.