Explore BrainMass

Linear Programming Problem : key information

Let A be a symmetric square matrix. Consider the linear programming problem
Minimize C'X
such that AX >= C and X >= 0
Prove that if X* satisfies AC*=C and X*>=0, then X* is an optimal solution.

Solution Preview

We are given the linear programming problem:
Minimize C'X
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* ...

Solution Summary

This solution thoroughly demonstrates an optimal solution.