IEOR 4004
Practice 1
1. Consider the linear program
max 15×1 + 6×2 3×3 + 8×4
Subject to
2×1 1
5
x2 + 2×3 + 5×4 + 4×5 ≤ 20
1
2
x1 + 2×2 + x3 + 8×4 ≤ 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 4×1 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 8×1 + x2 + x3 + x4
Subject To
2×1 + 5×2 3×3 + 4×4 + x5 = 10
x2 + 8×3 + 6×4 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
