Micro Processor

So far we have avoided the problem of defining exactly what OR is. In order to get a clearer idea of what OR is we shall actually do some by considering the specific problem below and then highlight some general lessons and concepts from this specific example.
Two Mines Company

The Two Mines Company own two different mines that produce an ore which, after being crushed, is graded into three classes: high, medium and low-grade. The company has contracted to provide a smelting plant with 12 tons of high-grade, 8 tons of medium-grade and 24 tons of low-grade ore per week. The two mines have different operating characteristics as detailed below.

Mine Cost per day (£'000) Production (tons/day)
High Medium Low
X 180 6 3 4
Y 160 1 1 6

How many days per week should each mine be operated to fulfil the smelting plant contract?

Note: this is clearly a very simple (even simplistic) example but, as with many things, we have to start at a simple level in order to progress to a more complicated level.

Guessing

To explore the Two Mines problem further we might simply guess (i.e. use our judgement) how many days per week to work and see how they turn out.

* work one day a week on X, one day a week on Y

This does not seem like a good guess as it results in only 7 tonnes a week of high-grade, insufficient to meet the contract requirement for 12 tonnes of high-grade a week. We say that such a solution is infeasible.

* work 4 days a week on X, 3 days a week on Y

This seems like a better guess as it results in sufficient ore to meet the contract. We say that such a solution is feasible. However it is quite expensive (costly).

Rather than continue guessing we can approach the problem in a structured logical fashion as below. Reflect for a moment though that really we would like a solution which supplies what is necessary under the contract at minimum cost. Logically such a minimum cost solution to this decision problem must exist. However even if we keep guessing we can never be sure whether we have found this minimum cost solution or not. Fortunately our structured approach will enable us to find the minimum cost solution.

Two Mines solution

What we have is a verbal description of the Two Mines problem. What we need to do is to translate that verbal description into an equivalent mathematical description.

In dealing with problems of this kind we often do best to consider them in the order:

1. variables
2. constraints
3. objective.

We do this below and note here that this process is often called formulating the problem (or more strictly formulating a mathematical representation of the problem).

(1) Variables

These represent the "decisions that have to be made" or the "unknowns".

Let

x = number of days per week mine X is operated
y = number of days per week mine Y is operated

Note here that x >= 0 and y >= 0.

(2) Constraints

It is best to first put each constraint into words and then express it in a mathematical form.

* ore production constraints - balance the amount produced with the quantity required under the smelting plant contract

Ore
High 6x + 1y >= 12
Medium 3x + 1y >= 8
Low 4x + 6y >= 24

Note we have an inequality here rather than an equality. This implies that we may produce more of some grade of ore than we need. In fact we have the general rule: given a choice between an equality and an inequality choose the inequality.

For example - if we choose an equality for the ore production constraints we have the three equations 6x+y=12, 3x+y=8 and 4x+6y=24 and there are no values of x and y which satisfy all three equations (the problem is therefore said to be "over-constrained"). For example the (unique) values of x and y which satisfy 6x+y=12 and 3x+y=8 are x=4/3 and y=4, but these values do not satisfy 4x+6y=24.

The reason for this general rule is that choosing an inequality rather than an equality gives us more flexibility in optimising (maximising or minimising) the objective (deciding values for the decision variables that optimise the objective).

* days per week constraint - we cannot work more than a certain maximum number of days a week e.g. for a 5 day week we have

x <= 5
y <= 5

Constraints of this type are often called implicit constraints because they are implicit in the definition of the variables.

(3) Objective

Again in words our objective is (presumably) to minimise cost which is given by 180x + 160y

Hence we have the complete mathematical representation of the problem as:

minimise
180x + 160y
subject to
6x + y >= 12
3x + y >= 8
4x + 6y >= 24
x <= 5
y <= 5
x,y >= 0

There are a number of points to note here:

* a key issue behind formulation is that IT MAKES YOU THINK. Even if you never do anything with the mathematics this process of trying to think clearly and logically about a problem can be very valuable.

* a common problem with formulation is to overlook some constraints or variables and the entire formulation process should be regarded as an iterative one (iterating back and forth between variables/constraints/objective until we are satisfied).

* the mathematical problem given above has the form
o all variables continuous (i.e. can take fractional values)
o a single objective (maximise or minimise)
o the objective and constraints are linear i.e. any term is either a constant or a constant multiplied by an unknown (e.g. 24, 4x, 6y are linear terms but xy is a non-linear term).
o any formulation which satisfies these three conditions is called a linear program (LP). As we shall see later LP's are important..Finally in 1971 the team of Ted Hoff, S. Mazor and F. Fagin develops the Intel
4004 microprocessor a “computer on a chip”. This 4004, is the world’s first
commercially available microprocessor. This breakthrough invention powered the
Busicom calculator and paved the way for embedding intelligence in inanimate objects as
well as the personal computer. Just four years later, in 1975, Fortune magazine said, “The
microprocessor is one of those rare innovations that simultaneously cuts manufacturing
costs and ads to the value and capabilities of the product. As a result, the microprocessor
has invaded a host of existing products and created new products never before possible.”
This single invention revolutionized the way computers are designed and applied.
It put intelligence into “dumb” machines and distributed processing capability into
previously undreamed applications. The advent of intelligent machines based on
microprocessors changed how we gather information, how we communicate, and how
and where we work.
In mid-1969 Busicom, a now-defunct Japanese calculator manufacturer, asked
Intel to design a set of chips for a family of high-performance programmable calculators.
Maracian E. “Ted” Hoff, an engineer who had joined Intel the previous year was
assigned to the project. In its original design, the calculator required twelve chips, which
Hoff considered to complex to be cost-effective. Furthermore, Intel’s small MOS staff
was fully occupied with the 1101 (MOS type of static semiconductor memory) so the
design resources were not available. Hoff came up with a novel alternative: by reducing
the complexity of the instructions and providing a supporting memory device, he could
create a general-purpose information processor. The processor, he reasoned, could find a
wide array of uses for which it could be modified by programs stored in memory.
“Instead of making their device act like a calculator,” he recalled, “I wanted to make it
function as a general purpose computer programmed to be a calculator.”
To this end, Hoff and fellow engineers Federico Faggin and Stan Mazor came up
with a design that involved four chips: a central processing unit (CPU) chip, a read-only
memory (ROM) chip for the custom application programs, a random access memory
(RAM) chip for processing data, and a shift register chip for input/output (I/O) port. The
CPU chip, though it then had no name, would eventually be called a microprocessor.
Measuring one-eighth of an inch wide by one-sixth of an inch long and made up of 2,300
MOS transistors, Intel’s first microprocessor is equal in computing power to the first
standards is primitive. It works at a clock rate of 108 KHz.The 8-bit 8008 microprocessor had been developed in tandem with the 4004 and
was introduced in April 1972. It was intended to be a custom chip for Computer
Terminals Corp. of Texas. But as it developed, CTC rejected the 8008 because it was too
slow for the company’s purpose and required too many supporting chips. However, Intel
offered the 8008 on the open market, where its orientation to data/character manipulation
versus the 4004’s arithmetic orientation caught the eye of a new group of users. The 8008
is made up of 3,500 MOS transistors and could work at a clock rate of 200 KHz.It soon became obvious to Intel and its competitors that there were almost
limitless number of applications for microprocessors. A big advance came in 1974 with
Intel’s 8080 chip, the first true general purpose microprocessor. It is much more highly
integrated chip than its predecessors, with about 10 times the performance. It could
execute about 290,000 operations a second and could address 64K bytes of memory.
Both the 4004 and 8008 utilized the P-channel MOS technology, whereas the 8080 used
the innovative N-channel MOS process yielding vast gains in speed, power, capacity and
density. What’s more the 8080 required only 6 support chips for operation as opposed to
20 with the 8008. It consisted of 60,000 transistors and worked at clock rate of 2 MHz.