动态规划算法代写

OPERATIONAL RESEARCH AND SYSTEMS ANALYSIS COURSEWORK
This coursework is due on Thursday 6th December 2018

Sustainable Reservoir Operation (56%)
The operation of a reservoir is the problem of finding an optimal sequence of controlled releases (r) which minimise the cost of the operation, given information (either deterministic or probabilistic) about the sequence of inflows (i), .

Let:
z be the storage at the beginning of period t,
r be the volume of water released to meet demand over that period
s be the spill, i.e. the volume of water sent through the spillway
with the following conditions:
– the release and inflow of water are contemporaneous);
– the spillway is only used when there is overflow from a full reservoir.

The costs are a function of these three variables: NC(z,r,s). They are operational and maintenance costs, plus the result of losses made on the potential use of the reservoir water for lake recreation, hydropower and the various species of wildlife and their habitats. It is estimated that the optimal level of reservoir contents for these activities is 20 volume units. The optimal volume of water which the reservoir should contribute to meeting local demand is 25 volume units per season (whereby the year is divided into 3 seasons). As a result, the cost function is approximately given by the following equation:

NC(z,r,s) = [(20-z)+(25-r)+s]

This function is the objective function to be considered here.

The reservoir has a capacity K=30 volume units. Its spillway can evacuate up to 20 volume units. The values of r which are technically feasible are 0, 10, 20, 30 or 40 volume units. The volume of stored water, z, is assumed to be a multiple of 10. The answers to the questions below should include easily usable guidance for a reservoir operator, while also clearly specifying the components of the Dynamic Programme framework that is used.

A

(1) Assuming that the inflows i for the three seasons are now always to be equal to 10, 50 and 30 volume units respectively, use Dynamic Programming to determine a sustainable optimal release policy over the year (indicating the annual cost of the operation).

(2) Assuming now that the inflows i for the first two seasons are assumed always to be equal to 10 and 50 volume units respectively, while the flow in the third season is known through its probability distribution only:

use Dynamic Programming to determine a sustainable optimal release policy (indicating the mean annual cost of the operation).

Warehouse Management (44%)
A warehouse stores cranes for the local construction industry. The demand for cranes in month t is described by the following distribution:
    

The warehouse can store up to 3 cranes every month. The policy adopted by the warehouse is to order 2 new cranes from the supplier when there are fewer than 2 cranes in stock (i.e. only 0 or 1 crane) at the end of the month.
There are costs attached to this operation. For every crane in the warehouse, there is a cost (security, maintenance, …) of 10 financial units for each month it spends in the warehouse. If demand for a particular month exceeds availability, the warehouse incurs a cost that is estimated to be 1000 financial units (damage to reputation, loss of market share, …).

(1) Define the states of the stochastic process representing the number Z of cranes in stock at the end of month t. Show that {Z} is a Markov chain and calculate its probability transition matrix.

(2) Find the steady-state probabilities of this chain if there are any, and the mean monthly cost of the operation.

Inflow











Probability

0.2

0.25

0.4

0.10

0.05

B

Assume now that the company which supplies cranes to the warehouse is not always able to provide 2 cranes. In fact, with probability , it can supply 2 cranes, and with probability   , it can supply 1 crane only.

(3) What is the new probability transition matrix?

(4) Find the steady-state probabilities (if there are any) of the chain as a function of .

Currently, the supplier is performing poorly, with  = 0.19. The warehouse is considering whether it is worth investing 1 financial unit (on a monthly basis) to alter its operation, so as to use another supplier who would appear to be more reliable.

(5) How reliable must that supplier be (i.e. what must its value of  be) for the monthly investment of 1 financial unit to be worthwhile?