DYNAMIC PROGRAMMING:PROBABILISTIC DYNAMIC PROGRAMMING

By -

PROBABILISTIC DYNAMIC PROGRAMMING

Probabilistic dynamic programming differs from deterministic dynamic programming in that the state at the next stage is not completely determined by the state and policy decision at the current stage. Rather, there is a probability distribution for what the next state will be. However, this probability distribution still is completely determined by the state

INTRODUCTION TO OPERATIONS RESEARCH-0083

and policy decision at the current stage. The resulting basic structure for probabilistic dynamic programming is described diagrammatically in Fig. 11.10.

For the purposes of this diagram, we let S denote the number of possible states at stage n + 1 and label these states on the right side as 1, 2, . . . , S. The system goes to state i with probability pi (i = 1, 2, . . . , S) given state sn and decision xn at stage n. If the system goes to state i, Ci is the contribution of stage n to the objective function.

When Fig. 11.10 is expanded to include all the possible states and decisions at all the

stages, it is sometimes referred to as a decision tree. If the decision tree is not too large, it provides a useful way of summarizing the various possibilities.

Because of the probabilistic structure, the relationship between fn(sn, xn) and the f *n+1(sn+1) necessarily is somewhat more complicated than that for deterministic dy- namic programming. The precise form of this relationship will depend upon the form of the overall objective function.

To illustrate, suppose that the objective is to minimize the expected sum of the con- tributions from the individual stages. In this case, fn(sn, xn) represents the minimum ex- pected sum from stage n onward, given that the state and policy decision at stage n are sn and xn, respectively. Consequently,

INTRODUCTION TO OPERATIONS RESEARCH-0084

EXAMPLE 5 Determining Reject Allowances

The HIT-AND-MISS MANUFACTURING COMPANY has received an order to supply one item of a particular type. However, the customer has specified such stringent quality requirements that the manufacturer may have to produce more than one item to obtain an item that is acceptable. The number of extra items produced in a production run is called the reject allowance. Including a reject allowance is common practice when producing for a custom order, and it seems advisable in this case.

The manufacturer estimates that each item of this type that is produced will be acceptable with probability -- and defective (without possibility for rework) with probability --.

Thus, the number of acceptable items produced in a lot of size L will have a binomial distribution; i.e., the probability of producing no acceptable items in such a lot is (1)L.

Marginal production costs for this product are estimated to be $100 per item (even if defective), and excess items are worthless. In addition, a setup cost of $300 must be in- curred whenever the production process is set up for this product, and a completely new setup at this same cost is required for each subsequent production run if a lengthy in- spection procedure reveals that a completed lot has not yielded an acceptable item. The manufacturer has time to make no more than three production runs. If an acceptable item has not been obtained by the end of the third production run, the cost to the manufacturer in lost sales income and penalty costs will be $1,600.

The objective is to determine the policy regarding the lot size (1 + reject allowance) for the required production run(s) that minimizes total expected cost for the manufacturer.

INTRODUCTION TO OPERATIONS RESEARCH-0085

INTRODUCTION TO OPERATIONS RESEARCH-0086

EXAMPLE 6 Winning in Las Vegas

An enterprising young statistician believes that she has developed a system for winning a popular Las Vegas game. Her colleagues do not believe that her system works, so they have made a large bet with her that if she starts with three chips, she will not have at least five chips after three plays of the game. Each play of the game involves betting any de- sired number of available chips and then either winning or losing this number of chips. The statistician believes that her system will give her a probability of 2 of winning a given play of the game.

Assuming the statistician is correct, we now use dynamic programming to determine her optimal policy regarding how many chips to bet (if any) at each of the three plays of the game. The decision at each play should take into account the results of earlier plays. The objective is to maximize the probability of winning her bet with her colleagues.

Formulation. The dynamic programming formulation for this problem is Stage n = nth play of game (n = 1, 2, 3), xn = number of chips to bet at stage n,

State sn = number of chips in hand to begin stage n.

This definition of the state is chosen because it provides the needed information about the current situation for making an optimal decision on how many chips to bet next.

Because the objective is to maximize the probability that the statistician will win her bet, the objective function to be maximized at each stage must be the probability of fin- ishing the three plays with at least five chips. (Note that the value of ending with more than five chips is just the same as ending with exactly five, since the bet is won either way.) Therefore, fn(sn, xn) = probability of finishing three plays with at least five chips, given that the statistician starts stage n in state sn, makes immediate decision xn, and makes optimal decisions thereafter,

The expression for fn(sn, xn) must reflect the fact that it may still be possible to ac- cumulate five chips eventually even if the statistician should lose the next play. If she loses, the state at the next stage will be sn - xn, and the probability of finishing with at least five chips will then be f *n+1(sn - xn). If she wins the next play instead, the state will become sn + xn, and the corresponding probability will be f *n+1(sn + xn). Because the as- sumed probability of winning a given play is 2, it now follows that

INTRODUCTION TO OPERATIONS RESEARCH-0088INTRODUCTION TO OPERATIONS RESEARCH-0089

This policy gives the statistician a probability of 20 of winning her bet with her colleagues.

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more