Chapter 6

Use the technique developed in this section to solve the minimization problem. $$ \begin{aligned} \text { Minimize } & C=-2 x+y \\ \text { subject to } & x+2 y \leq 6 \\ & 3 x+2 y \leq 12 \\ & x \geq 0, y \geq 0 \end{aligned} $$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{cccrc|c} x & y & u & v & P & \text { Constant } \\ \hline 0 & 1 & \frac{5}{7} & -\frac{1}{7} & 0 & \frac{20}{7} \\ 1 & 0 & -\frac{3}{7} & \frac{2}{7} & 0 & \frac{30}{7} \\ \hline 0 & 0 & \frac{13}{7} & \frac{3}{7} & 1 & \frac{220}{7} \end{array} $$

Find the maximum and/or minimum value(s) of the objective function on the feasible set \(S .\) $$Z=2 x+3 y$$

A company manufactures two products, \(A\) and \(B\), on two machines, \(\bar{I}\) and II. It has been determined that the company will realize a profit of $$\$ 3$$ on each unit of product \(A\) and a profit of $$\$ 4$$ on each unit of product \(\mathrm{B}\). To manufacture a unit of product A requires \(6 \mathrm{~min}\) on machine \(\mathrm{I}\) and \(5 \mathrm{~min}\) on machine II. To manufacture a unit of product B requires 9 min on machine \(\mathrm{I}\) and \(4 \mathrm{~min}\) on machine \(\mathrm{II}\). There are \(5 \mathrm{hr}\) of machine time available on machine \(\mathrm{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?

Use the technique developed in this section to solve the minimization problem. $$ \begin{array}{ll} \text { Minimize } & C=-2 x-3 y \\ \text { subject to } & 3 x+4 y \leq 24 \\ & 7 x-4 y \leq 16 \\ & x \geq 0, y \geq 0 \end{array} $$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{rrrrr|c} x & y & u & v & P & \text { Constant } \\ \hline 1 & 1 & 1 & 0 & 0 & 6 \\ 1 & 0 & -1 & 1 & 0 & 2 \\ \hline 3 & 0 & 5 & 0 & 1 & 30 \end{array} $$

Find the maximum and/or minimum value(s) of the objective function on the feasible set \(S .\) $$Z=3 x-y$$

Find the graphical solution of each inequality. $$3 y+2>0$$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{rrrrr|r} x & y & u & v & P & \text { Constant } \\ \hline 0 & \frac{1}{2} & 1 & -\frac{1}{2} & 0 & 2 \\ 1 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 4 \\ \hline 0 & -\frac{1}{2} & 0 & \frac{3}{2} & 1 & 12 \end{array} $$

Kane Manufacturing has a division that produces two models of fireplace grates, model A and model B. To produce each model \(\mathrm{A}\) grate requires \(3 \mathrm{lb}\) of cast iron and \(6 \mathrm{~min}\) of labor. To produce each model B grate requires \(4 \mathrm{lb}\) of cast iron and \(3 \mathrm{~min}\) of labor. The profit for each model A grate is $$\$ 2.00$$, and the profit for each model B grate is $$\$ 1.50$$. If \(1000 \mathrm{lb}\) of cast iron and \(20 \mathrm{hr}\) of labor are available for the production of grates per day, how many grates of each model should the division produce per day in order to maximize Kane's profits?

Find the graphical solution of each inequality. $$x-y \leq 0$$

Use the technique developed in this section to solve the minimization problem. $$ \begin{aligned} \text { Minimize } & C=x-2 y+z \\ \text { subject to } & x-2 y+3 z \leq 10 \\ & 2 x+y-2 z \leq 15 \\ & 2 x+y+3 z \leq 20 \\ & x \geq 0, y \geq 0, z & \geq 0 \end{aligned} $$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{cccccc|c} x & y & z & u & v & P & \text { Constant } \\ \hline 3 & 0 & 5 & 1 & 1 & 0 & 28 \\ 2 & 1 & 3 & 0 & 1 & 0 & 16 \\ \hline 2 & 0 & 8 & 0 & 3 & 1 & 48 \end{array} $$

Find the graphical solution of each inequality. $$3 x+4 y \leq-2$$

Use the technique developed in this section to solve the minimization problem. $$ \begin{aligned} \text { Minimize } & C=2 x-3 y-4 z \\ \text { subject to } &-x+2 y-z \leq 8 \\ & x-2 y+2 z \leq 10 \\ & 2 x+4 y-3 z \leq 12 \\ x & \geq 0, y \geq 0, z \geq 0 \end{aligned} $$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{rrrrrrr|c} x & y & z & u & v & w & P & \text { Constant } \\ \hline 1 & -\frac{1}{3} & 0 & \frac{1}{3} & 0 & -\frac{2}{3} & 0 & \frac{1}{3} \\\ 0 & 2 & 0 & 0 & 1 & 1 & 0 & 6 \\ 0 & \frac{2}{3} & 1 & \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{13}{3} \\ \hline 0 & 4 & 0 & 1 & 0 & 2 & 1 & 17 \end{array} $$

A division of the Winston Furniture Company manufactures dining tables and chairs. Each table requires 40 board feet of wood and 3 labor-hours. Each chair requires 16 board feet of wood and 4 labor-hours. The profit for each table is $$\$ 45$$, and the profit for each chair is $$\$ 20$$. In a certain week, the company has 3200 board feet of wood available, and 520 labor-hours. How many tables and chairs should Winston manufacture in order to maximize its profits?

Find the graphical solution of each inequality. $$x \leq-3$$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{rrrrrrr|c} x & y & z & u & v & w & P & \text { Constant } \\ \hline \frac{1}{2} & 0 & \frac{1}{4} & 1 & -\frac{1}{4} & 0 & 0 & \frac{19}{2} \\\ \frac{1}{2} & 1 & \frac{3}{4} & 0 & \frac{1}{4} & 0 & 0 & \frac{21}{2} \\ 2 & 0 & 3 & 0 & 0 & 1 & 0 & 30 \\ \hline-1 & 0 & -\frac{1}{2} & 6 & \frac{3}{2} & 0 & 1 & 63 \end{array} $$

Find the graphical solution of each inequality. $$y \geq-1$$

You are given the final simplex tablea for the dual problem. Give the solution to the primal prob lem and the solution to the associated dual problem. Problem: Minimize \(C=8 x+12 y\) subject to \(\begin{aligned} x+3 y & \geq 2 \\ 2 x+2 y & \geq 3 \\ x \geq 0, y & \geq 0 \end{aligned}\) Final tableau: $$ \begin{array}{ccccc|c} u & v & x & y & P & \text { Constant } \\ \hline 0 & 1 & \frac{3}{4} & -\frac{1}{4} & 0 & 3 \\ 1 & 0 & -\frac{1}{2} & \frac{1}{2} & 0 & 2 \\ \hline 0 & 0 & \frac{5}{4} & \frac{1}{4} & 1 & 13 \end{array} $$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{rrrrrrrr|r} x & y & z & s & t & u & v & P & \text { Constant } \\ \hline \frac{5}{2} & 3 & 0 & 1 & 0 & 0 & -4 & 0 & 46 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 9 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 12 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 6 \\ \hline-180 & -200 & 0 & 0 & 0 & 0 & 300 & 1 & 1800 \end{array} $$

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

Madison Finance has a total of $$\$ 20$$ million earmarked for homeowner and auto loans. On the average, homeowner loans have a \(10 \%\) annual rate of return whereas auto loans yield a \(12 \%\) annual rate of return. Management has also stipulated that the total amount of homeowner loans should be greater than or equal to 4 times the total amount of automobile loans. Determine the total amount of loans of each type Madison should extend to each category in order to maximize its returns.

Find the graphical solution of each inequality. $$2 x+y \leq 4$$

You are given the final simplex tablea for the dual problem. Give the solution to the primal prob lem and the solution to the associated dual problem. Problem: Minimize \(\quad C=3 x+2 y\) subject to \(\begin{aligned} 5 x+y & \geq 10 \\ 2 x+2 y & \geq 12 \\ x+4 y & \geq 12 \\ x \geq 0, y & \geq 0 \end{aligned}\) Final tableau: $$ \begin{array}{rrrrrr|r} u & v & w & x & y & P & \text { Constant } \\ \hline 1 & 0 & -\frac{3}{4} & \frac{1}{4} & -\frac{1}{4} & 0 & \frac{1}{4} \\ 0 & 1 & \frac{19}{8} & -\frac{1}{8} & \frac{5}{8} & 0 & \frac{7}{8} \\ \hline 0 & 0 & 9 & 1 & 5 & 1 & 13 \end{array} $$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{rrrrrrrr|r} x & y & z & s & t & u & v & P & \text { Constant } \\ \hline 1 & 0 & 0 & \frac{2}{5} & 0 & -\frac{6}{5} & -\frac{8}{5} & 0 & 4 \\ 0 & 0 & 0 & -\frac{2}{5} & 1 & \frac{6}{5} & \frac{8}{5} & 0 & 5 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 12 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 6 \\ \hline 0 & 0 & 0 & 72 & 0 & -16 & 12 & 1 & 4920 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{array}{lr} \text { Maximize } & P=x+2 y \\ \text { subject to } & x+y \leq 4 \\ & 2 x+y \leq 5 \\ & x \geq 0, y \geq 0 \end{array} $$

A financier plans to invest up to $$\$ 500,000$$ in two projects. Project A yields a return of \(10 \%\) on the investment whereas project B yields a return of \(15 \%\) on the investment. Because the investment in project \(\mathrm{B}\) is riskier than the investment in project \(\mathrm{A}\), the financier has decided that the investment in project \(\bar{B}\) should not exceed \(40 \%\) of the total investment. How much should she invest in each project in order to maximize the return on her investment?

Find the graphical solution of each inequality. $$-3 x+6 y \geq 12$$

You are given the final simplex tablea for the dual problem. Give the solution to the primal prob lem and the solution to the associated dual problem. \(\begin{array}{rr}\text { Problem: Minimize } & C=10 x+3 y+10 z \\ \text { subject to } & 2 x+y+5 z \geq 20 \\ & 4 x+y+z \geq 30 \\ x & \geq 0, y \geq 0, z \geq 0\end{array}\) Final tableau: $$ \begin{array}{rrrrrr|r} u & v & x & y & z & P & \text { Constant } \\ \hline 0 & 1 & \frac{1}{2} & -1 & 0 & 0 & 2 \\ 1 & 0 & -\frac{1}{2} & 2 & 0 & 0 & 1 \\ 0 & 0 & 2 & -9 & 1 & 0 & 3 \\ \hline 0 & 0 & 5 & 10 & 0 & 1 & 80 \end{array} $$

Determine whether the given simplex tableau is in final form. If so, find the solution to the associated regular linear programming problem. If not, find the pivot element to be used in the next iteration of the simplex method. $$ \begin{array}{ccrcrc|c} x & y & z & u & v & P & \text { Constant } \\ \hline 1 & 0 & \frac{3}{5} & 0 & \frac{1}{5} & 0 & 30 \\ 0 & 1 & -\frac{19}{5} & 1 & -\frac{3}{5} & 0 & 10 \\ \hline 0 & 0 & \frac{26}{5} & 0 & 0 & 1 & 60 \end{array} $$

Acoustical Company manufactures a CD storage cabinet that can be bought fully assembled or as a kit. Each cabinet is processed in the fabrications department and the assembly department. If the fabrication department only manufactures fully assembled cabinets, then it can produce 200 units/day; and if it only manufactures kits, it can produce 200 units/day. If the assembly department only produces fully assembled cabinets, then it can produce 100 units/day; but if it only produces kits, then it can produce 300 units/day. Each fully assembled cabinet contributes $$\$ 50$$ to the profits of the company whereas each kit contributes $$\$ 40$$ to its profits. How many fully assembled units and how many kits should the company produce per day in order to maximize its profits?

You are given the final simplex tablea for the dual problem. Give the solution to the primal prob lem and the solution to the associated dual problem. Problem: Minimize \(\quad C=2 x+3 y\) subject to \(\begin{aligned} x+4 y & \geq 8 \\ x+y & \geq 5 \\ 2 x+y & \geq 7 \\\ x \geq 0, y & \geq 0 \end{aligned}\) Final tableau: $$ \begin{array}{cccccc|c} u & v & w & x & y & P & \text { Constant } \\ \hline 0 & 1 & \frac{7}{3} & \frac{4}{3} & -\frac{1}{3} & 0 & \frac{5}{3} \\ 1 & 0 & -\frac{1}{3} & -\frac{1}{3} & \frac{1}{3} & 0 & \frac{1}{3} \\ \hline 0 & 0 & 2 & 4 & 1 & 1 & 11 \end{array} $$

Solve each linear programming problem by the method of corners. $$ \begin{array}{l} \text { Maximize } P=4 x+2 y \\ \text { subject to } \quad x+y \leq 8 \\ \quad 2 x+y \leq 10 \\ x \geq 0, y \geq 0 \end{array} $$

A farmer plans to plant two crops, A and B. The cost of cultivating crop \(\mathrm{A}\) is $$\$ 40 $$ acre whereas that of crop \(\mathrm{B}\) is $$\$ 60$$ acre. The farmer has a maximum of $$\$ 7400$$ available for land cultivation. Each acre of crop A requires 20 labor-hours, and each acre of crop \(\mathrm{B}\) requires 25 labor-hours. The farmer has a maximum of 3300 labor- hours available. If she expects to make a profit of $$\$ 150$$ acre on crop \(\mathrm{A}\) and $$\$ 200$$ acre on crop \(\mathrm{B}\), how many acres of each crop should she plant in order to maximize her profit?

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

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

Perth Mining Company operates two mines for the purpose of extracting gold and silver. The Saddle Mine costs $$\$ 14,000 $$ day to operate, and it yields 50 oz of gold and 3000 oz of silver each day. The Horseshoe Mine costs $$\$ 16,000 $$ day to operate, and it yields 75 oz of gold and 1000 oz of silver each day. Company management has set a target of at least 650 oz of gold and \(18.000\) oz of silver. How many days should each mine be operated so that the target can be met at a minimum cost?

Construct the dual problem associated with the primal problem. Solve the primal problem. $$ \begin{aligned} \text { Minimize } & C=3 x+2 y \\ \text { subject to } & 2 x+3 y \geq 90 \\ & 3 x+2 y \geq 120 \\ & x \geq 0, y \geq 0 \end{aligned} $$

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

Solve each linear programming problem by the method of corners. $$ \begin{array}{cc} \text { Maximize } & P=3 x-4 y \\ \text { subject to } & x+3 y \leq 15 \\ & 4 x+y \leq 16 \\ & x \geq 0, y \geq 0 \end{array} $$

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

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

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

The water-supply manager for a Midwest city needs to supply the city with at least 10 million gal of potable (drinkable) water per day. The supply may be drawn from the local reservoir or from a pipeline to an adjacent town. The local reservoir has a maximum daily yield of 5 million gallons of potable water, and the pipeline has a maximum daily yield of 10 million gallons. By contract, the pipeline is required to supply a minimum of 6 million gallons/day. If the cost for 1 million gallons of reservoir water is $$\$ 300$$ and that for pipeline water is $$\$ 500$$, how much water should the manager get from each source to minimize daily water costs for the city?

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

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

Solve each linear programming problem by the method of corners. $$ \begin{aligned} \text { Maximize } & P=2 x+5 y \\ \text { subject to } & 2 x+y \leq 16 \\ & 2 x+3 y \leq 24 \\ y & \leq 6 \\ x & \geq 0, y \geq 0 \end{aligned} $$

Ace Novelty manufactures "Giant Pandas" and "Saint Bernards." Each Panda requires \(1.5 \mathrm{yd}^{2}\) of plush, \(30 \mathrm{ft}^{3}\) of stuffing, and 5 pieces of trim; each Saint Bernard requires \(2 \mathrm{yd}^{2}\) of plush, \(35 \mathrm{ft}^{3}\) of stuffing, and 8 pieces of trim. The profit for each Panda is $$\$ 10$$ and the profit for each Saint Bemard is $$\$ 15$$. If \(3600 \mathrm{yd}^{2}\) of plush, \(66,000 \mathrm{ft}^{3}\) of stuffing and 13,600 pieces of trim are available, how many of each of the stuffed animals should the company manufacture to maximize profit?