Optimization modelMany 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.
The quarry is divided into more or less homogeneous blocks:
Block model of a quarry
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 .. .. .. .. ..
The goal is to maximize the profit
g = c1x1 + c2x2 + ...by taking
x1 tons from the block B1,and satisfying all constraints that follow below.
x2 tons from the block B2,
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
Rmin ≤ r1x1 + r2x2 + ... ≤ Rmax x1 + x2 + ...
(r1 - Rmin) x1 + (r2 - Rmin) x2 + ... ≥ 0Corresponding inequalities are added for further chemicals.
(r1 - Rmax) x1 + (r2 - Rmax) x2 + ... ≤ 0
The taken tonnages must satisfy the obvious constraints:
x1 ≥ 0
x2 ≥ 0
x1 ≤ B1
x2 ≤ B2
The company has only a limited production capacity Tmax:
x1 + x2 + ... ≤ Tmax
Two-dimensional caseWe 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
Graphical solution (Picture creation)
6x1 + 2x2 = mparametrized 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
Solution with Microsoft ExcelMicrosoft 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 AlgorithmSimplex 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.