A marketing manager wishes to maximize the number of people exposed to the company's advertising. He may choose television commercials, which reach 20 million people per commercial, or magazine advertising, which reaches 10 million people per advertisement. Magazine advertisements cost \(\$ 40,000\) each while a television advertisement costs \(\$ 75,000\). The manager has a budget of \(\$ 2,000,000\) and must buy at least 20 magazine advertisements. How many units of each type of advertising should be purchased?

Consider the following integer programming problem: Maximize \(\quad P=6 x_{1}+3 x_{2}+x_{3}+2 x_{4}\) subject to $$ \begin{array}{|l|l|l|l|l|l|} \hline \mathrm{x}_{1} & +\mathrm{x}_{2} & +\mathrm{x}_{3} & +\mathrm{x}_{4} & \leq & 8 \\ \hline 2 \mathrm{x}_{1} & +\mathrm{x}_{2} & +3 \mathrm{x}_{3} & & \leq & 12 \\\ \hline & 5 \mathrm{x}_{2} & +\mathrm{x}_{3} & +3 \mathrm{x}_{4} & \leq & 6 \\ \hline \mathrm{x}_{1} & & & & \leq & 1 \\ \hline & \mathrm{x}_{2} & & & \leq & 1 \\ \hline & & \mathrm{x}_{3} & & \leq & 4 \\ \hline & & & \mathrm{x}_{4} & \leq & 2 \\ \hline \end{array} $$ \(\mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3}, \mathrm{x}_{4}\) all non- negative integers. Use the branch and bound algorithm to solve this problem.

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?

Find a basic feasible solution to the problem: Maximize $\quad \mathrm{x}_{1}+2 \mathrm{x}_{2}+3 \mathrm{x}_{3}+4 \mathrm{x}_{4}$ while satisfying the conditions $$ \begin{aligned} &\mathrm{x}_{1}+2 \mathrm{x}_{2}+\mathrm{x}_{3}+\mathrm{x}_{4}=3 \\ &\mathrm{x}_{1}-\mathrm{x}_{2}+2 \mathrm{x}_{3}+\mathrm{x}_{4}=4 \\ &\mathrm{x}_{1}+\mathrm{x}_{2}-\mathrm{x}_{3}-\mathrm{x}_{4}=-1 \end{aligned} $$ \(\mathrm{x}_{1}, \mathrm{x}_{2}, \mathrm{x}_{3}, \mathrm{x}_{4} \geq 0\)

A manufacturer of electronic instruments produces two types of timer: a standard and a precision model with net profits of \(\$ 10\) and \(\$ 15\), respectively. His work force cannot produce more than 50 instruments per day. Moreover, the four main components used in production are in short supply so that the following stock constraints hold: $$ \begin{array}{|c|c|c|c|} \hline & & \text { Number used } & \text { per timer } \\ \hline \text { Component } & \text { Stock } & \text { Standard } & \text { Precision } \\ \hline \mathrm{a} & 220 & 4 & 2 \\ \hline \mathrm{b} & 160 & 2 & 4 \\ \hline \mathrm{c} & 370 & 2 & 10 \\ \hline \mathrm{d} & 300 & 5 & 6 \\ \hline \end{array} $$ Graphically determine the point of optimum profit. If profits on the standard timer were to change, by how much could they change without altering the original solution?

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} $$