|
Three different
data forms are available for the DP Solver add-in. The states,
actions and events are the same for the forms, but the representation
of the transition probabilities and costs change. This page
shows the three forms for the cab problem. The values on the
various lists are for the optimum solution. Although the measure
of effectiveness for the cab problem is profit, the
discussion uses the more general term cost. |
Probability/Cost Matrix |
|
|
This format was
illustrated on the previous page. It has both transition probabilities
and transitions costs entered in the matrix format. The result
is below. Notice that each state/action pair has a row in the
decision matrix, so the number of rows in the two transition
matrices is equal to the number of decisions. The number of
columns in the two matrices is equal to the number of states.
This option is easiest to use for small problems, but not
convenient for very large problems. Also, Excel is limited
by the number of columns on a worksheet. With Excel 2003/2004
worksheets have about 256 columns, so the representation is
limited to about 100 states.
The Next Value and State Probability vectors
each have the number of components equal to the number of states.
It is convenient for computational purposes to have these vectors
located above the transition probability matrix. |
| |
|
Probability/No Cost Matrix Option |
| |
This option deletes the Transition
Cost matrix and replaces it with the Expected Transition
Cost vector in column AD. The solution methods do not
use the individual transition costs, only the expected cost
for each state/action pair. Of course, this requires the user
to compute the expected values outside of the DP Solver add-in.
Considering the number of columns available for Excel 2003/2004,
this option allows about 200 states. |
|
Transition List Option |
| |
This option represents
transition probabilities and costs with lists rather than matrices.
Neither the probability nor cost matrix is used, so the number
of columns Excel allows is no longer a limitation. The decision
list is modified as shown below. Only the state index and action
index are entered by the user. For the current example only the
action for decision 6 is different than the default values. The
decision indicates that the radio alternative is not available
in city B. All the yellow columns contain formulas necessary
for the solution methods. |
|
| |
The Transition List is
placed to the right of the decision list and carries the transition
information. Each decision has one or more rows on this list.
The Event
Index is used to construct the Transition Name.
Each transition occupies a row of this matrix with its cost in
column AP, its probability in column AQ and the state reached
via the transition in column AR. |
|
| |
The information describing
the Next Value and the State Probability are
placed as columns in the state list, rather than above the transition
probability matrix. |
|
| |
For most problems, the
transition format is far more efficient than the matrix format,
because often there are few transitions from each state/action
combination. Since the number of rows for Excel worksheets is
very large, the Transition format allows much larger
problems than the matrix formats.
|
Summary |
| |
All three data formats are available
for Markov Chains and Markov Decision Processes. Only the transition
list option is available for deterministic dynamic programming. |
| |
|
