Linear Programming Notes V Problem Transformations 1 Introduction Any linear programming problem can be rewritten in either of two standard forms In the first form the objective is to maximize the material constraints are all of the form linear expression constant ai x bi and all variables are constrained to be non negative In symbols this form is max c x subject to Ax b x 0 In the second form the objective is to maximize the material constraints are all of the form linear expression constant ai x bi and all variables are constrained to be non negative In symbols this form is max c x subject to Ax b x 0 In this formulation but not the first we can take b 0 Note The c A b in the first problem are not the same as the c A b in the second problem In order to rewrite the problem I need to introduce a small number of transformations I ll explain them in these notes 2 Equivalent Representations When I say that I can rewrite a linear programming problem I mean that I can find a representation that contains exactly the same information For example the expression 2x 8 is equivalent to the expression x 4 They both describe the same fact about x In general an equivalent representation of a linear programming problem will be one that contains exactly the same information as the original problem Solving one will immediately give you the solution to the other When I claim that I can write any linear programming problem in a standard form I need to demonstrate that I can make several kinds of transformation change a minimization problem to a maximization problem replace a constraint of the form ai x bi by an equation or equations replace a constraint of the form ai x bi by an equation or equations replace a constraint of the form ai x bi by an inequality or inequalities replace a variable that is not explicitly constrained to be non negative by a variable or variables so constrained If I can do all that then I can write any problem in either of the desired forms 1 3 Rewriting the Objective Function The objective will be either to maximize or to minimize If you start with a maximization problem then there is nothing to change If you start with a minimization problem say min f x subject to x S then an equivalent maximization problem is max f x subject to x S That is minimizing f is the same as maximizing f This trick is completely general that is it is not limited to LPs Any solution to the minimization problem will be a solution to the maximization problem and conversely Note that the value of the maximization problem will be 1 times the value of the minimization problem In summary to change a max problem to a min problem just multiply the objective function by 1 4 Rewriting a constraint of the form ai x bi To transform this constraint into an equation add a non negative slack variable ai x bi is equivalent to ai x si bi and si 0 We have seen this trick before If x satisfies the inequality then si bi ai x 0 Conversely if x and si satisfy the expressions in the second line then the first line must be true Hence the two expressions are equivalent Note that by multiplying both sides of the expression ai x si bi by 1 we can guarantee that the right hand side is non negative 5 Rewriting a constraint of the form ai x bi To transform this constraint into an equation subtract a non negative surplus variable ai x bi is equivalent to ai x si bi and si 0 The reasoning is exactly like the case of the slack variable To transform this constraint into an inequality pointed in the other direction multiply both sides by 1 ai x bi is equivalent to ai x si bi 2 6 Rewriting a constraint of the form ai x bi To transform an equation into inequalities note that w z is exactly that same as w z and w z That is the one way for two numbers to be equal is for one to be both less than or equal to and greater than or equal to the other It follows that ai x bi is equivalent to ai x bi and ai x bi By the last section the second line is equivalent to ai x bi and ai x bi 7 Guaranteeing that All Variables are Explicitly Constrained to be Non Negative Most of the problems that we look at requires the variables to be non negative The constraint arises naturally in many applications but it is not essential The standard way of writing linear programming problems imposes this condition The section shows that there is no loss in generality in imposing the restriction That is if you are thinking about a linear programming problem then I can think of a mathematically equivalent problem in which all of the variables must be non negative The transformation uses a simple trick You replace an unconstrained variable xj by two variables uj and vj Whenever you see xj in the problem you replace it with uj vj Furthermore you impose the constraint that uj vj 0 When you carry out the substitution you replace xj by non negative variables You don t change the problem Any value that xj can take can be expressed as a difference in fact there are infinitely many ways to express it Specifically if xj 0 then you can let uj xj and vj 0 if xj 0 then you can let uj 0 and vj xj 8 What Is the Point The previous sections simply introduce accounting tricks There is no substance to the transformations If you put the tricks together they support the claim that I made in the beginning of the notes Who cares The form of the problem with equality constraints and non negative variables is the form that the simplex algorithm uses The inequality constraint form with non negative variables is the form used in for the duality theorem 3 Warnings These transformations really are transformations If you start with a problem in which x1 is not constrained to be non negative but act as if it is so constrained then you may not get the right answer you ll be wrong if the solution requires that x1 take a negative value If you treat an equality constraint like an inequality constraint then you ll get the wrong answer unless the constraint binds at the solution Similarly you can t treat as inequality constraint as an equation in general The transformations involve creating a new variable or constraint to compensate for the changing inequalities to equations equations to inequalities or whatever it is you do 9 Example You know all the ideas Let me show you how they work Start with the problem min subject to 4x1 2x1 x2 x2 x2 x3 x2 x3 x1 6 4 4 0 and let s …