Dynamic Programming

Views:
 
Category: Entertainment
     
 

Presentation Description

about dynamic programming

Comments

Presentation Transcript

Dynamic Programming:

Dynamic Programming Dr Neeraj Kaushik TIT&S Bhiwani

Dynamic Programming:

Dynamic Programming: Dr Neeraj Kaushik, TIT&S Bhiwani Dynamic Programming Dynamic Programming is used when the problem can be solved in stages. DP approach uses the idea of recursion to solve a complex problem, broken into a series of interrelated (Sequential) decision stages (sub-problems) where the outcome of a decision at one stage affects the decision at each of the next stages. Backward recursive approach is used where decisions are made from end stages.

Examples:

Examples Inventory control Evaluation of investment opportunities Long term corporate planning DP differed from LPP in two ways: In DP, there’s no set procedure (Algorithm) as in LP to solve any decision problems. LP approach provides one time period (Single stage) solution to a problem whereas DP approach is useful for decision making over time and solves each sub problem optimally. Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

DP Terminology:

DP Terminology Stage The DP problem can be decomposed or divided into a sequence of smaller sub-problems called stages. At each stage there’re number of decision alternatives (courses of action) and a decision is made by selecting the most suitable alternative. State Each stage in DPP has certain number of states associated with it. These states represents various conditions of the decision process at a stage. The variables which describe the status of the system at a particular stage are called state variables. Generally constraints formulate state Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

DP Terminology:

DP Terminology Decision Variable Same as that of LPP Criterion of Effectiveness (Objective function) Minimization or Maximization Policy A particular sequence of alternatives (course of action) adopted by the decision maker in a multi stage decision problem is called a policy. The optimal policy, therefore, is the sequence of alternatives that achieves the decision maker’s objective. Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

DP Terminology:

DP Terminology The solution of DPP is based on Bellman’s principle of optimality (recursive optimization technique) which states: The optimal policy must be one such that, regardless of how a particular state is reached, all later decisions (choices) proceeding from that state must be optimal. Based on this principle of optimality, we find the best policy by solving one stage at a time and then sequentially adding a series of one –stage problems that are solved until the overall optimum of the initial problem is obtained. Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

Shortest Route Problem:

Shortest Route Problem Arc Distance Arc Distance Arc Distance Arc Distance A-B 5 B-G 8 D-F 5 F-I 7 A-C 5 C-E 8 D-G 7 G-H 5 A-D 6 C-F 10 E-H 6 G-I 7 B-E 4 C-G 5 E-I 8 H-J 8 B-F 7 D-E 4 F-H 9 I-J 9 Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani A salesman located in city A decided to city J. he knew the distances of the alternative routes from city A to city J. the salesman’s problem is to find the shortest route.

Shortest Route Problem:

Shortest Route Problem Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani A B C D E F G H I J 5 5 6 4 7 8 8 10 5 4 5 7 8 6 9 7 5 7 8 9

Shortest Route Problem:

Shortest Route Problem Stage Stage State City where the person is located i.e. from where the decision is to be taken Decision Variable Where to go next? Criterion of effectiveness Minimization total costs Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

Shortest Route Problem:

N=1 One more stage to go Now if the person is in city E, he has to decide whether to go either d 2 =H or d 2 =I. for this hw must evaluate d E,H +f 1 * (H)=6+8=14 d E,I +f 1 * (I)=8+9=17 f 2 (s 2 )= Min{14,17} = 14 Shortest Route Problem f 1 (s 1 , d 1 ) Min Distance Optimal Decision States J f 1 * (s 1 ) D 1 H 8 8 J I 9 9 J Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

Shortest Route Problem:

Shortest Route Problem f 2 (s 2 ,d 2 )=d s2,d2 + f 1 * (d 2 ) Min Distance Optimal Decision States H I f 2 * (s 2 ) D 1 E 6+8=14 8+9=17 14 H F 9+8=17 7+9=16 16 I G 5+8=13 7+9=16 13 H Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani N=2 Two more stages to go

Shortest Route Problem:

Shortest Route Problem f 3 (s 3 ,d 3 )=d s2,d2 + f 2 (d 3 ) Min Distance Optimal Decision States E F G f 3 * (s 3 ) D 1 B 4+14=18 8+16=24 4+13=17 18 E C 7+14=21 10+16=26 5+13=18 18 G D 8+14=22 5+16=21 7+13=20 20 G Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani N=3 Three more stages to go

Shortest Route Problem:

Shortest Route Problem f 4 (s 4 ,d 4 )=d s2,d2 + f 3 * (d 4 ) Min Distance Optimal Decision States B C D f 4 * (s 4 ) D 1 A 5+18=23 5+18=23 6+20=26 23 B or C Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani N=4 Four more stages to go Final Route A-B-E-H-J with minimum distance=23 A-C-G-H-J with minimum distance=23

Reliability Problem:

Reliability Problem An electronic device consists of four components each of which must function for the system to function. The system reliability can be improved by installing parallel units in one or more components. The reliability of components, R with one, two or three parallel units and the corresponding cost, C are given in the table. The maximum amount available for this device is Rs 100. The problem is to determine the number of parallel units in each component. Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

Reliability Problem:

Reliability Problem No. of parallel units Components 1 2 3 4 R C R C R C R C 1 0.7 10 0.5 20 0.7 10 0.6 20 2 0.8 20 0.7 40 0.9 30 0.7 30 3 0.9 30 0.8 50 0.95 40 0.9 40 Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani 1 2 3 4

Reliability Problem:

Reliability Problem Let R 1 , R 2 , R 3 & R 4 be the reliability of components Let u 1 , u 2 , u 3 & u 4 be the number of units in parallel in components Let c 1 , c 2 , c 3 & c 4 be the cost of components Maximize Z=R 1 u 1 +R 2 u 2 +R 3 u 3 +R 4 u 4 Subject to constraints: c 1 u 1 +c 2 u 2 +c 3 u 3 +………+c n u n <= C (Total capital available) Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

Reliability Problem:

Reliability Problem The electronic device in this problem will consist of at least one unit in each component. Thus the range of investment x 1 , x 2 , x 3 , x 4 in each case will be as follows: 10<= x 1 <=50 30<= x 1 <=70 40<= x 1 <=80 60<= x 1 <=100 Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani

Reliability Problem:

Reliability Problem States x 1 f 1 (x 1 )=R 1 u 1 Optimal Return f 1 * (x 1 ) Optimal Decision U 1 * U 1 =1 U 1 =2 U 1 =3 R=0.7 C=10 R=0.8 C=20 R=0.9 C=30 10 0.7 - - 0.7 1 20 0.7 0.8 - 0.8 2 30 0.7 0.8 0.9 0.9 3 40 0.7 0.8 0.9 0.9 3 50 0.7 0.8 0.9 0.9 3 Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani n=1 One more stage to go

Reliability Problem:

Reliability Problem States x 2 f 2 (x 2 )=R 2 u 2 * f 1 (x 2 -c 2 x 2 ) Optimal Return f 1 * (x 1 ) Optimal Decision U 1 * U 2 =1 U 2 =2 U 2 =3 R=0.5 C=20 R=0.7 C=40 R=0.8 C=50 30 0.5*0.7 - - 0.35 1 40 0.5*0.8 - - 0.40 1 50 0.5*0.8 0.7*0.7 - 0.49 2 60 0.5*0.9 0.7*0.8 0.8*0.7 0.56 2,3 70 0.5*0.9 0.7*0.8 0.8*0.8 0.64 3 Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani n=2 Two more stages to go

Reliability Problem:

Reliability Problem States x 3 f 2 (x 2 )=R 2 u 2 * f 1 (x 2 -c 2 x 2 ) Optimal Return f 1 * (x 1 ) Optimal Decision U 1 * U 2 =1 U 2 =2 U 2 =3 R=0.7 C=10 R=0.9 C=30 R=0.95 C=40 40 0.7*0.35 - - 0.245 1 50 0.7*0.40 - - 0.280 1 60 0.7*0.49 0.9*0.35 - 0.343 1 70 0.7*0.56 0.9*0.40 0.95*0.35 0.392 1 80 0.7*0.64 0.9*0.49 0.95*0.40 0.448 1 Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani n=3 Three more stages to go

Reliability Problem:

Reliability Problem States X 4 f 2 (x 2 )=R 2 u 2 * f 1 (x 2 -c 2 x 2 ) Optimal Return f 1 * (x 1 ) Optimal Decision U 1 * U 4 =1 U 4 =2 U 4 =3 R=0.6 C=20 R=0.7 C=30 R=0.9 C=40 60 0.6*0.245 - - 0.245 1 70 0.6*0.28 0.7*0.245 - 0.280 1 80 0.6*0.343 0.7*0.280 0.9*0.245 0.343 1 90 0.6*0.392 0.7*0.343 0.9*0.28 0.392 1 100 0.6*0.448 0.7*0.392 0.9*0.343 0.448 1 Dynamic Programming : Dr Neeraj Kaushik, TIT&S Bhiwani n=4 Four more stages to go

Presentation by::

Presentation by: Dr. Neeraj Kaushik Associate Professor (Management Studies) The Technological Institute of Textile & Sciences Birla Colony Bhiwani-ABG0BA Haryana kaushikneeraj@gmail.com Website: http://titsbhiwani.ac.in