Showing that a Linear Program has an optimal solution given a condition

Asked Mar 29 '17 at 16:27

Active Mar 29 '17 at 16:27

Viewed 82 times

I was asked the following question on my linear programming midterm:

Consider the following linear program: $$ \text{max } c^{T}x \\ \text{s.t. } Ax \leq b $$

where A is a square $ n \times n $ matrix of full rank. Show that this linear program has an optimal solution if and only if $ (A^{T})^{-1}c \geq 0 $ and in this case the optimal value is $ b^{T}(A^{T})^{-1}c $ (Hint: Consider the dual problem. Observe that x variables are not constrained to be nonnegative)

This was my answer which received little credit:

Since all x variables are free all constraints in dual are equalities.

That is $ A^{T}y = c $ so $ y = (A^{T})^{-1}c $ and $ y $ must be $\geq$ 0 for complementary slackness to hold and an optimal solution to exist.

Also it is easy to see that $ b^{T}(A^{T})^{-1}c $ is the optimal value.

asked Mar 29 '17 at 16:27

Omar Wali

You should say why you see that $b^T(A^T)^{-1}$ is the optimal value. Did you wrote down the dual program ? – callculus42 Mar 29 '17 at 16:48
is this given by strong duality? – Omar Wali Mar 29 '17 at 16:51
1

Did you wrote down the dual program ? – callculus42 Mar 29 '17 at 16:52
That was my answer verbatim from my exam, i did not explicitly identify the dual program, no. – Omar Wali Mar 29 '17 at 17:00
That´s maybe the reason. But the best thing you can do is to ask the lecturer. – callculus42 Mar 29 '17 at 17:47

Showing that a Linear Program has an optimal solution given a condition

0 Answers0