Linear Programming (24 problems)

Woodco manufactures tables and chairs. Each table and chair must be made entirely out of oak or entirely out of pine. A total of 150 board feet of oak and 210 board feet of pine are available. A table requires either 17 board feet or oak or 30 board feet of pine, and a chair requires either 5 board feet of oak or 13 board feet of pine. Each table can be sold for $40, and each chair for $15. Determine how Woodco can maximize its revenue using Excel's solver.

The seasonal yield of olives in a Piraeus, Greece, vineyard is greatly influenced by a process of branch pruning. If olive trees are pruned every two weeks, output is increased. The pruning process, however, requires considerably more labor than permitting the olives to grow on their own and results in a smaller size olive. It also, though, permits olive trees to be spaced closer together. The yield of 1 barrel of olives by pruning requires 5 hours of labor and I acre of land. The production of a barrel of olives by the normal process requires only 2 labor hours but takes 2 acres of land. An olive grower has 250 hours of labor available and a total of 150 acres for grow­ing. Because of the olive size difference, a barrel of olives produced on pruned trees sells for $20, whereas a barrel of regular olives has a market price of $30. The grower has determined that because of uncertain demand, no more than 40 barrels of pruned olives should be produced. Use graphical LP to find

(a) The maximum possible profit.

(b) The best combination of barrels of pruned and regular olives.

(c) The number of acres that the olive grower should devote to each growing process.

The Skimmer boat company manufactures three kinds of molded fiberglass recreational boats – bass fishing, skiing, and speedboat. The profit for the bass boat is $20,500, the profit for the ski boat is $12,000, and the profit for the speedboat is $22,300. The company believes it will sell more bass boats than the other two boats combined but no more than twice as many. The ski boat is its standard production model and bass boats and speedboats are modifications. The company has a production capacity to manufacture 210 standard (ski-type) boats; however, a bass boat requires 1.3 times the standard production capacity, and a speedboat requires 1.5 times the normal production capacity. In addition, only 160 of the high-powered engines that are installed in the bass boats and 2 of those installed in the speedboats are available.

The company wants to know how many boats of each type to produce to maximize profit. Formulate and solve an integer programming model for this problem.

Serendipity: The three princes of Serendipity went on a little trip. They could not carry too much weight; More than 300 pounds made them hesitate. They planned to the ounce. When they returned to Ceylon, they discovered that their supplies were just about gone. When, what to their joy, Prince William found a pile of coconuts on the ground. "Each will bring 60 rupees," said Prince Richard with a grin, as he almost tripped over a lion skin. "Look out!" cried Prince Robert with glee, as he spied some more lion skins under a tree. "These are worth even more-300 rupees each if we can just carry them all down to the beach." Each skin weighed fifteen pounds and each coconut, five, but they carried them all and made it alive. The boat back to the island was very small 15 cubic feet baggage capacity-that was all. Each lion skin took up one cubic foot while eight coconuts the same space took with everything stowed they headed to sea and on the way calculated what their new wealth might be. "Eureka!" cried Prince Robert, "Our worth is so great that there's no other way we could return in this state. Any other skins or nut that we might have brought would now have us poorer. And now I know what. I'll write my friend Horace in England, for surely only he can appreciate our serendipity."

Formulate and solve Serendipity by graphical LP in order to calculate "what their new wealth might be."

Steelco manufactures two types of steel at three different steel mills. During a given month, each steel mill has 200 hours of blast furnace time available. Because of differences in the furnaces at each mill, the time and cost to produce a ton of steel differ for each mill, as listed in the file P04_62.xls. Each month Steelco must manufacture at least 500 tons of steel 1 and 600 tons of steel 2. Determine how Steelco can minimize the cost of manufacturing the desired steel using Excel's solver.

Each four hour from 10 A.M. to 7 P.M., Bank One receives checks and must process them. Its goal is to process all checks the same day they are received. The bank has 13 check processing machines, each of which can process up to 500 checks per hour. It takes one worker to operate each machine. Bank One hires both full-time and part-time workers. Full-time workers work 10 A.M. to 6 P.M., 11 A.M. to 7 P.M., or noon to 8P.M., and are paid $160 per day. Part-time workers work either 2 P.M. to 7 P.M., or 3 P.M. to 8 P.M., and are paid $75 per day. The number of checks received each hour is listed in the file P15_94.xls. In the interest of maintaining continuity, Bank One believes that it must have at least three full-time workers under contract. Develop a work schedule that processes all checks by 8 P.M. and minimizes daily labor costs.

A farmer in Iowa owns 45 acres of land. He is going to plant each acre with wheat or corn. Each acre planted with wheat yields $200 profit, requires 3 workers, and requires 2 tons of fertilizer; each with corn yields $300 profit, requires 2 workers, and requires 4 tons of fertilizer. One hundred workers and 120 tons of fertilizer are available.

Use Excel's Solver to help the farmer maximize the profit from his land.

A candidate for mayor in a small town has allocated $40,000 for last-minute advertising in the days pre­ceding the election. Two types of ads will be used: radio and television. Each radio ad costs $200 and reaches an estimated 3,000 people. Each television ad costs $500 and reaches an estimated 7,000 people. In planning the advertising campaign, the campaign manager would like to reach as many people as possi­ble, but she has stipulated that at least 10 ads of each type must be used. Also, the number of radio ads must be at least as great as the number of television ads. How many ads of each type should be used? How many people will this reach?

MSA Computer Corporation manufactures two mod­els of minicomputers, the Alpha 4 and the beta 5. The firm employs five technicians, working 160 hours each per month, on its assembly line. Management insists that full employment (i.e., all 160 hours of time) be maintained for each worker during next month's operations. It requires 20 labor hours to assemble each Alpha 4 computer and 25 labor hours to assemble each Beta 5 model. MSA wants to see at least 10 Alpha 4s and at least 15 Beta 5s produced during the produc­tion period. Alpha 4s generate $1,200 profit per unit, and Beta 5s yield $1,800 each. Determine the most profitable number of each model of minicomputer to produce during the coming month.

Harry and Melissa Jacobson produce handcrafted furniture in a workshop on their farm. They have obtained a load of 600 board feet of birch from a neighbor and are planning to produce round kitchen tables and ladder-back chairs during the next 3 months. Each table will require 30 hours of labor, each chair will require 18 hours, and between them they have a total of 480 hours of labor available. A table requires 40 board feet of wood to make, and a chair requires 15 board feet. A table earns the couple $575 in profit, and a chair earns $120 in profit. Most people who buy a table also want four chairs to go with it, so for every table that is produced, at least four chairs must also be made, although additional chairs can also be sold separately.

Formulate and solve an integer programming model to determine the number of tables and chairs the Jacobson’s should make to maximize profit.

Tots Toys makes a plastic tricycle that is composed of three major components: a handlebar-front wheel-pedal assembly, a seat and frame unit, and rear wheels. The company has orders for 12,000 of these trikes.

As indicated in the table below, the company obviously does not have the resources available to manufacture everything needed for the completion of 12000 tricycles, so it has arranged to purchase additional components, as necessary. Develop a linear programming model to tell the company how many of each component should be manufactured and how many should be purchased in order to provide 12000 fully completed tricycles at the minimum cost.

An ad campaign for a new snack chip will be conducted in a limited geographical area and can use TV time, radio time, and newspaper ads. Information about each medium is shown below.

If the number of TV ads cannot exceed the number of radio ads by more than 4, and if the advertising budget is $10000, develop the model that will maximize the number reached and achieve an exposure quality of at least 1000.

A clothing company produces shirts and pants. Each shirt requires 2 square yards of cloth, and each pair of pants requires 3 square yards of cloth. During the next two months the following demands for shirts and pants must be met (on time): month 1, 1000 shirts and 1500 pairs of pants; month 2, 1200 shirts and 1400 pairs of pants. During each month the following resources are available: month 1, 9000 square yards of cloth; month 2, 6000 square yards of cloth. (Cloth that is available during month 1 and is not used can be used during month 2). During each month it costs $4 to make an article of clothing with regular-time labor and $8 with overtime labor. During each month a total of at most 2500 articles of clothing can be produced with regular-time labor, and an unlimited number of articles of clothing can be produced with overtime labor. At the end of each month, a holding cost of $3 per article of clothing is assessed. Determine how to meet demands for the next 2 months (on time) at minimum cost. Assume that at the beginning of month 1, 100 shirts and 200 pairs of pans are available.

Each year, a shoe company faces demands (which must be met on time) for pairs of shoes as shown below:

Quarter1 Demand: 6000

Quarter2 Demand: 3000

Quarter3 Demand: 8000

Quarter4 Demand: 1000

Workers work three consecutive quarters and then receive one quarter off. For example, a worker might work during quarters 3 and 4 of one year and quarter 1 of the next year. During a quarter in which a worker works, he or she can produce up to 500 pairs of shoes. Each worker is paid $5000 per quarter. At the end of each quarter, a holding cost of $10 per pair of shoes is assessed. Determine how to minimize the cost per year (labor plus holding) of meeting the demands for shoes. To simplify matters, assume that at the end of each year, the ending inventory is zero. (Hint: you may assume that a given worker will get the same quarter off during each year.)

The Manning Metal Milling Company Problem. The J.J. Manning Metal Milling Company makes three products, flywheels, u-joints and axles. The manager is faced with the problem of deciding the best output schedule for the upcoming month. Management and staff have arrived at a table of data for the upcoming month:

It has been determined that there at most 1,620 hours of production time available next month, at a unit cost of $7.00 per hour. There is no limit on the supply of metal for the production runs, however each unit of metal will cost $2.00.

The company is experiencing a severe cash flow problem. Consequently all sales are made for cash, and all fixed costs and variable must be paid for in cash during the month of production. Fixed costs for the month will be $2,200, and there will be a payment on a loan due for $800. The cash balance at the beginning of the month is $28,125, and Manning Metal Milling would want to leave no less that $5,000 in the till at the end of the month.

Develop management's production program by linear programming so as to maximize profits.

(Solution: Interesting problem. Produce no flywheels, 550 u-joints and only 175 axles. All the labor will be utilized. The profit will be $9,742. There is no problem with the cash flow. Operations will produce a positive cash balance of +$37,067.00)

A farmer has a 2,500 acre farm. The farmer has potential cash crops of peanuts, alfalfa, and beef, and the beef are fed 100% alfalfa.

The farmer irrigates his normally parch-dry land from a series of deep drill wells. The wells are sufficient to provide him with 5,500 acre-feet of water per year. An acre-foot or water is sufficient water to cover one acre of land with water one foot deep over a year's time period.

With this data, the farmer is working on this farm production schedule for the upcoming year.

He estimates that beef will sell for $650 per ton, and a mature beef cow should produce a ton of beef. Peanuts will sell for $3.25 per bushel. His best guess is that he will be able to sell alfalfa for $64 per ton if he has excess alfalfa over what his cattle stocks require, but if he needs more alfalfa to feed his cattle than he can raise, then he will have to pay $66 per ton to get the alfalfa brought in.

Based on his past yields, his fields should yield 50 bushels of peanuts and 3 tons of alfalfa per acre.

His other costs and requirements are as follows:

What should he do to achieve a maximum return?

The Farmer Barley Problem. Farmer Barley operates a large, 2,500 acre, farm in southeast Virginia. Farmer Barley's potential cash crops are peanuts, alfalfa, and beef, and the beef are fed 100% alfalfa.

Farmer Barley irrigates his normally parch-dry land from a series of deep drill wells. The wells are sufficient to provide him with 5,500 acre-feet of water per year. An acre-foot or water is sufficient water to cover one acre of land with water one foot deep over a year's time period.

With this data, Farmer Barley is working on this farm production schedule for the upcoming year.

He estimates that beef will sell for $650 per ton, and a mature beef cow should produce a ton of beef. Peanuts will sell for $3.25 per bushel. His best guess is that he will be able to sell alfalfa for $64 per ton if he has excess alfalfa over what his cattle stocks require, but if he needs more alfalfa to feed his cattle than he can raise, then he will have to pay $66 per ton to get the alfalfa brought in.

Based on his past yields, Farmer Barley's fields should yield 50 bushels of peanuts and 3 tons of alfalfa per acre.

His other costs and requirements are as follows:

What should he do to achieve a maximum return?

THE SATURDAY SHIFT PROBLEM:

Tracey Ketchon, the manager of the Outrageous Rags Boutique is about to roster the Saturday three shift at her mall store. The twelve hour day is broken into three, four-hour shifts: 10AM to 2 PM, 2PM to 6PM, and 6PM to 10PM. Saturdays are her busy day; her requirements are as follows:

She has eight part-timers that could be selected. They are paid varying amounts depending on whether they are cashier trained and depending on their past sales. She would like to assign the clerks to the shift in a way that would maximize sales potential -- but not bust her payroll budget, which is $560. The part-timers, their sales volumes per four hour period, and whether or not they are cashier trained is as follows:

If a person is assigned to work on Saturday, they would need to be assigned for a full eight hours, with no split shifts, nor an assignment longer that eight hours. In addition, they will need at least one cashier-trained person on each shift.

There are several personnel problems. Hank and Denise are roommates and share Denise's car, and because of insurance problems, Hank can't drive Denise's car. Therefore, Hank can only work when Denise works. In addition, Charlotte hates Felicia, therefore you can't put them on the same shift. Finally, Tracey herself is off to the beach for the weekend and will not be working this Saturday.

Set up the LP algorithm to optimize the situation on the potential of maximizing sales, get the shift manned, and yet not break any of the constraints … and solve it via a computer output … show both the LP stubby pencil set up … the computer output … and then interpret the output back into the problem.

a. You are the manufacturer of two sizes of frammits, large and small. You have a machine that can spray paint frammits. If it were spraying just the large frammits, it could paint 500 per shift. However, if it were spraying just the small frammits, this number would jump to 750 -- but it could do a combination of both in the same ratios. Set up the constraint that will hold the ratio, not more than, nor less than.

b. A seafood processor can sell crabs as either plain dressed crabs for 70¢ each or as crab salad for $6.20 per pound. The crabs come from the crab watermen at 30¢ each. Each pound of crab salad requires 6 crabs. Set up the mini-objective function and the constraint(s) that will handle the crab and crab salad mix and yet achieve maximum profits.

The Whitney Agency Problem. The Whitney Agency has just landed an important client that manufactures electric shavers. The shaver company has allocated an advertising budget of $38,000, and Whitney has decided to focus the budget on magazine advertising.

Preliminary market research studies made my the agency have shown that the desired market for electric shavers is composed of men who are 20 to 45 years of age, who have incomes of $30,000 and up, and who have two or more years of college education. The researchers have decided to weigh these factors as follows:

In researching available magazine reader profiles, three magazines in particular were noted to have the highest percentages of readers in each of the three categories. The magazines were: Esquip, CQ, and Lite Quant.

Because of office politics, media balance and competitor shift, the agency has determined that the maximum number of advertisements that should be placed in each magazine is 36, 40 and 45 respectively. In addition, it has been decided that at least nine (9) advertisements should be placed in Esquip, and at least five (5) should be placed in Lite Quant.

Develop the best use of the advertising budget among the three magazines that will maximize exposure of the product to the most desirable market segments.