Computer Solution of Goal Programming Problems with QM for Windows and Excel | Introduction to Management Science (10th Edition)

[Page 397 ( continued )]

Goal programming problems can be solved using QM for Windows and Excel spreadsheets. In this section we will demonstrate how to use both computing alternatives to solve the Beaver Creek Pottery Company example we solved graphically in the previous section.

[Page 398]

Management Science Application: Developing Television Advertising Sales Plans at NBC

The National Broadcasting Company (NBC), a subsidiary of General Electric, generated more than $4 billion in revenue in 2000 from its television network. In May the network announces its programming schedule for the broadcast year, which begins in the third week in September. Soon after that initial announcement, the network begins the sale of its inventory of advertising slots on its TV shows to advertisers. During this time advertising agencies approach the network with requests to purchase time for their clients for the year. The requests generally include a budget, the demographic audience in which the client is interested, and a desired program mix. NBC subsequently develops a sales plan consisting of a schedule of television commercials that will meet the client's requirements. The most popular commercial durations are 30 and 15 seconds, although 60- and 120-second slots are not uncommon.

After the network finalizes its programming schedule, it develops a rating forecast that projects the audience size for several demographic groupings for each airing of a show. These ratings projections are based on such factors as the strength of the show, historical ratings for a time slot, competing shows on other networks, and the performance of adjacent shows. The network then develops advertising rate cards that set the prices of advertising slots for each airing of a show. The prices vary according to the time of the year the show airs. For example, prices are high during the sweeps months of November, February, and May and are lower in January and the summer; thus prices are weighted for different weeks of the year. The sales management staff prioritizes sales requests based on the client's importance to NBC. NBC also desires to make the most profitable use of its limited inventory. It is optimal for NBC to use as little premium inventory as possible in meeting each client's request.

NBC uses a 01 integer goal programming model to develop annual advertising sales plans for individual clients. The model minimizes the amount of premium inventory assigned to a sales plan while also minimizing the penalty incurred in not meeting other goals. Goals are for inventory (i.e., airtime availability), product conflict (i.e., no two similar products should advertise on the same show), client budget constraints, showmix goals, unitmix (i.e., commercial length) goals, and weekly weighting constraints. The decision variables are 01 and indicate the number of commercials of each length aired on shows during weeks included in the sales plan. The model has enabled NBC to save millions of dollars of premium inventory while meeting customer requirements, and it has reduced the time required to develop a sales plan from 3 to 4 hours to 20 minutes. It is estimated that this model and associated planning systems increase NBC's revenue by at least $50 million per year.

Source: S. Bollapragada, et al.,"NBC Optimization Systems Increase Revenues and Productivity," Interfaces 32, no. 1 (JanuaryFebruary 2002): 4760.

QM for Windows

We will demonstrate how to solve a goal programming model by using our Beaver Creek Pottery Company example, which was formulated as follows :

[Page 399]

QM for Windows includes a goal programming module that can be accessed by clicking on the "Module" button at the top of the screen. The model parameters are entered onto the data input screen as shown in Exhibit 9.1. Notice that each prioritized deviational variable must be assigned a weight, which for this problem is always one. The solution is obtained by clicking on the "Solve" button at the top of the screen. The solution summary for our model is shown in Exhibit 9.2.

Exhibit 9.1.

Exhibit 9.2.

QM for Windows will also provide a graphical analysis of a goal programming model. We click on the "Windows" button and then select "Graph" from the menu. The graph for our example is shown in Exhibit 9.3.

Exhibit 9.3.

(This item is displayed on page 400 in the print version)

Excel Spreadsheets

Solving a goal programming problem by using Excel is similar to solving a linear programming model, although not quite as straightforward. Exhibit 9.4 shows the spreadsheet format for our Beaver Creek Pottery Company example. Cells G5, G6, and G7, under the heading "Constraint Total," contain the formulas for our goal constraints, including deviational variables. The formula for the labor constraint is shown on the formula bar at the top of the screen in Exhibit 9.4. The model decision variables are in cells B10 and B11, and the deviational variables are in cells E5:F7 . The goals are established by setting the constraint formulas in G5 to G7 equal to the goal levels in cells I5 to I7.

Exhibit 9.4.

(This item is displayed on page 400 in the print version)

When using a spreadsheet (or any regular linear programming program) to solve a goal programming problem, it must be solved sequentially . In this procedure, a new problem is formulated and solved for each priority goal in the objective function, beginning with the highest priority. In other words, the minimization of the deviational variable at the highest priority is the initial objective. Once a solution for this formulation is achieved, the value of the deviational variable that is the objective is added to the model as a constraint, and the second-priority deviational variable becomes the new objective. A new solution is achieved for each new objective sequentially until all the priorities are exhausted or it is clear that a better solution cannot be reached. For our purposes, this means editing Excel's Solver for each new solution.

[Page 400]

Exhibit 9.5 shows the Solver Parameters window for our spreadsheet example. Recall that the first-priority goal for our model is the minimization of the negative deviational variable ( d ₁ ) for our labor goal. This deviational variable is located in cell E5; thus, we start Solver by minimizing cell E5. We identify B10:B11 (the decision variables) as well as E5:F7 (the deviational variables) as variables in the model. The model constraints are for our goals (i.e., G5:G7 = I5:I7 ).

[Page 401]

Exhibit 9.5.

The spreadsheet with the solution to our example problem is shown in Exhibit 9.6. We know this is the most satisfactory solution we can achieve from the QM for Windows solution, so it will not be necessary to perform any additional sequential steps. From the spreadsheet we can see that we have achieved all the goals except the fourth-priority goal, to minimize d ₁ ⁺ . However, if we had not achieved all our top goals so readily, the next step would be to include E5 = as a constraint in Solver and then minimize our next-priority goal, which would be E6 (i.e., d ₂ ).

[Page 402]

Exhibit 9.6.

(This item is displayed on page 401 in the print version)

Time Out: For Abraham Charnes and William W. Cooper

(This item is displayed on page 401 in the print version)

The concept of goal programming was first introduced in 1955 by Abraham Charnes and William Cooper of the Carnegie Institute of Technology, with R. O. Ferguson, a consultant for the Methods Engineering Council. They developed a model for a plan for executive compensation for a division of General Electric (using competing salary offers for executives as multiple goals), and they solved it by reducing it to an equivalent linear programming formulation. However, it was not until 1961 that Charnes and Cooper coined the name goal programming . Yuji Ijiri of Stanford (and a former doctoral student of Cooper's at Carnegie Tech) in 1965 developed the concept of preemptive priorities for treating multiple goals and the general solution approach.

Next we will use Excel to solve a slightly more complicated goal programming modelthat is, the altered Beaver Creek Pottery Company example we developed at the beginning of this chapter, with goals for overtime and maximum storage levels for bowls and mugs:

The spreadsheet for this modified version of our example is shown in Exhibit 9.7. The spreadsheet is set up much the same as the original version of this example, with the exception of the goal constraint for overtime. The formula for this goal constraint is included in cell G8 as = F5 + E8 F8 . In addition, the positive deviational variables for the last two goal constraints are now included in the formulas embedded in cells G9 and G10. For example, in cell G9 the constraint formula is = C9 * B13 + E9 .

Exhibit 9.7.

The Solver Parameters window for this spreadsheet is shown in Exhibit 9.8, and the resulting solution is shown in Exhibit 9.9.

Exhibit 9.8.

(This item is displayed on page 403 in the print version)

Exhibit 9.9.

(This item is displayed on page 403 in the print version)

You will notice that this solution achieves the first two priority goals for minimizing d ₁ and d ₂ , which are in cells E5 and E6. However, the third-priority goal to minimize d ₃ ⁺ is not achieved because its cell (F7) has a value of 24 in it. Thus, we must follow the sequential approach to attempt to obtain a better solution. We accomplish this by including E5=0 (the achievement of our first goal) as a constraint in Solver, as well as our second-priority goal that this solution achieved, E6=0 , and then minimizing F7. This Solver Parameters screen is shown in Exhibit 9.10.

[Page 403]

Exhibit 9.10.

[Page 404]

The solution is shown in Exhibit 9.11. This is the same solution that we obtained for our original version of the model, without the alterations for overtime and production levels. This solution achieves the first three priority goals. We could continue to attempt to achieve the fourth-priority goal by including F7 = 0 as a constraint in Solver and minimizing cell F5 (i.e., d ₁ ⁺ ); however, doing so will not result in a better solution without sacrificing the goal achievement at the higher-priority levels. Thus, this is the best solution we can achieve.