UE24MA244A – MATHEMATICS FOR

ELECTRONICS ENGINEERS
Unit 4: Engineering Optimization
Constrained Optimization : Linear Programming

Department of Electronics & Communication Engineering

Slide Ack: Dept. of Computer Science & Engineering

Mathematics for Electronics Engineers
Simplex Method
• The graphical approach can be used for two-variable LP problems
• Unfortunately, most real-life LPs problems require a method to find
optimal solutions capable of dealing with several variables: the
simplex algorithm
Mathematics for Electronics Engineers
Simplex Method - Formulation

In LP problem, the decision

maker usually wants to: Poets’ Problem
maximize (usually revenue or profit)
mminimize (usually costs)
(€/yr)
Max: Z = 90 x1 + 120 x2
the objective function (Z) is
expressed by a set of decision Subject to:
variables
x1 ≤ 40(ha of pine)
Certain limitations are often x2 ≤ 50(ha of eucalypt)
imposed to these decision
variables (expressed in the form 2x1 + 3x2 ≤ 180(days of work)
of ≤, = or ≥).
and x1 ≥ 0; x2 ≥ 0
These restrictions are called
constraints
Mathematics for Electronics Engineers
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on
geometric concepts that requires LP problems to be presented in the standard
form:

(€/yr)
Max: Z = 90 x1 + 120 x2
• 1) Objective function is maximized
• 2) Constraints in the form of ≤ Subject to:
inequalities x1 ≤ 40(ha of pine)
x2 ≤ 50(ha of eucalypt)
2x1 + 3x2 ≤ 180(days of work)
• 3) All values on the right handside are ≥
and x1 ≥ 0; x2 ≥ 0
• 4) All variables are nonnegative (≥)
Mathematics for Electronics Engineers
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on
geometric concepts that must be translated into algebraic language to allow solving
systems of equations.

1st - transform all inequalities into equalities by introducing one additional

variable to each constraint (the slack variables: S1, S2, S3).
Original form: Standard or augmented form:

Max: Z = 90 x1 + 120 x2 Max: Z = 90 x1 + 120 x2

Subject to: Subject to:

x1 + S1 ≤ 40 x1 + S1 = 40
x2 + S2 ≤ 50 x2 + S2 = 50
2x1 + 3x2 + S3 ≤ 180 2x1 + 3x2 + S3 = 180

and x1 x2 S1 S2 S3 ≥ 0 and x1 x2 S1 S2 S3 ≥ 0
Mathematics for Electronics Engineers
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on
geometric concepts that must be translated into algebraic language to allow solving
systems of equations.

1st - transform all inequalities into equalities by introducing one additional

variable to each constraint (the slack variables: S1, S2, S3).
2nd - transform the objective function into an additional constraint

Max: Z = 90 x1 + 120 x2

Subject to: Z - 90 x1 - 120 x2 = 0

x1 + S1 = 40 x1 + S1 = 40
x2 + S2 = 50 x2 + S2 = 50
2x1 + 3x2 + S3 = 180 2x1 + 3x2 + S3 = 180
and x1 , x2 , S1 , S2 , S3 ≥ 0
Mathematics for Electronics Engineers
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on
geometric concepts that must be translated into algebraic language to allow solving
systems of equations.
1st - transform all inequalities into equalities by introducing one additional
variable to each constraint (the slack variables: S1, S2, S3).
2nd - transform the objective function into an additional constraint
3rd - build the Simplex tabular form where only the essential information is
recorded

Z - 90 x1 - 120 x2 = 0
x1 + S1 = 40
x2 + S2 = 50
2x1 + 3x2 + S3 = 180
Mathematics for Electronics Engineers
Simplex Method - Formulation
The Simplex algorithm is an algebraic procedure to solve LP problems based on
geometric concepts that must be translated into algebraic language to allow solving
systems of equations.
1st - transform all inequalities into equalities by introducing one additional
variable to each constraint (the slack variables: S1, S2, S3).
2nd - transform the objective function into an additional constraint
3rd - build the Simplex tabular form where only the essential information is
recorded
Each basic feasible solution has basic
or non-basic variables
- non-basic variables are set to ZERO
- basic variables are directly obtained
from the table
initialize the procedure setting x1 = x2 =
Basic 0
Non-basic
variables variables (X1, X2, S1, S2, S3 ) =( 0, 0, 40, 50, 180)
Mathematics for Electronics Engineers
Simplex Method - Graphical analysis
• The Simplex algorithm is a search procedure that:
- shifts through the set of basic feasible solutions, one at a time, until the
optimal basic feasible solution (whenever it exists) is identified.
- the method is an efficient implementation the Corner Points Procedure.

Corner point feasible solutions

B= C= – vertices of the feasible region
(0,50) (15,50)

Optimal solution(s) – vertice(s)

D= (40,33) of the feasible region that
maximize Z, ie solution that gives
A= (0,0) E= (40,0) the best favorable value to the
objective function
Mathematics for Electronics Engineers
Simplex Method - Graphical analysis
• The Simplex algorithm is a search procedure that:
- shifts through the set of basic feasible solutions, one at a time, until the
optimal basic feasible solution (whenever it exists) is identified.
- the method is an efficient implementation the Corner Points Procedure.

Replacing X1 and X2 by the values of A,

B= C= B, C, D and E in the objective function:
(0,50) (15,50)
ZA= 0
D= (40,33)
ZB= 6000
ZC= 7350 Z = 90 x1 + 120 x2
A= (0,0) E= (40,0) ZD= 7600
ZE = 3600
Mathematics for Electronics Engineers
Simplex Method - Graphical analysis
• The Simplex algorithm is a search procedure that:
- shifts through the set of basic feasible solutions, one at a time, until the
optimal basic feasible solution (whenever it exists) is identified.
- the method is an efficient implementation the Corner Points Procedure.
Feasible solutions – within or
B= C= on the border of the feasible
(0,50) (15,50) region ie solutions for which the
constraints are satisfied
D= (40,33.3)
Infeasible solution – outside the
A= (0,0) E= (40,0)
feasible region, ie solution for
which at least one constraint is
violated
Mathematics for Electronics Engineers
Simplex Method - Formulation
Bring the LP problem to the standard form -> obtain a BFS ie set A= (x1, x2) = (0, 0)

Optimality check No Find another feasible solution

Find in which direction to move towards the algebraic

equivalent of an extreme point ie a Basic Feasible Solution
B=
(0,50)
C= (15,50) with a single different basic variable
Swap the
A = (X , Xnon-basic
, S , S , variable with one of the basic variables
A is adjacent to B but not to C
1 2 1 2 B is adjacent to both A and C
D= (40,33) S3 ) Gaussian elimination to transform
Apply the new basic
= ( 0, 0, 40, 50,
variable
180) to (0,1) while solving for Z A B C
A= (0,0) E= (40,0)
B = (X1, X2, S1, S2, basic S1, S2, S1, X2, S3 X1, X2, S2
S ) S3
3
= ( 0, 50, 40, 0, non- X1, X2 X1, S2 S1, S3
30) basic
C = (X1, X2, S1, S2,
S )
Mathematics for Electronics Engineers
Simplex Method - Procedure
Bring the LP problem to the standard form -> obtain a BFS ie set (x1, x2) = (0, 0)
Optimality check:
The current BFS is optimal (in a No Find another feasible solution
max LP) if every coefficient in
Row 0 is ≥ 0.
Entering variable: Choose the entering variable (in a max problem) to be the NBV with
the most negative coefficient in Row 0. Ties may be broken in an arbitrary fashion.
Yes
Leaving BV: apply minimum ratio test - identify the row with the smallest ratio RHS
/aij (the most restrictive Row); the BV for this row is the leaving BV (it becomes
nonbasic).
Apply Gauss-Jordan elimination procedure to solve the system of linear equations.

Optimal feasible solution found – STOP SIMPLEX

Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

-120 -> 0

3 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure
Mathematics for Electronics Engineers
Simplex Method - Procedure

Z = 6000 X1 = 0
S1 = 40 S2 = 0
X2 = 50
S3 = 30

(x1, x2) = (0,50) (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30)

X1 = 0 ⬄ Plant 0 ha of pine
X2 = 50 ⬄ Plant 50 ha of eucalypt
S1 = 40 ⬄ 40 ha of area available for pine plant
S2 = 0 ⬄ no ha of area available for eucalypt
plant.
S3 = 30 ⬄ 30 working hours still available
Mathematics for Electronics Engineers
Simplex Method - Procedure
(x1, x2) = (0,0) (x1, x2, S1, S2, S3) = (0, 0, 40, 50,
180)

Z = 6000 X1 = 0
S1 = 40 S2 = 0
X2 = 50
S3 = 30

(x1, x2) = (0,50) (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30)

The basic variables in these solutions differ in

one single variable (S1 and S3 are maintained
as basic variables)

These are adjacent solutions

Mathematics for Electronics Engineers
Simplex Method - Procedure
(x1, x2) = (0,0) (x1, x2, S1, S2, S3) = (0, 0, 40, 50,
180)

Z = 6000 X1 = 0
S1 = 40 S2 = 0
X2 = 50
S3 = 30

(x1, x2) = (0,50) (x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30)

B= C= (15,50)
(0,50)

D= (40,33)

A= (0,0) E= (40,0)
Mathematics for Electronics Engineers
Optimality check:
Simplex Method - Procedure The current BFS is optimal (in a
max LP) if every coefficient in
Row 0 is ≥ 0.

X1 will become basic

S3 will become non-basic variable

(X1 column will have to take the shape of

S3: (0, 0, 0, 1)
Mathematics for Electronics Engineers
Simplex Method - Procedure
Mathematics for Electronics Engineers
Simplex Method - Procedure

-90 -> 0
1 -> 0
Mathematics for Electronics Engineers
Simplex Method - Procedure

Z = 7350 S2 = 0
S1 = 25 S3 = 0
X2 = 50
x1 = 15

(x1, x2) = (0,0) (x1, x2, S1, S2, S3) = (0, 0, 40, 50, 180) z=0
(x1, x2) = (0,50) (A)
(x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30) z=6000
(x1, x2) = (15,50) (B)
(x1, x2, S1, S2, S3) = (15, 50, 25, 0, 0) z=7350
(C)
B= C= (15,50)
(0,50)
X1 = 15 ⬄ Planted 15 ha of pine
X2 = 50 ⬄ Planted 50 ha of eucalypt
S1 = 25 ⬄ 25 ha of area available for pine plant.
D= (40,33)
S2 = 0 ⬄ no ha of area available for eucalypt
plant.
S3 = 0 ⬄ no working hours available A= (0,0) E= (40,0)
Mathematics for Electronics Engineers
Optimality check:
Simplex Method - Procedure The current BFS is optimal (in a
max LP) if every coefficient in
Row 0 is ≥ 0.

S2 will become basic Entering variable: the most negative coefficient in Row 0
S1 will become non-basic variable
Leaving BV: the smallest positive ratio RHS /aij
(S2 column will have to take the shape of
S1: (0, 1, 0, 0)
Mathematics for Electronics Engineers
Optimality check:
Simplex Method - Procedure The current BFS is optimal (in a
max LP) if every coefficient in
Row 0 is ≥ 0.

S2 will become basic

S1 will become non-basic variable

(S2 column will have to take the

shape of S1: (0, 1, 0, 0)
Mathematics for Electronics Engineers Optimality check:
The current BFS is optimal (in a

Simplex Method - Procedure max LP) if every coefficient in

Row 0 is ≥ 0.

OPTIMAL
SOLUTION!

Z = 7600 S1 = 0
S2 = 16.67 S3 = 0
X2 = 33.33
x1 = 40

(x1, x2) = (0,0) (x1, x2, S1, S2, S3) = (0, 0, 40, 50, 180) z=0
(x1, x2) = (0,50) (A)
(x1, x2, S1, S2, S3) = (0, 50, 40, 0, 30) z=6000
(x1, x2) = (15,50) (B)
(x1, x2, S1, S2, S3) = (15, 50, 25, 0, 30) z=7350 (C)
(x1, x2) = (x1, x2, S1, S2, S3) = (40, 33.33, 0, 16.67, 0) z=7600
B= C= (15,50)
(40,33.33) (D)
(0,50)
X1 = 40 ⬄ Planted 40 ha of pine
X2 = 33.33 ⬄ Planted 33.33 ha of eucalypt
S1 = 0 ⬄ 0 ha of area available for pine plant. D= (40,33)
S2 = 16.67 ⬄ 16.67 ha of area available for eucalypt plant.
S3 = 0 ⬄ no working hours available A= (0,0) E= (40,0)
Mathematics for Electronics Engineers
Simplex Method – Graphical approach
Graphical Method Simplex Method

▪ Replace each inequality by an equality

▪ Find the set of points satisfying the equality (allows to draw a line that cuts the plane into 2 half-planes)
▪ Find which half-plane satisfies the inequality
▪ Intercept all the half-plane areas to find the feasible region (FR) – feasible solutions = (x1, x2) corners
▪ Draw iso-lines for the objective function to find the optimal solution: (x1, x2) corner point of the FR
Mathematics for Electronics Engineers
Simplex Method – Graphical approach
Simplex Method
Graphical Method

▪ Replace each inequality by an equality adding a slack variable

▪ Transform the objective function into an equality
▪ Build a table for the constraints only specifying the coefficients
▪ Replace each inequality by an equality
▪ Set x1 and x2 to ZERO =>x1=0; x2=0; S1=40; S2=50; S3=180
▪ Find the set of points satisfying the equality
(allows to draw a line that cuts the plane into 2
half-planes) ▪ Test different combinations of basic variables
Non-basic variables Basic variables
• Select the non-basic var. that results in a bigger increase in Z
▪ Find which half-plane satisfies the inequality (the smallest coefficient in R0)
▪ Intercept all the half-plane areas to find the • Select the basic var. that guarantees the biggest increase in Z
feasible region (FR) – feasible solutions = (x1, without leaving the feasible region and that all basic variables
x2) corners are nonnegative (smallest positive ratio)
• Gaussian elimination so that the new basic var. only has: 0,1
▪ Draw iso-lines for the objective function to find • Test optimality: all coeff. in R0 >=0? If not, test new
the optimal solution: (x1, x2) corner point of the combination
FR
Mathematics for Electronics Engineers
Simplex Method – Particular cases
• Tie for the Entering BV:
– Entering variable: Choose the entering variable (in a max problem) to be the
NBV with the most negative coefficient in Row 0.

– What to do when there is a tie for the entering basic variable ? Selection
made arbitrarily.
Mathematics for Electronics Engineers
Simplex Method – Particular cases
• Tie for the Leaving BV - Degenerate:
– Leaving BV: apply minimum ratio test - identify the row with the smallest
positive ratio bi /aij (the most restrictive Row); the BV for this row is the leaving
BV (it becomes nonbasic).

- Choose the leaving

variable arbitrary
- basic variables with a
value of zero are called
degenerate
- continue the Simplex
procedure until
optimality is reached
Mathematics for Electronics Engineers
Simplex Method – Particular cases
• No leaving BV – Unbounded Z:
Occurs if all the coefficients in the pivot column (where the entering basic variable is) are either
negative or zero (excluding row 0)

No solution – when the constraints do not prevent improving the objective function indefinitely
Mathematics for Electronics Engineers
Simplex Method – Particular cases
• Multiple optimal solutions:
When a NBV has a zero coefficient in row
0, then we perform one more iteration
to identify the other optimal BF solution.
Mathematics for Electronics Engineers
Simplex Method - exercises
• 1) A company produces 3 different products: A, B and C. Each product has to go under
3 processes consuming different amounts of time along the way. The time available for
each process is described in the table below.
Total number Number of hours needed to produce
Process of hours each product
available A B C
I 12000 5 2 4
II 24000 4 5 6
III 18000 3 5 4

Assuming the selling profits for products A, B and C are 2, 3 and 4€ per unit. Determine
how many units of each product should be produced to maximize the profit.
Was there any time left?
Mathematics for Electronics Engineers
Simplex Method - exercises
• 2) A company produces 3 diferente bookshelves: a luxury, a regular and na exportation
model. Consider the maximum demand for each model to be 500, 750 and 400
respectively. The working hours at the carpentry and finishing sections have the
working time limitations below:
Section Total number Number of hours needed to produce each model
of hours
(thousands) luxury regular exportation

carpentry 1.4 0.5 0.5 1.0

finishing 1.2 0.5 0.5 2.0

Assuming the selling profit for the luxury, regular and exportation models is 1500, 1300
2500 respectively, formulate the LP problema in order to maximize the profit.
Interpret the results detailling the optimal number of bookshelves of each type produced
discussing the total amount of hours used in each section. How far from meeting the
maximum demands were we?
Mathematics for Electronics Engineers
Simplex Method - exercises
• 3)
Max: Z = x1 + 2 x2 • 4) Max: Z = x1 + x2
Subject to: Subject to:
2x1 + 4x2 ≤ 20 x1 + x2 ≤ 4
x1 + x2 ≤ 8 2 x1 + x2 ≤ 6
and x1 x2 ≥ 0 x1 + 2 x2 ≤ 6
and x1 x2 ≥ 0

• 5) Max: Z = x1 + x2
Subject to:
x1 + x2 ≤ 10
Apply the Simplex to find the optimal
2 x1 - 3 x2 ≤ 15
solution
x1 - 2 x2 ≤ 20
Multiple, unbound and degenerate
and x1 x2 ≥ 0
solutions
Mathematics for Electronics Engineers
Simplex Method - exercises
• 6) Min: Z = 2 x1 - 3 x2 – 4 x3 • 7) Max: Z = 10 x1 + 30 x2
Subject to: Subject to:
x1 + 5 x2 - 3 x3 ≤ 15 x1 ≤ 15
x1 + x2 + x3 ≤ 11 x1 - x2 ≤ 20
5 x1 – 6 x2 + x3 ≤ 4 -3 x1 + x2 ≤ -30
and x1 x2 x3 ≥ 0 and x1 ≥ 0 x2 ≤ 0

• 8) Max: Z = - x2
Subject to:
x1 + x2 + x3 ≤ 100 Bring the following PL problems to standard form
and apply the Simplex to find the optimal solution
x1 - 5 x2 ≤ 40
x3 ≥ -10 Minimization, negative RHS, negative and
and x1 ≥ 0 x2 ≤ 0 x3 unbounded variables
unbounded
Mathematics for Electronics Engineers
Simplex Method - exercises
• 9) Min: Z = 4 x1 + 2 x2 • 10) Max: Z = x1 + 2 x2
Subject to: 2 x1 - x2 ≥ 4 Subject to: x1 + x2 ≤ 10
x1 + x2 ≥ 5 x1 - 2 x2 ≥ 6
x1, x2 ≥ 0 x1, x2 ≥ 0

Bring the following PL problems to standard form introducing

artificial variables apply the big M method using Simplex to find
the optimal solutions
 THANK YOU

Department of Electronics & Communication

Engineering