1. Consider the non-linear program P2 shown below:
max -x2 + 4x - y2 + 12y
P2 = s.t. -5x + 4y ≤ 20
x2 - y ≤ 0
Starting at the solution (x, y) = (1, 4), run one iteration of the General Improving Search Algorithm to find a better solution. Use the gradient as the direction d.
2. Use the two-phase simplex algorithm to find an optimal solution to the linear program P2 (if such a solution exists).
min -7X1 - 4X2 + 4X3
S.t. 5X1 - 4X2 - 3x3 ≥ -3
P2 = 3x1 + 5x2 ≤ 6
3x2 2x3 ≥ 5
X1, X2, X3 ≥ 0
3. Use the two-phase simplex algorithm to find an optimal solution to the linear program P3 (if such a solution exists).
max 4x1 + 5x2 - 3x3
s.t. x1 + 2x2 + x3 = 10
P3 = X1 - X2 ≥ 6
X1 + 3X2 + X3 ≤ 14
X1, X2, X3 ≥ 0
Given a feasible solution x to a linear program and an improving direction d if x + λd is feasible for all λ ≥ 0, then our optimization problem is unbounded.