In the product mix example in this chapter, Quick-Screen is considering adding some extra operators who would reduce processing times for each of the four clothing items by 10%. This would also increase the cost of each item by 10% and thus reduce unit profits by this same amount (because an increase in selling price would not be possible). Can this type of sensitivity analysis be evaluated using only original solution output, or will the model need to be solved again? Should Quick-Screen undertake this alternative?
In this problem, the profit per shirt is computed from the selling price less fixed and variable costs. The computer solution output shows the shadow price for T-shirts to be $4.11. If Quick-Screen decided to acquire extra T-shirts, could the company expect to earn an additional $4.11 for each extra T-shirt it acquires above 500, up to the sensitivity range limit of T-shirts?
If Quick-Screen were to produce equal numbers of each of the four shirts, how would the company reformulate the linear programming model to reflect this condition? What is the new solution to this reformulated model?
In the diet example in this chapter, what would be the effect on the optimal solution of increasing the minimum calorie requirement for the breakfast to 500 calories? to 600 calories ?
Increase the breakfast calorie requirement to 700 calories and reformulate the model to establish upper limits on the servings of each food item to what you think would be realistic and appetizing. Determine the solution for this reformulated model.
In the investment example in this chapter, how would the solution be affected if the requirement that the entire $70,000 be invested were relaxed such that it is the maximum amount available for investment?
If the entire amount available for investment does not have to be invested and the amount available is increased by $10,000 (to $80,000), how much will the total optimal return increase? Will the entire $10,000 increase be invested in one alternative?
For the marketing example in this chapter, if the budget is increased by $20,000, how much will audience exposures be increased?
If Biggs Department Store were to want the same total number of people exposed to each of the three types of advertisements, how should the linear programming model be reformulated? What would be the new solution for this reformulated model?
For the transportation example in this chapter, suppose that television sets not shipped were to incur storage costs of $9 at Cincinnati, $6 at Atlanta, and $7 at Pittsburgh. How would these storage costs be reflected in the linear programming model for this example problem, and what would the new solution be, if any?
The Zephyr Television Company is considering leasing a new warehouse in Memphis. The new warehouse would have a supply of 200 television sets, with shipping costs of $18 to New York, $9 to Dallas, and $12 to Detroit. If the total transportation cost for the company (ignoring the cost of leasing the warehouse) is less than with the current warehouses, the company will lease the new warehouse. Should the warehouse be leased?
If supply could be increased at any one warehouse, which should it be? What restrictions would there be on the amount of the increase?
For the blend example in this chapter, if the requirement that "at least 3,000 barrels of each grade of motor oil" were changed to exactly 3,000 barrels of each grade, how would this affect the optimal solution?
If the company could acquire more of one of the three components , which should it be? What would be the effect on the total profit of acquiring more of this component?
On their farm, the Friendly family grows apples that they harvest each fall and make into three productsapple butter, applesauce, and apple jelly. They sell these three items at several local grocery stores, at craft fairs in the region, and at their own Friendly Farm Pumpkin Festival for 2 weeks in October. Their three primary resources are cooking time in their kitchen, their own labor time, and the apples. They have a total of 500 cooking hours available, and it requires 3.5 hours to cook a 10-gallon batch of apple butter, 5.2 hours to cook 10 gallons of applesauce, and 2.8 hours to cook 10 gallons of jelly . A 10-gallon batch of apple butter requires 1.2 hours of labor, a batch of sauce takes 0.8 hour , and a batch of jelly requires 1.5 hours. The Friendly family has 240 hours of labor available during the fall. They produce about 6,500 apples each fall. A batch of apple butter requires 40 apples, a 10-gallon batch of applesauce requires 55 apples, and a batch of jelly requires 20 apples. After the products are canned, a batch of apple butter will generate $190 in sales revenue, a batch of applesauce will generate a sales revenue of $170, and a batch of jelly will generate sales revenue of $155. The Friendlys want to know how many batches of apple butter, applesauce, and apple jelly to produce in order to maximize their revenues .
A hospital dietitian prepares breakfast menus every morning for the hospital patients . Part of the dietitian's responsibility is to make sure that minimum daily requirements for vitamins A and B are met. At the same time, the cost of the menus must be kept as low as possible. The main breakfast staples providing vitamins A and B are eggs, bacon, and cereal. The vitamin requirements and vitamin contributions for each staple follow:
An egg costs $0.04, a bacon strip costs $0.03, and a cup of cereal costs $0.02. The dietitian wants to know how much of each staple to serve per order to meet the minimum daily vitamin requirements while minimizing total cost.
Lakeside Boatworks is planning to manufacture three types of molded fiberglass recreational boatsa fishing (bass) boat, a ski boat, and a small speedboat. The estimated selling price and variable cost for each type of boat are summarized in the following table:
The company has incurred fixed costs of $2,800,000 to set up its manufacturing operation and begin production. Lakeside has also entered into agreements with several boat dealers in the region to provide a minimum of 70 bass boats, 50 ski boats, and 50 speedboats. Alternatively, the company is unsure of what actual demand will be, so it has decided to limit production to no more than 120 of any one boat. The company wants to determine the number of boats that it must sell to break even while minimizing its total variable cost.
The Pyrotec Company produces three electrical productsclocks, radios, and toasters. These products have the following resource requirements:
The manufacturer has a daily production budget of $2,000 and a maximum of 660 hours of labor. Maximum daily customer demand is for 200 clocks, 300 radios, and 150 toasters. Clocks sell for $15, radios for $20, and toasters for $12. The company wants to know the optimal product mix that will maximize profit.
Betty Malloy, owner of the Eagle Tavern in Pittsburgh, is preparing for Super Bowl Sunday, and she must determine how much beer to stock. Betty stocks three brands of beerYodel, Shotz, and Rainwater. The cost per gallon (to the tavern owner) of each brand is as follows :
The tavern has a budget of $2,000 for beer for Super Bowl Sunday. Betty sells Yodel at a rate of $3.00 per gallon, Shotz at $2.50 per gallon, and Rainwater at $1.75 per gallon. Based on past football games , Betty has determined the maximum customer demand to be 400 gallons of Yodel, 500 gallons of Shotz, and 300 gallons of Rainwater. The tavern has the capacity to stock 1,000 gallons of beer; Betty wants to stock up completely. Betty wants to determine the number of gallons of each brand of beer to order so as to maximize profit.
The Kalo Fertilizer Company produces two brands of lawn fertilizerSuper Two and Green Growat plants in Fresno, California, and Dearborn, Michigan. The plant at Fresno has resources available to produce 5,000 pounds of fertilizer daily; the plant at Dearborn has enough resources to produce 6,000 pounds daily. The cost per pound of producing each brand at each plant is as follows:
The company has a daily budget of $45,000 for both plants combined. Based on past sales, the company knows the maximum demand (converted to a daily basis) is 6,000 pounds for Super Two and 7,000 pounds for Green Grow. The selling price is $9 per pound for Super Two and $7 per pound for Green Grow. The company wants to know the number of pounds of each brand of fertilizer to produce at each plant in order to maximize profit.
Grafton Metalworks Company produces metal alloys from six different ores it mines. The company has an order from a customer to produce an alloy that contains four metals according to the following specifications: at least 21% of metal A, no more than 12% of metal B, no more than 7% of metal C, and between 30% and 65% of metal D. The proportion of the four metals in each of the six ores and the level of impurities in each ore are provided in the following table:
When the metals are processed and refined, the impurities are removed.
The company wants to know the amount of each ore to use per ton of the alloy that will minimize the cost per ton of the alloy.
The Roadnet Transport Company has expanded its shipping capacity by purchasing 90 trailer trucks from a bankrupt competitor. The company subsequently located 30 of the purchased trucks at each of its shipping warehouses in Charlotte, Memphis, and Louisville. The company makes shipments from each of these warehouses to terminals in St. Louis, Atlanta, and New York. Each truck is capable of making one shipment per week. The terminal managers have each indicated their capacity for extra shipments. The manager at St. Louis can accommodate 40 additional trucks per week, the manager at Atlanta can accommodate 60 additional trucks, and the manager at New York can accommodate 50 additional trucks . The company makes the following profit per truck-load shipment from each warehouse to each terminal. The profits differ as a result of differences in products shipped, shipping costs, and transport rates:
The company wants to know how many trucks to assign to each route (i.e., warehouse to terminal) to maximize profit.
The Hickory Cabinet and Furniture Company produces sofas, tables, and chairs at its plant in Greensboro, North Carolina. The plant uses three main resources to make furniturewood, upholstery, and labor. The resource requirements for each piece of furniture and the total resources available weekly are as follows:
The furniture is produced on a weekly basis and stored in a warehouse until the end of the week, when it is shipped out. The warehouse has a total capacity of 650 pieces of furniture. Each sofa earns $400 in profit, each table, $275, and each chair, $190. The company wants to know how many pieces of each type of furniture to make per week to maximize profit.
Lawns Unlimited is a lawn care and maintenance company. One of its services is to seed new lawns as well as bare or damaged areas in established lawns. The company uses three basic grass seed mixes it calls Home 1, Home 2, and Commercial 3. It uses three kinds of grass seedtall fescue, mustang fescue, and bluegrass. The requirements for each grass mix are as follows:
The company believes it needs to have at least 1,200 pounds of Home 1 mix, 900 pounds of Home 2 mix, and 2,400 pounds of Commercial 3 seed mix on hand. A pound of tall fescue costs the company $1.70, a pound of mustang fescue costs $2.80, and a pound of bluegrass costs $3.25. The company wants to know how many pounds of each type of grass seed to purchase to minimize cost.
Alexandra Bergson has subdivided her 2,000-acre farm into three plots and has contracted with three local farm families to operate the plots. She has instructed each sharecropper to plant three crops: corn, peas, and soybeans. The size of each plot has been determined by the capabilities of each local farmer. Plot sizes, crop restrictions, and profit per acre are given in the following tables:
Any of the three crops may be planted on any of the plots; however, Alexandra has placed several restrictions on the farming operation. At least 60% of each plot must be under cultivation. Further, to ensure that each sharecropper works according to his or her potential and resources (which determined the acreage allocation), she wants the same proportion of each plot to be under cultivation. Her objective is to determine how much of each crop to plant on each plot to maximize profit.
As a result of a recently passed bill, a congressman's district has been allocated $4 million for programs and projects. It is up to the congressman to decide how to distribute the money. The congressman has decided to allocate the money to four ongoing programs because of their importance to his districta job training program, a parks project, a sanitation project, and a mobile library. However, the congressman wants to distribute the money in a manner that will please the most voters, or, in other words, gain him the most votes in the upcoming election. His staff's estimates of the number of votes gained per dollar spent for the various programs are as follows:
In order also to satisfy several local influential citizens who financed his election, he is obligated to observe the following guidelines:
Any money not spent in the district will be returned to the government; therefore, the congressman wants to spend it all. The congressman wants to know the amount to allocate to each program to maximize his votes.
Anna Broderick is the dietitian for the State University football team, and she is attempting to determine a nutritious lunch menu for the team. She has set the following nutritional guidelines for each lunch serving:
She selects the menu from seven basic food items, as follows, with the nutritional contribution per pound and the cost as given:
The dietitian wants to select a menu to meet the nutritional guidelines while minimizing the total cost per serving.
The Midland Tool Shop has four heavy presses it uses to stamp out prefabricated metal covers and housings for electronic consumer products. All four presses operate differently and are of different sizes. Currently the firm has a contract to produce three products. The contract calls for 400 units of product 1; 570 units of product 2; and 320 units of product 3. The time (in minutes) required for each product to be produced on each machine is as follows:
Machine 1 is available for 150 hours, machine 2 for 240 hours, machine 3 for 200 hours, and machine 4 for 250 hours. The products also result in different profits, according to the machine they are produced on, because of time, waste, and operating cost. The profit per unit per machine for each product is summarized as follows:
The company wants to know how many units of each product to produce on each machine in order to maximize profit.
The Cabin Creek Coal (CCC) Company operates three mines in Kentucky and West Virginia, and it supplies coal to four utility power plants along the East Coast. The cost of shipping coal from each mine to each plant, the capacity at each of the three mines, and the demand at each plant are shown in the following table:
The cost of mining and processing coal is $62 per ton at mine 1, $67 per ton at mine 2, and $75 per ton at mine 3. The percentage of ash and sulfur content per ton of coal at each mine is as follows:
Each plant has different cleaning equipment. Plant 1 requires that the coal it receives have no more than 6% ash and 5% sulfur; plant 2 coal can have no more than 5% ash and sulfur combined; plant 3 can have no more than 5% ash and 7% sulfur; and plant 4 can have no more than 6% ash and sulfur combined. CCC wants to determine the amount of coal to produce at each mine and ship to its customers that will minimize its total cost.
Ampco is a manufacturing company that has a contract to supply a customer with parts from April through September. However, Ampco does not have enough storage space to store the parts during this period, so it needs to lease extra warehouse space during the 6-month period. Following are Ampco's space requirements:
The rental agent Ampco is dealing with has provided it with the following cost schedule for warehouse space. This schedule shows that the longer the space is rented, the cheaper it is. For example, if Ampco rents space for all 6 months, it costs $1.00/ft. 2 per month, whereas if it rents the same space for only 1 month, it costs $1.70/ft. 2 per month:
Ampco can rent any amount of warehouse space on a monthly basis at any time for any number of (whole) months. Ampco wants to determine the least costly rental agreement that will exactly meet its space needs each month and avoid having any unused space.
Brooks City has three consolidated high schools, each with a capacity of 1,200 students. The school board has partitioned the city into five busing districtsnorth, south, east, west, and centraleach with different high school student populations. The three schools are located in the central, west, and south districts. Some students must be bused outside their districts, and the school board wants to minimize the total bus distance traveled by these students. The average distances from each district to the three schools and the total student population in each district are as follows:
The school board wants to determine the number of students to bus from each district to each school to minimize the total busing miles traveled.
The Southfork Feed Company makes a feed mix from four ingredientsoats, corn, soybeans, and a vitamin supplement. The company has 300 pounds of oats, 400 pounds of corn, 200 pounds of soybeans, and 100 pounds of vitamin supplement available for the mix. The company has the following requirements for the mix:
A pound of oats costs $0.50; a pound of corn, $1.20; a pound of soybeans, $0.60; and a pound of vitamin supplement, $2.00. The feed company wants to know the number of pounds of each ingredient to put in the mix in order to minimize cost.
The United Charities annual fund-raising drive is scheduled to take place next week. Donations are collected during the day and night, by telephone, and through personal contact. The average donation resulting from each type of contact is as follows:
The charity group has enough donated gasoline and cars to make at most 300 personal contacts during one day and night combined. The volunteer minutes required to conduct each type of interview are as follows:
The charity has 20 volunteer hours available each day and 40 volunteer hours available each night. The chairperson of the fund-raising drive wants to know how many different types of contacts to schedule in a 24-hour period (i.e., 1 day and 1 night) to maximize total donations.
Ronald Thump is interested in expanding his firm. After careful consideration, he has determined three areas in which he might invest additional funds: (1) product research and development, (2) manufacturing operations improvements, and (3) advertising and sales promotion. He has $500,000 available for investment in the firm. He can invest in its advertising and sales promotion program every year, and each dollar invested in this manner is expected to yield a return of the amount invested plus 20% yearly. He can invest in manufacturing operations improvements every 2 years , with an expected return of the investment plus 30% (at the end of each 2-year period). An investment in product research and development would be for a 3-year period, with an expected return of the investment plus 50% (at the end of the 3-year period). To diversify the total initial investment, he wishes to include the requirement that at least $30,000 must be invested on the advertising and sales promotion program, at least $40,000 on manufacturing operations improvements, and at least $50,000 on product research and development initially (at the beginning of the first year). Ronald wants to know how much should be invested in each of the three alternatives, during each year of a 4-year period, to maximize the total ending cash value of the initial $500,000 investment.
Iggy Olweski, a professional football player, is retiring , and he is thinking about going into the insurance business. He plans to sell three types of policieshomeowner's insurance, auto insurance, and life insurance. The average amount of profit returned per year by each type of insurance policy is as follows:
Each homeowner's policy will cost $14 to sell and maintain; each auto policy, $12; and each life insurance policy, $35. Iggy has projected a budget of $35,000 per year. In addition, the sale of a homeowner's policy will require 6 hours of effort; the sale of an auto policy, 3 hours; and the sale of a life insurance policy, 12 hours. Based on the number of working hours he and several employees could contribute, Iggy has estimated that he would have available 20,000 hours per year. Iggy wants to know how many of each type of insurance policy he would have to sell each year in order to maximize profit.
A publishing house publishes three weekly magazines Daily Life, Agriculture Today , and Surf's Up . Publication of one issue of each of the magazines requires the following amounts of production time and paper:
Each week the publisher has available 120 hours of production time and 3,000 pounds of paper. Total circulation for all three magazines must exceed 5,000 issues per week if the company is to keep its advertisers. The selling price per issue is $2.25 for Daily Life , $4.00 for Agriculture Today , and $1.50 for Surf's Up . Based on past sales, the publisher knows that the maximum weekly demand for Daily Life is 3,000 issues; for Agriculture Today , 2,000 issues; and for Surf's Up , 6,000 issues. The production manager wants to know the number of issues of each magazine to produce weekly in order to maximize total sales revenue.
The manager of a department store in Seattle is attempting to decide on the types and amounts of advertising the store should use. He has invited representatives from the local radio station, television station, and newspaper to make presentations in which they describe their audiences. The television station representative indicates that a TV commercial, which costs $15,000, would reach 25,000 potential customers. The breakdown of the audience is as follows:
The newspaper representative claims to be able to provide an audience of 10,000 potential customers at a cost of $4,000 per ad. The breakdown of the audience is as follows:
The radio station representative says that the audience for one of the station's commercials, which costs $6,000, is 15,000 customers. The breakdown of the audience is as follows:
The store has the following advertising policy:
Available space limits the number of newspaper ads to seven. The store wants to know the optimal number of each type of advertising to purchase to minimize total cost.
If the store were to consider this station along with the other media alternatives, how would this affect the solution?
The Mill Mountain Coffee Shop blends coffee on the premises for its customers. It sells three basic blends in 1-pound bags, Special, Mountain Dark, and Mill Regular. It uses four different types of coffee to produce the blendsBrazilian, mocha, Columbian, and mild. The shop has the following blend recipe requirements:
The cost of Brazilian coffee is $2.00 per pound, the cost of mocha is $2.75 per pound, the cost of Columbian is $2.90 per pound, and the cost of mild is $1.70 per pound. The shop has 110 pounds of Brazilian coffee, 70 pounds of mocha, 80 pounds of Columbian, and 150 pounds of mild coffee available per week. The shop wants to know the amount of each blend it should prepare each week to maximize profit.
Toyz is a large discount toy store in Valley Wood Mall. The store typically has slow sales in the summer months that increase dramatically and rise to a peak at Christmas. During the summer and fall, the store must build up its inventory to have enough stock for the Christmas season . To purchase and build up its stock during the months when its revenues are low, the store borrows money.
Following is the store's projected revenue and liabilities schedule for July through December (where revenues are received and bills are paid at the first of each month):
At the beginning of July, the store can take out a 6-month loan that carries an 11% interest rate and must be paid back at the end of December. The store cannot reduce its interest payment by paying back the loan early. The store can also borrow money monthly at a rate of 5% interest per month.
Money borrowed on a monthly basis must be paid back at the beginning of the next month. The store wants to borrow enough money to meet its cash flow needs while minimizing its cost of borrowing .
The Skimmer Boat Company manufactures the Water Skimmer bass fishing boat. The company purchases the engines it installs in its boats from the Mar-gine Company, which specializes in marine engines. Skimmer has the following production schedule for April, May, June, and July:
Mar-gine usually manufactures and ships engines to Skimmer during the month the engines are due. However, from April through July, Mar-gine has a large order with another boat customer, and it can manufacture only 40 engines in April, 60 in May, 90 in June, and 50 in July. Mar-gine has several alternative ways to meet Skimmer's production schedule. It can produce up to 30 engines in January, February, and March and carry them in inventory at a cost of $50 per engine per month until it ships them to Skimmer. For example, Mar-gine could build an engine in January and ship it to Skimmer in April, incurring $150 in inventory charges. Mar-gine can also manufacture up to 20 engines in the month they are due on an overtime basis, with an additional cost of $400 per engine. Mar-gine wants to determine the least costly production schedule that will meet Skimmer's schedule.
The Donnor meat processing firm produces wieners from four ingredients : chicken, beef, pork, and a cereal additive. The firm produces three types of wieners: regular, beef, and all-meat. The company has the following amounts of each ingredient available on a daily basis:
Each type of wiener has certain ingredient specifications, as follows.
The firm wants to know how many pounds of wieners of each type to produce to maximize profits.
Joe Henderson runs a small metal parts shop. The shop contains three machinesa drill press, a lathe, and a grinder. Joe has three operators, each certified to work on all three machines. However, each operator performs better on some machines than on others. The shop has contracted to do a big job that requires all three machines. The times required by the various operators to perform the required operations on each machine are summarized as follows:
Joe Henderson wants to assign one operator to each machine so that the total operating time for all three operators is minimized.
Green Valley Mills produces carpet at plants in St. Louis and Richmond. The plants ship the carpet to two outlets in Chicago and Atlanta. The cost per ton of shipping carpet from each of the two plants to the two warehouses is as follows:
The plant at St. Louis can supply 250 tons of carpet per week, and the plant at Richmond can supply 400 tons per week. The Chicago outlet has a demand of 300 tons per week; the outlet at Atlanta demands 350 tons per week. Company managers want to determine the number of tons of carpet to ship from each plant to each outlet in order to minimize the total shipping cost.
Dr. Maureen Becker, the head administrator at Jefferson County Regional Hospital, must determine a schedule for nurses to make sure there are enough of them on duty throughout the day. During the day, the demand for nurses varies. Maureen has broken the day into twelve 2-hour periods. The slowest time of the day encompasses the three periods from 12:00 A.M. to 6:00 A.M. , which, beginning at midnight, require a minimum of 30, 20, and 40 nurses, respectively. The demand for nurses steadily increases during the next four daytime periods. Beginning with the 6:00 A.M. 8:00 A.M. period, a minimum of 50, 60, 80, and 80 nurses are required for these four periods, respectively. After 2:00 P.M. the demand for nurses decreases during the afternoon and evening hours. For the five 2-hour periods beginning at 2:00 P.M. and ending at midnight, 70, 70, 60, 50, and 50 nurses are required, respectively. A nurse reports for duty at the beginning of one of the 2-hour periods and works 8 consecutive hours (which is required in the nurses' contract). Dr. Becker wants to determine a nursing schedule that will meet the hospital's minimum requirements throughout the day while using the minimum number of nurses.
A manufacturer of bathroom fixtures produces fiberglass bathtubs in an assembly operation that consists of three processesmolding, smoothing, and painting. The number of units that can undergo each process in an hour is as follows:
( Note : The three processes are continuous and sequential; thus, no more units can be smoothed or painted than have been molded.) The labor costs per hour are $8 for molding, $5 for smoothing, and $6.50 for painting. The company's labor budget is $3,000 per week. A total of 120 hours of labor is available for all three processes per week. Each completed bathtub requires 90 pounds of fiberglass, and the company has a total of 10,000 pounds of fiberglass available each week. Each bathtub earns a profit of $175. The manager of the company wants to know how many hours per week to run each process to maximize profit.
The admissions office at State University wants to develop a planning model for next year's entering freshman class. The university has 4,500 available openings for freshmen. Tuition is $8,600 for an in-state student and $19,200 for an out-of-state student. The university wants to maximize the money it receives from tuition, but by state mandate it can admit no more than 47% out-of-state students. Also, each college in the university must have at least 30% in-state students in its freshman class. In order to be ranked in several national magazines, it wants the freshman class to have an average SAT score of 1150. Following are the average SAT scores for last year's freshman class for in-state and out-of-state students in each college in the university plus the maximum size of the freshman class for each college:
A manufacturing firm located in Chicago ships its product by railroad to Detroit. Several different routes are available, as shown in the following diagram, referred to as a network:
Each circle in the network represents a railroad junction. Each arrow is a railroad branch between two junctions. The number above each arrow is the cost ($1,000s) necessary to ship 1 ton of product from junction to junction. The firm wants to ship 5 tons of its product from Chicago to Detroit at the minimum cost.
A refinery blends four petroleum components into three grades of gasolineregular, premium, and diesel . The maximum quantities available of each component and the cost per barrel are as follows:
To ensure that each gasoline grade retains certain essential characteristics, the refinery has put limits on the percentages of the components in each blend. The limits as well as the selling prices for the various grades are as follows:
The refinery wants to produce at least 3,000 barrels of each grade of gasoline. Management wishes to determine the optimal mix of the four components that will maximize profit.
The Cash and Carry Building Supply Company has received the following order for boards in three lengths:
The company has 25-foot standard-length boards in stock. Therefore, the standard-length boards must be cut into the lengths necessary to meet order requirements. Naturally, the company wishes to minimize the number of standard-length boards used. The company must therefore determine how to cut up the 25- foot boards to meet the order requirements and minimize the number of standard-length boards used.
An investment firm has $1 million to invest in stocks, bonds , certificates of deposit, and real estate. The firm wishes to determine the mix of investments that will maximize the cash value at the end of 6 years.
Opportunities to invest in stocks and bonds will be available at the beginning of each of the next 6 years. Each dollar invested in stocks will return $1.20 (a profit of $0.20) 2 years later; the return can be immediately reinvested in any alternative. Each dollar invested in bonds will return $1.40 3 years later; the return can be reinvested immediately.
Opportunities to invest in certificates of deposit will be available only once, at the beginning of the second year. Each dollar invested in certificates will return $1.80 four years later. Opportunities to invest in real estate will be available at the beginning of the fifth and sixth years. Each dollar invested will return $1.10 one year later.
To minimize risk, the firm has decided to diversify its investments. The total amount invested in stocks cannot exceed 30% of total investments, and at least 25% of total investments must be in certificates of deposit.
The firm's management wishes to determine the optimal mix of investments in the various alternatives that will maximize the amount of cash at the end of the sixth year.
The Jones, Jones, Smith, and Rodman commodities trading firm knows the prices at which it will be able to buy and sell a certain commodity during the next 4 months. The buying price ( c i ) and selling price ( p i ) for each of the given months ( i ) are as follows:
The firm's warehouse has a maximum capacity of 10,000 bushels. At the beginning of the first month, 2,000 bushels are in the warehouse. The trading firm wants to know the amounts that should be bought and sold each month in order to maximize profit. Assume that no storage costs are incurred and that sales are made at the beginning of the month, followed by purchases.
The production manager of Videotechnics Company is attempting to determine the upcoming 5-month production schedule for video recorders. Past production records indicate that 2,000 recorders can be produced per month. An additional 600 recorders can be produced monthly on an overtime basis. Unit cost is $10 for recorders produced during regular working hours and $15 for those produced on an overtime basis. Contracted sales per month are as follows:
Inventory carrying costs are $2 per recorder per month. The manager does not want any inventory carried over past the fifth month. The manager wants to know the monthly production that will minimize total production and inventory costs.
The manager of the Ewing and Barnes Department Store has four employees available to assign to three departments in the storelamps, sporting goods, and linens. The manager wants each of these departments to have at least one employee, but not more than two. Therefore, two departments will be assigned one employee, and one department will be assigned two. Each employee has different areas of expertise, which are reflected in the daily sales each employee is expected to generate in each department, as follows:
The manager wishes to know which employee(s) to assign to each department in order to maximize expected sales.
Tidewater City Bank has four branches with the following inputs and outputs:
The monthly output and input values for each bank are as follows:
Using data envelopment analysis (DEA), determine which banks, if any, are inefficient.
Carillon Health Systems owns three hospitals, and it wants to determine which, if any, of the hospitals are inefficient. The hospital inputs each month are (1) hospital beds (100s), (2) nonphysician labor (1,000 hrs.), and (3) dollar value of supplies ($1000s). The hospital outputs are patient days (100s) for three age groups(1) under 15, (2) 15 to 65, and (3) over 65. The output and input values for each hospital are as follows:
Using DEA, determine which hospitals are inefficient.
Managers at the Transcontinent Shipping and Supply Company want to know the maximum tonnage of goods they can transport from city A to city F. The firm can contract for railroad cars on different rail routes linking these cities via several intermediate stations , shown in the following diagram; all railroad cars are of equal capacity:
The firm can transport a maximum amount of goods from point to point, based on the maximum number of railroad cars shown on each route segment. Managers want to determine the maximum tonnage that can be shipped from city A to city F.
The law firm of Smith, Smith, Smith, and Jones is recruiting at law schools for new lawyers for the coming year. The firm has developed the following estimate of the number of hours of casework it will need its new lawyers to handle each month for the following year:
Each new lawyer the firm hires is expected to handle 150 hours per month of casework and to work all year. All casework must be completed by the end of the year. The firm wants to know how many new lawyers it should hire for the year.
In Problem 51 the optimal solution results in a fractional (i.e., non-integer) number of lawyers being hired. Explain how you would go about logically determining a new solution with a whole (integer) number of lawyers being hired and discuss the difference in results between this new solution and the optimal non-integer solution obtained in Problem 51.
The Goliath Tool and Machine Shop produces a single product that consists of three subcomponents that are assembled to form the product. The three components are manufactured in an operation that involves two lathes and three presses. The production time (in minutes per unit) for each machine for the three components is as follows:
The shop splits the lathe workload evenly between the two lathes, and it splits the press workload evenly among the three presses. In addition, the firm wishes to produce quantities of components that will balance the daily loading among lathes and presses so that, on the average, no machine is operated more than 1 hour per day longer than any other machine. Each machine operates 8 hours per day.
The firm also wishes to produce a quantity of components that will result in completely assembled products, without any partial assemblies (i.e., in-process inventories). The objective of the firm is to maximize the number of units of assembled product per day.
A ship has two cargo holds, one fore and one aft. The fore cargo hold has a weight capacity of 70,000 pounds and a volume capacity of 30,000 cubic feet. The aft hold has a weight capacity of 90,000 pounds and a volume capacity of 40,000 cubic feet. The shipowner has contracted to carry loads of packaged beef and grain. The total weight of the available beef is 85,000 pounds; the total weight of the available grain is 100,000 pounds. The volume per mass of the beef is 0.2 cubic foot per pound, and the volume per mass of the grain is 0.4 cubic foot per pound. The profit for shipping beef is $0.35 per pound, and the profit for shipping grain is $0.12 per pound. The shipowner is free to accept all or part of the available cargo; he wants to know how much meat and grain to accept to maximize profit.
Eyewitness News is shown on channel 5 Monday through Friday evenings from 5:00 P.M. to 6:00 P.M. During the hour-long broadcast, 18 minutes are allocated to commercials. The remaining 42 minutes of airtime are allocated to single or multiple time segments for local news and features, national news, sports, and weather. The station has learned through several viewer surveys that viewers do not consistently watch the entire news program; they focus on some segments more closely than others. For example, they tend to pay more attention to the local weather than the national news (because they know they will watch the network news following the local broadcast). As such, the advertising revenues generated for commercials shown during the different broadcast segments are $850 per minute for local news and feature segments, $600 per minute for national news, $750 per minute for sports, and $1,000 per minute for the weather. The production cost for local news is $400 per minute, the cost for national news is $100 per minute, the cost for sports is $175 per minute, and for weather it's $90 per minute. The station budgets $9,000 per show for production costs. The station's policy is that the broadcast time devoted to local news and features must be at least 10 minutes but not more than 25 minutes, whereas national news, sports, and weather must each have segments of at least 5 minutes but not more than 10 minutes. Commercial time must be limited to no more than 6 minutes for each of the four broadcast segment types. The station manager wants to know how many minutes of commercial time and broadcast time to allocate to local news, national news, sports, and weather to maximize advertising revenues.
The Douglas family raises cattle on their farm in Virginia. They also have a large garden in which they grow ingredients for making two types of relishchow-chow and tomato. These they sell in 16-ounce jars at local stores and craft fairs in the fall. The profit for a jar of chow-chow is $2.25, and the profit for a jar of tomato relish is $1.95. The main ingredients in each relish are cabbage, tomatoes, and onions. A jar of chow-chow must contain at least 60% cabbage, 5% onions, and 10% tomatoes, and a jar of tomato relish must contain at least 50% tomatoes, 5% onions, and 10% cabbage. Both relishes contain no more than 10% onions. The family has enough time to make no more than 700 jars of relish. In checking sales records for the past 5 years, they know that they will sell at least 30% more chow-chow than tomato relish. They will have 300 pounds of cabbage, 350 pounds of tomatoes, and 30 pounds of onions available. The Douglas family wants to know how many jars of relish to produce to maximize profit.
The White Horse Apple Products Company purchases apples from local growers and makes applesauce and apple juice. It costs $0.60 to produce a jar of applesauce and $0.85 to produce a bottle of apple juice . The company has a policy that at least 30% but not more than 60% of its output must be applesauce.
The company wants to meet but not exceed the demand for each product. The marketing manager estimates that the demand for applesauce is a maximum of 5,000 jars, plus an additional 3 jars for each $1 spent on advertising. The maximum demand for apple juice is estimated to be 4,000 bottles, plus an additional 5 bottles for every $1 spent to promote apple juice. The company has $16,000 to spend on producing and advertising applesauce and apple juice. Applesauce sells for $1.45 per jar; apple juice sells for $1.75 per bottle. The company wants to know how many units of each to produce and how much advertising to spend on each to maximize profit.
Mazy's Department Store has decided to stay open on a 24-hour basis. The store manager has divided the 24-hour day into six 4-hour periods and determined the following minimum personnel requirements for each period:
Personnel must report for work at the beginning of one of these times and work 8 consecutive hours. The store manager wants to know the minimum number of employees to assign for each 4-hour segment to minimize the total number of employees.
Venture Systems is a consulting firm that develops e-commerce systems and Web sites for its clients . It has six available consultants and eight client projects under contract. The consultants have different technical abilities and experience, and as a result, the company charges different hourly rates for its services. Also, the consultants' skills are more suited for some projects than others, and clients sometimes prefer some consultants over others. The suitability of a consultant for a project is rated according to a 5-point scale, in which 1 is the worst and 5 is the best. The following table shows the rating for each consultant for each project, as well as the hours available for each consultant and the contracted hours and maximum budget for each project:
The company wants to know how many hours to assign each consultant to each project in order to best utilize the consultants' skills while meeting the clients' needs.
Great Northwoods Outfitters is a retail phone-catalog company that specializes in outdoor clothing and equipment. A phone station at the company will be staffed with either full-time operators or temporary operators 8 hours per day. Full-time operators, because of their experience and training, process more orders and make fewer mistakes than temporary operators. However, temporary operators are cheaper because they receive a lower wage rate and they are not paid benefits. A full-time operator can process about 360 orders per week, whereas a temporary operator can process about 270 orders per week. A full-time operator averages 1.1 defective orders per week, and a part-time operator incurs about 2.7 defective orders per week. The company wants to limit defective orders to 200 per week. The cost of staffing a station with full-time operators is $610 per week, and the cost of a station with part-time operators is $450 per week. Using historical data and forecasting techniques, the company has developed estimates of phone orders for an 8-week period, as follows:
The company does not want to hire or dismiss full-time employees after the first week (i.e., the company wants a constant group of full-time operators over the 8-week period). The company wants to determine how many full-time operators it needs and how many temporary operators to hire each week to meet weekly demand while minimizing labor costs.
In Problem 60 Great Northwoods Outfitters is going to alter its staffing policy. Instead of hiring a constant group of full-time operators for the entire 8-week planning period, it has decided to hire and add full-time operators as the 8-week period progresses, although once it hires full-time operators, it will not dismiss them. Reformulate the linear programming model to reflect this altered policy and solve to determine the cost savings (if any).
Blue Ridge Power and Light Company generates electrical power at four coal- fired power plants along the eastern seaboard in Virginia, North Carolina, Maryland, and Delaware. The company purchases coal from six producers in southwestern Virginia, West Virginia, and Kentucky. Blue Ridge has fixed contracts for coal delivery from the following three coal producers :
The power-producing capabilities of the coal produced by these suppliers differs according to the quality of the coal. For example, coal produced by ANCO provides 26.2 million BTUs per ton, while coal produced at Boone Creek provides 27.1 million BTUs per ton. Blue Ridge also purchases coal from three backup auxiliary suppliers, as needed (i.e., it does not have fixed contracts with these producers). In general, the coal from these backup suppliers is more costly and lower grade:
The demand for electricity at Blue Ridge's four power plants is as follows (note that it requires approximately 10 million BTUs to generate 1 megawatt hour):
For example, the Afton plant must produce at least 4,600,000 million BTUs next year, which translates to approximately 460,000 megawatt hours.
Coal is primarily transported from the producers to the power plants by rail, and the cost of processing coal at each plant is different. Following are the combined transportation and processing costs for coal from each supplier to each plant:
Formulate and solve a linear programming model to determine how much coal should be purchased and shipped from each supplier to each power plant in order to minimize cost.
Valley United Soccer Club has 16 boys' and girls ' travel soccer teams. The club has access to three town fields, which its teams practice on in the fall during the season. Field 1 is large enough to accommodate two teams at one time, and field 3 can accommodate three teams, while field 2 only has enough room for one team. The teams practice twice per week, either on Monday and Wednesday from 3 P.M. to 5 P.M. or 5 P.M. to 7 P.M. , or on Tuesday and Thursday from 3 P.M. to 5 P.M. or 5 P.M. to 7 P.M. Field 3 is in the worst condition of all the fields, so teams generally prefer the other fields; teams also do not like to practice at field 3 because it can get crowded with three teams. In general, the younger teams like to practice right after school, while the older teams like to practice later in the day. In addition, some teams must practice later because their coaches are available only after work. Some teams also prefer specific fields because they're closer to their players' homes . Each team has been asked by the club field coordinator to select three practice locations and times, in priority order, and they have responded as follows:
For example, the under-11 boys' age group team has selected field 2 from 3 P.M. to 5 P.M. on Monday and Wednesday as its top priority, field 1 from 3 P.M. to 5 P.M. on Monday and Wednesday as its second priority, and so on.
Formulate and solve a linear programming model to optimally assign the teams to fields and times, according to their priorities. Are any of the teams not assigned to one of their top three selections? If not, how might you modify or use the model to assign these teams to the best possible time and location? How could you make sure that the model does not assign teams to unacceptable locations and timesfor example, a team whose coach can only be at practice at 5 P.M. ?
The city of Salem has four police stations, with the following inputs and outputs:
The monthly output and input data for each station are
Help the city council determine which of the police stations are relatively inefficient.
USAir South Airlines operates a hub at the Pittsburgh International Airport. During the summer, the airline schedules 7 flights daily from Pittsburgh to Orlando and 10 flights daily from Orlando to Pittsburgh, according to the following schedule:
The flight crews live in Pittsburgh or Orlando, and each day a new crew must fly one flight from Pittsburgh to Orlando and one flight from Orlando to Pittsburgh. A crew must return to its home city at the end of each day. For example, if a crew originates in Orlando and flies a flight to Pittsburgh, it must then be scheduled for a return flight from Pittsburgh back to Orlando. A crew must have at least 1 hour between flights at the city where it arrives. Some scheduling combinations are not possible; for example, a crew on flight 1 from Pittsburgh cannot return on flights A, B, or C from Orlando. It is also possible for a flight to ferry one additional crew to a city in order to fly a return flight, if there are not enough crews in that city.
The airline wants to schedule its crews in order to minimize the total amount of crew ground time (i.e., the time the crew is on the ground between flights). Excessive ground time for a crew lengthens its workday , is bad for crew morale , and is expensive for the airline. Formulate a linear programming model to determine a flight schedule for the airline and solve by using the computer. How many crews need to be based in each city? How much ground time will each crew experience?
The National Cereal Company produces a Light-Snak cereal package with a selection of small pouches of four different cerealsCrunchies, Toasties, Snakmix, and Granolies. Each cereal is produced at a different production facility and then shipped to three packaging facilities, where the four different cereal pouches are combined into a single box. The boxes are then sent to one of three distribution centers, where they are combined to fill customer orders and shipped. The following diagram shows the weekly flow of the product through the production, packaging, and distribution facilities (referred to as a "supply chain"):
Ingredients capacities (per 1,000 pouches) per week are shown along branches 12, 13, 14, and 15. For example, ingredients for 60,000 pouches are available at the production facility, as shown on branch 12. The weekly production capacity at each plant (in 1,000s of pouches) is shown at nodes 2, 3, 4, and 5. The packaging facilities at nodes 6, 7, and 8 and the distribution centers at nodes 9, 10, and 11 have capacities for boxes (1,000s) as shown.
The various production, packaging, and distribution costs per unit at each facility are shown in the following table:
Weekly demand for the Light-Snak product is 37,000 boxes.
Formulate and solve a linear programming model that indicates how much product must be produced at each facility to meet weekly demand at the minimum cost.
Valley Fruit Products Company has contracted with apple growers in Ohio, Pennsylvania, and New York to purchase apples that the company then ships to its plants in Indiana and Georgia, where they are processed into apple juice. Each bushel of apples produces 2 gallons of apple juice. The juice is canned and bottled at the plants and shipped by rail and truck to warehouses/distribution centers in Virginia, Kentucky, and Louisiana. The shipping costs per bushel from the farms to the plants and the shipping costs per gallon from the plants to the distribution centers are summarized in the following tables:
Formulate and solve a linear programming model to determine the optimal shipments from the farms to the plants and from the plants to the distribution centers in order to minimize total shipping costs.