Linear Algebra and Its Applications · Problem 8.3.10

Linear Programming and Game Theory — Gilbert Strang

Mathematics · linear-programming-duality-equality-constraints

Problem

If the primal problem is constrained by equations instead of inequalities---Minimize cxcx subject to Ax=bAx = b and x≥0x \geq 0---then the requirement y≥0y \geq 0 is left out of the dual: Maximize ybyb subject to yA≤cyA \leq c. Show that the one-sided inequality yb≤cxyb \leq cx still holds. Why was y≥0y \geq 0 needed in equation (1) but not here? This weak duality can be completed to full duality.

Related theory

Browse the problem library