Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
APM236: Homework 21
Due: Sat Feb 3 (before 9pm) on Crowdmark
In reference to the the lumber mill production problem:
“Ceder unstintingly provided for the people, who responded with gratitude and reciprocity, To-
day, when cedar is mistaken for a commodity from the lumberyard, the idea of gift is almost lost.
What can we who recognize the debt possibly give back?”
from the book Braiding Sweetgrass by Robin Wall Kimmerer
(1) Explain why the two differently looking problems below are in fact the same problem:
minimize x− 2y + z
subject to x+ y + 2z − 1 = 0
x, y, z ≥ 0
and
minimize 2x− y + 3z − 1
subject to x+ y + 2z − 1 = 0
x, y, z ≥ 0
Note: this is a very easy problem.
Remark: this example shows that there are different ways to write the cost function of a LPP.
(2) (a) Express the following optimization problem as an equivalent LPP:
minimize 236x+ y
subject to |y|+ |x+ y| ≤ 2024
Hint: You will need to express the inequality in another way so that there are no
absolute value signs. For example the inequality |x| ≤ 3 is equivalent to the pair of
inequlities x ≤ 3 and x ≥ −3.
(b) Explain why the following optimization problem is not equivalent to a LPP:
minimize 236x+ y
subject to |y|+ |x+ y| = 2024
Hint: for a LPP we know the feasible set is alway convex.
(3) In the game “paper, scissors, rock” there are two players: player I and player II. Each player
chooses one of the three objects: paper, scissors, or rock. The payoff to player I is given by
the following table:
1
II/I paper scissors rock
paper 0 −1 1
scissors 1 0 −1
rock −1 1 0
As we will learn later in this course, there is an important number V called the value of
the game. To compute the value of the game “paper, scissors, rock” we will use the formula
V = min
q1+q2+q3=1
q,q2,q3≥0
max{q3 − q2, q1 − q3, q2 − q1}.
That is, V is the optimal value of the following piecewise linear convex optimization
problem:
minimize f(q1, q2, q3)
subject to q1 + q2 + q3 = 1
q1, q2, q3 ≥ 0
where f(q1, q2, q3) = max{q3 − q2, q1 − q3, q2 − q1}.
(a) Convert this piecewise linear convex optimization problem into a LPP by introducing
a new variable z.
(b) Find the optimal value of the LPP in part (a).
(c) Find the optimal solution to the LPP in part (a). Hint: from part (b) you know the
value of the optimal solution.
Note: in parts (b) and (c) you do not need to follow any particular method. You can just
guess the solution and then prove that your guess is correct.
Remark: The optimal solution is the optimal strategy player I would play to win the game.
(4) Consider the following (piecewise linear) minimization problem where (x, y, z) ∈ R3:
minimize |y − z|+ |x− y + z|
subject to y + z ≤ 1
z ≥ 2
(a) Solve this problem graphically. Hint: try to find a way to graph this problem (or an
equivalent problem) in R2. Note that there is no constraint on x.
(b) Convert this problem into a Linear Programming Problem by introducing a new vari-
able u. Hint: express the cost function as a linear function without the absolute values.
(5) Consider the set
B˜2 =
{(
x11 x12
x21 x22
)
| xij ≥ 0 for i, j = 1, 2 , x11 + x12 = 2, x21 + x22 = 2, x11 + x21 = 1.5, x12 + x22 = 2.5
}
.
Identify the extreme points of B˜2 and then prove that B˜2 is a convex polytope. That is
prove that any point of B˜2 is a convex combination of its (two) extreme points.
(6) Consider the problem of minimizing c1x1+ c2x2+ c3x3 subject to the constraints x1+x2+
4x3 = 12, 6 ≥ x1 ≥ 0, x3 ≥ 0, and x2 ≥ 0.
(a) Graph the feasible set in R3.
(b) Convert this problem to an equivalent problem in canonical form. Write your final
answer in the form Ax = b,x ≥ 0 where the rows of the matrix A are linearly
independent.
(c) If (c1, c2, c3) = (1, 2,−1), use graphical analysis to find an optimal solution to this
minimization problem.
(7) Consider the LPP of minimizing x1+x2−2x3 subject to the constraints 2x1+9x2+x3 ≤ 18,
x1 ≥ 0, x2 ≥ 0, and 6 ≥ x3 ≥ 1.
(a) Graph the feasible set in R3.
(b) Using your graph from part (a) identify all the extreme points. Note: you do not need
to prove that these are extreme points, it’s ok here to rely on your geometric intutition.
(c) Solve the minimization problem by calculating the value of the objective function at
all the extreme points. Note: see the extreme point theorem [KB] Thm 1.7.
The following problems are for practice only and are not to be turned in.
• Let S ⊆ Rn × R and consider it’s projection onto R: S = {y ∈ R | (x, y) ∈ S for some x ∈
Rn}.
(1) Assuming S is convex, prove that S is convex.
(2) Suppose S is convex for some set S. Does it mean that the set S is convex? Prove or
give a counterexample.
• Consider the following very simple LPP (with feasible set Ω):
maximize z = x
subject to x ≤ 2
Recall that by adding a slack variable s we can change this LPP into the form (with feasible
set Ω′):
maximize z′ = 1x+ 0s
subject to x+ s = 2
s ≥ 0
We mentioned in lectures these two forms are equivalent. To see that they are equivalent,
consider the linear map f : Ω′ → Ω given by f(x, s) = x. Note that f is a bijection between
Ω′ and Ω. Note that z(f(x, s)) = z′(x, s). That is, the cost z′ of the second form at the
point (x, s) is the same as the cost z of the first form at the point f(x, s). This shows that
the two forms are equivalent (make sure you understand why).
Now try to do something similar for the following standard form LPP (with feasible set
Ω):
maximize z = x+ y
subject to x+ y ≤ 2
y − x ≤ 0
x, y ≥ 0
That is, convert this problem into canonical form (with feasible set Ω′) by adding two
slack variables s and t and show that there is a linear bijection f : Ω′ → Ω such that
z(f(x, y, s, t)) = z′(x, y, s, t).
• Conside the set of solutions to a system of linear equations {x ∈ Rn | Ax = b}. Assuming
the set is not empty, is this set a polytope, a polyhedron, or neither? Prove your claim.
The following problem is about linear functions: Rn → R.
• (a) Let a be a (column) vector in Rn. Show that the function f(x) = aTx is a linear
function from Rn to R.
(b) Show that any linear function f : Rn → R is of the form f(x) = aTx for some
vector a ∈ Rn. Hint: let ei denote the standard unit vectors in Rn and write x as
x = x1e1 + · · ·+ enxn. Let ai := f(ei) ∈ R. What is f(x1e1 + · · ·+ enxn)?
(c) Let aT = (1,−2). Draw (in R2) the level sets of the linear function f(x) = aTx =
(1,−2)
(
x1
x2
)
= x1 − 2x2. Separately, draw the sets {x ∈ R2 | aTx = 0} and {x ∈ R2 |
aTx ≥ 0}.
(d) Let aT = (−1, 1, 0). Describe in words the level sets (in R3) of the linear function
g(x) = aTx = (−1, 1, 0)
x1x2
x3
= −x1+x2. Describe in words the sets {x ∈ R3 | aTx =
0} and {x ∈ R3 | aTx ≥ 0}.