Quantitative Methods in Decision Making
Every manager is exposed to a number of decision situations and problems in
his everyday work which he can analyze from two points of view:
either based on knowledge and experience (qualitative analysis)
or using data in numerical form and mathematically processing it
(quantitative analysis),
Quantitative Methods in Decision Making
Every manager is exposed to a number of decision situations and problems in
his everyday work which he can analyze from two points of view:
either based on knowledge and experience (qualitative analysis)
or using data in numerical form and mathematically processing it
(quantitative analysis),
In certain situations, of course, only one of these analyzes can be performed.
However, if the manager uses only the qualitative analysis without numerical
calculations, the outcome depends to a large extent on the his good
judgment. Conversely, too much conﬁdence in numerical results can be
misleading: each numerical solution is accurate only if the model was well
constructed. In addition, a quantitative analysis of a problem can be lengthy
and inefﬁcient when a decision needs to be taken quickly.
Quantitative Methods in Decision Making
So in what situations are quantitative methods suitable?
Quantitative Methods in Decision Making
So in what situations are quantitative methods suitable? Speciﬁcally, if the
problem is:
complex and using simulating reality by a suitable model can help the
manager
very important or connected with very high costs
new and the decision-maker is lacking experience of solving similar
problems
repeated; using good quantitative procedures saves both time and
resources
The art of modeling
By a model we mean a certain representation of a real system. It is never a
perfect picture of reality (it is not possible and neither is it desirable). A
properly designed model should only capture those features that are
important to solve the problem. If we include all the details in the model, it will
be too complex, possibly unsolvable and confusing. On the other hand, if
there is too much effort to simplify the model, some important facts and links
may be omitted. In modeling it is crucial to choose the right relationship
between the real world and the model.
The art of modeling
By a model we mean a certain representation of a real system. It is never a
perfect picture of reality (it is not possible and neither is it desirable). A
properly designed model should only capture those features that are
important to solve the problem. If we include all the details in the model, it will
be too complex, possibly unsolvable and confusing. On the other hand, if
there is too much effort to simplify the model, some important facts and links
may be omitted. In modeling it is crucial to choose the right relationship
between the real world and the model. The problem should be well formulated
so that quantitative methods can be used to solve it and its results should be
interpreted and implemented. Experts or specialized software can help solve
the mathematical model. Even with the use of computer technology, however,
it is advisable to be familiar with the available methods so that in a particular
situation we can choose the appropriate algorithm and set its parameters.
Phases of modeling
Most of the process is based on teamwork and good communication.
Problem deﬁnition
Construction of the model - expressing the deﬁned problem by means of
mathematical relationships
Model solution - using exact or heuristic optimization algorithms or
simulations. (plus sensitivity analysis if we are not sure about the exact
values of the parameters involved in the model)
Model validation (Does the solution make sense? Are the results
acceptable? )
Solution implementation - translation into operating instructions
Optimization
When optimizing, we try to choose the "best solution"among all "possible
solutions". In a particular problem, these terms must be speciﬁed exactly.
Futhermore we will describe all possible solutions using the set of M , which
we call a feasible region or feasible set, and we will express the quality of the
solution through the function f : M → R which is called the goal or the
objective function. The formulation of the optimization problem follows:
Find x∗
∈ M such that: f(x∗
) ≥ f(x), ∀x ∈ M,
Optimization
When optimizing, we try to choose the "best solution"among all "possible
solutions". In a particular problem, these terms must be speciﬁed exactly.
Futhermore we will describe all possible solutions using the set of M , which
we call a feasible region or feasible set, and we will express the quality of the
solution through the function f : M → R which is called the goal or the
objective function. The formulation of the optimization problem follows:
Find x∗
∈ M such that: f(x∗
) ≥ f(x), ∀x ∈ M,
Comment: A maximization problem "f → max"is easily transformable into a
minimization problem "−f → min".
Optimization
When optimizing, we try to choose the "best solution"among all "possible
solutions". In a particular problem, these terms must be speciﬁed exactly.
Futhermore we will describe all possible solutions using the set of M , which
we call a feasible region or feasible set, and we will express the quality of the
solution through the function f : M → R which is called the goal or the
objective function. The formulation of the optimization problem follows:
Find x∗
∈ M such that: f(x∗
) ≥ f(x), ∀x ∈ M,
Comment: A maximization problem "f → max"is easily transformable into a
minimization problem "−f → min".
Some applications:
Optimization
When optimizing, we try to choose the "best solution"among all "possible
solutions". In a particular problem, these terms must be speciﬁed exactly.
Futhermore we will describe all possible solutions using the set of M , which
we call a feasible region or feasible set, and we will express the quality of the
solution through the function f : M → R which is called the goal or the
objective function. The formulation of the optimization problem follows:
Find x∗
∈ M such that: f(x∗
) ≥ f(x), ∀x ∈ M,
Comment: A maximization problem "f → max"is easily transformable into a
minimization problem "−f → min".
Some applications:
Proﬁt maximization (optimal product mix)
Portfolio optimization
Scheduling
Minimization of transportation costs, optimal routes and location of
distribution centers
Project management (minimal time, costs,...)
Inventory management
Classiﬁcation of optimization problems
There are two types of optimization problems with respect to the feasible set:
If any point x in Euclidean space Rn
is feasible, i.e. M = Rn
, we use the
term unconstrained optimization. The procedure of an analytical solution
of such problems is tought on the basic mathematics course
Otherwise, if M ⊂ Rn
, we talk about constrained optimization. The
existence of the solution for optimizing continuous functions on a
bounded closed set is guaranteed by the Weierstrass theorem.
An analytical solution is not always easy to ﬁnd (for example, when there are
too many variables or a complicated shape of the feasible set, or there are
nonlinear functions involved, etc.). Therefore, special methods have been
developed to solve certain types of optimization problems.
Mathematical programming
The term mathematical programming refers to a set of methods used to
optimize a criterion expressed as a function of n variables while meeting the
constraining conditions generally expressed in the form of equalities and
inequalities. The mathematical programming can be divided into:
linear programming (LP) for problems where both the objective function
and the constraints are expressed by means of linear functions of the
variables
nonlinear programming (NLP) when the above mentioned conditions are
not met. A special case of NLP is quadratic programming for problems
with the objective function in the form of the second degree polynomial
and linear constraints.
Mathematical programming
The term mathematical programming refers to a set of methods used to
optimize a criterion expressed as a function of n variables while meeting the
constraining conditions generally expressed in the form of equalities and
inequalities. The mathematical programming can be divided into:
linear programming (LP) for problems where both the objective function
and the constraints are expressed by means of linear functions of the
variables
nonlinear programming (NLP) when the above mentioned conditions are
not met. A special case of NLP is quadratic programming for problems
with the objective function in the form of the second degree polynomial
and linear constraints.
We will focus on LP models which are the most widespread. A lot of real
problems can be well formulated as an LP problem and software is available
for their effective solution. In practice, we can encounter non-linear
relationships (e.g. non-proportionality: if the price is not constant, then the
income is not proportional to the quantity sold, non-additivity: the synergy
effect, etc.), but due to the enormously greater complexity of NLP procedures,
it is often preferable to use an approximation by a linear model.
Linear programming
When formulating the mathematical programming problem it is necessary to
start from a well-described economic model.
Linear programming
When formulating the mathematical programming problem it is necessary to
start from a well-described economic model. It is therefore necessary to know:
what we want to achieve (so we have to choose the criterion: proﬁt or
cost or the volume of production etc., and determine whether we will try
to minimize or maximize it)
controllable inputs, i.e. which variables we can inﬂuence in order to
achieve the goal (the number of produced pieces of different types in
production problems, the load of the vehicles in transportation problems,
etc.)
uncontrollable inputs or constraints that limit us (prices of purchased raw
materials, disposition of resources, capacity of the device, etc.)
LP problem - Optimization of production mix
Further explanations will be illustrated by the following example from Josef
Jablonský: "Operations Research, Quantitative Models for Economic Decision
Making":
Example : Management of a company for coffee roasting and packing plan
the production of two blends - Mocca and Standard. Suppliers have three
types of coffee beans K1, K2 and K3 available at 40, 60 and 25 tons
respectivelly. The technological procedure determining the mixture
composition is summarized in the table.
Mocca Standard Capacity [t]
K1 0,5 0,25 40
K2 0,5 0,5 60
K3 0,25 25
Due to the production costs and the price of the blends, a proﬁt of CZK 20,000
or CZK 14,000 per tonne of mixture it Mocca or it Standard respectivelly was
calculated. The company’s management looks for the production mix which
will maximize the proﬁt.
Optimization of the production mix - problem
formulation
If we denote the amount of Mocca by x1 blend and the amount of Standard
blend x2, we can formulate the problem mathematically as a maximization
problem with an objective function:
z = 20000x1 + 14000x2
subject to the constraints
0, 5x1 + 0, 25x2 ≤ 40
0, 5x1 + 0, 5x2 ≤ 60
0, 25x2 ≤ 25
x1, x2 ≥ 0
Optimization of the production mix - problem
formulation
If we denote the amount of Mocca by x1 blend and the amount of Standard
blend x2, we can formulate the problem mathematically as a maximization
problem with an objective function:
z = 20000x1 + 14000x2
subject to the constraints
0, 5x1 + 0, 25x2 ≤ 40
0, 5x1 + 0, 5x2 ≤ 60
0, 25x2 ≤ 25
x1, x2 ≥ 0
We can also use a matrix formulation:
z = c · x → max subject to A · x ≤ b, x ≥ 0,
where x = (x1, x2) is a vector of the decision variables, c = (20, 14) is a
price vector, b = (40, 60, 25) is a vector of capacities and
A =


0,5 0,25
0,5 0,5
0 0,25

 is a technology matrix (structural coefﬁcients).
Mathematical formulation of a generic LP problem
A generic LP problem with n variables and m constraints can be formulated as
follows:
minimize (or maximize) function
z =
n
j=1 cj xj
subject to
n
j=1 aij xj ? bi , i = 1, . . . m
xj ≥ 0, j = 1, . . . n,
where the symbol „? „ represents any of the relationships ≤, =, ≥. Restrictions
are presented in such a way that the right sides of bi are non-negative.
Mathematical formulation of a generic LP problem
A generic LP problem with n variables and m constraints can be formulated as
follows:
minimize (or maximize) function
z =
n
j=1 cj xj
subject to
n
j=1 aij xj ? bi , i = 1, . . . m
xj ≥ 0, j = 1, . . . n,
where the symbol „? „ represents any of the relationships ≤, =, ≥. Restrictions
are presented in such a way that the right sides of bi are non-negative.
One problem can be formulated in many different ways. You can easily
convert a minimization problem to a maximization problem with
−z =
n
j=1(−cj )xj . Equality restrictions can be rewritten as two inequalities of
≤ and ≥ with the same coefﬁcients on both sides as in the original equation.
Conversion of the inequality constraint to the equality is possible by
introducing additional variables, as will be shown later.
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Because of the non-negativity of the variables, we are limited to the ﬁrst
quadrant only. Here we will illustrate the halfplane formed by the points
fulﬁlling the ﬁrst limiting condition.
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
We also show a halfplane formed by the points fulﬁlling the second limiting
condition.
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Next we show a halfplane formed by the points fulﬁlling the third limiting
condition.
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Feasible region M consists of the points satisfying all three constraints.
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Contour line of objective function z = 20000x1 + 14000x2 = 0
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Contour line of objective function z = 20000x1 + 14000x2 = 350000
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Contour line of objective function z = 20000x1 + 14000x2 = 700000
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Contour line of objective function z = 20000x1 + 14000x2 = 1050000
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
Contour line of objective function z = 20000x1 + 14000x2 = 1920000
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
The contour of the highest value touches M at x∗
Graphical solution of an LP problem
Two dimensional problems can be solved graphically. Let’s show it on our
coffee problem.
The point x∗
= [40, 80] is an optimal solution.
Fundamental theorem of linear programming
Feasible region M is given by the obligatory (non-negativity) conditions and
constraints A · x ≤ b. We can formulate them as equalities:
0, 5x1 + 0, 25x2 + x3 = 40
0, 5x1 + 0, 5x2 + x4 = 60
0, 25x2 + x5 = 25
Fundamental theorem of linear programming
Feasible region M is given by the obligatory (non-negativity) conditions and
constraints A · x ≤ b. We can formulate them as equalities:
0, 5x1 + 0, 25x2 + x3 = 40
0, 5x1 + 0, 5x2 + x4 = 60
0, 25x2 + x5 = 25
Variables x3, x4 and x5 are called slacks and can be interpreted economically
as unused capacity of raw materials.
Fundamental theorem of linear programming
Feasible region M is given by the obligatory (non-negativity) conditions and
constraints A · x ≤ b. We can formulate them as equalities:
0, 5x1 + 0, 25x2 + x3 = 40
0, 5x1 + 0, 5x2 + x4 = 60
0, 25x2 + x5 = 25
Variables x3, x4 and x5 are called slacks and can be interpreted economically
as unused capacity of raw materials. The system consists of m equations of
m + n variables and it can have an inﬁnite number of solutions. The solution
with n variables of zero value is called basic. (In 2D problems, the basic
solutions correspond to the intersections of the boundary lines of the
individual inequalities) We denote the non-zero variables as basic and zero as
nonbasic.
Fundamental theorem of linear programming
Feasible region M is given by the obligatory (non-negativity) conditions and
constraints A · x ≤ b. We can formulate them as equalities:
0, 5x1 + 0, 25x2 + x3 = 40
0, 5x1 + 0, 5x2 + x4 = 60
0, 25x2 + x5 = 25
Variables x3, x4 and x5 are called slacks and can be interpreted economically
as unused capacity of raw materials. The system consists of m equations of
m + n variables and it can have an inﬁnite number of solutions. The solution
with n variables of zero value is called basic. (In 2D problems, the basic
solutions correspond to the intersections of the boundary lines of the
individual inequalities) We denote the non-zero variables as basic and zero as
nonbasic.
Caution! Not every basic solution is feasible. The feasible basic solutions
correspond to the "corner points"of M. In our example, m = 3, n = 2, so we
will get ? basic solutions and ? of them is feasible.
Fundamental theorem of linear programming
Feasible region M is given by the obligatory (non-negativity) conditions and
constraints A · x ≤ b. We can formulate them as equalities:
0, 5x1 + 0, 25x2 + x3 = 40
0, 5x1 + 0, 5x2 + x4 = 60
0, 25x2 + x5 = 25
Variables x3, x4 and x5 are called slacks and can be interpreted economically
as unused capacity of raw materials. The system consists of m equations of
m + n variables and it can have an inﬁnite number of solutions. The solution
with n variables of zero value is called basic. (In 2D problems, the basic
solutions correspond to the intersections of the boundary lines of the
individual inequalities) We denote the non-zero variables as basic and zero as
nonbasic.
Caution! Not every basic solution is feasible. The feasible basic solutions
correspond to the "corner points"of M. In our example, m = 3, n = 2, so we
will get ? basic solutions and ? of them is feasible.
Fundamental theorem of linear programming: If the problem has an optimal
solution, then it also has an optimal basic solution.
Simplex tableau
We can use a matrix notation of the system (A, I) · (x1, x2, x3, x4, x5) = b,
where I is an identity matrix of the size m = 3. Every such system of m
equations of m + n unknowns, where the matrix on the left side contains all
the columns of the identity matrix, is called a system in the canonical form.
Simplex tableau
We can use a matrix notation of the system (A, I) · (x1, x2, x3, x4, x5) = b,
where I is an identity matrix of the size m = 3. Every such system of m
equations of m + n unknowns, where the matrix on the left side contains all
the columns of the identity matrix, is called a system in the canonical form.
We can easily ﬁnd at least one solution of such a system:
x1 = 0, x2 = 0, x3 = b1 = 40, x4 = b2 = 60, x5 = b3 = 25. This is even a
basic solution. Let’s summarize everything in a table:
basic var. x1 x2 x3 x4 x5 bi
x3
1
2
1
4 1 0 0 40
x4
1
2
1
2 0 1 0 60
x5 0 1
4 0 0 1 25
zj −20 −14 0 0 0 0
Simplex tableau
We can use a matrix notation of the system (A, I) · (x1, x2, x3, x4, x5) = b,
where I is an identity matrix of the size m = 3. Every such system of m
equations of m + n unknowns, where the matrix on the left side contains all
the columns of the identity matrix, is called a system in the canonical form.
We can easily ﬁnd at least one solution of such a system:
x1 = 0, x2 = 0, x3 = b1 = 40, x4 = b2 = 60, x5 = b3 = 25. This is even a
basic solution. Let’s summarize everything in a table:
basic var. x1 x2 x3 x4 x5 bi
x3
1
2
1
4 1 0 0 40
x4
1
2
1
2 0 1 0 60
x5 0 1
4 0 0 1 25
zj −20 −14 0 0 0 0
The last row (zj ) corresponds to the coefﬁcients of the objective function in an
annulated shape. We converted the equation z = 20x1 + 14x2 [in thousands of
CZK] into z − 20x1 − 14x2 − 0x3 − 0x4 − 0x5 = 0. For the initial basic solution,
we get a zero value of the objective function z = 0 (see the lower right corner
of the table). We’ll call this scheme the initial simplex tableau of the problem.
Simplex method
The Simplex method is an iterative procedure to ﬁnd the optimal solution of an
LP problem. The ﬁrst step is to ﬁnd the initial basic solution. This step is
simple for problems containing only "≤“ inequalities because of the slacks.
For other types of problems we can start by solving the initial problem of
minimizing the auxiliary variables expressing the violation of the constraints
(the procedure is called the two-phase simplex method). In the next steps the
method iteratively calculates new basic solutions with better values for the
objective function. After a ﬁnite number of steps, a basic solution with the best
value of the objective function is found (according to the fundamental LP
theorem it is the optimal solution of the whole problem) or it is determined that
such a solution does not exist.
Simplex method
The Simplex method is an iterative procedure to ﬁnd the optimal solution of an
LP problem. The ﬁrst step is to ﬁnd the initial basic solution. This step is
simple for problems containing only "≤“ inequalities because of the slacks.
For other types of problems we can start by solving the initial problem of
minimizing the auxiliary variables expressing the violation of the constraints
(the procedure is called the two-phase simplex method). In the next steps the
method iteratively calculates new basic solutions with better values for the
objective function. After a ﬁnite number of steps, a basic solution with the best
value of the objective function is found (according to the fundamental LP
theorem it is the optimal solution of the whole problem) or it is determined that
such a solution does not exist. In the ﬁgure there is a schematic
representation of the procedure in 3D.
The feasible region
Simplex method
The Simplex method is an iterative procedure to ﬁnd the optimal solution of an
LP problem. The ﬁrst step is to ﬁnd the initial basic solution. This step is
simple for problems containing only "≤“ inequalities because of the slacks.
For other types of problems we can start by solving the initial problem of
minimizing the auxiliary variables expressing the violation of the constraints
(the procedure is called the two-phase simplex method). In the next steps the
method iteratively calculates new basic solutions with better values for the
objective function. After a ﬁnite number of steps, a basic solution with the best
value of the objective function is found (according to the fundamental LP
theorem it is the optimal solution of the whole problem) or it is determined that
such a solution does not exist. In the ﬁgure there is a schematic
representation of the procedure in 3D.
Initial basic solution
Simplex method
The Simplex method is an iterative procedure to ﬁnd the optimal solution of an
LP problem. The ﬁrst step is to ﬁnd the initial basic solution. This step is
simple for problems containing only "≤“ inequalities because of the slacks.
For other types of problems we can start by solving the initial problem of
minimizing the auxiliary variables expressing the violation of the constraints
(the procedure is called the two-phase simplex method). In the next steps the
method iteratively calculates new basic solutions with better values for the
objective function. After a ﬁnite number of steps, a basic solution with the best
value of the objective function is found (according to the fundamental LP
theorem it is the optimal solution of the whole problem) or it is determined that
such a solution does not exist. In the ﬁgure there is a schematic
representation of the procedure in 3D.
We move to an adjacent corner point with a better objective value.
Simplex method
The Simplex method is an iterative procedure to ﬁnd the optimal solution of an
LP problem. The ﬁrst step is to ﬁnd the initial basic solution. This step is
simple for problems containing only "≤“ inequalities because of the slacks.
For other types of problems we can start by solving the initial problem of
minimizing the auxiliary variables expressing the violation of the constraints
(the procedure is called the two-phase simplex method). In the next steps the
method iteratively calculates new basic solutions with better values for the
objective function. After a ﬁnite number of steps, a basic solution with the best
value of the objective function is found (according to the fundamental LP
theorem it is the optimal solution of the whole problem) or it is determined that
such a solution does not exist. In the ﬁgure there is a schematic
representation of the procedure in 3D.
We move to an adjacent corner point with a better objective value next time.
Simplex method
The Simplex method is an iterative procedure to ﬁnd the optimal solution of an
LP problem. The ﬁrst step is to ﬁnd the initial basic solution. This step is
simple for problems containing only "≤“ inequalities because of the slacks.
For other types of problems we can start by solving the initial problem of
minimizing the auxiliary variables expressing the violation of the constraints
(the procedure is called the two-phase simplex method). In the next steps the
method iteratively calculates new basic solutions with better values for the
objective function. After a ﬁnite number of steps, a basic solution with the best
value of the objective function is found (according to the fundamental LP
theorem it is the optimal solution of the whole problem) or it is determined that
such a solution does not exist. In the ﬁgure there is a schematic
representation of the procedure in 3D.
We move to an adjacent corner point with a better objective value again.
Simplex method
The Simplex method is an iterative procedure to ﬁnd the optimal solution of an
LP problem. The ﬁrst step is to ﬁnd the initial basic solution. This step is
simple for problems containing only "≤“ inequalities because of the slacks.
For other types of problems we can start by solving the initial problem of
minimizing the auxiliary variables expressing the violation of the constraints
(the procedure is called the two-phase simplex method). In the next steps the
method iteratively calculates new basic solutions with better values for the
objective function. After a ﬁnite number of steps, a basic solution with the best
value of the objective function is found (according to the fundamental LP
theorem it is the optimal solution of the whole problem) or it is determined that
such a solution does not exist. In the ﬁgure there is a schematic
representation of the procedure in 3D.
There is no better adjacent vertex, we have achieved the optimum.
Iteration step of the simplex method
Numbers zj in the bottom row of the simplex tableau are called reduced
prices. They express the rate of change in an objective function when
switching to a new basic solution. If a variable xk enters the base (so its value
grows from 0 to t > 0), the objective function value increases by ∆z = −t · zk .
Iteration step of the simplex method
Numbers zj in the bottom row of the simplex tableau are called reduced
prices. They express the rate of change in an objective function when
switching to a new basic solution. If a variable xk enters the base (so its value
grows from 0 to t > 0), the objective function value increases by ∆z = −t · zk .
We want this ∆z to be positive when maximizing, which means that zk has to
be negative. If all reduced prices are non-negative , the objective value
cannot be increased and the solution is optimal .
Iteration step of the simplex method
Numbers zj in the bottom row of the simplex tableau are called reduced
prices. They express the rate of change in an objective function when
switching to a new basic solution. If a variable xk enters the base (so its value
grows from 0 to t > 0), the objective function value increases by ∆z = −t · zk .
We want this ∆z to be positive when maximizing, which means that zk has to
be negative. If all reduced prices are non-negative , the objective value
cannot be increased and the solution is optimal . Else we choose xk with the
least value of zk ( this xk is called the entering variable) and substitute a basic
(leaving) variable with it.
Iteration step of the simplex method
Numbers zj in the bottom row of the simplex tableau are called reduced
prices. They express the rate of change in an objective function when
switching to a new basic solution. If a variable xk enters the base (so its value
grows from 0 to t > 0), the objective function value increases by ∆z = −t · zk .
We want this ∆z to be positive when maximizing, which means that zk has to
be negative. If all reduced prices are non-negative , the objective value
cannot be increased and the solution is optimal . Else we choose xk with the
least value of zk ( this xk is called the entering variable) and substitute a basic
(leaving) variable with it. For the simplex tableau
basic var. x1 x2 x3 x4 x5 βi
x3
1
2
1
4 1 0 0 40
x4
1
2
1
2 0 1 0 60
x5 0 1
4 0 0 1 25
zj −20 −14 0 0 0 0
we have an entering variable x1 because −20 is the lowest reduced price.
Iteration step of the simplex method
The choice of the leaving variable is based on the need to maintain the
feasibility of the solution, i.e. the non-negativity of all the basic variables. Let
us write this condition for the new values of the original basic variables
x3, x4, x5. If we set x1 = t, we get:
x3 = 40 − 1
2 t ≥ 0
x4 = 60 − 1
2 t ≥ 0
x5 = 25 − 0 ≥ 0
Obviously the largest such t is t = 80, for which we get x3 = 0. It now
becomes the leaving variable. We can upgrade the table using elementary
row operations to get number one in the upper left corner and zeros below it.
Iteration step of the simplex method
The choice of the leaving variable is based on the need to maintain the
feasibility of the solution, i.e. the non-negativity of all the basic variables. Let
us write this condition for the new values of the original basic variables
x3, x4, x5. If we set x1 = t, we get:
x3 = 40 − 1
2 t ≥ 0
x4 = 60 − 1
2 t ≥ 0
x5 = 25 − 0 ≥ 0
Obviously the largest such t is t = 80, for which we get x3 = 0. It now
becomes the leaving variable. We can upgrade the table using elementary
row operations to get number one in the upper left corner and zeros below it.
basic var. x1 x2 x3 x4 x5 βi
x3
1
2
1
4 1 0 0 40
x4
1
2
1
2 0 1 0 60
x5 0 1
4 0 0 1 25
zj −20 −14 0 0 0 0
We multiply the ﬁrst row by two.
Iteration step of the simplex method
The choice of the leaving variable is based on the need to maintain the
feasibility of the solution, i.e. the non-negativity of all the basic variables. Let
us write this condition for the new values of the original basic variables
x3, x4, x5. If we set x1 = t, we get:
x3 = 40 − 1
2 t ≥ 0
x4 = 60 − 1
2 t ≥ 0
x5 = 25 − 0 ≥ 0
Obviously the largest such t is t = 80, for which we get x3 = 0. It now
becomes the leaving variable. We can upgrade the table using elementary
row operations to get number one in the upper left corner and zeros below it.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4
1
2
1
2 0 1 0 60
x5 0 1
4 0 0 1 25
zj −20 −14 0 0 0 0
Subtract a 0.5 multiplier of the ﬁrst row from the second row.
Iteration step of the simplex method
The choice of the leaving variable is based on the need to maintain the
feasibility of the solution, i.e. the non-negativity of all the basic variables. Let
us write this condition for the new values of the original basic variables
x3, x4, x5. If we set x1 = t, we get:
x3 = 40 − 1
2 t ≥ 0
x4 = 60 − 1
2 t ≥ 0
x5 = 25 − 0 ≥ 0
Obviously the largest such t is t = 80, for which we get x3 = 0. It now
becomes the leaving variable. We can upgrade the table using elementary
row operations to get number one in the upper left corner and zeros below it.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj −20 −14 0 0 0 0
Finally we add a 20 multiplier of the ﬁrst row to the last one.
Iteration step of the simplex method
The choice of the leaving variable is based on the need to maintain the
feasibility of the solution, i.e. the non-negativity of all the basic variables. Let
us write this condition for the new values of the original basic variables
x3, x4, x5. If we set x1 = t, we get:
x3 = 40 − 1
2 t ≥ 0
x4 = 60 − 1
2 t ≥ 0
x5 = 25 − 0 ≥ 0
Obviously the largest such t is t = 80, for which we get x3 = 0. It now
becomes the leaving variable. We can upgrade the table using elementary
row operations to get number one in the upper left corner and zeros below it.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
We have a new table.
The second iteration
Negative reduced price z2 = −4 indicates that we can increase the objective
value by choosing x2 as the entering variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
The second iteration
Negative reduced price z2 = −4 indicates that we can increase the objective
value by choosing x2 as the entering variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
When x2 = t, the largest value of t can be min{2 × 80, 4 × 20, 4 × 25} = 80.
We get new values of basic variables,
x1 = 80 − 1
2 t = 40, x4 = 20 − 1
4 t = 0, x5 = 25 − 1
4 t = 5. So x4 becomes
nonbasic; it is a leaving variable.
The second iteration
Negative reduced price z2 = −4 indicates that we can increase the objective
value by choosing x2 as the entering variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
When x2 = t, the largest value of t can be min{2 × 80, 4 × 20, 4 × 25} = 80.
We get new values of basic variables,
x1 = 80 − 1
2 t = 40, x4 = 20 − 1
4 t = 0, x5 = 25 − 1
4 t = 5. So x4 becomes
nonbasic; it is a leaving variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
We multiply the second row by 4.
The second iteration
Negative reduced price z2 = −4 indicates that we can increase the objective
value by choosing x2 as the entering variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
When x2 = t, the largest value of t can be min{2 × 80, 4 × 20, 4 × 25} = 80.
We get new values of basic variables,
x1 = 80 − 1
2 t = 40, x4 = 20 − 1
4 t = 0, x5 = 25 − 1
4 t = 5. So x4 becomes
nonbasic; it is a leaving variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x2 0 1 -4 4 0 80
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
We subtract its 0.5 multiplier from the ﬁrst row.
The second iteration
Negative reduced price z2 = −4 indicates that we can increase the objective
value by choosing x2 as the entering variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
When x2 = t, the largest value of t can be min{2 × 80, 4 × 20, 4 × 25} = 80.
We get new values of basic variables,
x1 = 80 − 1
2 t = 40, x4 = 20 − 1
4 t = 0, x5 = 25 − 1
4 t = 5. So x4 becomes
nonbasic; it is a leaving variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 4 0 0 40
x2 0 1 -4 4 0 80
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
We subtract its 0.25 multiplier from the third row.
The second iteration
Negative reduced price z2 = −4 indicates that we can increase the objective
value by choosing x2 as the entering variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
When x2 = t, the largest value of t can be min{2 × 80, 4 × 20, 4 × 25} = 80.
We get new values of basic variables,
x1 = 80 − 1
2 t = 40, x4 = 20 − 1
4 t = 0, x5 = 25 − 1
4 t = 5. So x4 becomes
nonbasic; it is a leaving variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 4 0 0 40
x2 0 1 -4 4 0 80
x5 0 0 1 -1 1 5
zj 0 −4 40 0 0 1600
Finally we add its 4 multiplier to the last one.
The second iteration
Negative reduced price z2 = −4 indicates that we can increase the objective
value by choosing x2 as the entering variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 1
2 2 0 0 80
x4 0 1
4 -1 1 0 20
x5 0 1
4 0 0 1 25
zj 0 −4 40 0 0 1600
When x2 = t, the largest value of t can be min{2 × 80, 4 × 20, 4 × 25} = 80.
We get new values of basic variables,
x1 = 80 − 1
2 t = 40, x4 = 20 − 1
4 t = 0, x5 = 25 − 1
4 t = 5. So x4 becomes
nonbasic; it is a leaving variable.
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 4 0 0 40
x2 0 1 -4 4 0 80
x5 0 0 1 -1 1 5
zj 0 0 24 16 0 1920
We have got a new simplex table.
The termination of the computation
All reduced prices are non-negative in the ﬁnal table:
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 4 0 0 40
x2 0 1 -4 4 0 80
x5 0 0 1 -1 1 5
zj 0 0 24 16 0 1920
It is not possible to increase the objective value; the maximal proﬁt is 1.920
millions of CZK. The variables x3, x4 are nonbasic so they are of zero value.
The values of basic variables can be determined from the table:
x1 = 40, x2 = 80, x5 = 5. This means that in order to maximize the proﬁt we
should produce 40 tons of the blend Mocca and 80 tons of the blend
Standard. The ﬁrst two raw materials would be used at their maximum
available amount, but ﬁve tons of the third raw material would be redundant.
The termination of the computation
All reduced prices are non-negative in the ﬁnal table:
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 4 0 0 40
x2 0 1 -4 4 0 80
x5 0 0 1 -1 1 5
zj 0 0 24 16 0 1920
It is not possible to increase the objective value; the maximal proﬁt is 1.920
millions of CZK. The variables x3, x4 are nonbasic so they are of zero value.
The values of basic variables can be determined from the table:
x1 = 40, x2 = 80, x5 = 5. This means that in order to maximize the proﬁt we
should produce 40 tons of the blend Mocca and 80 tons of the blend
Standard. The ﬁrst two raw materials would be used at their maximum
available amount, but ﬁve tons of the third raw material would be redundant.
Comment: The procedure is similar also for minimization problems, but we
treat the signs in the last row in an opposite way (we choose the entering
variable according to the largest reduced price and terminate the
computations when all of them are negative.)
Two-phase simplex method
If there are also constraints of other types than "≤"in the problem, we have to
ﬁnd the initial feasible solution ﬁrst. To do this, we use the ﬁrst phase of a
simplex method. Let’s show it on an illustrative example.
z = x1 − x2 → min
subject to
x1 ≥ 2
x2 ≥ 2
5x1 + 10x2 ≤ 50
Two-phase simplex method
If there are also constraints of other types than "≤"in the problem, we have to
ﬁnd the initial feasible solution ﬁrst. To do this, we use the ﬁrst phase of a
simplex method. Let’s show it on an illustrative example.
z = x1 − x2 → min
subject to
x1 ≥ 2
x2 ≥ 2
5x1 + 10x2 ≤ 50
Constraints can be converted to equalities using slack variables:
x1 −x3 = 2
x2 −x4 = 2
5x1 + 10x2 +x5 = 50
Two-phase simplex method
If there are also constraints of other types than "≤"in the problem, we have to
ﬁnd the initial feasible solution ﬁrst. To do this, we use the ﬁrst phase of a
simplex method. Let’s show it on an illustrative example.
z = x1 − x2 → min
subject to
x1 ≥ 2
x2 ≥ 2
5x1 + 10x2 ≤ 50
Constraints can be converted to equalities using slack variables:
x1 −x3 = 2
x2 −x4 = 2
5x1 + 10x2 +x5 = 50
Unfortunately, we don’t get a system in a canonical form because the
coefﬁcients at x3 and x4 are not = 1. Therefore, we add the non-negative
auxiliary variables y1, y2 to the left side of the appropriate constraints and
these variables will already be basic (together with x5). For the starting point
we have values y1 = y2 = 2, x5 = 50, but this doesn’t give us a feasible
solution for the original problem.
Two-phase simplex method
To obtain a feasible solution of the original problem, we have to ensure that
y1 = y2 = 0. This can be done by minimizing the auxiliary objective function
z = y1 + y2 (if this function has a minimum > 0, then the original problem has
no feasible solution). We express z using non-basic variables and write down
the resulting reduced prices into the simplex tableau:
z = (2 − x1 + x3) + (2 − x2 + x4) = 4 − x1 − x2 + x3 + x4
Two-phase simplex method
To obtain a feasible solution of the original problem, we have to ensure that
y1 = y2 = 0. This can be done by minimizing the auxiliary objective function
z = y1 + y2 (if this function has a minimum > 0, then the original problem has
no feasible solution). We express z using non-basic variables and write down
the resulting reduced prices into the simplex tableau:
z = (2 − x1 + x3) + (2 − x2 + x4) = 4 − x1 − x2 + x3 + x4
basic var. x1 x2 x3 x4 x5 y1 y2 βi
y1 1 0 -1 0 0 1 0 2
y2 0 1 0 -1 0 0 1 2
x5 5 10 0 0 1 0 0 50
zj 1 1 -1 -1 0 0 0 4
We may choose as a leaving variable either x1 or x2. Let us choose the
second one.
Two-phase simplex method
To obtain a feasible solution of the original problem, we have to ensure that
y1 = y2 = 0. This can be done by minimizing the auxiliary objective function
z = y1 + y2 (if this function has a minimum > 0, then the original problem has
no feasible solution). We express z using non-basic variables and write down
the resulting reduced prices into the simplex tableau:
z = (2 − x1 + x3) + (2 − x2 + x4) = 4 − x1 − x2 + x3 + x4
basic var. x1 x2 x3 x4 x5 y1 y2 βi
y1 1 0 -1 0 0 1 0 2
y2 0 1 0 -1 0 0 1 2
x5 5 10 0 0 1 0 0 50
zj 1 1 -1 -1 0 0 0 4
We subtract 10 times the second row from the third one.
Two-phase simplex method
To obtain a feasible solution of the original problem, we have to ensure that
y1 = y2 = 0. This can be done by minimizing the auxiliary objective function
z = y1 + y2 (if this function has a minimum > 0, then the original problem has
no feasible solution). We express z using non-basic variables and write down
the resulting reduced prices into the simplex tableau:
z = (2 − x1 + x3) + (2 − x2 + x4) = 4 − x1 − x2 + x3 + x4
basic var. x1 x2 x3 x4 x5 y1 y2 βi
y1 1 0 -1 0 0 1 0 2
y2 0 1 0 -1 0 0 1 2
x5 5 0 0 10 1 0 -10 30
zj 1 1 -1 -1 0 0 0 4
We subtract the second row from the fourth.
Two-phase simplex method
To obtain a feasible solution of the original problem, we have to ensure that
y1 = y2 = 0. This can be done by minimizing the auxiliary objective function
z = y1 + y2 (if this function has a minimum > 0, then the original problem has
no feasible solution). We express z using non-basic variables and write down
the resulting reduced prices into the simplex tableau:
z = (2 − x1 + x3) + (2 − x2 + x4) = 4 − x1 − x2 + x3 + x4
basic var. x1 x2 x3 x4 x5 y1 y2 βi
y1 1 0 -1 0 0 1 0 2
x2 0 1 0 -1 0 0 1 2
x5 5 0 0 10 1 0 -10 30
zj 1 0 -1 0 0 0 -1 2
We have a new table; the entering variable is x1. We subtract ﬁve times the
ﬁrst row from the third one.
Two-phase simplex method
To obtain a feasible solution of the original problem, we have to ensure that
y1 = y2 = 0. This can be done by minimizing the auxiliary objective function
z = y1 + y2 (if this function has a minimum > 0, then the original problem has
no feasible solution). We express z using non-basic variables and write down
the resulting reduced prices into the simplex tableau:
z = (2 − x1 + x3) + (2 − x2 + x4) = 4 − x1 − x2 + x3 + x4
basic var. x1 x2 x3 x4 x5 y1 y2 βi
y1 1 0 -1 0 0 1 0 2
x2 0 1 0 -1 0 0 1 2
x5 0 0 5 10 1 -5 -10 20
zj 1 0 -1 0 0 0 -1 2
We subtract the ﬁrst row from the last one.
Two-phase simplex method
To obtain a feasible solution of the original problem, we have to ensure that
y1 = y2 = 0. This can be done by minimizing the auxiliary objective function
z = y1 + y2 (if this function has a minimum > 0, then the original problem has
no feasible solution). We express z using non-basic variables and write down
the resulting reduced prices into the simplex tableau:
z = (2 − x1 + x3) + (2 − x2 + x4) = 4 − x1 − x2 + x3 + x4
basic var. x1 x2 x3 x4 x5 y1 y2 βi
x1 1 0 -1 0 0 1 0 2
x2 0 1 0 -1 0 0 1 2
x5 0 0 5 10 1 -5 -10 20
zj 0 0 0 0 0 -1 -1 0
We have found a minimum of an auxiliary function zopt = 0, so we can start
phase 2: we omit y1, y2 and minimize function
z = x1 − x2 = (2 − x3) − (2 − x4) = −x3 + x4 whose reduced prices we add to
the table. We start from the point [2, 2, 0, 0, 20].
Note: If we obtain zopt = 0 , there would be no feasible solution to the
original problem.
Two-phase simplex method
The second phase can be completed as usual:
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 -1 0 0 2
x2 0 1 0 -1 0 2
x5 0 0 5 10 1 20
zj 0 0 -1 1 0 0
The entering variable is x4.
Two-phase simplex method
The second phase can be completed as usual:
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 -1 0 0 2
x2 0 1 0 -1 0 2
x5 0 0 5 10 1 20
zj 0 0 -1 1 0 0
We divide the third row by 10.
Two-phase simplex method
The second phase can be completed as usual:
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 -1 0 0 2
x2 0 1 0 -1 0 2
x5 0 0 1
2 1 1
10 2
zj 0 0 -1 1 0 0
We add the third row to the second one.
Two-phase simplex method
The second phase can be completed as usual:
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 -1 0 0 2
x2 0 1 1
2 0 1
10 4
x5 0 0 1
2 1 1
10 2
zj 0 0 -1 1 0 0
We subtract the third row from the last one.
Two-phase simplex method
The second phase can be completed as usual:
basic var. x1 x2 x3 x4 x5 βi
x1 1 0 -1 0 0 2
x2 0 1 1
2 0 1
10 4
x4 0 0 1
2 1 1
10 2
zj 0 0 -3
2 0 - 1
10 -2
We have obtained the optimal table, so we have x1 = 2, x2 = 4, zopt = −2.
Two-phase simplex method
The whole process in a graphical representation:
Feasible region M. Both variables x1, x2 are non-basic at the beginning of the
ﬁrst phase, so we start from the origin.
Two-phase simplex method
The whole process in a graphical representation:
Variable x2 becomes basic after the ﬁrst step with the value x2 = 2.
Two-phase simplex method
The whole process in a graphical representation:
In the next step also variable x1 becomes basic with the value x1 = 2, we
achieved the feasible region and the second phase can start.
Two-phase simplex method
The whole process in a graphical representation:
Optimum is achieved at the point [x1, x2] = [2, 4] after one step.
Pitfalls of the simplex method - degeneration
If the variable is basic and at the same time it is = 0 (i.e. the corresponding
right side is zero), we say that degeneration has occurred. There is a risk that
procedure would get to an inﬁnite loop (after several steps we would return to
the same corner point of the feasible set).
Pitfalls of the simplex method - degeneration
If the variable is basic and at the same time it is = 0 (i.e. the corresponding
right side is zero), we say that degeneration has occurred. There is a risk that
procedure would get to an inﬁnite loop (after several steps we would return to
the same corner point of the feasible set). Degeneration is caused by the fact
that some constraints are redundant and can be eliminated in several ways:
By modifying the test of optimality
Charnes method - adjusts the zero right sides to positive values
Bland rule - modiﬁes the determination of a key column and a key row
Pitfalls of the simplex method - degeneration
If the variable is basic and at the same time it is = 0 (i.e. the corresponding
right side is zero), we say that degeneration has occurred. There is a risk that
procedure would get to an inﬁnite loop (after several steps we would return to
the same corner point of the feasible set). Degeneration is caused by the fact
that some constraints are redundant and can be eliminated in several ways:
By modifying the test of optimality
Charnes method - adjusts the zero right sides to positive values
Bland rule - modiﬁes the determination of a key column and a key row
Pitfalls of the simplex method - non-uniqueness of the
optimal solution
If, in the output table corresponding to the optimal solution x, a non-basic
coefﬁcient in the z row is = 0, then if the variable corresponding to this
coefﬁcient enters the base, we get x which will also be optimal. The optimum
does not only occur in both vertices x and x , but also at each point of the
edge between them (in the case of three optimal neighbours, even the entire
wall is optimized by them), etc.
Pitfalls of the simplex method - unbounded feasible
region
If all the values in the entering column are ≤ 0 in some iteration step, i.e. no
positive change is possible for that column, it means that the set of acceptable
solutions is unlimited (in the optimization direction). In practice, this is mostly
due to a wrong formulation of the problem (a constraint is missing, or a
parameter is not well estimated).
Pitfalls of the simplex method - unbounded feasible
region
If all the values in the entering column are ≤ 0 in some iteration step, i.e. no
positive change is possible for that column, it means that the set of acceptable
solutions is unlimited (in the optimization direction). In practice, this is mostly
due to a wrong formulation of the problem (a constraint is missing, or a
parameter is not well estimated).
Pitfalls of the simplex method - empty feasible set
The absence of a feasible solution is recognized by the fact that, in the ﬁrst
phase of the two-phase method a positive optimal value is obtained. This is
due to the constraints being contradictory. In such situations, we can use goal
programming or reformulate some constraints.
Pitfalls of the simplex method - empty feasible set
The absence of a feasible solution is recognized by the fact that, in the ﬁrst
phase of the two-phase method a positive optimal value is obtained. This is
due to the constraints being contradictory. In such situations, we can use goal
programming or reformulate some constraints.
Duality of LP problems
The original problem can be seen in another way. Suppose we did not process
the raw materials but sold them straight away. The question is, when will this
direct sale of resources be better than production. This will, of course, depend
on the proﬁt from the sale of individual resources - we will use the so-called
dual variables denoted by wi (we have three types of coffee beans, i.e.
i = 1, 2, 3). We can then formulate the dual problem to the primary problem:
What is the minimum proﬁt from the sale of resources when no production is
proﬁtable?
Duality of LP problems
The original problem can be seen in another way. Suppose we did not process
the raw materials but sold them straight away. The question is, when will this
direct sale of resources be better than production. This will, of course, depend
on the proﬁt from the sale of individual resources - we will use the so-called
dual variables denoted by wi (we have three types of coffee beans, i.e.
i = 1, 2, 3). We can then formulate the dual problem to the primary problem:
What is the minimum proﬁt from the sale of resources when no production is
proﬁtable? Thus, we minimize the proﬁt from the sale of resources
g(w) = 40w1 + 60w2 + 25w3 subject to the condition that it is not worthwhile
to produce either Mocca or Standard coffee, 0.5w1 + 0.5w2 ≥ 20,
0.5w1 + 0.25w2 + 0.5w3 ≥ 14.
Duality of LP problems
The original problem can be seen in another way. Suppose we did not process
the raw materials but sold them straight away. The question is, when will this
direct sale of resources be better than production. This will, of course, depend
on the proﬁt from the sale of individual resources - we will use the so-called
dual variables denoted by wi (we have three types of coffee beans, i.e.
i = 1, 2, 3). We can then formulate the dual problem to the primary problem:
What is the minimum proﬁt from the sale of resources when no production is
proﬁtable? Thus, we minimize the proﬁt from the sale of resources
g(w) = 40w1 + 60w2 + 25w3 subject to the condition that it is not worthwhile
to produce either Mocca or Standard coffee, 0.5w1 + 0.5w2 ≥ 20,
0.5w1 + 0.25w2 + 0.5w3 ≥ 14. When using the notation introduced above,
where c is the vector of proﬁts from the sale of mixtures, b = (40, 60, 25) and
A is a structural matrix; we can compare the matrix formulation of the original,
called primary, and the dual problem:
primary problem dual problem
maximize z = c · x minimize g(w) = b · w
s. t. A · x ≤ b, x ≥ 0, s. t. A · w ≥ c, w ≥ 0
Duality of LP problems
The following rules can be applied for the construction of dual LP problems in
a general case:
Maximization problem ↔ Minimization problem
primary ↔ dual
dual ↔ primary
constraint of the type ≤ ↔ non-negative variable
constraint of the type ≥ ↔ non-positive variable
constraint of the type = ↔ unbounded variable
non-negative variable ↔ constraint of the type ≥
non-positive variable ↔ constraint of the type ≤
unbounded variable ↔ constraint of the type =
Duality of LP problems
The mutual relationship between primary-dual problem can be described in
The duality theorem:
If there an optimal solution to one of the primary-dual problems exists,
then there is also an optimal solution to the second problem and
they have the same optimal values !
Duality of LP problems
The mutual relationship between primary-dual problem can be described in
The duality theorem:
If there an optimal solution to one of the primary-dual problems exists,
then there is also an optimal solution to the second problem and
they have the same optimal values !
As a consequence, if one of the problems has no optimal solution, neither
does the other problem. It can be shown that if the feasible set is empty for
one problem, the other problem is unbounded and vice versa. The next
corollary is called The week duality theorem:
The objective value of the maximization problem is always less or equal to
the objective value of the minimization problem.
Duality of LP problems
The mutual relationship between primary-dual problem can be described in
The duality theorem:
If there an optimal solution to one of the primary-dual problems exists,
then there is also an optimal solution to the second problem and
they have the same optimal values !
As a consequence, if one of the problems has no optimal solution, neither
does the other problem. It can be shown that if the feasible set is empty for
one problem, the other problem is unbounded and vice versa. The next
corollary is called The week duality theorem:
The objective value of the maximization problem is always less or equal to
the objective value of the minimization problem.
We can also formulate a theorem concerning Complementary slackness:
If the k-th variable of the primary problem is positive (non-zero), then the k-th
condition of the dual problem is satisﬁed as an equality. It is said that the k-th
constraint is binding.
Sensitivity analysis
Sensitivity analysis examines the extent to which the possible changes to the
input data affect the original optimal solution. In particular, we are interested in
the effect of changing a single product proﬁt or changing the resources
capacities. This can be determined without recalculation of the whole task.
We deﬁne the so-called stability intervals for:
the coefﬁcients ck of the objective function; we determine the range of
values of ck (while preserving values of the other coefﬁcients), for which
the optimal solution would lie in the same point,
the capacity limits bi , when we determine the range of bi (while
preserving the values of the other capacities), that would lead to the
same set of basic variables, i.e. the same set of active constraints.
It is important for managerial decision-making to ﬁnd out what is the
effect of changing the capacities on the optimal value of the objective
function. This can be determined from the optimal values of the dual
variables wi . These values are called shadow prices and they express the
value by which the objective function changes if we increase the capacity
of the i-th source bi by a unit (assuming that this change does not get out
of the stability interval)
Sensitivity analysis - the intervals for product prices
The determination of stability intervals is not difﬁcult and it is often an integral
part of software outputs. We will show graphical interpretation and derivation
of stability intervals for the objective function coefﬁcients in our simple
example of optimizing coffee production. The ﬁgure shows how much the
optimal level curve of the objective function can be tilted not to affect the
optimal solution x∗
.
Sensitivity analysis - the intervals for product prices
We deﬁne the bounds for a tilt so that the level line will cross the points
x∗
= [40, 80],A = [20, 100] or x∗
= [40, 80], B = [80, 0] respectively. Thus the
slope q should satisfy the conditions
−2 =
80 − 0
40 − 80
≤ q ≤
80 − 100
40 − 20
= −1.
The slope of the original level line z = c1x1 + c2x2 can be expressed as
q = −c1
c2
; for our problem we have c1 = 20, c2 = 14. Stability intervals for c1
can be determined by substituting q = −c1
14 into inequalities: −2 ≤ −c1
14 ≤ −1,
i.e. c1 ∈ 14, 28 . Analogically for c2 we get stability intervals by substituting
q = −20
c2
into inequalities: −2 ≤ −20
c2
≤ −1 and we get c2 ∈ 10, 20 .
Sensitivity analysis - the intervals for capacities
Let’s show similar graphical derivation of stability intervals for the right-hand
sides of constraints. The ﬁgure shows how we can move the boundary of the
ﬁrst constraint so that the optimal solution stays at the intersection of the
boundary lines of the ﬁrst and second constraint.
Sensitivity analysis - the intervals for capacities
The original equation of the boundary line for the ﬁrst constraint was
0, 5x1 + 0, 25x2 = 40. Its right-hand side b1 can be changed to move the line
at most to the point A or C respectively. By substituting the coordinates of the
point A = [20, 100] into the left side of the constraint we get
0, 5 · 20 + 0, 25 · 100 = 35 which is the lower bound for b1.
By substituting the coordinates of the point C = [120, 0] into the left side of the
constraint we get 0, 5 · 120 + 0, 25 · 0 = 60 which is the upper bound for b1.
Sensitivity analysis - the intervals for capacities
The original equation of the boundary line for the ﬁrst constraint was
0, 5x1 + 0, 25x2 = 40. Its right-hand side b1 can be changed to move the line
at most to the point A or C respectively. By substituting the coordinates of the
point A = [20, 100] into the left side of the constraint we get
0, 5 · 20 + 0, 25 · 100 = 35 which is the lower bound for b1.
By substituting the coordinates of the point C = [120, 0] into the left side of the
constraint we get 0, 5 · 120 + 0, 25 · 0 = 60 which is the upper bound for b1.
So we obtained the stability interval for b1: ∈ 35, 60 . Similarly, we can obtain
stability intervals for other constraints. These intervals are important when the
managers decide to purchase additional resources: if the shadow price of the
constraint is greater than the purchase price of the resource, it is worthwhile
to increase capacity within the stability interval. And how do we ﬁnd shadow
price for b1? By changing its value to b1 + ∆ we get a new optimal point as the
intersection of lines 0, 5x1 + 0, 25x2 = 40 + ∆, 0, 5x1 + 0, 5x2 = 60 which is
the point [40 + 4∆, 80 − 4∆]. At this point, the objective function attains the
value of z = 20(40 + 4∆) + 14(80 − 4∆) = 1920 + 24∆. The shadow price is
w1 = 24.
Sensitivity analysis - the intervals for capacities
The original equation of the boundary line for the ﬁrst constraint was
0, 5x1 + 0, 25x2 = 40. Its right-hand side b1 can be changed to move the line
at most to the point A or C respectively. By substituting the coordinates of the
point A = [20, 100] into the left side of the constraint we get
0, 5 · 20 + 0, 25 · 100 = 35 which is the lower bound for b1.
By substituting the coordinates of the point C = [120, 0] into the left side of the
constraint we get 0, 5 · 120 + 0, 25 · 0 = 60 which is the upper bound for b1.
So we obtained the stability interval for b1: ∈ 35, 60 . Similarly, we can obtain
stability intervals for other constraints. These intervals are important when the
managers decide to purchase additional resources: if the shadow price of the
constraint is greater than the purchase price of the resource, it is worthwhile
to increase capacity within the stability interval. And how do we ﬁnd shadow
price for b1? By changing its value to b1 + ∆ we get a new optimal point as the
intersection of lines 0, 5x1 + 0, 25x2 = 40 + ∆, 0, 5x1 + 0, 5x2 = 60 which is
the point [40 + 4∆, 80 − 4∆]. At this point, the objective function attains the
value of z = 20(40 + 4∆) + 14(80 − 4∆) = 1920 + 24∆. The shadow price is
w1 = 24.
Shadow prices can be found in the last row of an optimal table under the column
Special problems of linear programming
Some LP problems have special properties. These properties can relate to
the structure of the model, the type of variables, methods of solving, etc. An
important class of such special problems is the class of distribution problems.
We will explore some representatives of this group, particularly a
transportation problem, an assignment problem, and a travelling salesman
problem. Other problems (container or multi-stage transportation problem,
coverage problem, cutting plans, etc.) can be found in the literature.
Special problems of linear programming
Some LP problems have special properties. These properties can relate to
the structure of the model, the type of variables, methods of solving, etc. An
important class of such special problems is the class of distribution problems.
We will explore some representatives of this group, particularly a
transportation problem, an assignment problem, and a travelling salesman
problem. Other problems (container or multi-stage transportation problem,
coverage problem, cutting plans, etc.) can be found in the literature.
We will also deal with the speciﬁcs of integer problems and basic approaches
to their solution. Problems in which some variables have range restricted to a
set of integer numbers are called integer programming problems. Integer
variables usually represent the number of indivisible pieces. In some
problems, there are binary variables where values 0 and 1 encode the
absence or presence of a certain connection between the speciﬁed objects.
Transportation problem
Typically, the transportation problem deals with cost minimizing associated
with the delivery of goods from the suppliers to customers. We deﬁne m
vendors - V1, V2, . . . , Vm with limited capacities a1, a2, . . . , am, and n target
locations - subscribers S1, S2, . . . , Sn with requests b1, b2, . . . , bn. Each
source-target connection is associated with a value, typically, for example, the
cost of transporting the unit of goods. We denote these costs by
cij , i = 1, . . . , m, j = 1, . . . , n. The goal is to schedule transport volumes
between sources and targets (denoted by xij , i = 1, . . . , m, j = 1, . . . , n) in
such way that customer requirements are satisﬁed and resource capacities
are not exceeded.
Transportation problem
Typically, the transportation problem deals with cost minimizing associated
with the delivery of goods from the suppliers to customers. We deﬁne m
vendors - V1, V2, . . . , Vm with limited capacities a1, a2, . . . , am, and n target
locations - subscribers S1, S2, . . . , Sn with requests b1, b2, . . . , bn. Each
source-target connection is associated with a value, typically, for example, the
cost of transporting the unit of goods. We denote these costs by
cij , i = 1, . . . , m, j = 1, . . . , n. The goal is to schedule transport volumes
between sources and targets (denoted by xij , i = 1, . . . , m, j = 1, . . . , n) in
such way that customer requirements are satisﬁed and resource capacities
are not exceeded. Therefore, the problem consists of m · n variables xij , for
which we minimize the objective function
z =
m
i=1
n
j=1 cij xij subject to
n
j=1 xij ≤ ai , i = 1, . . . , m,
m
i=1 xij = bj , j = 1, . . . , n,
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n
Both objective function and constraints are linear, so it is a LP problem.
Transportation problem - solution methods
Even though transportation problem is as an LP problem solvable by a
standard simplex method, special procedures are more suitable due to a large
number of variables and special sparse structure of the matrix (there are
many zeros and the other numbers are positioned in a block scheme).
Transportation problem - solution methods
Even though transportation problem is as an LP problem solvable by a
standard simplex method, special procedures are more suitable due to a large
number of variables and special sparse structure of the matrix (there are
many zeros and the other numbers are positioned in a block scheme).
Example: For a problem with 20 sources and 300 customers there is ?
variables and ? constraints. The simplex tableau of such problem has
1920000 cells, which means 11 MB of operational memory.
Transportation problem - solution methods
Even though transportation problem is as an LP problem solvable by a
standard simplex method, special procedures are more suitable due to a large
number of variables and special sparse structure of the matrix (there are
many zeros and the other numbers are positioned in a block scheme).
Example: For a problem with 20 sources and 300 customers there is ?
variables and ? constraints. The simplex tableau of such problem has
1920000 cells, which means 11 MB of operational memory.
An exact solution can be achieved by Modiﬁed distribution method (MODI),
which is based on the simplex method. We can also quickly obtain an
approximate solution by some heuristics; we will mention three of them:
North-western corner method, Index method and Vogel approximate method
(VAM).
Transportation problem - solution methods
It is obviously not possible to supply all customers if total demand
n
j=1 bj
exceeds total capacity
n
i=1 ai , then there is no feasible solution to the
problem. The problem fulﬁlling equality
n
j=1 bj =
n
i=1 ai is called balanced
transportation problem. The balanced problem has a feasible solution even if
the capacities constraints are stated as equalities; let’s assume such
formulation of the problem for the explanation of solution methods.
Transportation problem - solution methods
It is obviously not possible to supply all customers if total demand
n
j=1 bj
exceeds total capacity
n
i=1 ai , then there is no feasible solution to the
problem. The problem fulﬁlling equality
n
j=1 bj =
n
i=1 ai is called balanced
transportation problem. The balanced problem has a feasible solution even if
the capacities constraints are stated as equalities; let’s assume such
formulation of the problem for the explanation of solution methods.
Unbalanced problem with the surplus of demand can be adjusted by
introducing a dummy source with the capacity
n
j=1 bj −
n
i=1 ai . In the case
of supply surplus, there is introduced a dummy customer with the request
n
i=1 ai −
n
j=1 bj .
Remark: Transportation costs to dummy places are always zero!
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
We will demonstrate the method on the following problem (M. Plevný, M.
Žižka: Modelování a optimalizace v manažerském rozhodování): Find a
feasible solution to the transportation problem with four customers S1, S2, S3
and S4, requesting 3, 6, 4 and 5 units of product and three sources V1, V2 and
V3 with capacities 5, 7 and 6 units respectively.
requests
xij 3 6 4 5
cap.left
5
7
6
The S1 will get 3 units from the ﬁrst source, then 2 units will be left in the V1.
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
We will demonstrate the method on the following problem (M. Plevný, M.
Žižka: Modelování a optimalizace v manažerském rozhodování): Find a
feasible solution to the transportation problem with four customers S1, S2, S3
and S4, requesting 3, 6, 4 and 5 units of product and three sources V1, V2 and
V3 with capacities 5, 7 and 6 units respectively.
requests
xij 0 6 4 5
cap.left
2 3
7
6
Two units left in V1 will be transported to S2 and we move to another source.
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
We will demonstrate the method on the following problem (M. Plevný, M.
Žižka: Modelování a optimalizace v manažerském rozhodování): Find a
feasible solution to the transportation problem with four customers S1, S2, S3
and S4, requesting 3, 6, 4 and 5 units of product and three sources V1, V2 and
V3 with capacities 5, 7 and 6 units respectively.
requests
xij 0 4 4 5
cap.left
0 3 2
7
6
Four remaining units requested by the S2 will be supplied by the V2, three
units will be left.
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
We will demonstrate the method on the following problem (M. Plevný, M.
Žižka: Modelování a optimalizace v manažerském rozhodování): Find a
feasible solution to the transportation problem with four customers S1, S2, S3
and S4, requesting 3, 6, 4 and 5 units of product and three sources V1, V2 and
V3 with capacities 5, 7 and 6 units respectively.
requests
xij 0 0 4 5
cap.left
0 3 2
3 4
6
Three remaining units from the V2 are delivered to the S3.
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
We will demonstrate the method on the following problem (M. Plevný, M.
Žižka: Modelování a optimalizace v manažerském rozhodování): Find a
feasible solution to the transportation problem with four customers S1, S2, S3
and S4, requesting 3, 6, 4 and 5 units of product and three sources V1, V2 and
V3 with capacities 5, 7 and 6 units respectively.
requests
xij 0 0 1 5
cap.left
0 3 2
0 4 3
6
A last unit requested by customer S3 will be transported from the source V3.
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
We will demonstrate the method on the following problem (M. Plevný, M.
Žižka: Modelování a optimalizace v manažerském rozhodování): Find a
feasible solution to the transportation problem with four customers S1, S2, S3
and S4, requesting 3, 6, 4 and 5 units of product and three sources V1, V2 and
V3 with capacities 5, 7 and 6 units respectively.
requests
xij 0 0 0 5
cap.left
0 3 2
0 4 3
5 1
Remaining ﬁve units of the V3 will be left for the customer S4.
Transportation problem - NW corner method
North-western corner method is the simplest way how to obtain a feasible
solution of the transportation problem. We begin to match requests with the
sources in the upper left corner of the table and proceed to the right (if the
request is completed) or down (if the capacity of the source is reached). We
ﬁnish in the right bottom corner.
We will demonstrate the method on the following problem (M. Plevný, M.
Žižka: Modelování a optimalizace v manažerském rozhodování): Find a
feasible solution to the transportation problem with four customers S1, S2, S3
and S4, requesting 3, 6, 4 and 5 units of product and three sources V1, V2 and
V3 with capacities 5, 7 and 6 units respectively.
requests
xij 0 0 0 0
cap.left
0 3 2
0 4 3
0 1 5
Now we have a feasible solution.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
requests
xij 3 6 4 5
cap.left
5
7
6
transportation costs
cij S1 S2 S3 S4
V1 2 1 3 4
V2 6 2 6 1
V3 7 3 3 3
The lowest costs are c12 = c24 = 1. We choose for example the ﬁrst
connection, the V1 can supply to the S2 at most 5 units. Its capacity will be
reached and that is why we don’t use the ﬁrst row of the cost matrix anymore.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
requests
xij 3 1 4 5
cap.left
0 5
7
6
transportation costs
cij S1 S2 S3 S4
V1
V2 6 2 6 1
V3 7 3 3 3
Now the lowest costs are c24 = 1. Customer S4 can get from the V2 at most 5
units. He has no other requests and we ignore the fourth column from now on.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
requests
xij 3 1 4 0
cap.left
0 5
2 5
6
transportation costs
cij S1 S2 S3 S4
V1
V2 6 2 6
V3 7 3 3
The lowest costs are c22 = 2. The S2 can take from the V2 only 1 unit, the
second column is completed.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
requests
xij 3 0 4 0
cap.left
0 5
1 1 5
6
transportation costs
cij S1 S2 S3 S4
V1
V2 6 6
V3 7 3
The lowest costs are c33 = 3. Customer S3 can get from the V3 4 units, the
third column is completed.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
requests
xij 3 0 0 0
cap.left
0 5
1 1 5
2 4
transportation costs
cij S1 S2 S3 S4
V1
V2 6
V3 7
The lowest costs are c21 = 6. V2 can supply S1 with 1 unit, the third row is
completed.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
requests
xij 2 0 0 0
cap.left
0 5
0 1 1 5
2 4
transportation costs
cij S1 S2 S3 S4
V1
V2
V3 7
In the last step we transport from V3 to S1 remaining two units.
Transportation problem - the index method
The index method usually gives a better feasible solution with lower costs
than the previous method. It is based on the so-called greedy algorithm, the
preferred connections are those with the lowest costs. Let’s demonstrate the
method on the previously solved problem. We add the table with unit costs of
transportation cij , i = 1, . . . 3, j = 1, . . . 4.
requests
xij 0 0 0 0
cap.left
0 5
0 1 1 5
0 2 4
transportation costs
cij S1 S2 S3 S4
V1 2 1 3 4
V2 6 2 6 1
V3 7 3 3 3
The cost of the transportation will be
x12·c12+x21·c21+x22·c22+x24·c24+x31·c31+x33·c33 = 5+6+2+5+14+12 = 44.
Previous method would cost 6 + 2 + 6 + 2 + 5 + 14 + 12 = 47.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Lets apply the method on our example. We attach to the cost table row and
column differences di., i = 1, . . . 3 a d.j , j = 1, . . . 4.
requests
xij 3 6 4 5
cap.left
5
7
6
cij S1 S2 S3 S4 di.
V1 2 1 3 4 1
V2 6 2 6 1 1
V3 7 3 3 3 0
d.j 4 1 0 2
The highest difference is in the ﬁrst column, where is the lowest cost c11 = 2.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Lets apply the method on our example. We attach to the cost table row and
column differences di., i = 1, . . . 3 a d.j , j = 1, . . . 4.
requests
xij 0 6 4 5
cap.left
2 3
7
6
cij S1 S2 S3 S4 di.
V1 1 3 4 2
V2 2 6 1 1
V3 3 3 3 0
d.j 1 0 2
The highest difference is in the ﬁrst row, where is the lowest cost c12 = 1.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Lets apply the method on our example. We attach to the cost table row and
column differences di., i = 1, . . . 3 a d.j , j = 1, . . . 4.
requests
xij 0 4 4 5
cap.left
0 3 2
7
6
cij S1 S2 S3 S4 di.
V1
V2 2 6 1 1
V3 3 3 3 0
d.j 1 3 2
The highest difference is in the third column, we choose its lowest cost
c33 = 3.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Lets apply the method on our example. We attach to the cost table row and
column differences di., i = 1, . . . 3 a d.j , j = 1, . . . 4.
requests
xij 0 4 0 5
cap.left
0 3 2
7
2 4
cij S1 S2 S3 S4 di.
V1
V2 2 1 1
V3 3 3 0
d.j 1 2
The highest difference is in the fourth column, where is the lowest cost
c24 = 1.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Lets apply the method on our example. We attach to the cost table row and
column differences di., i = 1, . . . 3 a d.j , j = 1, . . . 4.
requests
xij 0 4 0 0
cap.left
0 3 2
2 5
2 4
cij S1 S2 S3 S4 di.
V1
V2 2
V3 3
d.j 1
The highest difference is in the fourth column, where is the lowest cost
c22 = 2.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Lets apply the method on our example. We attach to the cost table row and
column differences di., i = 1, . . . 3 a d.j , j = 1, . . . 4.
requests
xij 0 2 0 0
cap.left
0 3 2
0 2 5
2 4
cij S1 S2 S3 S4 di.
V1
V2
V3
d.j
It remains to transport two units from the source V3 to the customer S2.
Transportation problem - method VAM
Vogel approximate method is the third heuristics and its advantage lies in
considering alternative costs of the cheapest connection. It uses differences
(we compute them by subtracting row minima from the second lowest price in
every row and column minima from the second cheapest connection in every
column). In every step we choose the cheapest connection in the line (row or
column) with the highest difference.
Lets apply the method on our example. We attach to the cost table row and
column differences di., i = 1, . . . 3 a d.j , j = 1, . . . 4.
requests
xij 0 0 0 0
cap.left
0 3 2
0 2 5
0 2 4
cij S1 S2 S3 S4 di.
V1 2 1 3 4 1
V2 6 2 6 1 1
V3 7 3 3 3 0
d.j 4 1 0 2
Final transport costs are remarkably lower than those obtained by previous
methods: x11 · c11 + x12 · c12 + x22 · c22 + x24 · c24 + x32 · c32 + x33 · c33 = 35.
Transportation problem - method MODI
The modiﬁed distribution method for the solution of balanced problems is
based on theorems of duality in linear programming. A dual problem to our
task
z =
m
i=1
n
j=1 cij xij → min subject to
n
j=1 xij = ai , i = 1, . . . , m,
m
i=1 xij = bj , j = 1, . . . , n,
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n
is formulated by means of dual variables ui , vj , i = 1, . . . , m, j = 1, . . . , n :
m
i=1 ai ui +
n
j=1 bj vj → max
subject to ui + vj ≤ cij , i = 1, . . . , m, j = 1, . . . , n
Transportation problem - method MODI
The modiﬁed distribution method for the solution of balanced problems is
based on theorems of duality in linear programming. A dual problem to our
task
z =
m
i=1
n
j=1 cij xij → min subject to
n
j=1 xij = ai , i = 1, . . . , m,
m
i=1 xij = bj , j = 1, . . . , n,
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n
is formulated by means of dual variables ui , vj , i = 1, . . . , m, j = 1, . . . , n :
m
i=1 ai ui +
n
j=1 bj vj → max
subject to ui + vj ≤ cij , i = 1, . . . , m, j = 1, . . . , n
The complementary slackness condition of LP duality implies that all primal
basic variables (xij > 0) have the corresponding constraints satisﬁed as
equality. (ui + vj = cij ). If there is no degeneration, the basis contains exactly
m + n − 1 variables. So we have the system of m + n − 1 equations for m + n
dual variables. That means that we can choose one value arbitrarily and solve
the system for the rest of the dual variables. By checking the dual feasibility
condition
ui + vj − cij ≤ 0, i = 1, . . . , m, j = 1, . . . , n
Transportation problem - method MODI
We can determine the values of dual variables and perform the optimality test
right in the table; let’s show it on the feasible table obtained by the method
VAM:
requests
xij 3 6 4 5
capacity
5 3 2
7 2 5
6 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4
V2 6 2 6 1
V3 7 3 3 3
vj
We choose such values of ui , vj , so that the sums of individual pairs are equal
to the numbers in the red cells. We can choose one value arbitrarily, let’s say
v2 = 0. Remaining values will be computed so that the above mentioned
condition is satisﬁed.
Transportation problem - method MODI
We can determine the values of dual variables and perform the optimality test
right in the table; let’s show it on the feasible table obtained by the method
VAM:
requests
xij 3 6 4 5
capacity
5 3 2
7 2 5
6 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4 1
V2 6 2 6 1 2
V3 7 3 3 3 3
vj 1 0 0 -1
We choose such values of ui , vj , so that the sums of individual pairs are equal
to the numbers in the red cells. We can choose one value arbitrarily, lets say
v2 = 0. Remaining values will be computed so that the above mentioned
condition is satisﬁed. The table is optimal, the sums of dual variables are not
higher than the numbers inside the table.
Transportation problem - method MODI
If we begin from a different starting point, the situation would not be that easy.
The test of optimality is not satisﬁed for a feasible solution determined by the
index method:
requests
xij 3 6 4 5
capacity
5 5
7 1 1 5
6 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4
V2 6 2 6 1
V3 7 3 3 3
vj
Transportation problem - method MODI
If we begin from a different starting point, the situation would not be that easy.
The test of optimality is not satisﬁed for a feasible solution determined by the
index method:
requests
xij 3 6 4 5
capacity
5 5
7 1 1 5
6 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4 -1
V2 6 2 6 1 0
V3 7 3 3 3 1
vj 6 2 2 1
We choose ui , vj so that the sums of individual pairs are equal to the numbers
in the red cells. We can start by choosing u2 = 0, the rest has to be computed
again.
Transportation problem - method MODI
If we begin from a different starting point, the situation would not be that easy.
The test of optimality is not satisﬁed for a feasible solution determined by the
index method:
requests
xij 3 6 4 5
capacity
5 5
7 1 1 5
6 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4 -1
V2 6 2 6 1 0
V3 7 3 3 3 1
vj 6 2 2 1
We can see that the optimality condition is violated in the upper left corner:
u1 + v1 = 5 > c11 = 2.
Transportation problem - method MODI
If we begin from a different starting point, the situation would not be that easy.
The test of optimality is not satisﬁed for a feasible solution determined by the
index method:
requests
xij 3 6 4 5
capacity
5 + 5 -
7 1 - 1 + 5
6 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4 -1
V2 6 2 6 1 0
V3 7 3 3 3 1
vj 6 2 2 1
We can see that the optimality condition is violated in the upper left corner:
u1 + v1 = 5 > c11 = 2. We can do the iteration step and proceed to another
basic solution with a better value of the primal objective function by choosing
the entering variable x11, which will replace one of variables x12, x22, x21
forming the so-called Dantzig closed loop going through x11. The feasibility of
the primal problem must not be violated. We can see that the variable x21 can
be decreased by 1 and therefore be excluded from the basis. At the same
time, we have to increase x22 and decrease x12 (see the signs + and - in the
left table). We get a new basic solution.
Transportation problem - method MODI
If we begin from a different starting point, the situation would not be that easy.
The test of optimality is not satisﬁed for a feasible solution determined by the
index method:
requests
xij 3 6 4 5
capacity
5 1 4
7 0 2 5
6 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4 -1
V2 6 2 6 1 0
V3 7 3 3 3 4
vj 3 2 -1 1
We compute the values of ui , vj again and check the optimality. The condition
is violated at c32 and c34.
Transportation problem - method MODI
If we begin from a different starting point, the situation would not be that easy.
The test of optimality is not satisﬁed for a feasible solution determined by the
index method:
requests
xij 3 6 4 5
capacity
5 1 + 4 -
7 0 2 5
6 2 - + 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4 -1
V2 6 2 6 1 0
V3 7 3 3 3 4
vj 3 2 -1 1
We compute the values of ui , vj again and check for the optimality. The
condition is violated at c32 and c34.
We compare the differences (u3 + v2) − c32 = 6 − 3 = 3 and
(u3 + v4) − c34 = 5 − 3 = 2. The ﬁrst one is higher, so by choosing x32 as
entering variable, we improve the objective value more. We have to complete
Dantzig loop by the basic variables x31, x11 and x12. The leaving variable will
be x31, its 2 units will be moved to x32. We also have to change other variables
in the loop - we increase x11 by 2 and lower x12 by the same amount. We get a
new table.
Transportation problem - method MODI
If we begin from a different starting point, the situation would not be that easy.
The test of optimality is not satisﬁed for a feasible solution determined by the
index method:
requests
xij 3 6 4 5
capacity
5 3 2
7 2 5
6 0 2 4
cij S1 S2 S3 S4 ui
V1 2 1 3 4 1
V2 6 2 6 1 2
V3 7 3 3 3 3
vj 1 0 0 -1
Resulting solution is already optimal as we could see before (when starting
from VAM initial solution). The optimal value z = 35 cannot be improved.
In MODI computations we sometimes face degeneracy, when there are less
than m + n − 1 non-negative variables. We can get rid of it by letting some
zero basis variable xij have small value ε > 0.
Application area of a transportation problem
Examples of possible applications of a transportation problem are illustrated
in the following overview.
activity type source destination
fuel distribution reﬁnery, warehouse gas station
mail distribution sorting centre post ofﬁce
distribution warehouses of pharmacies,
of pharmaceuticals distribution companies hospitals
beet processing production centres sugar factories
Exceptionally, we can deal with transportation problems with maximization
type of objective function. When?
Assignment problem
In an assignment problem , we try to make pairs of objects from two different
groups so that the beneﬁt of the matching is as high as possible. Typically, the
task is to assign jobs to machines or projects to employees in order to
minimize costs or maximize proﬁt, etc. It is similar to the transportation
problem, but the variables are binary and the matching is one to one.
We will demonstrate solution of such a problem on the following example (M.
Kavan: Výrobní a provozní management): Find optimal matching of jobs 1, 2,
3 to machines A, B, C, D for production costs given by the table:
machines
cij A B C D
jobs
1 15 19 17 12
2 12 10 15 9
3 18 14 11 14
We have to choose one number in each row, so that their sum is minimal and
their columns are unique.
Assignment problem - the mathematical formulation
We can represent assigning the i-th job to the j-th machine by the equality
xij = 1 (zero otherwise). If there are more jobs than machines (m > n), the
problem is unsolvable. In the case n > m we can balance the problem by
introducing dummy jobs with zero production costs so that m = n. Let’s
assume that the problem is balanced.
Mathematical formulation of the assignment problem assumes binary
variables xij , i, j = 1 . . . n and conditions that all row and column sums are
equal to 1. If we denote production cost by cij , i, j = 1 . . . n, we get the
following formulation:
Minimize objective function
z =
n
i=1
n
j=1 cij xij
subject to
n
j=1 xij = 1, i = 1, . . . , n,
n
i=1 xij = 1, j = 1, . . . , n,
xij ∈ {0, 1}, i = 1, j = 1, . . . , n
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example.
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 15 19 17 12
2 12 10 15 9
3 18 14 11 14
We introduce one dummy job with zero production costs.
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 15 19 17 12
2 12 10 15 9
3 18 14 11 14
4 0 0 0 0
We do primary reduction by subtracting row minima, there will be at least one
zero in every row.
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 3 7 5 0
2 3 1 6 0
3 7 3 0 3
4 0 0 0 0
The same should be done for columns, but it is not necessary due to a
dummy job - there is already a zero in every column.
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 3 7 5 0
2 3 1 6 0
3 7 3 0 3
4 0 0 0 0
We need only three lines to cover all zeros, so the table is not optimal. In the
iteration step we add the smallest uncovered element to the numbers in the
intersections of covering lines and at the same time, we subtract it from every
uncovered element (the elements covered by only one line remain
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 2 6 5 0
2 2 0 6 0
3 6 2 0 3
4 0 0 1 1
After the secondary reduction we have a new uncovered zero and there are
no zeros covered by two lines. We have to construct a new covering.
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 2 6 5 0
2 2 0 6 0
3 6 2 0 3
4 0 0 1 1
Let’s check the optimality of a new table. It is not possible to cover all zeros by
less than four lines, we have an optimal solution and the algorithm terminates
(otherwise we would perform the secondary reduction again).
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 2 6 5 0
2 2 0 6 0
3 6 2 0 3
4 0 0 1 1
We can ﬁnd independent zeros among those covered by only one line. Their
positions determine the optimal matching of jobs and machines: 1-D, 2-B, 3-C.
A dummy job is assigned to machine A, so it is not used.
Assignment problem - solution methods
Assignment problem can be solved by the Hungarian method. We perform the
row and column reduction of the cost table in order to highlight row and
column minima (they are zeros after the reduction). If there exist n
independent zeros (not sharing any row or column), the table is optimal. The
zeros are independent if it is not possible to cover them all by less than n
vertical or horizontal lines. Let’s demonstrate the method on the previous
example. We have to balance the problem because there are more machines
than jobs.
machines
cij A B C D
jobs
1 15 19 17 12
2 12 10 15 9
3 18 14 11 14
The optimal solution can be highlighted in an original table. The total costs of
matching are 12 + 10 + 11 = 33. The solution is not always unique - covering
lines and independent zeros can be chosen in different ways - but all optimal
solution have the same objective value.
travelling salesman problem (TSP)
The TSP is a special case of the vehicle routing problem . The objective is to
start from an initial place (labelled by A1), visit each of the places A2, . . . , An
exactly once and return to the place A1 so that the total route is as short as
possible. There is a lot of real TSP applications - e.g. the distribution of
products, waste collection, etc.
travelling salesman problem (TSP)
The TSP is a special case of the vehicle routing problem . The objective is to
start from an initial place (labelled by A1), visit each of the places A2, . . . , An
exactly once and return to the place A1 so that the total route is as short as
possible. There is a lot of real TSP applications - e.g. the distribution of
products, waste collection, etc.
The mathematical model of TSP is similar to an assignment problem, it deals
with binary variables xij , that have value 1 if the connection Ai , Aj is on the
route and the value 0 if it is not. The route goes through every place just once,
so we can match the starting and ending points of each route segment in the
table with the constraint of row and column sums equal to 1. However, TSP is
much more difﬁcult, because we have to add other constraints preventing the
route from decomposing to separate cycles (see example).
travelling salesman problem (TSP)
The TSP is a special case of the vehicle routing problem . The objective is to
start from an initial place (labelled by A1), visit each of the places A2, . . . , An
exactly once and return to the place A1 so that the total route is as short as
possible. There is a lot of real TSP applications - e.g. the distribution of
products, waste collection, etc.
The mathematical model of TSP is similar to an assignment problem, it deals
with binary variables xij , that have value 1 if the connection Ai , Aj is on the
route and the value 0 if it is not. The route goes through every place just once,
so we can match the starting and ending points of each route segment in the
table with the constraint of row and column sums equal to 1. However, TSP is
much more difﬁcult, because we have to add other constraints preventing the
route from decomposing to separate cycles (see example).
For a large n it is practically impossible to use standard optimization
algorithms (we can hardly ﬁnd solutions for problems up to n = 30 nodes
using common computers).
travelling salesman problem - feasibility of the solution
We can demonstrate the difference between the TSP and an assignment
problem on the following example:
If we try to ﬁnd any closed route going through cities A1, . . . , A5 (without taking
into account the costs), we have to choose a pair of leaving and entering city
for every segment of the route. Every city is just once leaving and just once
entering. Let’s depict some solution in the table:
A1 A2 A3 A4 A5
A1 0 0 1 0 0
A2 0 0 0 1 0
A3 0 1 0 0 0
A4 0 0 0 0 1
A5 1 0 0 0 0
It is a feasible solution of TSP, because it represents the route
A1 − A3 − A2 − A4 − A5 − A1.
travelling salesman problem - feasibility of the solution
We can demonstrate the difference between the TSP and an assignment
problem on the following example:
If we try to ﬁnd any closed route going through cities A1, . . . , A5 (without taking
into account the costs), we have to choose a pair of leaving and entering city
for every segment of the route. Every city is just once leaving and just once
entering. Let’s depict some solution in the table:
A1 A2 A3 A4 A5
A1 0 1 0 0 0
A2 0 0 1 0 0
A3 1 0 0 0 0
A4 0 0 0 0 1
A5 0 0 0 1 0
This is not a feasible solution of TSP, because it represents two cycles
A1 − A2 − A3 − A1 and A4 − A5 − A4.
travelling salesman problem - approximate solution
There are many heuristics for ﬁnding an approximate solution to TSP, we will
show the greedy algorithm of the nearest neighbour on an example from the
book J. Pelikán, V. Chýna: Kvantitativní management.
The bakery in Kralupy supplies grocery shops in surrounding cities every day.
Find the order of stops of bakery car minimizing the total length of the route.
Distances between the cities are given by the table:
travelling salesman problem - approximate solution
There are many heuristics for ﬁnding an approximate solution to TSP, we will
show the greedy algorithm of the nearest neighbour on an example from the
book J. Pelikán, V. Chýna: Kvantitativní management.
The bakery in Kralupy supplies grocery shops in surrounding cities every day.
Find the order of stops of bakery car minimizing the total length of the route.
Distances between the cities are given by the table:
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza
Kralupy 0 4 16 8 18 25 17
Veltrusy 4 0 20 12 22 28 13
Slaný 16 20 0 12 7 14 17
Velvary 8 12 12 0 10 17 10
Zlonice 18 22 7 10 0 7 10
Vraný 25 28 14 17 7 0 15
Bˇríza 17 13 17 10 10 15 0
travelling salesman problem - approximate solution
There are many heuristics for ﬁnding an approximate solution to TSP, we will
show the greedy algorithm of the nearest neighbour on an example from the
book J. Pelikán, V. Chýna: Kvantitativní management.
The bakery in Kralupy supplies grocery shops in surrounding cities every day.
Find the order of stops of bakery car minimizing the total length of the route.
Distances between the cities are given by the table:
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza
Kralupy 0 4 16 8 18 25 17
Veltrusy 4 0 20 12 22 28 13
Slaný 16 20 0 12 7 14 17
Velvary 8 12 12 0 10 17 10
Zlonice 18 22 7 10 0 7 10
Vraný 25 28 14 17 7 0 15
Bˇríza 17 13 17 10 10 15 0
The nearest neighbour algorithm chooses the ﬁrst segment of the route
according to the shortest distance from the starting point. Next, we continue to
the next closest place and control for not closing the loop before we go
through all the places. We will get the route Kralupy - Veltrusy - Velvary -
travelling salesman problem - approximate solution
There are many heuristics for ﬁnding an approximate solution to TSP, we will
show the greedy algorithm of the nearest neighbour on an example from the
book J. Pelikán, V. Chýna: Kvantitativní management.
The bakery in Kralupy supplies grocery shops in surrounding cities every day.
Find the order of stops of bakery car minimizing the total length of the route.
Distances between the cities are given by the table:
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza
Kralupy 0 4 16 8 18 25 17
Veltrusy 4 0 20 12 22 28 13
Slaný 16 20 0 12 7 14 17
Velvary 8 12 12 0 10 17 10
Zlonice 18 22 7 10 0 7 10
Vraný 25 28 14 17 7 0 15
Bˇríza 17 13 17 10 10 15 0
The algorithm can give a better solution if we try to start the route from
another city. Initialization from Veltrusy leads to the route Veltrusy - Kralupy Velvary
- Zlonice - Slaný - Vraný - Bˇríza - Veltrusy with the total distance
4+8+10+ 7+ 14+15 +13 = 71 km.
travelling salesman problem - approximate solution
There are many heuristics for ﬁnding an approximate solution to TSP, we will
show the greedy algorithm of the nearest neighbour on an example from the
book J. Pelikán, V. Chýna: Kvantitativní management.
The bakery in Kralupy supplies grocery shops in surrounding cities every day.
Find the order of stops of bakery car minimizing the total length of the route.
Distances between the cities are given by the table:
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza
Kralupy 0 4 16 8 18 25 17
Veltrusy 4 0 20 12 22 28 13
Slaný 16 20 0 12 7 14 17
Velvary 8 12 12 0 10 17 10
Zlonice 18 22 7 10 0 7 10
Vraný 25 28 14 17 7 0 15
Bˇríza 17 13 17 10 10 15 0
Initialization from Veltrusy leads to the route Vraný -Zlonice - Slaný - Velvary Kralupy
- Veltrusy - Bˇríza -Vraný with the total distance 7+7+12+8+4+13 +15
= 66 km. It can be shown that this is even the shortest route.
travelling salesman problem - approximate solution
Another heuristics for TSP is the method of advantage numbers. It is based
on comparing the length of the route A1 − Ai − Aj − A1 and the sum of
distances A1 − Ai − A1, A1 − Aj − A1. The advantage number Sij is deﬁned as
their difference, it expresses the advantage of connecting Ai with Aj
comparing to two separate journeys from A1: Sij = c1i + c1j − cij .
We can compute the advantage matrix for a bakery example:
travelling salesman problem - approximate solution
Another heuristics for TSP is the method of advantage numbers. It is based
on comparing the length of the route A1 − Ai − Aj − A1 and the sum of
distances A1 − Ai − A1, A1 − Aj − A1. The advantage number Sij is deﬁned as
their difference, it expresses the advantage of connecting Ai with Aj
comparing to two separate journeys from A1: Sij = c1i + c1j − cij .
We can compute the advantage matrix for a bakery example:
Veltrusy Slaný Velvary Zlonice Vraný Bˇríza
Veltrusy X 0 0 0 1 8
Slaný 0 X 12 27 27 16
Velvary 0 12 X 16 16 15
Zlonice 0 27 16 X 36 25
Vraný 1 27 16 36 X 27
Bˇríza 8 16 15 25 27 X
The route is constructed sequentially starting from the largest advantage
numbers, controlling for not completing the circle too early. We got the route
Slaný - Zlonice - Vraný - Bˇríza - Velvary - Veltrusy. Kralupy are at the same
time starting and ending point, so the total distance is 16+7+7+15+10+12+4 =
71 km.
Integer programming
Special cases of LP include also integer programming problems. They are
standard LP problems with an additional condition that some variables or all
variables are integers (the ﬁrst case is referred to as
mixed integer programming ). These conditions usually follow directly from
the economic model, if the variables represent pieces of goods, number of
employees, number of repeating certain operation, etc. The variables may
often have range restricted to {0, 1} if they represent a decision, status,
presence of st., etc. We refer to those problems as
binary programming problems
Integer programming
Special cases of LP include also integer programming problems. They are
standard LP problems with an additional condition that some variables or all
variables are integers (the ﬁrst case is referred to as
mixed integer programming ). These conditions usually follow directly from
the economic model, if the variables represent pieces of goods, number of
employees, number of repeating certain operation, etc. The variables may
often have range restricted to {0, 1} if they represent a decision, status,
presence of st., etc. We refer to those problems as
binary programming problems and among their typical representatives can
be found an assignment problem, the TSP or the so-called knapsack problem:
Example: There is n indivisible items of different value and a knapsack of
limited capacity. The objective is to choose items of maximal total value, which
do not exceed the capacity of the knapsack.
Integer programming
Special cases of LP include also integer programming problems. They are
standard LP problems with an additional condition that some variables or all
variables are integers (the ﬁrst case is referred to as
mixed integer programming ). These conditions usually follow directly from
the economic model, if the variables represent pieces of goods, number of
employees, number of repeating certain operation, etc. The variables may
often have range restricted to {0, 1} if they represent a decision, status,
presence of st., etc. We refer to those problems as
binary programming problems and among their typical representatives can
be found an assignment problem, the TSP or the so-called knapsack problem:
Example: There is n indivisible items of different value and a knapsack of
limited capacity. The objective is to choose items of maximal total value, which
do not exceed the capacity of the knapsack.
Remark: Without the indivisibility assumption the problem would not be a
binary problem and its solution would be trivial: order items according to their
value/weight ratio and load the knapsack in that order until the capacity is not
full. If the last item cannot be loaded whole, cut it and load only part of it, so
that the weight limit is achieved.
Example of integer programming
Example: Textile company Style, l.t.d. is the producer of men’s fashion. Let’s
denote by x1 its week production of a suit "Marcel"and by x2 the same for a
suit "Filip". The time needed for producing one suit of type "Marcel"is 10 hours
and material costs are 400 CZK. The production of suit "Filip"takes 20 hours
and the material costs are 300 CZK. The company has been offered to supply
fashion for an international fair which takes place next week. Expected proﬁt
from selling respective suits is 20 EUR for "Marcel"and 30 EUR for "Filip".
Design an optimal production plan, if there are one full-time employee and
one half-time employee (that means 60 hours) available and on the stock,
there is a material of the value 1300 CZK.
Example of integer programming
Example: Textile company Style, l.t.d. is the producer of men’s fashion. Let’s
denote by x1 its week production of a suit "Marcel"and by x2 the same for a
suit "Filip". The time needed for producing one suit of type "Marcel"is 10 hours
and material costs are 400 CZK. The production of suit "Filip"takes 20 hours
and the material costs are 300 CZK. The company has been offered to supply
fashion for an international fair which takes place next week. Expected proﬁt
from selling respective suits is 20 EUR for "Marcel"and 30 EUR for "Filip".
Design an optimal production plan, if there are one full-time employee and
one half-time employee (that means 60 hours) available and on the stock,
there is a material of the value 1300 CZK.
Mathematical formulation of the problem is following: Maximize objective
function
z = 20x1 + 30x2
subject to
400x1 + 300x2 ≤ 1300
10x1 + 20x2 ≤ 60
x1, x2 ∈ {0, 1, 2, 3, . . .}
Integer programming- graphical representation
The model contains only two variables, so it is possible to solve it graphically.
Integer programming- graphical representation
The model contains only two variables, so it is possible to solve it graphically.
The feasible set consists of points with integer coordinates lying in the gray
polygon.
Integer programming- graphical representation
The model contains only two variables, so it is possible to solve it graphically.
The zero level curve of the proﬁt function.
Integer programming- graphical representation
The model contains only two variables, so it is possible to solve it graphically.
The highest level curve goes through the point [0, 3] which is the optimal
solution x∗
. We gain 3 · 30 = 90 EUR.
Integer programming- graphical representation
The model contains only two variables, so it is possible to solve it graphically.
Optimal solution of the relaxed problem (loosing the assumption on integer
range of variables) is xcel = [1, 6; 2, 2], corresponding optimal proﬁt is
zcel = 98 EUR.
Integer programming- graphical representation
The model contains only two variables, so it is possible to solve it graphically.
By rounding coordinates of xcel = [1, 6; 2, 2] we get the point [2, 2] that is not
feasible. If we round the ﬁrst coordinate down to [1, 2] instead, we get a
feasible point, but its proﬁt is only 20 + 2 · 30 = 80 EUR, which is signiﬁcantly
less than 90 EUR for x∗
.
Integer programming- methods
We could see on a previous example that the intuitive approach of neglecting
the integer type of variables in the model (this is called relaxed model) and
rounding the relaxed solution is not always suitable. That is why different
special procedures designed for integer problems are used. However, their
computations are more complicated and time-consuming, so common
computers can collapse even by solving relatively small tasks (tens of
variables and constraints).
Integer programming- methods
We could see on a previous example that the intuitive approach of neglecting
the integer type of variables in the model (this is called relaxed model) and
rounding the relaxed solution is not always suitable. That is why different
special procedures designed for integer problems are used. However, their
computations are more complicated and time-consuming, so common
computers can collapse even by solving relatively small tasks (tens of
variables and constraints).
Cutting Hyperplane Methods (such as Gomory algorithm) search for the
optimum of the relaxed problem and then add another restriction that cuts off
the non-integer optimal point. These methods are quite old and less used
nowadays.
pause Combinatorial methods are based on an effective scan of the feasible
set, which, for purely integer problems, usually contains ﬁnite but great
number of elements. In program systems, the branch and bound method ( ie
B & B) is most often used.
pause Special methods are used for problems with a special structure,
including different heuristics for a TSP or the Hungarian method for the
Integer programming- method B & B
The feasible set is sequentially divided into smaller parts (branching), where
we ﬁnd the upper bound (the lower bound when minimizing) of the objective
function (bounding). This allows estimating subsets where the optimum
probably could be and subsets where it cannot occur.
Integer programming- method B & B
The feasible set is sequentially divided into smaller parts (branching), where
we ﬁnd the upper bound (the lower bound when minimizing) of the objective
function (bounding). This allows estimating subsets where the optimum
probably could be and subsets where it cannot occur.
Branching is done by solving a relaxed linear program - its feasible set is
labelled by M0. If the optimal solution x0
of this relaxation is an integer, it is
also a solution to the original integer problem. Else we choose an index i, for
which i-th coordinate of the solution x0
i is not an integer and we construct
additional constraints xi ≤ a or xi ≥ b, where a, b are integers surrounding xi .
By that is the set M0 divided into subsets M1 and M2.
Integer programming- method B & B
The feasible set is sequentially divided into smaller parts (branching), where
we ﬁnd the upper bound (the lower bound when minimizing) of the objective
function (bounding). This allows estimating subsets where the optimum
probably could be and subsets where it cannot occur.
Branching is done by solving a relaxed linear program - its feasible set is
labelled by M0. If the optimal solution x0
of this relaxation is an integer, it is
also a solution to the original integer problem. Else we choose an index i, for
which i-th coordinate of the solution x0
i is not an integer and we construct
additional constraints xi ≤ a or xi ≥ b, where a, b are integers surrounding xi .
By that is the set M0 divided into subsets M1 and M2.
On each of subsets M1 and M2 we ﬁnd optima x1
and x2
and compute their
objective values z1
and z2
. By rounding downward these values we get upper
bounds of objective functions on the sets M1 and M2. The whole algorithm
proceeds until its termination in one of the following cases:
integer solution is found in a branch or
there is no feasible solution in a branch or
non-integer optimal solution is found in a branch whose objective value is
worse than the value of an integer point in a different branch.
Integer programming - method B & B
Lets demonstrate the B & B method for a textile company example.
Integer programming - method B & B
Lets demonstrate the B & B method for a textile company example.
We have a solution of the relaxed problem, x0
= xcel = [1, 6; 2, 2]. Its ﬁrst
coordinate is not integer, so we introduce the constraints x1 ≥ 2 and x1 ≤ 1
respectively, thus dividing the feasible set into the M1 and the M2.
Integer programming - method B & B
Lets demonstrate the B & B method for a textile company example.
On the feasible set M1, the optimum is achieved at x1
= [2; 5
3 ] and on the M2,
it is x2
= [1; 5
2 ]. Their values are z1
= 90 and z2
= 95, which determines the
upper bounds for M1 and M2.
Integer programming - method B & B
Lets demonstrate the B & B method for a textile company example.
The upper bound of M2 is higher, so we continue by dividing this set. The
second coordinate of x2
is equal to 5
2 , so we introduce the constraint x2 ≤ 2 or
x2 ≥ 3 into the model, thus we get new feasible sets M3 and M4 (which
consists of only one element).
Integer programming - method B & B
Lets demonstrate the B & B method for a textile company example.
Solutions x3
and x4
are both integers, their objective values are z3
= 80 and
z4
= 90. The algorithm terminates, in no branch better value than 90 EUR
(that is gained for x4
= [0, 3]) cannot be achieved.
Integer programming - method B & B
Lets demonstrate the B & B method for a textile company example.
We can draw a scheme of the solution procedure.
Optimization on graphs
A lot of real-world systems can be represented by planar graphs (e.g.
distribution network, project activities, etc.). A graph consists of the nodes,
labelled by u1, . . . , un and the edges, the edge connecting ui and uj is denoted
by hij . We can represent a graph visually using points (circles) for the nodes
and edges as lines connecting them. We distinguish between undirected
edges allowing movement in both directions and directed edges, where the
orientation is depicted by an arrow. If there are no directed edges in the
graph, it is called undirected, else it is directed. Both above-mentioned types
of graphs are shown in the following picture.
Optimization on graphs
The path from the node ui to uj is the sequence of successive edges, where
the ﬁrst one is starting in ui and the last one is ending in uj . If the orientation
of the edges is respected, then the path is directed (else it is undirected). We
can see a directed path from the node 1 to the node 6. There are only
undirected paths going from 6 to 1.
Optimization on graphs
The path from the node ui to uj is the sequence of successive edges, where
the ﬁrst one is starting in ui and the last one is ending in uj . If the orientation
of the edges is respected, then the path is directed (else it is undirected). We
can see a directed path from the node 1 to the node 6. There are only
undirected paths going from 6 to 1.
The path that has the same starting node as the end point ui = uj is called a
cycle, or in the case of an undirected graph, a circle. The graph in the picture
contains circles, for example, 1 − 3 − 4 − 1. If there is at least one undirected
path between every two nodes, we call the graph connected. Every connected
undirected graph that does not contain a circle is called the tree.
Optimization on graphs
Optimization on graphs involves weighted graphs. We assign edges weights
according to their economic meaning (distances of distribution centres, costs
on the transport of goods between them, etc.). A connected directed weighted
graph with two special nodes (the source and the target) is called a network. If
we assign weights to edges of the graph from our example, we get a network
with the source in the node 1 and the target in the node 6.
Optimization on graphs
Optimization on graphs involves weighted graphs. We assign edges weights
according to their economic meaning (distances of distribution centres, costs
on the transport of goods between them, etc.). A connected directed weighted
graph with two special nodes (the source and the target) is called a network. If
we assign weights to edges of the graph from our example, we get a network
with the source in the node 1 and the target in the node 6.
The path length is the sum of its edges weights. For example, the length of the
directed path 1-2-5-6 is 3+7+6=16. Caution! A weighted graph is deﬁned by
the set of its nodes, edges and their weights, not by its graphical
representation. Distances between the nodes do not need to correspond to
weights of edges connecting them.
Optimization on graphs - problems
We can deﬁne many optimization problems on graphs:
A standard problem is represented by looking for the shortest path
between two nodes. The problem is deﬁned on directed as well as
undirected graphs. There are many algorithms for solving this problem,
one of the best known is the Dijkstra algorithm.
Looking for a minimal spanning tree of the graph - the task is to choose
such subset of edges, that each pair of nodes is connected and their total
weight is minimal (so the spanning tree cannot contain cycles).
Determining maximal ﬂow in a network: If the weights of edges in a
network represent capacities, we try to ﬁnd a maximal number of units
that can be transported from a source to a ﬁnal node.
Other problems, as colouring the graph, Chinese postman problem,
travelling salesman problem, ﬁnding the median of a graph and the centre
of a graph, etc.
Optimization on graphs - minimal spanning tree
For determining minimal spanning tree of the graph we can use a Kruskal
algorithm: We form a subgraph by sequentially including edges with minimal
weights until all the nodes are connected. We have to avoid forming a cycle:
those edges that would complete the cycle are not included.
Example: Find a minimal spanning tree of a graph from T. Šubrt:
Ekonomicko-matematické metody:
Optimization on graphs - minimal spanning tree
For determining minimal spanning tree of the graph we can use a Kruskal
algorithm: We form a subgraph by sequentially including edges with minimal
weights until all the nodes are connected. We have to avoid forming a cycle:
those edges that would complete the cycle are not included.
Example: Find a minimal spanning tree of a graph from T. Šubrt:
Ekonomicko-matematické metody:
First we choose the edge of weight 1.
Optimization on graphs - minimal spanning tree
For determining minimal spanning tree of the graph we can use a Kruskal
algorithm: We form a subgraph by sequentially including edges with minimal
weights until all the nodes are connected. We have to avoid forming a cycle:
those edges that would complete the cycle are not included.
Example: Find a minimal spanning tree of a graph from T. Šubrt:
Ekonomicko-matematické metody:
Then we add all edges with weight 2.
Optimization on graphs - minimal spanning tree
For determining minimal spanning tree of the graph we can use a Kruskal
algorithm: We form a subgraph by sequentially including edges with minimal
weights until all the nodes are connected. We have to avoid forming a cycle:
those edges that would complete the cycle are not included.
Example: Find a minimal spanning tree of a graph from T. Šubrt:
Ekonomicko-matematické metody:
We add edges of weight 3 with the exception of v3-v4 which would close the
circle.
Optimization on graphs - minimal spanning tree
For determining minimal spanning tree of the graph we can use a Kruskal
algorithm: We form a subgraph by sequentially including edges with minimal
weights until all the nodes are connected. We have to avoid forming a cycle:
those edges that would complete the cycle are not included.
Example: Find a minimal spanning tree of a graph from T. Šubrt:
Ekonomicko-matematické metody:
The edge weighted 6 cannot be included in the spanning tree, so we choose
the edge weighted 7 instead.
Optimization on graphs - minimal spanning tree
For determining minimal spanning tree of the graph we can use a Kruskal
algorithm: We form a subgraph by sequentially including edges with minimal
weights until all the nodes are connected. We have to avoid forming a cycle:
those edges that would complete the cycle are not included.
Example: Find a minimal spanning tree of a graph from T. Šubrt:
Ekonomicko-matematické metody:
We have obtained a connected subgraph, so it is the sought minimal spanning
tree (of total value 20).
Optimization on graphs - the shortest path
For ﬁnding the shortest path between the v1 and other nodes we can use a
Dijkstra algorithm: Let us show it on a graph from the previous example:
Optimization on graphs - the shortest path
For ﬁnding the shortest path between the v1 and other nodes we can use a
Dijkstra algorithm: Let us show it on a graph from the previous example:
An algorithm divides nodes into two groups according to whether we already
know their distance from v1 or not. We begin with the path of the length 0 from
v1 to v1. In every step, we check all edges connecting a node from the
„known distance“ group with the node from the other group and choose that
one minimizing the sum of the distance and the weight of the edge; this
minimal sum is the distance to a new node. This node now moves to the
group with the known distance from v1. The procedure is repeated until all the
Optimization on graphs - the shortest path
We can follow the steps of the algorithm in a table of neighbours (the weights
of edges are in brackets):
neighbours v1 v2 v3 v4 v5 v6 v7 v8
v2 (7) v1 (7) v1 (9) v1 (8) v2 (8) v2 (2) v5 (10) v5 (7
v3 (9) v3 (10) v2 (10) v2 (3) v3 (6) v3 (10) v6 (3) v6 (2
v4 (8) v4 (3) v4 (3) v3 (3) v4 (3) v4 (2) v8 (1) v7 (1
v5 (8) v5 (6) v5 (3) v6 (10) v5 (10)
v6 (2) v6 (10) v6 (2) v7 (9) v7 (3)
v8 (7) v8 (2)
dist. from v1 0
In the ﬁrst step we know only the distance to v1, so we go through its
neighbours and choose the edge with the least weight, which is v1-v2
weighting 7. So the node v2 can be moved to the group with a known distance
from v1.
Optimization on graphs - the shortest path
We can follow the steps of the algorithm in a table of neighbours (the weights
of edges are in brackets):
neighbours v1 v2 v3 v4 v5 v6 v7 v8
v2 (7) v1 (7) v1 (9) v1 (8) v2 (8) v2 (2) v5 (10) v5 (7
v3 (9) v3 (10) v2 (10) v2 (3) v3 (6) v3 (10) v6 (3) v6 (2
v4 (8) v4 (3) v4 (3) v3 (3) v4 (3) v4 (2) v8 (1) v7 (1
v5 (8) v5 (6) v5 (3) v6 (10) v5 (10)
v6 (2) v6 (10) v6 (2) v7 (9) v7 (3)
v8 (7) v8 (2)
dist. from v1 0 7
In the second step we check the neighbours of v1 and also of v2, lengths of
paths going through v2 are 7+10, 7+3, 7+8, 7+2, so the new node with a
known distance from v1 is v4, because the length of v1-v4 is 8.
Optimization on graphs - the shortest path
We can follow the steps of the algorithm in a table of neighbours (the weights
of edges are in brackets):
neighbours v1 v2 v3 v4 v5 v6 v7 v8
v2 (7) v1 (7) v1 (9) v1 (8) v2 (8) v2 (2) v5 (10) v5 (7
v3 (9) v3 (10) v2 (10) v2 (3) v3 (6) v3 (10) v6 (3) v6 (2
v4 (8) v4 (3) v4 (3) v3 (3) v4 (3) v4 (2) v8 (1) v7 (1
v5 (8) v5 (6) v5 (3) v6 (10) v5 (10)
v6 (2) v6 (10) v6 (2) v7 (9) v7 (3)
v8 (7) v8 (2)
dist. from v1 0 7 8
In the next step we check all neighbours of v1, v2 and v4 with unknown
distance from v1. The shortest path through these nodes to their neighbours
is v1-v3 with the length equal to 9. So this is the distance from v1 to v3.
Optimization on graphs - the shortest path
We can follow the steps of the algorithm in a table of neighbours (the weights
of edges are in brackets):
neighbours v1 v2 v3 v4 v5 v6 v7 v8
v2 (7) v1 (7) v1 (9) v1 (8) v2 (8) v2 (2) v5 (10) v5 (7
v3 (9) v3 (10) v2 (10) v2 (3) v3 (6) v3 (10) v6 (3) v6 (2
v4 (8) v4 (3) v4 (3) v3 (3) v4 (3) v4 (2) v8 (1) v7 (1
v5 (8) v5 (6) v5 (3) v6 (10) v5 (10)
v6 (2) v6 (10) v6 (2) v7 (9) v7 (3)
v8 (7) v8 (2)
dist. from v1 0 7 9 8
The path to v6 through v2 is of the same length (9).
Optimization on graphs - the shortest path
We can follow the steps of the algorithm in a table of neighbours (the weights
of edges are in brackets):
neighbours v1 v2 v3 v4 v5 v6 v7 v8
v2 (7) v1 (7) v1 (9) v1 (8) v2 (8) v2 (2) v5 (10) v5 (7
v3 (9) v3 (10) v2 (10) v2 (3) v3 (6) v3 (10) v6 (3) v6 (2
v4 (8) v4 (3) v4 (3) v3 (3) v4 (3) v4 (2) v8 (1) v7 (1
v5 (8) v5 (6) v5 (3) v6 (10) v5 (10)
v6 (2) v6 (10) v6 (2) v7 (9) v7 (3)
v8 (7) v8 (2)
dist. from v1 0 7 9 8 9
We try to prolong certain path to a node with unknown distance from v1. The
minimum length we can get by adding one edge is 11 for the path to v5 via v4.
Optimization on graphs - the shortest path
We can follow the steps of the algorithm in a table of neighbours (the weights
of edges are in brackets):
neighbours v1 v2 v3 v4 v5 v6 v7 v8
v2 (7) v1 (7) v1 (9) v1 (8) v2 (8) v2 (2) v5 (10) v5 (7
v3 (9) v3 (10) v2 (10) v2 (3) v3 (6) v3 (10) v6 (3) v6 (2
v4 (8) v4 (3) v4 (3) v3 (3) v4 (3) v4 (2) v8 (1) v7 (1
v5 (8) v5 (6) v5 (3) v6 (10) v5 (10)
v6 (2) v6 (10) v6 (2) v7 (9) v7 (3)
v8 (7) v8 (2)
dist. from v1 0 7 9 8 11 9
The path of the same length 11 can be achieved by connecting v8 through v6.
Optimization on graphs - the shortest path
We can follow the steps of the algorithm in a table of neighbours (the weights
of edges are in brackets):
neighbours v1 v2 v3 v4 v5 v6 v7 v8
v2 (7) v1 (7) v1 (9) v1 (8) v2 (8) v2 (2) v5 (10) v5 (7
v3 (9) v3 (10) v2 (10) v2 (3) v3 (6) v3 (10) v6 (3) v6 (2
v4 (8) v4 (3) v4 (3) v3 (3) v4 (3) v4 (2) v8 (1) v7 (1
v5 (8) v5 (6) v5 (3) v6 (10) v5 (10)
v6 (2) v6 (10) v6 (2) v7 (9) v7 (3)
v8 (7) v8 (2)
dist. from v1 0 7 9 8 11 9 11
Finally, we attach the node v7; the shortest way how to do it is via v6. The
total distance is 12.
Optimization on graphs - the median of a graph
The median of a graph is the node minimizing the sum of distances from
other nodes. We use a graph from the example on TSP, but now we want
choose the city, which is the most suitable location for a central depot.
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza SUM
Kralupy 0 4 16 8 18 25 17 88
Veltrusy 4 0 20 12 22 28 13 99
Slaný 16 20 0 12 7 14 17 86
Velvary 8 12 12 0 10 17 10 69
Zlonice 18 22 7 10 0 7 10 74
Vraný 25 28 14 17 7 0 15 106
Bˇríza 17 13 17 10 10 15 0 82
Optimization on graphs - the median of a graph
The median of a graph is the node minimizing the sum of distances from
other nodes. We use a graph from the example on TSP, but now we want
choose the city, which is the most suitable location for a central depot.
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza SUM
Kralupy 0 4 16 8 18 25 17 88
Veltrusy 4 0 20 12 22 28 13 99
Slaný 16 20 0 12 7 14 17 86
Velvary 8 12 12 0 10 17 10 69
Zlonice 18 22 7 10 0 7 10 74
Vraný 25 28 14 17 7 0 15 106
Bˇríza 17 13 17 10 10 15 0 82
In order to minimize the total distance to the depot, we should locate it in
Velvary.
Comment: When locating two depots we speak about the double median, etc.
Optimization on graphs - the centre of a graph
The centre of a graph is the node minimizing maximal distance from other
nodes. Let us show it on the same example as before, but now we want to
choose location for a ﬁremen station.
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza MAX
Kralupy 0 4 16 8 18 25 17 25
Veltrusy 4 0 20 12 22 28 13 28
Slaný 16 20 0 12 7 14 17 20
Velvary 8 12 12 0 10 17 10 17
Zlonice 18 22 7 10 0 7 10 22
Vraný 25 28 14 17 7 0 15 28
Bˇríza 17 13 17 10 10 15 0 17
Optimization on graphs - the centre of a graph
The centre of a graph is the node minimizing maximal distance from other
nodes. Let us show it on the same example as before, but now we want to
choose location for a ﬁremen station.
Kralupy Veltrusy Slaný Velvary Zlonice Vraný Bˇríza MAX
Kralupy 0 4 16 8 18 25 17 25
Veltrusy 4 0 20 12 22 28 13 28
Slaný 16 20 0 12 7 14 17 20
Velvary 8 12 12 0 10 17 10 17
Zlonice 18 22 7 10 0 7 10 22
Vraný 25 28 14 17 7 0 15 28
Bˇríza 17 13 17 10 10 15 0 17
The best location for a ﬁremen station is Velvary or Bˇríza, because every city
is at most 17 km far from them.
Remark: When locating two stations, we speak about a double centre, etc.
Optimization on networks
A common problem solved on networks is the maximal ﬂow problem (on
waterworks, conduction, road or data network,etc.). The problem must be
stated in terms of:
the network description (a graph, usually directed)
where does the ﬂow start (a special node called the source)
which is the ﬁnal node (a target)
How much of the medium can go through the edges (capacities =
non-negative weights of edges)
A graph described above is called the network.
Optimization on networks
A common problem solved on networks is the maximal ﬂow problem (on
waterworks, conduction, road or data network,etc.). The problem must be
stated in terms of:
the network description (a graph, usually directed)
where does the ﬂow start (a special node called the source)
which is the ﬁnal node (a target)
How much of the medium can go through the edges (capacities =
non-negative weights of edges)
A graph described above is called the network.
A ﬂow on a network is a function assigning every edge a non-negative
number less or equal to its capacity. This function has to fulﬁl the so-called
Kirchhoff’s law: The sum of the ﬂows on entering edges is equal to the sum of
the ﬂows on leaving edges for every node except the source and the target.
The ﬂow size is the sum of ﬂows entering the target. Zero ﬂow means that
nothing goes through the network (every edge is assigned a zero value).
Optimization on networks
The problem of maximal ﬂow can be solved by an improving algorithm: we
start with zero ﬂow and look for an improving path (every edge of this path has
nonzero reserve - that means the difference between the capacity and the
actual ﬂow on the edge). The ﬂow on the path can be increased by the
minimal reserve of its edges. We follow by looking for another improving path.
However, this approach need not lead to an optimal solution, sometimes we
have to decrease ﬂow on some edges in order to obtain higher total ﬂow.
Optimization on networks
The problem of maximal ﬂow can be solved by an improving algorithm: we
start with zero ﬂow and look for an improving path (every edge of this path has
nonzero reserve - that means the difference between the capacity and the
actual ﬂow on the edge). The ﬂow on the path can be increased by the
minimal reserve of its edges. We follow by looking for another improving path.
However, this approach need not lead to an optimal solution, sometimes we
have to decrease ﬂow on some edges in order to obtain higher total ﬂow.
Better results are gained by applying following Ford-Fulkerson algorithm:
For each edge, we monitor its reserve as well as its reverse reserve (how
much the ﬂow can be decreased). In the beginning, reserves on all edges
are equal to their capacities (and reverse reserves of directed edges are
zero).
We ﬁnd an improving path and increase its ﬂow by its reserve. At the
same time, we decrease reserves of all edges on the path and increase
their reverse reserves.
We proceed until there is no path with nonzero reserve.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
We start with zero ﬂow, we denote reserves by blue numbers on edges and
reverse reserves by green numbers.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
We ﬁnd an improving path.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
Minimal reserve on this path is 6, so we add this number to the current ﬂow on
the path. Reserves of all involved edges drop by 6, simultaneously all their
reverse reserves increase by the same number.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
We ﬁnd another improving path.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
There is an edge with a reserve equal to 5 on this path, so we cannot improve
the ﬂow more than that.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
For increasing total ﬂow we ﬁnd another path with nonzero reserve.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
We increased ﬂow on the path by 7.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
There is also an improving path with reserve 1.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
We increased the ﬂow.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
We can improve the ﬂow on the path that goes between v5 and v7 in reverse
direction.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
We increase the ﬂow by a minimal reserve of this path (1, on the last edge).
The size of the ﬂow on the edge connecting v5 and v7 is decreased by 1.
Maximal ﬂow in network: Ford-Fulkerson algorithm
Let’s apply Ford-Fulkerson algorithm for determining maximal ﬂow in a given
network:
Total size of the resulting ﬂow is 7+8 +5=20 (see green numbers on edges
entering the target). This must be the optimal solution, there is no free
capacity left.
Project management
A typical application area for application of graph algorithms is project
management. Generally, a project can be understood as a set of activities and
connections between them. The activities are characterized by their expected
duration, costs, requirements on conditions of their realization, their
predecessors, etc. Usually, we try to ﬁnd answers to these questions:
What is the shortest possible time for a realization of the project?
Which are the key activities for ﬁnishing the project on time, i.e. critical
activities?
What time reserves do we have for the other activities?
How to prepare the time schedule for the project execution?
Besides the time analysis of a project, we are interested in the cost analysis
(costs differ according to project duration). We can also explore time
distribution of the resources needed for the individual activities.
Project management - construction of a project
network
The project can be visualized by a network graph, where the edges represent
the activities, their weights are equal to durations of the activities and nodes
correspond to the moments of starting or ﬁnishing the activities. First, we have
to deﬁne the activities, estimate their durations and specify the order of
activities by a list of activity predecessors.
Project management - construction of a project
network
The project can be visualized by a network graph, where the edges represent
the activities, their weights are equal to durations of the activities and nodes
correspond to the moments of starting or ﬁnishing the activities. First, we have
to deﬁne the activities, estimate their durations and specify the order of
activities by a list of activity predecessors. Let us show the network of an
example from J.Jablonský: Operaˇcní výzkum: Construct the graph of a project
of launching a new business centre for Q-mark company which is deﬁned by
elementary activities and their characteristics, see the table:
activity activity description duration [weeks] predecessors
A project kick off 6 B
processing the project 4 A
C hiring management 3 A
D hiring staff 3 B,C
E reconstruction and the equipment 8 B
F staff training 2 D
G selection of goods 2 B,C
H contracts with suppliers 5 G
I ordering goods 3 E,F,H
J marketing campaign 2 H
Project management - construction of a project
network
When constructing a graph we may face difﬁculties with the deﬁnition of
nodes. For example, we have to ﬁnish B and C before D, but at the same time,
B is the predecessor of E, while C is not. How to capture the right order of
activities? Examples of an incorrect representation are in the following ﬁgure:
Similar situation occurs for activities I,J that have a common predecessor H,
but there are two more predecessors E and F for I.
Project management - construction of a project
network
The above-mentioned issues can be solved by introducing dummy activities
with corresponding dummy edges that supplement missing connections. We
denote them by dashed lines. The duration of a dummy task is always zero. In
our example we need two dummy activities: X representing the relation
between B and D and a dummy activity Y for H and I.
Project management - construction of a project
network
The above-mentioned issues can be solved by introducing dummy activities
with corresponding dummy edges that supplement missing connections. We
denote them by dashed lines. The duration of a dummy task is always zero. In
our example we need two dummy activities: X representing the relation
between B and D and a dummy activity Y for H and I. One of the possible
ways of constructing the graph is in the ﬁgure:
There is a golden rule for constructing a project network: always try to number
the nodes in such a way that every edge goes from the node with a lesser
index to the node with a higher index. Then the graph doesn’t contain any
Critical Path Method (CPM)
The method CPM was developed in the ﬁfties of the last century. It is based
on computing four characteristics for every activity:
The earliest start of the activities beginning in the node ui ; we denote it
by t0
i
The earliest ﬁnish of activity represented by the edge hij ; we compute it
by adding the duration of the task: t0
i + yij
The latest ﬁnish of activities on edges going to uj ; we label it by t1
j
The latest start of activity represented by the edge hij is computed by
subtracting its duration: t1
j − yij
Let’s mark all the nodes in a project network by the earliest start and latest
ﬁnish of activities going from/to them:
Critical Path Method (CPM)
The algorithm comprises of four phases:
1 a computation of earliest starts: For activities beginning at uj we ﬁnd
maxima of earliest ﬁnishes of entering activities: t0
j = maxi (t0
i + yij ) For
the last node we obtain the earliest ﬁnish of the whole project.
2 a computation of latest ﬁnishes: For activities ending at ui we ﬁnd minima
of latest starts of following activities. t1
i = minj (t1
j − yij )
3 a computation of total time reserves: Activity represented by the edge hij
cannot start earlier than t0
i and shall not ﬁnish later than t1
j . The time
window for its realization is t1
j − t0
i and because its duration is yij , we get
formula for its time reserve: Rij = t1
j − t0
i − yij
4 a construction of the time schedule
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
First lets have a look on the graph with the durations of activities.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
The earliest start of tasks B and C is t0
2 = 0 + 6 = 6.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
The earliest start of E is t0
3 = 6 + 4 = 10.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
The earliest start of activities D and G is t0
4 = max(10 + 0, 6 + 3) = 10.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
The earliest start of F is t0
5 = 10 + 3 = 13 and for H it is t0
6 = 10 + 2 = 12.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
The earliest start of task J is t0
7 = 12 + 5 = 17.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
The earliest start of task I is t0
8 = max(10 + 8, 13 + 2, 17 + 2) = 18.
Critical Path Method (CPM) - 1st phase
In the ﬁrst phase of CPM we go through the graph from the left to the right
and compute earliest starts of all activities.
We have gone through the whole network. The project cannot ﬁnish earlier
than in t0
9 = max(18 + 3, 17 + 2) = 21 weeks.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
If we insist on ﬁnishing the whole project in 21 weeks, the activities I andJ
shouldn’t ﬁnish later than t1
9 = 21.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
The latest ﬁnish of activities F and E is t1
8 = 21 − 3 = 18.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
The latest ﬁnish of the task H is t1
7 = min(21 − 2, 18 − 0) = 18.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
The latest ﬁnish of the task D is t1
5 = 18 − 2 = 16 and for G it is
t1
6 = 18 − 5 = 13.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
The latest ﬁnish of the activity C is t1
4 = min(13 − 2, 16 − 3) = 11.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
The latest ﬁnish of task B is t1
3 = min(18 − 8, 11 − 0) = 10.
Critical Path Method (CPM) - 2nd phase
In the second phase we proceed from the right to the left and compute the
latest ﬁnish for every node. We assume that the project should be completed
in the shortest time, that is in 21 weeks.
The latest ﬁnish of the ﬁrst activity A is t1
2 = min(10 − 4, 11 − 3) = 6. It is not
surprising that t1
1 = 6 − 6 = 0, as we insisted on the shortest possible
realization time.
Critical Path Method (CPM) - 3rd phase
We compute time reserves of the activities according to the formula
Rij = t1
j − t0
i − yij . For example, the time window for a task J is between 17th
and 21th week and its realization lasts two weeks, so its reserve is
R79 = 21 − 17 − 2 = 2 weeks, etc.
We supplied the edges with time reserves (the numbers in brackets). The
critical path consists of activities with zero reserve, A,B,E,I; they are
highlighted by a red colour.
Critical Path Method (CPM) - 4th phase
The last but not least phase is creating the project schedule. It is necessary to
decide which activities can be realized simultaneously with regard to the
possibility of sharing resources needed for individual tasks. In the ﬁgure we
can see the timing diagram (it is called a Gantt chart) for our example, earliest
starts and latest ﬁnishes of the tasks are represented by the frames and the
duration is highlighted by shading. Critical activities with zero time reserves
are placed in the upper part of the table. Those activities have to be realized
immediately one after another unless the project is delayed.
Činnost Čas
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
A
B
E
I
C
D
F
G
H
J
Method PERT
The method PERT (Program Evaluation and Review Technique) is a
probabilistic extension of the CPM method. In reality, it is often impossible to
specify exact duration of activities, so in the PERT the values yij are replaced
by random variables with supports aij , bij . The bounds represent optimistic
and pessimistic estimates of the duration. By mij we denote the most likely,
the modal estimate.
Method PERT
The method PERT (Program Evaluation and Review Technique) is a
probabilistic extension of the CPM method. In reality, it is often impossible to
specify exact duration of activities, so in the PERT the values yij are replaced
by random variables with supports aij , bij . The bounds represent optimistic
and pessimistic estimates of the duration. By mij we denote the most likely,
the modal estimate. As we generally don’t know the probability distribution of
the random variables, we approximate it usually by a β-distribution. There are
following formulas for its mean and variance:
µij =
aij +4mij +bij
6
σij =
bij −aij
6
Method PERT
The method PERT (Program Evaluation and Review Technique) is a
probabilistic extension of the CPM method. In reality, it is often impossible to
specify exact duration of activities, so in the PERT the values yij are replaced
by random variables with supports aij , bij . The bounds represent optimistic
and pessimistic estimates of the duration. By mij we denote the most likely,
the modal estimate. As we generally don’t know the probability distribution of
the random variables, we approximate it usually by a β-distribution. There are
following formulas for its mean and variance:
µij =
aij +4mij +bij
6
σij =
bij −aij
6
The algorithm of the PERT method doesn’t differ from the CPM, with the
exception that durations yij are substituted by their means µij . If certain
conditions are met, we can use the central limit theorem and estimate the total
time of project realization by a Gaussian random variable. This allows us to
answer questions such as: What is the probability of ﬁnishing project in a
certain time, what total time of ﬁnishing corresponds to a probability p, etc.
Method PERT - example
Example : A company plans to reconstruct its manufacturing plant including
replacement of the production equipment, construction work, overhaul of the
wiring, etc. Individual activities of the project together with their expected
durations in weeks (optimistic/modal/pessimistic) are in the table. Use method
PERT for determining the critical path.
Activity description predecessors aij mij bij
A Dismantling old equipment - 5 8 10
B Repairing the roof of the production hall - 4 6 7
C Floor Repair A 1 2 5
D Interior design B,C 2 4 6
E Overhaul of wiring D 7 10 14
F Installation New Production Equipment E 10 12 13
G Installation of air conditioning E 4 5 8
H Testing F 3 4 6
I Completing G 1 3 5
Method PERT - example
Solution: We compute means and variances:
(i, j) aij mij bij µij σ2
ij
A(1,2) 5 8 10 7,83 0,69
B(1,3) 4 6 7 5,83 0,25
C(2,3) 1 2 5 2,33 0,44
D(3,4) 2 4 6 4,00 0,44
E(4,5) 7 10 14 10,17 1,36
F(5,6) 10 12 13 11,83 0,25
G(5,7) 4 5 8 5,33 0,44
H(6,8) 3 4 6 4,17 0,25
I(7,8) 1 3 5 3,00 0,44
Method PERT - example
Solution: We compute means and variances:
(i, j) aij mij bij µij σ2
ij
A(1,2) 5 8 10 7,83 0,69
B(1,3) 4 6 7 5,83 0,25
C(2,3) 1 2 5 2,33 0,44
D(3,4) 2 4 6 4,00 0,44
E(4,5) 7 10 14 10,17 1,36
F(5,6) 10 12 13 11,83 0,25
G(5,7) 4 5 8 5,33 0,44
H(6,8) 3 4 6 4,17 0,25
I(7,8) 1 3 5 3,00 0,44
The critical path of simple projects can be determined by checking all the
paths connecting the source and target node in the project network (there are
four of them in our example). Instead of exact times, we consider their
expected values. For every path, we compute the total time of its realization
as the sum of the means of durations of activities lying on the path. We sum
also individual variances in order to achieve the total variance on the path.
The path with the maximal mean of total time is the critical path, in our
example it is A, C, D, E, F, H.
Method PERT - example
critical path aij mij bij µij σ2
ij
A(1,2) 5 8 10 7,83 0,69
C(2,3) 1 2 5 2,33 0,44
D(3,4) 2 4 6 4,00 0,44
E(4,5) 7 10 14 10,17 1,36
F(5,6) 10 12 13 11,83 0,25
H(6,8) 3 4 6 4,17 0,25
40, 33 3, 43
Method PERT - example
critical path aij mij bij µij σ2
ij
A(1,2) 5 8 10 7,83 0,69
C(2,3) 1 2 5 2,33 0,44
D(3,4) 2 4 6 4,00 0,44
E(4,5) 7 10 14 10,17 1,36
F(5,6) 10 12 13 11,83 0,25
H(6,8) 3 4 6 4,17 0,25
40, 33 3, 43
Total project duration T is a random variable with the mean µ(T) = 40, 33
weeks and the variance σ2
(T) = 3, 43 weeks. For projects with a large
number of activities, probabilistic computations are performed under the
assumption that their durations are independent random variables. According
to the central limit theorem, the probability distribution of T, which is the sum
of independent variables tij , converges to the normal distribution
N(µ(T), σ2
(T)) .
Probability of ﬁnishing in the planned time Tpl
This probability is computed from the cumulative distribution function φ(u) of
standard normal distribution N(0; 1). First we have to standardize random
variable T according to the formula U = T−µ(T)
σ(T)) ∼ N(0; 1). So
P(T ≤ Tpl ) = φ
Tpl −µ(T)
σ(T) .
Probability of ﬁnishing in the planned time Tpl
This probability is computed from the cumulative distribution function φ(u) of
standard normal distribution N(0; 1). First we have to standardize random
variable T according to the formula U = T−µ(T)
σ(T)) ∼ N(0; 1). So
P(T ≤ Tpl ) = φ
Tpl −µ(T)
σ(T) .
If the planned realization time is shorter than the mean duration of the
project (Tpl ≤ µ(T)), then the argument of function φ(u) is negative. We
can determine its value from the tables of standard normal cdf using
formula φ(u) = 1 − φ(−u). The probability of completing the project in
time Tpl is less than 50%.
If the planned realization time is equal to the mean duration of the project
(Tpl = µ(T)), the probability of completing the project in time is exactly
50%.
If the planned realization time is longer than mean duration of the project
(Tpl ≥ µ(T)), the probability of completing the project in time is greater
than 50%.
Determining the time of project termination in time Tr
for a given risk r
This problem can be solved using tables of standard normal cdf φ(u). If the
risk r is given in per cent, we have to ﬁnd a quantile u1−r/100. Corresponding
time Tr is derived from the formula u1−r/100 = Tr −µ(T)
σ(T) : after some algebra, we
have Tr = µ(T) + σ(T) · u1−r/100
Determining the time of project termination in time Tr
for a given risk r
This problem can be solved using tables of standard normal cdf φ(u). If the
risk r is given in per cent, we have to ﬁnd a quantile u1−r/100. Corresponding
time Tr is derived from the formula u1−r/100 = Tr −µ(T)
σ(T) : after some algebra, we
have Tr = µ(T) + σ(T) · u1−r/100
Example : Let’s consider the previous example with expected project
duration equal to 40,33 weeks and variance of 3,43.
Determining the time of project termination in time Tr
for a given risk r
This problem can be solved using tables of standard normal cdf φ(u). If the
risk r is given in per cent, we have to ﬁnd a quantile u1−r/100. Corresponding
time Tr is derived from the formula u1−r/100 = Tr −µ(T)
σ(T) : after some algebra, we
have Tr = µ(T) + σ(T) · u1−r/100
Example : Let’s consider the previous example with expected project
duration equal to 40,33 weeks and variance of 3,43.
1 Find the probability of completing the project in 42 weeks.
Determining the time of project termination in time Tr
for a given risk r
This problem can be solved using tables of standard normal cdf φ(u). If the
risk r is given in per cent, we have to ﬁnd a quantile u1−r/100. Corresponding
time Tr is derived from the formula u1−r/100 = Tr −µ(T)
σ(T) : after some algebra, we
have Tr = µ(T) + σ(T) · u1−r/100
Example : Let’s consider the previous example with expected project
duration equal to 40,33 weeks and variance of 3,43.
1 Find the probability of completing the project in 42 weeks.
Solution: P(T ≤ 42) = φ 42−40,33√
3,43
= φ(0, 90). Using statistical
software or tables we ﬁnd the probability φ(0, 90) = 0, 8159. The
probability of completing the project no later than in 42 weeks is 81,59%.
Determining the time of project termination in time Tr
for a given risk r
This problem can be solved using tables of standard normal cdf φ(u). If the
risk r is given in per cent, we have to ﬁnd a quantile u1−r/100. Corresponding
time Tr is derived from the formula u1−r/100 = Tr −µ(T)
σ(T) : after some algebra, we
have Tr = µ(T) + σ(T) · u1−r/100
Example : Let’s consider the previous example with expected project
duration equal to 40,33 weeks and variance of 3,43.
1 Find the probability of completing the project in 42 weeks.
Solution: P(T ≤ 42) = φ 42−40,33√
3,43
= φ(0, 90). Using statistical
software or tables we ﬁnd the probability φ(0, 90) = 0, 8159. The
probability of completing the project no later than in 42 weeks is 81,59%.
2 Find time which won’t be exceeded with the risk of 20%.
Determining the time of project termination in time Tr
for a given risk r
This problem can be solved using tables of standard normal cdf φ(u). If the
risk r is given in per cent, we have to ﬁnd a quantile u1−r/100. Corresponding
time Tr is derived from the formula u1−r/100 = Tr −µ(T)
σ(T) : after some algebra, we
have Tr = µ(T) + σ(T) · u1−r/100
Example : Let’s consider the previous example with expected project
duration equal to 40,33 weeks and variance of 3,43.
1 Find the probability of completing the project in 42 weeks.
Solution: P(T ≤ 42) = φ 42−40,33√
3,43
= φ(0, 90). Using statistical
software or tables we ﬁnd the probability φ(0, 90) = 0, 8159. The
probability of completing the project no later than in 42 weeks is 81,59%.
2 Find time which won’t be exceeded with the risk of 20%.
Solution: The 20% risk corresponds to 80% probability of meeting the
deadline. We look up a quantile for this probability u0,8 = 0, 84 and
substitute it to the formula Tr = 40, 33 +
√
3, 43 · 0, 84 = 41, 88. So we
can assume that project terminates no later than in 41,88 weeks with
20% risk of breaking this deadline.
Time - cost project analysis
Methods CPM and PERT take into account only the time dimension of the
project, whereas optimal time schedule is not necessarily the cheapest one.
The basic criterion of project effectiveness is usually represented by
realization costs, which are closely related to the project duration:
Indirect costs are connected to the project as a whole (operational costs,
penalties, etc). They are increasing function of project duration (we
usually suppose linearity).
Direct costs connected to individual activities (material, labour costs, etc).
By summing indirect and direct costs of all activities we get total costs.
We will denote by cij direct costs of activity (i, j) realized in time tij . We will
assume that they are a linear function of tij (it is a non-increasing function; we
can shorten the realization time only with additional costs). Following bounds
are considered:
Dij . . . normal time for the activity (i, j), corresponding to minimal costs cij (D)
dij . . . crash time for the activity (i, j), corresponding to maximal costs cij (d).
Time - cost project analysis: direct costs
The line KN is the approximation of direct costs according to realization time
of activity (i, j). Its analytical equation is: cij = bij − aij tij , where
aij =
cij (d)−cij (D)
Dij −dij
, bij = aij dij + cij (d)
Minimization of direct costs for a given project duration
Total direct costs of the project can be expressed by the equation:
cP = (i,j)∈P(bij − aij tij ) .
The coefﬁcient aij is the slope of the line connecting points of normal and
crash time.
Minimization of direct costs for a given project duration
Total direct costs of the project can be expressed by the equation:
cP = (i,j)∈P(bij − aij tij ) .
The coefﬁcient aij is the slope of the line connecting points of normal and
crash time.
Direct costs cP of realization in time T fulﬁll the condition:
(i,j)∈P cij (D) ≤ cP ≤ (i,j)∈P cij (d)
These costs can be lowered without delaying whole project by prolonging the
duration of non-critical activities till the normal time of activity so that their time
slack would diminish.
Minimization of direct costs for a given project duration
- example
Example : Minimize costs of the project described by the table (time slacks
are labeled by VRij and critical activities are highlighted by red colour).
(i, j) tij dij Dij cij (d) cij (D) aij VRij cij
(1,2) 3 3 4 23 20 3 0 23
(1,3) 4 3 5 17 15 1 16
(2,5) 3 2 5 16 10 2 5 14
(3,4) 3 2 4 26 22 2 0 24
(3,5) 7 5 7 38 30 4 30
(4,5) 1 1 1 10 10 - 3 10
130 107 117
Minimization of direct costs for a given project duration
- example
Example : Minimize costs of the project described by the table (time slacks
are labeled by VRij and critical activities are highlighted by red colour).
(i, j) tij dij Dij cij (d) cij (D) aij VRij cij
(1,2) 3 3 4 23 20 3 0 23
(1,3) 4 3 5 17 15 1 16
(2,5) 3 2 5 16 10 2 5 14
(3,4) 3 2 4 26 22 2 0 24
(3,5) 7 5 7 38 30 4 30
(4,5) 1 1 1 10 10 - 3 10
130 107 117
Realization of the project is associated with direct costs equal to 117 cost
units (CU). These costs can be reduced by prolonging the duration of
non-critical activity (2,5) by 2 time units. This would decrease total costs by 4
CU, so we have a total of 117 – 4 = 113 CU. We continue prolonging the
duration of non-critical activities by ∆tij = min(VRij ; Dij − tij ) and we prefer
activities with a higher slope aij .
Optimal duration of the project
From the effectiveness point of view, such duration is optimal that minimizes
total costs (the sum of direct and indirect costs). We already know that direct
costs are decreasing and indirect costs increasing function of time.
Optimal duration of the project
From the effectiveness point of view, such duration is optimal that minimizes
total costs (the sum of direct and indirect costs). We already know that direct
costs are decreasing and indirect costs increasing function of time. The
optimal time can be found by shortening duration of critical activities (we
prefer activities with the lowest cost slope) until crash time is achieved. We
have to be aware of the possibility that another critical path can be formed.
Optimal duration of the project
From the effectiveness point of view, such duration is optimal that minimizes
total costs (the sum of direct and indirect costs). We already know that direct
costs are decreasing and indirect costs increasing function of time. The
optimal time can be found by shortening duration of critical activities (we
prefer activities with the lowest cost slope) until crash time is achieved. We
have to be aware of the possibility that another critical path can be formed.
We can illustrate the procedure on the above example. The initial row
represents situation when all activities are realized in normal time. The other
rows show the effect of shortening critical activities.
T (i,j) tij ∆cij IC DC TC=DC+IC
12 - - - 60 107 167
11 (1,3) 4 1 55 108 163
10 (1,3) 3 1 50 109 159
9 (3,5) 6 4 45 113 158
8 (3,5) 5 4 40 117 157
(2,5) 4 2
In the last row we can see that new activity has become critical.
Time and resources project analysis
Every project depends on resources such as labour, material, machines, etc.
Managers make effort to distribute resources evenly throughout the project
duration. In some cases, the generation of capacity peaks results in a
shortage of resources (its need exceeds its available quantity). The
summation line graphically expresses aggregate resource requirements at
any time of the project, assuming that each activity begins at its earliest
possible start. The summation line changes its course at the moments when
an activity begins or ends.
Time and resources project analysis - example
Gantt chart for the problem from the previous example (numbers in the frames
express demand for resources) and its summation line.
Time and resources project analysis - example
We can reduce the demand for resources between weeks 3 and 6 by
exploiting time slack of activity (2,5) and starting this activity in week 8 instead
of week 3 (latest start instead of earliest start).
Remark : If we prolong the time of non-critical activities, it inﬂuences the
need for resources in the course of time.
Multiple-criteria decision making (MCDM)
In real decision situations, it is often important to consider more optimization
criteria. However, these are seldom consistent, so it is not possible to ﬁnd the
solution that will be the best with respect to all criteria. The problems of
multi-criteria decision-making are divided according to the way decisions are
determined.
Problems with a ﬁnite set of decision alternatives, Multiple-criteria
evaluation problems and
Multi-objective (linear) programming problems with inﬁnitely many
alternatives deﬁned by a set of constraints.
Multiple-criteria evaluation problems
We have a set of alternatives X = {X1, . . . , Xn} and criteria of evaluation
Y1, . . . , Yk . Each alternative is assigned a vector of criteria values that can be
arranged as rows of a criteria matrix.
Y1 Y2 . . . Yk
X1 y11 y12 . . . y1k
X2 y21 y22 . . . y2k
...
...
...
...
...
Xn yn1 yn2 . . . ynk
Multiple-criteria evaluation problems
We have a set of alternatives X = {X1, . . . , Xn} and criteria of evaluation
Y1, . . . , Yk . Each alternative is assigned a vector of criteria values that can be
arranged as rows of a criteria matrix.
Y1 Y2 . . . Yk
X1 y11 y12 . . . y1k
X2 y21 y22 . . . y2k
...
...
...
...
...
Xn yn1 yn2 . . . ynk
Some decision problems deal with either maximization and minimization
criteria (e.g., when evaluating the economics of EU countries: the GDP per
capita is maximization criteria and unemployment is minimization criteria).
Since some methods require that all criteria are of the same type, it is often
necessary to transform them. Application area of MCDM is very broad:
tenders, ranking of companies, products or services, etc.
Multiple-criteria evaluation problems - example
Methods of multiple-criteria evaluation will be explained in the example of a
tablet selection (from Tomáš Šubrt et al .: Ekonomicko - matematické
metody): The user has deﬁned ﬁve relevant aspects according to which the
individual tablets will be evaluated: price [CZK], RAM memory [MB], battery
life [h], weight [g], and the ﬁfth criterion (combination of OS, processor, and
display size). Five speciﬁc T1 - T5 tablets are considered, let us give an
overview of their characteristics:
price RAM battery weight OS, processor,
life display
T1 12000 1000 9,5 680 Android 3.0,Tegra 1 GHz, 10,1”
T2 12000 1000 10 600 Apple 1054,1 GHz Dual, 9,7”
T3 5000 512 7 380 Android 2.2, 1 GHz, 7”
T4 20000 4000 3 1160 Windows 7,iCore5 1 GHz, 12,1”
T5 5000 256 4 400 Android 2.1, 800 MHz, 7”
The ﬁrst four criteria are quantitative (price and weight are minimization
criteria, others are maximization); for the ﬁfth criterion, we have at least ordinal
information, i.e. the ranking of the tablets according to an expert: 1,3,4,2,5.
Multiple-criteria evaluation problems
The basic objectives of MCDM analysis include:
selection of one, the so-called compromise alternative (e.g. elections,
etc.)
ordering alternatives (e.g. quality of products - charts for consumers)
classiﬁcation of alternatives (e.g. accepted/unaccepted or bank rating,
etc.)
The relation between alternatives can be:
the alternative Xi dominates the alternative Xj if
(yi1, . . . , yik ) ≥ (yj1, . . . , yjk ), but they are not the same.
the alternative Xj dominates the alternative Xi
the alternatives Xi , Xj are mutually non-dominated.
Let us say that the Xi alternative is non-dominated if there is no other
alternative that dominates it. Apparently, the compromise alternative must
always be non-dominated. Next, we deﬁne the terms basal (ideal) alternative,
which means a generally non-existent alternative acquiring the worst (or the
best) values according to all criteria.
MCDM - dominance of alternatives, example
Find non-dominated alternatives and construct a basal and an ideal
alternative in a tablet selection problem.
price RAM battery weight OS, processor,
life display
Tablet 1 12000 1000 9,5 680 1
Tablet 2 12000 1000 10 600 3
Tablet 3 5000 512 7 380 4
Tablet 4 20000 4000 3 1160 2
Tablet 5 5000 256 4 400 5
The best values for individual criteria are highlighted in the table.
MCDM - dominance of alternatives, example
Find non-dominated alternatives and construct a basal and an ideal
alternative in a tablet selection problem.
price RAM battery weight OS, processor,
life display
Tablet 1 12000 1000 9,5 680 1
Tablet 2 12000 1000 10 600 3
Tablet 3 5000 512 7 380 4
Tablet 4 20000 4000 3 1160 2
Tablet 5 5000 256 4 400 5
The best values for individual criteria are highlighted in the table. The ideal
alternative would therefore be unrealistic (5000 CZK, 4000 MB, 10 hours,
380g and 1st rank according to the expert). Similarly basal alternative doesn’t
exist (20000 CZK, 256 MB, 3 hours, 1160g and 5th order by the expert).
Nearly all variants are non-dominated, with the exception of Tablet 5 (worse
than Tablet 3 in every aspect).
MCDM - information on the preference of criteria
For most MCDM methods, it is necessary for the decision maker to express
his preferences relating the individual criteria. These preferences can be
determined using
aspiration levels of criteria, i.e. by setting minimum values to be reached
for the individual maximization criteria (or maximum values for the
minimization criteria). Criteria preference is thus expressed indirectly if
we set a higher aspiration level for more important criteria.
ranking of criteria (ordinal information on criteria)
weights of criteria: v = (v1, . . . , vk ) vi = 1, vi > 0, i = 1, . . . , k.
(cardinal information on criteria)
substitution rates of the criteria on which the compensation MCDM
methods are based
MCDM - estimating weights of criteria
Obtaining weights from the decision maker directly in numerical form is
problematic, so it is appropriate to facilitate his situation using a simple tool.
The ranking method requires only criteria ranking from the least important
to the most important. Thus, the assigned values pi will be 1, . . . , k, and
the weight estimates can be obtained by normalizing them: vi = pi
k
i=1 pi
.
In the scoring method, the decision maker assigns pi points of a
pre-selected scale to each criterion. The conversion of points into weights
is the same as above.
Fuller’s triangle is based on pair comparison of criteria. The individual
criterion is assigned pi points according to the number of criteria that are
less or equally important than the i-th criterion (there are k(k − 1)/2 pairs
and they can be arranged in a triangular scheme, hence the name of the
method).
A slightly more sophisticated approach is the Saaty’s method, in which
the pairs of criteria are assigned the number sij ≈ vi
vj
that estimates how
many times more important is the i-th criterion than the j-th one. The
matrix S = (sij )i,j=1,...,k is called the Saaty’s matrix.
Saaty’s method for estimating weights of criteria
The Saaty’s method allows us to formulate preferences verbally and then
express them numerically using a scale:
criteria Yi a Yj are of the same importance, sij = sji = 1,
criterion Yi is slightly more important than Yj , sij = 3, sji = 1/3,
criterion Yi is more important than Yj , sij = 5, sji = 1/5,
criterion Yi is much more important than Yj , sij = 7, sji = 1/7,
criterion Yi is absolutely more important than Yj , sij = 9, sji = 1/9.
If the scale is not sufﬁcient, intermediate steps 2,4,6,8 can also be used.
If the Saaty’s matrix is consistent, we can determine the weights as the
solution of the system vi
vj
= sij , i, j = 1, . . . , k, vi = 1. If the matrix is not
consistent, the system has no solution and weights can be estimated for
example by normalizing geometrical means of rows of the matrix S:
pi = k k
j=1 sij .
MCDM - estimating weights of criteria, example
We can show different ways of determining the criteria weights for the tablet
selection problem with decision-maker preferences „1. price, 2. RAM, 3.
expert’s opinion, 4. battery life, 5. weight (size)“. The simplest ranking method
would assign criteria weights v = ( 5
15 , 4
15 , 2
15 , 1
15 , 3
15 ).
MCDM - estimating weights of criteria, example
We can show different ways of determining the criteria weights for the tablet
selection problem with decision-maker preferences „1. price, 2. RAM, 3.
expert’s opinion, 4. battery life, 5. weight (size)“. The simplest ranking method
would assign criteria weights v = ( 5
15 , 4
15 , 2
15 , 1
15 , 3
15 ).
Another way is to express the preference of a criterion in a given row versus
the criteria in the individual columns by marking a value of 1 in the Fuller’s
triangle:
price RAM battery size expert scores weights
price 1 1 1 1
RAM 1 1 1
battery 1 0
size 0
expert
We complete the table by ﬁlling the lower triangle symmetrically with opposite
values (fij = 1 − fji , i = j), because we need them for the computation of
scores.
MCDM - estimating weights of criteria, example
We can show different ways of determining the criteria weights for the tablet
selection problem with decision-maker preferences „1. price, 2. RAM, 3.
expert’s opinion, 4. battery life, 5. weight (size)“. The simplest ranking method
would assign criteria weights v = ( 5
15 , 4
15 , 2
15 , 1
15 , 3
15 ).
Another way is to express the preference of a criterion in a given row versus
the criteria in the individual columns by marking a value of 1 in the Fuller’s
triangle:
price RAM battery size expert scores weights
price 1 1 1 1
RAM 0 1 1 1
battery 0 0 1 0
size 0 0 0 0
expert 0 0 1 1
We calculate scores as the sum of the number of preferences in the given
rows.
MCDM - estimating weights of criteria, example
We can show different ways of determining the criteria weights for the tablet
selection problem with decision-maker preferences „1. price, 2. RAM, 3.
expert’s opinion, 4. battery life, 5. weight (size)“. The simplest ranking method
would assign criteria weights v = ( 5
15 , 4
15 , 2
15 , 1
15 , 3
15 ).
Another way is to express the preference of a criterion in a given row versus
the criteria in the individual columns by marking a value of 1 in the Fuller’s
triangle:
price RAM battery size expert scores weights
price 1 1 1 1 4
RAM 0 1 1 1 3
battery 0 0 1 0 1
size 0 0 0 0 0
expert 0 0 1 1 2
We now calculate the weights by dividing the scores by their total sum, i.e. by
10.
MCDM - estimating weights of criteria, example
We can show different ways of determining the criteria weights for the tablet
selection problem with decision-maker preferences „1. price, 2. RAM, 3.
expert’s opinion, 4. battery life, 5. weight (size)“. The simplest ranking method
would assign criteria weights v = ( 5
15 , 4
15 , 2
15 , 1
15 , 3
15 ).
Another way is to express the preference of a criterion in a given row versus
the criteria in the individual columns by marking a value of 1 in the Fuller’s
triangle:
price RAM battery size expert scores weights
price 1 1 1 1 4 0,4
RAM 0 1 1 1 3 0,3
battery 0 0 1 0 1 0,1
size 0 0 0 0 0 0
expert 0 0 1 1 2 0,2
Unfortunately, the weight of the least important criterion would be zero if the
points are divided consistently. We can modify the process by adding ones to
diagonal elements (as if each criterion was preferred to itself).
MCDM - estimating weights of criteria, example
We can show different ways of determining the criteria weights for the tablet
selection problem with decision-maker preferences „1. price, 2. RAM, 3.
expert’s opinion, 4. battery life, 5. weight (size)“. The simplest ranking method
would assign criteria weights v = ( 5
15 , 4
15 , 2
15 , 1
15 , 3
15 ).
Another way is to express the preference of a criterion in a given row versus
the criteria in the individual columns by marking a value of 1 in the Fuller’s
triangle:
price RAM battery size expert scores weights
price 1 1 1 1 1 5 5
15
RAM 0 1 1 1 1 4 4
15
battery 0 0 1 1 0 2 2
15
size 0 0 0 1 0 1 1
15
expert 0 0 1 1 1 3 3
15
We get the same weights as by the ranking method.
MCDM - estimating weights of criteria, example
Let us show one of the possible user evaluations of the Saaty’s matrix for the
same decision problem.
price RAM battery size expert bi vi
price 1 4 2 9 2
RAM 1/4 1 1/2 3 1/2
battery 1/2 2 1 7 1
size 1/9 1/3 1/7 1 1/7
expert 1/2 2 1 7 1
Matrix is consistent enough (its consistency index is equal to 0,005 which is
less than the limit 0,1). We compute geometrical means of rows bi and
determine weights vi .
MCDM - estimating weights of criteria, example
Let us show one of the possible user evaluations of the Saaty’s matrix for the
same decision problem.
price RAM battery size expert bi vi
price 1 4 2 9 2 2,7 0,41
RAM 1/4 1 1/2 3 1/2 0,72 0,11
battery 1/2 2 1 7 1 1,48 0,22
size 1/9 1/3 1/7 1 1/7 0,24 0,04
expert 1/2 2 1 7 1 1,48 0,22
Saaty’s method gives more differentiated weights than the other methods.
MCDM - classiﬁcation of methods
There are many approaches to solving MCDM problems, we will only mention
the simpler ones. The methods can be classiﬁed according to the type of
preference information for criteria and alternatives, see the following brief
overview.
Preference information on alternatives
aspiration ordinal cardinal
levels information information
utility distance preference marginal rate of
function of alternative relation substitution
from bazal
or ideal
Methods
PRIAM Lexicographic WSA TOPSIS AHP Compensation
ORESTE PROMETHEE
Permutation ELECTRE
MCDM - methods not using weights of criteria
If there are no preferences between the criteria or the criteria are of equal
importance, we can use a simple order of values for each criterion to select
the compromise alternative (if there are the same values, the average order is
assigned). We choose the alternative that has the lowest total ranking across
all criteria.
In the tablets example, we have already rankings in the last column (expert
opinion). In the other columns, we replace the individual values with the
ranking within the column and compute row totals:
price RAM battery size OS, processor sum
life display
Tablet 1 3 2,5 2 4 1 12,5
Tablet 2 3 2,5 1 3 3 12,5
Tablet 3 1 4 3 1 4 13
Tablet 4 5 1 5 5 2 18
Tablet 5 1 5 4 2 5 17
Tablet 1 and tablet 2 would be chosen by the above described approach as
most suitable.
MCDM - methods not using weights of criteria
Another method not requiring apriori weights of criteria is the PRIAM
method. Alternatives are marked as acceptable or unacceptable according to
given setting of aspiration levels for individual criteria. There may be situations
where no alternative is acceptable, then some constraint needs to be relaxed.
Conversely, the number of acceptable alternatives can be reduced by
tightening some of the aspiration levels. The PRIAM method is an interactive
procedure of gradual adaptation of aspiration limits to achieve the required
number of acceptable alternatives (in the extreme case it would be only one
compromise alternative).
MCDM - methods not using weights of criteria
Another method not requiring apriori weights of criteria is the PRIAM
method. Alternatives are marked as acceptable or unacceptable according to
given setting of aspiration levels for individual criteria. There may be situations
where no alternative is acceptable, then some constraint needs to be relaxed.
Conversely, the number of acceptable alternatives can be reduced by
tightening some of the aspiration levels. The PRIAM method is an interactive
procedure of gradual adaptation of aspiration limits to achieve the required
number of acceptable alternatives (in the extreme case it would be only one
compromise alternative).
price RAM battery size OS, processor, acceptable
life display
Tablet 1 12000 1000 9,5 680 1 YES
Tablet 2 12000 1000 10 600 3 YES
Tablet 3 5000 512 7 380 4 YES
Tablet 4 20000 4000 3 1160 2 YES
Tablet 5 5000 256 4 400 5 YES
If wet set initial vector of aspiration levels on the values of basal alternative
z0
= (20000, 256, 3, 1160, 5) then all tablets are acceptable.
MCDM - methods not using weights of criteria
Another method not requiring apriori weights of criteria is the PRIAM
method. Alternatives are marked as acceptable or unacceptable according to
given setting of aspiration levels for individual criteria. There may be situations
where no alternative is acceptable, then some constraint needs to be relaxed.
Conversely, the number of acceptable alternatives can be reduced by
tightening some of the aspiration levels. The PRIAM method is an interactive
procedure of gradual adaptation of aspiration limits to achieve the required
number of acceptable alternatives (in the extreme case it would be only one
compromise alternative).
price RAM battery size OS, processor, acceptable
life display
Tablet 1 12000 1000 9,5 680 1 YES
Tablet 2 12000 1000 10 600 3 YES
Tablet 3 5000 512 7 380 4 YES
Tablet 4 20000 4000 3 1160 2 NO
Tablet 5 5000 256 4 400 5 YES
If we tighten up requirement on price not to exceed 12000 CZK, we get
z1
= (12000, 256, 3, 1160, 5), so the tablet 4 is not acceptable.
MCDM - methods not using weights of criteria
Another method not requiring apriori weights of criteria is the PRIAM
method. Alternatives are marked as acceptable or unacceptable according to
given setting of aspiration levels for individual criteria. There may be situations
where no alternative is acceptable, then some constraint needs to be relaxed.
Conversely, the number of acceptable alternatives can be reduced by
tightening some of the aspiration levels. The PRIAM method is an interactive
procedure of gradual adaptation of aspiration limits to achieve the required
number of acceptable alternatives (in the extreme case it would be only one
compromise alternative).
price RAM battery size OS, processor, acceptable
life display
Tablet 1 12000 1000 9,5 680 1 YES
Tablet 2 12000 1000 10 600 3 YES
Tablet 3 5000 512 7 380 4 NO
Tablet 4 20000 4000 3 1160 2 NO
Tablet 5 5000 256 4 400 5 NO
By tightening up requirement on battery and expert opinion,
z2
= (12000, 256, 7, 1160, 3), we eliminate also tablets 3 and 5.
MCDM - methods not using weights of criteria
Another method not requiring apriori weights of criteria is the PRIAM
method. Alternatives are marked as acceptable or unacceptable according to
given setting of aspiration levels for individual criteria. There may be situations
where no alternative is acceptable, then some constraint needs to be relaxed.
Conversely, the number of acceptable alternatives can be reduced by
tightening some of the aspiration levels. The PRIAM method is an interactive
procedure of gradual adaptation of aspiration limits to achieve the required
number of acceptable alternatives (in the extreme case it would be only one
compromise alternative).
price RAM battery size OS, processor, acceptable
life display
Tablet 1 12000 1000 9,5 680 1 NO
Tablet 2 12000 1000 10 600 3 YES
Tablet 3 5000 512 7 380 4 NO
Tablet 4 20000 4000 3 1160 2 NO
Tablet 5 5000 256 4 400 5 NO
When we require also smaller size of a tablet z3
= (12000, 256, 7, 600, 3),
then only the tablet 2 remains acceptable.
MCDM - methods using ordinal preference of criteria
The most common and probably the simplest method in a class of procedures
requiring only ordinal information on the criteria is the lexicographical
method. We follow the most important criterion, and if the best option under
this criterion is the only one, it is chosen as a compromise. If the best value is
reached by multiple alternatives, we choose the one that has better ranking
according to the second most important criterion, etc.
MCDM - methods using ordinal preference of criteria
The most common and probably the simplest method in a class of procedures
requiring only ordinal information on the criteria is the lexicographical
method. We follow the most important criterion, and if the best option under
this criterion is the only one, it is chosen as a compromise. If the best value is
reached by multiple alternatives, we choose the one that has better ranking
according to the second most important criterion, etc.
By using the lexicographic method for selection of a tablet, if the ﬁrst is the
price criterion and the second criterion is battery life, we choose tablet 3
(Tablets 3 and 5 are the cheapest and battery of tablet 3 lasts 7 hours
whereas tablet 5 lasts only 4 hours):
price RAM battery size OS, processor, ranking
life display
Tablet 1 12000 1000 9,5 680 1 4
Tablet 2 12000 1000 10 600 3 3
Tablet 3 5000 512 7 380 4 1
Tablet 4 20000 4000 3 1160 2 5
Tablet 5 5000 256 4 400 5 2
MCDM - methods using weights of criteria
There are three basic categories of approaches to evaluation of alternatives
using weighting criteria, namely:
maximization of utility
minimization of distance from an ideal alternative
the preference relation
MCDM - methods using weights of criteria
There are three basic categories of approaches to evaluation of alternatives
using weighting criteria, namely:
maximization of utility
minimization of distance from an ideal alternative
the preference relation
We will introduce at least one representative from each group of methods.
The ﬁrst option is to quantify the utility of alternatives on a scale from 0 to 1.
To express the overall beneﬁt of the alternative, it is necessary to express the
partial functions of utility uj according to the individual criteria j = 1, . . . , k.
Thus, the values yij are replaced with the values uij = uj (yij ), j = 1, . . . , k.
Utility functions are normalized so that the ideal alternative has a partial utility
according to all criteria equal to 1 and basal alternative all zeros. We
distinguish three types of beneﬁts:
1 linear (utility changes proportionally to the value of criteria)
2 progressive (rate of change in utility increases with the growing value of
criteria)
3 regressive (rate of change in utility decreases with the growing value of
criteria)
MCDM - methods using utility function
The method of weighted sum (WSA) is based on a linear utility function with
the scale of 0 to 1. We denote by Dj minimal and by Hj maximal value in the
column Yj (i.e. for the j-th criterion), then all values yij in the column Yj can be
standardized using the formula
yij =
yij −Dj
Hj −Dj
for maximization type of criteria. For minimization criteria we use the formula
yij =
Hj −yij
Hj −Dj
.
After this transformation, the worst option in every column is assigned zero
value and the best option corresponds to 1. Total utility of the alternative Xi is
computed as the weighted sum of standardized values u(Xi ) =
k
j=1 vj yij .
Finally the alternatives are ranked according to their utilities.
MCDM - method WSA, example
Lets apply WSA on tablet selection problem, we use weights given by Saaty’s
method:
price RAM battery size OS, processor, utility
life display
Tablet 1 12000 1000 9,5 680 1
Tablet 2 12000 1000 10 600 3
Tablet 3 5000 512 7 380 4
Tablet 4 20000 4000 3 1160 2
Tablet 5 5000 256 4 400 5
weight 0,41 0,12 0,22 0,03 0,22
Dj 5000 256 3 380 1
Hj 20000 4000 10 1160 5
type min max max min min
We compute standardized values (partial utilities) yij .
MCDM - method WSA, example
Lets apply WSA on tablet selection problem, we use weights given by Saaty’s
method:
price RAM battery size OS, processor, utility
life display
Tablet 1 0,53 0,2 0,93 0,62 1
Tablet 2 0,53 0,2 1 0,72 0,5
Tablet 3 1 0,07 0,57 1 0,25
Tablet 4 0 1 0 0 0,75
Tablet 5 1 0 0,14 0,97 0
weight 0,41 0,12 0,22 0,03 0,22
Dj 5000 256 3 380 1
Hj 20000 4000 10 1160 5
type min max max min min
Then we aggregate partial utilities for each alternative.
MCDM - method WSA, example
Lets apply WSA on tablet selection problem, we use weights given by Saaty’s
method:
price RAM battery size OS, processor, utility
life display
Tablet 1 0,53 0,2 0,93 0,62 1 0,69
Tablet 2 0,53 0,2 1 0,72 0,5 0,59
Tablet 3 1 0,07 0,57 1 0,25 0,63
Tablet 4 0 1 0 0 0,75 0,29
Tablet 5 1 0 0,14 0,97 0 0,47
weight 0,41 0,12 0,22 0,03 0,22
Dj 5000 256 3 380 1
Hj 20000 4000 10 1160 5
type min max max min min
Maximal utility can be achieved by purchasing the tablet 1 (the second best is
the tablet 3).
MCDM - methods based on distance from basal and
ideal alternatives
The method TOPSIS (Technique for Order of Preference by Similarity to Ideal
Solution) tries to ﬁnd the alternative that is as close as possible to the ideal
alternative and at the same time as far as possible from the basal alternative.
Let’s describe the procedure for the case of maximization criteria. The method
consists of the following steps:
1 Normalization: values yij are transformed to rij using the formula
rij =
yij
n
i=1 y2
ij
.
2 Weighted criteria matrix W = (wij ) is computed as wij = vj rij .
3 Column maxima of W form ideal alternative H = (H1, . . . , Hk ) and column
minima form basal alternative D = (D1, . . . , Dk ), i.e. Hj = maxi (wij ),
Dj = mini (wij ). (Values of H and D are different from that used in WSA!)
4 For each alternative we compute its distance from ideal and basal
alternative: d+
i =
k
j=1(wij − Hj )2, d−
i =
k
j=1(wij − Dj )2
5 Finally, we assign each alternative the index ci =
d−
i
d+
i
+d−
i
and rank
alternatives according to descending values of the index.
MCDM - method TOPSIS, example
Lets apply the TOPSIS method on a tablet selection problem for Saaty’s
weights.
price RAM battery size expert d+
i d−
i ci
life
T1 0,442 0,234 0,584 0,432 0,135
T2 0,442 0,234 0,615 0,382 0,405
T3 0,184 0,120 0,431 0,242 0,539
T4 0,736 0,934 0,185 0,738 0,270
T5 0,184 0,06 0,246 0,254 0,674
vj 0,41 0,12 0,22 0,03 0,22
type min max max min min
Dj
Hj
Normalized values rij .
MCDM - method TOPSIS, example
Lets apply the TOPSIS method on a tablet selection problem for Saaty’s
weights.
price RAM battery size expert d+
i d−
i ci
life
T1 0,181 0,028 0,129 0,013 0,03
T2 0,181 0,028 0,135 0,011 0,089
T3 0,075 0,014 0,095 0,007 0,119
T4 0,302 0,112 0,041 0,022 0,059
T5 0,075 0,007 0,054 0,008 0,148
vj 0,41 0,12 0,22 0,03 0,22
type min max max min min
Dj 0,302 0,007 0,041 0,022 0,148
Hj 0,075 0,112 0,135 0,007 0,030
Weighted matrix Wij , ideal alternative H and basal alternative D are in bottom
rows.
MCDM - method TOPSIS, example
Lets apply the TOPSIS method on a tablet selection problem for Saaty’s
weights.
price RAM battery size expert d+
i d−
i ci
life
T1 0,181 0,028 0,129 0,013 0,03 0,135 0,192 0,587
T2 0,181 0,028 0,135 0,011 0,089 0,148 0,166 0,53
T3 0,075 0,014 0,095 0,007 0,119 0,138 0,235 0,63
T4 0,302 0,112 0,041 0,022 0,059 0,248 0,138 0,357
T5 0,075 0,007 0,054 0,008 0,148 0,178 0,227 0,56
vj 0,41 0,12 0,22 0,03 0,22
type min max max min min
Dj 0,302 0,007 0,041 0,022 0,148
Hj 0,075 0,112 0,135 0,007 0,030
Final step is computation of distances from ideal and basal alternative d+
i and
d−
i and the relative index ci . The smallest value of ci is obtained for the tablet
3.
MCDM - methods of class ELECTRE
An important group of methods is based on the preference relation between
the alternatives. The overall preference is derived from partial preferences by
appropriate aggregation procedures. Unfortunately, the result does not have
to be transitive, so there is a need for another procedure that determines the
overall order of the alternatives. The method ELECTRE I doesn’t produce
complete ranking but a partition into groups of the so-called effective or
ineffective alternatives.
MCDM - methods of class ELECTRE
An important group of methods is based on the preference relation between
the alternatives. The overall preference is derived from partial preferences by
appropriate aggregation procedures. Unfortunately, the result does not have
to be transitive, so there is a need for another procedure that determines the
overall order of the alternatives. The method ELECTRE I doesn’t produce
complete ranking but a partition into groups of the so-called effective or
ineffective alternatives.
Assume that all criteria are maximizing. For each pair of alternatives Xi , Xj ,
we determine the set
Cij = {h ∈ {1, . . . , k}; yih ≥ yjh}
consisting of indexes of those criteria, that doesn’t rank Xi worse than Xj .
Additionally, we determine the set
Dij = {h ∈ {1, . . . , k}; yih < yjh}
consisting of indexes of those criteria, that rank Xi worse than Xj
MCDM - methods of class ELECTRE
Weights v1, . . . , vk are used for computation of the preference degree for
each pair of alternatives according to the formula
cij = h∈Cij
vh
Apparently, cij ∈ 0, 1 .
MCDM - methods of class ELECTRE
Weights v1, . . . , vk are used for computation of the preference degree for
each pair of alternatives according to the formula
cij = h∈Cij
vh
Apparently, cij ∈ 0, 1 .
In the next step, we assign each pair of alternatives dispreference degree by
the formula
dij =
maxh∈Dij
|yih−yjh|
maxh=1,...,k |yih−yjh| ;
in the case Dij = ∅ we deﬁne dij = 0. Again dij ∈ 0, 1 .
MCDM - methods of class ELECTRE
Weights v1, . . . , vk are used for computation of the preference degree for
each pair of alternatives according to the formula
cij = h∈Cij
vh
Apparently, cij ∈ 0, 1 .
In the next step, we assign each pair of alternatives dispreference degree by
the formula
dij =
maxh∈Dij
|yih−yjh|
maxh=1,...,k |yih−yjh| ;
in the case Dij = ∅ we deﬁne dij = 0. Again dij ∈ 0, 1 .
Suitable constants called preference threshold c∗
and dispreference threshold
d∗
help to decide on the relation between Xi and Xj :
Xi is preferred to Xj , if cij ≥ c∗
∧ dij ≤ d∗
.
MCDM - methods of class ELECTRE
Weights v1, . . . , vk are used for computation of the preference degree for
each pair of alternatives according to the formula
cij = h∈Cij
vh
Apparently, cij ∈ 0, 1 .
In the next step, we assign each pair of alternatives dispreference degree by
the formula
dij =
maxh∈Dij
|yih−yjh|
maxh=1,...,k |yih−yjh| ;
in the case Dij = ∅ we deﬁne dij = 0. Again dij ∈ 0, 1 .
Suitable constants called preference threshold c∗
and dispreference threshold
d∗
help to decide on the relation between Xi and Xj :
Xi is preferred to Xj , if cij ≥ c∗
∧ dij ≤ d∗
.
Alternatives that are preferred over at least one another, but at the same time
there is no alternative preferred to them are considered to be effective. The
result depends on the choice of thresholds, so adjustments in their values can
be used to reduce the number of effective alternatives to ﬁnd "the
best"compromise option.
MCDM - method ELECTRE I - example
Determination of the sets Cij for the tablet problem:
Cij T1 T2 T3 T4 T5
T1 {1, 2, 5} {2, 3, 5} {1, 3, 4, 5} {2, 3, 5}
T2 {1, 2, 3, 4} {2, 3, 5} {1, 3, 4} {2, 3, 5}
T3 {1, 4} {1, 4} {1, 4} {1, 2, 3, 4, 5}
T4 {2} {2, 5} {2, 3, 5} {2, 5}
T5 {1, 4} {1, 4} {1} {1, 3, 4}
MCDM - method ELECTRE I - example
Determination of the sets Cij for the tablet problem:
Cij T1 T2 T3 T4 T5
T1 {1, 2, 5} {2, 3, 5} {1, 3, 4, 5} {2, 3, 5}
T2 {1, 2, 3, 4} {2, 3, 5} {1, 3, 4} {2, 3, 5}
T3 {1, 4} {1, 4} {1, 4} {1, 2, 3, 4, 5}
T4 {2} {2, 5} {2, 3, 5} {2, 5}
T5 {1, 4} {1, 4} {1} {1, 3, 4}
Again we use Saaty’s weights (0, 41; 0, 12; 0, 22; 0, 03; 0, 22)
for the determination of preference degrees:
cij T1 T2 T3 T4 T5
T1 0,75 0,56 0,88 0,56
T2 0,78 0,56 0,66 0,56
T3 0,44 0,44 0,44 1
T4 0,12 0,34 0,56 0,34
T5 0,44 0,44 0,41 0,66
MCDM - method ELECTRE I - example
The sets Dij for individual pairs of tablets are
Dij T1 T2 T3 T4 T5
T1 {3, 4} {1, 4} {2} {1, 4}
T2 {5} {1, 4} {2, 5} {1, 4}
T3 {2, 3, 5} {2, 3, 5} {2, 3, 5} {}
T4 {1, 3, 4, 5} {1, 3, 4} {1, 4} {1, 3, 4}
T5 {2, 3, 5} {2, 3, 5} {2, 3, 4, 5} {2, 5}
MCDM - method ELECTRE I - example
The sets Dij for individual pairs of tablets are
Dij T1 T2 T3 T4 T5
T1 {3, 4} {1, 4} {2} {1, 4}
T2 {5} {1, 4} {2, 5} {1, 4}
T3 {2, 3, 5} {2, 3, 5} {2, 3, 5} {}
T4 {1, 3, 4, 5} {1, 3, 4} {1, 4} {1, 3, 4}
T5 {2, 3, 5} {2, 3, 5} {2, 3, 4, 5} {2, 5}
We use standardized values yij to complete the table of dispreference
degrees:
dij T1 T2 T3 T4 T5
T1 0,1/0,5 0,47/0,75 0,8/0,93 0,47/1
T2 0,5/0,5 0,47/0,47 0,8/1 0,47/0,86
T3 0,75/0,75 0,28/0,47 0,93/1 0/0,43
T4 0,93/0,93 1/1 1/1 1/1
T5 1/1 0,86/0,86 0,43/0,43 1/1
MCDM - method ELECTRE I - example
We set the preference threshold c∗
= 0, 5 and highlight cij ≥ c∗
.
cij T1 T2 T3 T4 T5
T1 0,75 0,56 0,88 0,56
T2 0,78 0,56 0,66 0,56
T3 0,44 0,44 0,44 1
T4 0,12 0,34 0,56 0,34
T5 0,44 0,44 0,41 0,66
MCDM - method ELECTRE I - example
We set the preference threshold c∗
= 0, 5 and highlight cij ≥ c∗
.
cij T1 T2 T3 T4 T5
T1 0,75 0,56 0,88 0,56
T2 0,78 0,56 0,66 0,56
T3 0,44 0,44 0,44 1
T4 0,12 0,34 0,56 0,34
T5 0,44 0,44 0,41 0,66
We set the preference threshold d∗
= 0, 5 and highlight dij ≤ d∗
.
dij T1 T2 T3 T4 T5
T1 0,2 0,62 0,86 0,47
T2 1 1 0,8 0,55
T3 1 0,6 0,93 0
T4 1 1 1 1
T5 1 1 1 1
MCDM - method ELECTRE I - example
Preference relation can be represented by a matrix or an oriented graph (it
contains only those edges that correspond to pairs satisfying both conditions
cij ≥ c∗
, dij ≤ d∗
):
As can be seen, alternatives 1 and 3 are effective (corresponding nodes are
starting points of some edges, but no edges end in them).
MCDM - methods of class PROMETHEE
These methods are one of the most popular among MCDM procedures. They
are based on a pair comparison of alternatives with respect to all criteria. We
deﬁne for each pair Xi , Xj the preference intensity with respect to Yh:
Ph(Xi , Xj )
as a function with the range 0, 1 , such that Ph(Xi , Xj ) = 0 if Xi is not
preferred to Xj and Ph(Xi , Xj ) = 1 in the case it is absolutely preferred.
MCDM - methods of class PROMETHEE
These methods are one of the most popular among MCDM procedures. They
are based on a pair comparison of alternatives with respect to all criteria. We
deﬁne for each pair Xi , Xj the preference intensity with respect to Yh:
Ph(Xi , Xj )
as a function with the range 0, 1 , such that Ph(Xi , Xj ) = 0 if Xi is not
preferred to Xj and Ph(Xi , Xj ) = 1 in the case it is absolutely preferred.
Transformation Q converting the difference dh to the preference intensity
Ph(Xi , Xj ) is called a generalized criterion and may have various shapes, for
example, see the ﬁgure:
MCDM - methods of class PROMETHEE
For given weights we can compute the global preference index of Xi , Xj by the
formula
P(Xi , Xj ) =
k
h=1 vhPh(Xi , Xj ).
To obtain the ﬁnal order of alternatives we have to assign to them their
positive and negative ﬂow as
F+
(Xi ) =
n
j=1 P(Xi , Xj )/(n − 1),
F−
(Xi ) =
n
j=1 P(Xj , Xi )/(n − 1),
MCDM - methods of class PROMETHEE
For given weights we can compute the global preference index of Xi , Xj by the
formula
P(Xi , Xj ) =
k
h=1 vhPh(Xi , Xj ).
To obtain the ﬁnal order of alternatives we have to assign to them their
positive and negative ﬂow as
F+
(Xi ) =
n
j=1 P(Xi , Xj )/(n − 1),
F−
(Xi ) =
n
j=1 P(Xj , Xi )/(n − 1),
There are different ways how to conclude, for example the method
PROMETHEE II ranks alternatives with respect to the net ﬂow
F(Xi ) = F+
(Xi ) − F−
(Xi ).
MCDM - method PROMETHEE II, example
In a tablet problem, we derive differences dh from standardized values yij :
yij price RAM battery size OS, processor,
life display
Tablet 1 0,53 0,2 0,93 0,62 1
Tablet 2 0,53 0,2 1 0,72 0,5
Tablet 3 1 0,07 0,57 1 0,25
Tablet 4 0 1 0 0 0,75
Tablet 5 1 0 0,14 0,97 0
MCDM - method PROMETHEE II, example
In a tablet problem, we derive differences dh from standardized values yij :
yij price RAM battery size OS, processor,
life display
Tablet 1 0,53 0,2 0,93 0,62 1
Tablet 2 0,53 0,2 1 0,72 0,5
Tablet 3 1 0,07 0,57 1 0,25
Tablet 4 0 1 0 0 0,75
Tablet 5 1 0 0,14 0,97 0
After computation of differences dh(Xi , Xj ) for all i, j = 1, . . . , n and all
h = 1, . . . , k we use general criterion Q1 with the threshold d∗
= 0, 5 to
transform them to preference intensities Ph(Xi , Xj ).
Computations for the ﬁrst criterion are shown in the following tables; ﬁrst, it is
necessary to determine d1, then transform it to P1.
MCDM - method PROMETHEE II, example
d1(Xi , Xj ) T1 T2 T3 T4 T5
T1 0 0 -0,47 0,53 -0,47
T2 0 0 -0,47 0,53 -0,47
T3 0,47 0,47 0 1 0
T4 -0,53 -0,53 -1 0 1
T5 0,47 0,47 0 -1 0
MCDM - method PROMETHEE II, example
d1(Xi , Xj ) T1 T2 T3 T4 T5
T1 0 0 -0,47 0,53 -0,47
T2 0 0 -0,47 0,53 -0,47
T3 0,47 0,47 0 1 0
T4 -0,53 -0,53 -1 0 1
T5 0,47 0,47 0 -1 0
Table of preference intensity:
P1(Xi , Xj ) T1 T2 T3 T4 T5
T1 0 0 0 1 0
T2 0 0 0 1 0
T3 0 0 0 1 0
T4 0 0 0 0 1
T5 0 0 0 0 0
MCDM - method PROMETHEE II, example
The procedure is repeated for other criteria and ﬁnally the Saaty’s weights
(0, 41; 0, 12; 0, 22; 0, 03; 0, 22) are used to aggregate preference intensities
to get the global preference index:
P(Xi , Xj ) T1 T2 T3 T4 T5 F+
(Xi )
T1 0 0 0,22 0,66 0,22
T2 0 0 0 0,44 0,22
T3 0 0 0 0,66 0,22
T4 0,12 0,12 0,12 0 0,75
T5 0 0 0 0 0
F−
(Xi )
Row averages show positive ﬂows and column averages negative ﬂows.
MCDM - method PROMETHEE II, example
The procedure is repeated for other criteria and ﬁnally the Saaty’s weights
(0, 41; 0, 12; 0, 22; 0, 03; 0, 22) are used to aggregate preference intensities
to get the global preference index:
P(Xi , Xj ) T1 T2 T3 T4 T5 F+
(Xi )
T1 0 0 0,22 0,66 0,22 0,275
T2 0 0 0 0,44 0,22 0,165
T3 0 0 0 0,66 0,22 0,22
T4 0,12 0,12 0,12 0 0,75 0,2775
T5 0 0 0 0 0 0
F−
(Xi ) 0,03 0,03 0,085 0,44 0,3525
The difference of positive and negative ﬂow is the net ﬂow:
F(T1) = 0, 245, F(T2) = 0, 135, F(T3) = 0, 135,
F(T4) = −0, 1625, F(T5) = −0, 3525
The highest net ﬂow is obtained for the tablet 1.
MCDM - method AHP
The method AHP (Analytic Hierarchy Process) models decision problem by
means of hierarchical structure. The simplest problems are described using
three-level hierarchy (see ﬁgure).
MCDM - method AHP
The importance of the individual elements of the hierarchy can be expressed
by dividing the initial unit (100%) according to the preference of the
decision-maker to the next level. First, on the second level, criteria are
assigned weights vj , j = 1, . . . , k. Each weight vj is further subdivided into
numbers wij , i = 1, . . . , n expressing how individual alternatives fulﬁl a given
criterion. So we have
k
j=1 vj = 1,
n
i=1 wij = vj , j = 1, . . . k Finally total
ranking of alternatives is derived from their beneﬁt given as u(Xi ) =
k
j=1 wij .
MCDM - method AHP
The importance of the individual elements of the hierarchy can be expressed
by dividing the initial unit (100%) according to the preference of the
decision-maker to the next level. First, on the second level, criteria are
assigned weights vj , j = 1, . . . , k. Each weight vj is further subdivided into
numbers wij , i = 1, . . . , n expressing how individual alternatives fulﬁl a given
criterion. So we have
k
j=1 vj = 1,
n
i=1 wij = vj , j = 1, . . . k Finally total
ranking of alternatives is derived from their beneﬁt given as u(Xi ) =
k
j=1 wij .
The numerical realization is based on pairwise comparison of elements as in
the Saaty s method: For the highest node, a comparison matrix (k × k) is
constructed and the criterion weights are derived from it. Subsequently, for
each criterion, preference of alternatives is determined by pairwise
comparisons in the matrix (n × n). The disadvantage of the method is
obviously a large number of comparisons. On the other hand the pros of the
method are its versatility and the possibility of using a verbal scale to express
preferences.
Multi-criteria programming
The goal of multi-criteria programming is the optimization of more objective
functions on the feasible region deﬁned by the system of constraints. Unlike in
MCDM problems, the set of decision alternatives is inﬁnite and the criteria are
deﬁned in terms of functions. If all objective functions and limiting conditions
are linear, we talk about multi-criteria linear programming (MLP). Therefore,
the MLP problem can be formulated as a problem to "optimize"
z1 = c1
· x, z2 = c2
· x, . . . zk = ck
· x,
subject to
x ∈ X = {x ∈ Rn
|Ax ≤ b, x ≥ 0},
where ci
is the price vector of the i-th objective function.
Multi-criteria programming
The goal of multi-criteria programming is the optimization of more objective
functions on the feasible region deﬁned by the system of constraints. Unlike in
MCDM problems, the set of decision alternatives is inﬁnite and the criteria are
deﬁned in terms of functions. If all objective functions and limiting conditions
are linear, we talk about multi-criteria linear programming (MLP). Therefore,
the MLP problem can be formulated as a problem to "optimize"
z1 = c1
· x, z2 = c2
· x, . . . zk = ck
· x,
subject to
x ∈ X = {x ∈ Rn
|Ax ≤ b, x ≥ 0},
where ci
is the price vector of the i-th objective function.
Using the equivalency of a minimization problem with an objective zi to a
maximization problem with −zi , we can convert a multi-criteria problem into a
form with all criteria having maximizing character. The problem can then be
written using a matrix notation, if we denote z = (z1, z2, . . . , zk ) vector of
objective functions and C matrix with rows given by price vectors c1
, c2
, . . . ck
:
z = C · x → MAX, x ∈ X.
MLP model - basic deﬁnitions
Typically, the goal of MLP is to ﬁnd an acceptable compromise solution in a
set of all feasible solutions. It is good to realize that when looking for a
compromise solution, we can restrict the search to non-dominated solutions
only. The solution x ∈ X is non-dominated if there is no feasible solution with
value vector „greater“ than the vector C · x („Vector u is greater than v“
means that all their components satisfy ui ≥ vi and at least one component
satisﬁes ui > vi ).
MLP model - basic deﬁnitions
Typically, the goal of MLP is to ﬁnd an acceptable compromise solution in a
set of all feasible solutions. It is good to realize that when looking for a
compromise solution, we can restrict the search to non-dominated solutions
only. The solution x ∈ X is non-dominated if there is no feasible solution with
value vector „greater“ than the vector C · x („Vector u is greater than v“
means that all their components satisfy ui ≥ vi and at least one component
satisﬁes ui > vi ).
Most of the principles for ﬁnding a compromise solution are based on solving
partial linear programming problems zi = ci
· x → max, x ∈ X by a standard
simplex method. The vector xH, for which all objective functions gain their
optimal values, is called the ideal solution. By analogy, we can introduce the
basal solution xD. Optimal and basal solutions usually don’t lie in the feasible
set.
MLP model - graphical representation
The multi-criteria linear model with two variables can be displayed in the
decision space or in the criteria space. First, we show a problem in the
decision space where the coordinate axes represent the values of the
variables.
The feasible set X.
MLP model - graphical representation
The multi-criteria linear model with two variables can be displayed in the
decision space or in the criteria space. First, we show a problem in the
decision space where the coordinate axes represent the values of the
variables.
Partial LP problem for the objective z1 = c1
· x with its optimum point x1
.
MLP model - graphical representation
The multi-criteria linear model with two variables can be displayed in the
decision space or in the criteria space. First, we show a problem in the
decision space where the coordinate axes represent the values of the
variables.
Partial LP problem for the objective z2 = c2
· x with its optimum point x2
.
MLP model - graphical representation
The multi-criteria linear model with two variables can be displayed in the
decision space or in the criteria space. First, we show a problem in the
decision space where the coordinate axes represent the values of the
variables.
Ideal solution xH lies in the intersection of level curves of individual objective
functions going through partial optima points.
MLP model - graphical representation
The multi-criteria linear model with two variables can be displayed in the
decision space or in the criteria space. First, we show a problem in the
decision space where the coordinate axes represent the values of the
variables.
Normal vectors to these lines (i.e. the price coefﬁcient vectors ci
) determine
the direction of growth of the objective functions. Their non-negative linear
combinations deﬁne the so-called criteria hull.
MLP model - graphical representation
The multi-criteria linear model with two variables can be displayed in the
decision space or in the criteria space. First, we show a problem in the
decision space where the coordinate axes represent the values of the
variables.
All non-dominated solutions lie in the intersection of the criteria hull and
feasible set boundary.
MLP model - graphical representation
When displaying the solution in the criteria space, the individual axes
correspond to the values partial objective functions.
Non-dominated values are marked by a blue color.
Multi-criteria programming - classiﬁcation of methods
When solving MLP problems, we may require results in the form of a complete
description of a set of non-dominated solutions or its representative subset or
the selection of several compromise solutions. If the user wants to choose the
only compromise solution, his decision will depend heavily on his preferences
of the individual criteria. These can be entered in different phases of
calculation:
before the computation,
interactively in the course of the computation,
after the computation.
The preferences can be expressed by means of aspiration levels, criteria
order or the substitution rates of criteria values.
Multi-criteria programming - classiﬁcation of methods
When solving MLP problems, we may require results in the form of a complete
description of a set of non-dominated solutions or its representative subset or
the selection of several compromise solutions. If the user wants to choose the
only compromise solution, his decision will depend heavily on his preferences
of the individual criteria. These can be entered in different phases of
calculation:
before the computation,
interactively in the course of the computation,
after the computation.
The preferences can be expressed by means of aspiration levels, criteria
order or the substitution rates of criteria values. We distinguish between:
methods with apriori preference information
methods with aposteriori preference information
methods with interactive adjusting preference information
combined methods
Multi-criteria programming - classiﬁcation of methods
Methods with apriori preference information can be divided into several
groups:
lexicographic method
method of minimal component
aggregation of criteria
switching the role of criteria and constraints
"minimization of deviation"from ideal values (for a suitable metric)
Multi-criteria programming - classiﬁcation of methods
Methods with apriori preference information can be divided into several
groups:
lexicographic method
method of minimal component
aggregation of criteria
switching the role of criteria and constraints
"minimization of deviation"from ideal values (for a suitable metric)
Methods with information aposteriori is based on the description of the set of
non-dominated solutions in which the user chooses a compromise solution.
This class includes:
the parametric method (aggregation of criteria for a parametric vector of
weights)
the constraint method (searches for non-dominated solutions where
criterion values reach parametric target values)
multi-criteria simplex algorithm (determines non-dominated basic
solutions gradually)
Multi-criteria programming - classiﬁcation of methods
Methods with apriori preference information can be divided into several
groups:
lexicographic method
method of minimal component
aggregation of criteria
switching the role of criteria and constraints
"minimization of deviation"from ideal values (for a suitable metric)
Methods with information aposteriori is based on the description of the set of
non-dominated solutions in which the user chooses a compromise solution.
This class includes:
the parametric method (aggregation of criteria for a parametric vector of
weights)
the constraint method (searches for non-dominated solutions where
criterion values reach parametric target values)
multi-criteria simplex algorithm (determines non-dominated basic
solutions gradually)
Interactive methods are based on throughout communication between the
analyst and the decision-maker.
Multi-criteria programming - example
Ski and snowboard rental management is considering to broaden its product
range by four types of sets. The calculation includes the daily proﬁts from
lending the individual sets [in CZK] and the risk of loss of non-lending [in
points].
ski ski cross-country snowboard
set set skiing set
adult child set
proﬁt 300 200 170 250
risk 10 15 25 5
The company allocated 1 million CZK for the purchase of sets, where at least
200 thousand CZK should be used for snowboard sets. Suggest managers of
the company the portfolio that maximizes the proﬁt and minimizes the loss.
Multi-criteria LP example - building the model
Let’s denote the amounts of respective sets purchased by x1, . . . , x4 . The
objectives are
z1 = 300x1 + 200x2 + 170x3 + 250x4 → max
z2 = 10x1 + 15x2 + 25x3 + 5x4 → min
The budget and requirement on snowboard sets give following constraints:
x1 + x2 + x3 + x4 ≤ 100
x4 ≥ 20
We include also non-negativity constraints :
x1, x2, x3, x4 ≥ 0
We should also treat the problem as an integer problem, but for the sake of
simplicity let us omit this constraint.
First, we solve the simpliﬁed model considering only one criteria function, we
get the partial optimal solution.
Multi-criteria LP example - partial optimal solution
We can see that the company can achieve minimal risk if they purchase only
required snowboard sets, i.e. 20 pcs costing 10,000 CZK each.
Multi-criteria LP example - partial optimal solution
We can see that the company can achieve minimal risk if they purchase only
required snowboard sets, i.e. 20 pcs costing 10,000 CZK each.
Similarly, maximal return is gained if in addition to obligatory snowboard sets
(20 pcs), the company spends the rest of the budget on the most proﬁtable
adult ski sets. The money would sufﬁce for 80 pcs of sets.
Multi-criteria LP example - partial optimal solution
We can see that the company can achieve minimal risk if they purchase only
required snowboard sets, i.e. 20 pcs costing 10,000 CZK each.
Similarly, maximal return is gained if in addition to obligatory snowboard sets
(20 pcs), the company spends the rest of the budget on the most proﬁtable
adult ski sets. The money would sufﬁce for 80 pcs of sets.
Partial optimal solutions can be arranged in the criteria table:
Criteria function
return risk
80 ski adult 29000 880
+ 20 snowboard sets
20 snowboard sets 5000 100
The values on the diagonal form the (nonexistent) ideal solution with return of
29,000 CZK and 100 risk points.
Multi-criteria LP - lexicographic method
Let’s describe some methods with apriori preference information.
When using the lexicographic method, the decision-maker determines the
order of importance of the criteria functions (assuming that the functions are
already marked so that z1 is the most signiﬁcant, and zk least signiﬁcant, their
optimal values are denoted by zopt
1 , . . . , zopt
k ). Finding a compromise solution
involves solving a sequence of optimization problems
max z1 = c1
· x, x ∈ X. If it has more than one optimal solution, we solve
another problem:
max z2 = c2
· x, x ∈ X, c1
x ≥ zopt
1 . Again, if the solution is non-unique, we
proceed further until we ﬁnd the compromise solution as the optimal point of
the problem
max zk = ck
· x, x ∈ X, c1
x ≥ zopt
1 , . . . , ck−1
x ≥ zopt
k−1.
Multi-criteria LP - lexicographic method
Let’s describe some methods with apriori preference information.
When using the lexicographic method, the decision-maker determines the
order of importance of the criteria functions (assuming that the functions are
already marked so that z1 is the most signiﬁcant, and zk least signiﬁcant, their
optimal values are denoted by zopt
1 , . . . , zopt
k ). Finding a compromise solution
involves solving a sequence of optimization problems
max z1 = c1
· x, x ∈ X. If it has more than one optimal solution, we solve
another problem:
max z2 = c2
· x, x ∈ X, c1
x ≥ zopt
1 . Again, if the solution is non-unique, we
proceed further until we ﬁnd the compromise solution as the optimal point of
the problem
max zk = ck
· x, x ∈ X, c1
x ≥ zopt
1 , . . . , ck−1
x ≥ zopt
k−1.
To mitigate the absolute preference of more important criteria, it is possible to
allow a deviation from optimal value δi , i = 1, . . . , k in each step. For example,
in the second step, we would solve the problem
max z2 = c2
· x, x ∈ X, c1
x ≥ zopt
1 − δ1, etc.
The described method is similar to the way of thinking of managers.
Lexicographic method, example
We already know that when we prefer the risk, we should buy only 20
snowboard sets. Under the preference of proﬁt, 20 snowboard and 80 adult
sets should be purchased.
What is the solution in the second step if we prefer risk, but accept its
deviation from the ideal value of 100 to 120? We maximize the proﬁt
z1 = 300x1 + 200x2 + 170x3 + 250x4 subject to
z2 = 10x1 + 15x2 + 25x3 + 5x4 ≤ 120 , (risk constraint) and other constraints
of the model
x1 + x2 + x3 + x4 ≤ 100 x4 ≥ 20 , x1, . . . , x4 ≥ 0.
Lexicographic method, example
We already know that when we prefer the risk, we should buy only 20
snowboard sets. Under the preference of proﬁt, 20 snowboard and 80 adult
sets should be purchased.
What is the solution in the second step if we prefer risk, but accept its
deviation from the ideal value of 100 to 120? We maximize the proﬁt
z1 = 300x1 + 200x2 + 170x3 + 250x4 subject to
z2 = 10x1 + 15x2 + 25x3 + 5x4 ≤ 120 , (risk constraint) and other constraints
of the model
x1 + x2 + x3 + x4 ≤ 100 x4 ≥ 20 , x1, . . . , x4 ≥ 0.
We can easily arrive at optimal solution x1 = 2, x2 = 0, x3 = 0, x4 = 20, so we
should buy 2 adult ski sets in addition to 20 snowboard sets. The return would
be 5600 CZK and the risk would reach its limit 120 risk points.
Multi-criteria LP - minimal component method
Another approach to determining the compromise solution is a minimal
component method, where we maximize the worst (i.e. the smallest)
component of the function value vector. So we get LP to maximize z = δ
under conditions c1
· x ≥ δ, c2
· x ≥ δ, . . . ck
· x ≥ δ, x ∈ X .
Multi-criteria LP - minimal component method
Another approach to determining the compromise solution is a minimal
component method, where we maximize the worst (i.e. the smallest)
component of the function value vector. So we get LP to maximize z = δ
under conditions c1
· x ≥ δ, c2
· x ≥ δ, . . . ck
· x ≥ δ, x ∈ X .
If some of the criteria are of a minimization nature, they must ﬁrst be
converted to maximization and all have to be adjusted to dimensionless
variables to ensure their comparability.
Multi-criteria LP - aggregation of criteria functions
By using a suitable operator, it is possible to merge all the criteria functions
into a single one. Generally, different operators are used for aggregation, for
example linear combination of individual functions using a standardized
weight vector v = (v1, . . . , vk). We replace the initial problem
z = C · x → MAX, x ∈ X by an one-dimensional problem
zv = v · C · x → max, x ∈ X.
Multi-criteria LP - aggregation of criteria functions
By using a suitable operator, it is possible to merge all the criteria functions
into a single one. Generally, different operators are used for aggregation, for
example linear combination of individual functions using a standardized
weight vector v = (v1, . . . , vk). We replace the initial problem
z = C · x → MAX, x ∈ X by an one-dimensional problem
zv = v · C · x → max, x ∈ X.
We can depict the aggregate criterion graphically (green line). It has no
practical interpretation, it is only an auxiliary criterion. Attention! When setting
the weights it is necessary to take into account different scales of the
respective functions.
Aggregation of criteria functions, example
For aggregation of the proﬁt z1 and the risk z2 we need to take into account
different types of criteria, e.g. to multiply z2 by the coefﬁcient (-1).
If we set the weights equal to
v = 5
100 , 95
100 ,
the aggregated criteria function would be given by the formula
zv = 5, 5x1 − 4, 25x2 − 15, 25x3 + 7, 75x4.
Aggregation of criteria functions, example
For aggregation of the proﬁt z1 and the risk z2 we need to take into account
different types of criteria, e.g. to multiply z2 by the coefﬁcient (-1).
If we set the weights equal to
v = 5
100 , 95
100 ,
the aggregated criteria function would be given by the formula
zv = 5, 5x1 − 4, 25x2 − 15, 25x3 + 7, 75x4.
We can easily see that the optimal solution would be
x1 = 0, x2 = 0, x3 = 0, x4 = 100, spending all the money on snowboard sets.
The optimal value of zv = 775 has no meaning, but can be used to calculate
the proﬁt 25000 CZK and the risk of 500 points for the solution found.
Multi-criteria LP - conversion of criteria to constraints
The procedure is similar to the lexicographic method when we apply the
sequential conversion of criteria. Again, we assume that the functions are
ordered from the most to the least important. Finding a compromise solution
involves solving a sequence of optimization tasks
max. z1 = c1
· x, x ∈ X. Optimal value is denoted by z∗
1 . In the next step we
solve another problem for z2 allowing for a certain deviation of the ﬁrst criteria
from z∗
1 :
max. z2 = c2
· x, x ∈ X, c1
x ≥ z∗
1 − δ1. Again we ﬁnd z∗
2 and proceed further
until we ﬁnd a compromise solution as the solution of
max. zk = ck
· x, x ∈ X, c1
x ≥ z∗
1 − δ1, . . . , ck−1
x ≥ z∗
k−1 − δk .
Multi-criteria LP - conversion of criteria to constraints
The procedure is similar to the lexicographic method when we apply the
sequential conversion of criteria. Again, we assume that the functions are
ordered from the most to the least important. Finding a compromise solution
involves solving a sequence of optimization tasks
max. z1 = c1
· x, x ∈ X. Optimal value is denoted by z∗
1 . In the next step we
solve another problem for z2 allowing for a certain deviation of the ﬁrst criteria
from z∗
1 :
max. z2 = c2
· x, x ∈ X, c1
x ≥ z∗
1 − δ1. Again we ﬁnd z∗
2 and proceed further
until we ﬁnd a compromise solution as the solution of
max. zk = ck
· x, x ∈ X, c1
x ≥ z∗
1 − δ1, . . . , ck−1
x ≥ z∗
k−1 − δk .
We can also convert the criteria to the constraints simultaneously by
maximizing only the most important criterion z1 and adding to the model all
the conditions zi ≥ aui , i = 2, . . . k (aspiration levels of criteria aui , i = 2, . . . k
set somewhere between basal and ideal value for a given criterion
zmin
i , zmax
i .) The disadvantage of this approach is that it can be difﬁcult to set
aspiration levels correctly, so that the set is not empty and neither is the
signiﬁcance of the criteria completely eliminated.
Goal programming
It represents a different approach to solving LP problems. Instead of
distinguishing constraints and the criterion of optimality, ﬁxed and free goals
assigned with target values are used. The value of ﬁxed targets have to be
reached exactly (analogy of limiting conditions). For free targets, we can
achieve both higher and lower values than the target (but it must not differ too
much). Since there are in general many target values and not all of them can
be reached, one of two approaches is usually chosen:
using preference information - the goal of top priority is optimized ﬁrst,
etc.
using weights - coefﬁcients expressing the importance of respective
goals; then the weighted sum of deviations from all targets is optimized
Goal programming models are more general than standard LP models and
they often better represent real situations in applications.
Goal programming - example
Example from J. Jablonský, „Operational Research“: Management of the
pension fund decides to purchase two types of assets (shares and bonds).
There is a budget that can not be exceeded. Up to 50% of the total budget
can be invested in the shares and the maximum of 75 % of money in the
funds. Expected revenues are is 15 % from shares and alert 10 % from
bonds, the risk of the investment is rated at 5 pts for shares and 2 pts for
bonds. Design a portfolio [x1, x2] to achieve the average return of 12 % p.a.
and risk equal to 3 points of risk .
Goal programming - example
Example from J. Jablonský, „Operational Research“: Management of the
pension fund decides to purchase two types of assets (shares and bonds).
There is a budget that can not be exceeded. Up to 50% of the total budget
can be invested in the shares and the maximum of 75 % of money in the
funds. Expected revenues are is 15 % from shares and alert 10 % from
bonds, the risk of the investment is rated at 5 pts for shares and 2 pts for
bonds. Design a portfolio [x1, x2] to achieve the average return of 12 % p.a.
and risk equal to 3 points of risk .
In the standard LP approach, we would have to choose one of the criteria as
the objective function (let’s say revenue) and maximize it under conditions,
that the risk cannot exceed 3 points. It can be veriﬁed that the optimal solution
can be reached in this approach if 1
3 of funds would be invested into shares
and 2
3 into bonds. At the average risk equal to 3 points, we get return 11,67 %
p.a.
Goal programming - example
Example from J. Jablonský, „Operational Research“: Management of the
pension fund decides to purchase two types of assets (shares and bonds).
There is a budget that can not be exceeded. Up to 50% of the total budget
can be invested in the shares and the maximum of 75 % of money in the
funds. Expected revenues are is 15 % from shares and alert 10 % from
bonds, the risk of the investment is rated at 5 pts for shares and 2 pts for
bonds. Design a portfolio [x1, x2] to achieve the average return of 12 % p.a.
and risk equal to 3 points of risk .
In the standard LP approach, we would have to choose one of the criteria as
the objective function (let’s say revenue) and maximize it under conditions,
that the risk cannot exceed 3 points. It can be veriﬁed that the optimal solution
can be reached in this approach if 1
3 of funds would be invested into shares
and 2
3 into bonds. At the average risk equal to 3 points, we get return 11,67 %
p.a.
Similarly, we can minimize the objective function expressed by the weighted
risk with an additional condition that the average yield is at least 12 % p.a. We
can get the solution that it is optimal to invest 40 % into shares and 60 % into
bonds. At the return 12% p.a. the risk rate will be 3.2 points.
Goal programming - model formulation
We use deviation variables for expressing positive or negative slacks in free
goals (we denote them by d+
i or d−
i respectively). If the target value is
achieved, then d+
i = d−
i = 0. If the target is exceeded, then d+
i > 0, d−
i = 0,
and if the goal is not achieved, then d+
i = 0, d−
i > 0. Fixed targets must be
respected, no deviations are allowed.
Goal programming - model formulation
We use deviation variables for expressing positive or negative slacks in free
goals (we denote them by d+
i or d−
i respectively). If the target value is
achieved, then d+
i = d−
i = 0. If the target is exceeded, then d+
i > 0, d−
i = 0,
and if the goal is not achieved, then d+
i = 0, d−
i > 0. Fixed targets must be
respected, no deviations are allowed.
In the goal programming model, the objective function is always expressed as
minimizing deviation variables, including either positive, negative or both types
of deviations (then we approach the target values from the top or bottom or
from both sides). Therefore, a portfolio optimization problem formulation
would be:
d+
2 , d−
1 → min,
subject to:
x1 + x2 ≤ 1
x1 ≤ 0, 5; x2 ≤ 0, 75
15x1 + 10x2 + d+
1 − d−
1 = 12
5x1 + 2x2 + d+
2 − d−
2 = 3
x1, x2, d+
1 , d−
1 , d+
2 , d−
2 ≥ 0
Goal programming - weights method
While minimizing multiple deviations, we can express their importance by
weights. In order to avoid problems with different units, it is better to work with
relative deviations
d+
i
gi
,
d−
i
gi
, where gi is i-th goal. If the return is ﬁve times more
important than the risk, we will set the weights equal to 5 and 1 and the
objective function will take the form z = 5
d−
1
12 +
d+
2
3 . The problem can be
solved by a simplex method.
Goal programming - weights method
While minimizing multiple deviations, we can express their importance by
weights. In order to avoid problems with different units, it is better to work with
relative deviations
d+
i
gi
,
d−
i
gi
, where gi is i-th goal. If the return is ﬁve times more
important than the risk, we will set the weights equal to 5 and 1 and the
objective function will take the form z = 5
d−
1
12 +
d+
2
3 . The problem can be
solved by a simplex method.
The solution is to invest 1
3 of funds to shares and 2
3 to bonds; the target value
of the risk is achieved and the return is 11.67%.
Goal programming - preemptive method
In the preemptive method, we start by minimizing the deviation from a more
important goal. If we get more solutions, we minimize the second most
important deviation on this set, etc. If the priority of return is higher in our
portfolio problem, we minimize d−
1 ﬁrst.
Goal programming - preemptive method
In the preemptive method, we start by minimizing the deviation from a more
important goal. If we get more solutions, we minimize the second most
important deviation on this set, etc. If the priority of return is higher in our
portfolio problem, we minimize d−
1 ﬁrst.
The situation can be visualized in the plane x1, x2.
First, we show a feasible set M where all ﬁxed targets are met.
Goal programming - preemptive method
In the preemptive method, we start by minimizing the deviation from a more
important goal. If we get more solutions, we minimize the second most
important deviation on this set, etc. If the priority of return is higher in our
portfolio problem, we minimize d−
1 ﬁrst.
The situation can be visualized in the plane x1, x2.
The line 15x1 + 10x2 = 12 corresponds to the lowest possible value of d−
1 = 0.
Its intersection with M represents all the optimal solutions in the ﬁrst step.
Goal programming - preemptive method
In the preemptive method, we start by minimizing the deviation from a more
important goal. If we get more solutions, we minimize the second most
important deviation on this set, etc. If the priority of return is higher in our
portfolio problem, we minimize d−
1 ﬁrst.
The situation can be visualized in the plane x1, x2.
In the second step, we minimize the deviation d+
2 . Zero value of this deviation
is achieved on the line 5x1 + 2x2 = 3.
Goal programming - preemptive method
In the preemptive method, we start by minimizing the deviation from a more
important goal. If we get more solutions, we minimize the second most
important deviation on this set, etc. If the priority of return is higher in our
portfolio problem, we minimize d−
1 ﬁrst.
The situation can be visualized in the plane x1, x2.
Since the lines intersect outside the feasible set, the equality d+
2 = 0 cannot
be satisﬁed. We have to raise the risk, i.e. to move the blue line so that it
intersects with the optimal line for d−
1 inside M. We’ve found the optimum
point x∗
= [0, 4; 0, 6].
Linear fractional programming
A class of problems that can be converted to a linear program, is represented
by problems of linear fractional programming, i. e. to optimize a function
f(x) = d ·x+d0
c ·x+c0
subject to x ≥ 0, A · x ≤ b. Assuming positivity of the
denominator c · x + c0 > 0, we can use the substitution r = 1
c ·x+c0
. We get
the objective function in the form f = d · x · r + d0r, which can be linearized
after introducing new variables r, yi = xi · r, i = 1, . . . , n:
f(r, y1, . . . yn) = d · y + d0r . Similar linearization can be used for the
constraints r ≥ 0, y ≥ 0, A · y ≤ b · r . We must not forget to add another
constraint given by the deﬁnition of variable r, i.e. 1 = r(c · x + c0) or in
linear form: 1 = c · y + c0r .
We have a common LP problem, which can be solved e.g. by the simplex
method.
Linear fractional programming - example
In corporate economy, many indicators of a ratio type are used. If the
expressions in the numerator and the denominator of the indicator are linear
functions of the variables, optimizing the indicator is a problem of linear
fractional programming, see the example from the book I. Gros: "Kvantitativní
metody v manažerském rozhodování":
Linear fractional programming - example
In corporate economy, many indicators of a ratio type are used. If the
expressions in the numerator and the denominator of the indicator are linear
functions of the variables, optimizing the indicator is a problem of linear
fractional programming, see the example from the book I. Gros: "Kvantitativní
metody v manažerském rozhodování":
Example: Let us consider the company that has three products A, B and C in
the production program with the following characteristics:
Product Variable costs [CZK/t] Price [CZK/t]
A 11 000 12 000
B 15 000 18 000
C 14 000 16 000
ﬁxed costs 150 000 CZK
If we denote the amount of the respective products sold by x1, x2, x3, we can
deﬁne for example following indicators:
cost of sales z = 11000x1+15000x2+14000x3+150000
12000x1+18000x2+16000x3
,
proﬁtability of sales z = 1000x1+3000x2+2000x3−150000
12000x1+18000x2+16000x3
.
Linear fractional programming - example
Example: Minimize the cost of sales from this example, provided that the total
cost does not exceed 200 000 CZK.
Linear fractional programming - example
Example: Minimize the cost of sales from this example, provided that the total
cost does not exceed 200 000 CZK.
Mathematical formulation: minimize z = 11x1+15x2+14x3+150
12x1+18x2+16x3
subject to 11x1 + 15x2 + 14x3 + 150 ≤ 200, x1, x2, x3 ≥ 0.
Linear fractional programming - example
Example: Minimize the cost of sales from this example, provided that the total
cost does not exceed 200 000 CZK.
Mathematical formulation: minimize z = 11x1+15x2+14x3+150
12x1+18x2+16x3
subject to 11x1 + 15x2 + 14x3 + 150 ≤ 200, x1, x2, x3 ≥ 0.
After the substitution r = 1
12x1+18x2+16x3
we get the problem of minimizing
function
f(y1, y2, y3, r) = 11y1 + 15y2 + 14y3 + 150r
subject to 11y1 + 15y2 + 14y3 − 50r ≤ 0, y1, y2, y3, r ≥ 0 and additional
condition 12y1 + 18y2 + 16y3 = 1
Linear fractional programming - example
Example: Minimize the cost of sales from this example, provided that the total
cost does not exceed 200 000 CZK.
Mathematical formulation: minimize z = 11x1+15x2+14x3+150
12x1+18x2+16x3
subject to 11x1 + 15x2 + 14x3 + 150 ≤ 200, x1, x2, x3 ≥ 0.
After the substitution r = 1
12x1+18x2+16x3
we get the problem of minimizing
function
f(y1, y2, y3, r) = 11y1 + 15y2 + 14y3 + 150r
subject to 11y1 + 15y2 + 14y3 − 50r ≤ 0, y1, y2, y3, r ≥ 0 and additional
condition 12y1 + 18y2 + 16y3 = 1
Similar procedure can be used for the problem of maximizing the proﬁtability
of sales.
Introduction
Data envelopment analysis (DEA) is used to evaluate the technical efﬁciency
of production units based on the size of inputs and outputs (without the need
for pricing).
Introduction
Data envelopment analysis (DEA) is used to evaluate the technical efﬁciency
of production units based on the size of inputs and outputs (without the need
for pricing).
History:
1957: Farrell: model for one input and one output
1978: Charnes, Cooper, Rhodes: CCR model: multiple inputs and outputs,
constant returns to scale
1984: Banker, Charnes, Cooper: BCC model: variable returns to scale
Introduction
Data envelopment analysis (DEA) is used to evaluate the technical efﬁciency
of production units based on the size of inputs and outputs (without the need
for pricing).
History:
1957: Farrell: model for one input and one output
1978: Charnes, Cooper, Rhodes: CCR model: multiple inputs and outputs,
constant returns to scale
1984: Banker, Charnes, Cooper: BCC model: variable returns to scale
Let us consider homogeneous production units consuming the same type of
resources (material, ﬂoor area, workers, etc.), so-called inputs, to produce
equivalent effects (sales, proﬁts, number of serviced clients), i.e. outputs. If
there is only one input and one output, it is easy to express efﬁciency using
the ratio indicator
efﬁciency = input/output
Introduction
Data envelopment analysis (DEA) is used to evaluate the technical efﬁciency
of production units based on the size of inputs and outputs (without the need
for pricing).
History:
1957: Farrell: model for one input and one output
1978: Charnes, Cooper, Rhodes: CCR model: multiple inputs and outputs,
constant returns to scale
1984: Banker, Charnes, Cooper: BCC model: variable returns to scale
Let us consider homogeneous production units consuming the same type of
resources (material, ﬂoor area, workers, etc.), so-called inputs, to produce
equivalent effects (sales, proﬁts, number of serviced clients), i.e. outputs. If
there is only one input and one output, it is easy to express efﬁciency using
the ratio indicator
efﬁciency = input/output
An aggregation indicator can be constructed for multiple inputs and outputs
efﬁciency = weighted inputs/weighted outputs
One output/ one input model
Let us consider 8 branches of a business ﬁrm, which are characterized by one
input (number of employees) and one output (the number of contracts
concluded with clients). Their efﬁciency can be expressed using the indicator
"number of contracts per employee"; data are recorded in the table:
branch A B C D E F G H
employees 2 3 3 4 5 5 6 8
contracts 1 3 2 3 4 2 3 5
efﬁciency 0,5 1 0,667 0,75 0,8 0,4 0,5 0,625
One output/ one input model
We represent the data graphically, see Fig:
One output/ one input model
We represent the data graphically, see Fig:
One output/ one input model
We represent the data graphically, see Fig:
The efﬁciency of a given branch is indicated by the slope of the line
connecting the point to the origin. The highest value of the slope is obtained
for branch B - this line will be called the efﬁcient frontier.
One output/ one input model
We represent the data graphically, see Fig:
Efﬁciency of a given branch is indicated by the slope of the line connecting the
point to the origin. The line with the largest slope is obtained for branch B this
line will be called the efﬁcient frontier. The branch B is the best and the
efﬁciency of other units can be expressed relatively as the ratio of their slopes
to the slope of B. For example Efﬁciency of A / Efﬁciency of B =0.5 meaning
that unit A is only 50% efﬁcient compared to B. This relative measure acquires
values from [0, 1] for all branches and is independent of units used for input
and output.
One output/ one input model
How can unit A achieve 100% value of efﬁciency score, i.e. reach effective
frontier? It can reduce inputs while maintaining outputs (input-oriented model,
graphically represented by the point A1) or increase output while maintaining
inputs (output-oriented model, graphically represented by the point A2) or
change both. Units A1, A2 are called virtual, they represent no real branch.
Line segment A1A2 represents all points on the efﬁcient frontier, that are
reachable from A without increasing the number of employees or reducing the
number of contracts.
One output/ one input model
Let’s denote the coordinates of the points A[x, y], A1[x1, y1], A2[x2, y2]. The
points A1, A2 are on the efﬁcient frontier, so we can substitute coordinates of
these virtual units to the denominator of the ratio expressing relative efﬁciency
of A.
We have
x
y /x1
y1
= x/x1 , because y = y1
or
x
y /x2
y2
= y2/y , because x = x2.
One output/ one input model
Let’s denote the coordinates of the points A[x, y], A1[x1, y1], A2[x2, y2]. The
points A1, A2 are on the efﬁcient frontier, so we can substitute coordinates of
these virtual units to the denominator of the ratio expressing relative efﬁciency
of A.
We have
x
y /x1
y1
= x/x1 , because y = y1
or
x
y /x2
y2
= y2/y , because x = x2.
In the output-oriented model, we can interpret relative efﬁciency as a
necessary increase in output, y2
y = 2
1 = 2, so the branch A can reach the
efﬁcient frontier by doubling the number of contracts.
For the input-oriented model, the reciprocal of relative efﬁciency represents
necessary input reduction, x1
x = 1
2 = 0, 5, so the branch A would lay on the the
efﬁcient frontier with half of the employees.
One output/ one input model
Until now, we have assumed constant returns to scale, so the efﬁcient frontier
was formed by ray going from the origin to the most efﬁcient unit. For every
unit with the coordinates [x, y], the input and output [αx, αy] are feasible for
every α > 0 under CRS assumption. The efﬁciency score is independent of
the input/output orientation.
One output/ one input model
Until now, we have assumed constant returns to scale, so the efﬁcient frontier
was formed by ray going from the origin to the most efﬁcient unit. For every
unit with the coordinates [x, y], the input and output [αx, αy] are feasible for
every α > 0 under CRS assumption. The efﬁciency score is independent of
the input/output orientation.
Let’s redraw the efﬁcient frontier assuming variable returns to scale.
Units E and H are fully efﬁcient under VRS assumption.
One output/ one input model
The efﬁciency scores differ according to the orientation of the VRS model. For
example unit F achieves the score efﬁciency F1 / efﬁciency F = 2/5 = 0,4,
under input orientation, whereas its score is
efﬁciency F/efﬁciency E = 1/2= 0,5 under output orientation.
Two inputs and one output
Consider an example of 9 stores with inputs given by the number of
employees (in tens) and the ﬂoor area ( 1000 m2
) and annual sales (in
1000000 CZK) on the output side. Let’s assume constant returns to scale. For
the sake of comparability, we can further consider the input values per 1
million of CZK of the sales. The normalized values are listed in the table.
Store A B C D E F G H I
employees 4 7 8 4 2 5 6 5.5 6
area 3 3 1 2 4 2 4 2.5 2.5
sales 1 1 1 1 1 1 1 1 1
Two inputs and one output
In the graphical representation, those stores that are closer to the origin
appear to be more efﬁcient. The efﬁcient frontier envelops the data as follows:
Two inputs and one output
In the graphical representation, those stores that are closer to the origin
appear to be more efﬁcient. The efﬁcient frontier envelops the data as follows:
Store A is inefﬁcient, its efﬁciency can be measured radially as
|OP|
|OA| = 0.8571 . Virtual unit P is convex combination of D and E which are
called peer units of A.
Two inputs and one output
In the graphical representation, those stores that are closer to the origin
appear to be more efﬁcient. The efﬁcient frontier envelops the data as follows:
Store A is inefﬁcient, its efﬁciency can be measured radially as
|OP|
|OA| = 0.8571 . Virtual unit P is a convex combination of D and E which are
called peer units of A. Efﬁcient frontier can be achieved by proportionally
reducing both inputs by 15% or different way; decreasing one input while
maintaining the level of the second one is demonstrated by the points A1, D.
One input and two outputs
Now consider the case of 1 input (number of traders) and two outputs
(customers and sales) at 7 sales ofﬁces. The values of the outputs per 1
trader for individual branches are listed in the table.
Ofﬁce A B C D E F G
traders 1 1 1 1 1 1 1
customers 1 2 3 4 4 5 6
sales 5 7 4 3 6 5 2
One input and two outputs
We can depict each ofﬁce by its unitary outputs; the efﬁcient frontier will
envelop the data from the opposite side, because the points lying closer to the
origin represent less efﬁcient units (units A, C, D).
One input and two outputs
We can depict each ofﬁce by its unitary outputs; the efﬁcient frontier will
envelop the data from the opposite side, because the points lying closer to the
origin represent less efﬁcient units (units A, C, D).
We can measure the efﬁciency radially, e.g. for unit D we have |OD|
|OP| = 0.75 .
For unit Q we have this measure equal to 1. This fact doesn’t mean that Q is
fully efﬁcient; one can still increase sales in Q without losing clients to the
level of B.)
CCR model
Consider n decision making units (DMUs) U1, . . . , Un transforming m inputs
into r outputs. We will use the notation xiq for i-th input of q-th DMU and yjq for
j-th output of q-th DMU. The values of Uq can be arranged into vectors
xq = (x1q, . . . , xmq) , yq = (y1q, . . . , yrq) and these vectors can be arranged
into matrices
X = [xiq]
i=1,...,m
q=1,...,n
, Y = [yjq]
j=1,...,r
q=1,...,n
.
CCR model
Consider n decision making units (DMUs) U1, . . . , Un transforming m inputs
into r outputs. We will use the notation xiq for i-th input of q-th DMU and yjq for
j-th output of q-th DMU. The values of Uq can be arranged into vectors
xq = (x1q, . . . , xmq) , yq = (y1q, . . . , yrq) and these vectors can be arranged
into matrices
X = [xiq]
i=1,...,m
q=1,...,n
, Y = [yjq]
j=1,...,r
q=1,...,n
.
By introducing nonnegative weights v = (v1, . . . , vm), u = (u1, . . . , ur ) we can
deﬁne for every unit Uq its
virtual input = v1x1q + . . . + vmxmq = vxq and
virtual output = u1y1q + . . . + ur yrq = uyq.
The efﬁciency of the decision making unit can be expressed as the ratio of its
virtual output and input.
CCR model
Consider n decision making units (DMUs) U1, . . . , Un transforming m inputs
into r outputs. We will use the notation xiq for i-th input of q-th DMU and yjq for
j-th output of q-th DMU. The values of Uq can be arranged into vectors
xq = (x1q, . . . , xmq) , yq = (y1q, . . . , yrq) and these vectors can be arranged
into matrices
X = [xiq]
i=1,...,m
q=1,...,n
, Y = [yjq]
j=1,...,r
q=1,...,n
.
By introducing nonnegative weights v = (v1, . . . , vm), u = (u1, . . . , ur ) we can
deﬁne for every unit Uq its
virtual input = v1x1q + . . . + vmxmq = vxq and
virtual output = u1y1q + . . . + ur yrq = uyq.
The efﬁciency of the decision making unit can be expressed as the ratio of its
virtual output and input.
In the CCR model we optimize input and output weights so that efﬁciency of
the unit Uq, z =
u1y1q+...+ur yrq
v1x1q+...+vmxmq
=
uyq
vxq
is maximal subject to the constraints
that efﬁciency of other unit is less or equal to 1. If there exist positive solution
with optimal objective value z∗
= 1, the unit Uq is said to be CCR efﬁcient.
Input-oriented CCR model
The model for DMU Uq can be formulated as fractional linear program
z =
u1y1q+...+ur yrq
v1x1q+...+vmxmq
→ maxu,v
subject to
u1y1k +...+ur yrk
v1x1k +...+vmxmk
≤ 1, k = 1, . . . n,
ui ≥ 0, vj ≥ 0, i = 1, . . . m, j = 1, . . . r.
Input-oriented CCR model
The model for DMU Uq can be formulated as fractional linear program
z =
u1y1q+...+ur yrq
v1x1q+...+vmxmq
→ maxu,v
subject to
u1y1k +...+ur yrk
v1x1k +...+vmxmk
≤ 1, k = 1, . . . n,
ui ≥ 0, vj ≥ 0, i = 1, . . . m, j = 1, . . . r.
The problem is easy to linearize using Charnes-Cooper transformation:
z = u1y1q + . . . + ur yrq → maxu,v
za omezení
v1x1q + . . . + vmxmq = 1
u1y1k + . . . + ur yrk ≤ v1x1k + . . . + vmxmk , k = 1, . . . n,
ui ≥ 0, vj ≥ 0, i = 1, . . . m, j = 1, . . . r.
Input-oriented CCR model
The model for DMU Uq can be formulated as fractional linear program
z =
u1y1q+...+ur yrq
v1x1q+...+vmxmq
→ maxu,v
subject to
u1y1k +...+ur yrk
v1x1k +...+vmxmk
≤ 1, k = 1, . . . n,
ui ≥ 0, vj ≥ 0, i = 1, . . . m, j = 1, . . . r.
The problem is easy to linearize using Charnes-Cooper transformation:
z = u1y1q + . . . + ur yrq → maxu,v
za omezení
v1x1q + . . . + vmxmq = 1
u1y1k + . . . + ur yrk ≤ v1x1k + . . . + vmxmk , k = 1, . . . n,
ui ≥ 0, vj ≥ 0, i = 1, . . . m, j = 1, . . . r.
This problem is called Input-oriented CCR model. The set of indexes
k ∈ {1, . . . n} of efﬁcient units, which correspond to binding constraints for Uq,
deﬁnes peer DMUs for Uq.
CCR model - example
Let’s consider the problem of 6 DMUs with two inputs and one output:
Unit A B C D E F
x1 4 7 8 4 2 10
x2 3 3 1 2 4 1
y 1 1 1 1 1 1
CCR model - example
Let’s consider the problem of 6 DMUs with two inputs and one output:
Unit A B C D E F
x1 4 7 8 4 2 10
x2 3 3 1 2 4 1
y 1 1 1 1 1 1
Linearized problem for unit A is to be:
z = u → max
subject to
4v1 + 3v2 = 1, u, v1, v2 ≥ 0
u ≤ 4v1 + 3v2 (A) u ≤ 7v1 + 3v2 (B)
u ≤ 8v1 + v2 (C) u ≤ 4v1 + 2v2 (D)
u ≤ 2v1 + 4v2 (E) u ≤ 10v1 + v2 (F)
CCR model - example
Let’s consider the problem of 6 DMUs with two inputs and one output:
Unit A B C D E F
x1 4 7 8 4 2 10
x2 3 3 1 2 4 1
y 1 1 1 1 1 1
Linearized problem for unit A is to be:
z = u → max
subject to
4v1 + 3v2 = 1, u, v1, v2 ≥ 0
u ≤ 4v1 + 3v2 (A) u ≤ 7v1 + 3v2 (B)
u ≤ 8v1 + v2 (C) u ≤ 4v1 + 2v2 (D)
u ≤ 2v1 + 4v2 (E) u ≤ 10v1 + v2 (F)
The problem can be solved by standard methods of linear programming. The
solution for DMU A is z∗
= u∗
= 6/7, v∗
1 = v∗
2 = 1/7 . Unit A is not efﬁcient,
because z∗
= 6/7 ≤ 1. Constraints corresponding to the units D, E are
binding, hence D,E are peer units for A.
CCR model - example
Problems for remaining DMUs are similar, they differ only in an equality
constraint; it will be 7v1 + 3v2 = 1 for unit B, etc. Table summarizes results for
all DMUs:
DMU x1 x2 y v∗
1 v∗
2 z∗
= u∗
peer units
A 4 3 1 1/7 1/7 6/7 D,E
B 7 3 1 1/19 4/19 12/19 C,D
C 8 1 1 1/12 1/3 1 C
D 4 2 1 1/6 1/6 1 D
E 2 4 1 3/14 1/7 1 E
F 10 1 1 0 1 1 C
CCR model - example
Problems for remaining DMUs are similar, they differ only in an equality
constraint; it will be 7v1 + 3v2 = 1 for unit B, etc. Table summarizes results for
all DMUs:
DMU x1 x2 y v∗
1 v∗
2 z∗
= u∗
peer units
A 4 3 1 1/7 1/7 6/7 D,E
B 7 3 1 1/19 4/19 12/19 C,D
C 8 1 1 1/12 1/3 1 C
D 4 2 1 1/6 1/6 1 D
E 2 4 1 3/14 1/7 1 E
F 10 1 1 0 1 1 C
We can see that units C,D,E are efﬁcient and their scores are equal to 1.
Optimal objective value for F is equal to 1 as well, but its peer unit is C,
because it has the same input v2, but lesser input v1. It must be emphasized
that a unit is CCR efﬁcient, iff z∗
= 1 and the solution satisﬁes u∗
> 0, v∗
> 0.
Requirement on positivity of weights can be embedded directly in the model
by changing the right-hand side of the constraint to an ε > 0.
CCR model - dual problem
Let’s rewrite the CCR model for Uq using matrix notation:
z = uyq → maxu,v
subject to:
vxq = 1
uY ≤ vX,
u, v ≥ 0.
CCR model - dual problem
Let’s rewrite the CCR model for Uq using matrix notation:
z = uyq → maxu,v
subject to:
vxq = 1
uY ≤ vX,
u, v ≥ 0.
We can formulate dual problem by introducing dual variables θ and
λ = (λ1, . . . λn) :
z = θ → minθ,λ
subject to:
θxq ≥ Xλ,
Yλ ≥ yq,
λ ≥ 0
Using duality is suitable for computational and interpretation reasons.
Dual CCR model - interpretation
The model looks for a virtual unit with inputs and outputs Xλ, Yλ that is better
or at least comparable to the radial projection of the evaluated unit Uq at the
effective boundary: θxq ≥ Xλ, Yλ ≥ yq
Dual CCR model - interpretation
The model looks for a virtual unit with inputs and outputs Xλ, Yλ that is better
or at least comparable to the radial projection of the evaluated unit Uq at the
effective boundary: θxq ≥ Xλ, Yλ ≥ yq
The unit Uq under evaluation lies directly at the efﬁcient frontier if it is identical
to the corresponding virtual unit. Therefore, the optimal value of the objective
function θ∗
(so-called Farrell efﬁciency) must necessarily be equal to 1. It
represents necessary radial reduction of inputs needed for achieving the
frontier performance. When condition θ∗
= 1 holds, the unit Uq is called
technically efﬁcient.
Dual CCR model - interpretation
The model looks for a virtual unit with inputs and outputs Xλ, Yλ that is better
or at least comparable to the radial projection of the evaluated unit Uq at the
effective boundary: θxq ≥ Xλ, Yλ ≥ yq
The unit Uq under evaluation lies directly at the efﬁcient frontier if it is identical
to the corresponding virtual unit. Therefore, the optimal value of the objective
function θ∗
(so-called Farrell efﬁciency) must necessarily be equal to 1. It
represents necessary radial reduction of inputs needed for achieving the
frontier performance. When condition θ∗
= 1 holds, the unit Uq is called
technically efﬁcient.
To achieve CCR-efﬁciency, it is necessary that all slacks in the inequality
constraints are zeros:
s−
= θxq − Xλ = 0, s+
= Yλ − yq = 0 .
Dual CCR model - interpretation
The model looks for a virtual unit with inputs and outputs Xλ, Yλ that is better
or at least comparable to the radial projection of the evaluated unit Uq at the
effective boundary: θxq ≥ Xλ, Yλ ≥ yq
The unit Uq under evaluation lies directly at the efﬁcient frontier if it is identical
to the corresponding virtual unit. Therefore, the optimal value of the objective
function θ∗
(so-called Farrell efﬁciency) must necessarily be equal to 1. It
represents necessary radial reduction of inputs needed for achieving the
frontier performance. When condition θ∗
= 1 holds, the unit Uq is called
technically efﬁcient.
To achieve CCR-efﬁciency, it is necessary that all slacks in the inequality
constraints are zeros:
s−
= θxq − Xλ = 0, s+
= Yλ − yq = 0 .
When all the above mentioned conditions are satisﬁed, the unit is efﬁcient
according to Pareto-Koopmans deﬁnition of efﬁciency, i.e. it is not possible to
improve any input or output without worsening the other.
Dual CCR model - alternative formulation
Consider primal CCR model with positivity constraint for weights u, v ≥ ε > 0
and denote e = (1, . . . , 1) . Dual problem can be formulated as follows
z = θ − ε · (e · s+
+ e · s−
) → minθ,λ,s+, s−
subject to
s−
= θxq − Xλ,
s+
= Yλ − yq,
λ, s+
, s−
≥ 0
Dual CCR model - alternative formulation
Consider primal CCR model with positivity constraint for weights u, v ≥ ε > 0
and denote e = (1, . . . , 1) . Dual problem can be formulated as follows
z = θ − ε · (e · s+
+ e · s−
) → minθ,λ,s+, s−
subject to
s−
= θxq − Xλ,
s+
= Yλ − yq,
λ, s+
, s−
≥ 0
Optimal solution for Uq deﬁnes how to improve inputs and outputs to xq, yq by
means of CCR - projection:
xq = θ∗
xq − s−∗
, yq = yq + s+∗
,
or equivalently
xq = Xλ∗
, yq = Yλ∗
.
The indexes j ∈ {1, . . . , n}, corresponding to positive λ∗
j , determine peer units
for Uq.
Output-oriented CCR model
We can also deﬁne Output-oriented CCR model for Uq, let’s formulate it using
modiﬁed dual problem:
z = Θ + ε · (e · s+
+ e · s−
) → maxΘ,λ,s+, s−
subject to
s−
= xq − Xλ,
s+
= Yλ − Θyq,
λ, s+
, s−
≥ 0
Output-oriented CCR model
We can also deﬁne Output-oriented CCR model for Uq, let’s formulate it using
modiﬁed dual problem:
z = Θ + ε · (e · s+
+ e · s−
) → maxΘ,λ,s+, s−
subject to
s−
= xq − Xλ,
s+
= Yλ − Θyq,
λ, s+
, s−
≥ 0
If Θ∗
> 1, the unit Uq is not efﬁcient and value of Θ∗
expresses necessary
proportional increase of outputs. CCR projection can be deﬁned analogically
as
xq = Xλ∗
, yq = Yλ∗
.
Output-oriented CCR model
We can also deﬁne Output-oriented CCR model for Uq, let’s formulate it using
modiﬁed dual problem:
z = Θ + ε · (e · s+
+ e · s−
) → maxΘ,λ,s+, s−
subject to
s−
= xq − Xλ,
s+
= Yλ − Θyq,
λ, s+
, s−
≥ 0
If Θ∗
> 1, the unit Uq is not efﬁcient and value of Θ∗
expresses necessary
proportional increase of outputs. CCR projection can be deﬁned analogically
as
xq = Xλ∗
, yq = Yλ∗
.
It is true in CCR model that the input-oriented efﬁciency is the reciprocal of
output-oriented efﬁciency, θ∗
· Θ∗
= 1
Output-oriented BCC model
As a modiﬁcation of the CCR model, which assumes constant returns to scale
and deﬁnes a conical envelope of the data, Banker, Charnes and Cooper
introduced a model using variable returns to scale, so-called BCC model. This
approach deﬁnes a convex envelope of the data, virtual units are not arbitrary
non-negative combinations Xλ, Yλ, the coefﬁcients must also satisfy another
condition, eλ = 1 . Due to this additional constraint, there are usually more
units efﬁcient under BCC speciﬁcation.
Output-oriented BCC model
As a modiﬁcation of the CCR model, which assumes constant returns to scale
and deﬁnes a conical envelope of the data, Banker, Charnes and Cooper
introduced a model using variable returns to scale, so-called BCC model. This
approach deﬁnes a convex envelope of the data, virtual units are not arbitrary
non-negative combinations Xλ, Yλ, the coefﬁcients must also satisfy another
condition, eλ = 1 . Due to this additional constraint, there are usually more
units efﬁcient under BCC speciﬁcation.
Let’s formulate the input-oriented BCC model:
z = θ − ε · (e · s+
+ e · s−
) → minθ,λ,s+, s−
subject to
s−
= θxq − Xλ,
s+
= Yλ − yq,
eλ = 1
λ, s+
, s−
≥ 0
Output-oriented BCC model
As a modiﬁcation of the CCR model, which assumes constant returns to scale
and deﬁnes a conical envelope of the data, Banker, Charnes and Cooper
introduced a model using variable returns to scale, so-called BCC model. This
approach deﬁnes a convex envelope of the data, virtual units are not arbitrary
non-negative combinations Xλ, Yλ, the coefﬁcients must also satisfy another
condition, eλ = 1 . Due to this additional constraint, there are usually more
units efﬁcient under BCC speciﬁcation.
Let’s formulate the input-oriented BCC model:
z = θ − ε · (e · s+
+ e · s−
) → minθ,λ,s+, s−
subject to
s−
= θxq − Xλ,
s+
= Yλ − yq,
eλ = 1
λ, s+
, s−
≥ 0
BCC efﬁcient are those units that have θ∗
= 1, s+∗
= 0, s−∗
= 0.
Alternative DEA models
In addition to the basic DEA models, a number of modiﬁcations have been
proposed, among others:
Additive model SBM (Slack-Based Measure) model: it is not necessary to
specify input or output orientation, the efﬁciency is expressed using
additional variables s−
, s+
DEA models with non-controllable inputs or outputs
DEA models with undesirable inputs or outputs
Superefﬁciency models
discrete models, e.g. FDH (Free Disposable Hull) model
Malmquist index for the efﬁciency change in time
Methods are described in more detail in the books
S. C. Ray: Data Envelopment Analysis: Theory and Techniques for
Economics and Operations Research, Cambridge 2004
W. W. Cooper, L. M. Seiford, K. Tone: Data Envelopement Analysis,
Springer, New York 2007