Scribd
Upload
7 views2 pages

ORIE 630 Homework 7 Solutions

This document contains solutions to three problems from homework assignment 7 in the course ORIE 630. 1) The first problem proves that the optimal solution to a linear program is unique if the reduced costs of all non-basic variables are positive. 2) The second problem shows that the optimal solution is unique if and only if the optimal value of a related linear program is 0. 3) The third problem proves by contradiction that a variable cannot leave the basis if it was the only variable with a negative reduced cost upon entering the basis.

Uploaded by

alamin018
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

ORIE 630 Homework 7 Solutions

This document contains solutions to three problems from homework assignment 7 in the course ORIE 630. 1) The first problem proves that the optimal solution to a linear program is unique if the reduced costs of all non-basic variables are positive. 2) The second problem shows that the optimal solution is unique if and only if the optimal value of a related linear program is 0. 3) The third problem proves by contradiction that a variable cannot leave the basis if it was the only variable with a negative reduced cost upon entering the basis.

Uploaded by

alamin018
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

ORIE 630

Homework #7 Solutions:

Problem #1
Note that there are many dierent proofs to this problem. (a): Let x be given and let x be another feasible solution. Suppose the reduced cost of every non-basic variable is positive, so x is optimal. First, note that since x =x , there exists an i N such that x i > 0. To see this, note that if x N = 0, but Ax = b, then AB x B = b, so x B = x B and, hence, x =x . Finally, note that 0 = c x < c i x i c x , since c i > 0, x i > 0. Hence, x cannot be optimal. Therefore, the optimal solution is unique. (b): Suppose x is optimal and non-degenerate, but there is a non-positive reduced cost c j . Since x is optimal, it must be that c j = 0.
1 Let d = A B td 0. Such a t exists since B Aj and t > 0 such that x x is non-degenerate.

Let x be such that xj = t, xB = x B td, and xi = 0 for i N, i = j . Then c x = c j xj + c B xb + c N xn = 0 = c x . Hence, x is also optimal, so the optimal solution is not unique. Note that, with an appropriate choice of t, this is simply performing an iteration of the Revised Simplex method.

Problem #2
Recall that min{cx : Ax = b, x 0} has the same optimal solutions as min{c x : Ax = b, x 0}. Let x be one such optimal solution. : Suppose the optimal value of min{ iI xi : Ax = b, x 0, xi = 0i N \I } is 0. Then any feasible solution to this LP has xi = 0 for all i I . By construction, xi = 0 for all i N \I , so xi = 0 for all i N . Therefore, the only feasible solution to this LP is x . 1

Let x be any other feasible solution to the original LP, other than x . Then there must be some i N such that xi > 0 (See problem 1(a)). If i N \I , then c x = c N \I xN \I c i xi > 0 = c x , so x cannot be optimal. (The above I = 0.) Hence, xN \I = 0. By the rst part, any solution follows since c B = c that has xN \I = 0 also has xI = 0. Therefore, x must be the unique optimal solution. : Suppose the optimal value of the new LP is positive. Then there exists x = x such that xi = 0 for all i N \I . But, since c i = 0 for all i B I, c x = 0 = c x . Hence, x has the same objective value as x , so it is also optimal. Hence, the optimal solution is not unique.

Problem #3
Let B be your current basic solution such that xj is the unique variable with c j < 0. Let x be the current basic solution before pivoting in xj . Suppose be the at some point later during the algorithm, xj leaves the basis. Let x basic solution at that point. Since xj > 0, there was a non-degenerate iteration between when xj enN xN = 0 since c B = 0 = xN . tered and left, so c x > c x . But, c x = c B xB + c N < 0. Hence, c N x Finally, c N x N = c j x j + iN c i x i 0 since x j = 0 and c i 0 for all i N \{j }. Hence, 0 < 0, which is a contradiction.

You might also like