MAST20018 – Introduction to Discrete Mathematics and Operations Research Assignment 4 1. Is the following tableau optimal x1 x2 x3 x4 x5 RHS x2 0 1 0 1/6 0 2/3 x3 2 0 1 1/2 0 10 x5 1 0 0 5/2 1 19 z 4 0 0 31 0 460 under the circumstances below? If it is optimal, also state the value of the optimal objective function. (a) The problem is a minimisation problem and the z-row of the tableau was initialised with the cost vector (ct). (b) The problem is a maximisation problem and the z-row of the tableau was initialised with the cost vector (ct). (c) The problem is a minimisation problem and the z-row of the tableau was initialised with the negative of the cost vector (−ct). (d) The problem is a maximisation problem and the z-row of the tableau was initialised with the negative of the cost vector (−ct). 2. Consider the linear program max 5x + y s.t. x + y ≤ 7 x− y ≤ 3 x, y ≥ 0 (a) Derive the dual linear program. (b) Plot the feasible regions to both the primal and the dual problems. (c) Solve the primal problem using the simplex method. In each iteration, indicate on the graphs both the current primal basic feasible solution and its corresponding dual solution. 1 MAST20018 – Introduction to Discrete Mathematics and Operations Research 3. The simplex method is a typically efficient algorithm for solving linear programs. However, there is no version of it that has been shown theoretically to solve any linear program in polynomial time. In fact, it is much worse. In 1972, Klee and Minty came up with an example in n dimensions that requires 2n − 1 iterations if Dantzig’s rule1 is used to choose entering variables. These problems are of the form max n∑ j=1 10n−jxj s.t. 2 ( i−1∑ j=1 10i−jxj ) + xi ≤ 100i−1, i ∈ {1, 2, . . . , n} xj ≥ 0, j ∈ {1, 2, . . . , n}. (a) Write the problem for n = 3. (b) Solve the problem using Dantzig-rule. 1For a maximisation problem, Dantzig’s rule asks to select as entering variable the non-basic variable with largest reduced cost. 2
欢迎咨询51作业君