# Chapter 17: Chapter 17

Problem 398

Find nonnegative numbers $\mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3}, \mathrm{x}_{4}\( which maximize \)4 \mathrm{x}_{1}+5 \mathrm{x}_{2}+3 \mathrm{x}_{3}+6 \mathrm{x}_{4}$ and satisfy the inequalities $\mathrm{x}_{1}+3 \mathrm{x}_{2}+\mathrm{x}_{3}+2 \mathrm{x}_{4} \leq 2$ \(3 \mathrm{x}_{1}+3 \mathrm{x}_{2}+2 \mathrm{x}_{3}+2 \mathrm{x}_{4} \leq 4\) \(3 \mathrm{x}_{1}+2 \mathrm{x}_{2}+4 \mathrm{x}_{3}+5 \mathrm{x}_{4} \leq 6\)

Problem 399

Find nonnegative numbers $\mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3}, \mathrm{x}_{4}\( which maximize \)3 \mathrm{x}_{1}+\mathrm{x}_{2}+9 \mathrm{x}_{3}-9 \mathrm{x}_{4}$ and satisfy the conditions $\mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3}-5 \mathrm{x}_{4}=4$ \(\mathrm{x}_{1}-\mathrm{x}_{2}+3 \mathrm{x}_{3}+\mathrm{x}_{4}=0\)

Problem 400

Use the simplex algorithm to solve the following linear programming problem: Maximize $$ z=4 x_{1}+8 x_{2}+5 x_{3} $$ subject to $$ \begin{aligned} &\mathrm{x}_{1}+2 \mathrm{x}_{2}+3 \mathrm{x}_{3} \leq 18 \\ &\mathrm{x}_{1}+4 \mathrm{x}_{2}+\mathrm{x}_{3} \leq 6 \\ &2 \mathrm{x}_{1}+6 \mathrm{x}_{2}+4 \mathrm{x}_{3} \leq 15 \\ &\mathrm{x}_{1} \geq 0, \mathrm{x}_{2} \geq 0, \mathrm{x}_{3} \geq 0 \end{aligned} $$

Problem 401

Show through the simplex method and then graphically that the following linear program has no solution. Maximize \(\quad 2 \mathrm{x}+\mathrm{y}\) subject to $$ \begin{aligned} &-x+y \leq 1 \\ &x-2 y \leq 2 \end{aligned} $$ \(\mathrm{x}, \mathrm{y} \geq 0 .\)

Problem 402

The following problem is an illustration of degeneracy. Maximize $\quad \mathrm{P}=4 \mathrm{x}_{1}+3 \mathrm{x}_{2}$ subject to $$ \begin{aligned} &4 \mathrm{x}_{1}+2 \mathrm{x}_{2} \leq 10.0 \\ &2 \mathrm{x}_{1}+8 / 3 \mathrm{x}_{2} \leq 8.0 \\ &\mathrm{x}_{1} \geq 0, \mathrm{x}_{2} \geq 1.8 \end{aligned} $$ What are the signs of degeneracy a) in the simplex tableau b) graphically?

Problem 403

The optimum solution to the problem Maximize $\quad \mathrm{P}=12 \mathrm{x}_{1}+9 \mathrm{x}_{2}$ subject to $$ \begin{aligned} &3 \mathrm{x}_{1}+2 \mathrm{x}_{2} \leq 7 \\ &3 \mathrm{x}_{1}+\mathrm{x}_{2} \leq 4 \\ &\mathrm{x}_{1} \geq 0, \mathrm{x}_{2} \geq 0 \end{aligned} $$ is \(P=9(7 / 2)=31(1 / 2)\). The solution to the dual is $\mathrm{y}_{1}=4(1 / 2), \mathrm{y}_{2}=0$ Now assume the first constraint of \((2)\) is changed from 7 to 8 , i.e., $$ 3 \mathrm{x}_{1}+2 \mathrm{x}_{2} \leq 8 $$ Find the increase in \(\mathrm{P}\). What is the dual for this new problem?

Problem 404

In a manufacturing process, the final product has a requirement that it must weigh exactly 150 pounds. The two raw materials used are \(\mathrm{A}\), with a cost of \(\$ 4\) per unit and \(\mathrm{B}\), with a cost of \(\$ 8\) per unit. At least 14 units of \(\mathrm{B}\) and no more than 20 units of A must be used. Each unit of A weighs 5 pounds; each unit of \(\mathrm{B}\) weighs 10 pounds. How much of each type of raw material should be used for each unit of final product if we wish to minimize cost?

Problem 406

Consider the following problem: Maximize \(\quad \mathrm{P}=5 \mathrm{x}_{1}+8 \mathrm{x}_{2}\) subject to $$ \begin{aligned} &2 \mathrm{x}_{1}+\mathrm{x}_{2} \leq 14 \\ &\mathrm{x}_{1}+3 \mathrm{x}_{2} \leq 12 \\ &\mathrm{x}_{2} \leq 3 \\ &\mathrm{x}_{1} \geq 0, \mathrm{x}_{2} \geq 0 \end{aligned} $$ Suppose that an additional constraint on \(\mathrm{x}_{1}\) and \(\mathrm{x}_{2}\) is imposed: $$ \mathrm{x}_{1}+\mathrm{x}_{2} \leq \mathrm{K} $$ where \(\mathrm{K}\) is some unspecified amount. How does the solution of \((1),(2)\) and (3) change as \(\mathrm{K}\) varies from zero to very large values?

Problem 408

The Brown Company has two warehouses and three retail outlets. Warehouse number one (which will be denoted by \(\mathrm{W}_{1}\) ) has a capacity of 12 units; warehouse number two \(\left(\mathrm{W}_{2}\right)\) holds 8 units. These warehouses must ship the product to the three outlets, denoted by \(\mathrm{O}_{1}, \mathrm{O}_{2}\), and \(\mathrm{O}_{3} \cdot \mathrm{O}_{1}\) requires 8 units. \(\mathrm{O}_{2}\) requires 7 units, and \(\mathrm{O}_{3}\) requires 5 units. Thus, there is a total storage capacity of 20 units, and also a demand for 20 units. The question is, which warehouse should ship how many units to which outlet? (The objective being, of course, to accomplish this at the least possible cost.) Costs of shipping from either warehouse to any of the outlets are known and are summarized in the following table, which also sets forth the warehouse capacities and the needs of the retail outlets: $$ \begin{array}{|c|c|c|c|c|} \hline & \mathrm{O}_{1} & \mathrm{O}_{2} & \mathrm{O}_{3} & \text { Capacity } \\\ \hline \mathrm{W}_{1} \ldots \ldots \ldots & \$ 3.00 & \$ 5.00 & \$ 3.00 & 12 \\\ \hline \mathrm{W}_{2} \ldots \ldots . . & 2.00 & 7.00 & 1.00 & 8 \\ \hline \text { Needs (units) } & 8 & 7 & 5 & \\ \hline \end{array} $$

Problem 410

Solve the following problem in integer programming: Find non-negative integers \(X_{i j}\) which will Minimize $200 \mathrm{X}_{11}+300 \mathrm{X}_{12}+250 \mathrm{x}_{21}+100 \mathrm{X}_{22}+250 \mathrm{X}_{31}+250 \mathrm{X}_{32}$ subject to