Exercise 44 Let A be a symmetric square matrix Consider the

Exercise 4.4 Let A be a symmetric square matrix. Consider the linear pro gramming problem minimize c?x subject to Ax greater than equal to c x greater than equal to o. Prove that if x* satisfies Ax* = c and x? greater than equal to 0, then x* is an optimal solution.

Solution

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.

then Ax* = c when x*>0 , then x* is an optimal solution