‫ﻛﻠﯿﺔ اﻟﻜﻨﻮز اﻟﺠﺎﻣﻌﺔ‬

‫ﻗﺴﻢ ھﻨﺪﺳﺔ ﺗﻘﻨﯿﺎت اﻟﺤﺎﺳﻮب‬

Project Management
Chapter 8
Linear Programming Simplex Method
4th Stage
Fall Semester 2023 – 2024
Prof. Dr. Taleb Obaid
 Simplex Method
THE SIMPLEX METHOD
1. Set up the problem. That is, write the objective function
and the inequality constraints.
2. Convert the inequalities into equations. This is done by
adding one slack variable for each inequality.
3. Construct the initial simplex tableau. Write the objective
function as the bottom/above row.
4. The most negative entry in the objective row identifies the
pivot column.
Prof. Dr. Taleb Obaid 2
 Simplex Method
THE SIMPLEX METHOD … cont..
5. Calculate the quotients (RHS/Pivot column) ‫ﺣﺎﺻﻞ اﻟﻘﺴﻤﺔ‬. The smallest
quotient identifies a row. The element in the intersection of the column
identified in step 4 and the row identified in this step is identified as
the pivot element. The quotients are computed by dividing the far right
column by the identified column in step 4. A quotient that is a zero, or a
negative number, or that has a zero in the denominator, is ignored.
6. Perform pivoting to make all other entries in this column zero. This is
done the same way as we did with the Gauss-Jordan method.
7. When there are no more negative entries in the objective row, we are
finished; otherwise, we start again from step 4

Prof. Dr. Taleb Obaid 3

 Simplex Method
Basic Feasible Solution (BFS) are of two types:
•Degenerate BFS: If one or more basic variables are
zero.
•Non-Degenerate BFS: All basic variables are non-zero.
•Optimal BFS: which optimizes the objective function.

Prof. Dr. Taleb Obaid 4

 Simplex Method
Miki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12
hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of
preparation time, and for every hour she works at Job II, she needs one hour of preparation time,
and she cannot spend more than 16 hours for preparation. If she makes $40 an hour at Job I, and
$30 an hour at Job II, how many hours should she work per week at each job to maximize her
income?

Solution
STEP 1. Set up the problem. Write the objective function and the constraints.
Maximize Z=40x1+30x2
Subject to:
x1+x2 ≤12
2x1+x2 ≤16
x1≥0; x2≥0

Prof. Dr. Taleb Obaid 5

 Simplex Method
STEP 2. Convert the inequalities into equations If we arbitrarily choose X1=0 and X2=0,
After adding the slack variables, our we get
problem reads S1 S2 Z RHS
Objective function Z− 40x1−30x2=0 1 0 0 12
Subject to constraints: 0 1 0 16
x1+x2 +S1=12 0 0 1 0
2x1+x2 +S2=16
x1≥0; x2≥0 which reads
STEP 3. Construct the initial simplex tableau
X1 X2 S1 S2 Z RHS S1=12, S2=16, Z=0
1 1 1 0 0 12
2 1 0 1 0 16
40- 30- 0 0 1 0
Prof. Dr. Taleb Obaid 6
 Simplex Method
STEP 4. The most negative entry in the bottom row identifies the pivot column.
•The most negative entry in the bottom row is -40; therefore the column 1 is identified.

•Question Why do we choose the most negative entry in the bottom row?
•Answer The most negative entry in the bottom row represents the largest coefficient in
the objective function - the coefficient whose entry will increase the value of the objective
function the quickest.
Prof. Dr. Taleb Obaid 7
 Simplex Method
STEP 5. Calculate the quotients.
The smallest quotient identifies a row. The element in the intersection
of the column identified in step 4 and the row identified in this step is
identified as the pivot element.
•Following the algorithm, in order to calculate the quotient, we divide
the entries in the far right column by the entries in column 1, excluding
the entry in the bottom row.

Pivot element

Prof. Dr. Taleb Obaid 8

 Simplex Method
•Question Why do we find quotients, and why does the smallest
quotient identify a row?
• Answer When we choose the most negative entry in the bottom row,
we are trying to increase the value of the objective function by
bringing in the variable x1.

•Question Why do we identify the pivot element?

•Answer . The value of the objective function is improved by changing
the number of units of the variables. We may add the number of units
of one variable, while throwing away the units of another. Pivoting
allows us to do just that.
Prof. Dr. Taleb Obaid 9
 Simplex Method
•The variable whose units are being added is called
the entering variable, and the variable whose units
are being replaced is called the departing variable.
The entering variable in the above table is x1, and it
was identified by the most negative entry in the
bottom row. The departing variable y2 was identified
by the lowest of all quotients.

Prof. Dr. Taleb Obaid 10

 Simplex Method
STEP 6. Perform pivoting to make all other entries in this column zero.
Pivoting is a process of obtaining a one (1) in the location of the pivot
element, and then making all other entries zeros in that column. So
now our job is to make our pivot element a 1 by dividing the entire
second row by 2. The result follows.

R2=R2/2

•To obtain a zero in the entry first above the pivot element, we
multiply the second row by -1 and add it to row 1. We get

Prof. Dr. Taleb Obaid 11

 Simplex Method

R1=R1-R2

•To obtain a zero in the element below the pivot, we multiply the second row by
40 and add it to the last row.

R3=R3+R2(40)

Prof. Dr. Taleb Obaid 12

 Simplex Method
STEP 7. When there are no more negative entries in the bottom row,
we are finished; otherwise, we start again from step 4.
•Since there is still a negative entry, -10, in the bottom row, we need
to begin, again, from step 4. This time we will not repeat the details of
every step, instead, we will identify the column and row that give us
the pivot element, and highlight the pivot element. The result is as
follows.

Prof. Dr. Taleb Obaid 13

 Simplex Method
•We make the pivot element 1 by multiplying row 1 by 2, and we get

R1=2*R1

Now to make all other entries as zeros in this column, we first multiply row 1 by
-1/2 and add it to row 2, and then multiply row 1 by 10 and add it to the bottom
row.

R1=R1
R2=R2-R1/2
R3=R3+R1*10 , x1=4, x2=8, z=400 (=40*4+30*8)
We no longer have negative entries in the bottom row, therefore we are finished
Prof. Dr. Taleb Obaid 14
 Simplex Method
• When decision variables are more than 2, we always use Simplex Method
• Slack Variable: Variable added to a ≤ constraint to convert it to an equality
(=).
❑ A slack variable represents unused resources

❑ A slack variable contributes nothing to the objective function value.

• Surplus Variable: Variable subtracted from a ≥ constraint to convert it to

an equality (=).
❑ A surplus variable represents an excess above a constraint requirement level.
❑ Surplus variables contribute nothing to the calculated value of the objective function.
Prof. Dr. Taleb Obaid 15
 Simplex Method
Basic Solution(BS) : This solution is obtained by setting any n variables
(among m+n variables) equal to zero and solving for remaining m
variables, provided the determinant of the coefficients of these
variables is nonzero. Such m variables are called basic variables and

remaining n zero valued variables are called non basic variables.

Basic Feasible Solution(BFS) : It is a basic solution which also satisfies

the non negativity restrictions.

Prof. Dr. Taleb Obaid 16

 Simplex Method
BFS are of two types:

❑ Degenerate ‫ ﻣﻨﺤﻞ‬BFS: If one or more basic variables are zero.

❑ Non-Degenerate BFS: All basic variables are non-zero.

Optimal BFS: BFS which optimizes the objective function.

Prof. Dr. Taleb Obaid 17

 Simplex Method
Example

Max Z = 13x1 + 11x2

Subject to

4x1 + 5x2 ≤ 1500

5x1 + 3x2 ≤ 1575
x1 + 2x2 ≤ 420

x1 , x2 ≥ 0

Prof. Dr. Taleb Obaid 18

 Simplex Method
Solution

Step 1: Convert all the inequality constraints into equalities by the use
of slack variables. Let s1, s2 , s3 be three slack variables.

Introducing these slack variables into the inequality constraints 3

and rewriting the objective function such that all variables are on the
left-hand side of the equation. Model can rewritten as:

Prof. Dr. Taleb Obaid 19

 Simplex Method
Z – 13x1 – 11x2 = 0

Subject to

4x1 + 5x2 + s1 = 1500

5x1 + 3x2 + s2 = 1575
x1 + 2x2 + s3 = 420

x1 , x2 , s2 , s3 , s3 ≥ 0

Prof. Dr. Taleb Obaid 20

 Simplex Method
Step II: Find the Initial BFS.

One Feasible solution that satisfies all the constraints is: x1= 0, x2= 0,
s1=1500, s2 = 1575, s3 =420 and Z = 0.

Now s1, s2, s3 are Basic variables

Step III: Set up an initial table as:

Prof. Dr. Taleb Obaid 21

 Simplex Method

Row Basic Coefficients of :Ratio

Sol
No Variable Z X1 X2 S1 S2 S3 Sol/cof (X1)

A1 Z 1 13- 11- 0 0 0 0
B1 S1 0 4 5 1 0 0 1500 1500/4=375
C1 S2 0 5 3 0 1 0 1575 1575/5= 315
D1 S3 0 1 2 0 0 1 420 420/1= 420

Prof. Dr. Taleb Obaid 22

 Simplex Method
•

Prof. Dr. Taleb Obaid 23

 Simplex Method
Divide the row pivot by pivot element, and subtract multiples of this row from the other rows.

Coefficients of
Basic
Row No C Sol
Variable
Z X1 X2 S1 S2 S3

A1 Z 1 13- 11- 0 0 0 0 A1=A1-(-13) A1

B1 S1 0 4 5 1 0 0 1500 B1=B1-4*A1

=1575/5
C1=C1/5 S2 0 1 3/5 0 1/5 0
315

D1 S3 0 1 2 0 0 1 420 D1=D-1*A1

Prof. Dr. Taleb Obaid 24

 Simplex Method

Coefficients of
Row Basic
Sol Ratio
No Variable
Z X1 X2 S1 S2 S3

A1 Z 1 0 16/5- 0 13/5 0 4095

B1 S1 0 0 13/5 1 4/5- 0 240 92.3

C1 X1 0 1 3/5 0 1/5 0 315 525
D1 S3 0 0 7/5 0 1/5- 1 105 75

Prof. Dr. Taleb Obaid 25

 Simplex Method
Coefficients of
Row Basic
Sol
No Variable
Z X1 X2 S1 S2 S3

A1 Z 1 0 16/5- 0 13/5 0 4095

B1 S1 0 0 13/5 1 4/5- 0 240

C1 X1 0 1 3/5 0 1/5 0 315
D1 S3 0 0 7/5 0 1/5- 1 105

Prof. Dr. Taleb Obaid 26

 Simplex Method
Coefficients of
Row Basic
Sol
No Variable
Z X1 X2 S1 S2 S3

A1 Z 1 0 -16/5 0 13/5 0 4095 A1=A1+D1*16/5

B1 S1 0 0 13/5 1 -4/5 0 240 B1=B1-D1*13/5

C1 X1 0 1 3/5 0 1/5 0 315 C1=C1-D1*3/5

D1 S3 0 0 1 0 75

Prof. Dr. Taleb Obaid 27

 Simplex Method
Coefficients of
Row Basic
Sol Ratio
No Variable
Z X1 X2 S1 S2 S3

A1 Z 1 0 0 0 15/7 16/7 4335

B1 S1 0 0 1 1 3/7- 13/7- 45 92.3

C1 X1 0 1 0 0 2/7 3/7- 270 525
D1 X2 0 0 1 0 1/7- 5/7 75 75

No negative Z coefficient , so the Optimal Solution is: x1=270, x2=75, Z=4335

Prof. Dr. Taleb Obaid 28
 Simplex Method
Example:
Max Z = 3X1 + 5X2 + 4X3
S. t.
2X1 + 3X2 ≤8
2X2 + 5X3 ≤ 10
3X1 + 2X2 + 4X3 ≤ 15
X1, X2, X3 ≥ 0

Prof. Dr. Taleb Obaid 29

 Simplex Method
Let S1, S2, S3 be the slack variables. Modified form is:

Z - 3X1 - 5X2 - 4X3 = 0

S. t.
2X1 + 3X2 + S1 = 8
2X2 + 5X3 + S 2 = 10
3X1 + 2X2 + 4X3 + S3 = 15
X1, X2, X3, S1, S2, S3 ≥ 0
Initial BFS is: X1= 0, X2= 0, X3= 0, S1=8, S2= 10, S1=15 and Z=0.

Prof. Dr. Taleb Obaid 30

 Simplex Method
Coefficients of
Basic
Variable
Sol Ratio
Z X1 X2 X3 S1 S2 S3

Z 1 3- 5- 4- 0 0 0 0

S1 0 2 3 0 1 0 0 8 8/3

S2 0 0 2 5 0 1 0 10 5

S3 0 3 2 4 0 0 1 15 15/2

Prof. Dr. Taleb Obaid 31

 Simplex Method
Coefficients of
Basic
Variable
Sol Ratio
Z X1 X2 X3 S1 S2 S3

Z 1 1/3 0 4- 5/3 0 0 40/3

X2 0 2/3 1 0 1/3 0 0 8/3

S2 0 4/3- 0 5 2/3- 1 0 14/3 14/15

S3 0 5/3 0 4 2/3- 0 1 29/3 29/12

Prof. Dr. Taleb Obaid 32

 Simplex Method
Coefficients of
Basic
Variable
Sol Ratio
Z X1 X2 X3 S1 S2 S3

Z 1 11/15- 0 0 17/15 4/5 0 256/15

X2 0 2/3 1 0 1/3 0 0 8/3 4

X3 0 4/3- 0 1 2/3- 1/5 0 14/3 -

S3 0 41/15 0 0 2/15 4/5- 1 89/15 89/41

Prof. Dr. Taleb Obaid 33

 Simplex Method
Coefficients of
Basic
Variable
Sol Ratio
Z X1 X2 X3 S1 S2 S3

Z 1 0 0 0 45/41 24/41 11/41 765/41

X2 0 0 1 0 15/41 8/41 -10/41 50/41

X3 0 0 0 1 -6/41 5/41 4/41 62/41

X1 0 1 0 0 -2/41 -12/41 15/41 89/41

Prof. Dr. Taleb Obaid 34

 Simplex Method
Min Z = X1 – 3X2 + 2X3
S. t.
3X1 – X2 + 3X3 ≤ 7
-2X1 + 4X2 ≤ 12
-4X1 + 3X2 + 8X3 ≤ 10
X1 , X 2 , X 3 ≥ 0

Prof. Dr. Taleb Obaid 35

 Simplex Method
Convert the problem into maximization problem

Max Z’ = - X1 + 3X2 - 2X3 where Z’ = - Z

S. t.

3X1 – X2 + 3X3 ≤ 7

-2X1 + 4X2 ≤ 12

-4X1 + 3X2 + 8X3 ≤ 10

X1 , X 2 , X 3 ≥ 0

Prof. Dr. Taleb Obaid 36

 Simplex Method
Let S1, S2 and S3 be three slack variables. Modified form is:

Max Z’ + X1 - 3X2 + 2X3 = 0

3X1 – X2 + 3X3 + S1 = 7

-2X1 + 4X2 + S2 = 12

-4X1 + 3X2 + 8X3 + S3 = 10

X1 , X 2 , X 3 ≥ 0

Initial BFS is : X1 = 0, X2 = 0, X3 = 0, S1 = 7, S2 =12, S3=10, Z = 0

Prof. Dr. Taleb Obaid 37

 Simplex Method
Coefficients of
Basic
Variable
Sol Ratio
Z’ X1 X2 X3 S1 S2 S3

Z’ 1 1 -3 2 0 0 0 0

S1 0 3 -1 3 1 0 0 7 -

S2 0 -2 4 0 0 1 0 12 3

S3 0 -4 3 8 0 0 1 10 10/3

Prof. Dr. Taleb Obaid 38

 Simplex Method
Coefficients of
Basic
Variable
Sol Ratio
Z’ X1 X2 X3 S1 S2 S3

Z’ 1 -1/2 0 2 0 3/4 0 9 4

S1 0 5/2 0 3 1 1/4 0 10

X2 0 -1/2 1 0 0 1/4 0 3

S3 0 -5/2 0 8 0 -3/4 1 1

Prof. Dr. Taleb Obaid 39

 Simplex Method
Coefficients of
Basic
Variable
Sol Ratio
Z’ X1 X2 X3 S1 S2 S3

Z’ 1 0 0 13/5 1/5 8/10 0 11

X1 0 1 0 6/5 2/5 1/10 0 4

X2 0 0 1 3/5 1/5 3/10 0 5

S3 0 0 0 11 1 1 1 11

Prof. Dr. Taleb Obaid 40

 Simplex Method
Max Z = 3 X1 + 4 X2

S.t.

X1 – X2 ≤ 1
-X1 + X2 ≤ 2
X1, X2 ≥ 0

Prof. Dr. Taleb Obaid 41

 Simplex Method
Let S1 and S2 be two slack variables

Modified form is:

Z - 3 X1 - 4 X2 = 0

S.t.

X1 – X 2 + S 1 = 1
-X1 + X2 + S2 = 2
X1, X2 , S1, S2 ≥ 0
Initial BFS is : X1=0, X2=0 , S1=1, S2=1 ≥ 0, and Z=0

Prof. Dr. Taleb Obaid 42

 Simplex Method

Coefficients of
Basic
Sol Ratio
Variable
Z X1 X2 S1 S2

Z 1 3- 4- 0 0 0

S1 0 1 1- 1 0 1 -

S2 0 1- 1 0 1 2 2

Therefore, X2 is the entering variable and S2 is the departing variable.

Prof. Dr. Taleb Obaid 43
 Simplex Method

Coefficients of
Basic
Sol Ratio
Variable
Z X1 X2 S1 S2

Z 1 7- 0 0 4 8

S1 0 0 0 1 1 3 -

X2 0 1- 1 0 1 2 -

X1 is the entering variable, but as in X1 column every no, is less than equal
to zero, ratio cannot be calculated. Therefore given problem is having a
unbounded solution
Prof. Dr. Taleb Obaid 44
 Simplex Method
Graphically,
X2
Max Z = 3 X1 + 4 X2
S.t.
X1 – X2 ≤ 1
-X1 + X2 ≤ 2
X1, X2 ≥ 0 (0,2)

(0,1)
(0,-2) (0, -1) X1
(0, 0)

Prof. Dr. Taleb Obaid 45