Set Output
For all selections in the Show
Detail frame except None, a worksheet
is added with a name like DP1_Details. The prefix
to the word Details is the name of the DP worksheet.
The results printed on the Details
worksheet depends on the button pressed. In all
cases there is a line for each state of the problem.
If one expects the problem to have very many states,
the option should not be used. As we descend the
list of options, more and more output is provided.
The state tree is the structure used to store the
state information by the computer.
Set Interaction
These options affect the information
displayed during a run of the program. Options providing
more information are helpful to the student trying
to discover the DP solution process.
The Demonstration option presents
a dialog at each step of the procedure. The dialog
below shows the initial state of the forward generation
procedure.
After watching the dialog for several
steps, the student may choose to skip to the next
major activity of the algorithm without the detailed
dialog. The Let Go button accomplishes this. For
the case shown, the demonstration would begin again
at the forward generation procedure. Other major
steps in the computation are the recursive procedure
and the recovery procedure.
The buttons at the bottom of the dialog
allow a switch in the interaction option. The Run/Stop
option runs without interruption for a number of
steps equal to the value in the cell at the lower
right (100). When that number is reached the process
displays the demo dialog. In this way the student
can observe the process at a variety of points during
the solution process.
The Run/no stop option allows the
program to run to completion without interruption.
While the program is running the progress strip
at the bottom of the Excel screen shows information
about the solution. The information is updated at
the interval specified as the number of states between
stops.
The Update Screen checkbox
at the bottom of the dialog controls the display
during optimization. If it is not checked, the screen
is not updated during the process until the end.
This is the fast option and should be the choice
for large problems. When the box is checked, the
changes in the state and decision vectors may be
seen as rapidly varying numbers. The number change
too rapidly to be observed, but the result is a
dynamic display that gives the user some idea about
the procedures of the computer program.
The Show Graphics checkbox
causes the solution process to generate a graphical
display as illustrated below. The figure illustrates
the state space for a knapsack problem with a single
constraining resource. The model has two state variables,
and for the example the maximum values are 10 for
both. The strategy used is forward generation and
backward recursion.
The display shows the states as colored
circles: red for initial states, white for intermediate
feasible states, gray for infeasible states, blue
for final states and gold for states along the optimal
path. The states are located on a grid defined for
S1, the first state variable, and S2, the second
state variable. Lines connect the states. Not shown
on the figure are narrow black lines which show
the change of states for a tentative decision. The
red lines show the optimum decision leaving each
state, the heavy black lines show the optimum path.
The graphical display is a useful
tool for learning the DP process. When both the
Demo and graphical options are chosen, each step
is explained with a text dialog and a graphic presentation.
The graphical option is available only for problems
with two state variables. The maximum range for
each variable must be no more than 20.
