0

I'm trying to study for a linear programming exam and I came across this statement:

"For a linear program in standard form with coefficient matrix A, if the cost vector c belongs to the row space of A then every feasible solution is optimal."

I understand kind of intuitively that it's true but thoroughly. Can anyone offer a more formal proof of why? Or at least help me wrap my head around it more concretely.

JB Sithebe
  • 1

1 Answers1

1

Suppose $A$ is $m \times n$ and your LP is to minimize $cx$ subject to $Ax=b$. You are given that there exists $y\in \mathbb{R}^m$ such that $y A = c$. Let $x\in \mathbb{R}^n$ be an arbitrary feasible solution. Then $$cx = (yA)x = yAx = y(Ax) = yb,$$ which does not depend on $x$. That is, every feasible solution has the same objective value $yb$.

RobPratt
  • 45,619