Exercise 5 Goal Programming [PDF]

Citation preview

%JCRVGT



)QCN 2TQiTCOOKPi



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.



241$.'/5



*8-1. 8-2.



Section



Assigned Problems



8.1 8.2.1 8.2.2



8-1 to 8-11 8-12 to 8-21 8-22 to 8-25



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. 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 Band concert Art show



*8-3.



Teenagers



Young/middle-age



Seniors



200 0



100 400



0 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. The Ozark University admission office is processing freshman applications for the upcoming 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.



2TQDNGOu (d) The female–male ratio is at least 3:4. (e) Out-of-state students constitute at least 20% of the incoming class. 8-4.



Formulate the problem as a GP model. 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 Limestone Corn Soybean meal



*8-5.



Calcium



Protein



Fiber



.380 .001 .002



.00 .09 .50



.00 .02 .08



Formulate the problem as a GP model, and state your opinion regarding the applicability of GP to this situation. 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



8-6.



Shift



Wheels



Seats



1 2 3



500 600 640



300 280 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. 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 2 3 4



5 6 4 7



3 2 6 4



%JCRVGT



)QCN 2TQiTCOOKPi



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 2



5 6



3 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).



8-10.



8-11.



*8-12.



8-13.



(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.) 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. 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. 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? 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 associated solution, and check if all the goals have been met.



2TQDNGOu 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 requirements 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.



*8-15. 8-16. 8-17.



*8-18.



8-19. 8-20.



(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? In the Circle K model of Problem 8-4, is it possible to satisfy all the nutritional requirements? In Problem 8-5, determine the solution, and specify whether or not the daily production of wheels and seats can be balanced. 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. 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. 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? 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 (year)



Education (year)



Experience (year)



Annual income ($)



30 39 44 48 37



4 5 2 0 3



5 10 14 18 9



40,000 48,000 38,000 36,000 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.



%JCRVGT



)QCN 2TQiTCOOKPi



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.