Multiobjective Linear Programming Using
Lexicographic, Ꜫ-constrained, Weighted
Sum, and Minimax Methods with
Graphical Representation.
Prepared by Krishnendranath Mitra.
Linear programming is a mathematical programming technique used to find the maximum or
minimum value of a linear objective function while satisfying all the linear constraints.
Multiobjective linear programming provides optimal solutions where some trade-offs are
made for the individual objectives of its multiple conflicting objectives. This document
demonstrates four mathematical modelling approaches for multiobjective optimization,
namely lexicographic method, Ꜫ-constrained method, weighted sum method, and modified
weighted sum method with minimax objective. It uses a simple example to explain the
concepts and the graphical representations for these methods are intended to enhance the
ease of understanding the concepts.
Multiobjective Optimization:
Multiobjective optimization, also known as multicriteria optimization or Pareto optimization,
is a mathematical approach used to solve problems involving multiple conflicting objectives.
In real-world scenarios, decision makers often need to consider multiple, often conflicting,
criteria simultaneously. For example, in engineering design, one might aim to minimize cost
while maximizing performance and minimizing environmental impact.
Single objective optimization focuses on optimizing a single criterion or objective function,
aiming to find the best solution. A solution of an optimization problem is the set of values of
all decision variables at a given condition. Decision variables are those entities whose optimal
values represent the best decisions and are the outcomes of the optimization process.
1
Contact for any query:
,Optimization means maximizing or minimizing the value of an objective function, by changing
the values of the decision variables, such that all the constraints are satisfied. If even one of
the constraints is violated, the solution is infeasible. Solutions that satisfy all constraints are
called feasible solutions and all feasible solutions together constitute the feasible region.
Solutions that lie outside the feasible region are infeasible and need to be rejected straight
away from the optimization process.
Among the feasible solutions of a linear programming problem, those lying at corners of the
feasible region are called corner-point feasible solutions. These corners of the feasible region
are formed by the intersection of two or more constraint functions. In single objective linear
programming problems, the optimal solution is always a corner-point feasible solution. If the
objective line is parallel to a constraint line, the optimality may be obtained along the length
of that constraint function at the feasible region boundary. In such a case, there can be
multiple optimal solutions for the single objective between two adjacent corner-points. The
optimal values of the decision variables differ in these multiple solutions but the optimal
objective function value remains the same.
In case of multiobjective functions, there will be multiple optimal solutions, meaning that the
values of the set of all decision variables at each optimal solution will differ. However, unlike
multiple optimal solutions in a single objective problem that have a same optimal objective
value, the value of the objective function in a multiobjective problem will differ at the different
optimal solutions. This is because when there are different conflicting objectives, it is
impossible to optimize all the objectives at the same time to their single objective optimization
levels. Hence, decision makers need to trade-off between optimal values of the different
objectives. Different trade-offs represent different optimal solutions.
The key idea behind multiobjective optimization is to find a set of optimal solutions that
represent the best trade-offs among the conflicting objectives. The multiple optimal objective
values of a multiobjective problem are equally good, each offering different compromises
between the objectives. These equally good optimal solutions are called Pareto optimal
solutions. The concept of Pareto optimality is central to multiobjective optimization. A
solution is considered Pareto optimal if there is no other solution that improves on at least
one objective without worsening another. The set of all Pareto optimal solutions forms the
2
Contact for any query:
, Pareto front or Pareto set, which represents the best possible trade-offs between the
objectives.
There are various techniques for solving multiobjective optimization problems, including
evolutionary algorithms (such as genetic algorithms and particle swarm optimization),
mathematical programming methods (such as linear programming and nonlinear
programming), and heuristic approaches (such as simulated annealing and tabu search). Four
mathematical programming methods are discussed here using a simple two variable, two
objective linear programming model. Graphical representations of the same are presented for
the ease of understanding of the concepts.
The Example Problem:
A multiobjective linear programming problem with two decision variables and two objective
functions are shown below for the purpose of demonstration of the methods:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑓1 = 2𝑥1 + 𝑥2
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓2 = 3𝑥1 + 𝑥2
Subject to:
6𝑥1 + 8𝑥2 ≥ 12
5𝑥1 + 3𝑥2 ≤ 10
𝑥1 ≥ 0
𝑥2 ≥ 0
In this model, 𝑥1 and 𝑥2 are the decision variables. The values of these variables need to be
found out after solving the problem. All the numerical values in the objective functions as well
as in the constraints are parameters. The values of parameters are already known before
solving the problem. The maximization or minimization functions are the objective functions
3
Contact for any query:
Lexicographic, Ꜫ-constrained, Weighted
Sum, and Minimax Methods with
Graphical Representation.
Prepared by Krishnendranath Mitra.
Linear programming is a mathematical programming technique used to find the maximum or
minimum value of a linear objective function while satisfying all the linear constraints.
Multiobjective linear programming provides optimal solutions where some trade-offs are
made for the individual objectives of its multiple conflicting objectives. This document
demonstrates four mathematical modelling approaches for multiobjective optimization,
namely lexicographic method, Ꜫ-constrained method, weighted sum method, and modified
weighted sum method with minimax objective. It uses a simple example to explain the
concepts and the graphical representations for these methods are intended to enhance the
ease of understanding the concepts.
Multiobjective Optimization:
Multiobjective optimization, also known as multicriteria optimization or Pareto optimization,
is a mathematical approach used to solve problems involving multiple conflicting objectives.
In real-world scenarios, decision makers often need to consider multiple, often conflicting,
criteria simultaneously. For example, in engineering design, one might aim to minimize cost
while maximizing performance and minimizing environmental impact.
Single objective optimization focuses on optimizing a single criterion or objective function,
aiming to find the best solution. A solution of an optimization problem is the set of values of
all decision variables at a given condition. Decision variables are those entities whose optimal
values represent the best decisions and are the outcomes of the optimization process.
1
Contact for any query:
,Optimization means maximizing or minimizing the value of an objective function, by changing
the values of the decision variables, such that all the constraints are satisfied. If even one of
the constraints is violated, the solution is infeasible. Solutions that satisfy all constraints are
called feasible solutions and all feasible solutions together constitute the feasible region.
Solutions that lie outside the feasible region are infeasible and need to be rejected straight
away from the optimization process.
Among the feasible solutions of a linear programming problem, those lying at corners of the
feasible region are called corner-point feasible solutions. These corners of the feasible region
are formed by the intersection of two or more constraint functions. In single objective linear
programming problems, the optimal solution is always a corner-point feasible solution. If the
objective line is parallel to a constraint line, the optimality may be obtained along the length
of that constraint function at the feasible region boundary. In such a case, there can be
multiple optimal solutions for the single objective between two adjacent corner-points. The
optimal values of the decision variables differ in these multiple solutions but the optimal
objective function value remains the same.
In case of multiobjective functions, there will be multiple optimal solutions, meaning that the
values of the set of all decision variables at each optimal solution will differ. However, unlike
multiple optimal solutions in a single objective problem that have a same optimal objective
value, the value of the objective function in a multiobjective problem will differ at the different
optimal solutions. This is because when there are different conflicting objectives, it is
impossible to optimize all the objectives at the same time to their single objective optimization
levels. Hence, decision makers need to trade-off between optimal values of the different
objectives. Different trade-offs represent different optimal solutions.
The key idea behind multiobjective optimization is to find a set of optimal solutions that
represent the best trade-offs among the conflicting objectives. The multiple optimal objective
values of a multiobjective problem are equally good, each offering different compromises
between the objectives. These equally good optimal solutions are called Pareto optimal
solutions. The concept of Pareto optimality is central to multiobjective optimization. A
solution is considered Pareto optimal if there is no other solution that improves on at least
one objective without worsening another. The set of all Pareto optimal solutions forms the
2
Contact for any query:
, Pareto front or Pareto set, which represents the best possible trade-offs between the
objectives.
There are various techniques for solving multiobjective optimization problems, including
evolutionary algorithms (such as genetic algorithms and particle swarm optimization),
mathematical programming methods (such as linear programming and nonlinear
programming), and heuristic approaches (such as simulated annealing and tabu search). Four
mathematical programming methods are discussed here using a simple two variable, two
objective linear programming model. Graphical representations of the same are presented for
the ease of understanding of the concepts.
The Example Problem:
A multiobjective linear programming problem with two decision variables and two objective
functions are shown below for the purpose of demonstration of the methods:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑓1 = 2𝑥1 + 𝑥2
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓2 = 3𝑥1 + 𝑥2
Subject to:
6𝑥1 + 8𝑥2 ≥ 12
5𝑥1 + 3𝑥2 ≤ 10
𝑥1 ≥ 0
𝑥2 ≥ 0
In this model, 𝑥1 and 𝑥2 are the decision variables. The values of these variables need to be
found out after solving the problem. All the numerical values in the objective functions as well
as in the constraints are parameters. The values of parameters are already known before
solving the problem. The maximization or minimization functions are the objective functions
3
Contact for any query:
