IEOR 4004
Practice 1
1. Consider the linear program
max 15x1 + 6x2 − 3x3 + 8x4
Subject to
2x1 − 1
5
x2 + 2x3 + 5x4 + 4x5 ≤ 20
1
2
x1 + 2x2 + x3 + 8x4 ≤ 10
x ≥ 0.
Consider the basic solution consisting of variables 1 and 3.
(a) Verify that the basis inverse equals [
1 −2
−1/2 2
]
(b) Write down the tableau for this basis
(c) Is the basic solution feasible?
(d) Argue that the tableau does not show optimality.
(e) Change the objective vector as little as possible so as to make the tableau optimal.
(f) What are the optimal dual variables (after the change in (e)).
2. Consider the optimization problem (on two variables)
min −ln (20− 4x1 − x2)
Subject to
x1 + x2 ≤ 10
x ≥ 0.
(a) Draw a picture of the feasible region. Show the subset of the feasible region where the objective
is well-defined.
(b) Prove that the objective is convex in the subset of the feasible region where it is well-defined.
(c) Consider the point (3, 0). Suppose we move away from (3, 0) in the direction of (1,−1), i.e.
we consider the points of the form (3 + s,−s) for s ≥ 0. Draw this direction. Is this a feasible
direction?
(d) Same as (c) but now we are at the point (3, 3). Is the direction (1,−1) feasible? Is it a descent
direction?
3. Consider the LP
1
max 8x1 + x2 + x3 + x4
Subject To
2x1 + 5x2 − 3x3 + 4x4 + x5 = 10
−x2 + 8x3 + 6x4 − x6 = 2
x1 + x3 = 17
x2 + x4 + x7 = 30
x ≥ 0.
(a) Write the dual.
(b) Suppose the basic variables are (2, 3, 6, 7). In that case the inverse basis matrix is
0.2 0 0.6 0
0 0 1 0
−0.2 −1 7.4 0
−0.2 0 −0.6 1

(b.1) What are the values of the basic variables?
(b.2) In the tableau for this basic solution, what are the matrix coefficients for the nonbasic
variables?
(b.3) In the tableau for this basic solution, what are the objective coefficients for the nonbasic
solutions?
(b.4) Suppose we pivot in x5. Do we get an optimal solution? If so, what are the optimal dual
variables (extra credit)?
(b.5) Suppose that, instead, we pivot in x1. Do we get an optimal solution? If so, what are the
optimal dual variables (extra credit)?
4. Consider the optimization problem (on three variables)
min ex1+x2 + 106(x3 − 10)−2
Subject to
x1 + x2 ≥ 4
x3 ≤ 9.5
x ≥ 0.
(a) Is the point (5, 5, 5)T optimal? If not optimal, prove using a gradient argument.
(b) Is the objective funtion convex?
(c) Is the point (2, 2, 0)T optimal? If not, can you find a feasible descent direction that keeps x3
fixed at 0?