Eight step procedures: Difference between revisions
| Line 7: | Line 7: | ||
===Methodology=== | ===Methodology=== | ||
To solve a problem using the 8-step procedure, one must | To solve a problem using the 8-step procedure, one must use the following steps: <br /> | ||
<br /> | <br /> | ||
'''Step 1: Specify the stages of the problem''' <br /> | '''Step 1: Specify the stages of the problem''' <br /> | ||
The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable <math>n</math>. <br /> | |||
<br /> | <br /> | ||
'''Step 2: Specify the states for each stage''' <br /> | '''Step 2: Specify the states for each stage''' <br /> | ||
The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. <br /> | |||
<br /> | <br /> | ||
'''Step 3: Specify the allowable actions for each state in each stage''' <br /> | '''Step 3: Specify the allowable actions for each state in each stage''' <br /> | ||
This can be defined as: <br /> | |||
<math> | |||
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \} | |||
</math> <br /> | |||
<br /> | <br /> | ||
'''Step 4: Describe the optimization function using an English-language description.''' <br /> | '''Step 4: Describe the optimization function using an English-language description.''' <br /> | ||
In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> <br /> | |||
<br /> | <br /> | ||
'''Step 5: Define the boundary conditions''' <br /> | '''Step 5: Define the boundary conditions''' <br /> | ||
This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> <br /> | |||
<br /> | <br /> | ||
'''Step 6: Define the recurrence relation''' <br /> | '''Step 6: Define the recurrence relation''' <br /> | ||
During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: <br /> | |||
<math> f^{*}_{n}(s)= \overset{max}{j=0,1,...,min\left \{ a[n],\left \lfloor \frac{s}{w[n]} \right \rfloor \right \}} \left \{ b[n,j]+ f^{*}_{n+1}(s-j*w[n]) \right \} </math> <br /> | |||
<br /> | <br /> | ||
'''Step 7: Compute the optimal value from the bottom-up''' <br /> | '''Step 7: Compute the optimal value from the bottom-up''' <br /> | ||
In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. <br /> | |||
<br /> | <br /> | ||
'''Step 8: Arrive at the optimal solution''' <br /> | '''Step 8: Arrive at the optimal solution''' <br /> | ||
Once the value for <math>f^{*}_{n}(s)</math> is computed, we would look at the optimal decision that corresponds to the table entry for that value. We start with the optimal value for our first <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. <br /> | |||
=Numerical Example= | =Numerical Example= | ||
Revision as of 21:34, 20 November 2020
Author: Eljona Pushaj, Diana Bogdanowich, Stephanie Keomany
Steward: Fengqi You
Introduction
Theory, Methodology, and/or Algorithmic Discussion
Methodology
To solve a problem using the 8-step procedure, one must use the following steps:
Step 1: Specify the stages of the problem
The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable $ n $.
Step 2: Specify the states for each stage
The states of a problem are defined as the knowledge necessary to make a decision, or $ s $. We set $ C $ equal to the maximum value of $ s $.
Step 3: Specify the allowable actions for each state in each stage
This can be defined as:
$ U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \} $
Step 4: Describe the optimization function using an English-language description.
In this sentence, we describe the optimization function for each state, or $ s $, and each stage, or $ n $. This can also be called $ f^{*}_{n}(s) $
Step 5: Define the boundary conditions
This helps create a starting point to finding a solution to the problem. First, we set $ f^{*}_{n+1}(s) = 0 $ for all values of $ s $. Here, we can note that $ s=0,...,C $
Step 6: Define the recurrence relation
During this step, we make an allowable decision involving $ j $ items for the remaining capacity $ s $ for items $ n $. We can write this statement as:
$ f^{*}_{n}(s)= \overset{max}{j=0,1,...,min\left \{ a[n],\left \lfloor \frac{s}{w[n]} \right \rfloor \right \}} \left \{ b[n,j]+ f^{*}_{n+1}(s-j*w[n]) \right \} $
Step 7: Compute the optimal value from the bottom-up
In this step, a table is made containing all $ s $, $ f^{*}_{n}(s) $, and optimal values for all $ n $ variables. This step can be done manually or by using programming.
Step 8: Arrive at the optimal solution
Once the value for $ f^{*}_{n}(s) $ is computed, we would look at the optimal decision that corresponds to the table entry for that value. We start with the optimal value for our first $ n $, calculate our remaining space $ s $, and use that value to arrive at an optimal value for all $ n $.