Converting a Linear Program to Standard Form Hi, welcome to a tutorial on converting an LP to Standard Form. Amit, an MIT Beaver We hope that you enjoy it and find it useful. Mita, an MIT Beaver 2 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 nonnegative. An LP not in Standard Form max Ella I think it is really cool that when Ella speaks, some of her words are in red, and some are underlined. I wish I could do that. Stan z = 3x1 + 2x2 - x3 + x4 x1 + 2x2 + x3 - x4 ≤ 5 ; not equality -2x1 - 4x2 + x3 + x4 ≤ -1; not equality, and negative RHS x1 ≥ 0, x2 ≤ 0 x2 is required to be nonpositive; x3 and x4 may be positive or 3 negative. Why do students need to know how to convert a linear program to standard form? What’s so special about standard form? The main reason that we care about standard form is that this form is the starting point for the simplex method, which is the primary method for solving linear programs. Students will learn about the simplex algorithm very soon. In addition, it is good practice for students to think about transformations, which is one of the key techniques used in mathematical modeling. Tom Next we will show some techniques (or tricks) for transforming an LP into standard form. 4 Converting a “≤” constraint into standard form We first consider a simple inequality constraint. The first inequality constraint of the previous LP is x1 + 2x2 + x3 - x4 ≤ 5 Nooz can speak in red, just like Ella. How does he do that? Wow! I just spoke in boldface. Cool! To convert a “≤” constraint to an equality, add a slack variable. In this case, the inequality constraint becomes the equality constraint: x1 + 2x2 + x3 - x4 +s1 = 5. We also require that the slack variable is non-negative. That is s1 ≥ 0. s1 is called a slack variable, which measures the amount of “unused resource.” Note that s1 = 5 - x1 - 2x2 - x3 + x4. 5 Converting a “≥” constraint into standard form, and converting inequalities with a negative RHS. We next consider the constraint -2x1 - 4x2 + x3 + x4 ≤ -1 I know how to do that one. Just add a slack variable, like we did on the last slide. Nice try, Tom, but incorrect. First we have to multiply the inequality by -1 in order to obtain a positive RHS. Then we get 2x1 + 4x2 - x3 - x4 ≥ 1. Then we add a surplus variable and get 2x1 + 4x2 - x3 - x4 - s2 = 1. To convert a “≤” constraint to an equality, add a slack variable. s2 is called a surplus variable, which measures the amount by which the LHS exceeds the RHS. Note that s2 = 2x1 + 4x2 - x3 - x4 -1 To convert a “≥” constraint to an equality, add a surplus variable. 6 Getting Rid of Negative Variables Next, I’ll show you how to transform the constraint constraint: x2 ≤ 0 into standard form. Can’t we just write: x2 + s3 = 0 and s3 ≥ 0? Tom, what you wrote is correct, but it doesn’t help. Standard form requires all variables to be non-negative. But after your proposed change, it is still true that x2 ≤ 0. The solution in this case is a substitution of variables. We let y2 = -x2. Then y2 ≥ 0. And we substitute –y2 for x2 wherever x2 appears in the LP. The resulting LP is given below. (after you click.) max z= 3x1 x1 2x1 x1 ≥ 0, -+ 2x 2y2 - x3 + x4 -+ 2x 2y2 + x3 - x4 + s1 = 5 ; -+ 4x 4y2 - x3 - x4 - s2 = 1; 0 s1 ≥ 0, s2 ≥ 0 xy22≤≥ 0, 7 Getting Rid of Variables that are Unconstrained in Sign Actually, we’ll show you two ways. The first way is substitution. For example, x3 below is unconstrained in sign. (Sometimes we call this a free variable.) Notice that the second constraint can be rewritten as: x3 = 2x1 - 4y2 - x4 - s2 - 1. Next, we’ll show you how to get rid of a variable that is unconstrained in sign. That is, it can be positive or negative. Now substitute 2x1 - 4y2 - x4 - s2 - 1 for x3 into the current linear program. Notice that you get an equivalent linear program without x3. You can see it on the next slide. max z= 3x1 x1 2x1 x1 ≥ 0, - 2y2 - x3 + x4 - 2y2 + x3 - x4 + s1 = 5 ; - 4y2 - x3 - x4 - s2 = 1; y2 ≥ 0, s1 ≥ 0, s2 ≥ 0 8 Getting Rid of Free Variables by Substitution When we substitute 2x1 - 4y2 - x4 - s2 - 1 for x3 here is what we get. (Click now.) The variable x4 is also unconstrained in sign. You can substitute for it as well. After this substitution, all that will remain is an objective function and non-negativity constraints for x1, y2, s1 and s2. max max z= z= 3x1 x1 2x1 x1 ≥ 0, This trick only works for variables that are unconstrained in sign. If you tried eliminating x1 instead of x3 by substitution, the optimal solution for the resulting LP would not necessarily satisfy the original constraint x1 ≥ 0. So eliminating x1 in this manner would not create an equivalent LP. - 2y2 - x3 + x4 - 2y2 + x3 - x4 + s1 = 5 ; - 4y2 - x3 - x4 - s2 = 1; y2 ≥ 0, s1 ≥ 0, s2 ≥ 0 1x1 + 2y2 + 2x4 + s2 + 1 3x1 - 6y2 - 2x4 + s1 + s2 = 5 ; x1 ≥ 0, y2 ≥ 0, s1 ≥ 0, s2 ≥ 0 Cathy 9 Getting Rid of Free Variables: Version 2 There is an even simpler way of getting rid of free variables. We replace a free variable by the difference of two nonnegative variables. For example, we replace x3 by y3 – w3, and require y3 and w3 to be non-negative. (Click now.) You can then substitute y4 – w4 for x4. max z= 3x1 - 2y2 x1 - 2y2 2x1 - 4y2 x1 ≥ 0, y2 ≥ 0, max z= After solving this new linear program, we can find the solution to the original linear program. For example, x3 = y3 – w3 and x4 = y4 – w4. - x3 + x4 + x3 - x4 + s1 = 5 ; - x3 - x4 - s2 = 1; s1 ≥ 0, s2 ≥ 0 3x1 - 2y2 - y3 + w3 + x4 x1 - 2y2 + y3 - w3 - x4 + s1 = 5 ; 2x1 - 4y2 - y3 + w3 - x4 - s2 = 1; x1 ≥ 0, y2 ≥ 0, y3 ≥ 0, w3 ≥ 0, s1 ≥ 0, s2 ≥ 0 10 Getting Rid of Free Variables: Version 2 It depends on what you mean by “the same.” Here is what we mean. For every solution to the original LP, there is a solution to the transformed LP with the same objective value. For example, if there is a feasible solution with x3 = -4, then there is a feasible solution to the transformed problem with the same objective value. In this case, let y3 = 0 and w3 = 4. This doesn’t make sense to me. Before we had a variable x3, and now we have two variables y3 and w3. How can two variables be the same as a single variable? max z= 3x1 - 2y2 x1 - 2y2 2x1 - 4y2 x1 ≥ 0, y2 ≥ 0, max z= - x3 + x4 + x3 - x4 + s1 = 5 ; - x3 - x4 - s2 = 1; s1 ≥ 0, s2 ≥ 0 3x1 - 2y2 - y3 + w3 + x4 x1 - 2y2 + y3 - w3 - x4 + s1 = 5 ; 2x1 - 4y2 - y3 + w3 - x4 - s2 = 1; x1 ≥ 0, y2 ≥ 0, y3 ≥ 0, w3 ≥ 0, s1 ≥ 0, s2 ≥ 0 11 Similarly, if there is a feasible solution for the transformed problem, then there is a feasible solution for the original problem with the same objective value. For example, if there is a feasible solution with y3 = 1, and w3 = 5, then there is a feasible solution for the original problem with the same objective value. In this case, let x3 = -4. But for every solution to the original problem, there are an infinite number of solutions to the transformed problem. If x3 = -4, we could have chosen y3 = 2 and w3 = 6, or any other solution such that y3 – w3 = -4. Tom, that’s true. But every one of those solutions will still have the same objective function value. In each case - y3 + w3 = 4. So, even though the two linear programs differ in some ways, they are equivalent in the most important way. An optimal solution for the original problem can be transformed into an optimal solution for the transformed problem. And an optimal solution for the transformed problem can be transformed into an optimal solution for the original problem. 12 Transforming Max to Min We still have one last pair of transformations. We will show you how to transform a maximization problem into a minimization problem, and how to transform a minimization problem into a maximization problem. This is not part of converting to standard form, but it is still useful. min max We illustrate with our original linear program, which is given below. All you need to know is that if we maximize z, then we are minimizing –z, and vice versa. See if you can use this hint to figure out how to change the problem to a minimization problem. Then click to see if you are right. -3x 2x z-z==3x x3x+3 -xx 1 -2x 1 + 2 2- + 44 x1 + 2x2 + x3 - x4 ≤ 5 ; -2x1 - 4x2 + x3 + x4 ≤ -1; x1 ≥ 0, x2 ≤ 0 McGraph 13 min Here is an example for which you can test out these techniques. Consider the LP to the right. See if you can transform it to standard form, with maximization instead of minimization. To see the new variables, click once. To see the transformed problem, click again. z = x1 - x2 + x3 x1 + 2x2 - x3 ≤ 3 - x1 + x2 + x3 ≥ 2 x1 - x2 = 10 x1 ≥ 0, x2 ≤ 0 Transformations. s1 = slack variable for 1st constraint. s2 = surplus variable for 2nd constraint. y2 = - x2 y3 - y4 = x3. max -z = -x1 – y2 – (y3 – y4) x1 – 2y2 – (y3 – y4) + s1 = 3 - x1 – y2 + (y3 – y4) - s2 = 2 x1 + y2 = 10 x1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, s1 ≥ 0, s2 ≥ 0 14 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 these types of transformation are useful for other types of algorithms too. Perhaps we shall see their usefulness again some time later in this course. Well, that concludes this tutorial on transforming a linear program into standard form. We hope to see you again soon. 15 MIT OpenCourseWare http://ocw.mit.edu 15.053 Optimization Methods in Management Science Spring 2013 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

© Copyright 2018 AnyForm