Operations Research Example 1, Section 4.16

Example 1, Section 4.16 The Leon Burnit Ad Agency is trying to determine a TV schedule for Priceler Auto. Ad HIM LIP HIW Cost Football 7 10 5 100, 000 3 5 4 60, 000 Soap Opera Goals 40 60 35 600, 000 This means, for example, that the ad agency wants to reach at least 40 million viewers “HIM”, 60 million “HIW”, and 35 million “LIP”, with a total budget of $600,000.00. SOLUTION (for the penalty terms): − − + min z = 200s− 1 + 100s2 + 50s3 + s4 − s.t. 7x1 + 3x2 + s1 − s+ 1 + 10x1 + 5x2 + s− − s 2 2 + 5x1 + 4x2 + s− − s 3 3 100x1 + 60x2 = 40 HIM = 60 LIP = 35 HIW ≤ 600 Budget The initial tableau: rhs x1 x2 s − s+ s− s+ s− s+ s− s+ 1 1 2 2 3 3 4 4 0 0 200 0 100 0 50 0 0 1 0 7 3 1 −1 0 0 0 0 0 0 40 10 5 0 0 1 −1 0 0 0 0 60 5 4 0 0 0 0 1 −1 0 0 35 100 60 0 0 0 0 0 0 1 −1 600 Final tableau:  x1 x2 s − s+ 1 1  0 0 200 0    1 0 0 0    0 0 −1 1   0 0 0 0  0 1 0 0 s− 2 280 3 4 15 13 15 20 3 − 13 Conclusion: x1 = s− 3 s+ 2 20 3 130 3 4 − 15 − 13 − 13 − 13 15 − 20 3 1 3 13 3 20 3 2 3 x2 = s+ 3 20 3 1 3 1 3 − 20 3 2 −3  rhs s− s+ 4 4  1 0 − 100 3   13  0 0 3   1 0 0  3  100  −1 1  3 0 0 10 3 10 3 Which gives: + s− 1 = 0, s1 = 1 3 + s− 2 = 0, s2 = 0 + s− 3 = 0, s3 = 0 + s− 4 = 0, s4 = 33 1 3 CONCLUSION: An increase in the budget by 33 13 thousands of dollars would allow us to meet all of our advertising goals. 1 Example 2, Section 4.16 (Goal Programming) The Dewright company is considering three new products to replace current models. ... Factor Prod 1 2 3 Goal (units) Penalty Long run profit 12 9 15 ≥ 125 (millions dollars) 5 Employment 5 3 4 = 40 (hundreds of people) 2(+), 4(−) 5 7 8 ≤ 55 (millions dollars) 3 Capital − SOLUTION: As before, let s+ i be the amount over, si be the amount under the stated goal. In goal 1, we see that the amount under gets the penalty (s− 1 ), in employment, we get both, and in capital, the penalty is for going over (s+ ). 3 min + − + z = 5s− 1 + 2s2 + 4s2 + 3s3 + 12x1 + 9x2 + 15x3 + s− 1 − s1 = 125 + 5x1 + 3x2 + 4x3 + s− 2 − s2 = 40 − 5x1 + 7x2 + 8x3 + s3 − s+ 3 = 55 Solution in LINDO: min 5s1m+2s2p+4s2m+3s3p st 12x1+9x2+15x3+s1m-s1p=125 5x1+3x2+ 4x3+s2m-s2p=40 5x1+7x2+ 8x3+s3m-s3p=55 LINDO OUTPUT: LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION VALUE 1) VARIABLE S1M S2P S2M S3P X1 X2 X3 S1P S3M 16.66667 VALUE 0.000000 8.333333 0.000000 0.000000 8.333333 0.000000 1.666667 0.000000 0.000000 REDUCED COST 3.095238 0.000000 6.000000 0.428571 0.000000 6.857143 0.000000 1.904762 2.571429 We see Goal 1 was attained, we went over Goal 2 by 25/3, and met Goal 3 by taking x1 = 25/3, x2 = 0 and x3 = 5/3. 2 Example 3: Preemptive Goal Programming, In-Class Going back to Example 1, suppose we prioritize the goals: min z = P1 s− 1 min z = P 2 s− 2 min z = P3 s − 3 To reiterate, the “constraints” were: 7x1 + 3x2 10x1 + 5x2 5x1 + 4x2 100x1 + 60x2 ≥ 40 HIM ≥ 60 LIP ≥ 35 HIW ≤ 600 Budget Write the tableau that we will put into Maple: s− x1 x2 s + s+ s− s+ s− s4 rhs 1 1 2 2 3 3 0 0 0 0 0 P1 0 0 0 0 0 0 0 0 P2 0 0 0 0 0 0 0 0 0 0 P3 0 0 0 0 7 3 −1 0 0 1 0 0 0 40 10 5 0 −1 0 0 1 0 0 60 5 4 0 0 −1 0 0 1 0 35 100 60 0 0 0 0 0 0 1 600 The final tableau in Maple:  x1 x2  0 0    0 0    0 0    1 0   0 0    0 0  0 1 s+ 1 0 s+ 2 0 s+ s− 3 1 0 P1 s− 2 0 s− 3 0 0 0 0 0 P2 0 0 P3 P3 0 −P3 0 0 − 35 0 0 0 1 − 65 0 −1 3 5 6 5 0 −1 −1 0 1 1 0 −1 0 0 1 0 0 s4 0 rhs 0      0 0   3  P3 −5 P3 20   1 6 − 20    1 − 20 2   3  5 − 20  1 0 10 Interpretation: By spending 6 units of advertising on football games (x1 ) and nothing on soap operas, we should be able to reach our target audience of high income men and high income women. 3 Example 4: Color TVs and VCRs This is a modification of Exercise 3 from the text. Highland Appliance must determine how many color TVs and VCRs should be stocked. It costs Highland $300 to purchase a TV and $200 to purchase a VCR. A TV requires 3 square yards of storage space, and a VCR requires 1 square yard. A TV will bring $150 in profit, a VCR $100. Highland has set the following goals (in order of importance): • Goal 1: We have $20,000 to buy TVs and VCR’s • Goal 2: We need at least $11,000 in profit • Goal 3: We have no more than 200 square yards of storage space. First, formulate a nonpreemptive goal program that makes the penalty for profit 10 times that of the other two goals, and solve with LINDO. Then make them all equal and re-solve (using LINDO). Secondly, write a preemptive goal program and solve it with Maple. (Go to next several pages for the solutions) FIRST PART OF SOLUTION: Write down the constraints and variables needed: 300x1 +200x2 ≤ 20000 150x1 +100x2 ≥ 11000 3x1 +2x2 ≤ 200 Moolah for Product, Penalize overage Profit, Penalize underage Storage Space, Penalize overage Therefore, the variables are: 300x1 +200x2 +s− −s+ = 20000 1 1 − + 150x1 +100x2 +s2 −s2 = 11000 3x1 +2x2 +s− −s+ = 200 3 3 4 Bad: s+ 1 Bad: s− 2 Bad: s+ 3 SOLUTION 1 (LINDO, with weighted penalties): min s1p+10s2m+s3p st 300x1+200x2+s1m-s1p=20000 150x1+100x2+s2m-s2p=11000 3x1+2x2+s3m-s3p=200 Output from LINDO: LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 2020.000 VARIABLE VALUE REDUCED COST S1P 2000.000000 0.000000 S2M 0.000000 7.980000 S3P 20.000000 0.000000 X1 73.333336 0.000000 X2 0.000000 0.000000 S1M 0.000000 1.000000 S2P 0.000000 2.020000 S3M 0.000000 1.000000 SOLUTION 2: LINDO, using equal weights OBJECTIVE FUNCTION VALUE 1000 VARIABLE VALUE REDUCED COST S1P 0.000000 0.510000 S2M 1000.000000 0.000000 S3P 0.000000 0.000000 X1 66.666664 0.000000 X2 0.000000 0.000000 S1M 0.000000 0.490000 S2P 0.000000 1.000000 S3M 0.000000 1.000000 5 SOLUTION 3: Solve the preemptive program using Maple Originally, in Maple we’ll solve the maximization problem: − + max −z = −P1 s+ 1 − P2 s 2 − P3 s 3 ⇒ − − −z + P1 s+ 1 + P 2 s 2 + P3 s 3 = 0 which we put down in three goal rows. s+ s− s+ s− s+ RHS x1 x2 s − 1 1 2 2 3 3 0 0 0 P1 0 0 0 0 0 0 P2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 P3 0 300 200 1 −1 0 0 0 0 20, 000 150 100 0 0 1 −1 0 0 11, 000 3 2 0 0 0 0 1 −1 200 Oh no! I can’t use the columns with the Pi as basic variables! What am I to do? ANSWER: The two phase method. In Maple, we get: s+ s− s+ s− s+ a1 a2 RHS x1 x2 s − 1 1 2 2 3 3 0 0 0 0 0 0 0 0 1 1 0 0 0 0 P1 0 0 0 0 0 0 0 0 P2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 P3 0 0 0 300 200 1 −1 0 0 0 0 1 0 20, 000 150 100 0 0 1 −1 0 0 0 0 11, 000 0 0 0 1 −1 0 1 200 3 2 0 Then (follow along in Maple to the end): x1 x2 s− s− s− a1 a2 RHS s+ s+ s+ 1 2 3 1 2 3 0 0 0 0 0 0 0 0 1 1 0 0 0 0 P1 0 0 0 0 0 0 0 P2 /2 −P2 /2 0 P2 0 0 P 2/2 0 −1000P2 0 0 0 0 −P3 /100 P3 /100 0 0 P3 0 −P3 /100 P3 0 0 0 1/100 −1/100 0 0 −1 1 1/100 −1 0 0 0 −1/2 1/2 1 −1 0 0 −1/2 0 1, 000 1 2/3 1/300 −1/300 0 0 0 0 1/300 0 200/3 Notes: • We cannot pivot in the s+ 1 column to get a better P2 result without decreasing our first goal (since P1 is above − 12 P2 ). Therefore, goal P2 is finished. Similarly, we cannot pivot in Column 2 (s− 1 ) without decreasing Goal 2. Therefore, Goal 3 is finished. • The zeros to the right of Goals 1 and 3 mean that they have both been met. • Goal 2 has not been met. + • Current set of basic variables: x1 , s− 2 , and s3 . The full BFS is (in order) x1 = 66 2 3 ± − + x2 = 0 s ± 1 = 0 s2 = 1000, s2 = 0, s3 = 0 6 Solving TV/VCRs with LINDO As discussed in the text, we can use LINDO to solve the LP with priorities. We start − + with the initial tableau, and the highest priority goal. Recall that s+ 1 , s2 and s3 are the “bad” variables for goals 1, 2, and 3 respectively. min s1p st 300x1+200x2+s1m-s1p=20000 150x1+100x2+s2m-s2p=11000 3x1+ 2x2+s3m-s3p=200 LINDO OUTPUT: OBJECTIVE FUNCTION VALUE 1) 0.0000000E+00 VARIABLE VALUE REDUCED COST S1P 0.000000 1.000000 X1 0.000000 0.000000 X2 0.000000 0.000000 S1M 20000.000000 0.000000 S2M 11000.000000 0.000000 S2P 0.000000 0.000000 S3M 200.000000 0.000000 S3P 0.000000 0.000000 Now, rerun with the new problem using the second priority: min s2m st 300x1+200x2+s1m-s1p=20000 150x1+100x2+s2m-s2p=11000 3x1+ 2x2+s3m-s3p=200 s1p=0 ***NOTE THIS NEW LINE! LINDO OUTPUT: OBJECTIVE FUNCTION VALUE 1) 1000.000 VARIABLE VALUE REDUCED COST S2M 1000.000000 0.000000 X1 66.666664 0.000000 X2 0.000000 0.000000 S1M 0.000000 0.500000 S1P 0.000000 0.000000 S2P 0.000000 1.000000 S3M 0.000000 0.000000 S3P 0.000000 0.000000 And finally, rerun with the modified system: 7 min s3p st 300x1+200x2+s1m-s1p=20000 150x1+100x2+s2m-s2p=11000 3x1+ 2x2+s3m-s3p=200 s1p=0 s2m=1000 LINDO OUTPUT: OBJECTIVE FUNCTION VALUE 1) 0.0000000E+00 VARIABLE VALUE REDUCED COST S3P 0.000000 1.000000 X1 66.666664 0.000000 X2 0.000000 0.000000 S1M 0.000000 0.000000 S1P 0.000000 0.000000 S2M 1000.000000 0.000000 S2P 0.000000 0.000000 S3M 0.000000 0.000000 (Same solution as Maple with priorities) 8