Consider the following linear program: Minimize 20x1 + 13x2 + 10x3 + 14

Consider the following linear program: Minimize 20x1 + 13x2 + 10x3 + 14.14 + 2815 Subject to 12x1 + 412 + 713 + 314 + 615 = 62 3x1 + 12 + 613 + 514 + 1015 = 58 Ari + 2x2 + 7x3 + 614 + 13x5 + 16 = 80 T1 , . . ., '6 2 0 Assume that, at the current iteration of the simplex algorithm, the basis is B = [a2, a4, a6], where a; is the ith column of the coefficient matrix of constraints. You could use the information provided below to answer questions. TB = CB 7 = (3, 1, 0) ByB = 41 yB = (3, 0, -2) BIB = b TB = (8, 10, 4) ByB = 43 yB = (1, 1, -1) ByB = 45 yB = (0, 2, 1) a: What is the current basic feasible solution ? What is its objective value? b: What variables are candidates to enter the basis? C: If r3 enters the basis, which variable leaves the basis?

(1: Suppose that entering and leaving variables have been chosen as in (c). 1What is the new basic feasible solution? 1What is its objective value? Suppose that, after some more iterations, the current basis is B = [(13, (14,116] and 3TB : CB 2} 1T 2 (—21410} By? : ‘11 2'" yB : (31 _31 1) 1333:!) 2:» j3={8,2,12) Byg =62 => yB:(11—111) By? : ‘15 2'" yB : (01211) e: What is the current basic feasible solution 5:? What is its objective value? f: [5 this is optimal? How can you tell? 3: Denote by ’?'j as jth dual variables. Write the dual program. in What is the optimal solution ir‘ = («Lari erg) of the dual program.