Take-Home Exam I
IE 501 - Linear Programming and Extensions
Due: May 28, 2018 at 11:55pm
Question 1 (15 points)
The starting and current tableaux of a given problem are shown below. Find the values of the
unknowns a through n.
Question 2 (20 points)
Consider the following linear programming problem:
min 4𝑥1 + 2𝑥2 + 5𝑥3
s.t.
𝑥1 + 𝛼𝑥2 + 𝑥3 ≥ 430
3𝑥1 + 2𝑥3 ≤ 460
𝑥1 + 4𝑥2 ≤ 420
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
where α is an unknown coefficient. Let e1 be the excess variable for the first constraint and a1 be
the artificial variable for the first constraint. Let s2 and s3 be the slack variables for the second and
third constraints, respectively. The final optimal tableau is given below. Note that the column
corresponding to the artificial variable a1 has been deleted.
z x1 x2 x3 e1 s2 s3 RHS
z 1 c1 0 0 c2 0 -2 1310
x3 0 d1 0 1 -1 0 -0.5 b1
s2 0 d2 0 0 2 1 1 b2
x2 0 d3 1 0 0 0 0.25 b3
1
(a) (5 points) Find the inverse of the optimal basis, that is B−1, and the values of each basic
variable. Also find the value of α.
(b) (5 points) What is the range of values for the right hand side of the first constraint for which
the current basis remains optimal?
(c) (5 points) Compute the values for b1, b2, b3, c1, c2, d1, d2, and d3 and conclude that current
tableau is indeed optimal and that its associated basic feasible solution is the unique optimal
solution.
(d) (5 points) Suppose now that we want to minimize the objective function z = (4 − 2θ) x1 + (2 +
θ) x2 + (5 + 3θ) x3, where θ is a scalar, subject to the same constraints. What is the range of
values of θ for which the current basis remains optimal?
Question 3 (15 points)
Consider the following LP:
max x1 - x2
s.t.
5x1 - x2 ≥ 5
x1 - 2x2 ≤ 12
2x1 + x2 ≤ 4
x1 ≥ 0
x2 ≤ 0
Suppose that in the optimal solution x1, x2 and e1 are the basic variables where e1 is the
excess/surplus variable associated with the first constraint. Use complementary slackness to find
the optimal values of the dual variables.
Question 4 (20 points)
Consider the following LP:
(a) (10 points) Write the dual problem and verify that (w1, w2) = (4, 5) is a feasible solution.
(b) (10 points) Use the information in Part (a) to derive an optimal solution to both the primal
and the dual problems.
2
Question 5 (30 points)
For each of the following statements, state whether it is true or false. If true, provide a proof, else,
provide a counter-example.
(a) (10 points) The following linear program is infeasible if and only if its dual is unbounded.
max 𝑐𝑇 𝑥
s.t.
𝐴𝑥 ≤ 𝑏
0≤𝑥≤𝑑
(b) (10 points) If {𝑥 ∈ 𝑅𝑛 ∶ 𝐴𝑥 = 0, 𝑥 ≥ 0} = {𝟎}, then there exists 𝑦 ∈ 𝑅𝑚 such that 𝑦 𝑇 𝐴 > 0.
(c) (10 points) If the problem: Minimize cTx subject to Ax = b and x ≥ 0 has a finite
optimal solution, then the new problem: Minimize cTx subject to Ax = b’ and x ≥ 0
cannot be unbounded, no matter what value the vector b’ might take.