Fundamentals of Optimization MATH11111 Thursday 10th December 2020 1300-1500 * All students: you have an additional 1 hour to assemble and submit your PDF. Final submission deadline: 16:00. * Students with a Schedule of Adjustment: You are entitled to a further fixed additional 1 hour for this remote examination. Final submission deadline: 17:00 Attempt all questions Important instructions 1. Start each question on a new sheet of paper. 2. Number your sheets of paper to help you scan them in order. 3. Only write on one side of each piece of paper. 4. If you have rough work to do, simply include it within your overall answer – put brackets at the start and end of it if you want to highlight that it is rough work. MATH11111 Fundamentals of Optimization 1 (1) Puzzle (8 marks) Consider the following linear programming problem in standard form: min 2×1 3×2 3×3 + c4 x4 s.t. 2×1 + x2 + 2×3 + 4×4 = b1 2×1 + 3×2 + 6×3 + 8×4 = b2 x1 , x2 , x3 , x4 ≥ 0 Below is the final dictionary with the optimal solution: z = 4 + 3×3 + 5×4 x1 = G + d13 x3 x4 x2 = 2 + d23 x3 2×4 Determine the unknown values for c4, b1, b2, G, d13, and d23. Justify your solution. Recall that, for an invertible matrix M ∈ R2×2 given by M = [ a b c d ] , its inverse is M 1 = 1 det(M) [ d b c a ] . [Please turn over] MATH11111 Fundamentals of Optimization 2 (2) Duality & Sensitivity Analysis (12 marks & 40 marks) (a) Determine an optimal solution x ∈ R4 and the optimal value z ∈ R for the following linear programming problem using the graphical method: (P ) min 4×1 + 11×2 + 5×3 + 4×4 s.t. x1 + x2 + x3 + x4 = 3 x1 + 2×2 2×4 = 9 x1 , x2 , x3 , x4 ≥ 0 Justify your solution. [12 marks] (b) Consider the following linear programming problem: min 2×1 + 3×2 3×3 + 2×4 4×5 s.t. 2×1 + x2 + 3×3 + x4 + 2×5 = 10 3×1 + 2×2 + x3 + 2×5 = 18 x1 , x2 , x3 , x4 , x5 ≥ 0 The optimal dictionary is given below: z = 14 + 28×3 + 15×4 + 6×5 x1 = 2 5×3 2×4 2×5 x2 = 6 + 7×3 + 3×4 + 2×5 [Please turn over] MATH11111 Fundamentals of Optimization 3 Instructions: For the primal simplex, if there is more than one nonbasic variable with a negative reduced cost, choose the one with the most negative reduced cost as the entering variable. In the minimum ratio test, if there is a tie between two or more rows, choose the row whose basic variable has the smallest index to determine the leaving variable. For the dual simplex, if there is more than one negative basic variable, choose the one with the most negative value as the leaving variable and break ties in favour of the basic variable with the smallest index. In the minimum ratio test, if there is a tie between two or more nonbasic variables, then break the tie in favour of the nonbasic variable with the smallest index. Questions: (i) By how much can we decrease the value of b1 = 10 such that current dictionary remains optimal Justify your solution. [6 marks] (ii) If we increase the value of b1 = 10 by δ = 4, does the current dictionary remain optimal Justify your solution. If not, then perform one iteration of the appropriate simplex method and derive a new dictionary with its corresponding solution. For the new dictionary, write down the index sets B and N , values of all variables, reduced costs of all variables, and the current objective function value. State whether the corresponding solution is optimal or not. State whether it is primal feasible or dual feasible or both. Justify your solution. [14 marks] (iii) By how much can you decrease the value of c4 = 2 such that the current dictionary remains optimal Justify your solution. [3 marks] (iv) If we increase the value of c4 = 2 by δ = 4, does the current dictionary remain optimal Justify your solution. If not, then perform one iteration of the appropriate simplex method and derive a new dictionary with its corresponding solution. For the new dictionary, write down the index sets B and N , values of all variables, reduced costs of all variables, and the current objective function value. State whether the corresponding solution is optimal or not. State whether it is primal feasible or dual feasible or both. Justify your solution. [2 marks] (v) If we decrease the value of c2 = 3 by δ = 3, does the current dictionary remain optimal Justify your solution. If not, then perform one iteration of the appropriate simplex method and derive a new dictionary with its corresponding solution. For the new dictionary, write down the index sets B and N , values of all variables, reduced costs of all variables, and the current objective function value. State whether the corresponding solution is optimal or not. State whether it is primal feasible or dual feasible or both. Justify your solution. [9 marks] (vi) Consider the variable x5. If we change A 5 from [2, 2]T to [2, 2]T + δ[1, 2]T , where δ ∈ R, find the range of δ for which the current dictionary remains optimal. Justify your solution. [6 marks] [Please turn over] MATH11111 Fundamentals of Optimization 4 (3) Duality (14 marks) Consider the following linear programming problem in standard form: (P) min{cTx : Ax = b, x ≥ 0}, where A ∈ Rm×n, b ∈ Rm, and c ∈ Rn are the parameters, x ∈ Rn is the vector of decision variables, and 0 ∈ Rn denotes the vector of all zeroes. Assume that (P) has a finite optimal value. Suppose that the right-hand side vector b ∈ Rm is replaced by b′ ∈ Rm, where b′ 6= b, i.e., the new linear programming problem is given by (P′) min{cTx : Ax = b′, x ≥ 0}. Prove the following statement: The linear programming problem (P′) is either infeasible or has a finite optimal value. [Please turn over] MATH11111 Fundamentals of Optimization 5 (4) Duality & Convexity (26 marks) Consider the following polyhedron: P = {x ∈ Rn : Ax = b, x ≥ 0}, where A ∈ Rm×n, b ∈ Rm, and c ∈ Rn, and 0 ∈ Rn denotes the vector of all zeroes. Assume that P 6= . Consider the following linear programming problem parametrized by the cost vector c ∈ Rn: (P(c)) min{cTx : x ∈ P}, i.e., for each vector c ∈ Rn, the corresponding linear programming problem is denoted by (P(c)). Let f : Rn → R ∪ { ∞} be a function defined as follows. For each c ∈ Rn, f(c) denotes the optimal value of the linear programming problem (P(c)). For a given vector c ∈ Rn, note that we define f(c) = ∞ if the corresponding linear programming problem (P(c)) is unbounded. (a) Show that there exists a vector c ∈ Rn such that f(c ) is finite (i.e., the corresponding linear programming problem (P(c )) has a finite optimal value). [6 marks] (b) Prove that f is a concave function. (Hint: Consider how the dual problem changes as a function of c and think of using appropriate duality relations.) [20 marks] [End of Paper]
