Chapter 6

Construct the dual problem associated with the primal problem. Solve the primal problem. $$ \begin{array}{ll} \text { Minimize } & C=200 x+150 y+120 z \\ \text { subject to } & 20 x+10 y+z \geq 10 \\ & x+y+2 z \geq 20 \\ x & \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=4 x+6 y \\ \text { subject to } & 3 x+y \leq 24 \\ & 2 x+y \leq 18 \\ & x+3 y \leq 24 \\ & x \geq 0, y \geq 0 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{array}{rr} \text { Minimize } & C=3 x+4 y \\ \text { subject to } & x+y \geq 3 \\ & x+2 y \geq 4 \\ & x \geq 0, y \geq 0 \end{array} $$

A nutritionist at the Medical Center has been asked to prepare a special diet for certain patients. She has decided that the meals should contain a minimum of \(400 \mathrm{mg}\) of calcium, \(10 \mathrm{mg}\) of iron, and \(40 \mathrm{mg}\) of vitamin C. She has further decided that the meals are to be prepared from foods \(A\) and \(B\). Each ounce of food \(A\) contains \(30 \mathrm{mg}\) of calcium, \(1 \mathrm{mg}\) of iron, \(2 \mathrm{mg}\) of vitamin \(\mathrm{C}\), and \(2 \mathrm{mg}\) of cholesterol. Each ounce of food \(\mathrm{B}\) contains \(25 \mathrm{mg}\) of calcium, \(0.5 \mathrm{mg}\) of iron, \(5 \mathrm{mg}\) of vitamin \(\mathrm{C}\), and \(5 \mathrm{mg}\) of cholesterol. Find how many ounces of each type of food should be used in a meal so that the cholesterol content is minimized and the minimum requirements of calcium, iron, and vitamin \(\mathrm{C}\) are met.

Construct the dual problem associated with the primal problem. Solve the primal problem. $$ \begin{array}{ll} \text { Minimize } & C=40 x+30 y+11 z \\ \text { subject to } & 2 x+y+z \geq 8 \\ & x+y-z \geq 6 \\ x & \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the simplex method. $$ \begin{array}{rr} \text { Maximize } & P=15 x+12 y \\ \text { subject to } & x+y \leq 12 \\ & 3 x+y \leq 30 \\ & 10 x+7 y \leq 70 \\ x & \geq 0, y \geq 0 \end{array} $$

AntiFam, a hunger-relief organization, has earmarked between $$\$ 2$$ and $$\$ 2.5$$ million (inclusive) for aid to two African countries, country \(\mathrm{A}\) and country B. Country \(\mathrm{A}\) is to receive between $$\$ 1$$ million and $$\$ 1.5$$ million (inclusive), and country B is to receive at least $$\$ 0.75$$ million. It has been estimated that each dollar spent in country A will yield an effective retum of $$\$ .60$$, whereas a dollar spent in country B will yield an effective return of $$\$ .80 .$$ How should the aid be allocated if the money is to be utilized most effectively according to these criteria? Hint: If \(x\) and \(y\) denote the amount of money to be given to country A and country B, respectively, then the objective function to be maximized is \(P=0.6 x+0.8 y\).

Construct the dual problem associated with the primal problem. Solve the primal problem. $$ \begin{aligned} \text { Minimize } & C=6 x+8 y+4 z \\ \text { subject to } & x+2 y+2 z \geq 10 \\ & 2 x+y+z \geq 24 \\ & x+y+z \geq 16 \\ x & \geq 0, y \geq 0, z \geq 0 \end{aligned} $$

Solve each linear programming problem by the simplex method. $$ \begin{array}{lc} \text { Maximize } & P=3 x+4 y+5 z \\ \text { subject to } & x+y+z \leq 8 \\ & 3 x+2 y+4 z \leq 24 \\ & x \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{array}{rr} \text { Minimize } & C=3 x+6 y \\ \text { subject to } & x+2 y \geq 40 \\ & x+y \geq 30 \\ x & \geq 0, y \geq 0 \end{array} $$

Everest Deluxe World Travel has decided to advertise in the Sunday editions of two major newspapers in town. These advertisements are directed at three groups of potential customers. Each advertisement in newspaper I is seen by 70,000 group-A customers, 40,000 group-B customers, and 20,000 group-C customers. Each advertisement in newspaper II is seen by 10,000 group-A, 20,000 group-B, and 40,000 group-C customers. Each advertisement in newspaper I costs $$\$ 1000$$, and each advertisement in newspaper II costs $$\$ 800$$. Everest would like their advertisements to be read by at least 2 million people from group A. \(1.4\) million people from group \(\mathrm{B}\), and 1 million people from group C. How many advertisements should Everest place in each newspaper to achieve its advertisement goals at a minimum cost?

Construct the dual problem associated with the primal problem. Solve the primal problem. $$ \begin{array}{ll} \text { Minimize } & C=12 x+4 y+8 z \\ \text { subject to } & 2 x+4 y+z \geq 6 \\ & 3 x+2 y+2 z \geq 2 \\ & 4 x+y+z \geq 2 \\ & x \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=3 x+3 y+4 z \\ \text { subject to } & x+y+3 z \leq 15 \\ & 4 x+4 y+3 z \leq 65 \\ x & \geq 0, y \geq 0, z \geq 0 \end{array} $$

Construct the dual problem associated with the primal problem. Solve the primal problem. $$ \begin{aligned} \text { Minimize } & C=30 x+12 y+20 z \\ \text { subject to } & 2 x+4 y+3 z \geq 6 \\ & 6 x+z \geq 2 \\ 6 y+2 z & \geq 4 \\ x & \geq 0, y \geq 0, z & \geq 0 \end{aligned} $$

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=3 x+4 y+z \\ \text { subject to } & 3 x+10 y+5 z \leq 120 \\ & 5 x+2 y+8 z \leq 6 \\ & 8 x+10 y+3 z \leq 105 \\ & x \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{aligned} \text { Minimize } & C=2 x+10 y \\ \text { subject to } & 5 x+2 y \geq 40 \\ & x+2 y \geq 20 \\ & y \geq 3, x \geq 0 \end{aligned} $$

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{array}{r} 2 x+4 y>16 \\ -x+3 y \geq 7 \end{array} $$

Construct the dual problem associated with the primal problem. Solve the primal problem. $$ \begin{array}{rr} \text { Minimize } & C=8 x+6 y+4 z \\ \text { subject to } & 2 x+3 y+z \geq 6 \\ & x+2 y-2 z \geq 4 \\ & x+y+2 z \geq 2 \\ & x \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=x+2 y-z \\ \text { subject to } & 2 x+y+z \leq 14 \\ & 4 x+2 y+3 z \leq 28 \\ & 2 x+5 y+5 z \leq 30 \\ & x \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{array}{rr} \text { Minimize } & C=2 x+5 y \\ \text { subject to } & 4 x+y \geq 40 \\ & 2 x+y \geq 30 \\ & x+3 y \geq 30 \\ & x \geq 0, y \geq 0 \end{array} $$

Ashley has earmarked at most $$\$ 250,000$$ for investment in three mutual funds: a money market fund, an international equity fund, and a growth-and- income fund. The money market fund has a rate of return of \(6 \% /\) year, the international equity fund has a rate of return of \(10 \%\) /year, and the growth-and-income fund has a rate of return of \(15 \% / y\) ear. Ashley has stipulated that no more than \(25 \%\) of her total portfolio should be in the growth-and-income fund and that no more than \(50 \%\) of her total portfolio should be in the international equity fund. To maximize the return on her investment, how much should Ashley invest in each type of fund?

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{array}{r} 3 x-2 y>-13 \\ -x+2 y>5 \end{array} $$

Deluxe River Cruises operates a fleet of river vessels. The fleet has two types of vessels: A type-A vessel has 60 deluxe cabins and 160 standard cabins. whereas a type-B vessel has 80 deluxe cabins and 120 standard cabins. Under a charter agreement with Odyssey Travel Agency, Deluxe River Cruises is to provide Odyssey with a minimum of 360 deluxe and 680 standard cabins for their 15 -day cruise in May. It costs $$\$ 44,000$$ to operate a type-A vessel and $$\$ 54,000$$ to operate a type-B vessel for that period. How many of each type vessel should be used in order to keep the operating costs to a minimum? What is the minimum cost?

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=4 x+6 y+5 z \\ \text { subject to } & x+y+z \leq 20 \\ & 2 x+4 y+3 z \leq 42 \\ & 2 x+3 z \leq 30 \\ x & \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{array}{rr} \text { Minimize } & C=2 x+5 y \\ \text { subject to } & 4 x+y \geq 40 \\ & 2 x+y \geq 30 \\ & x+3 y \geq 30 \\ & x \geq 0, y \geq 0 \end{array} $$

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{array}{r} x-y \leq 0 \\ 2 x+3 y \geq 10 \end{array} $$

Acrosonic manufactures a model-G loudspeaker system in plants I and II. The output at plant \(I\) is at most \(800 /\) month, and the output at plant II is at most \(600 /\) month. Model-G loudspeaker systems are also shipped to the three warehouses \(-\mathrm{A}, \mathrm{B}\), and \(\mathrm{C}\) -whose minimum monthly requirements are 500,400 , and 400 systems, respectively. Shipping costs from plant I to warehouse A. warehouse \(\mathrm{B}\), and warehouse \(\mathrm{C}\) are $$\$ 16$$, $$\$ 20$$, and $$\$ 22$$ per loudspeaker system, respectively, and shipping costs from plant II to each of these warehouses are $$\$ 18$$, $$\$ 16$$, and $$\$ 14$$, respectively. What shipping schedule will enable Acrosonic to meet the requirements of the warehouses while keeping its shipping costs to a minimum? What is the minimum cost?

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=x+4 y-2 z \\ \text { subject to } & 3 x+y-z \leq 80 \\ & 2 x+y-z \leq 40 \\ & -x+y+z \leq 80 \\ x & \geq 0, y \geq 0, z \geq 0 \end{array} $$

As part of a campaign to promote its annual clearance sale, the Excelsior Company decided to buy television advertising time on Station KAOS. Excelsior's advertising budget is $$\$ 102,000$$. Morning time costs $$\$ 3000 $$ minute, afternoon time costs $$\$ 1000 $$ minute, and evening (prime) time costs $$\$ 12,000 $$ minute. Because of previous commitments, KAOS cannot offer Excelsior more than \(6 \mathrm{~min}\) of prime time or more than a total of 25 min of advertising time over the 2 weeks in which the commercials are to be run. KAOS estimates that morning commercials are seen by 200,000 people, afternoon commercials are seen by 100,000 people, and evening commercials are seen by 600,000 people. How much morning, afternoon, and evening advertising time should Excelsior buy in order to maximize exposure of its commercials?

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{array}{rr} x+y & \geq-2 \\ 3 x-y & \leq 6 \end{array} $$

Everest Deluxe World Travel has decided to advertise in the Sunday editions of two major newspapers in town. These advertisements are directed at three groups of potential customers. Each advertisement in newspaper I is seen by 70,000 group-A customers, 40,000 group-B customers, and 20,000 group-C customers. Each advertisement in newspaper II is seen by 10,000 group-A, 20,000 group-B, and 40,000 group-C customers. Each advertisement in newspaper I costs $$\$ 1000$$, and each advertisement in newspaper II costs $$\$ 800$$. Everest would like their advertisements to be read by at least 2 million people from group A, \(1.4\) million people from group \(\mathrm{B}\), and 1 million people from group C. How many advertisements should Everest place in each newspaper to achieve its advertising goals at a minimum cost? What is the minimum cost?

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=12 x+10 y+5 z \\ \text { subject to } & 2 x+y+z \leq 10 \\ & 3 x+5 y+z \leq 45 \\ & 2 x+5 y+z \leq 40 \\ x & \geq 0, y \geq 0, z \geq 0 \end{array} $$

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{aligned} x+2 y & \geq 3 \\ 2 x+4 y & \leq-2 \end{aligned} $$

Steinwelt Piano manufactures uprights and consoles in two plants, plant I and plant II. The output of plant I is at most \(300 /\) month, and the output of plant \(I I\) is at most \(250 /\) month. These pianos are shipped to three warehouses that serve as distribution centers for Steinwelt. To fill current and projected future orders, warehouse A requires a minimum of 200 pianos/month, warehouse \(B\) requires at least 150 pianos/month, and warehouse \(C\) requires at least 200 pianos/month. The shipping cost of each piano from plant I to warehouse \(\mathrm{A}\), warehouse \(\mathrm{B}\), and warehouse \(\mathrm{C}\) is $$\$ 60$$, $$\$ 60$$, and $$\$ 80$$, respectively, and the shipping cost of each piano from plant II to warehouse \(\mathrm{A}\), warehouse \(\mathrm{B}\), and warehouse \(\mathrm{C}\) is $$\$ 80$$, $\$ 70$$, and $$\$ 50$$, respectively. What shipping schedule will enable Steinwelt to meet the requirements of the warehouses while keeping the shipping costs to a minimum? What is the minimum cost?

Solve each linear programming problem by the simplex method. $$ \begin{aligned} \text { Maximize } & P=2 x+6 y+6 z \\ \text { subject to } & 2 x+y+3 z \leq 10 \\ & 4 x+y+2 z \leq 56 \\ & 6 x+4 y+3 z \leq 126 \\ & 2 x+y+z \leq 32 \\ & x \geq 0, y \geq 0, z \geq 0 \end{aligned} $$

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{array}{l} 2 x-y \geq 4 \\ 4 x-2 y<-2 \end{array} $$

The owner of the Health JuiceBar wishes to prepare a low-calorie fruit juice with a high vitamin A and vitamin \(\mathrm{C}\) content by blending orange juice and pink grapefruit juice. Each glass of the blended juice is to contain at least 1200 International Units (IU) of vitamin A and \(200 \mathrm{IU}\) of vitamin \(\mathrm{C}\). One ounce of orange juice contains \(60 \mathrm{IU}\) of vitamin A, \(16 \mathrm{IU}\) of vitamin \(\mathrm{C}\), and 14 calories; each ounce of pink grapefruit juice contains \(120 \mathrm{IU}\) of vitamin A, \(12 \mathrm{IU}\) of vitamin \(\mathrm{C}\), and 11 calories. How many ounces of each juice should a glass of the blend contain if it is to meet the minimum vitamin requirements while containing a minimum number of calories?

Solve each linear programming problem by the simplex method. $$ \begin{array}{ll} \text { Maximize } & P=24 x+16 y+23 z \\ \text { subject to } & 2 x+y+2 z \leq 7 \\ & 2 x+3 y+z \leq 8 \\ & x+2 y+3 z \leq 7 \\ & x \geq 0, y \geq 0, z \geq 0 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{array}{ll} \text { Maximize } & P=2 x+3 y \\ \text { subject to } & x+y \leq 48 \\ & x+3 y \geq 60 \\ & 9 x+5 y \leq 320 \\ x & \geq 10, y & \geq 0 \end{array} $$

Costs Steinwelt Piano manufactures uprights and consoles in two plants, plant I and plant II. The output of plant \(I\) is at most \(300 \) month, whereas the output of plant II is at most \(250 \) month. These pianos are shipped to three warehouses that serve as distribution centers for the company. To fill current and projected future orders, warehouse A requires a minimum of 200 pianos/month, warehouse \(B\) requires at least 150 pianos/month, and warehouse \(\mathrm{C}\) requires at least 200 pianos/month. The shipping cost of each piano from plant I to warehouse A, warehouse \(\mathrm{B}\), and warehouse \(\mathrm{C}\) is $$\$ 60$$, $$\$ 60$$, and $$\$ 80$$, respectively, and the shipping cost of each piano from plant II to warehouse A, warehouse \(\mathrm{B}\), and warehouse \(\mathrm{C}\) is $$\$ 80$$, $$\$ 70$$, and $$\$ 50$$, respectively. What shipping schedule will enable Steinwelt to meet the warehouses' requirements while keeping shipping costs to a minimum?

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{array}{r} x+y \leq 6 \\ 0 \leq x \leq 3 \\ y \geq 0 \end{array} $$

An oil company operates two refineries in a certain city. Refinery I has an output of 200 , 100 , and 100 barrels of low-, medium-, and high-grade oil per day, respectively. Refinery II has an output of 100,200 , and 600 barrels of low-, medium-, and high-grade oil per day, respectively. The company wishes to produce at least 1000,1400 , and 3000 barrels of low-, medium-, and highgrade oil to fill an order. If it costs $$\$ 200 /$$ day to operate refinery I and $$\$ 300 /$$ day to operate refinery II, determine how many days each refinery should be operated in order to meet the production requirements at minimum cost to the company. What is the minimum cost?

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{array}{l} 4 x-3 y \leq 12 \\ 5 x+2 y \leq 10 \\ x \geq 0, y \geq 0 \end{array} $$

Determine whether the statement is true or false. If it is true, explain why it is true. If it is false, give an example to show why it is false. If a standard minimization linear programming problem has a unique solution, then so does the corresponding maximization problem with objective function \(P=-C\), where \(C=a_{1} x_{1}+a_{2} x_{2}+\cdots+a_{n} x_{n}\) is the objective function for the minimization problem.

Show that the following linear programming problem $$ \begin{array}{ll} \text { Maximize } & P=2 x+2 y-4 z \\ \text { subject to } & 3 x+3 y-2 z \leq 100 \\ & 5 x+5 y+3 z \leq 150 \\ & x \geq 0, y \geq 0, z \geq 0 \end{array} $$ has optimal solutions \(x=30, y=0, z=0, P=60\) and \(x=0, y=30, z=0, P=60\).

Solve each linear programming problem by the method of corners. Find the maximum and minimum of \(P=10 x+12 y\) subject to $$ \begin{aligned} 5 x+2 y & \geq 63 \\ x+y & \geq 18 \\ 3 x+2 y & \leq 51 \\ x \geq 0, y & \geq 0 \end{aligned} $$

Determine graphically the solution set for each system of inequalities and indicate whether the solution set is bounded or unbounded. $$ \begin{aligned} 3 x-6 y & \leq 12 \\ -x+2 y & \leq 4 \\ x \geq 0, y & \geq 0 \end{aligned} $$

A company manufactures two products, \(\mathrm{A}\) and \(\mathrm{B}\), on two machines, \(\overline{\mathrm{I}}\) and II. It has been determined that the company will realize a profit of $$\$ 3 $$ unit of product \(A\) and a profit of $$\$ 4 $$ unit of product \(\mathrm{B}\). To manufacture 1 unit of product \(\mathrm{A}\) requires 6 min on machine I and 5 min on machine II. To manufacture 1 unit of product \(\mathrm{B}\) requires \(9 \mathrm{~min}\) on machine \(\mathrm{I}\) and \(4 \mathrm{~min}\) on machine II. There are \(5 \mathrm{hr}\) of machine time available on machine I and \(3 \mathrm{hr}\) of machine time available on machine II in each work shift. How many units of each product should be produced in each shift to maximize the company's profit? What is the largest profit the company can realize? Is there any time left unused on the machines?

Solve each linear programming problem by the method of corners. Find the maximum and minimum of \(P=4 x+3 y\) subject to $$ \begin{aligned} 3 x+5 y & \geq 20 \\ 3 x+y & \leq 16 \\ -2 x+y & \leq 1 \\ x \geq 0, y & \geq 0 \end{aligned} $$

Beyer Pharmaceutical produces three kinds of cold formulas: formula I, formula II, and formula III. It takes \(2.5 \mathrm{hr}\) to produce 1000 bottles of formula I, \(3 \mathrm{hr}\) to produce 1000 bottles of formula II, and 4 hr to produce 1000 bottles of formula III. The profits for each 1000 bottles of formula I, formula II, and formula III are $$\$ 180$$, $$\$ 200$$, and $$\$ 300$$, respectively. For a certain production run, there are enough ingredients on hand to make at most 9000 bottles of formula I. \(12.000\) bottles of formula II, and 6000 bottles of formula III. Furthermore, the time for the production run is limited to a maximum of \(70 \mathrm{hr}\). How many bottles of each formula should be produced in this production run so that the profit is maximized?