Linear Optimization

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.

Optimization Model

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.

Discretization

The quarry is divided into more or less homogeneous blocks:

Data

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

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

Quarry data

Maximum function

The goal is to maximize the profit

by taking

x₁ tons from the block B₁,
x₂ tons from the block B₂,
...

and satisfying all constraints that follow below.

Requirements on the blend

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:

This is reformulated as two inequalities:

Corresponding inequalities are added for further chemicals.

Natural constraints on the tonnage

The taken tonnages must satisfy the obvious constraints:

Limited production capacity

The company has only a limited production capacity T_max:

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 T_max = 25 tons. The task is then: Find the variables x₁, x₂ such that the profit

is maximal and the constraints:

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 (x₁, x₂)-plane.

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

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

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 (PDF) 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.