compx530 Assignment 1 s2 2025
Problem 1. For a given vector b ∈ R2, we define a polyhedron Pb = {x ∈ R2 :
Ax = b, x ≥ 0} where
A =
[
1 2
3 1
]
.
Let Q = {b ∈ R2 : Pb ̸= ∅}. Your task is to
Prove that Q is a polyhedron.a)
Provide an explicit formulation (list the constraints) for Q.b)
Problem 2. Suppose your friend designs a super fast algorithm for solving LPs
having the following special form
minimize c · x
subject to Ax ≥ b
Sadly all the LPs you need to solve are in standard form. Before you can use this
new algorithm, you need to come up with a reduction from LPs in standard form
to LPs in special form. Your task is to
Provide a reduction from standard form to special form.a)
Give a short argument to justify that your reduction is sound.b)
Problem 3. Recall that a basis B of a linear program in standard form
minimize c · x
subject to Ax = b
x ≥ 0
is said to be non-degenerate if xB = A−1B b > 0.
Your task is to provide a counter-example for each of the following claims:
If a linear program in standard admits two non-degenerate bases, then there
exists an infinite number of non-degenerate bases.
a)
If a feasible linear program in standard form has exactly one equality con-
straint, then there is always a non-degenerate basic feasible solution.
b)
If a linear program in standard form has multiple optimal solutions, then it
must have at least one degenerate basis.
c)
1

学霸联盟