\pdfpagewidth=8.5truein  \pdfpageheight=11truein
\hsize=5.7truein  \vsize=8.6truein
\pdfhorigin=1.4truein  \pdfvorigin=1.2truein

\def\_{\leavevmode \vbox{\hrule height0pt depth0.4pt width3em}}
\def\frac#1#2{{#1\over#2}}

\headline={\hfil}  \footline={\hfil Page~\folio\hfil}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf3.5.9.}\enspace The Mythic Forge \& Steel Co.\ (MF\&S) supplies
castings to a variety of customers. It plans to devote the next week of
production to just two, James Manufacturing and Woolcott Enterprises. MF\&S
uses a combination of pure steel and scrap metal to fulfill its orders and has
400~pounds of pure steel and 360~pounds of scrap metal in stock. The pure steel
costs MF\&S \$6~per pound and the scrap \$3~per pound. Pure steel requires
3~hours per pound to process into a casting, while scrap requires only 2~hours
per pound. Total available processing time in the week is 2,000 hours.

The castings for James each require 5~pounds of metal, with a quality control
restriction limiting the ratio of scrap to pure steel to a maximum
of~$\frac57$. James has ordered 30~castings at a price of \$50 each.

The castings for Woolcott each require 8~pounds of metal, with a quality
restriction of a maximum scrap-to-pure-steel ratio of~$\frac23$. Woolcott has
ordered 40~castings at a price of \$80 each.

Determine how MF\&S should allocate their metal stocks to produce the castings
ordered by these two customers if the objective is to maximize the value added
to the metal, i.e., to maximize the selling price minus the cost of the metal.

\bigbreak

\noindent{\it Variables.}\enspace The first thing to consider is what our
variables are. Think about the decisions in the problem, and what an answer to
the problem would look like. In this case, an answer to the problem would look
like the following:

{\smallskip\narrower

\noindent MF\&S should allocate \_ pounds of pure steel and \_ pounds of scrap
metal to the castings for James, and \_ pounds of pure steel and \_ pounds of
scrap metal to the castings for Woolcott.

\smallskip}

\noindent This is the form of a full and complete answer to the question posed
in the problem. These blanks should contain numbers. Those numbers are the
decisions we must make in order to answer the question. Therefore, we should
define a variable for each of these blanks.

So we'll define the following variables, being very careful to define precisely
what each of the variables means:

\def\PJ{\mathord{\hbox{\it PJ\/}}}  \def\SJ{\mathord{\hbox{\it SJ\/}}}
\def\PW{\mathord{\hbox{\it PW\/}}}  \def\SW{\mathord{\hbox{\it SW\/}}}

\smallskip

\item{$\bullet$} Let $\PJ$ be the number of pounds of pure steel allocated to
the castings for James.

\item{$\bullet$} Let $\SJ$ be the number of pounds of scrap metal allocated to
the castings for James.

\item{$\bullet$} Let $\PW$ be the number of pounds of pure steel allocated to
the castings for Woolcott.

\item{$\bullet$} Let $\SW$ be the number of pounds of scrap metal allocated to
the castings for Woolcott.

\smallskip

\noindent Notice that we are using descriptive names for the variables, rather
than nondescriptive names like $x_1$,~$x_2$, $x_3$, and~$x_4$.

\medbreak

\noindent{\it Variable domains.}\enspace It is important to specify the domains
of the variables, that~is, whether each variable is nonnegative, nonpositive,
or unrestricted. This is easy to forget, so let's do it now. In this case, all
of our variables must be nonnegative, so we have the variable domains
$\PJ\ge0$, $\SJ\ge0$, $\PW\ge0$, and $\SW\ge0$.

\medbreak

\noindent{\it Objective function.}\enspace Now that we have defined our
variables, we should consider the objective function. The objective function is
the quantity that we are aiming to minimize or maximize. In this problem, our
objective is to maximize the selling price minus the cost of the metal.

We know that the total selling price of the castings for James will be
$30\times\$50=\$1500$, and the total selling price of the castings for Woolcott
will be $40\times\$80=\$3200$, so the total selling price of all of the
castings will be $\$1500+\$3200=\$4700$.

Each pound of pure steel that MF\&S uses costs~\$6. There will be
$\PJ$~pounds of pure steel used for James and $\PW$~pounds of pure steel used
for Woolcott, so the total number of pounds of pure steel used will be
$\PJ+\PW$. Therefore, the total cost of the pure steel used will be
$6(\PJ+\PW)=6\PJ+6\PW$ dollars.

Similarly: Each pound of scrap metal that MF\&S uses costs~\$3. There will be
$\SJ$~pounds of scrap metal used for James and $\SW$~pounds of scrap metal used
for Woolcott, so the total number of pounds of scrap metal used will be
$\SJ+\SW$. Therefore, the total cost of the scrap metal used will be
$3(\SJ+\SW)=3\SJ+3\SW$ dollars.

This means that the total cost of all of the metal used will be
$6\PJ+6\PW+3\SJ+3\SW$ dollars.

Our objective is to maximize the selling price minus the cost of the metal, so
we want to maximize $4700-6\PJ-6\PW-3\SJ-3\SW$. That is our objective function.

\medbreak

\noindent{\it Constraints.}\enspace To identify the constraints, let's go
through the problem sentence by sentence.

{\smallskip\narrower

\noindent The Mythic Forge \& Steel Co.\ (MF\&S) supplies castings to a variety
of customers. It plans to devote the next week of production to just two, James
Manufacturing and Woolcott Enterprises. MF\&S uses a combination of pure steel
and scrap metal to fulfill its orders $\ldots$

\smallskip}

\noindent Okay, so far this is just introductory information about the company.

{\smallbreak\narrower

\noindent $\ldots$ and has 400~pounds of pure steel and 360~pounds of scrap
metal in stock.

\smallskip}

\noindent This is a description of two resource constraints. The total amount
of pure steel MF\&S uses, which is given by $\PJ+\PW$, must not exceed
400~pounds; therefore, we have the constraint $\PJ+\PW\le400$. Likewise, the
total amount of scrap metal MF\&S uses, which is given by $\SJ+\SW$, must not
exceed 360~pounds; therefore, we have the constraint $\SJ+\SW\le360$.

{\smallbreak\narrower

\noindent The pure steel costs MF\&S \$6~per pound and the scrap \$3~per pound.

\smallskip}

\noindent We used this information to formulate the objective function.

{\smallbreak\narrower

\noindent Pure steel requires 3~hours per pound to process into a casting,
whil scrap requires only 2~hours per pound. Total available processing time in
the week is 2,000 hours.

\smallskip}

\noindent This describes another resource constraint; the resource here is
processing time. As with all resources, the amount of this resource that MF\&S
uses must not exceed the amount that is available, so the form of the resource
constraint should be $(\hbox{amount used})\le(\hbox{amount available})$. The
amount of processing time available is clearly stated: 2,000 hours. To find the
amount of processing time used, break it up into the amount used for the pure
steel and the amount used for the scrap metal. The total amount of pure steel
used is $\PJ+\PW$ pounds, and each pound of pure steel requires 3~hours of
processing time, so the amount of processing time used for the pure steel is
$3(\PJ+\PW)=3\PJ+3\PW$ hours. Likewise, the total amount of scrap metal used is
$\SJ+\SW$ pounds, and each pound of scrap metal requires 2~hours of processing
time, so the amount of processing time used for the scrap metal is
$2(\SJ+\SW)=2\SJ+2\SW$ hours. Therefore, the total amount of processing time
required for all of the metal is $3\PJ+3\PW+2\SJ+2\SW$ hours, and this must not
exceed the amount of this resource that we have available, which is 2,000
hours. This means that we have the constraint $3\PJ+3\PW+2\SJ+2\SW\le2{,}000$.

{\smallbreak\narrower

\noindent The castings for James each require 5~pounds of metal \dots. James
has ordered 30~castings at a price of \$50 each.

\smallskip}

\noindent We used the price information to formulate the objective function.
But these sentences also give us information about the total weight of metal
that must be used for the castings for James: $30\times5=150$ pounds. Now, the
amount of metal that is to be allocated to these castings is $\PJ+\SJ$ pounds,
so we must have the equality constraint $\PJ+\SJ=150$.

{\smallbreak\narrower

\noindent The castings for James $\ldots$ [have] a quality control restriction
limiting the ratio of scrap to pure steel to a maximum of~$\frac57$.

\smallskip}

\noindent The amount of scrap metal used for the castings for James is
$\SJ$~pounds, and the amount of pure steel used for the castings for James is
$\PJ$~pounds, so the ratio of scrap metal to pure steel for these castings
is~$\SJ/\PJ$. The requirement is that this ratio be no greater than~$\frac57$,
so we have the constraint $\SJ/\PJ\le\frac57$. As written, this is not a linear
inequality, because we are dividing one variable by another. But we can
multiply both sides of the inequality by~$\PJ$ (which is nonnegative, so the
inequality sign does not flip) to get the linear inequality $\SJ\le\frac57\PJ$.

{\smallbreak\narrower

\noindent The castings for Woolcott each require 8~pounds of metal, with a
quality restriction of a maximum scrap-to-pure-steel ratio of~$\frac23$.
Woolcott has ordered 40~castings at a price of \$80 each.

\smallskip}

\noindent Exactly like the previous paragraph: The total amount of metal that
must be used for the Woolcott castings is $40\times8=320$ pounds, and the
amount of metal that is to be allocated to these castings is $\PW+\SW$ pounds,
so we must have the equality constraint $\PW+\SW=320$. These castings are to be
made from $\SW$~pounds of scrap metal and $\PW$~pounds of pure steel, so the
ratio of scrap metal to pure steel is~$\SW/\PW$. This ratio must be no larger
than~$\frac23$, so we have the constraint $\SW/\PW\le\frac23$. In order to
write this as a linear inequality, we multiply both sides by the (nonnegative)
quantity~$\PW$ to get $\SW\le\frac23\PW$.

{\smallbreak\narrower

\noindent Determine how MF\&S should allocate their metal stocks to produce the
castings ordered by these two customers if the objective is to maximize the
value added to the metal, i.e., to maximize the seling price minus the cost of
the metal.

\smallskip}

\noindent This paragraph is telling us what our objective function is (and,
before that, what questions we are asked to answer, so that we know what our
variables should be).

\medbreak

That's every sentence in the problem, so that takes care of the constraints.
Putting everything together now, we get the following linear program:
$$\eqalignno{
	{\rm maximize}\quad
		&4700-6\PJ-6\PW-3\SJ-3\SW\cr
	{\rm subject\ to}\quad
		&\PJ+\PW\le400&\hbox{[pure steel in stock]}\cr
		&\SJ+\SW\le360&\hbox{[scrap metal in stock]}\cr
		&3\PJ+3\PW+2\SJ+2\SW\le2{,}000&\hbox{[processing time]}\cr
		&\PJ+\SJ=150&\hbox{[enough metal for James]}\cr
		&\SJ\le\frac57\PJ&\hbox{[quality restriction for James]}\cr
		&\PW+\SW=320&\hbox{[enough metal for Woolcott]}\cr
		&\SW\le\frac23\PW&\hbox{[quality restriction for Woolcott]}\cr
	\noalign{\smallskip}
		&\PJ\ge0,\quad\SJ\ge0,\quad\PW\ge0,\quad\SW\ge0.\hskip10em\cr
}$$

\medbreak

\noindent{\it Implementation notes.}\enspace What we have above is a perfectly
fine linear programming formulation of the problem. If we want to actually
solve this linear program, however, we will have to make two small changes.

First, our objective function contains a constant term, 4700. The simplex
algorithm is not designed to work with objective functions containing constant
terms. But because 4700 is a constant, this is not a problem: we will just
subtract the 4700 term from the objective function, maximize the quantity
$-6\PJ-6\PW-3\SJ-3\SW$ instead (which is 4700~less than the quantity we really
want to maximize), and remember to add 4700 back to the optimal objective value
at the end.

(The textbook's formulation for this problem takes a different approach here.
Rather than subtracting the total cost of the metal from the total selling
price, as we did, the textbook works with each pound of metal individually.
Each pound of pure steel allocated to the castings for James costs~\$6 and
sells for~\$10, because the 5-pound castings for James sell for~\$50; so the
value added for each pound of pure steel allocated for James is $\$10-\$6=\$4$,
and therefore the total value added for all of the pure steel allocated for
James is $4\PJ$~dollars. Similarly, the total value added for the scrap metal
allocated for James is $7\PW$~dollars, the total value added for the pure steel
allocated for Woolcott is $4\PW$~dollars, and the total value added for the
scrap metal allocated for Woolcott is $7\SW$~dollars. Therefore, the total
value added altogether is $4\PJ+7\PW+4\PW+7\SW$ dollars, and this is what the
textbook uses as the objective function. This will be equal to our objective
function, $4700-6\PJ-6\PW-3\SJ-3\SW$, for any feasible solution.)

Second, some of our constraints have variables on the right-hand side of the
inequality. We will need to move these to the left-hand side before we apply
the simplex algorithm. So the constraint $\SJ\le\frac57\PJ$ becomes
$\SJ-\frac57\PJ\le0$, and the constraint $\SW\le\frac23\PW$ becomes
$\SW-\frac23\PW\le0$. (If we like, we can multiply these constraints by a
constant to clear the fractions; so $\SJ-\frac57\PJ\le0$ becomes
$7\SJ-5\PJ\le0$ after we multiply by~7, and $\SW-\frac23\PW\le0$ becomes
$3\SW-2\PW\le0$ after we multiply by~3. But doing this will not necessarily
make the simplex algorithm easier, because once we start pivoting we will
probably have to divide by these constants and come back to fractions anyway.)

\goodbreak

After we make these small changes and rearrange the constraints to line up the
variables in columns, we get the linear program
$$\eqalign{
	{\rm maximize}\quad{-6}\PJ-3\SJ-6\PW-3\SW&\cr
	{\rm subject\ to}\quad
	\phantom{-6}\PJ\phantom{{}+0\SJ}+\phantom1\PW\phantom{{}+0\SW}&\le\phantom{0,}400\cr
	\SJ\phantom{{}+0\PW}+\phantom1\SW&\le\phantom{0,}360\cr
	3\PJ+2\SJ+3\PW+2\SW&\le2{,}000\cr
	\PJ+\phantom1\SJ\phantom{{}+0\PW+0\SW}&=\phantom{0,}150\cr
	-\frac57\PJ+\phantom1\SJ\phantom{{}+0\PW+0\SW}&\le\phantom{0{,}00}0\cr
	\PW+\phantom1\SW&=\phantom{0,}320\cr
	-\frac23\PW+\phantom1\SW&\le\phantom{0{,}00}0\cr
\noalign{\smallskip}
	&\phantom{{}=0{,}000}\llap{$\PJ\ge0,\quad\SJ\ge0,\quad\PW\ge0,\quad\SW\ge0$}.\cr
}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
