Linear Programming

Samia Kerdjoudj
kerdjoudj_samia@[Link]

University of Blida 1.

12 octobre 2025
 Chapter 2
Geometric interpretation of linear programming

S. Kerdjoudj Linear programming 1/33

 Mathematical Program

Mathematical Program
Given a domain D ⊂ Rn and a function f : D → R.
A Mathematical Program (MP) is a problem that consists in finding an
element x∗ ∈ D (if such an element exists) that maximizes or minimizes
the function f . In other words :
1 ∀x ∈ D, f (x) ≥ f (x∗ ) (minimization problem : min f (x)),
x∈D
or
2 ∀x ∈ D, f (x) ≤ f (x∗ ) (maximization problem : max f (x)).
x∈D

S. Kerdjoudj Linear programming 2/33

 Mathematical Program Terminology

Vocabulary
Let (P ) : max f (x) be a mathematical program. Then :
x∈D
A point x is called a solution of (P ).
The set D is called the feasible region of (P ).
A point x ∈ D is called a feasible solution of (P ).
The function f is called the objective function of (P ).
A point x∗ ∈ D is called an optimal solution of (P ), i.e., a feasible
solution whose value is the greatest possible for (P ).

S. Kerdjoudj Linear programming 3/33

 Mathematical Program Possible Cases in Solving a Mathematical Program

For any mathematical program (P ) : max f (x), only one of the

x∈D
following three situations can occur :
1 If D = ∅, then (P ) has no feasible solution.
Example : max (x)
{x≥0 and x≤−1}

S. Kerdjoudj Linear programming 4/33

 Mathematical Program Possible Cases in Solving a Mathematical Program

For any mathematical program (P ) : max f (x), only one of the

x∈D
following three situations can occur :
1 If D = ∅, then (P ) has no feasible solution.
Example : max (x)
{x≥0 and x≤−1}
2 If D =
6 ∅ and f is unbounded over D, then (P ) has no optimal
solution.
Example : max (x)
{x≥0}

S. Kerdjoudj Linear programming 4/33

 Mathematical Program Possible Cases in Solving a Mathematical Program

For any mathematical program (P ) : max f (x), only one of the

x∈D
following three situations can occur :
1 If D = ∅, then (P ) has no feasible solution.
Example : max (x)
{x≥0 and x≤−1}
2 If D =
6 ∅ and f is unbounded over D, then (P ) has no optimal
solution.
Example : max (x)
{x≥0}
3 If D =
6 ∅ and f is bounded over D, then (P ) :

S. Kerdjoudj Linear programming 4/33

 Mathematical Program Possible Cases in Solving a Mathematical Program

For any mathematical program (P ) : max f (x), only one of the

x∈D
following three situations can occur :
1 If D = ∅, then (P ) has no feasible solution.
Example : max (x)
{x≥0 and x≤−1}
2 If D =
6 ∅ and f is unbounded over D, then (P ) has no optimal
solution.
Example : max (x)
{x≥0}
3 If D =
6 ∅ and f is bounded over D, then (P ) :
admits at least one optimal solution.
Example : max (x2 )
{−2≤x≤2}

S. Kerdjoudj Linear programming 4/33

 Mathematical Program Possible Cases in Solving a Mathematical Program

For any mathematical program (P ) : max f (x), only one of the

x∈D
following three situations can occur :
1 If D = ∅, then (P ) has no feasible solution.
Example : max (x)
{x≥0 and x≤−1}
2 If D =
6 ∅ and f is unbounded over D, then (P ) has no optimal
solution.
Example : max (x)
{x≥0}
3 If D =
6 ∅ and f is bounded over D, then (P ) :
admits at least one optimal solution.
Example : max (x2 )
{−2≤x≤2}
may not admit an optimal solution : the function is bounded but
does not attain a maximum.
Example : max (x)
{x<0}

S. Kerdjoudj Linear programming 4/33

 Mathematical Program General Form of a Linear Program

General Form of a Linear Program


X n
min or max(Z) = cj xj






 j=1
n



 X



 s.t. aij xj ≤ bi , ∀i ∈ I1
j=1



 n

 X
aij xj = bi , ∀i ∈ I2


(P ) j=1


 Xn
aij xj ≥ bi , ∀i ∈ I3







 j=1

 xj ≥ 0, ∀j ∈ J1




xj ≤ 0, ∀j ∈ J2





xj ∈ R, ∀j ∈ J3


I = I1 ∪ I2 ∪ I3 with |I| = m : number of constraints.

J = J1 ∪ J2 ∪ J3 with |J| = n : number of variables.
S. Kerdjoudj Linear programming 5/33
 Mathematical Program Matrix Representation of a Linear Program

A linear program (LP) can be represented in matrix form as follows :


 max(Z) = CX

(P ) s.t. AX ≤ b

X ≥0


where :
   
x1 a11 a12 ··· a1n
 x2   a21 a22 ··· a2n 
   
X =
 .. 
 A=
 .. .. .. .. 
 .   . . . . 


xn am1 am2 · · · amn

Vector of variables (n × 1) Constraint matrix (m × n)
 
b1
 b2 
 
 
C = c1 c2 · · · cn b= .. 

 . 
Cost vector (1 × n)
bm
Right-hand side vector (m × 1)
S. Kerdjoudj Linear programming 6/33
 Mathematical Program Matrix Representation of a Linear Program

Once the linear program is formulated, the next step is to solve the
model.

S. Kerdjoudj Linear programming 7/33

 Mathematical Program Matrix Representation of a Linear Program

Once the linear program is formulated, the next step is to solve the
model.

Mathematical Techniques for Solving a Linear Program

Graphical method (n = 2 or n = 3).
Simplex method (n ≥ 2).

S. Kerdjoudj Linear programming 7/33

 Geometry of Linear Programming Definition of a Convex Set

Convex Set
A set C ⊂ Rn is said to be convex if

∀x, y ∈ C, ∀λ ∈ [0, 1], λx + (1 − λ)y ∈ C.

In other words, a set C is convex if the line segment joining any two of
its points lies entirely within the set C.

S. Kerdjoudj Linear programming 8/33

 Geometry of Linear Programming Definition of a Convex Set

Convex Set
A set C ⊂ Rn is said to be convex if

∀x, y ∈ C, ∀λ ∈ [0, 1], λx + (1 − λ)y ∈ C.

In other words, a set C is convex if the line segment joining any two of
its points lies entirely within the set C.

Illustration
b

b b

Figure – Convex set – Non-convex set

S. Kerdjoudj Linear programming 8/33

 Geometry of Linear Programming Definition of a Convex Set

Convex Combination
Let x1 , . . . , xk ∈ Rn . A convex combination of x1 , . . . , xk is a vector x
such that :
k
X k
X
x= λi xi , λi ≥ 0, λi = 1
i=1 i=1

S. Kerdjoudj Linear programming 9/33

 Geometry of Linear Programming Definition of a Convex Set

Convex Combination
Let x1 , . . . , xk ∈ Rn . A convex combination of x1 , . . . , xk is a vector x
such that :
k
X k
X
x= λi xi , λi ≥ 0, λi = 1
i=1 i=1

Example of a Convex Combination

! !
1 3
Let x1 = , and x2 = be two points in R2 :
2 4
X2
Assume : λ1 = 0.4, λ2 = 0.6. with λi = 0.4 + 0.6 = 1.
i=1
then : ! ! !
1 3 2.2
x = 0.4x1 + 0.6x2 = 0.4 + 0.6 = is a convex
2 4 3.2
combination of the points x1 and x2 .
S. Kerdjoudj Linear programming 9/33
 Geometry of Linear Programming Hyperplane in Rn

Hyperplane
Let a be a nonzero vector in Rn and let b be a scalar.
A hyperplane H is the set of all points x ∈ Rn that satisfy aT x = b.

H = {x ∈ Rn | aT x = b}

This hyperplane partitions the space Rn into two half-spaces :

Half-Spaces of the Hyperplane
1 Positive closed half-space H+ :
H+ = {x ∈ Rn | aT x ≥ b}
2 Negative closed half-space H− :
H− = {x ∈ Rn | aT x ≤ b}

S. Kerdjoudj Linear programming 10/33

 Geometry of Linear Programming Polyedron

Polyhedron
A Polyhedron P in Rn is the intersection of finitely many halfspaces. It
can be equivalently defined to be the set

P = {x ∈ Rn | Ax ≤ b}

where A ∈ Rm×n is a real matrix, and b ∈ Rm is a real vector.

Fact
The feasible region of any linear program can be described as a
polyhedron.

S. Kerdjoudj Linear programming 11/33

 Geometry of Linear Programming Polyedron

Bounded Set
A set S ⊆ Rn is said to be bounded if there exists a constant k > 0 such
that the absolute value of every component of every element of S is at
most k. In other words, ∃k ∈ R+ , kxk ≤ k, ∀x ∈ S

Polytope
A nonempty bounded polyhedron is called a polytope.

S. Kerdjoudj Linear programming 12/33

 Geometry of Linear Programming Theorems

Theorems
1 A hyperplane is convex.

2 The closed half-spaces H+ and H− are convex.

3 Any intersection of convex sets is still convex.
4 Every polyhedron is an intersection of halfspaces, and convex.

S. Kerdjoudj Linear programming 13/33

 Geometry of Linear Programming Theorems

Proof of Theorem 1 : A hyperplane is convex.

Let H = {x ∈ Rn | aT x = b} be a hyperplane.
Suppose u, v ∈ H, then

aT u = b and aT v = b.

Let λ ∈ [0, 1] and define w = λu + (1 − λ)v.

Then,

aT w = aT (λu + (1 − λ)v) = λaT u + (1 − λ)aT v = λb + (1 − λ)b = b.

Hence, w ∈ H, so H is convex.


S. Kerdjoudj Linear programming 14/33

 Geometry of Linear Programming Extreme Points

Extreme Point
Let P ⊂ Rn be a polyhedron. A point x ∈ P is called an extreme point
of P if there do not exist two distinct points y, z ∈ P such that x is a
convex combination of them :

∄ y, z ∈ C, λ ∈ ]0, 1[ such that x = λy + (1 − λ)z.

Example
w is not an extreme point because ∃u, v ∈ P such that w ∈ [uv].
x is an extreme point because if x = λy + (1 − λ)z, with λ ∈]0, 1[
and y, z 6= x, then either y ∈
/ P or z ∈
/ P.

b
y P
b
x b
b
b v
b
z w
u
S. Kerdjoudj Linear programming 15/33
 Geometry of Linear Programming Existence of Extreme Points

Definition
A polyhedron P ⊆ Rn is said to contain a line if there exist a point
x ∈ Rn and a nonzero vector d ∈ P such that :

x + λd ∈ P for all λ ∈ R.

Example

P Q

P contain a line Q does not contain a line

S. Kerdjoudj Linear programming 16/33

 Geometry of Linear Programming Existence of Extreme Points

Theorem 2 : Existence of Extreme Points

Let P ⊆ Rn be a nonempty polyhedron. The following are equivalent :
1 P does not contain a line.
2 P has at least one extreme point.

Corollary
Every bounded polyhedron (i.e., every polytope) has at least one
extreme point.

S. Kerdjoudj Linear programming 17/33

 Geometry of Linear Programming Optimality of extreme point

Theorem 3 : Optimality of Extreme Point

If a feasible region D of a linear program (P ) has at least one extreme
point, and the LP (P ) has an optimal solution, then at least one
optimal solution is an extreme point of D.

S. Kerdjoudj Linear programming 18/33

 Geometry of Linear Programming Optimality of extreme point

Proof of Theorem 3
Let D = {x ∈ Rn | Ax ≤ b} be a feasible region, and let x∗ be an
optimal solution to the LP with optimal value v = cT x∗


S. Kerdjoudj Linear programming 19/33
 Geometry of Linear Programming Optimality of extreme point

Proof of Theorem 3
Let D = {x ∈ Rn | Ax ≤ b} be a feasible region, and let x∗ be an
optimal solution to the LP with optimal value v = cT x∗
Let Q = {x ∈ Rn | Ax ≤ b, cT x = v} ⊆ D be the set of all opt. sol.


S. Kerdjoudj Linear programming 19/33
 Geometry of Linear Programming Optimality of extreme point

Proof of Theorem 3
Let D = {x ∈ Rn | Ax ≤ b} be a feasible region, and let x∗ be an
optimal solution to the LP with optimal value v = cT x∗
Let Q = {x ∈ Rn | Ax ≤ b, cT x = v} ⊆ D be the set of all opt. sol.
D has an extreme point ====⇒ D has no lines ===⇒ Q has no lines
thm. 2 Q⊆D
====⇒ Q has an extreme point.
Thm. 2


S. Kerdjoudj Linear programming 19/33
 Geometry of Linear Programming Optimality of extreme point

Proof of Theorem 3
Let D = {x ∈ Rn | Ax ≤ b} be a feasible region, and let x∗ be an
optimal solution to the LP with optimal value v = cT x∗
Let Q = {x ∈ Rn | Ax ≤ b, cT x = v} ⊆ D be the set of all opt. sol.
D has an extreme point ====⇒ D has no lines ===⇒ Q has no lines
thm. 2 Q⊆D
====⇒ Q has an extreme point.
Thm. 2
Let x′ be an extreme point of Q. Suppose that x′ is not an extreme
point of D. Then ∃y 6= x′ , z 6= x′ , λ ∈]0, 1[ s.t x′ = λy + (1 − λ)z


S. Kerdjoudj Linear programming 19/33
 Geometry of Linear Programming Optimality of extreme point

Proof of Theorem 3
Let D = {x ∈ Rn | Ax ≤ b} be a feasible region, and let x∗ be an
optimal solution to the LP with optimal value v = cT x∗
Let Q = {x ∈ Rn | Ax ≤ b, cT x = v} ⊆ D be the set of all opt. sol.
D has an extreme point ====⇒ D has no lines ===⇒ Q has no lines
thm. 2 Q⊆D
====⇒ Q has an extreme point.
Thm. 2
Let x′ be an extreme point of Q. Suppose that x′ is not an extreme
point of D. Then ∃y 6= x′ , z 6= x′ , λ ∈]0, 1[ s.t x′ = λy + (1 − λ)z
cT x′ = λcT y + (1 − λ)cT z = v. Since v is the optimal value, and
y, z ∈ D, we have : cT y ≤ v and cT z ≤ v


S. Kerdjoudj Linear programming 19/33
 Geometry of Linear Programming Optimality of extreme point

Proof of Theorem 3
Let D = {x ∈ Rn | Ax ≤ b} be a feasible region, and let x∗ be an
optimal solution to the LP with optimal value v = cT x∗
Let Q = {x ∈ Rn | Ax ≤ b, cT x = v} ⊆ D be the set of all opt. sol.
D has an extreme point ====⇒ D has no lines ===⇒ Q has no lines
thm. 2 Q⊆D
====⇒ Q has an extreme point.
Thm. 2
Let x′ be an extreme point of Q. Suppose that x′ is not an extreme
point of D. Then ∃y 6= x′ , z 6= x′ , λ ∈]0, 1[ s.t x′ = λy + (1 − λ)z
cT x′ = λcT y + (1 − λ)cT z = v. Since v is the optimal value, and
y, z ∈ D, we have : cT y ≤ v and cT z ≤ v
But the equality above implies : cT y = cT z = v ⇒ y, z ∈ Q
Hence, x′ is not an extreme point of Q. Contradiction.

S. Kerdjoudj Linear programming 19/33
 Geometry of Linear Programming Optimality of extreme point

Properties
Let (P ) be a linear program (LP) and let D be its feasible region.
Then :
1 If D is a non-empty bounded polyhedron, then :
1 (P ) admits a unique optimal solution, and this solution is an
extreme point ; or
2 (P ) admits an infinite number of optimal solutions, which are
convex combinations of a finite number of extreme points of D.
2 If D is a non-empty unbounded polyhedron, then :
1 Cases (1) and (2) may still occur ;
2 (P ) may not have a finite optimal solution, i.e., max(Z) → +∞ or
min(Z) → −∞.
3 If D = ∅, then (P ) has no feasible solution. As a consequence, (P )
has no optimal solution.
S. Kerdjoudj Linear programming 20/33
 Graphical Solution of an LP

Algorithm 1: Graphical Method Algorithm

(1) Draw an orthonormal coordinate system (O, x~1 , x~2 ) ;
(2) Plot the constraints (both functional and non-negativity) ;
(3) Determine the closed half-plane that satisfies each constraint ;
(4) Draw the set of feasible solutions (D) ;
(5) if (D) is bounded then An optimal solution exists, go to (7) ;
(6) else if (D) is unbounded then
if the problem is a maximization then No optimal solution ;
else if the problem is a minimization then An optimal solution
exists, go to (7) ;
(7) Find all the extreme points of (D) and select the optimal point using
one of the two methods :
Extreme point enumeration approach ;

Gradient method

S. Kerdjoudj Linear programming 21/33

 Graphical Solution of an LP Application Example 1

Production Problem
A manufacturer produces two types of strawberry yogurt, labeled A
and B, using strawberries, milk, and sugar. Producing one pot of
yogurt A requires 1 kg of strawberries, 2 kg of milk, and 1 kg of sugar.
For one pot of yogurt B, the recipe requires 2 kg of strawberries, and 1
kg of milk.
The total available quantities of ingredients in stock are 800 kg of
strawberries, 700 kg of milk, and 300 kg of sugar. Yogurt A is sold at 4
DA per pot, and yogurt B at 5 DA per pot.

The manufacturer aims to maximize profit.

S. Kerdjoudj Linear programming 22/33

 Graphical Solution of an LP Application Example 1




 max(Z) = 4x1 + 5x2

 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0



S. Kerdjoudj Linear programming 23/33

Graphical Solution of an LP Graphical Representation of the Production Problem


 max(Z) = 4x1 + 5x2

 s.t

 x1 + 2x2 ≤ 800


 2x1 + x2 ≤ 700
(P )


 x1 ≤ 300
x1 ≥ 0, x2 ≥ 0







x2

x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2

x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2

x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2

x1 + 2x2 = 800
x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2

x1 + 2x2 = 800
x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2

2x1 + x2 = 700

x1 + 2x2 = 800
x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2

2x1 + x2 = 700

x1 + 2x2 = 800
x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2
x1 = 300

2x1 + x2 = 700

x1 + 2x2 = 800
x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2
x1 = 300

2x1 + x2 = 700

x1 + 2x2 = 800
x1

S. Kerdjoudj Linear programming 24/33

Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2
x1 = 300

2x1 + x2 = 700

x1 + 2x2 = 800
x1

S. Kerdjoudj Linear programming 24/33

 Graphical Solution of an LP Graphical Representation of the Production Problem
max(Z) = 4x1 + 5x2



 s.t x1 + 2x2 ≤ 800



(P ) 2x1 + x2 ≤ 700

x1 ≤ 300





x1 ≥ 0, x2 ≥ 0

x2
x1 = 300

2x1 + x2 = 700

A = (0, 400)

B = (200, 300)

D C = (300, 100)
O = (0, 0) x1 + 2x2 = 800
x1
D = (300, 0)

Figure – Feasible Region of the Production Problem

S. Kerdjoudj Linear programming 24/33
 Graphical Solution of an LP Finding the Optimum of the Production Problem

1st Method : Extreme point enumeration approach

The feasible region D of (P ) is a convex polytope and the optimal

solution occurs at one of the extreme points of this polytope.
Method Description
Enumerate all extreme points of the feasible region.
Evaluate the objective function at each extreme point.
Select the extreme point with the best (maximum or minimum)
objective value.

S. Kerdjoudj Linear programming 25/33

 Graphical Solution of an LP Finding the Optimum of the Production Problem

1st Method : Extreme point enumeration approach

Vertex Coordinates Value of max(Z) = 4x1 + 5x2

O (0, 0) 0
A (0, 400) 2000
B (200, 300) 2300
C (300, 100) 1700
D (300, 0) 1200
!
200
Conclusion : The optimal solution is X ∗ = , where Z ∗ = 2300.
300

Note
This approach is effective for small problems but becomes
computationally expensive in higher dimensions.
S. Kerdjoudj Linear programming 26/33
 Graphical Solution of an LP Finding the Optimum of the Production Problem

2nd Method : Gradient-Based Geometric Approach

The vector (c1 , c2 ) is the gradient of the linear objective function :
f (x1 , x2 ) = c1 x1 + c2 x2 , with c1 , c2 ∈ R.
Method Description
The gradient vector (c1 , c2 ) is perpendicular to the level lines
defined by : c1 x1 + c2 x2 = Z, for all Z ∈ R.
Increasing Z corresponds to shifting these lines in the direction of
the gradient (c1 , c2 ), without changing their orientation.
Geometrically, this means "sliding" the line outward, parallel to
itself, until it last touches the feasible region.
This point of contact represents the optimal solution, where the
objective function reaches its maximum (or minimum) over the
feasible region.
S. Kerdjoudj Linear programming 27/33
 Graphical Solution of an LP Finding the Optimum of the Production Problem

x2

x1 = 300

2x1 + x2 = 700

!
4
▽Z =
5

A = (0, 400)

B = (200, 300)

D C = (300, 100)
O = (0, 0) x1 + 2x2 = 800
x1
D = (300, 0)

4x1 + 5x2 = 625 4x1 + 5x2 = 2300 = max(Z)

4x1 + 5x2 = 0
4x1 + 5x2 = 1500

S. Kerdjoudj Linear programming 28/33

 Graphical Solution of an LP Finding the Optimum of the Production Problem

x2

x1 = 300

2x1 + x2 = 700

!
4
▽Z =
5

A = (0, 400)
B = (200, 300) Optimal Solution

D C = (300, 100)
O = (0, 0) x1 + 2x2 = 800
x1
D = (300, 0)

4x1 + 5x2 = 625 4x1 + 5x2 = 2300 = max(Z)

4x1 + 5x2 = 0
4x1 + 5x2 = 1500

S. Kerdjoudj Linear programming 28/33

 Graphical Solution of an LP Finding the Optimum of the Production Problem

Some examples are given of how to graphically solve linear problems in

various possible scenarios.

S. Kerdjoudj Linear programming 29/33

Graphical Solution of an LP Problem with Unbounded Solution


 max(Z) = −2x1 + 3x2

 s.t x1 ≤ 5
(P )


 2x1 − 3x2 ≤ 6
x1 ≥ 0, x2 ≥ 0


S. Kerdjoudj Linear programming 30/33

 Graphical Solution of an LP Problem with Unbounded Solution


 max(Z) = −2x1 + 3x2

 s.t x1 ≤ 5
(P )


 2x1 − 3x2 ≤ 6
x1 ≥ 0, x2 ≥ 0


x2
x1 = 5

−2x1 + 3x2 = 0

D 2x1 − 3x2 = 6
!
−2
▽Z =
3
B = (5, 4/3)

O = (0, 0)
x1
A = (3, 0)

S. Kerdjoudj Linear programming 30/33

 Graphical Solution of an LP Problem with Unbounded Solution


 max(Z) = −2x1 + 3x2

 s.t x1 ≤ 5
(P )


 2x1 − 3x2 ≤ 6
x1 ≥ 0, x2 ≥ 0


x2
x1 = 5

−2x1 + 3x2 = 0

D 2x1 − 3x2 = 6
!
−2
▽Z =
3
B = (5, 4/3)

O = (0, 0)
x1
A = (3, 0)

It is clear that the value of Z can be increased in the direction of the gradient
vector of the objective function, indicating that the solution is unbounded
(i.e., it tends to infinity).
S. Kerdjoudj Linear programming 30/33
Graphical Solution of an LP Infeasible Problem (No Solution Exists)


 max(Z) = 3x1 + 3x2

 s.t x1 + 2x2 ≤ 2
(P )


 2x1 + 4x2 ≥ 8
x1 ≥ 0, x2 ≥ 0


S. Kerdjoudj Linear programming 31/33

Graphical Solution of an LP Infeasible Problem (No Solution Exists)


 max(Z) = 3x1 + 3x2

 s.t x1 + 2x2 ≤ 2
(P )


 2x1 + 4x2 ≥ 8
x1 ≥ 0, x2 ≥ 0


x2

x1
2x1 + 4x2 = 8
x1 + 2x2 = 2

S. Kerdjoudj Linear programming 31/33

 Graphical Solution of an LP Infeasible Problem (No Solution Exists)


 max(Z) = 3x1 + 3x2

 s.t x1 + 2x2 ≤ 2
(P )


 2x1 + 4x2 ≥ 8
x1 ≥ 0, x2 ≥ 0


x2

x1
2x1 + 4x2 = 8
x1 + 2x2 = 2

Since the feasible region is empty (D = ∅), the problem (P ) admits no

solution.
S. Kerdjoudj Linear programming 31/33
Graphical Solution of an LP Problem Admitting Infinitely Many Solutions
min(Z) = 2x1 + 2x2



 s.t x1 + x2 ≥ 2



(P ) x1 ≤ 3

x2 ≤ 3





x1 ≥ 0, x2 ≥ 0

S. Kerdjoudj Linear programming 32/33

Graphical Solution of an LP Problem Admitting Infinitely Many Solutions
min(Z) = 2x1 + 2x2



 s.t x1 + x2 ≥ 2



(P ) x1 ≤ 3

x2 ≤ 3





x1 ≥ 0, x2 ≥ 0

x2
x1 = 3

C D
x2 = 3
D
B
▽Z

x1
A E
x1 + x2 = 2

S. Kerdjoudj Linear programming 32/33

 Graphical Solution of an LP Problem Admitting Infinitely Many Solutions
min(Z) = 2x1 + 2x2



 s.t x1 + x2 ≥ 2



(P ) x1 ≤ 3

x2 ≤ 3





x1 ≥ 0, x2 ≥ 0

x2
x1 = 3

C D
x2 = 3
D
B
▽Z

x1
A E
x1 + x2 = 2

The points
!
on the
!
segment [AB] represent the optimal solutions of (P ).
2 0
X∗ = , X ∗∗ = , Z ∗ = 4.
0 2

S. Kerdjoudj Linear programming 32/33

Graphical Solution of an LP Degenerate Problem

max(Z) = x1 + x2



 s.t 3x1 + 2x2 ≤ 40



(P ) x1 ≤ 10

x2 ≤ 5





x1 ≥ 0, x2 ≥ 0

S. Kerdjoudj Linear programming 33/33

Graphical Solution of an LP Degenerate Problem

max(Z) = x1 + x2



 s.t 3x1 + 2x2 ≤ 40



(P ) x1 ≤ 10

x2 ≤ 5





x1 ≥ 0, x2 ≥ 0

x2
x1 = 10

▽Z
C Sol. Opt
x2 = 5
B
D
x1
A D
3x1 + 2x2 = 40

S. Kerdjoudj Linear programming 33/33

 Graphical Solution of an LP Degenerate Problem

max(Z) = x1 + x2



 s.t 3x1 + 2x2 ≤ 40



(P ) x1 ≤ 10

x2 ≤ 5





x1 ≥ 0, x2 ≥ 0

x2
x1 = 10

▽Z
C Sol. Opt
x2 = 5
B
D
x1
A D
3x1 + 2x2 = 40

!
10
The optimal solution is X ∗ = , with Z ∗ = 15. A solution X ∗ is called
5
degenerate if at least three constraints are active (i.e., intersect) at that point.

S. Kerdjoudj Linear programming 33/33