Information Technology
DE | ENContact

Optimization model

Many quantitative decision tasks in economy and industry lead naturally to optimization problems. A broad category of practically tractable problems are linear optimization problems where the goal function and the constraints depend linearly on the decision variables. Let us illustrate the linear optimization (also called linear programming) on an example from the mining industry.

A mining company extracts rock or minerals from an open pit (quarry), mixes them to achieve the required quality and sells the blend on the market. The company wants obviously achieve a maximum profit under the constraints given by the quarry composition, the mix, production costs and capacity. The situation can be modeled mathematically as follows.

  1. The quarry is divided into more or less homogeneous blocks:

    Block Model

    Block model of a quarry

  2. The mineral concentration, the weight, the production cost and other properties of the blocks are measured or estimated:

    Block Tonnage Profit c/ton R % S % ..
    B1 20 6 15 .. ..
    B2 10 2 35 .. ..
    B3 .. .. .. .. ..

    Quarry data

  3. The goal is to maximize the profit

    g = c1x1 + c2x2 + ...

    by taking

    x1 tons from the block B1,
    x2 tons from the block B2,
    ...

    and satisfying all constraints that follow below.
  4. The concentration of the chemicals in the blend must lay between specified limits:
    Chemical Min % Max %
    R 20 25
    S .. ..
    .. .. ..

    Requirements on the chemical mix

    This means for the chemical R:
    Rmin   ≤ r1x1 + r2x2 + ... ≤   Rmax
    x1 + x2 + ...
    This is reformulated as two inequalities:

    (r1  -  Rmin) x1 + (r2  -  Rmin) x2 + ...   ≥   0
    (r1  -  Rmax) x1 + (r2  -  Rmax) x2 + ...   ≤   0

    Corresponding inequalities are added for further chemicals.
  5. The taken tonnages must satisfy the obvious constraints:

    x1   ≥   0
    x2   ≥   0
    ...
    x1   ≤   B1
    x2   ≤   B2
    ...

  6. The company has only a limited production capacity Tmax:

    x1  +  x2 + ...   ≤   Tmax

Two-dimensional case

We will now solve the problem in the simplified case of 2 blocks only. We assume that the maximum production capacity is Tmax = 25 tons. The task is then: Find the variables x1, x2 such that the profit

g = 6x1 + 2x2 = max !

is maximal and the constraints:

-5x1 + 15x2   ≥   0
-10x1 + 10x2   ≤   0
x1   ≥   0
x2   ≥   0
x1   ≤   20
x2   ≤   10
x1  +  x2   ≤   25

are satisfied. This kind of problems are called linear optimization problems because the function to be optimized and all restrictions are linear functions in the variables x. Treatment of these problems and the corresponding solution methods is also called - for historical reasons - linear programming.

Graphical solution

In the case of 2 variables the problem can be solved graphically in the (x1, x2)-plane.
Graphical Solution

Graphical solution (Picture creation)

The inequalities correspond to half-planes bounded by the constraint equations (inequality replaced by equality). The intersection of these half-planes is a convex polygon called the "feasible region". The points of the feasible region satisfy all constraints. The goal corresponds to a family of parallel lines

6x1 + 2x2 = m

parametrized by the value of m. When this line is moved to the right, the value m of the goal is increased and it achieves the maximum 125 at the right most corner (18.75, 6.25) of the feasible region. So, the optimal solution is

x1 = 18.75
x2 = 6.25
Profit = 125

The graphical solution method provides an excellent insight into the structure of linear optimization problems. Even if we cannot use it directly in higher dimensions, we can imagine how it would work. Constraints correspond to half-spaces bounded by hyperplanes. The feasible region, which is the intersection of half-spaces, is a convex polyhedron. The goal is a hyperplane that must be moved to that vertex of the polyhedron where its value is maximal.

Solution with Microsoft Excel

Microsoft Excel provides the add-on "Solver" that allows to solve optimization problems numerically. The application of Excel Solver to our two-dimensional example is easy. However, the Solver becomes impractical and error-prone for real-world large scale problems.

Simplex Algorithm

Simplex Algorithm (PDF) is the method of choice for linear optimization of real-world large scale problems. This method was devised by G. B. Dantzig in 1947. My implementation of the Simplex Algorithm in C++ can handle thousands of variables and constraints, is numerically stable and computes the solution very efficiently.