Exercise 37 Optimality conditions Consider a feasible soluti

Exercise 3.7 (Optimality conditions) Consider a feasible solution x to a standard form problem, and let Z = {i | xi = 0}. Show that x is an optimal solution if and only if the linear programming problem minimize c?d subject to Ad = 0 di > = 0, i element of Z has an optimal cost of zero. (In this sense, deciding optimality is equivalent to solving a new linear programming problem.)

Solution

Here A is an mxn matrix and d is an m dimensional vector and c is an n dimensional vector.

now Z = {x}   and its given that x_i=0

so Z will have values {0,0,0,0......x_i=0}

and in our constraints are Ad=0 and d_i >= 0 , i E Z

so i will only take 0 as a value as set Z is a null set

so d_i = 0

now Ad=0

hence the function c\'d is optimal when the cost vector is zero

therefore x is the optimal solution.