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

mathematics

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


Related Questions in mathematics category


Disclaimer
The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.