TABLE 4.1

In this question, you do not need to show your work for converting an LP into another equivalent form, and do not need to show the derivation of any dual. By the dual of an LP here, we mean the dual obtained by using Table 4.1 from the textbook. (a) Consider the following LP (P) over the variables I ER, U ERK: max such that idual (PL) Ac > b Dr - Fu 0, where A Rmx, De Rkxn, and F eRkxk are matrices, and ceR, b ER", and d Rk are vectors. Let the LP (P/) be the result of converting (P) to SEF by substituting the non-positive variables with non-negative ones, and then adding or subtracting one non-negative slack variable cach from the LHS of the constraints (1) and (2) as necessary. Show that the dual LPs (D) and (D) of (P) and (P), respectively, are the same up to renaming the variables. (b) Consider the following LP (P2) in SEF over the variables r ER": max {c r: Az =b, 1 >0} , (P2) where c ER", A E Rmxn, and b E RM Let (P) be the LP obtained by replacing the con- straint Ar b by constraints Ar 0 variable constraint free variable > constraint 0 variable > constraint free variable =constraint 50 variable constraint min subject to Ar? x? AY? y? neral Primal LP Its dual according to the table: In this question, you do not need to show your work for converting an LP into another equivalent form, and do not need to show the derivation of any dual. By the dual of an LP here, we mean the dual obtained by using Table 4.1 from the textbook. (a) Consider the following LP (P) over the variables I ER, U ERK: max such that idual (PL) Ac > b Dr - Fu 0, where A Rmx, De Rkxn, and F eRkxk are matrices, and ceR, b ER", and d Rk are vectors. Let the LP (P/) be the result of converting (P) to SEF by substituting the non-positive variables with non-negative ones, and then adding or subtracting one non-negative slack variable cach from the LHS of the constraints (1) and (2) as necessary. Show that the dual LPs (D) and (D) of (P) and (P), respectively, are the same up to renaming the variables. (b) Consider the following LP (P2) in SEF over the variables r ER": max {c r: Az =b, 1 >0} , (P2) where c ER", A E Rmxn, and b E RM Let (P) be the LP obtained by replacing the con- straint Ar b by constraints Ar 0 variable constraint free variable > constraint 0 variable > constraint free variable =constraint 50 variable constraint min subject to Ar? x? AY? y? neral Primal LP Its dual according to the table