Let A be a symmetric square matrix. Consider the linear programming problem
such that AX >= C and X >= 0
Prove that if X* satisfies AC*=C and X*>=0, then X* is an optimal solution.
We are given the linear programming problem:
such that AX >= C, and X >= 0,
where A is a symmetric square matrix.
Note that C' is the transpose of C, where C is the column vector corresponding to the right hand side (RHS) of the constraints. C' is merely the row vector with the same entries as C.
Also, since A is a symmetric square matrix, the transpose of A is A itself. That is, A' = A.
Now, it is given that X* ...
This solution thoroughly demonstrates an optimal solution.