1. Consider an LP which has as its rst constraint
x1 + x2 x3 x4 1:
Assume that you know (based on other constraints) that x2 = 0. Show that the dual variable
y1 associated with the rst constraint is zero.
2. A question using LINDO (or other software). Consider the following LP:
max c1x1 +7x2 +7x3 +11:1x4
(10 + d1)x1 +4:5x2 +1:2x3 +9x4 100
(10 + d2)x1 +4x2 +1x3 +8:2x4 100
(10 + d3)x1 +3x2 +3x3 +3x4 100
(10 + d4)x1 +2x2 +4x3 +x4 100
(10 + d5)x1 +x2 +5x3 +x4 100
x1;x2;x3;x4 0
where d1d2d3d4d5 are the rst 5 digits of your student number.
a) Graph (sketch) the optimal value of the objective function as a function of c1 for all
c1 2 ( 1;1). Use the LINDO package or any other software but provide a printout of at
least one input and one output. Begin with c1 = 0 and use ranging to determine an interval
for c1 for which you know the answer. Ranging gives you the interval in which the optimal
basis B is unchanged and the value for x1 in the optimal solution gives the slope (Why?). Now
choose a c1 outside this interval and repeat. Continue until you know the optimal values for
all possible c1. You might need as many as nine intervals or as few as two intervals depending
on your student number.
b) Consider the optimal value of the objective function as a function of the value c1, say
f(c1). Show that f(c1) is a concave upwards function.
3. (from an old exam) If you are given an optimal primal solution x to an LP and you wish to
deduce an optimal dual solution y , then you might try to determine y using
(1) Complementary Slackness of y with x .
(2) y satis es constraints (including positivity constraints if any) in dual, i.e. y is a
feasible solution of the dual..
Many of our examples in class and quizzes yielded unique optimal y but in general there
may be many optimal dual solutions. Are all y satisfying (1),(2) optimal to the dual? Is
every optimal dual solution determined as a solution to (1),(2)? Explain.
4. Let A be an m n matrix with A 0 and each column of A has a non-zero positive entry.
Let b 0. Then show that the LP
maxc x
Ax b
x 0
always has an optimal solution.
5.
a) Show there is an x 0 with Ax would
generally mean and6= but this is not true for matrices or vectors. A vector x might satisfy
x 0 and also x6= 0 and yet still have some 0 entries. Such a vector x with 0 entries has
x6>0.
b) Let A be an m n matrix. Prove that either:
i) there exists an x 0 with Ax < 0 or
ii) there exists y 0 with ATy 0 and y6= 0
but not both.
Hint: Extend the idea in a) and use it in setting up a primal dual pair.