Optimisation Models

A variant of a mathematical model is the optimization problem. In this case, we are not interested in any or all feasible solution, but only those solutions that maximize (or minimize) a function f(x) (in analogy of the house choosing problem: we want the “best” house only):

Y = {max  f(x ) | x ∈ X ∧  R(x )}

Example 6: A trivial example is maximizing a parable in the whole real 1-dimensional space:

                        2        def
x ∈ ℝ , f (x ) = - (x - 1) , R(x )=  (true)

The solution is x = 1, because the parable has a maximum at x = 1 where f(x) = 0 (for all other x the function value f(x) is smaller than 0 (try it out!).

Example 7:

Now let us construct a real but easy problem. Answer the following question “What is the height and the width of a cylindric aluminium can that contains a volume of 1 liter (dm3), such that the quantity of material to build the can is as small as possible?”

Supposing that the material has identical thickness on its surface, we may substitute “quantity of material” by “surface of the cylinder”. Given the height h and the diameter 2r of a cylinder, its volume is given as follows (which must be 1):

         2
V  = πhr  =  1

The surface O of the cylinder is then as follows (two circles and a cylinder coat):

O = 2 πr2 + 2πrh

We need to minimize the surface O (which we suppose to be proportional to the material usage, as already mentioned). Hence, the model is as follows:

                            def                     def
x =  (r,h ) ∈ ℝ2+ , min f (x) =  2πr2 + 2πrh ,  R (x) = (πhr2  = 1)

One can also simplify the model by eliminating the variable h. We then get the model:

O  = 2πr2 +  2-
             r

where O must be minimal.


PIC

Figure 6: Solution of the can problem

This is a minimization problem with one variable and no constraint. The solution is given in Figure 6. The minimal usage of material to construct a cylindric can that contains a volume of 1 liter has a radius of 5.42cm and a height of 10.9cm, and the surface is 554cm2. Any other size has a larger surface, check it!

Another way to express the can problem – with two variables – is as follows:

               2
min         2πr  + 2πrh
subject to  πhr2 =  1
            r,h ≥ 0

Basically, every mathematical model is like our house choosing problem, only the size of the state space change and the requirements are expressed in a mathematical notation. At this point, I could introduce a really powerful concept to formulate large and complex mathematical models, that is, models with many variables and constraints. This concept is called indexing. Since it is a so important and powerful notation, I wrote a separate paper for that (see [9]). If you want to get a pro in mathematical modeling, these concepts are a must!

A historical note: The concepts of the mathematical model are historically recent ones. According to Tarski, “the invention of variables constitutes a turning point in the history of mathematics.” Greek mathematicians used them rarely and in an ad hoc way. Vieta (1540-1603) was the first who made use of variables on a systematic way. He introduced vowels to represent variables and consonants to represent known quantities (parameters). “Only at the end of the 19th century, however, when the notion of a quantifier had become firmly established, was the role of variables in scientific language and especially in the formulation of mathematical theorems fully recognized” [1] p.12.