Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    DP 2

    Uploaded by

    Hrijul chauhan

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    DP 2

    Uploaded by

    Hrijul chauhan
    9 views22 pages

    Original Title

    DP_2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    9 views22 pages

    DP 2

    Uploaded by

    Hrijul chauhan

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 22

    DYNAMIC PROGRAMMING

    Contents

    • Stage Coach Problem solution - Backward Recursive Approach


    • Terminology
    • Reliability Problem
    Stage Coach Problem

    • A person wants to go from city 1 to city 10. the various


    possibilities and the distances are given in the following table.
    Arc Distance Arc Distance Arc Distance Arc Distance

    1-2 5 2-7 8 4-6 5 6-9 7

    1-3 5 3-5 8 4-7 7 7-8 5

    1-4 6 3-6 10 5-8 6 7-9 7

    2-5 4 3-7 5 5-9 8 8-10 8

    2-6 7 4-5 4 6-8 9 9-10 9


    Stage Coach Problem

    4
    2 6
    7 5
    8
    8
    5 8
    8 8
    5 10 9
    1 3 6 10
    5 7
    6 9 9
    4 5
    5
    4 7 7
    7

    Shorted path from node 1 to node 10


    Backward Recursive Approach

    ✔ n=1: One more stage to go

    s X1 f1*(s) X1*

    8 10 8 10

    9 10 9 10
    Backward Recursive Approach
    ✔ n=2: Two more stage to go
    s X2 f2*(s) X2*
    8 9
    5 6+8 8+9 14 8
    =14 =17
    6 9+8 7+9 16 9
    =17 =16

    7 5+8 7+9 13 8
    =13 =16

    Corresponding
    Backward Recursive Approach
    ✔ n=3: Three more stage to go
    s X3 f3*(s) X3*
    5 6 7
    2 4+14 16+7 8+13 18 5
    =18 =23 =21
    3 8+14 10+16 5+13 18 7
    =22 =26 =18

    4 4+14 5+16 7+13 18 5


    =18 =21 =20

    Corresponding
    Backward Recursive Approach
    ✔ n=4: Four more stage to go

    s X4 f4*(s) X4*
    2 3 4
    1 5+18 5+18 6+18 23 2, 3
    =23 =23 =24

    Corresponding
    Final solution

    • 1-2-5-8-10
    • 1-3-7-8-10
    • Z=23.
    Terminology

    • Stage (n to go) – Stage


    • State (s)- city from which the person is traveling
    • Decision variables (X)- next destination
    • Criterion of effectiveness (f(s,X))- Minimize total distance
    Reliability Problem

    • Let us consider an equipment that function using four


    components, A, B, C and D which are connected in series.
    • Each component has a certain reliability and the reliability
    of the equipment is the product of the individual reliability.
    • In order to increase the reliability of the equipment, we can
    have some additional components in standby and the
    reliabilities and cost for standby units for the four
    components are shown in the Table.
    Reliability Problem
    ✔ Total available budget = 400 THB
    No. of A B C D
    units

    Reliab Cost Reliab Cost Reliab Cost Reliab Cost


    ility ility ility ility

    1 0.60 100 0.70 80 0.70 75 0.80 60

    2 0.70 130 0.75 100 0.80 80 0.85 70

    3 0.80 150 0.80 120 0.90 85 0.88 75

    4 0.90 170 0.85 140 0.95 90 0.90 80


    Reliability Problem

    A B C D
    Terminology

    • Stage (n to go) – Component


    • State (s)- amount of money available
    • Decision variables (X)- How many units of each component
    • Criterion of effectiveness (f(s,X))- Maximize Reliability
    Backward Recursive Approach
    ✔ n=1: One more stage to go
    s X4 f1*(s) X4*
    60-70 1 0.8 1

    70-74 2 0.85 2

    75-79 3 0.88 3

    80-145 4 0.90 4

    Corresponding value
    ✔ n=2: Two more stage to go
    s X3 f2*(s) X3*
    1 2 3 4
    135-139 0.7X0.8 -- -- -- 0.56 1
    =0.56
    140-144 0.7X0.8 0.8X0.8 -- -- 0.64 2
    =0.56 =0.64
    145-149 0.7X0.85 0.8X0.8 0.9X0.8 -- 0.72 3
    =0.595 =0.64 =0.72
    150-154 0.7X0.88 0.8X0.85 0.9X0.8 0.95X0.8 0.76 4
    =0.616 =0.68 =0.72 =0.76
    155-159 0.7X0.9 0.8X0.88 0.9X0.85 0.95X0.8 0.765 3
    =0.63 =0.704 =0.765 =0.76
    160-164 0.7X0.9 0.8X0.9 0.9X0.88 0.95X0.85 0.8075 4
    =0.63 =0.72 =0.792 =0.8075
    165-169 0.7X0.9 0.8X0.9 0.9X0.9 0.95X0.88 0.836 4
    =0.63 =0.72 =0.81 =0.836
    170-220 0.7X0.9 0.8X0.9 0.9X0.9 0.95X0.9 0.855 4
    =0.63 =0.72 =0.81 =0.855
    Recursive relation
    ✔ n=2: Two more stage to go

    Corresponding value
    ✔ n=3: Two more stage to go

    s X2 f3*(s) X2*
    1 2 3 4
    215-219 0.7X0.56 -- -- -- 0.392 1
    =0.392
    220-224 0.7X0.64 -- -- -- 0.448 1
    =0.448
    225-229 0.7X0.72 -- -- -- 0.504 1
    =0.504
    230-234 0.7X0.76 -- -- -- 0.532 1
    =0.532
    235-239 0.7X0.765 0.75X0.56 -- -- 0.5355 1
    =0.5355 =0.42
    240-244 0.7X0.8075 0.75X0.64 -- -- 0.56525 1
    =0.56525 =0.48

    245-249 0.7X0.836 0.75X0.72 -- -- 0.5852 1


    =0.5852 =0.54
    250-254 0.7X0.855 0.75X0.76 -- -- 0.5985 1
    =0.5985 =0.57
    s X2 f3*(s) X2*
    1 2 3 4
    255-259 0.7X0.855 0.75X0.765 0.8X0.56 -- 0.5985 1
    =0.5985 =0.57375 =0.448
    260-264 0.7X0.855 0.75X0.8075 0.8X0.64 -- 0.605625 2
    =0.5985 =0.605625 =0.512
    265-269 0.7X0.855 0.75X0.836 0.8X0.72 -- 0.627 2
    =0.5985 =0.627 =0.576
    270-274 0.7X0.855 0.75X0.855 0.8X0.76 -- 0.64125 2
    =0.5985 =0.64125 =0.608
    275-279 0.7X0.855 0.75X0.855 0.8X0.765 0.85X0.56 0.64125 2
    =0.5985 =0.64125 =0.6120 =0.476
    280-284 0.7X0.855 0.75X0.855 0.8X0.8075 0.85X0.64 0.646 3
    =0.5985 =0.64125 =0.646 =0.544

    285-289 0.7X0.855 0.75X0.855 0.8X0.836 0.85X0.72 0.6688 3


    =0.5985 =0.64125 =0.6688 =0.612
    290-294 0.7X0.855 0.75X0.855 0.8X0.855 0.85X0.76 0.684 3
    =0.5985 =0.64125 =0.684 =0.646
    295-299 0.7X0.855 0.75X0.855 0.8X0.855 0.85X0.765 0.684 3
    =0.5985 =0.64125 =0.684 =0.65025
    Recursive relation
    ✔ n=3: Three more stage to go

    Corresponding value
    Backward Recursive Approach
    ✔ n=4: Four more stage to go
    s X1 f4*(s) X1*
    1 2 3 4

    400 0.6X0.686375 0.7X0.64125 0.8X0.5985 0.9X0.532 0.4788 3&4


    =0.411825 =0.448875 =0.4788 =0.4788

    Corresponding value
    Final solution
    • Solution 1:

    • Solution 2:

    You might also like