Applications and Solutions of Linear Programming

Chapter 4Applications and Solutions of Linear ProgrammingPart 2 Introduction to Management Science and ForecastingLearning ObjectivesFormulate linear programming problems with different objectives.Set up constraints that have unique structures.Translate statements into constraint formulas.Utilize Excel to solve a variety of linear programming problems.Interpret the Excel output of linear programming problems.Make managerial conclusions based on computer (Excel) output.Explain at least two applications of linear programming.After completing this chapter, you should be able to:2Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Elements of Linear ProgrammingIssues in formulating problemsDegree of simplification of the real-world problemViolation of the assumptions of linear programming (additivity, divisibility, certainty, and proportionality)Linear programming problems may include:Different types of decision variables definitionsDifferent types of constraintsDifferent types of objective functions.3Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-1 Product-Mix ProblemThe Style and Comfort Furniture Manufacturing Company wishes to determine its production schedule for the next quarter. The company produces four types of furniture, including sofas, love seats, recliners, and coffee tables. The profit contribution from selling one sofa is $120, one love seat is $105, one recliner is $150, and one coffee table is $73. The quarterly production budget is set at $180,000. Each unit of a sofa, love seat, recliner, and coffee table costs $400, $300, $500, and $150, respectively. The sales forecasts indicate that the potential sales volume is limited to 200 units of sofas, 150 units of love seats, 100 units of recliners, and 400 units of coffee tables. There are an aggregate of 800 machine hours available and 1,200 labor hours available. Table 4-1 summarizes the number of machine hours and the number of labor hours required per unit of each product.4Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 4–1 Per Unit Machine and Labor Hour Required for Each Product5Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Style of Comfort Furniture Example6Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 4-1 Input Screen for the Style and Comfort Furniture Company Problem7Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 4–2 Solver Dialog BoxExhibit 4–3 Add Constraint Dialog Box8Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 4–4 Completed Solver Dialog BoxThere are three types of Solver cells:Target cell shows the overall performance measure (i.e., the maximum profit or the minimum cost). Output cell shows the output or quantity of the decision variables based on the changing cells.Data cells simply show the data of the problem (constraint coefficients, objective function coefficients, and right-hand-side constraints).9Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 4-5 Solver Options Dialog Box10Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 4–7 Output Screen for the Style and Comfort Furniture Company Problem11Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 4–2 Cost per Ounce and Dietary Requirements for Diet Problem12Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-2 Diet Problem13Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-3 Blending ProblemFormulate the appropriate model for the following blending problem: The sugar content of three juices—orange, banana, and pineapple—is 10, 15, and 20 percent, respectively. How many quarts of each must be mixed together to achieve one gallon (four quarts) that has a sugar content of at least 17 percent to minimize cost? The cost per quart is 20 cents for orange juice, 30 cents for banana juice, and 40 cents for pineapple juice.SolutionVariable definitionsO = quantity of orange juice in quartsB = quantity of banana juice in quartsP = quantity of pineapple juice in quarts14Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Marketing ApplicationsApplications of linear programming in marketingMedia selection—how to allocate an advertising budget among different media of advertising.Determination of the optimal assignment of salespeople that work for the company among the sales territories.Marketing research which the objective is to determine the best number of interviews, mailings, or phone calls, given a number of client-specified constraints and the cost considerations.15Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-5 Media SelectionThe Long Last Appliance Sales Company is in the business of selling appliances such as microwave ovens, traditional ovens, refrigerators, dishwashers, washers, dryers, and the like. The company has stores in the greater Chicagoland area and has a monthly advertising budget of $90,000.Among its options are radio advertising, advertising in the cable TV channels, newspaper advertising, and direct-mail advertising. A 30-second advertising spot on the local cable channel costs $1,800, a 30-second radio ad costs $350, a half-page ad in the local newspaper costs $700, and a single mailing of direct-mail insertion for the entire region costs $1,200 per mailing. The number of potential buying customers reached per advertising medium usage is as follows:Radio 7,000TV 50,000Newspaper 18,000Direct mail 34,000Due to company restrictions and availability of media, the maximum number of usages of each medium is limited to the following:Radio 35TV 2 5Newspaper 30Direct mail 1816Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-5 (cont’d)The management of the company has met and decided that in order to ensure a balanced utilization of different types of media and to portray a positive image of the company, at least 10 percent of the advertisements must be on TV. No more than 40 percent of the advertisements must be on radio. The cost of advertising allocated to TV and direct mail cannot exceed 60 percent of the total advertising budget.What is the optimal allocation of the budget among the four media? What is the total maximum audience contact?17Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-5 (cont’d)18Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 4–8 Output Screen for the Long Last Appliance Sales Company19Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 4–9 Excel Answer Report for the Long Last Appliance Sales Company20Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Marketing ResearchStages of marketing research study development:Design study.Conduct marketing survey.Analyze data and obtain results.Make recommendations based on the results.21Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-6 Market ResearchMarket Facts Inc. is a marketing research firm that works with client companies to determine consumer reaction toward various products and services. A client company requested that Market Facts investigate the consumer reaction to a recently developed electronic device. Market Facts and the client company agreed that a combination of telephone interviews and direct-mail questionnaires would be used to obtain the information from different type of households.The households are divided into six categories:Households containing a single person under 40 years old and without children under 18 years of age.Households containing married people under 40 years old and without children under 18 years of age.Households containing single parents with children under 18 years of age.Households containing married families with children under 18 years of age.Households containing single people over 40 years old without children under 18 years of age.Households containing married people over 40 years old without children under 18 years of age.22Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-6 (cont’d)RestrictionsAt least 60 percent of the phone interviews must be conducted at households with children.At least 50 percent of the direct-mail questionnaires must be mailed to households with children.No more than 30 percent of the phone interviews and mail-in questionnaires must be conducted at households with single people.At least 25 percent of the phone interviews and mail-in questionnaires must be conducted at households that contain married couples.23Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-6 (cont’d)Problem formulation24Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-6 (cont’d)Problem solution25Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Financial ApplicationsPlanning Problems for BanksLinear programming can be very beneficial in banking decisions.Financial planning: bankers must decide how a bank wants to allocate its funds among the various types of loans and investment securities. Portfolio management: decisions are based on maximizing annual rate of return subject to state and federal regulations, and bank policies and restrictions.26Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-7 Financial PlanningFirst American Bank issues five types of loans. In addition, to diversify its portfolio, and to minimize risk, the bank invests in risk-free securities. The loans and the risk-free securities with their annual rate of return are given in Table 4-3.Table 4-3 Rates of Return for Financial Planning ProblemType of Loan or Security Annual Rate of Return (%)Home mortgage (first) 6Home mortgage (second) 8Commercial loan 11Automobile loan 9Home improvement loan 10Risk-free securities 427Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-7 Financial Planning (cont’d)The bank’s objective is to maximize the annual rate of return on investments subject to the following policies, restrictions, and regulations:The bank has $90 million in available funds. Risk-free securities must contain at least 10 percent of the total funds available for investments.Home improvement loans cannot exceed $8,000,000.The investment in mortgage loans must be at least 60 percent of all the funds invested in loans.The investment in first mortgage loans must be at least twice as much as the investment in second mortgage loans.Home improvement loans cannot exceed 40 percent of the funds invested in first mortgage loans.Automobile loans and home improvement loans together may not exceed the commercial loans.Commercial loans cannot exceed 50 percent of the total funds invested in mortgage loans.28Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-7 Financial Planning (cont’d)29Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-7 Financial Planning (cont’d)30Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-8 Portfolio SelectionA conservative investor has $100,000 to invest. The investor has decided to use three vehicles for generating income: municipal bonds, a certificate of deposit (CD), and a money market account. After reading a financial newsletter, the investor has also identified several additional restrictions on the investments:No more than 40 percent of the investment should be in bonds.The proportion allocated to the money market account should be at least double the amount in the CD.The annual return will be 8 percent for bonds, 9 percent for the CD, and 7 percent for the money market account. Assume the entire amount will be invested. Formulate the LP model for this problem, ignoring any transaction costs and the potential for different investment lives. Assume that the investor wants to maximize the total annual return.31Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-8 Portfolio Selection (cont’d)32Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Production ApplicationsLinear programming in production management in manufacturing:Multiperiod production schedulingWorkforce schedulingMake-or-buy decisions.33Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-9 Multiperiod Production SchedulingMorton and Monson Inc. is a small manufacturer of parts for the aerospace industry. The production capacity for the next four months is given as follows:Production Capacity in UnitsMonth Regular Production Overtime ProductionJanuary 3,000 500February 2,000 400March 3,000 600April 3,500 800The regular cost of production is $500 per unit and the cost of overtime production is $150 per unit in addition to the regular cost of production. The company can utilize inventories to reduce fluctuations in production, but carrying one unit of inventory costs the company $40 per unit per month. Currently there are no units in inventory. However, the company wants to maintain a minimum safety stock of 100 units of inventory during the months of January, February, and March. The estimated demand for the next four months is as follows:Month January February March AprilDemand 2,800 3,000 3,500 3,00034Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-9 Multiperiod Production Scheduling (cont’d)Continued on next slide.35Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-9 Multiperiod Production Scheduling (cont’d)36Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-9 Multiperiod Production Scheduling (cont’d)37Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-10 Workforce Scheduling38Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-11 Make-or-Buy Decisions39Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-12 Agriculture ApplicationsA farm owner in Des Moines, Iowa, is interested in determining how to divide the farmland among four different types of crops. The farmer owns two farms in separate locations and has decided to plant the following four types of crops in these farms: corn, wheat, bean, and cotton. The first farm consists of 1,450 acres of land, while the second farm consists of 850 acres of land. Any of the four crops may be planted on either farm. However, after a survey of the land, based on the characteristics of the farmlands, Table 4-7 shows the maximum acreage restrictions the farmer has placed for each crop.40Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Data Envelopment AnalysisData envelopment analysis (DEA)The use linear programming to measure the relative efficiency of the departments within an organization or relative efficiencies of two different organizations.Fast food restaurants, hospitals, schools, and banks.Measuring the efficiency of departments within the same organization is difficult because departments have multiple input measures (number of workers, cost of labor, cost of machine operations, pay scale for employees, and cost of advertising) and multiple output measures (profit, sales, and market share).41Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 4-12 Airline EfficiencyA consumer advocacy group would like to evaluate the efficiency of three airline companies with respect to several criteria that are important to consumers. The three companies are Beta, Unified, and Southeast. The output measures are identified as average minutes late arriving, number of luggage loser per 10,000 customers, waiting time for check-in, friendliness, and quality of air service (result of a questionnaire that measured this output on a 100-point scale). The input measures were labor cost per day, number of flights per day, and over head cost per day. Table 4-9 summarizes the results.42Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Other ApplicationsTransportation problemsDeveloping distribution plans that will minimize total distribution costs given the capacities of the various factories and the needs of the warehouses.Assignment problemsAssigning jobs to machines in such a way that the total cost of performing the jobs is minimized.Project management problemsFinding the minimum project duration for project competition to shorten various project tasks and minimize total project costs.43Copyright © 2007 The McGraw-Hill Companies. All rights reserved.