354 Chapter 8 Goal Programming

unlikely that a trial-and-error rounded solution will meet room availability limits. This means
that there is no alternative to imposing the integer condition.
One way to improve the chances for a successful execution of the integer model is to limit
the feasible ranges for the variables xijk by taking into account the availability of other resources.
For example, if the hospital has only two dental surgeons on a given day, no more than two
rooms (of any type) can be assigned to that department on that day. Setting tighter bounds may
be effective in securing an optimal integer solution. Short of meeting this requirement, the only
remaining option is to devise a heuristic for the problem.

PROBLEMS

Section Assigned Problems

8.1 8-1 to 8-11

8.2.1 8-12 to 8-21
8.2.2 8-22 to 8-25

*8-1. Formulate the Fairville tax problem, assuming that the town council is specifying an
additional goal, G5, that requires gasoline tax to equal at least 20% of the total tax bill.
8-2. The NW Shopping Mall conducts special events to attract potential patrons. Among the
events that seem to attract teenagers, the young/middle-aged group, and senior citizens,
the two most popular are band concerts and art shows. Their costs per presentation are
$1500 and $3000, respectively. The total (strict) annual budget allocated to the two events
is $20,000. The mall manager estimates the attendance as follows:

Number attending per presentation

Event Teenagers Young/middle-age Seniors

Band concert 200 100 0

Art show 0 400 250

The manager has set minimum goals of 1500, 450, and 900 for the attendance of teenagers,
the young/middle-aged group, and seniors, respectively. Formulate the problem as a goal
programming model.
*8-3. The Ozark University admission office is processing freshman applications for the up-
coming academic year. The applications fall into three categories: in-state, out-of-state,
and international. The male–female ratios for in-state and out-of-state applicants are
1:1 and 3:2, respectively. For international students, the corresponding ratio is 8:1. The
American College Test (ACT) score is an important factor in accepting new students.
The statistics gathered by the university indicate that the average ACT scores for
in-state, out-of-state, and international students are 27, 26, and 23, respectively. The
committee on admissions has established the following desirable goals for the new
freshman class:
(a) The incoming class is at least 1200 freshmen.
(b) The average ACT score for all incoming students is at least 25.
(c) International students constitute at least 10% of the incoming class.
 Problems 355

(d) The female–male ratio is at least 3:4.

(e) Out-of-state students constitute at least 20% of the incoming class.
Formulate the problem as a GP model.
8-4. Circle K Farms consumes 3 tons of special feed daily. The feed—a mixture of limestone,
corn, and soybean meal—must satisfy the following nutritional requirements:
Calcium. At least 0.8% but not more than 1.2%.
Protein. At least 22%.
Fiber. At most 5%.
The following table gives the nutritional content of the feed ingredients:

lb per lb of ingredient

Ingredient Calcium Protein Fiber

Limestone .380 .00 .00

Corn .001 .09 .02
Soybean meal .002 .50 .08

Formulate the problem as a GP model, and state your opinion regarding the applicability
of GP to this situation.
*8-5. Mantel produces a toy carriage, whose final assembly must include four wheels and two
seats. The factory producing the parts operates three shifts a day. The following table
provides the amounts produced of each part in the three shifts:

Units produced per run

Shift Wheels Seats

1 500 300
2 600 280
3 640 360

Ideally, the number of wheels produced is exactly twice that of the number of seats.
However, because production rates vary from shift to shift, exact balance in production
may not be possible. Mantel is interested in determining the number of production runs
in each shift that minimizes the imbalance in the production of the parts. The capacity
limitations restrict the number of runs to between 4 and 5 for shift 1, 10 and 20 for shift 2,
and 3 and 5 for shift 3. Formulate the problem as a GP model.
8-6. Camyo Manufacturing produces four parts that require the use of a lathe and a drill
press. The two machines operate 10 hours a day. The following table provides the time in
minutes required by each part:

Production time in min

Part Lathe Drill press

1 5 3
2 6 2
3 4 6
4 7 4
356 Chapter 8 Goal Programming

It is desired to balance the two machines by limiting the difference between their total
operation times to at most 30 minutes. The market demand for each part is at least
10 units. Additionally, the number of units of part 1 may not exceed that of part 2.
Formulate the problem as a GP model.
8-7. Two products are manufactured on two sequential machines. The following table gives
the machining times in minutes per unit for the two products:

Machining time in min

Machine Product 1 Product 2

1 5 3
2 6 2

The daily production quotas for the two products are 80 and 60 units, respectively. Each
machine runs 8 hours a day. Overtime, though not desirable, may be used if necessary to
meet the production quota. Formulate the problem as a GP model.
8-8. Vista City Hospital plans the short-stay assignment of surplus beds (those that are not
already occupied) 4 days in advance. During the 4-day planning period, about 30, 25, and
20 patients will require 1-, 2-, or 3-day stays, respectively. Surplus beds during the same
period are estimated at 20, 30, 30, and 30, respectively. Use GP to resolve the problem of
overadmission and underadmission in the hospital.
8-9. The Von Trapp family is in the process of moving to a new city where both parents have
accepted new jobs. In trying to find an ideal location for their new home, the family list
the following goals:
(a) It should be as close as possible to Mrs. Von Trapp’s place of work (within 14 mile).
(b) It should be as far as possible from the noise of the airport (at least 10 miles).
(c) It should be reasonably close to a shopping mall (within 1 mile).
Mr. and Mrs. Von Trapp use a landmark in the city as a reference point and locate
the (x, y)-coordinates of work, airport, and shopping mall at (1, 1), (20, 15), and (4, 7),
respectively (all distances are in miles). Formulate the problem as a GP model. (Note:
The resulting constraints are not linear.)
8-10. Regression analysis. In a laboratory experiment, suppose that yi is the ith observed
(independent) yield associated with the dependent observational measurements
xij, i = 1, 2, c, m; j = 1, 2, c, n. It is desired to determine a linear regression fit into
these data points. Let bj, j = 0, 1, c, n, be the regression coefficients. It is desired to
determine all bj such that the sum of the absolute deviations between the observed
and the estimated yields is minimized. Formulate the problem as a GP model.
8-11. Chebyshev Problem. An alternative goal for the regression model in Problem 8-10 is to
minimize over bj the maximum of the absolute deviations. Formulate the problem as a
GP model.
*8-12. Consider Problem 8-1, dealing with the Fairville tax situation. Solve the problem,
assuming that all five goals have the same weight. Does the solution satisfy all the
goals?
8-13. In Problem 8-2, suppose that the goal of attracting young/middle-aged people is twice as
important as for either of the other two categories (teens and seniors). Find the associ-
ated solution, and check if all the goals have been met.
 Problems 357

8-14. In the Ozark University admission situation described in Problem 8.3, suppose that the
limit on the size of the incoming freshmen class must be met, but the remaining require-
ments can be treated as flexible goals. Further, assume that the ACT score goal is twice as
important as any of the remaining goals.
(a) Solve the problem, and specify whether or not all the goals are satisfied.
(b) If, in addition, the size of the incoming class can be treated as a flexible goal
that is twice as important as the ACT goal, how would this change affect
the solution?
*8-15. In the Circle K model of Problem 8-4, is it possible to satisfy all the nutritional
requirements?
8-16. In Problem 8-5, determine the solution, and specify whether or not the daily production
of wheels and seats can be balanced.
8-17. In Problem 8-6, suppose that the market demand goal is twice as important as that of
balancing the two machines, and that no overtime is allowed. Solve the problem, and
determine if the goals are met.
*8-18. In Problem 8-7, suppose that production strives to meet the quota for the two products,
using overtime if necessary. Find a solution to the problem, and specify the amount of
overtime, if any, needed to meet the production quota.
8-19. In the Vista City Hospital of Problem 8-8, suppose that only the bed limits represent
flexible goals and that all the goals have equal weights. Can all the goals be met?
8-20. The Malco Company has compiled the following table from the files of five of its
employees to study the impact on income of three factors: age, education (expressed in
number of college years completed), and experience (expressed in number of years in
the business).

Age Education Experience Annual income

(year) (year) (year) ($)

30 4 5 40,000
39 5 10 48,000
44 2 14 38,000
48 0 18 36,000
37 3 9 41,000

Use the GP formulation in Problem 8-10 to fit the data into the linear equation
y = b0 + b1x1 + b2x2 + b3x3.
8-21. Solve Problem 8-20 using the Chebyshev method proposed in Problem 8-11.
8-22. In Example 8.2-2, suppose that the budget goal is increased to $150,000. The exposure
goal remains unchanged at 45 million persons. Show how the preemptive method will
reach a solution.3
*8-23. Solve Problem 8-1 using the following priority ordering for the goals:
G1 ≻ G2 ≻ G3 ≻ G4 ≻ G5.

3
You may find it computationally convenient to use interactive AMPL to solve Problems 8-22 to 8-25.
358 Chapter 8 Goal Programming

8-24. Consider Problem 8-2, which deals with the presentation of band concerts and art shows
at the NW Mall. Suppose that the goals set for teens, the young/middle-aged group, and
seniors are referred to as G1, G2, and G3, respectively. Solve the problem for each of the
following priority orders:
(a) G1 ≻ G2 ≻ G3
(b) G3 ≻ G2 ≻ G1
Show that the satisfaction of the goals (or lack of it) can be a function of the priority
order.
8-25. Solve the Ozark University model (Problem 8-3) using the preemptive method, assuming
that the goals are prioritized in the same order given in the problem.