Spring 2021 ESI 6417: Linear Programming & Network Optimization Homework 3
Homework 3
Instructor: Aleksandr M. Kazachkov
Version March 21, 2021
Due Tuesday, March 30, 2021 at 11:59pm ET
Instructions. The assignment is to be submitted individually. The point value is shown at the start of each question. Please submit the pdf file of your solutions, not the LATEX source or auxiliary files. As always, this homework cannot be shared with anyone outside the class.
You should first attempt each question seriously using only the class notes.
If you do not succeed in solving a question that way, request input from me or your classmates. If afterwards you still could avail of more help, you are allowed to use online resources. In all cases, you must properly attribute your sources.
However, do not copy directly from external sources. Try to understand every part of the source, and then close it and set the problem aside for some time. When you return to answer the question, see if you can do it without consulting that source. If you still are puzzled at that point, return to the step of consulting me or your classmates.
3.1 (25 points) Suppose you are given c ∈ Rn, A ∈ Rm×n, and b ∈ Rm, with rank(A) = m. Define P .= {x ∈ Rn : Ax = b, x ≥ 0}. Consider the linear program
min cTx. x∈P
(1)
Suppose that B is a feasible basis to (1), and let N .= [n] \ B. We assume (without
loss of generality) that B = [m]. Let AB denote the columns of A indexed by B. Define
x ̄ .= (A−1b,0) and u ̄ .= cT A−1. For every j ∈ [n], let c ̄ .= c −u ̄TA , where A is column j
j j ·j ·j
of matrix A. In this problem, we will revisit some aspects of the simplex method from class.
BBB
(a) (1point)Showthatc ̄ =0forallj∈B. j
(b) (4 points) The vector c ̄ is known as the reduced cost vector. One way to see its relevance
is to plug in the tableau corresponding to B into the objective function: from Ax = b,
we split into ABxB + AN xN = b, then multiply by A−1 on both sides to obtain B
xB =A−1b−A−1ANxN. BB
Use this to write the objective function cTx as function of only the nonbasic variables,
and simplify the expression (collect all xN terms, and substitute in u ̄ or c ̄ as appropri-
ate). What can you conclude about the optimal solution and value of (1) compared to
min {c ̄ x : x ∈ P}? x
(c) (1 point) Write down the dual to (1).
(d) (5 points) Prove that if c ̄ ≥ 0 for all j ∈ N , then x ̄ is an optimal solution to (1). Also
prove that u ̄ is an optimal solution to the dual.
Hint: Show that u ̄ is dual feasible, then apply strong duality.
(e) (4 points) Suppose that c ̄ ≥ 0, so that B is optimal. Moreover, assume that x ̄j > 0 for all j ∈ B, which is the definition of not having primal degeneracy. How would you use the reduced costs to determine whether there exists an alternative optimal solution x′ ̸= x ̄? State this as a “necessary and sufficient condition”, i.e., prove that if your condition holds, then there exists a distinct (from x ̄) optimal solution, and if the condition does not hold, then x ̄ is the unique optimum. This is known as dual degeneracy.
T
j
1
Spring 2021 ESI 6417: Linear Programming & Network Optimization Homework 3
(f) (10 points) Show that it is possible to have a basis B for which the corresponding point x ̄isoptimalbutc ̄k <0forsomek∈[n].
Hint: Recall that in the simplex method, after an improving direction is found, the maximum distance along that improving direction needs to be calculated. You can either give a worked- out example, or describe the situation algebraically.
3.2 (25 points) Let P ⊂ R2 be the following region:
(x1,x2): −x1+x2≤0
P .=
x 2 ≤ 1 x1 + x2 ≤ 3 x 1 , x 2 ≥ 0
.
In this exercise, you will practice with simplex operations.
(a) (2 points) Draw the feasible region P . You can include a scanned picture if it saves you time (though adapting your previous TikZ code may be quicker).
(b) (1 point) List the extreme points and extreme rays of this polyhedron.
(c) (1point)WriteP instandardform,asapolyhedronQ.={x∈R5 :Ax=b,x≥0};
that is, you need to add slack variables x3, x4, and x5, and define A and b appropriately.
(d) (2 points) The point (x ̄1, x ̄2) = (2, 1) belongs to P . Give the corresponding point that
belongs to Q, and find a basis B ⊆ [5] for Q for this point.
Hint: The picture of P can help you infer what variables (in Q) are basic. The insight is
that inactive constraints have strictly positive slack, and positive variables in Q are basic.1
(e) (2 points) Let c .= (−1, −2, 0, 0, 0) and consider the linear program minx∈Q cT x. Show
that the point in Q with x ̄1 = 2 and x ̄2 = 1 is optimal by calculating the reduced costs.
(f) (7 points) If instead c .= (−2, −1, 0, 0, 0), starting at the basis B you identified in (d), find a variable to enter the variable, a variable to exit the basis, a ray corresponding to an improving direction, the distance you will go along that ray to reach the next basic solution, and the coordinates of this new basic solution. Hint: It may be helpful to afterwards look at what the improving direction looks like in your picture from part (a).
(g) (10 points) Let us return to the generic linear program given in (1), and let B be an optimal basis for the problem, in which c ̄ ≥ 0 for all j ∈ [n]. Suppose we are given
j
∆ ∈ Rn and define a new objective vector d .= c + ∆, so that we would like to solve
minx{dTx : x ∈ P}. Given the optimal basis B for (1), if ∆B = 0, what values can ∆k, k ∈ N , take such that B continues to be optimal for the new LP?
Hint: Look at the reduced cost vector for d with respect to B.
1Note that there is a modification of the simplex method in which this is not true, in which we allow variables to be nonbasic if they are either at their lower or upper bounds.
2