 |
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. |
Enumeration |
| |
|
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. |
| |
|
Transitions |
| |
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. |
|
Summary |
| |
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. |
| |
|
