probabilistic dynamic programming

Q3- ( 25 points) Due to increasing population in the city, 4 (four) school buildings must be constructed over the next 3 years. Suppose that the need for the school building is known with certainty and the minimum levels of cumulative need (demand) for the building, which is indicated in the table below, must be satisfied. For example, in order to satisfy the need by the end of year 2023, at least 1 school building should be built. Similarly, at least 4 school building should be built by the end of 2025 . The constructing of school takes approximately one year. For example, if 3 schools are built by the end of 2024 , at least one power plant must be built in early 2025 to meet the demand for 2025. In addition to a cost directly associated with the construction of a building, there is a common cost of $750,000 incurred when any buildings are constructed in any year, independent of the number of buildings constructed. This common cost results from contract preparation and some other common expenses. The cost of construction per building is given in the table above for each year in the planning horizon. In any given year, at most three buildings can be constructed. Currently, we have no school under construction, and by the end of each year in the planning horizon we must have completed a number of school buildings equal to or greater than the cumulative need (demand). Further, it is assumed that there is no need ever to construct more than four school buildings. Use dynamic programming to determine the optimal policy (Hint: about the number of buildings to be constructed at the beginning of each year) that minimizes the total construction cost while satisfying the need (demand) in each year. (a) (5 points) Define the stages, decision variables, and states explicitly. (b) (5 points) Define an appropriate DP recursion and boundary conditions. (c) (15 points) Determine your optimal policy and expected costs if you follow the optimal policy. Show all your calculations