IEM - Spring 2014 Operations Research (MA224): Mid Exam Instructor : F. Chen Oﬃce : ME A618 E-mail : [email protected] Name: Scores: Problem Problem Problem Problem Date : Apr 29, 2014 Time : 10:00am-12:00am Room : Shangyuan-101 Student No.: 1 2 3 4 (25’): (25’): (25’): (25’): Total: Problem 1,25’ Find all BF S (basic feasible solution) and EP (extreme point) for the following linear program LP1). For each BF S , point out the BV (basic variable), N BV (nonbasic variable), and B (basis), and show the mapping from BF S to EP . LP1) max 3x1 + x2 s.t. x1 + x2 ≤ 5 −x1 + 2x2 ≤ 6 x1 , x2 ≥ 0 Problem 2,25’ An industrial recycling center uses two scrap aluminum metals, A and B, to produce a special alloy. Scrap A contains 6% aluminum, 3% silicon, and 4% carbon. Scrap B has 3% aluminum, 6% silicon, and 3% carbon. The piecewise costs for scraps A and B are as follows.   if x ∈ [0, 200] 100x CA (x) = 80x + 4000 if x ∈ [200, 500]   60x + 14000 if x ≥ 500 { 80y if y ∈ [0, 600] CB (y) = 50y + 18000 if y ≥ 600 Here, CA (x), and CB (y) are the cost for scraps A and B, respectively, if x tons of scraps A, and y tons of scraps B are purchased. 1 The specifications of the special alloy require that (1) the aluminum content must be at least 4% and at most 5%, (2) the silicon content must lied between 4% and 5%, and (3) the carbon content must be between 3.3% and 3.8%. The objective is to minimize the total cost of the scraps that should be used in producing 1000 tons of the alloy. Please build a mixed integer linear programming (MILP) model for above problem.(you need not to solve it) Problem 3,25’ Consider the following linear program LP3): LP3) max s.t. x1 + 5x2 + 3x3 x1 + 2x2 + x3 = 3 2x1 − x2 = 4 x1 , x2 , x3 ≥ 0 We use Big-M method to solve it. The starting basic variables are x3 in the first constraint and an artificial x4 in the second constraint with M = 100. The optimal tableau is given as x3 x1 x1 x2 x3 x4 −OBJ 0 −2 0 −99 −5 0 2.5 1 −0.5 1 1 −0.5 0 0.5 2 Show the dual linear program of LP3) and based on such optimal tableau, determine the dual optimal solution according to the property of complementary slackness (do not use the simplex method to solve the dual linear program again). Problem 4,25’ Use two-phase method to solve the following linear program LP4), and show the shadow price of b1 (= 15). LP4) max 7x1 + 3x2 + x3 s.t. −x1 + 3x2 = 15 2x1 + x2 + x3 = 24 x 1 , x 2 , x3 ≥ 0 (The End) 2