Optimization Methods in Management Science Tutorial 1 - Algebraic Formulations

Algebraic Formulations Usually in class, we describe linear programs by writing them out fully. This is fine for small linear programs, but it doesn’t work when the linear programs are very large. In that case, it helps to use algebraic formulations. Algebraic formulations sound hard. But they are not so hard. However, they do take a while to get used to. 1 On creating algebraic formulations • When we create algebraic formulations, we rely on substituting notation for some of the coefficients. Let’s start with an example of a linear program. Minimize 500 x1 + 200 x2 + 250 x3 + 125 x4 subject to 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000 0 ≤ x1 ≤ 20 0 ≤ x2 ≤ 15 0 ≤ x3 ≤ 10 0 ≤ x4 ≤ 15 This is the MSR example from lecture 1. Cleaver 2 More on the MSR Problem •Need to choose ads to reach at least 1.5 million people •Minimize Cost •Upper bound on number of ads of each type Audience Size Cost/Impression Max # of ads TV Radio Mail 50,000 25,000 20,000 15,000 $500 $200 $250 $125 15 10 20 Newspaper 15 In the MSR problem, we wanted to determine the number of ads of four different types of advertising media. We let x1, x2, x3, and x4 denote the number of ads on TV, Radio, Mail, and Newspaper. 3 The LP Formulation again Minimize 500 x1 + 200 x2 + 250 x3 + 125 x4 subject to 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000 0 ≤ x1 ≤ 20 0 ≤ x2 ≤ 15 0 ≤ x3 ≤ 10 0 ≤ x4 ≤ 15 The objective is the cost of advertising. The first constraint says that the number of people who see the ads is at least 1.5 million. The remaining four constraints give upper and lower bounds on the number of showings of each of the four ads. Cleaver 4 Transforming into an algebraic problem • We’ll transform this problem into an algebraic version in a couple of stages. Then we’ll show how to do it all at once. • So, let’s start with the four upper bound constraints. Suppose that we let d = (d1, d2, d3, d4) = (20, 15, 10, 15). We can then write the linear program as follows: Minimize 500 x1 + 200 x2 + 250 x3 + 125 x4 subject to 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000 0 ≤ xj ≤ dj for j = 1 to 4. Ollie, the computationally wise owl. It looks like dj is a variable, but it isn’t. It’s called a “parameter” and it means that there is an associated value stored for it somewhere. 5 Parameters versus decision variables I don’t get it. The d’s don’t look like numbers to me. Tim, the turkey Most students (and others) find this confusing at the beginning. But after a while, one gets used to it. For students who have seen linear algebra, it’s pretty similar to when one first sees a system of linear equations expressed as Ax = b. Ollie, the computationally wise owl. 6 More on the algebraic formulation Minimize 500 x1 + 200 x2 + 250 x3 + 125 x4 subject to 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000 0 ≤ xj ≤ dj for j = 1 to 4. Another advantage of the algebraic formulation is that the formulation becomes “independent” of the data. For example, if we were to change the upper bounds on the x’s, this more algebraic version would still be valid. Actually, it won’t be the algebraic version until we get rid of almost all of the numbers. We will permit the number 0 at times, plus numbers for the indices. Nooz, the most trusted name in fox. 7 Making the remaining constraint more algebraic Minimize 500 x1 + 200 x2 + 250 x3 + 125 x4 subject to 50,000 a1 x1 +x1 + 25,000 a2 x2 +x2 + 20,000 a3 x3 + x3 + 15,000 a4 x4 ≥x4 ≥ b1,500,000 0 ≤ xj ≤ dj for j = 1 to 4. Let aj be the coefficient of xj in the constraint. And let b denote the RHS of the constraint. We then can rewrite the constraint. It doesn’t look simpler than the old version. But it would if there were 1000 variables instead of just 4. Ollie Nooz 8 Transforming the cost coefficients Minimize 500 c1 x11 + 200 c2 x22 + 250 c3 xx33++ 125 c4 xx44 subject to a1 x1 + a2 x2 + a3 x3 + a4 x 4 ≥ b 0 ≤ xj ≤ dj for j = 1 to 4. Let cj be the cost coefficient of xj We now rewrite the objective. Nooz 9 Using Summation Notation cx ∑ c x + c x + c x + a x ≥b a x ∑ + a x + a x + 4 Minimize 1 1 j =1 j 2 2 j =1 2 2 j 3 3 c4 x4 3 3 a4 x 4 ≥ 4 subject to 1 1 j j x j ≤j =d1j tofor 4. 0 ≤ xj ≤0 d≤j for b j = 1 to 4. Next we use summation notation. Nooz 10 Replacing the number of variables. ∑ ∑ Minimize n 4 j =1 n 4 subject to j =1 c j xj aj x j ≥ b 0 ≤ xj ≤ d j Finally, we use n to represent the number of variables. for j = 1 to n. 4. Yes. I know it looks much more abstract that the original formulation. But the abstraction means that this formulation is correct for many different possible choices of the data. Ollie Nooz 11 Summary of the transformation • • • • Let xj be the number of ads purchased of type j for j = 1 to n. Let aj be the number of persons who view one ad of type j Let b be the required number of viewers to see the ads. (That is, the total number of viewers must be at least b) Let dj be an upper bound on the number of ads purchased of type j. Minimize subject to ∑ ∑ n j =1 n j =1 c j xj aj x j ≥ b 0 ≤ xj ≤ d j for j = 1 to n. Minimize 500 x1 + 200 x2 + 250 x3 + 125 x4 subject to 50,000 x1 + 25,000 x2 + 20,000 x3 + 15,000 x4 ≥ 1,500,000 0 ≤ x1 ≤ 20; 0 ≤ x2 ≤ 15; 0 ≤ x3 ≤ 10; 0 ≤ x4 ≤ 15; 12 On the reason for algebraic formulations • Remember that the advantage of algebraic formulations is in their ability to describe very large problems in a very compact manner. This is critical if one is to model large problems, involving thousands or perhaps millions of variables. • For small problems, it seems unnecessarily cumbersome and difficult. And it is unnecessarily abstract for describing small problems. The notation is also very useful when we describe the simplex algorithm for linear programs. We next formulate the problem for DTC, David’s Tool Company Ollie 13 Formulation of the DTC Problem (David’s Tool Company) We will write the linear program as if up the constraints are broken into two parts, the demand constraints and the resource constraints. Maximize subject to z = 3 K + 5 S 2 K + 3 S ≤ 100 K + 2 S ≤ 60 Smoothing time: K + S ≤ 50 Delivery time: K S Gathering time: ≤ 40 Slingshot demand: ≤ 30 Shield demand: K,S ≥ 0 Resource Constraints Bounds on variables. Non-negativity: 14 The algebraic formulation Maximize subject to z = 3 x 1 + 5 x2 2 x1 + x1 + x1 + x1 ≤ 3 x2 ≤ 100 Gathering time: 2 x2 ≤ 60 Smoothing time: x2 ≤ 50 40 x2 ≤ x 1 , x2 ≥ 0 Delivery time: Slingshot demand: 30 Resource Constraints Shield demand: Bounds on variables. Non-negativity: Let xj amount of the j-th item that is produced. In the above formulation we have replaced K by x1 and S by x2. This will make it more easily described using algebraic notation. 15 The algebraic formulation z == ∑ x j j 5 x2 z 3 xj =11 p + n Maximize subject to 2 x1 + x1 ∑ + n 3 x2 ≤ 100 j =1 2 aij x j ≥ bi x2 ≤ 60 Gathering time: Smoothing time: x1 for + i =x21 ≤to m. 50 Delivery time: x1 ≤ 40 Slingshot demand: 0 ≤ xxj2≤≤ dj 30 for j = 1 to n. x 1 , x2 ≥ 0 Shield demand: Resource Constraints Bounds on variables. Non-negativity: Let dj be an upper bound on the demand for item j. Let n denote the number of items. Let aij be the amount of resource i used up by one unit of item j. Let m denote the number of different resources. Let pj be the profit from making one unit of item j 16 Notation for linear programs in standard form • Finally, we show some conventions that are used in describing a linear programming in standard form. The conventions are used in 15.053. • • • There are usually n variables and m equality constraints The variables are usually x1, …, xn. The cost coefficients are usually c1, …, cn. (Objective function coefficients are often called cost coefficients even if one is maximizing profit. Every knows that this is a weird convention, but it is commonly done.) The coefficient for xj in constraint i is aij. The RHS is bi. Then the LP in standard form can be written as follows: • • maximize subject to z= ∑ ∑ n j =1 c j xj x j =1 aij x j = bi xj ≥ 0 for i = 1 to m for j = 1 to n 17 Last slide In case you were wondering, there are different ways of writing algebraic formulations. You can n choose notation aij xyou ≥ bi j differently, j =1and can combine groups of for i = 1 to m. constraints differently. ∑ You will have a chance to practice algebraic formulations on the homework sets. And that’s the end of this tutorial. I hope it was of value to you. Bye! Ollie Cleaver 18