Professional blog

Description

4. (15 points)

Description

4. (15 points) Classify the following statements as true or false. If true, give a 1-3 line explanation, otherwise provide a counterexample or explanation. No rigorous formal justification needed.

(a) If a LP has an optimal solution, then this optimal solution is an optimal basic feasible solution.

(b) In simplex method, a departing variable can not re-enter the basis in the next iteration.

(c) In simplex method, an entering variable can not become a departing variable in the next iteration.

(d) If some decision variable xj in a LP is unrestriced in sign, we can substitute xj = x + j − x − j for every xj , where x + j ≥ 0, x − j ≥ 0. In the optimal solution obtained by simplex method, it is possible that x + j > 0 and x − j > 0. (e) For a LP in standard form, the optimal value of the decision variable associated with the largest cost coefficient in its object function is always positive.

5. (10 points) Consider the following linear programming problem in standard form (P) Maximize c T x Subject to Ax = b x ≥ 0 and its dual problem (D). Let x ∗ and u ∗ be optimal solutions of (P) and (D) respectively. (a) Let ˆx be the optimal solution of (P) when c is replaced by ˆc. Show that (ˆx − x ∗ ) T (ˆc − c) ≥ 0. (b) Assume the cost vector is still c. Let ˜x be the optimal solution of (P) when b is replaced by b˜. Show that

If true, give a 1-3 line explanation, otherwise provide a counterexample or explanation. No rigorous formal justification needed.

(a) If a LP has an optimal solution, then this optimal solution is an optimal basic feasible solution.

(b) In simplex method, a departing variable can not re-enter the basis in the next iteration.

(c) In simplex method, an entering variable can not become a departing variable in the next iteration.

(d) If some decision variable xj in a LP is unrestriced in sign, we can substitute xj = x + j − x − j for every xj , where x + j ≥ 0, x − j ≥ 0. In the optimal solution obtained by simplex method, it is possible that x + j > 0 and x − j > 0. (e) For a LP in standard form, the optimal value of the decision variable associated with the largest cost coefficient in its object function is always positive.

5. (10 points) Consider the following linear programming problem in standard form (P) Maximize c T x Subject to Ax = b x ≥ 0 and its dual problem (D). Let x ∗ and u ∗ be optimal solutions of (P) and (D) respectively. (a) Let ˆx be the optimal solution of (P) when c is replaced by ˆc. Show that (ˆx − x ∗ ) T (ˆc − c) ≥ 0. (b) Assume the cost vector is still c. Let ˜x be the optimal solution of (P) when b is replaced by b˜. Show that