University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

429

Pages:

7
Author:

Jamarion Leonard

1 Outline Slide 1 1. The idea of column generation 2. The cutting stock problem 3. Stochastic programming 2 Column Generation Slide 2 For x 2 0 8j ) current solution optimal If z � > 1 ) 9 s: 1 ; p As < 0 ) Variable xs becomes basic, i.e., a new pattern As will enter the basis. Perform min-ratio test and update the basis. Slide 16 0 0 3.5 Dynamic Programming F (u) = max p1 a1 + + pm am s:t: w1 a1 + + wm am u ai 0 integer For u wmin, F (u) = 0. For u wmin F (u) = i�1max fp + F (u ; wi)g ::: m i Slide 17 Why ? 3.6 Example max 11x1 + 7x2 + 5x3 + x4 s:t: 6x1 + 4x2 + 3x3 + x4 25 xi 0 xi integer F (0) = 0 F (1) = 1 F (2) = 1 + F (1) = 2 F (3) = max(5 + F (0)� 1 + F (2)) = 5 F (4) = max(7 + F (0)� 5 + F (1) 1 + F (3)) = 7 F (5) = max(7 + F (1)� 5 + F (2) 1 + F (4)) = 8 (6) F (7) F (8) F (9) F (10) F (u) F = max(11 + F (0)� 7 + F (2) 5 + F (3) 1 + F (5)) = 11 = max(11 + F (1)� 7 + F (2) 5 + F (3) 1 + F (4)) = 12 = max(11 + F (2) 7 + F (4)� 5 + F (5) 1 + F (7)) = 14 = 11 + F (3) = 16 = 11 + F (4) = 18 = 11 + F (u ; 6) = 16 u � 11 4 Slide 18 Slide 19 ) (25) = 11 + (19) = 11 + 11 + (13) = 11 + 11 + 11 + (7) = 33 + 12 = 45 F � x = (4 0 0 1) F F F 4 Stochastic Programming 4.1 Example Slide 20 Wrenches Pliers Cap. 1.5 1.0 27,000 Steel (lbs) 1.0 1.0 21,000 Molding machine (hrs) 0.3 0.5 9,000* Assembly machine (hrs) Demand limit (tools/day) 15,000 16,000 Contribution to earnings $130* $100 ($/1000 units) Slide 21 max 130W + 100P s:t: W 15 P 16 1:5W + P 27 W + P 21 0:3W + 0:5P 9 W P 0 4.1.1 Random data 8 > < 8000 with probability Assembly capacity is random: > : 10 000 with probability 8 > < 160 with probability 12 Contribution from wrenches: > : 90 with probability 1 1 2 1 2 Slide 22 2 4.1.2 Decisions Slide 23 4.1.3 Formulation Slide 24 Need to decide steel capacity in the current quarter. Cost 58$/1000lbs. Soon after, uncertainty will be resolved. Next quarter, company will decide production quantities. 5 State Cap. W. contr. 1 8,000 160 10,000 160 2 90 8,000 3 10,000 90 4 Decision Variables: S: steel capacity, Pi Wi : i = 1 : : : 4 production plan under state i. max ;58S + 0:25Z1 + 0:25Z2 + 0:25Z3 + 0:25Z4 s:t: Ass: 1 0:3W1 + 0:5P1 8 Mol: 1 W1 + P1 21 Ste: 1 ;S + 1:5W1 + P1 0 W:d: 1 W1 15 P:d: 1 P1 16 Obj: 1 ;Z1 + 160W1 + 100P1 = 0 Ass: 2 0:3W2 + 0:5P2 10 Mol: 2 W2 + P2 21 Ste: 2 ;S + 1:5W2 + P2 0 W:d: 2 W2 15 P:d: 2 P2 16 Obj: 2 ;Z2 + 160W2 + 100P2 = 0 Ass: 3 0:3W3 + 0:5P3 8 Mol: 3 W3 + P3 21 Ste: 3 ;S + 1:5W3 + P3 0 W:d: 3 W3 15 P:d: 3 P3 16 Obj: 3 ;Z3 + 90W3 + 100P3 = 0 Ass: 4 0:3W4 + 0:5P4 10 Mol: 4 W4 + P4 21 Ste: 4 ;S + 1:5W4 + P4 0 W:d: 4 W4 15 P:d: 4 P4 16 Obj: 4 ;Z4 + 90W4 + 100P4 = 0 S Wi Pi 0 4.1.4 Solution Solution: S = 27 250lb. 1 2 3 4 Prob. 0.25 0.25 0.25 0.25 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Wi 15,000 15,000 12,500 5,000 6 Pi 4,750 4,750 8,500 16,000 4.2 Two-stage problems Random scenarios indexed by w = 1 : : : k. Scenario w has probability w . First stage decisions: x: Ax = b x 0. Second stage decisions: yw : w = 1 : : : k. Constraints: Bw x + Dw yw = dw , yw 0. 4.2.1 Formulation min c x + 0 Ax B1x + B2x + .. . 1f1y1 + 0 D1y1 + k fk yk 0 =b = d1 = d2 D2y2 .. ... . Dkyk = dk y2 : : : yk 0: Bkx + x y1 Structure: x y1 y2 y3 y4 Objective 7 Slide 30 Slide 31 Slide 32