CLRS 29-2 Complementary slackness describes a relationship between the values of the primal variables and the dual constraints and between the values of the dual variables and the primal constraints. Let x be a feasible solution to the primal linear program given in (29.16)- (29.18) in the text, and let y be a feasible solution to the dual linear program given in (29.83)-(29.85) in the text. Complementary slackness states that the following conditions are necessary and sufficient for x and y to be optimal: a) Verify that complementary slackness holds for the linear program in lines (29.53)- (29.57) in the text. b)Prove that complementary slackness holds for any primal linear program and its corresponding dual. c) Prove that a feasible solution x to a primal linear program given in lines (29.16)-(29.18) is optimal if and only if there exist values y = (y1; y2; : : : ; ym) such that i. y us a feasible solution to the dual linear program given in (29.83)-(29.85), ii. Σm i=1 aijyi = cj for all j such that xj > 0, and iii. yi = 0 for all i such that Σn j=1 aijxj < bi.