\pdfpagewidth=8.5truein  \pdfpageheight=11truein
\hsize=5.5truein  \vsize=9truein
\pdfhorigin=1.5truein  \pdfvorigin=1truein

\font\smfont=cmr8

\newcount\pno \pno=0
\def\problem#1{\global\advance\pno by1%
	\medskip\filbreak\noindent{\llap{\bf\the\pno.\enspace}}{\bf#1.\enspace}\ignorespaces}

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

\centerline{\bf IP formulation examples}
\centerline{June~24, 2015}

\medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{Machine shop reopening} A small machine shop is reopening after a fire
had forced it to close for extensive repairs. The shop has three product lines:
plates, gears, and housings. Each product line requires specialized equipment,
and because of inactivity and possible damage all equipment must be serviced
before it is used.

The shop plans to open on a limited basis for the first two weeks, employing
only three workers, each for 40~hours per week. It has available 2800 units of
metal and can purchase additional metal for \$2~per unit. The per-unit labor,
metal, overhead costs, and selling prices for their products are shown below.
$$\vbox{\offinterlineskip
\halign{\enspace\strut#\hfil\enspace&&\enspace\hfil\strut#\hfil\enspace\cr
&Labor&Metal&Overhead&Selling price\cr
&(minutes)&(units)&(dollars)&(dollars)\cr
\noalign{\vskip2pt\hrule\vskip2pt}
Plates&10&4&6&24\cr
Gears&30&1&9&32\cr
Housings&20&6&8&30\cr}}$$

The existing backlog of orders for gears includes mostly orders for large
quantities. Therefore, management does not believe that it would be useful to
make gears during the first two weeks unless the shop can produce at least 200
of them.

The servicing costs are \$600 for the plate equipment, \$900 for the gear
equipment, and \$700 for the housing equipment. The shop does not expect to use
all equipment in the first two weeks.

Management has \$2000 remaining from its fire insurance settlement, and plans
to spend that sum on the necessary service and possibly additional metal stock.
The large backlog of orders that accumulated while the shop was closed
indicates that they can sell any products they make. The overhead is charged
against the selling price.

Management's goal for the first two weeks is to maximize the profit so that
they can afford to reopen full operations as quickly as possible.

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

\problem{Utility connections} Five major electrical consumers A,~B, C, D, and~E
(e.g., manufacturing plants, hospitals, and housing developments) are to be
added in a region served by three power plants X,~Y, and~Z. The connection
costs to the new consumers (in millions of dollars) are given in the table
below. The objective is to connect the new consumers to the generating plants
in the most economical way possible.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&A&B&C&D&E\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
X&&2&2&3&1&8\cr
Y&&3&7&2&6&4\cr
Z&&5&4&4&3&6\cr}}$$

The needs of the new consumers are 12,~10, 15, 16, and~15, respectively. The
available capacities of the generating plants are 40,~32, and~30, respectively.

Two of the new consumers, A~and~B, are hospitals. In order to lessen the
possibility that both hospitals could be without power simultaneously, they
cannot both be connected to the same power plant.

Determine which new consumers should be connected to which power plant in order
to minimize the connection costs.

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

\problem{Product introduction} Esquire Products will produce four new product
lines in the next month. The respective per-unit profits on the lines are
\$200,~\$220, \$185, and~\$190. They are basically testing the market and do
not wish to produce more than 700 of any one line. The respective fixed
start-up costs for the products are \$4000,~\$5000, \$3000, and~\$3500. Each
item produced will require a part called an autorhombulator. The supplier of
the autorhombulators charges according to the following schedule:
$$\cases{
	\$50&\hbox{ordering charge},\cr
	\phantom0\$9&\hbox{each for the first 100~units},\cr
	\phantom0\$6&\hbox{each for all additional units}.\cr
}$$
Esquire has budgeted \$20,500 for the start-up costs and the purchase of the
autorhombulators. Product lines 1~and~2 require a half hour of production time
per item while lines 3~and~4 require 0.4~hour per item. There will be 800~hours
of production time available during the month. How many of each line should
they produce in order to maximize their profit?

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

\problem{Boolean satisfiability} Determine truth values for the Boolean
variables $x_1$,~$x_2$, and~$x_3$ so that the propositional formula
$$(x_1\lor\bar x_2)\land(\bar x_2\lor\bar x_3)\land(x_1\lor x_2\lor\bar x_3)
	\land(\bar x_1\lor x_3)$$
is satisfied (i.e., evaluates to true), or determine that the formula is
unsatisfiable. Here $\land$~denotes {\smfont AND}, $\lor$~denotes {\smfont OR},
and $\bar x_i$~denotes {\smfont NOT}~$x_i$.

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

\bye