Return to Index
Operations Research Models and Methods
Computation Section
Subunit Dynamic Programming Data
 - Birth-Death: Markov Chain Model

We illustrate the model for the DTMC version of the birth-death process. The data form has a single red button. The Build Model button calls the DP Models add-in to insert the model worksheet and construct a general model. The DP Data add-in then fills the form to describe the birth-death process. If you are not interested in the modeling process you may proceed by clicking the Transfer to Markov Analysis button. This button calls the Markov Analysis add-in for further analysis. The Transfer to DP Solver button calls the DP Solver add-in. The Markov Analysis add-in has more analysis options that the DP Solver add-in, but the DP Solver add-in can deal with larger problems. Although at first the model form appears to be complex, the user really not be concerned about the form. It is automatically constructed and filed with the necessary formulas by the add-ins.

The complete worksheet is shown below. Generally yellow cells hold formulas that should not be changed and white cells hold parameters that define or limit the model. Cells with a red outline are changed by the DP Data add-in to replace default vales.


States and Events

  The figure below shows the parts of the model defining the states and events associated with this process. We call the State and Event sections in rows 10 through 27 the elements of the model. The VBA code of the DP Data add-in specifies the number of state variables and event variables to include in the model. For this case, there is one state variable indicating the population. The state value is in cell F14. There are two event variables, indicating birth or death events. Note that events have only two values 0 or 1. The Event is represented by the vector consisting of cells K14:L14.

Red outlines identify most of the cells that are filled by the DP Data add-in. Some of the titles that are filled are not outlined in red to make the figure more readable. Others not outlined hold default values. You may be able to identify some of the data items in the model form. For example, cell F19, the maximum state value, holds a formula linking the Max Population cell to the data cell holding that parameter. This makes it easy to experiment with different values.


The summary area in columns O through R indicate whether the State is feasible and whether the event leads to a feasible transition. The current state has 0 population and the current event is a birth. Subsequent components of the model verifies that this is a feasible state and the event results in a feasible transition.




The state definition appears at the left. Cells F18 and F19 hold minimum and maximum values of the state variable. Cells E20 and F20 hold the components of the state name. They are combined in cell G20 to obtain the name of the state, P_10 in this case. Row 21 holds the definition of the state cost function. The function for the state cost is in G21. In this case it is the Excel function:

= E21+F14*F21

Any valid function of the state variable can be entered in cell G21. The model here is that the cost of the state is proportional to the number in the population. The entry in F21 is a formula that links to the holding cost on the data form.

The yellow cells: F14, F15, F16 and E16 hold formulas that are used to enumerate the state set. The index value in E14 determines the value of the state variable. We provide the spinner control in column H to increment or decrement the cell E14. Manual manipulation of E14 is useful for debugging the model. The computer varies the contents of cell E14 to enumerate all feasible states.

A state is feasible if its state variables lie with the range between the minimum and maximum values, and the state satisfies externally supplied feasibility conditions. Cell F17 returns TRUE when the state value is within the limits. Cell E17 holds a user-supplied logical formula evaluates TRUE for all feasible states. Cell G17 is TRUE, and the state is feasible. when both E17 and F17 are TRUE.

The State Subset region below the state definition may further restrict the set of states, however, it is not necessary in this case.

  The figure below shows the results obtained by clicking the List States button. The computer generates the 11 feasible states for this problem. Columns for the names, values and cost are computed. The column labeled Trans. Range points to a row in the decision list that is described later.

The event definition is similar to the state definition except the event vector has two components. The components represent the two events that occur for this model: birth and death. The range 0 to 1 constricts the event variables to be binary. For this example, however, an event is either a birth or a death, but not both. To assert this feasibility condition we add the logical expression in J17.

=(K14 + L14) =1 or =SUM(BD_1_MM_Event)=1

The second form is actually used by the add-in because BD_1_MM_Event is the name for the range (K14:L14). A feasible state lies between the minimum and maximum values such that cell J17 is TRUE. The logical result is in cell M17. This evaluates to TRUE when the sum of K14 through L14 is equal to 1. An event with both a birth and a death in a single time interval is determined as not feasible and the associated transition is not included in the model. Although the event of neither a birth nor death is feasible, we do not require transitions that do not change the state to be explicitly defined.

Rows 20, 21 and 22 determine the name, cost and probability of the event. This information is transferred by formula from the birth-death data worksheet.


The enumeration of all feasible events results in the Event List shown below. There are two feasible events.





The remainder of the model describes transitions. With the system in some state, the occurrence of an event usually causes the state to change. This portion of the model indicates the state/event combinations that might occur with associated cost and probability. Also the model indicates the new state reached when the event occurs. Starting in row 47 the model identifies three possible transitions, the purge transition, the transitions that occur when the system is empty, and the transitions caused by births and deaths. There are several ways to model a situation. The goal is to create a model that is clear and is an efficient in representation for computation.


The transition section of the model has two parts, the transition summary in lines 42 to 46 and several transition blocks. The transition summary holds the current state and event in row 45. These values are transferred from the state and event definitions at the top of the display. The name for the transition, in cell Q33, combines the state and event names. Cell Q44 holds a logical formula which evaluates as TRUE if one of the transition blocks is feasible. When Q44 is true, cell Q45 holds the number of the transition block that defines the remainder of the transition. In the example, the second block is selected.

Each transition block defines a subset of feasible transitions. The first block describes states and events associated with the purge operation. Purging is only possible when the state has the maximum value, so the bounds on the state variable are both equal to 10. The bounds on the event variable indicate that this block is only effective for the birth event. Because the current state does not fall within the bounds, the block is assigned the value FALSE in the feasible cell, Q48.

Transition 2 describes the transitions when the system is empty. The lower and upper limits on the state are both 0 so the current state is feasible for this block. The bounds on the events admit only the birth event. The feasibility for block 2 is indicated in Q58 as TRUE. This indicates that this block describes a feasible transition. The cost in cell Q59 is 5, the cost associated with a birth. And the probability in Q60 is the probability of this event. Cells Q59 and Q60 hold formulas that point to the cost and probability of the event, but these formulas may be changed as required. The next state reached from state 0 with the birth event is computed in cell 65 as the sum of the current state (0) and the contents of C63 (in this case 1). Thus the next state in C65 is 1. Cell D65 indicates the index of this state (2). The index for states is the row number of the state in the State List.

When more than one transition is feasible, the first transition block encountered (considered from top to bottom) is the one chosen for inclusion in the transition set. This is the case for this example, because we see that transition 3 is also feasible. The program picks the first feasible transition, that is transition 2.

The complete transition list is found when the List Elements button at the top of the page is clicked. The VBA program generates all combinations of feasible states and feasible events. The transitions observed are included in the transition list shown below. When the transitions probabilities for a state sum to less than 1, a Null event is defined for the remainder of the probability. The probability for this event is set equal to 1 less than the sum of the other transition probabilities. The cost for the null event is zero and the state does not change due to the null event.

Note that the purge occurs with a birth event when the system is in state 10. The next state is the empty state, P_0. The cost of the purge, in this case -120 is computed in cell Q55, the cost cell for transition block 1.

  The state, event and transition lists are the outputs of the DP Models add-in. This data is sufficient to define the Markov chain. The data for the model is entirely linked to the data in the birth-death table constructed by the DP Data add-in. The casual user of the birth-death model described on this page need not interact with the model form. Every necessary function is performed by one of the add-ins. Changing the data on the table immediately changes the affected cells on the model form.


Markov Chain Analysis

  A DTMC model is created by clicking on the Transfer to Markov Analysis button. Then the Markov Analysis add-in constructs the appropriate Excel worksheets and the DP Models add-in inserts the data defined by the model. The probability transition matrix model for the example is shown below. Note that the state P_0 allows only the birth transition, to P_1, with probability 0.1. The remainder of the probability, 0.9, is assigned to the null event. With the null event the system does not change state.
  The economic transition matrix is also constructed. The purge action occurs in state 10 with the birth event. The system moves from state 10 to state 0 with probability 0.1. The cost of this transition is the fixed purge cost plus the variable cost of purge (100-20*11=-120). The multiplier on the variable is the maximum population plus the birth that triggered the purge. The State Costs shown in column E represent the holding costs in the model. The birth and death costs are shown in the Transition Cost Matrix.
  The Markov Analysis add-in allows several different analysis as indicated by the buttons on the Matrix page. The steady-state probabilities are shown below.




The DP Data add-in constructs a table holding data for the birth-death process. By clicking the Build Model button on the data page, the DP Models add-in constructs the model worksheet and it is filled with the constants and formulas that implement the model. By clicking the Build Matrix Model button, the Markov Analysis add-in builds the probability and economic transition matrices and inserts the values describing the birth-death process. Note that all three add-ins must be installed for all the steps to work.

Click the Transfer to DP Solver button for an alternative analysis method. Since the DP Solver accepts the transition list as a data form, large matrices are not required. The DP Solver can evaluate steady-state probabilities, and compute the associated NPW values.

Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved