Introduction to Optimization Recitation 3 - Solutions

Problem 1. a) If we graph this problem, we obtain the feasible region shown in green below. The thick lines represent the constraints, and the thin lines are the isoprofit lines of the objective function. Notice that as we move the isoprofit lines along the feasible region, the last point of intersection is along the line segment between points A=(0,1) and B≈(3.29, 2.65). Hence all points on this line segment are optimal. The optimal cost is 2. 10 9 8 7 6 5 4 3 2 1 0 -1 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 -1 0 B A 1 2 3 4 5 6 7 8 9 10 b) If the objective function changes to -2x1 + 6x2, then the isoprofit lines will become flatter (closer to horizontal). We can verify that if we move these lines across the feasible region, the last point they touch will be point B. So point B is optimal. c) If the objective function changes to –4x1 + 6x2, then the isoprofit lines will become steeper (closer to vertical). We can verify that if we move these lines across the feasible region, the last point they touch will be point A. So point A is optimal. Problem 2. a) Standard form: max 8 x1 + 4 x 2 + 5 y1 − 5 y 2 s.t. x 1 + 2 x 2 + y1 − y 2 + s1 = 10 2 x1 − 3 x 2 + s 2 = 8 x1 , x 2 , y1 , y 2 , s1 , s 2 ≥ 0 Page 1 of 5 b) Simplex Tableaux: Z x1 1 0 0 Z x2 -8 1 2 x1 1 0 0 Z -4 2 -3 x2 0 0 1 x1 1 0 0 y1 -5 1 0 y1 -16 3.5 -1.5 x2 0 0 1 y2 5 -1 0 y2 -5 1 0 y1 1.5 3.5 -1.5 s1 0 1 0 s1 5 -1 0 y2 0 1 0 0 0 1 0 1 0 0 10 8 RHS s2 s1 0 -1 0 RHS s2 4 -0.5 0.5 RHS s2 5 1 0 32 6 4 1.5 -0.5 0.5 62 6 4 (Note: Blue indicates the current basic variables.) With respect to the standard form problem, the optimal solution is: x1 = 4, x2 = 0, y1 = 6, y2 = 0, s1 = 0, s2 = 0; optimal objective value = 62. In terms of the original problem, we this translates to: x1 = 4, x2 = 0, x3 = 6; optimal objective value = 62. Problem 3. a) For the current basic solution to be optimal, we need: o e ≥ 0, so the solution is feasible. o c ≥ 0 and d ≥ 0, so the solution cannot be improved upon. b) For the current basic solution to be infeasible, we need: o e < 0, which implies that x3 is negative and violates the bounds set in our standard form assumptions. c) For the current basic solution to be degenerate, we need: o e = 0, which implies that basic variable x3 is equal to zero. d) For the current basic solution to be feasible, but with an unbounded LP, we need: o e ≥ 0, so the solution is feasible. o d < 0, so the objective function will improve if we increase variable x2. o a < 0, so an increase in x2 will not run up against any of our resource constraints (i.e. we can increase x2 indefinitely). e) For the current basic solution to be feasible, but where the objective function value can be improved by bringing x1 into the basis and pivoting out x6, we need: o e ≥ 0, so the solution is feasible. o c < 0, so pivoting on variable x1 improves the objective value. Page 2 of 5 o f > 0, so it is possible for x6 to be the leaving variable. 3 e o ≤ , so that x6 wins (or at least ties) in the minimum ratio test to be the f 4 exiting basic variable. Problem 4. a) True or false: Every LP has a feasible solution. False. Consider the LP max x x≥3 x ≤1 s.t. This LP does not have a feasible solution. b) True or false: Every optimal solution must lie at a corner point. False. Consider the LP max x s.t. x≤3 y≤2 x,y ≥ 0 In this problem, (3,1) is an optimal solution but it is not a corner point. c) True or false: If an LP is infeasible, then it may be possible to change the objective function to make the LP feasible. False. If an LP is currently infeasible, this means that there is no point that satisfies all of the constraints. The objective function is what we use to find the best feasible point for our problem. If we only change the objective function, all we are changing is our criterion to find the best point out of all the feasible ones. Thus, since the constraints are the same and no point satisfies them, the feasible region remains empty and the LP still cannot be solved. d) True or false: If the feasible region in a linear program with a maximization objective is unbounded, then there is a sequence of feasible solutions such that the limit of the objective values is infinity. False. Consider the LP max − x − y s.t. Page 3 of 5 x≥0 y≥0 The feasible region is unbounded. However, the point (0,0) is the optimal solution, which is located at a corner point. The optimal objective value for this problem is 0. e) True or false: If an LP has at least two optimal solutions, then it has an infinite number of different optimal solutions. True. If x and y are optimal solutions, then every point on the line segment connecting x and y will be optimal too. More formally, for any number λ ≥ 0, the point (1-λ)⋅x + λ⋅y will be optimal, since c((1-λ)⋅x + λ⋅y) = (1-λ)c(x) + λc(y) = (1-λ)c(x) + λc(x) = c(x). The first equality follows since our cost function is linear, and the second follows since c(x) = c(y). Note that this argument only holds because the feasible region of a linear program is convex. The convexity ensures that all the points between x and y are contained in the feasible region. If we were trying to maximize over a non-convex feasible region, such as y x then the statement would not necessarily be true. (In this picture, there are exactly two optimal solutions.) f) True or false: If an LP has more then one optimal solution, then there are at least two BFS that are optimal. False. Consider the LP max − y s.t. y≤2 x, y ≥ 0 This LP has two corner points, (0,0) and (0,2). However, any point (x, 0) with x ≥0 is an optimal point. Thus this LP has an infinite number of optimal points, but it has only one BFS that is optimal, the point (0,0). Page 4 of 5 g) True or false: When running simplex, a variable that has just left the basis cannot reenter the basis on the very next iteration. True. When we pivot out a variable, the coefficient in the objective row of that variable becomes non-negative. In next iteration of simplex, we will only pivot on variables with a negative coefficient. Hence we will not pivot on the variable that just left. (It is important to note in general that once a variable has left the basis, it is eligible to return on any iteration except for the iteration directly after it was pivoted out.) h) True or false: When running simplex, a variable that has just been pivoted into the basis cannot leave in the very next iteration. False. The following is a counter-example. In problem 2, after pivoting on variable x1, pivot on x2 instead of y1. After completing this pivot, the only variable with a negative coefficient is y1. Pivot in y1, and you will see that by the minimum ratio test x2 leaves the basis. The pivots for this are shown below: Z x1 1 0 0 Z x2 -8 1 2 x1 1 0 0 Z x2 0 0 1 x1 1 0 0 Z 0 0 1 y1 s1 5 -1 0 y2 RHS s2 0 1 0 s1 0 0 1 0 10 8 RHS s2 -5 1 0 5 -1 0 0 1 0 4 -0.5 0.5 32 6 4 0 1 0 y1 0.428571 0.285714 0.428571 y2 -0.42857 -0.28571 -0.42857 s1 -4.57143 0.285714 0.428571 s2 -1.71429 -0.14286 0.285714 RHS -59.4286 1.714286 6.571429 y1 y2 s1 s2 RHS x2 0 0 1 y2 -5 1 0 -16 3.5 -1.5 x2 x1 1 0 0 y1 -4 2 -3 1.5 3.5 -1.5 0 1 0 0 -1 0 5 1 0 1.5 -0.5 0.5 62 6 4 i) An iteration of the simplex method may move the feasible solution by a positive distance while leaving the objective value the same. False. The only time the simplex method pivots and leaves the objective value the same is when it is performing a degenerate pivot. In this case, the feasible solution does not change by a positive distance (since we are merely changing the assignment of basic variables). Page 5 of 5