introduction to dynamic programming and linear programming

  • Published on
    12-Nov-2014

  • View
    440

  • Download
    7

Embed Size (px)

DESCRIPTION

dynamic programming and linear programming 101

Transcript

<ul><li> 1. introduction to Dynamic programming &amp; Linear programming </li></ul> <p> 2. . Introduction to algorithm 3rd . 3. Dynamic programming (Divide-and-conquer ) , (Divide-and-conquer ) solution , optimization problem 4. . 1. Optimal solution 2. Optimal solution 3. Optimal solution (bottom-up) . 4. optimal solution - - 2 . - station . - station . - station station , station . - station , station . station ? ? 5. station station O(n) . 2 . dynamic programming . 1, 1,1 , 1,1 optimal solution. 1, optimal solution 1,1 optimal solution 1,1 optimal solution 1, optimal solution subproblem . step1 optimal structure 6. . = min(1 [] + 1, 2[] + 2) station . 1[] = 1 + 1,1 ( = 1 ) = min(1[ 1] + 1,, 2[ 1] + 2, + 2,1) ( 2 ) 2[] = 2 + 2,1 ( = 1 ) = min(1[ 1] + 1, + 1,1, 2[ 1] + 2,) ( 2 ) [] + 1 . 1[1] 2 . [] [ 1] [ 1] optimal solution . O(n) . 7. optimal solution 1[1] = 2 + 7 = 9 2[1] = 4 + 8 = 12 1[2] = min( 9 + 9 = 18, 12 + 9 + 2 = 23 ) = 18 2[2] = min( 9 + 2 + 5 = 16, 12 + 5 = 17 ) = 16 , 38 . min() station . , 1 2 1 2- 2 1 . 8. Linear programming . . Linear programming linear programming . linear programming . 9. Introduction to algorithms 3 (, , ) . ( ) 100, 200, 50 . 50, 100, 25 4 , -2 +5 +3 +8 +2 -5 - - +10 +10 - -2 , $1000 . ? 10. linear programming , . linear constraint . -21 + 82 + 03 + 104 50 51 + 22 + 03 + 04 100 31 52 + 103 24 25 linear constraints . objective function linear constraint . , 1 + 2 + 3 + 4 objective function . 11. . feasible solution 1, 2, . optimal solution optimal value feasible solution objective function , objective function optimal value . unbounded ( optimal objective value ) feasible solution optimal function optimal objective value unbounded . infeasible solution 1, 2, . 12. standard form linear problem , . . 1. objective function minimization maximization . . 2. non-negativity constraint . 0 , 1 2 1, 2 non-negativity constraint . 3. linear constraint = . 4. linear constraint . . maximize -1 - 2 - 3 - 4 subject to 21 - 82 - 03 - 104 -50 -51 - 22 - 03 - 04 -100 -31 + 52 - 103 + 24 -25 1, 2, 3, 4 0 linear programming slack form simplex algorithm . 13. slack form simplex algorithm standard form slack form . standard form slack form . maximize = -1 - 2 - 3 - 4 subject to 5 = 50 + 21 - 82 - 03 - 104 6 = 100 - 51 - 22 - 03 - 04 7 = 25 - 31 + 52 - 103 + 24 1, 2, 3, 4, 5, 6, 7 0 . non-negativity constraint . basic variable , 1, 2, 3, 4 non-basic variable . 14. simplex algorithm linear programming . Interior point method linear programming , . 1. linear constraints objective function slack form . 2. optimal solution . 3. objective function z non-basic variable linear constraints . linear constraint . 4. linear constraints objective function . 5. basic solution , z solution . 15. example standard form slack form basic solution non-basic variables 0 solution (1, 2, 3, 4, 5, 6) = (0, 0, 0, 30, 24, 36) z 0. z non-basic variable . 1 linear constraints non-negativity 1 (30, 12, 9) . tight 9 1 . 16. . basic solution (1, 2, 3, 4, 5, 6) = (9, 0, 0, 30, 24, 0) z 27. z non-basic variable . 3 linear constraints non-negativity 3 (18, 3/2, 42/5) . tight 3/2 3 . 17. basic solution (1, 2, 3, 4, 5, 6) = (44/3, 0, 3/2, 69/4, 0, 0) z 111/4. z non-basic variable . 2 2 tightest constraint . tight 2 4. 2 . </p>