University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

211

Pages:

10
Author:

Hayley Roman

Converting a Linear Program to Standard Form In this tutorial, we briefly explain what standard form is, and how to convert a linear program to standard form 1 Linear Programs in Standard Form We say that a linear program is in standard form if the following are all true: 1. Non-negativity constraints for all variables. 2. All remaining constraints are expressed as equality constraints. 3. The right hand side vector, b, is non-negative. An LP not in Standard Form maximize z = 3x1 + 2x2 - x3 + x4 x1 + 2x2 + x3 - x4 ≤ 5 ; -2x1 - 4x2 + x3 + x4 ≤ -1; x1 ≥ 0, x2 ≥ 0 not equality not equality, and negative RHS x3 and x4 may be negative 2 And … Isn’t this exactly the same as was done Tim, the turkey 3 Converting Inequalities into Equalities Plus Non-negatives After Before x1 + 2x2 + x3 - x4 ≤ 5 To convert a “≤” constraint to an equality, add a slack variable. x1 + 2x2 + x3 - x4 +s1 = 5 s1 ≥ 0 s1 is called a slack variable, which measures the amount of “unused resource.” Note that s1 = 5 - x1 - 2x2 - x3 + x4. After Before x1 + 2x2 + x3 ≥ 7 To convert a “≥” constraint to an equality, add a surplus variable. x1 + 2x2 + x3 – s2 = 7 s2 ≥ 0 s2 is called a surplus variable, which measures the amount of excess. Note that s1 = 7 - x1 - 2x2 - x3. 4 Transforming Max to Min How can one convert a minimization problem to a maximization problem? Example: Minimize z = 3x1 + 2x2 subject to “constraints” Has the same optimum solution(s) as Maximize v = -3x1 - 2x2 subject to “constraints” 5 And … So, when is there going to be any new material? Please be patient. The transformations on the next slides were not presented in class. Tim 6 Getting Rid of Negative Variables Before Max s.t. z = 3x1 + 4x2 + 5x3 2x1 - 5x2 + 2x3 = 7 other constraints x1 ≤ 0, x2 ≥ 0, x3 ≥ 0 After max z = -3y1 + 4x2 + 5x3 -2y1 -5x2 +2x3 =7 other constraints y1 ≥ 0, x2 ≥ 0 x3 ≥ 0 Transformation: replace x1 by y1 = -x1; and require that y1 ≥ 0. If y1, x2, x3 is an optimal solution for the transformed problem, then -y1, x2, x3 is an optimal solution for the original problem. 7 Other constraints? Why did we writing “other constraints on the previous slide? It doesn’t seem to add anything. Tim “Other constraints” is added to emphasize that the transformation works even if there are lots of constraints. And the transformation y1 = -x1 is used regardless of the other constraints. Ollie, the computationally wise owl. 8 Transforming variables that may take on negative values. Before max z = 3x1 + 4x2 +5x3 2x1 -5x2 +2x3 =7 other constraints x1 ≥ 0, x2 is unconstrained in sign, x3 ≥ 0 The transformation here is a little more complex. We use the fact that a real number can be expressed as the difference of two non-negative numbers (in an infinite number of ways). For example, -5 can be written as 0 – 5 or as 1-6 or as 2-7 etc. We replace x2 by x2 = y3 - y2; and require that y2 ≥ 0, y3 ≥ 0. After If max z = 3x1 + 4(y3 - y2) +5x3 2x1 -5y3 +5y2 +2x3 = 7 other constraints x1 , y2, y3, x3 ≥ 0 x1, y2, y3, x3 is an optimal solution for the transformed problem, then x1, y3 - y2, x3 is an optimal solution for the original problem. 9 Last Slide Remember that the major reason we do this is because the simplex method starts with a linear program in standard form. But it turns out that this type of transformation is useful for other types of algorithms too. Perhaps we shall see their usefulness some time later in this course. Well, that concludes this tutorial on transforming a linear program into standard form. I hope to see you again soon. Cleaver 10