Part 2: Methods
Graphical solution of LP problems with two variables
General form
Max cx
s.t. Ax ≤ b
x≥0
To graphically determine the
solution of an LP problem we will
represent the information we have
in a graph by drawing the lines of
all the constraints and determine
on basis if that the feasible region.
In order to find the optimal
solution of the feasible set we will
draw the objective function and
make it move in the direction c.
C is the improving direction and is the vector made with the coefficients of the objective
function.
Isoprofit line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥?) for
maximization problems
Isocost line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥? ) for minimization
problems
As we move the isoprofit lines in the direction of c, the total profit will increase. To solve an
LP problem in 2 variables, we should try tp push isoprofit (or isocost) lines in the improving
direction as much as possible while still staying in the feasible region.
!! for a maximization problem we use c as improving direction. For minimization problems
we will have to use ( -c) because otherwise we are improving.
The feasible region is defined by the constraints so if we modify the objective function while
keeping the constraints the same, this one won’t change.
What will change in this case is the improving direction => is defined by the objective
function.
Convex set
Set S is convex if the line joining any pair of points in S is completely contained in S.
, Convex if for two points 𝑥 ∈ 𝑆 and 𝑦 ∈ 𝑆, their convex combination 𝜆𝑥 + (1 − 𝜆)𝑦 ∈ 𝑆 for
all 𝜆 ∈ [0,1].
ð Feasible set of an LP must be a convex set
Strict convex combination
X is a strict convex combination of 𝑥$ and 𝑥? if 𝑥 = 𝜆𝑥$ + (1 − 𝜆)𝑥? for some 𝜆 ∈ ]0,1[.
Extreme point (corner point)
P is an extreme point of it cannot be represented as a strict convex combination of distinct
points of S. If to represent the point as a convex combination of 2 other points then if one
point is in the set then the other one will necessarily have to be outside of the set S.
In the case that the isoprofit or isocost line on a constraint line arrives when optimization its
direction, we will have as optimal solution every feasible solution on the segment of the
constraint line that belongs to the feasible region.
ð LP has multiple or alternate optimal solutions
Unbounded LP Problems:
Arises when we the objective function can be moved infinitely while keeping optimizing the
problem and staying in the feasible region.
For such a LP problem there is no optimal solution because we can always find beter and
the optimal value is defined to be +∞ (−∞)
Infeasible LP Problems:
Happens when we can’t find a feasible solution.
Fundamental Theorem of Linear Programming
“If the feasible set is not empty, if there is a feasible solution, then there is at least an
extreme point.”
“If an LP with feasible set has an optimal solution, then there is an extreme point of the
feasible region that is an optimal solution to the LP.”
ð ! not every optimal solution needs to be an extreme point!
Graphical solution of LP problems with two variables
General form
Max cx
s.t. Ax ≤ b
x≥0
To graphically determine the
solution of an LP problem we will
represent the information we have
in a graph by drawing the lines of
all the constraints and determine
on basis if that the feasible region.
In order to find the optimal
solution of the feasible set we will
draw the objective function and
make it move in the direction c.
C is the improving direction and is the vector made with the coefficients of the objective
function.
Isoprofit line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥?) for
maximization problems
Isocost line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥? ) for minimization
problems
As we move the isoprofit lines in the direction of c, the total profit will increase. To solve an
LP problem in 2 variables, we should try tp push isoprofit (or isocost) lines in the improving
direction as much as possible while still staying in the feasible region.
!! for a maximization problem we use c as improving direction. For minimization problems
we will have to use ( -c) because otherwise we are improving.
The feasible region is defined by the constraints so if we modify the objective function while
keeping the constraints the same, this one won’t change.
What will change in this case is the improving direction => is defined by the objective
function.
Convex set
Set S is convex if the line joining any pair of points in S is completely contained in S.
, Convex if for two points 𝑥 ∈ 𝑆 and 𝑦 ∈ 𝑆, their convex combination 𝜆𝑥 + (1 − 𝜆)𝑦 ∈ 𝑆 for
all 𝜆 ∈ [0,1].
ð Feasible set of an LP must be a convex set
Strict convex combination
X is a strict convex combination of 𝑥$ and 𝑥? if 𝑥 = 𝜆𝑥$ + (1 − 𝜆)𝑥? for some 𝜆 ∈ ]0,1[.
Extreme point (corner point)
P is an extreme point of it cannot be represented as a strict convex combination of distinct
points of S. If to represent the point as a convex combination of 2 other points then if one
point is in the set then the other one will necessarily have to be outside of the set S.
In the case that the isoprofit or isocost line on a constraint line arrives when optimization its
direction, we will have as optimal solution every feasible solution on the segment of the
constraint line that belongs to the feasible region.
ð LP has multiple or alternate optimal solutions
Unbounded LP Problems:
Arises when we the objective function can be moved infinitely while keeping optimizing the
problem and staying in the feasible region.
For such a LP problem there is no optimal solution because we can always find beter and
the optimal value is defined to be +∞ (−∞)
Infeasible LP Problems:
Happens when we can’t find a feasible solution.
Fundamental Theorem of Linear Programming
“If the feasible set is not empty, if there is a feasible solution, then there is at least an
extreme point.”
“If an LP with feasible set has an optimal solution, then there is an extreme point of the
feasible region that is an optimal solution to the LP.”
ð ! not every optimal solution needs to be an extreme point!
