Linear Programming Notes VProblem Transformations1 IntroductionAny linear programming problem can be rewritten in either of two standardforms. In the first form, the objective is to maximize, the material constraintsare all of the form: “linear expression ≤ constant” (ai· x ≤ bi), and all variablesare 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 constraintsare all of the form: “linear expression = constant” (ai· x = bi), and all variablesare 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 thesecond problem.In order to rewrite the problem, I need to introduce a small number oftransformations. I’ll explain them in these notes.2 Equivalent RepresentationsWhen I say that I can rewrite a linear programming problem, I mean that I canfind a representation that contains exactly the same information. For example,the expression 2x = 8 is equivalent to the expression x = 4. They both describethe same fact about x. In general, an equivalent representation of a linearprogramming problem will be one that contains exactly the same informationas the original problem. Solving one will immediately give you the solution tothe other.When I claim that I can write any linear programming problem in a standardform, I need to demonstrate that I can make several kinds of transformation:change a minimization problem to a maximization problem; replace a constraintof the form (ai· x ≤ bi) by an equation or equations; replace a constraint of theform (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 ex-plicitly 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.13 Rewriting the Objective FunctionThe objective will be either to maximize or to minimize. If you start w itha maximization problem, then there is nothing to change. If you start with aminimization problem, say min f(x) subject to x ∈ S , then an equivalent maxi-mization problem is max −f(x) subject to x ∈ S. That is, minimizing −f is thesame as maximizing f. This trick is completely general (that is, it is not limitedto LPs). Any solution to the minimization problem will be a solution to themaximization problem and conversely. (Note that the value of the maximizationproblem will be −1 time s the value of the minimization problem.)In summary: to change a max problem to a min problem, just multiply theobjective 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 ≤ biis equivalent toai· x + si= biand si≥ 0.We have seen this trick before. If x satisfies the inequality, then si= bi− ai· x ≥ 0.Conversely, if x and sisatisfy the expressions in the second line, then the firstline must be true. Hence the two expressions are equivalent. Note that bymultiplying both sides of the expression ai· x + si= biby −1 we can guaranteethat 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 surplusvariable:ai· x ≥ biis equivalent toai· x − si= biand 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 ≥ biis equivalent to−ai· x + si≤ −bi.26 Rewriting a constraint of the form (ai· x = bi)To transform an equation into inequalities, note that w = z is exactly that sameas w ≥ z and w ≤ z. That is, the one way for two numbers to be equal is forone to be b oth less than or equal to and greater than or equal to the other. Itfollows thatai· x = biis equivalent toai· x ≤ biand ai· x ≥ bi.By the last section, the second line is equivalent to:ai· x ≤ biand − ai· x ≤ −bi.7 Guaranteeing that All Variables are ExplicitlyConstrained to be Non-NegativeMost 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. Thestandard 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 canthink of a mathematically equivalent problem in which all of the variables mustbe non-negative.The transformation uses a simple trick. You replace an unconstrained vari-able xjby two variables ujand vj. Whenever you see xjin the problem, youreplace it with uj− vj. Furthermore, you impose the constraint that uj, vj≥ 0.When you carry out the substitution, you replace xjby non-negative variables.You don’t change the problem. Any value that xjcan take, can be expressed asa difference (in fact, there are infinitely many ways to express it). Specifically,if xj≥ 0, then you can let uj= xjand vj= 0; if xj< 0, then you can letuj= 0 and vj= −xj.8 What Is the Point?The previous sections simply introduce accounting tricks. There is no substanceto the transformations. If you put the tricks together, they support the claimthat I made in the beginning of the notes. Who cares? The form of the problemwith equality constraints and non-negative variables is the form that the simplexalgorithm uses. The inequality constraint form (with non-negative variables) isthe form used in for the duality theorem.3Warnings: These transformations really are transformations. If you startwith a problem in which x1is not constrained to be non-negative, but act asif it is so constrained, then you may not get the right answer (you’ll be wrongif the solution requires that x1take a negative value). If you treat an equalityconstraint like an inequality constraint, then you’ll get the wrong answer (unlessthe constraint binds at the solution). Similarly, you can’t treat as inequalityconstraint as an equation in general. The transformations involve creating a newvariable or constraint to compensate for the changing inequalities to equations,equations to inequalities, or