APM236 HW51
Due date: Sat, Nov 29 (before 9pm) on Crowdmark.
In relation to payoff function in game theory being negative:
“It might as well be me beacuse I have nothing to lose, less than noting, in fact.”
from the book Nickel and Dimed (on not getting by in America) by Barbara Ehrenreich
(1) [From winter 2024 final] Consider the following LPP:
minimize x1 + 2x2
subject to −x1 + x2 ≥ 1
x1 + x2 ≤ 3
x1 ≥ 0
x2 free
(a) Find the dual of this LPP. You can use the table at bottom.
(b) Use graphical analysis to find the optimal solution to the dual maximization problem. What is
the maximum value of the objective function?
(c) Write down the complementary slackness conditions for this problem. (You should have 4
equations.)
(d) Use the complementary slackness conditions to find an optimal solution to the primal minimiza-
tion problem. What is the minimum value of the objective function?
(2) Recall the following LPP from HW4 Q3:
maximize
c
2
x1 + cx2
subject to x1 + x2 ≤ 2b
x1 − x2 ≥ b
x1, x2 ≥ 0,
where c > 0 and b > 0. Suppose this LPP has an optimal solution.
(a) Find the dual of this problem.here x4 = x5 + 236 so find the basic solutions
(b) Use complementary slackness and the solution to Q3 on HW4 to find solution(s) to the dual LPP.
(3) Consider the following LPP from Q6b on HW4 where a = 2:
minimize z
subject to z ≥ −2q + 4(1− q)
z ≥ 2q − 4(1− q)
q ≤ 1
q ≥ 0
z free
(a) Find the dual of this problem and solve it graphically. Hint: after finding the dual you can
simplify it by using one of the equations to eliminate one of the dual variables.
(b) Use complementary slackness to find the solution to the primal LPP. Do you get the same
answer you found on Q6 of HW4?
1Copyright©2025 J. Korman. Sharing or selling this material without permission of author is a copyright violation.
1
(4) Consider the following LPP where all the constants ci are positive:
maximize
∑n
i=2(−1)icixi
subject to xi ≤ i2 for i = 1, . . . , n
xi ≥ 0 for i = 2, . . . , n.
Note that x1 is free. and x1 = 4− x2
(a) Find a formula for the optimal cost. Hint: consider the cases when n is even and then the cases
when it is odd.
(b) Write the dual and find an optimal solution to the dual. Note: the matrix A is an n×n matrix:
n constraints with n variables.
(c) Use complementary slackness and the solution(s) you found in part (b) to find primal optimal
solution(s). Do you get the same answer you found in part (a)?
(5) Recall Q4 on HW4 where Let (a1, b1) = (−3, 0), (a2, b2) = (5, 4) ∈ R2 be two points in the plane.
Supopse we are trying to find a line L through the origin with equation y = αx, such that the sum
of the vertical distances from the points (ai, bi) to L is minimized. Here you can assume α ≥ 0. We
set up the following piecewise linear convex problem:
min
α≥0
2∑
i=1
|αai − bi|
Note that here α is the variable.
(a) Write this problem as a linear programming problem. Note: this is the same LPP you already
formulated in HW4.
(b) Find and solve the dual of your LPP from part (a).
(6) An n × n matrix A with entries aij is called stochastic if all of its entries are nonnegative and the
sum of the entries in each row is one; i.e.,
n∑
j=1
aij = 1 ∀i.
Use duality to show that if A is a stochastic matrix, then there is some p ≥ 0 that solves the system
of equations pTA = pT (i.e., pT is a left eigenvector of A with eigenvalue 1). If you know about
Markov chains, this is useful when showing existence of stationary distributions.
Hint: Phrase this as a linear programming problem and find its dual, and then comment on
feasibility and boundedness of both problems using duality theorems.
Table for converting a primal LPP to a dual LPP:
Here A is a matrix whose rows are aTi and whose columns are Aj .
PRIMAL DUAL
minimize cTx maximize bTp
aTi x ≥ bi pi ≥ 0
aTi x ≤ bi pi ≤ 0
aTi x = bi pi free
xj ≥ 0 pTAj ≤ cj
xj ≤ 0 pTAj ≥ cj
xj free p
TAj = cj

学霸联盟