• Columbia University

• IEOR 6613

Solution for E6613, Homework 4 October 20, 2018 1 Exercise 3.25 1. The system of equations Ax = b, xi = 0, i ∈ L, xi = ui , i ∈ U. (1.1) is equivalent to Bx + X i∈U Aiui = b, xi = 0, i ∈ L, xi = ui , i ∈ U. (1.2) Since B = (AB(1), . . . , AB(m) ) is a nonsingular matrix, it follows that the above equations have a unique solution. Thus, the resulting vector x is a basic solution. Then x is nondegenerate.⇔ There are exactly n linear constraints being active at x. ⇔ 0 < xi < ui for every basic variable xi . 2. Let w = B−1Aj , in order to preserve feasibility, θ must satisfy xB(i) − θwi ≥ 0, for wi > 0, xB(i) − θwi ≤ ui , for wi < 0, θ ≤ uj (1.3) or equivalently, θ ≤ θ ∗ = min{min wi>0 xB(i) wi , uj , min wi<0 xB(i) − ui wi }. If θ ∗ = uj , then xj remains a nonbasic variable, but it is moved from L to U. Otherwise, we let l be an index i that attains the minimum. Then, xB(l) exits the basis and is replaced by xj .