Math 171A Homework #6
Due date: March 2, 2018
1. (10 points) Consider the kth iteration of the simplex method as de ned in Algorithm 4.2 of
the textbook.
(a) Show that the matrix Ak+1, de ned by replacing the sth row of Ak by the tth row of Ak
is nonsingular. (The index t =2 Wk is such that k = t, and the tth constraint is called a
blocking constraint.)
(b) Show that the component of the Lagrange multiplier a at xk+1 corresponding to the new
constraint in the working set must be positive. (This implies that it is impossible to delete
the constraint that was just added.)
2. (10 points) Consider the LP of minimizing cTx subject to Ax b where
Find the minimizer of this LP by using optimality conditions (do not use simplex method).
Also explain why your solution is a minimizer.
3. (10 points) Let a = (a1;:::;an) 2 Rn+ be a positive vector. Consider the LP:
Minimize x1 + x2 + + xn
subject to a1x1 + a2x2 + + anxn 1
x1 0;:::;xn 0:
Find the solution x of the above LP by using optimality conditions (i.e., do not use the
simplex method), and express it in terms of ai. Explain why your solution is optimal.
4. (5 points) Find the solution of the following LP
Minimize c1x1 + c2x2 + + cnxn
subject to ℓ x u
and express it in terms of ci;ℓi;ui. Here ℓ and u are vectors whose components are all nite
and satisfy ℓi ui for i = 1 : n. Do not use the simplex method.
5. (15 points) Consider the constraints
1 2x1 + x2 4; 0 x1 2; x2 0:
(a) Formulate a phase-1 LP with a single arti cial variable. De ne the phase-1 problem
in such a way that you know an initial vertex for the phase-1 constraints in which
x1 = x2 = 0.
(b) Solve the phase-1 LP of part (a) by using the simplex method for problems in all in-
equality form.
(c) Use the solution of your phase-1 LP to get a feasible point for the original constraints.
Is your solution a vertex for phase-2 LP? Justify your answer.
6. (10 points) Consider the iLP: Minimize cTx s.t. Ax b, where A =
Suppose x is a feasible point, i.e., Ax b. Show that x is an optimizer if and only if there
exists =2641...m3
75 0 such that AT = c and
i(aiTx bi) = 0 for all i.
satisfying [A e]y b. Show that the set fAx bg is empty.
Consider the iLP: {
Minimize cTx
subject to Ax b
Use optimality condition to determine if it has minimizer or not. If yes, please nd one. If
no, please give reasons.
9. (10 points) Consider the iLP: {
Minimize cTx
subject to Ax b
Suppose u ̸= v are two distinct minimizers.
(a) Show that p1 := v u is a feasible direction at u and p2 := u v is a feasible direction
at v.
(b) Show that cTu = cTv, so the minimum value is unique.