Question

(20 points) Consider the linear program

max cT (x) s.t. Ax<=b (1)
x∈Rn
where A is a square invertible matrix. Show the optimal value is
ct (A-1).(b) if
(AT )-1. c >=0 and +[infinity] otherwise.

Answer 1

To show the optimal value of a linear program with an invertible matrix, we consider the dual problem and use the inverse of the matrix. If a condition is met, the optimal value is calculated using the inverse matrix. Otherwise, it is +∞.

Step-by-step explanation:

To show the optimal value of the given linear program, we need to consider the dual problem. The dual problem is min bT (y) s.t. AT (y)>=c, where y is the vector of dual variables. Since A is a square invertible matrix, its inverse exists. Let's denote its inverse as A-1. The optimal value of the dual problem is given by cT (A-1) (b).

If (AT)-1 c >= 0, then the optimal value of the original linear program is cT (A-1) (b). Otherwise, it is +∞.