CONTENTS 1.0 Introduction 2.0
Intended Learning Outcomes
3.0 Main Content
3.1Important Terms Used in Dynamic Programming 3.2Dynamic Programming Approach
3.3Formulation and Solution of Dynamic Programming Problems
4.0 Conclusion 5.0 Summary
6.0 Self-Assessment Exercises 7.0 References/Further Reading 1.0 INTRODUCTION
While discussing problems and solutions in previous chapters, we assumed that values of decision variable remain constant over the planning period. These problems could be considered as static and their solution were capable only for specific situation and for a particular period of time. But as we know, there could be many situations in which decision variables will change with time. Such situations are considered dynamic in nature. Dynamic programming techniques help in finding dynamic solution for such problems.
Dynamic programming was originated by Richard E Bellman and G. B. Dantzing in early 1950s. It is a quantitative technique which converts one big/large problem having many decision variables into a sequence of problems each with small number of decisions variables.
Thus, a big problem which is difficult to solve can be converted into a series of small problems, which can be easily solved. It attempts to optimise multi-stage decision variables and uses the word „programming‟ in the mathematical sense of selection of optimal allocation of resources. Also, the word „dynamic‟ is used to indicate that the decisions are taken at a number of stages like daily, weekly etc. Dynamic programming is different from linear programming in the following ways:
It does not involve any mathematical computation as was done in simplex method. It uses a multistage approach by dividing the problem in number of sequential stages.
LP gives a single stage solution. However, dynamic programming helps in finding optimal solution over a period of time, say over a period of six months or one year by breaking the problem into six or twelve months and solving each of them.
2.0 INTENDED LEARNING OUTCOMES
At the end of this unit, you should be able to:
explain the terminologies used in dynamic programming identify the methods of dynamic programming
formulate dynamic programming model
state how to solve dynamic programming problems using branch and bound method.
CIT907 ADVANCED OPERATION RESEARCH
91 3.0 MAIN CONTENT
3.1 Important Terms Used in Dynamic Programming
Stage –when a large problem is developed into various sub-problems in a sequence, these are the stages of the original problem. It is in fact, each point where the decision must be made.
For example, in salesman allocation, a stage may represent a group of cities while in the case of replacement problem each year may represent a stage.
State – specific information describing the problem at different stages with the help of variables. The variables linking two stages are called the state variables. In the salesman allocation and replacement problem, the state is the stage of beginning with a new machine.
Principle of Optimality- Bellman‟s principle of optimally states “an optimal policy (a sequence of decisions) has the property that whatever the initial state and decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision”. According to this principle, a wrong decision (non-optimal) taken at one stage does not mean that optimum decisions for the remaining stages cannot be taken. This can be shown diagrammatically as follows.
Stage Decision Stage Decision Stage Decision where n = stage number
Sn = Input to stage n from stage n + 1 Dn = Decision variable at stage n.
Forward and Backward Recursive approach – it is the type of computation Forward or Backward depending upon whether we proceed from stage 1 to n i.e. S1 → S2 S3 → Sn or from stage Sn to
S1 i.e. Sn → Sn-1 → Sn-2 → S1 .
3.2 Dynamic Programming Approach
Numerical problems and examples can only be discussed after a student has clear understanding of the fundamental concepts of Dynamic Programming. The two most important concepts are the concept of stage. As already stated above, a large problem is broken down into a number of smaller or sub-problems and each sub-problem is referred to as a Stage. Every stage is a part of the decision problem and a separate decision can be taken for each stage. Stage decision is the selection of one feasible solution out of a large number of alternatives available at every stage of the problem. The stage for decision will contribute to the overall decision of the entire problem. The second very important concept is that of the
„State‟ which provides the specific „current status‟ conditions or parameters which may be referred to as „state variables‟.
In the overall decision-making process for the entire problem, a decision made changes the
„state of the problem‟ with the aim of maximising the returns. The next stage of the problem-solving process uses the values of the state variables which are the outcome of the decision of the previous stage.
3.3 Formulations and Solution of Dynamic Programming Problems The following steps are involved in this:
CIT907 ADVANCED OPERATION RESEARCH
92
Step 1 Definition of problem variables, formulation of objective functions in terms of maximisation or minimisation of an objective and list the problem constraints
Step 2 specific definitions of stages of a multi-stage decision problem.
This amounts to finding out different variables and their values for each state and specifying the relationship by which the state is determined at one stage with the state and decisions at the next stage.
Step 3 Developing optimal return function through recursion relationship. Optimal return function at stage 1 is determined as this is slightly different from the general optimal return function for other stages.
Step 4 Constructing tabular representation clearly showing the values and computations at each stage of the solution. The solution may be developed manually or with the help of a suitable computer software depending upon the complexity of the problem.
Step 5 Determining optimal solution. This is done when all stages of the problem have been sequentially solved.
Example 1
(Salesman Employment Smoothening Problem)
A manufacturing company has divided its total target market into three zones. The company’s marketing department has been collecting data regarding the deployment of salesmen and the sales made in each zone. They have realised that the sales are directly dependent upon the number of salesmen in each zone. The data collected by the company is given in the table below. For various reasons, the company has decided to retain only nine salesmen during the next year. The problem is to determine allocation of these salesmen to three different zones so that the totals sales can be maximised.
No of Profits in thousands of Naira Salesmen
Zone 1 Zone 2 Zone 3
0 35 40 45
1 40 50 50
2 45 65 60
3 60 75 70
4 70 85 80
5 80 95 90
6 90 100 100
7 105 105 110
8 100 100 120
9 90 105 100
Solution
In this problem, the solution can be obtained by step process. The problem is to allocate nine salesmen into three marketing zones to maximise total sales and hence profits. In this problem, three stages are the three zones and state variables are the number of salesmen varying from zero to nine. For zone 1, the return corresponding to deployment of different number of salesmen is as follow:
CIT907 ADVANCED OPERATION RESEARCH
93
Zone 1
No of salesmen 0 1 2 3 4 5 6 7 8 9
Sales (in thousands of Rupees) 35 40 45 60 70 80 90 105 100
90
Let us consider zone 1 and zone 2 together. Nine salesmen can be divided into two zones 1 and 2 in 10 different ways. This is shown below:
No of Zone I x1 9 8 7 6 5 4 3 2 1 0
salesme
n Zone x1 0 1 2 3 4 5 6 7 8 9
II f1(x1) 90 100 105 90 80 70 60 45 40 35
Sales (in Zone I
thousands
of Zone f2(x2) 40 50 65 75 85 95 100 10 100 105
rupees) II
Total 130 150 170 165 16
5 165 160 150 140 140 where x1, x2 are the salesmen n zone 1 and Zone 2
respectively and f1 (x1) = sales from zone I f2 (x2) = sales from zone II
Let S = Total sales from each combination Then S = f1 (9) + f2 (0)
= f1 (8) + f2(1)
= f1 (7) + f2(2) :
:
= f1 (0) + f2(9) In general S = f1 (x) + f2(9-x) Or S = f1 (x) + f2(A - x)
where A is the number of salesmen to be allocated to Zone 1 and Zone 2 Maximise S = F (A) [f1 (x) + f2(A - x)]
F (A) is the maximum sales
This equation can be used to determine the optimum distribution of any number of salesmen.
In the present case of nine salesmen, the distribution in zone 1 and zone 2 is shown below.
Expected sales for all combination are provided in the table. For a particular number of allocation of salesmen, the sales can be read along the diagonal. For example if three salesmen are to be distributed in the two zones the possible sales when in combination are 3+ 0, 2 + 1, 1 + 2, 0 + 3 and can be read along diagonal 3 – 3. Maximum profit of N10,000 results from combination of 0 salesmen for zone 1 and three for zone 2.
CIT907 ADVANCED OPERATION RESEARCH
94
The optimum results for all combinations can be tabulated as follow.
Maximum sales from optimum allocation of salesmen in Zone 1 and Zone 2
No of Salesmen 0 1 2 3 4 5 6 7 8 9
A
Total sales 75 85 140 110 120 130 135 145 155 170 f1 (x1) +f2(x2)
(x2 + x1) 0 + 0 0 + 1 0 + 2 0 + 3 0 + 3 0 + 5 1 + 5 3 + 4 Now, we can move to the next stage and nine salesmen can be allotted to three zones: Zone 1, Zone 2 and Zone 3. It means allotting certain salesmen to zone 3 and the balance would be allotted to Zone 1 and Zone 2 put together and then further they will be distributed between Zone 1 and Zone 2. For example, if we allot four salesmen to Zone 1 and 2 and five to Zone 3, then the best sales would be
S = F(4) + f3(5)
where F(4) – Maximum sales by Zone 1 and Zone 2 F(5) – Maximum sales in Zone 3
If salesmen are allotted. in general, it can be written as S = F(x) +f3 (A – x)
where x = Salesmen allotted to Zone 1 and Zone 2 combined (A – x) = Salesmen allotted to Zone 3.
i.e. Maximise S = F(A) = F(x) + f3 9A –x)] , 0 < x < A
Let us use the subscript II for the first two zones i.e. Z1 and Z2 then F3 (A3) = Maximum [FII (AII) + f3 (A3 – AII)], 0 < x < A3
The calculations for selecting the optimum combination of AII and (A3 – AII) with A3 = 9 can be carried out the same way as was done earlier. It can be seen that optimum combination is along diagonal 9 – 9 i.e. seven salesmen in Zone 3 and two combined with Zone 1 and Zone 2.
This gives maximum sales of # 250,000. Further distribution of two salesmen in Zone 1 and Zone 2 can be seen from our earlier table i.e. maximum sale of 140,000 for two salesmen, one in Zone 2 and one in Zone 1.
4.0 CONCLUSION
This unit focused on stage, state and principle of optimality (forward and backward recursive approach). The dynamic programming approach, formulation and solution of dynamic programming problems were also discussed.
5.0 SUMMARY
This unit focused on stage, state and principle of optimality (forward and backward recursive approach). The dynamic programming approach, formulation and solution of dynamic programming problems were also discussed.
6.0 SELF-ASSESSMENT EXERCISES
Explain the important terms in dynamic programming that you have learnt.
State and explain the steps that are involved in the formulation and solution of dynamic programming.
CIT907 ADVANCED OPERATION RESEARCH
95 7.0 REFERENCES/FURTHER READING
Asoke Kumar Bhunia, Laxminarayan Sahoo, Ali Akbar Shaikh (2019), Advanced Optimization and Operations Research, Springer Optimization and Its Applications, 153 https://doi.org/10.1007/978-32-9967-2_1
Merigó, José M; Yang, Jian-Bo (2017). "A bibliometric analysis of operations research and management science". Omega - International Journal of Management Science. 73: 37–48.
doi:10.1016/j.omega.2016.12.004. ISSN 0305-0483
Frederick S. Hillier & Gerald J. Lieberman (2014), Introduction to Operations Research, McGraw-Hill: Boston MA; 10th Edition
The Institute for Operations Research and the Management Sciences (INFORMS), https://www.informs.org/
Taha, Hamdy A. (2016), "Operations Research: An Introduction", Pearson, 10th Edition Saul I. Gass, Arjang A. Assad, An Annotated Timeline of Operations Research: An Informal History. New York, Kluwer Academic Publishers, 2005.
International Federation of Operational Research Societies https://www.ifors.org/
Saul I. Gass (Editor), Arjang A. Assad (2011), Profiles in Operations Research: Pioneers and Innovators. Springer
.