Langrangean Example

LAGRANGEAN EXAMPLE Prof. Stephen Graves Production quantities for metal stamping (from David B. Kletter’s SM thesis, Determining Production Lot Sizes and Safety Stocks for an Automobile Stamping Plant, 1994) : A metal stamping plant for an automobile manufacturer will produce 100’s of parts on dozens of stamping lines to satisfy part demand from the assembly plants. In running the stamping plant, a key planning decision is the assignment of parts to stamping lines. Once this assignment is made, then inventory control policies need to be established for the family of parts assigned to each line. A common control policy is to determine the relative production frequency (and/or batch size) for each part and the necessary buffer stock to assure a high level of service for the assembly plants. The following describes how to find the production batch sizes. n Si Di H i Qi min ∑ + 2 i =1 Qi n s.t. Ti Di =K ∑ i =1 Qi Qi = production quantity or lot size Si = setup cost Hi = holding cost Ti = setup time Di = annual demand K = available capacity for setups Introduce Lagrange Multiplier: λ ⎛ n ⎞ n S Di H iQ ⎜ ⎟ T D i i i i ⎜ L(Q,λ ) = ∑ − K ⎟⎟ + + λ ⎜∑ ⎜⎜ ⎟⎟ Qi 2 ⎝ i =1 ⎠ i =1 Qi Approach: • for given λ, find Qi that minimize L (Q, λ); • then choose λ such that Qi satisfy original constraint. Look at first-order conditions: ∂L = 0 ∂ Qi ∂L = 0 ∂λ for i = 1, ... n ∂ L = − Si Di + Hi − λTi Di = 0 ∂ Qi 2 Qi2 Qi2 ⇒ Qi2 = 2 ( S i + λT i ) Di Hi * Qi = 2 + H i ( S i λT i ) Di Now choose λ such that ∂ L = n T i Di − K = 0 ∑ ∂λ i=1 Q*i n ∑ i =1 T i Di 2 + λT ) D ( S i i i Hi Solve by univariate search. −K =0 Note that ∂ L = −λ ∂K ⇒ λ is a shadow price on the capacity, and equals the amount we would pay for additional capacity, on the margin. This approach is very useful for removing "troublesome" constraints. Lagrange Example Limit Total Item 1 Item 2 Item 3 25 10000 1 20 707.11 40 20000 1 10 1264.91 50 5000 1 25 707.11 617.73 2679.12 282.84 707.11 158.11 1264.91 176.78 707.11 400 160.77 122.91 116.32 2898.16 822.98 1305.23 769.95 Annual Setup Time Quantity Item 1 Quantity Item 2 Quantity Item 3 total cost 617.73 496.58 250.97 326.39 405.19 359.27 380.09 392.11 398.69 402.11 400.39 399.54 399.96 400.18 400.07 400.02 707.11 948.68 2121.32 1581.14 1224.74 1414.21 1322.88 1274.36 1249.00 1236.12 1242.58 1245.79 1244.19 1243.38 1243.78 1243.99 1264.91 1414.21 2366.43 1897.37 1612.45 1760.68 1688.19 1650.45 1630.95 1621.11 1626.04 1628.50 1627.27 1626.65 1626.96 1627.11 707.11 866.03 1732.05 1322.88 1060.66 1198.96 1131.92 1096.59 1078.19 1068.88 1073.55 1075.87 1074.71 1074.13 1074.42 1074.56 2679.12 2732.34 3710.15 3169.42 2884.89 3026.59 2955.22 2919.57 2901.61 2892.68 2897.14 2899.38 2898.26 2897.70 2897.98 2898.12 Setup cost($) Demand (per yr) Hold. cost($/un-yr) Setup time (hrs) EOQ EOQ setup time/year EOQ Cost Avail. Setup Time 400 Constrained cost Lagrange multiplier 0 1 10 5 2.5 3.75 3.125 2.81 2.65 2.57 2.61 2.63 2.62 2.615 2.6175 2.61875 Microsoft Excel Answer Report Worksheet: Lagrange example Target Cell (Min) Cell $C$19 Name Constrained cost Total Original Value Final Value 2679.12 2898.16 Original Value Final Value 707.11 1264.91 707.11 1244.05 1627.16 1074.61 Cell Value Formula Adjustable Cells Cell $D$4 $E$4 $F$4 Name Quantity Item 1 Quantity Item 2 Quantity Item 3 Constraint Cell $C$17 $D$4 $E$4 $F$4 Name Avail. Setup Time Total Quantity Item 1 Quantity Item 2 Quantity Item 3 400 1244.05 1627.16 1074.61 $C$17<=$B$17 $D$4>=0 $E$4>=0 $F$4>=0 Microsoft Excel Sensitivity Report Worksheet: Lagrange example Changing Cells Cell $D$4 $E$4 $F$4 Name Quantity Item 1 Quantity Item 2 Quantity Item 3 Final Value Reduced Gradient 1244.05 1627.16 1074.61 0.00 0.00 0.00 Final Value Lagrange Multiplier 400 -2.61915 Constraints Cell $C$17 Name Avail. Setup Time Status Binding Not Binding Not Binding Not Binding Slack 0 1244.05 1627.16 1074.61