Linear Optimization (1:640:354:05)
Spring 1999, Professor Ben-Israel
Assignment 5: Simplex Algorithm & Duality
Date: Tuesday, March 4
Due: Thursday, March 11
This assignment has four problems, of equal weight.
1 Let B =
{v1, v2, .... , vm}
be a basis of Rm, and let x be a vector
in Rm. The representation of x w.r.t.
B is the vector (xi) given by
x = x1 v1 +
x2 v1 + .... +
xm
vm
Consider a set B' obtained by replacing one vector of B,
say vp, by some vector u in Rm.
(a) Give a (necessary & sufficient) condition for B' to be a
basis of Rm.
(b) If this condition is satisfied, compute the representation of
a general vector w.r.t. B' in terms of
- its representation w.r.t.
B, and
- the representation of u w.r.t. B.
(c) Explain the simplex algorithm in light of (a) & (b).
2 Exercise 2, attached handout.
Solve the following problems and show every iteration.
3 Text, p. 214, Exercise 2.
4 Text, p. 215, Exercise 4.
Return to the HW Assignments page