Chapter 4

Each serving of Gerber Mixed Cereal for Baby contains 60 calories and 11 grams of carbohydrates, and each serving of Gerber Mango Tropical Fruit Dessert contains 80 calories and 21 grams of carbohydrates. \({ }^{3}\) You want to provide your child with at least 140 calories and at least 32 grams of carbohydrates. Draw the feasible region that shows the number of servings of cereal and number of servings of dessert that you can give your child. Find the corner points of the region.

Investments Your friend's portfolio manager has suggested two energy stocks: Exxon Mobil (XOM) and British Petroleum (BP). XOM shares cost \(\$ 80\), yield \(2 \%\) in dividends, and have a risk index of \(2.5\). BP shares cost \(\$ 50\), yield \(7 \%\) in dividends, and have a risk index of \(4.5 .{ }^{19}\) Your friend has up to \(\$ 40,000\) to invest, and would like to earn at least \(\$ 1,400\) in dividends. How many shares (to the nearest tenth of a unit) of each stock should she purchase to meet your requirements and minimize the total risk index for your portfolio? What is the minimum total risk index?

Each serving of Gerber Mixed Cereal for Baby contains 60 calories, 11 grams of carbohydrates, and no vitamin C. Each serving of Gerber Apple Banana Juice contains 60 calories, 15 grams of carbohydrates, and 120 percent of the U.S. Recommended Daily Allowance (RDA) of vitamin \(\mathrm{C}\) for infants. \({ }^{4}\) You want to provide your child with at least 120 calories, at least 26 grams of carbohydrates, and at least 50 percent of the U.S. RDA of vitamin \(\mathrm{C}\) for infants. Draw the feasible region that shows the number of servings of cereal and number of servings of juice that you can give your child. Find the corner points of the region.

\mathrm{\\{} G a m e ~ T h e o r y ~ - ~ P o l i t i c s ~ I n c u m b e n t ~ T a x ~ \(\mathrm{N}\). Spend and chal- lenger Trick L. Down are running for county executive, and polls show them to be in a dead heat. The election hinges on three cities: Littleville, Metropolis, and Urbantown. The candidates have decided to spend the last weeks before the election campaigning in those three cities; each day each candidate will decide in which city to spend the day. Pollsters have determined the following payoft matrix, where the payoff represents the number of votes gained or lost for each one-day campaign trip. T. N. Spend \begin{tabular}{|l|c|c|c|} \hline & Littleville & Metropolis & Urbantown \\ \hline Littleville & \(-200\) & \(-300\) & 300 \\ \hline Metropolis & \(-500\) & 500 & \(-100\) \\ \hline Urbantown & \(-500\) & 0 & 0 \\ \hline \end{tabular} T. L. Down What percentage of time should each candidate spend in each city in order to maximize votes gained? If both candidates use their optimal strategies, what is the expected vote?

\(\nabla\) \mathrm{\\{} T r a n s p o r t a t i o n ~ S c h e d u l i n g ~ W e ~ r e t u r n ~ t o ~ y o u r ~ e x p l o i t s ~ c o - ~ ordinating distribution for the Tubular Ride Boogie Board Company. \({ }^{36}\) You will recall that the company has manufacturing plants in Tucson, Arizona and Toronto, Ontario, and you have been given the job of coordinating distribution of their latest model, the Gladiator, to their outlets in Honolulu and Venice Beach. The Tucson plant can manufacture up to 620 boards per week, while the Toronto plant, beset by labor disputes, can produce no more than 410 Gladiator boards per week. The outlet in Honolulu orders 500 Gladiator boards per week, while Venice Beach orders 530 boards per week. Transportation costs are as follows: Tucson to Honolulu: \(\$ 10 /\) board; Tucson to Venice Beach: \(\$ 5 /\) board; Toronto to Honolulu: \(\$ 20 /\) board; Toronto to Venice Beach: \(\$ 10 /\) board. Your manager has said that you are to be sure to fill all orders and ship the boogie boards at a minimum total transportation cost. How will you do it?

Your company’s new portable phone/music player/PDA/bottle washer, the RunMan, will compete against the established market leader, the iNod, in a saturated market. (Thus, for each device you sell, one fewer iNod is sold.) You are planning to launch the RunMan with a traveling road show, concentrating on two cities, New York and Boston. The makers of the iNod will do the same to try to maintain their sales. If, on a given day, you both go to New York, you will lose 1,000 units in sales to the iNod. If you both go to Boston, you will lose 750 units in sales. On the other hand, if you go to New York and your competitor to Boston, you will gain 1,500 units in sales from them. If you

Finance Senator Porkbarrel habitually overdraws his three bank accounts, at the Congressional Integrity Bank, Citizens' Trust, and Checks R Us. There are no penalties because the overdrafts are subsidized by the taxpayer. The Senate Ethics Committee tends to let slide irregular banking activities as long as they are not flagrant. At the moment (due to Congress" preoccupation with a Supreme Court nominee), a total overdraft of up to \(\$ 10,000\) will be overlooked. Porkbarrel's conscience makes him hesitate to overdraw accounts at banks whose names include expressions like "integrity" and "citizens' trust." The effect is that his overdrafts at the first two banks combined amount to no more than one-quarter of the total. On the other hand, the financial officers at Integrity Bank, aware that Senator Porkbarrel is a member of the Senate Banking Committee, "suggest" that he overdraw at least \(\$ 2,500\) from their bank. Find the amount he should overdraw from each bank in order to avoid investigation by the Ethics Committee and overdraw his account at Integrity by as much as his sense of guilt will allow.

Transportation Scheduling (This exercise is almost identical to Exercise 26 in Section \(2.3\) but is more realistic; one cannot always expect to fill all orders exactly, and keep all plants operating at 100 percent capacity.) The Tubular Ride Boogie Board Company has manufacturing plants in Tucson, Arizona, and Toronto, Ontario. You have been given the job of coordinating distribution of the latest model, the Gladiator, to their outlets in Honolulu and Venice Beach. The Tucson plant, when operating at full capacity, can manufacture 620 Gladiator boards per week, while the Toronto plant, beset by labor disputes, can produce only 410 boards per week. The outlet in Honolulu orders 500 Gladiator boards per week, while Venice Beach orders 530 boards per week. Transportation costs are as follows: Tucson to Honolulu: \(\$ 10\) per board; Tucson to Venice Beach: \(\$ 5\) per board; Toronto to Honolulu: \(\$ 20\) per board; Toronto to Venice Beach: \(\$ 10\) per board. Your manager has informed you that the company's total transportation budget is \(\$ 6,550\). You realize that it may not be possible to fill all the orders, but you would like the total number of boogie boards shipped to be as large as possible. Given this, how many Gladiator boards should you order shipped from each manufacturing plant to each distribution outlet?

Your portfolio manager has suggested two high-yielding stocks: Consolidated Edison (ED) and General Electric (GE). ED shares cost \(\$ 40\) and yield \(6 \%\) in dividends. GE shares cost \(\$ 16\) and yield \(7.5 \%\) in dividends. \({ }^{7}\) You have up to \(\$ 10,000\) to invest, and would like to earn at least \(\$ 600\) in dividends. Draw the feasible region that shows how many shares in each company you can buy. Find the corner points of the region. (Round each coordinate to the nearest whole number.)

\(\nabla\) Scheduling Because Joe Slim's brother was recently elected to the State Senate, Joe's financial advisement concern, Inside Information Inc., has been doing a booming trade, even though the financial counseling he offers is quite worthless. (None of his seasoned clients pays the slightest attention to his advice.) Slim charges different hourly rates to different categories of individuals: \(\$ 5,000 /\) hour for private citizens, \(\$ 50,000 /\) hour for corporate executives, and \(\$ 10,000 /\) hour for presidents of universities. Due to his taste for leisure, he feels that he can spend no more than 40 hours/week in consultation. On the other hand, Slim feels that it would be best for his intellect were he to devote at least 10 hours of consultation each week to university presidents. However, Slim always feels somewhat uncomfortable dealing with academics, so he would prefer to spend no more than half his consultation time with university presidents. Furthermore, he likes to think of himself as representing the interests of the common citizen, so he wishes to offer at least 2 more hours of his time each week to private citizens than to corporate executives and university presidents combined. Given all these restrictions, how many hours each week should he spend with each type of client in order to maximize his income?

Your friend's portfolio manager has suggested two energy stocks: Exxon Mobil (XOM) and British Petroleum (BP). XOM shares cost \(\$ 80\) and yield \(2 \%\) in dividends. BP shares cost \(\$ 50\) and yield \(7 \%\) in dividends. \({ }^{8}\) Your friend has up to \(\$ 40,000\) to invest, and would like to earn at least \(\$ 1,400\) in dividends. Draw the feasible region that shows how many shares in each company she can buy. Find the corner points of the region. (Round each coordinate to the nearest whole number.)

Management \(^{20}\) You are the service manager for a supplier of closed- circuit television systems. Your company can provide up to 160 hours per week of technical service for your customers, although the demand for technical service far exceeds this amount. As a result, you have been asked to develop a model to allocate service technicians' time between new customers (those still covered by service contracts) and old customers (whose service contracts have expired). To ensure that new customers are satisfied with your company's service, the sales department has instituted a policy that at least 100 hours per week be allocated to servicing new customers. At the same time, your superiors have informed you that the company expects your department to generate at least \(\$ 1,200\) per week in revenues. Technical service time for new customers generates an average of \(\$ 10\) per hour (because much of the service is still under warranty) and for old customers generates \(\$ 30\) per hour. How many hours per week should you allocate to each type of customer to generate the most revenue?

\(\nabla\) Transportation Scheduling Your publishing company is about to start a promotional blitz for its new book, Physics for the Liberal Arts. You have 20 salespeople stationed in Chicago and 10 in Denver. You would like to fly at least 10 into Los Angeles and at least 15 into New York. A round-trip plane flight from Chicago to LA costs \(\$ 195 ;{ }^{.37}\) from Chicago to \(\mathrm{NY}\) costs \(\$ 182 ;\) from Denver to LA costs \(\$ 395\); and from Denver to NY costs \(\$ 166\). How many salespeople should you fly from each of Chicago and Denver to each of LA and NY to spend the least amount on plane flights?

Transportation Scheduling Your publishing company is about to start a promotional blitz for its new book, Physics for the Liberal Arts. You have 20 salespeople stationed in Chicago and 10 in Denver. You would like to fly at most 10 into Los Angeles and at most 15 into New York. A round-trip plane flight from Chicago to LA costs \(\$ 195 ;^{28}\) from Chicago to \(\mathrm{NY}\) costs \(\$ 182 ;\) from Denver to LA costs \(\$ 395 ;\) and from Denver to NY costs \(\$ 166\). You want to spend at most \(\$ 4,520\) on plane flights. How many salespeople should you fly from each of Chicago and Denver to each of \(\mathrm{LA}\) and \(\mathrm{NY}\) to have the most salespeople on the road?

You are the marketing director for a company that manufactures bodybuilding supplements and you are planning to run ads in Sports Illustrated and \(G Q\) Magazine. Based on readership data, you estimate that each one-page ad in Sports Illustrated will be read by 650,000 people in your target group, while each one-page ad in \(G Q\) will be read by \(150,000 .{ }^{9}\) You would like your ads to be read by at least three million people in the target group and, to ensure the broadest possible audience, you would like to place at least three fullpage ads in each magazine. Draw the feasible region that shows how many pages you can purchase in each magazine. Find the corner points of the region. (Round each coordinate to the nearest whole number.)

The Scottsville Textile Mill produces several different fabrics on eight dobby looms which operate 24 hours per day and are scheduled for 30 days in the coming month. The Scottsville Textile Mill will produce only Fabric 1 and Fabric 2 during the coming month. Each dobby loom can turn out \(4.63\) yards of either fabric per hour. Assume that there is a monthly demand of 16,000 yards of Fabric 1 and 12,000 yards of Fabric 2. Profits are calculated as 33 d per yard for each fabric produced on the dobby looms. a. Will it be possible to satisfy total demand? b. In the event that total demand is not satisfied, the Scottsville Textile Mill will need to purchase the fabrics from another mill to make up the shortfall. Its profits on resold fabrics ordered from another mill amount to \(20 \mathrm{~d}\) per yard for Fabric 1 and \(16 \mathrm{e}\) per yard for Fabric \(2 .\) How many yards of each fabric should it produce to maximize profits?

If a linear programming problem has a bounded, nonempty feasible region, then optimal solutions (A) must exist (B) may or may not exist (C) cannot exist

Give one possible advantage of using duality to solve a standard minimization problem.

Can the following linear programming problem be stated as a standard maximization problem? If so, do it; if not, explain why. \(\begin{array}{ll}\text { Maximize } & p=3 x-2 y \\ \text { subject to } & x-y+z \geq 0 \\ & x-y-z \leq 6 \\ & x \geq 0, y \geq 0, z \geq 0 .\end{array}\) 28 Prices from Travelocity, at www.travelocity.com, for the week of June 3,2002 , as of May 5,2002 .

Find a system of inequalities whose solution set is unbounded.

If a linear programming problem has an unbounded, nonempty feasible region, then optimal solutions (A) must exist (B) may or may not exist (C) cannot exist

To ensure that the dual of a minimization problem will result in a standard maximization problem, (A) the primal problem should satisfy the non-negative objective condition. (B) the primal problem should be a standard minimization problem. (C) the primal problem should not satisfy the non-negative objective condition.

Can the following linear programming problem be stated as a standard maximization problem? If so, do it; if not, explain why. \(\begin{array}{ll}\text { Maximize } & p=-3 x-2 y \\ \text { subject to } & x-y+z \geq 0 \\ & x-y-z \geq-6 \\ & x \geq 0, y \geq 0, z \geq 0 .\end{array}\)

Find a system of inequalities whose solution set is empty.

Give an example of a standard minimization problem whose dual is not a standard maximization problem. How would you go about solving your problem?

Explain the need for Phase I in a nonstandard LP problem.

Why is the simplex method useful? (After all, we do have the graphical method for solving LP problems.)

How would you use linear inequalities to describe the triangle with corner points \((0,0),(2,0)\), and \((0,1)\) ?

Describe at least one drawback to using the graphical method to solve a linear programming problem arising from a real-life situation.

Explain the need for Phase II in a nonstandard LP problem.

Explain the advantage of shading the region of points that do not satisfy the given inequalities. Illustrate with an example.

Solve the following nonstandard minimization problem using duality. Recall from a footnote in the text that to find the dual you must first rewrite all of the constraints using "\geq " The Miami Beach City Council has offered to subsidize hotel development in Miami Beach, and is hoping for at least two hotels with a total capacity of at least 1,400 . Suppose that you are a developer interested in taking advantage of this offer by building a small group of hotels in Miami Beach. You are thinking of three prototypes: a convention-style hotel with 500 rooms costing \(\$ 100\) million, a vacation- style hotel with 200 rooms costing \(\$ 20\) million, and a small motel with 50 rooms costing \(\$ 4\) million. The city council will approve your plans provided you build at least one convention-style hotel and no more than two small motels. How many of each type of hotel should you build to satisfy the city council's wishes and stipulations while minimizing your total cost?

Your friend Janet is telling everyone that if there are only two constraints in a linear programming problem, then, in any optimal basic solution, at most two unknowns (other than the objective) will be nonzero. Is she correct? Explain.

Describe at least one drawback to the method of finding the corner points of a feasible region by drawing its graph, when the feasible region arises from real-life constraints.

Create a linear programming problem in two variables that has more than one optimal solution.

Given a minimization problem, when would you solve it by applying the simplex method to its dual, and when would you apply the simplex method to the minimization problem itself?

Your other friend Jason is telling everyone that if there is only one constraint in a standard linear programming problem, then you will have to pivot at most once to obtain an optimal solution. Is he correct? Explain.

Create an interesting scenario leading to the following linear programming problem: Maximize \(\quad p=10 x+10 y\) \(\begin{aligned} \text { subject to } & 20 x+40 y \leq 1,000 \\ & 30 x+20 y \leq 1,200 \\ & x \geq 0, y \geq 0 \end{aligned}\)

What is a "basic solution"? How might one find a basic solution of a given system of linear equations?

There should be at least 3 more grams of ingredient \(\mathrm{A}\) than ingredient \(\mathrm{B}\). (A) \(3 x-y \leq 0\) (B) \(x-3 y \geq 0\) (C) \(x-y \geq 3\) (D) \(3 x-y \geq 0\)

In a typical simplex method tableau, there are more unknowns than equations, and we know from the chapter on systems of linear equations that this typically implies the existence of infinitely many solutions. How are the following types of solutions interpreted in the simplex method? a. Solutions in which all the variables are positive. b. Solutions in which some variables are negative. c. Solutions in which the inactive variables are zero.

Use an example to show why there may be no optimal solution to a linear programming problem if the feasible region is unbounded.

Can the value of the objective function decrease in passing from one tableau to the next? Explain.

There should be at least 3 parts (by weight) of ingredient \(\mathrm{A}\) to 2 parts of ingredient \(\mathrm{B}\). (A) \(3 x-2 y \geq 0\) (B) \(2 x-3 y \geq 0\) (C) \(3 x+2 y \geq 0\) (D) \(2 x+3 y \geq 0\)

Can the value of the objective function remain unchanged in passing from one tableau to the next? Explain.

There should be no more of ingredient \(\mathrm{A}\) (by weight) than ingredient \(\mathrm{B}\). (A) \(x-y=0\) (B) \(x-y \leq 0\) (C) \(x-y \geq 0\) (D) \(x+y \geq y\)

You are setting up an LP problem for Fly-by-Night Airlines with the unknowns \(x\) and \(y\), where \(x\) represents the number of first-class tickets it should issue for a specific flight and \(y\) represents the number of business-class tickets it should issue for that flight, and the problem is to maximize profit. You find that there are two different corner points that maximize the profit. How do you interpret this?

You are setting up a system of inequalities in the unknowns \(x\) and \(y\). The inequalities represent constraints faced by Fly-byNight Airlines, where \(x\) represents the number of first-class tickets it should issue for a specific flight and \(y\) represents the number of business-class tickets it should issue for that flight. You find that the feasible region is empty. How do you interpret this?

Consider the following example of a nonlinear programming problem: Maximize \(p=x y\) subject to \(x \geq 0, y \geq 0\), \(x+y \leq 2\). Show that \(p\) is zero on every corner point, but is greater than zero at many noncorner points.

Create an interesting scenario that leads to the following system of inequalities: $$ \begin{aligned} &20 x+40 y \leq 1,000 \\ &30 x+20 y \leq 1,200 \\ &x \geq 0, y \geq 0 \end{aligned} $$