For eachb inRm, let ξ(b) denote the optimal objective function value for
the following linear program:
maximize c' x
subject toAx ≤ b
x ≥ 0.
Suppose thatξ(b) < ∞ for all b. Show that the function ξ(b) is concave (a
function f on Rm is called concave if f(tx+(1−t)y) ≥ tf (x)+(1−t)f(y)
for all x and y in Rm and all 0 < t < 1). Hint: Consider the dual problem.
Isn't there only one objective value? Not one for each b value?