Consider the following primal-dual pair of linear programs Minimize Z = cx aximize V 6...

Transcribed Image Text:

Consider the following primal-dual pair of linear programs Minimize Z = cx Мaximize V — 6"у (P){ Subject to Ax > b Subject to ATy < cT (D) x > 0 y > 0 Let x and y be feasible solutions for (P) and (D) respectively. Show that a necessary and sufficient condition for both solutions to be optimal (for (P) and (D) respectively) is that we have (i) x; > 0 → a1jY1+a2;Y2+...+ amjYm = C; Vj = 1, 2, n .... (2) a1jY1 + a2jY2 + . . + amjYm < Cj → x; = 0 Vj = 1, 2, n .... (iii) Yi > 0 → a;1x1+a;2x2 + ...+ ain&n = bị Vi = 1, 2, ..., m (iv) A¡1X1+ A¿2X2 +..+ ainXn > b; → Yi = 0 Vi = 1, 2, ..., m Consider the following primal-dual pair of linear programs Minimize Z = cx Мaximize V — 6"у (P){ Subject to Ax > b Subject to ATy < cT (D) x > 0 y > 0 Let x and y be feasible solutions for (P) and (D) respectively. Show that a necessary and sufficient condition for both solutions to be optimal (for (P) and (D) respectively) is that we have (i) x; > 0 → a1jY1+a2;Y2+...+ amjYm = C; Vj = 1, 2, n .... (2) a1jY1 + a2jY2 + . . + amjYm < Cj → x; = 0 Vj = 1, 2, n .... (iii) Yi > 0 → a;1x1+a;2x2 + ...+ ain&n = bị Vi = 1, 2, ..., m (iv) A¡1X1+ A¿2X2 +..+ ainXn > b; → Yi = 0 Vi = 1, 2, ..., m

Answer rating: 100% (QA)

By Weak duallity Theorem that states The objective function Value for ... View the full answer