University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

485

Pages:

2
Author:

swtdreamz714njr

Problem 1. (Adapted from BHM, Applied Mathematical Programming) Solve the following linear program graphically: max − 3x1 + 6 x 2 s.t. 5x 1 + 7 x 2 ≤ 35 − x1 + 2 x 2 ≤ 2 x1 , x 2 ≥ 0 a) What is the optimal solution? b) What if the objective function was -2x1 + 6x2? c) What if the objective function was -4x1 + 6x2? Problem 2. Simplex Method Consider the following LP: max 8 x1 + 4 x 2 + 5 x3 s.t. x1 + 2 x 2 + x3 ≤ 10 2 x1 − 3 x 2 ≤ 8 x1 , x 2 ≥ 0; x3 free a) Write the LP in standard form. b) Solve the LP using the simplex method. Problem 3. Simplex Tableaux Suppose in solving a maximization problem we obtain the tableau: z 1 0 0 0 Page 1 of 2 x1 c 4 -1 f x2 d a -5 -3 x3 0 1 0 0 x4 0 0 1 0 x5 2 b -1 -4 x6 0 0 0 1 rhs 10 e 2 3 Give conditions on the missing values a, b, c, d, e and f required to make the each of the following statements true: a) b) c) d) e) The current basic solution is optimal. The current basic solution is not a basic feasible solution. The current basic solution is a degenerate basic feasible solution. The current basic solution is feasible, but the LP has unbounded objective value. The current basic solution is feasible, but the objective function value can be improved by bringing x1 into the basis and pivoting x6 out. Problem 4. True or False (Note: We are assuming non-negativity constraints are present in all of the problems.) a) Every LP has a feasible solution. b) Every optimal solution must lie at a corner point. c) If an LP is infeasible, then it may be possible to change the objective function to make the LP feasible. d) 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. e) If an LP has at least two optimal solutions, then it has an infinite number of different optimal solutions. f) If an LP has more then one optimal solution, then there are at least two BFS that are optimal. g) When running simplex, a variable that has just left the basis cannot re-enter the basis on the very next iteration. h) When running simplex, a variable that has just been pivoted into the basis, can not leave in the very next iteration. i) An iteration of the simplex method may move the feasible solution by a positive distance while leaving the objective value the same. Page 2 of 2